Модели параллельных вычислений и DVM технология разработки параллельных программ (2) (1158288)

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

Текст из файла

- 4 - 21.9.2019

Лабораторный практикум

"Модели параллельных вычислений и DVM‑технология разработки параллельных программ"

Общее описание лабораторного практикума

Цели и задачи практикума:

Приобретение навыков разработки и отладки параллельных программ типовых вычислительных алгоритмов в модели DVM (модель параллелизма по данным и параллелизма задач).

Необходимое оборудование и ПО:

Вычислительный кластер МВС15000 (МСЦ), система DVM .

Необходимый уровень подготовки:

Для успешного выполнения практикума предполагается наличие следующих знаний:

• Знание языков программирования Си и Фортран,

• Предварительное ознакомление с методикой разработки и отладки программ в системе DVM [1,2].

Методические рекомендации по выполнению:

Весь материал, необходимый для выполнения практикума, содержится в лекционном курсе и методических пособиях [1,2]. Полезная дополнительная информация может быть найдена в материалах [3,4,5].

Планируемый результат:

• Параллельные программы,

• Результаты выполнения экспериментов по оценке производительности (таблицы и графики времени выполнения, ускорения и эффективности),

• Выводы по полученным результатам (объяснение убывания или возрастания производительности параллельной программы при варьировании виртуальной решетки процессоров).

Распараллеливание матричных алгоритмов

Цель:

• Получить навыки разработки новой параллельной программы в модели параллелизма по данным.

• Оценить производительность на разном количестве процессоров и достичь максимальной производительности для определенного количества процессоров вариацией размера блока (ширины ленты) m.

Алгоритмы умножения матриц

Блочное представление

При построении параллельных способов умножения матриц наряду с рассмотрением матриц в виде набора строк и столбцов используется блочное представление матриц.

Пусть даны матрицы A, B и результирующая матрица C размером nn. Представим матрицы в виде блоков размера mm, где n кратно m (т.е. n= mk). Тогда операцию матричного умножения в блочном виде можно представить следующим образом:

A₁₁ A₁₂…A_1k B₁₁ B₁₂…B_1k C₁₁ C₁₂…C_1k

. . .  . . . = . . . ,

A_k1 A_k2…A_kk B_k1 B_k2…B_kk C_k1 C_k2…C_kk

где каждый блок C_ij матрицы C определяется в соответствии с выражением

k

C_ij =  A_it B_tj

t=1

Алгоритм Фокса

Основные положения параллельного метода, известного как алгоритм Фокса, состоят в следующем.

Инициализация матриц A, B

C = 0

B' = B

На каждой итерации t (1  t  k ) выполняются следующие операции:

• Блок Aij_t рассылается (размножается) по блокам i-ой строки матрицы A'

A'ij = Aij_t (1  j  k )

где j_t = (1+t-k)mod k + 1 (mod k – остаток целочисленного деления на k)

• Для каждого блока Cij выполняется операция

Cij = Cij + A'ij  B'ij

• Блоки B'ij сдвигаются (пересылаются) вверх по столбцу на 1 позицию (блок) по кольцу.

Bij = B'i₂j , где i₂ = ( i )mod k + 1, (1  i  k )

B' = B

Пересылка по кольцу означает, что первая строка блоков пересылается в последнюю строку блоков.

Алгоритм Кеннона

Основные положения алгоритма Кеннона.

Инициализация матриц A, B

C = 0

Блок Aij смещается влево по кольцу i-ой строки на i позиций (блоков)

A'ij = Aij₃ , где j₃ = (i+j-1)mod k +1, (1  i  k )

Блок Bij смещается вверх по кольцу j-ого столбца на j позиций

B'ij = Bi₃j , где i₃ = ( i+j-1)mod k +1, (1  i  k )

На каждой итерации t (1  t  k ) выполняются следующие операции:

• Для каждого блока Cij выполняется операция

Cij = Cij + A'ij  B'ij

• Блоки A'ij смещается влево по кольцу i-ой строки на 1 позицию

Aij = A'ij₂ , где j₂ = ( j )mod k + 1

• Блоки B'ij смещается вверх по кольцу j-ого столбца на 1 позицию

Bij = B'i₂j , где i₂ = ( i )mod k + 1

• Копирование матриц

A' = A

B' = B

Ленточный алгоритм

В ленточном алгоритме матрицы разделяются по одному измерению. Матрицы разделяются на ленты шириной m (n=mk).

Разделим матрицы A и C по строкам, а матрицы B и B' разделим по столбцам.

Представим логически матрицу C в виде блоков размера mm.

Введем следующие обозначения:

Ai - i-ая лента матрицы A по строкам

B'j - j -ая лента матрицы B' по столбцам

Cij – логический блок матрицы C

Основные положения ленточного алгоритма.

Инициализация матриц A, B

C = 0

B'=B

На каждой итерации t (1  t  k ) выполняются следующие операции:

Вычисление следующих блоков матрицы C

Cij = Ai  Bj , где 1  i  k и j= (i+t-2)mod k + 1

Ленты смещаются влево по строкам на 1 позицию

Bj = B'j₁ , где j₁ = ( j )mod k + 1

Копирование матрицы

B' = B

Целое число t внутри каждого блока указывает номер итерации, на которой вычисляется соответствующий блок матрицы Cij.

Отображение блочных методов в модели DVM

Обычно блочные методы рассматриваются для двумерной решетки процессоров pp = p². При этом на каждый процессор p_ij распределяется по одному блоку каждой матрицы, что требует кратности размера матрицы n количеству процессоров p.

Предлагаемый алгоритм не зависит от количества процессоров и требования кратности.

Если k=p, то на каждый процессор будет распределен ровно 1 блок каждой матрицы.

Если k>p, то на некоторые процессоры будет распределено несколько блоков матриц. При этом, если k не кратно p, то мы получим несбалансированную загрузку процессоров.

Все эти варианты описываются следующими спецификациями на языке Fortran-DVM.

CDVM$ DISTRIBUTE A (MULT_BLOCK(m), MULT_BLOCK(m))

Спецификация распределяет матрицу А на виртуальную решетку процессоров pp (p1). При этом по каждому измерению матрица А распределяется блоками кратности m.

CDVM$ ALIGN ( i,j ) WITH A( i,j ) :: B, C, A1, B1

Спецификация указывает, что матрицы B, C, A1, B1 будут распределены в точном соответствии с распределением матрицы A.

Для ленточного метода матрицы распределяются на виртуальную линейку процессоров следующими директивами языка Fortran-DVM:

CDVM$ DISTRIBUTE A ( MULT_BLOCK(m), *)

CDVM$ ALIGN ( i,j ) WITH A( i,j ) :: C

CDVM$ ALIGN ( j,i) WITH A( i,j ) :: B, B1

Асинхронная (параллельная) пересылка блоков на языке Fortran‑DVM

Описание переменной типа «сигнал»:

CDVM$ ASYNCID TSIG

…

Начало цикла копирования одного или нескольких блоков:

CDVM$ ASYNCHRONOUS

A1(IL1:IR1, JL1:JL1) = A(IL:IR, JL:JR)

…

CDVM$ END ASYNCHRONOUS

Конец цикла копирования.

Ожидание конца копирования:

CDVM$ ASYNC_WAIT TSIG

Оператор пересылки блока матрицы является частным случаем оператора присваивания секций массива языка Фортран 90. По каждому измерению матрицы указываются начальные и конечные координаты (индексы элементов) блока в матрице.

Параллельная пересылка блоков на языке C-DVM описана в методике [2] (см.директиву COPY)

Планируемый результат:

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

Программа должна состоять из следующих частей:

• Инициализация:

DO(I,0,N-1,1)

DO(J,0,N-1,1)

{

C[I][J]=0;

A[I][J]=I+J+2;

B[I][J]=I+J+2;

}

• основной цикл вычислений,

• вывод результатов.

Результатом является сумма элементов результирующей матрицы или массивов. Эта же сумма используется для сравнения выполнения параллельной программы и последовательной программы (функциональная отладка).

1. Таблицы времени, ускорения и эффективности для разного количества процессоров.

2. Файл статистики максимальной производительности для определенного количества процессоров и размер блока m, при котором достигнута эта производительность.

Литература

1. Параллельное программирование на языке FORTRAN-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г.

2. Параллельное программирование на языке C-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г.

3. Дж. Ортега. Введение в параллельные и векторные методы решения линейных систем. Москва, «Мир», 1991.

4. Описание языка FORTRAN-DVM. http://www.keldysh.ru/dvm

5. Описание языка C-DVM. http://www.keldysh.ru/dvm

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы