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


 

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

53826. Изменение имен прилагательных по родам 29 KB
  Минутка красивого письма на доске показ аяое какие буквы соединения будем писать чем отличаются прописываю на доске Словарь: какую группу слов повторяли дома на доске слова но из каждого слова потерялась буква дети устно называют букву учитель вставляет яблко кпуста гурец грох млина записать в три столбика Жен.Изучение нового материала на доске картинки земляника арбуз яблоко.
53827. Комплексний підхід у корекційній роботі з попередження та подолання вад усного і писемного мовлення учнів 51.5 KB
  Актуальність знань щодо процесу розвитку мовлення дітей визначається завданням гуманізації виховання створенням оптимальних умов для найповнішого розкриття їхніх потенційних можливостей як субєкта спілкування та предметно практичної діяльності. Головні положення лінгвістичних напрямів і напрямів які досліджують спілкування та мовлення як окремий випадок комунікативної діяльності визначають нові завдання щодо практики й теорії мовленнєвого розвитку дітей: потребу показати комплексний підхід до вивчення мови як засобу взаємодії...
53828. Тотожні перетворення виразів, що містять квадратні корені 644 KB
  Мета: Формувати вміння та навички перетворювати вирази що містять арифметичні квадратні корені розвивати вміння аналізувати порівнювати навчальний матеріал виховувати вміння співпрацювати з однокласниками впроваджувати в життя учнів спрямованості на здоровий спосіб життя застосовуючи здоровязберігаючі технології.2 хв Квадратні корені з чисел вавилонські мате тематики вміли добувати ще в 4 тис.
53829. Порядок и источники выплаты дивидендов 31 KB
  Методика постоянного процентного распределения прибыли. Одним из основных аналитических показателей, характеризующих дивидендную политику, является коэффициент «дивидендный выход» (коэффициент выплаты дивидендов), представляющий собой отношение дивиденда по обыкновенным акциям к прибыли, доступной владельцам обыкновенных акций (в расчете на одну акцию).
53830. Внутреннее строение корня в связи с его функциями 39.5 KB
  Сформировать понятие о зонах корня. Развивать понятие о клеточном строении корня. Продолжить формирование понятий о тканях и показать на конкретных примерах зон корня определенные виды тканей.
53831. Властивості арифметичного квадратного кореня 108.15 KB
  Розглянути властивості арифметичного квадратного кореня; розвивати вміння учнів добувати квадратні корені, використовуючи вивчені властивості; виховувати повагу до історії Збройних Сил України, розуміння почесного обов’язку захисника Вітчизни, почуття колективізму.
53832. Строение корня. Виды корней. Корневые системы. Видоизменения корней. Лабораторная работа № 2: корень и корневые системы 80 KB
  Виды корней. Видоизменения корней. Видоизменения корней. Задачи: дать понятия корень и виды корней типы корневых систем; выработать практические умения различать виды корней и типы корневых систем; познакомить учащихся с зонами корня их строением в связи с выполняемыми функциями; определить роль корня в жизни...
53833. Косметичні проблеми підлітків 51 KB
  Три групи обговорюють між собою завдання а четвертауважно слухає відповіді та аналізує їх Слово вчителя: Як бачимо в описі кожного портрету звучали словаздорова шкіра здорове волосся. Шкіра людини має складну будову: зовнішній середній і внутрішній шар. Шкіра виконує захисну видільну дихальну терморегуляторну та тактильну функції. Шкіра нормальна.
53834. Тематична композиція «Космічні світи» 43.5 KB
  Мета: ознайомити учнів з космічним живописом, навчити зображувальних прийомів передачі простору, повітряної перспективи; розвивати творчу уяву,фантазію; виховувати космополітичні почуття.