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

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

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

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

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

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

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

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

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

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

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

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