4568

Использование параллелизма процессора для повышения эффективности программ

Лабораторная работа

Информатика, кибернетика и программирование

Использование параллелизма процессора для повышения эффективности программ Цель работы: научить студента самостоятельно разрабатывать максимально эффективные программы. Материал для изучения. Рассмотрим задачу умножения двух n ...

Русский

2012-11-22

35.5 KB

6 чел.

Использование параллелизма процессора для повышения эффективности программ

Цель работы: научить студента самостоятельно разрабатывать максимально эффективные программы.

Материал для изучения.

Рассмотрим задачу умножения двух n n квадратных  матриц: С = АВ.

Элементы матриц хранятся по строкам, а именно сначала хранятся элементы первой строки, затем второй и т.д.

Таким образом. Последовательнее элементы строки матрицы лежат друг за другом и доступ к ним будет максимально быстрым. Так как стратегия предвыборки элементов в кэш (т.е. чтение каждый раз целого блока оперативной памяти, равного по размеру строке кэша) себя полностью оправдывает. С другой стороны, последовательные элементы столбца матрицы лежат на расстоянии n* sizeof(double) байт друг от друга и доступ к ним будет максимально медленным (поскольку строка кэш-памяти существенно меньше расстояния между элементами).

Вычислим произведение матриц несколькими способами.

1. Стандартный способ. Цикл проведем по строкам матрицы.

для всех   m = 1, 2,…,n

для всех i = 1, 2,,n

 вычислить

В цикле по j (вычисление суммы) элементы одной строки матрицы А (к которым быстрый доступ) будут использованы многократно (в цикле по i), элементы же столбцов матрицы В (к которым относительно медленный доступ) повторно (в цикле по i) не используются. Тем самым при доступе к элементам В кэш-память  практически ничего не дает.

2. Цикл по столбцам матрицы.

для всех   m = 1, 2,…,n

для всех i = 1, 2,…,n

 вычислить

В цикле по j  (вычисление суммы) элементы матрицы А повторно (в цикле по i) не используются. Элементы же столбцов матрицы В используются много кратно (в цикле по i). Кэш память ускоряет доступ к элементам А за счет предвыборки подряд идущих элементов, и ускоряет доступ к элементам В, если столбец целиком поместился в кэш память (тогда в цикле по i обращение к элементам В в оперативной памяти будет только на первом шаге). Отметим, что если размер кэш памяти недостаточен (например n велико), то этот способ может оказаться хуже предыдущего, т.к. ухудшился способ доступа  к А и не получен выигрыш при доступе к В.

3. Третий метод.

Цикл проведем по N N, N=10 блокам матрицы С, внутри блока идем по столбцам.

для всех  bm = 1, 1+N, 1+2N, … ,    bm < n 

для всех bi = 1, 1+N, 1+2N, … ,    bi < n 

 для всех m= bm, bm+1, …, bm+N-1, m<n

   для всех i=bi, bi+1, … , bi+N-1, i < n

   вычислять  

В этом случае большой выигрыш в скорости получаем в том случае если используемые в циклах по m, i, j N строк матрицы А и N столбцов матрицы В поместились в кэш память. Если n  настолько велико что даже один столбец матрицы В не поместился целиком в кэш, то этот способ может оказаться хуже самого первого.

4.  Зададим параметр N таким, что n делится на N нацело. Тогда всякая матрица М может быть представлена:


Где  Mij – NN матрица, k=n/N. Тогда каждый блок Cim произведения С=АВ матриц А и В может быть вычислен через блоки матриц А и В.

 

В вычислении произведения NN матрица матриц Aij  и Bjm участвует только подмножество их N2 элементов матриц А и В . При небольшом N  это подмножество полностью поместится в кэш-памяти и каждое слагаемое послежней суммы быдет вычислено максимально быстро.

5. В предыдущих вариантах преимущества кэш-памяти почти уже были исчерпаны. Для получения дальнейшего прироста производительности вспомним о конвейерной организации процессора (современные процессоры имеют конвейер инструкций, достаточно глубокий). Для его заполнения длина линейного участка программы должна быть как минимум больше глубины конвейера (желательно в несколько раз ). Во всех предыдущих вариантах в самом внутреннем цикле (по j) находится оператор языка, который, в зависимости от целевого процессора, транслируется компилятором в 7 … 12 инструкций (включая операторы обслуживания цикла).  Для увеличения линейного участка программы в предыдущем варианте реализуем цикл следующим образом:

За один проход цикла по j будем вычислять сразу 4 элемента матрицы С – ci,m, ci,m+1, ci+1,m, ci+1,m+1. Поскольку при их вычислении используются повторяющиеся элементы матриц А и В, то также появляются дополнительные резервы для ускорения работы за счет оптимизации компилятора и кэш памяти.

Задание к лабораторной работе.

1. Запрограммировать алгоритмы умножения матриц.

2. Повести эксперименты на ЭВМ  с разными процессорами.

3. Построить таблицу соотношения скорости работы различных алгоритмов умножения матриц. (матрицы брать размерностью 10001000, 50005000, 1000010000 ). В таблицу заносить значения: отношения времени работы первого варианта к времени работы каждого из пяти вариантов.

4. Написать отчет.

5. Защитить у преподавателя.

Дополнительная литература:

Богачёв К.Ю. Основы параллельного программирования / К.Ю. Богачев. – М.: БИНОМ. Лаборатория знаний, 2003. – 342 с.


 

А также другие работы, которые могут Вас заинтересовать

29085. Результаты интеллектуальной деятельности (общая характеристика, виды, сроки охраны, правообладатели). Исключительные права и особенности их передачи 27.5 KB
  Результаты интеллектуальной деятельности общая характеристика виды сроки охраны правообладатели. Результатами интеллектуальной деятельности и приравненными к ним средствами индивидуализации юридических лиц товаров работ услуг и предприятий которым предоставляется правовая охрана интеллектуальной собственностью являются: произведения науки литературы и искусства; программы для электронных вычислительных машин; базы данных; фонограммы; селекционные достижения; фирменные наименования; товарные знаки и знаки обслуживания....
29086. Средства индивидуализации (общая характеристика, виды, сроки, особенности охраны, правообладатели) 27.5 KB
  Средства индивидуализации общая характеристика виды сроки особенности охраны правообладатели. Средство индивидуализации обозначение служащее для различения товаров услуг предприятий организаций и других объектов в сфере хозяйственного оборота. Виды средств индивидуализации: фирменное наименование наименование некоммерческой организации товарный знак знак обслуживания коммерческое обозначение наименование места происхождения товара доменное имя. Исключительные права на результаты интеллектуальной деятельности и на средства...
29087. Сделки (понятие, виды, условия действительности) 28.5 KB
  Сделки понятие виды условия действительности. Виды сделок: По количеству субъектов Односторонние завещание Многосторонние Двусторонние купля продажа По критерию встречности Возмездные аренда Безвозмездные дарение По способу закрепления Вербальные Литеральные По риску Алеаторные рисковые Нейтральные По особенностям механизма Под условием Без уловия Действительность сделки определяется законодательством посредством следующей системы условий: а законность содержания;б способность физических и юридических лиц...
29088. Гражданское право как отрасль права. Система гражданско-правовых институтов 25 KB
  Гражданское право как отрасль права. Отрасль гражданского права совокупностью правовых норм регулирующих имущественные и связанные с ними личные неимущественные отношения основанные на равенстве автономии воли и имущественной самостоятельности их участников а в случаях прямо предусмотренных действующим законодательством и на властном подчинении одной стороны другой а также защищающих неотчуждаемые права и свободы человека и другие нематериальные блага. Система гражданского права: Лица правоспособные дееспособные полная...
29089. Предмет гражданского права 27.5 KB
  Предметом гражданского права являются три группы отношений: 1 имущественные отношения – только товароденежные: отношения собственности и другие вещные отношения; отношения связанные с исключительными правами на результаты интеллектуальной деятельности отношения возникающие в рамках договорных и иных обязательств 2 относительно имущественные: отношения авторства на произведения науки литературы искусства изобретения результаты интеллектуальной деятельности 3 личные неимущественные отношения: отношения невозможно оценить в...
29090. Методология гражданского права. Приемы и методы гражданского права. Элементы юридической техники, применяемые в гражданском праве (отраслевые аксиомы, презумпции, фикции, юридические конструкции) 28.5 KB
  Методология гражданского права. Приемы и методы гражданского права. В методологию входят: Правопонимание нормативное психологическое историческое Методы общенаучные частнонаучные специальные Толкование интерпретация норм обычаев принципов права Отраслевая техника аксиомы презумпции фикции юридические конструкции договор сделка юр. лицо Методы гражданского права – способ регуляции или защиты: Общенаучные – анализ синтез системно структурный Частнонаучные – метод толкования права сравнительно – правовой...
29091. Принципы и функции гражданского права 34 KB
  Принципы и функции гражданского права. Принципы – руководящие основополагающие начал которыми должны находится в канве более конкретных положении. Особенности: Принципы связанны с интерпретацией толкования Принципы нужно выводить из действующих норм права Принцип действует на стадии правоприменения Виды принципов: свободу договора субъекты гражданского оборота свободны в решении вступления в договорные отношения или воздержания от заключения гражданскоправовых договоров; неприкосновенность собственности никто не может быть лишен...
29092. Источники гражданского права. Гражданское законодательство. Действие гражданских законов 37 KB
  Источники гражданского права. Источники гражданского права – внешнее выражение гражданскоправовых норм. Являются источниками гражданского права: Конституция РФ ГК РФ ФЗ и законы субъектов Подзаконные акты Указы президента Постановления правительства Ведомственные акты Общепризнанные принципы и нормы международного права Обычаи делового оборота Не являются источниками гражданского права постановления Пленумов Верховного Суда РФ постановления Высшего Арбитражного Суда РФ. При этом нормы гражданского права содержащиеся в других...
29093. Гражданское правоотношение (понятие, структура, виды) 31 KB
  Гражданское правоотношение это урегулированное нормами гражданского права правоотношение возникающее между юридически равными субъектами по поводу имущества а также нематериальных благ выражающаяся в наличие у них субъективных прав и обязанностей. Структура гражданских правоотношений: Субъект: Физические лица граждане иностранцы лица без гражданства Юридические лица российские иностранные Публичноправовые образования органы МСУ Объект: Имущественные вещи деньги ценные бумаги Интеллектуальные права Личные...