ID: 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 – NN матрица, k=n/N. Тогда каждый блок Cim произведения С=АВ матриц А и В может быть вычислен через блоки матриц А и В.

 

В вычислении произведения NN матрица матриц 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. Построить таблицу соотношения скорости работы различных алгоритмов умножения матриц. (матрицы брать размерностью 10001000, 50005000, 1000010000 ). В таблицу заносить значения: отношения времени работы первого варианта к времени работы каждого из пяти вариантов.

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

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

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

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