РАЗРАБОТКА ИНСТРУМЕНТА ОПТИМИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ Руководитель: проф. Мулярчик Степан Григорьевич

2 ВВЕДЕНИЕ Целью дипломной работы является разработка и реализация инструмента автоматической оптимизации параллельных алгоритмов

3 ПОСТАНОВКА ЗАДАЧИ Разработать модель распределенной вычислительной сети Разработать модель распределенной вычислительной сети Разработать адаптивный алгоритм способный оптимизировать параметры параллельной программы или вычислительного кластера на основе результатов моделирования Разработать адаптивный алгоритм способный оптимизировать параметры параллельной программы или вычислительного кластера на основе результатов моделирования Разработать интерфейс взаимодействия модели и параллельных программ. Разработать интерфейс взаимодействия модели и параллельных программ. Разработать средства визуализации результатов моделирования Разработать средства визуализации результатов моделирования Провести тестирование модели и анализ полученных результатов Провести тестирование модели и анализ полученных результатов

4 Структура инструмента оптимизации

5 МОДЕЛЬ СЕТИ Модель структуры сети Алгоритм маршрутизации Алгоритм обмена данными Алгоритм учета загрузки сети

6 Иерархия классов описывающих элементы сети

7 Алгоритм обмена данными

8 АЛГОРИТМ LU ФАКТОРИЗАЦИИ Ax=b A=LU => LUx=b = ) 2)

9 АЛГОРИТМ LU ФАКТОРИЗАЦИИ Расчёт значений блоков Матричное умножение блоков Пересылка блоков

10 ПЛАНИРОВЩИК Процессор 1 Процессор 2Процессор 3Процессор 4 LU1,1 LU1,2LU2,1LU1,3LU3,1 M2,1-1,2M3,1-1,2M2,1-1,3M3,1-1,3 LU2,2LU1,4LU4,1 LU2,3LU3,2M4,1-1,2M2,1-1,4 M3,2-2,3LU2,4LU4,2M4,1-1,3 LU3,3M3,1-1,4M4,2-2,3M3,2-2,4 LU3,4LU4,3M4,1-1,4M4,2-2,4 M4,3-3,4 LU4,4

11 СТРУКТУРА КЛАССОВ МОДЕЛИ АЛГОРИТМА

12 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ Хромосомой для генетического алгоритма при оптимизации параллельного метода LU факторизации выбран план выполнения операций Оператор скрещивания реализуется компоновкой различных ярусов двух планов Оператор мутации представляет собой случайные перемещения операций отправки данных внутри одного плана

13 ВЗАИМОДЕЙСТВИЕ МОДУЛЕЙ ИНСТРУМЕНТА

14 РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ

15 График зависимости времени работы алгоритма LU факторизации, при фиксированном количестве процессов, от количества блоков

16 ОПТИМИЗАЦИЯ МЕТОДА LU ФАКТОРИЗАЦИИ Номер поколенияНаилучший коэффициент приспособленности 10, , , , , , , , 51283

17 ЗАКЛЮЧЕНИЕ Предложен инструмент оптимизации параллельных программ. Для его реализации разработаны: Модель распределенной вычислительной сети Алгоритм оптимизации параметров параллельных программ Средство визуализации результатов работы модели Построена модель параллельного алгоритма LU факторизации После оптимизации алгоритма LU факторизации время его выполнения уменьшилось на 18 %.

18 СПАСИБО ЗА ВНИМАНИЕ