Белорусский государственный университет Механико-математический факультет Кафедра уравнений математической физики Горбач Александр Николаевич ОПТИМИЗАЦИЯ. - презентация

1 Белорусский государственный университет Механико-математический факультет Кафедра уравнений математической физики Горбач Александр Николаевич ОПТИМИЗАЦИЯ ТАЙЛИНГА ПРИ ЧИСЛЕННОМ РЕШЕНИИ ОДНОМЕРНОГО УРАВНЕНИЯ ТЕПЛОПРОВОДНОСТИ НА КОЛЬЦЕ ПРОЦЕССОРОВ Руководитель: доктор физ.-мат. наук, доцент кафедры Уравнений матфизики Соболевский Павел Иосифович Магистерская диссертация Минск 2008

2 Содержание 1.Введение.Введение. 2.Определение тайлинга.Определение тайлинга. 3.Задание алгоритма.Задание алгоритма. 4.Разбиение алгоритма.Разбиение алгоритма. 5.Отображение на кольцо процессоров.Отображение на кольцо процессоров. 6.Основные результаты.Основные результаты. 7.Научная новизна.Научная новизна.

3 Введение На практике процесс построения параллельного алгоритма включает в себя этап его оптимизации под целевой суперкомпьютер. При оптимизации необходимо учитывать конфигурацию компьютера, в частности, его топологию и такие параметры как производительность и объем локальной памяти вычислительных узлов, время инициализации и пропускную способность каналов связи. Задача оптимизации паралельных алгоритмов с учетом перечисленных выше параметров – это задача, решению которой посвящена данная работа.

4 Определение тайлинга Тайлингом называется нелинейное отображение индексного множества (итерационного пространства) V, определяемое как где соответственно, «целая часть каждой координаты вектора a» (ближайшая снизу) и «дробная часть каждой координаты вектора a».

5 Задание алгоритма в виде гнезда тесновложенных циклов: Алгоритмы такого вида характеризуются областью вычислений V и множеством векторов зависимостей. Область вычислений есть подмножество точек целочисленного пространства которое определяется как

6 1-я краевая задача для уравнения теплопроводности с начальным условием и граничными условиями

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

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

9 Основные результаты Найдена оценка времени реализации алгоритма, она позволяет рассматривать задачу оптимизации размеров тайла, как задачу минимизации функции зависящей от двух переменных r 1, r 2.

10 Функция времени реализации алгоритма придля

11 Научная новизна Исследована техника тайлинга для случев, когда множество векторов зависимостей алгоритма и множество нормальных векторов гиперплоскостей, осуществляющих разбиение на тайлы, состоит не только из координатных векторов.

12 Спасибо за внимание…