«Оптимизация распределения многоблочных задач» Студента 527 группы: Нгуен Там Чинь Научный руководитель: к.ф.-м.н. Коновалов Николай Архипович. - презентация

1 «Оптимизация распределения многоблочных задач» Студента 527 группы: Нгуен Там Чинь Научный руководитель: к.ф.-м.н. Коновалов Николай Архипович

2 Постановка задачи Многоблочная задача – разделение области моделирования на логически- прямоугольные области (неоднородность блоков, неоднородность коммуникаций между блоками) разработать процедуру балансировки вычислений и коммуникаций в рамках модели DVM (база – механизм задач DVM)

3 Метод решения Анализ существующих методов и систем статической балансировки (бинарная упаковка, METIS, Chаco, EVAN и др.) Использование лучших возможностей этих систем в одной процедуре

4 Достоинства и недостатки Бинарная упаковка: простота реализации, нет учета коммуникаций EVAN: простой и быстрый алгоритм, ориентированный граф задач. нет разделения крупных блоков между процессорами METIS, Chаco: неориентированный граф, укрупнение графа, разбиение графа. Зависит от структуры графа, эффективно для графов большого размера

5 Комбинированный метод G = (V, E), |V| = n: суммарный вес всех блоков/узлов. Количество однородных процессоров k Q = n/k – оптимальная средняя нагрузка. Если существует блок V i, вес которого больше Q то, в общем случае применить METIS для разделения блока на две части Обновить конфигурацию графа Применить например EVAN для распределения блоков по процессорам

6 Практическая реализация Граф неориентированный, два теста: 810 блоков (128x128 – 2048x2048) и 128 блоков (4x4 – 2048x2048). Задача Якоби.

7 Первый тест PБин.упаковкаMETISEVANКом.метод

8 Второй тест PБин.упаковкаMETISEVANКом.метод

9 Результаты Проведен анализ наиболее используемых методов статической балансировки На базе исследования предложен комбинированный метод, который показал повышение эффективности Комбинированный метод может быть использован в системе DVM