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

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

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

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

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

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

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

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

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