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 с.


 

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

60127. Українське кіномистецтво 951 KB
  Народилася Наталія Михайлівна Ужвій 22 серпня 1898 року в містечку Любомлі на Волині в селянській сім’ї. До 1912 року сім’я Ужвій жила в робітничому селищі Брудно поблизу Варшави.
60129. Класна година: Не рубай ялинку, не губи тваринку, а краще природу бережи 44 KB
  Вони ростуть у суворому кліматі там завжди дуже холодно ростуть на збіднених ґрунтах де мало вологи і поживних речовин. Слайд 3 Група 1 Ялинка як і всі вічнозелені дерева дуже красива. Людям у яких є хвороби серця чи дихальних шляхів це повітря дуже корисне...
60130. Хлеб - всему голова 73 KB
  Демонстрация видеоролика Хлеб - всему голова Вступительное слово преподавателя Гетман А. Хлеб во все времена и у всех народов наибольшей святостью считается хлеб. Когда не было хлеба приходила беда.
60131. Виховний захід: «Я - за безпечний Інтернет» 69.5 KB
  Мета: знайомство учасників для створення комфортної атмосфери для роботи Метод: індивідуальна робота Теоретична інформація: На ватмані малюється квітка без пелюстків. Вправа 2: Очікування гра Гаряча картопля...
60132. Музыкально - литературное кафе «Огонёк» 113.5 KB
  Воспитательная: формировать интерес и уважение к отечественной культуре; создать атмосферу единения характерную для концертов бардовской песни 60–-70х годов обогатить духовный мир учащихся.
60133. Вікторина «Найрозумніший»/ Quiz Der Klugste 37.5 KB
  lso wir hben hier 2 Mnnschfte die schon so ungeduldig uf den nfng wrten. Команди представляють себе: назва та девіз Ведучий: Gut gemcht Und jetzt kommt die ufwrmung Dfr ht mn feine Zungenbrecher usgewhlt. Mn muss die zuerst zusmmensetzen dnch liest jemnd uns vor und bekommt dfr 2 Punkte eine fr die Richtigkeit und eine fr ds Lesen selbst. Wie heit die Huptstdt der Bundesrepublik Deutschlnd Bonn; bFrnkfurt; cBerlin.
60134. Космическое путешествие 92.5 KB
  Уважаемые выпускники 2 стюардесса: Уважаемые учителя 1 стюардесса: Уважаемые родители 2 стюардесса: Мы рады приветствовать вас на борту космолайнера Мечта. 1 стюардесса: Во время полета запрещается: скучать; катапультироваться...
60135. Нітрати. Вплив нітратів на організм людини 80.5 KB
  Мета: з’ясувати вплив нітратів на організм людини формувати в учнів науковий світогляд навички обговорення проблеми забруднення харчових продуктів хімічними речовинами формувати образно-логічне та екологічне мислення...