Южный федеральный университет Факультет математики механики и компьютерных наук Исследования по оптимальному использованию распределенной и кэш памяти Гервич Л.Р., Юрушкин М.В. Научный руководитель: зав. каф. АДМ, д.т.н. Штейнберг Б.Я.

ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ЗАДАЧИ ДИРИХЛЕ

Задача Дирихле u(x, y, 0)=a(x,y) u (x, y, 1)=b(x,y) u (x, 0, z)=c (x,z) u (x, 1, z)=d (x,z) u (0, y, z)=e(y,z) u (1, y, z)=f (y,z) Аналитическая форма U i,j,k = (U i,j-1,k + U i,j+1,k + U i-1,j,k + U i+1,j,k + U i,j,k-1 + U i,j,k+1 )/6 Разностная схема

Стандартный последовательный алгоритм For (i=0,…,maxIt) { For (j=1,..,n-1) For (k=1,..,n-1) For (s=1,..,n-1) B[j,k,s]=1/6*(U[j,k-1,s]+ U[j,k+1,s]+ U[j-1,k,s]+ U[j+1,k,s]+U[j,k,s-1]+ U[j,k,s+1]) For (j=1,..,n-1) For (k=1,..,n-1) For (s=1,..,n-1) U[j,k,s]=B[j,k,s] }

Стандартный параллельный алгоритм двумерной (для наглядности) задачи Дирихле Разбиение двумерной матрицы на блоки, каждый из которых находится в своем процессоре.

Схема межпроцессорных пересылок на каждой итерации

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

Слайд взят из презентации проф. Корнеева В.В. (ФГУП Квант) Темп роста быстродействия процессоров и памяти На сегодняшний день доступ к памяти в 20 раз дольше умножения

Методы оптимизации параллельного алгоритма Уменьшение количества межпроцессорных пересылок. Увеличение локальности данных для оптимального использования кэш-памяти.

Результаты численных экспериментов (ускорение в 2.4 раза) Кластер INFINI Югинфо Размерность сетки Количество итераций Количество Процессоров Время простого алгоритма Время простого алгоритма с блочностью Время алгоритма с перекрытием Время алгоритма с перекрытие м и блочностью 500*500* m 27s24m 36s13m 38s11m 24s

ОПТИМИЗАЦИЯ В РАСПРЕДЕЛЕННОЙ ПАМЯТИ

Параллельный алгоритм с перекрытиями (know how) Размер перекрытия равен m Схема обмена на итерациях, кратных m:

Параллельный алгоритм с перекрытиями Между каждыми двумя итерациями с пересылками выполняются m-1 итераций без пересылки.

Сравнение параллельных алгоритмов Количество алгебраических операций у алгоритма с перекрытиями больше, чем у простого алгоритма. Объем пересылаемых данных у обоих алгоритмов одинаков. Количество пересылок алгоритма с перекрытиями меньше, чем у простого параллельного алгоритма. Одинаковые объемы данных лучше пересылать данные за меньшее количество пересылок, чем за большее

РАЗМЕЩЕНИЕ ДАННЫХ ПОД ИСПОЛНЯЕМЫЙ КОД

Размещения данных Стандартные размещения матриц компиляторами: Размещение по строкам (СИ, Паскаль) Размещение по столбцам (ФОРТРАН) Другие: Блочное Скошенное

Скошенная форма хранения матрицы. В каждом модуле памяти хранится косая диагональ: позволяет одновременно считывать как строки так и столбцы матриц

Оптимизирующие компиляторы нового поколения Автоматическое размещение данных, зависящее от кода программы и целевой архитектуры. Подстройка под кэш-память Минимизация межпроцессорных пересылок (в случае распределенной памяти)

Реализация в ДВОР ДВОР – Диалоговый высокоуровневый оптимизирующий распараллеливатель. Блочное распределение данных в общей памяти. Блочно-аффинное размещение массивов в распределенной памяти. Первый в мире online-распараллеливатель:

Реализация блочного распределения данных в общей памяти. #pragma ops distribute data(A, N, N, 1, d, d) #pragma ops distribute data(B, N, N, 1, d, d) #pragma ops distribute data(C, N, N, 1, d, d) for (bi = 0; bi < blockCount; bi++) for (bj = 0; bj < blockCount; bj++) for (bk = 0; bk < blockCount; bk++) for (i = 0; i < d; i++) for (j = 0; j < d; j++) for (k =0; k

Тест 1. Возведение матрицы в квадрат Intel® Pentium® Processor E5300 (2M Cache, 2.60 GHz, 800 MHz FSB) N = 1000 Размер блока Стандартный алгоритм(мс) Блочный код (мс) Блочный код + распределение массивов (мс) Ускорение

Тест 2. Умножение матриц Intel® Pentium® Processor E5300 (2M Cache, 2.60 GHz, 800 MHz FSB) N = 1000 Размер блока Стандартный алгоритм(мс) Блочный код (мс) Блочный код + распределение массивов (мс) Ускорение

Тест 3. Двумерная задача Дирихле Intel® Pentium® Processor E5300 (2M Cache, 2.60 GHz, 800 MHz FSB) N = 4000 Размер блока Стандартный алгоритм(мс) Блочный код (мс) Блочный код + распределение массивов (мс) Ускорение

Наши публикации Гервич Л. Р., Штейнберг Б.Я. Параллельное итерационное умножение матрицы на вектор // Труды научной школы И.Б. Симоненко, отв. ред.: Я. М. Ерусалимский, Б.Я. Штейнберг. Ростов н/Д: Изд-во ЮФУ, С. 275 Гервич Л.Р., Штейнберг Б.Я.Размещение массивов с перекрытиями в параллельных итерационных процессах. «Современные проблемы и методы теории операторов и гармонического анализа и их приложения» Тезисы докладов международного семинара, приуроченного к 70-летию проф. С.Г. Самко. Ростов-на-Дону, Южный федеральный университет, апреля 2011 г., с. 61 Штейнберг Б.Я., Абрамов А.А., Алымова Е.В., Баглий А.П., Гуда С.А., Дубров Д.В., Кравченко Е.Н., Морылев Р.И., Нис З.Я., Петренко В.В., Полуян С.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкин М. Диалоговый высокоуровневый автоматический распараллеливатель (ДВОР). Научный сервис в сети Интернет.: Труды Всероссийской суперкомпьютерной конференции (20-26 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010., с Штейнберг Б.Я., Штейнберг Р.Б., Морылев Р.И., Петренко В.В., Полуян С.В., Штейнберг О.Б., Баглий А.П., Нис З.Я., Скиба И.С., Юрушкин М.В., Шаповалов В.Н.,Алымова Е.В., Кравченко Е.Н. Диалоговый высокоуровневый оптимизирующий распараллеливатель программ. Свидетельство о регистрации программ Соловьев А.Н., Гервич Л.Р., Штейнберг Б.Я., Наседкин А.В., Скалиух А.С., Сумбатян М.А. Параллельные решатели для пакета ACELAN. Свидетельство о регистрации программ

Группа ОРС (=ДВОР) Оптимизирующая распараллеливающая система