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


 

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

43878. Разработка программы обучения персонала продажам банковских услуг ООО «Хоум Кредит энд Финанс Банк» 984.5 KB
  Подходы к созданию программ обучения персонала Корпоративные стандарты Кейс Организация обучения персонала в ООО Хоум Кредит энд Финанс...
43879. Процесс влияния состояния основных средств на деятельность таможенных органов 547 KB
  Еще одно принципиальное нововведение - глубокий аналитический учет, обязательный и единообразный для всех субъектов бюджетного учета. Это достигается путем интеграции кодов бюджетной классификации в номер бухгалтерского счета. Кроме того, вводится еще один вид бюджетной классификации - классификация операций сектора государственного управления.
43880. Программный комплекс расчета комплексной нетранзитивности отношения превосходства на группе объектов 7.88 MB
  Требования к помещениям для работы с ПЭВМ Требования к уровням электромагнитного и электростатического полей в помещениях с ВДТ и ПЭВМ Требования к режиму работы пользователя ПЭВМ Вредные факторы возникающие при работе на ПЭВМ Вид работы Вредные факторы Действие на организм Средства Защиты Пользователь ПЭВМ Отклонение параметров микроклимата от нормы Охлаждение или перегрев Системы отопления или кондиционирования Неправильное освещение
43881. Организация управленческого учета на примере ООО «Фабрика мебели «Роникон» 840 KB
  Теоретические основы управленческого учета Сущность субъект и объект цели и задачи методы и принципы управленческого учета Пути совершенствования системы управленческого учета на ООО Фабрика мебели Роникон
43882. Визначення та наукове обгрунтування психолого-педагогічних умов подолання особистісної тривожності у дітей молодшого шкільного віку та пятикласників 959.5 KB
  Підходи науковців до реалізації наступності зорієнтовані передусім на інтеграцію двох ланок освіти, усунення суперечок між запитами школи і амбіційним завищеними вимогами окремих батьків щодо підготовки їхніх дітей; між непідготовленістю окремих учнів, які не відвідували дошкільних установ, і необхідністю враховувати специфіку дошкільної освіти.
43883. Экономика и управление на предприятии АПК». Методические указания 605 KB
  В методических указаниях рассматриваются вопросы подготовки написания процедуры защиты дипломных работ раскрыты требования по оформлению работы. ПОДГОТОВКА КВАЛИФИКАЦИОННОЙ РАБОТЫ Выбор темы дипломной работы Назначение руководителя дипломной работы и выдача дипломного задания.
43884. Створення когнітивно-семантичного підґрунтя вибору варіантів перекладу одиниць на позначення концепту “Кількість” 249 KB
  Кількість як узагальнений когнітивний зміст великий фрагмент кодованої засобами мови картини світу того чи іншого етносу. На першому етапі необхідно чітко визначити поняття âкартина світуâ âмовна картина світуâ âконцептâ для чого слід виконати критичний аналіз наукової літератури. Новизна одержаних результатів визначається тим що в ньому виявлено спільні і відмінні ознаки репрезентації концепту âКількістьâ в англійській та українській мовних картинах світу встановлені абсолютні і варіантні еквіваленти перекладу в...
43885. Проектування поліграфічного підприємства 3.18 MB
  Вибір напруги живлячої мережі. Вибір напруги розподільчої мережі. Характеристика джерела живлення Підприємство можна заживити від районних підстанцій що мають три рівні напруги.
43886. Изучение и систематизация теоретических аспектов организации финансов на ООО "Компания ОГАТ" 599 KB
  Финансы предприятий будучи частью общей системы финансовых отношений отражают процесс образования распределения и использования доходов на предприятиях различных отраслей народного хозяйства и тесно связаны с предпринимательством поскольку предприятие является формой предпринимательской деятельности. Целью данной дипломной работы является систематизация теоретических аспектов организации финансов на предприятиях различных форм собственности изучение аналитических сведений практической деятельности финансового состояния конкретного...