Дипломная работа: Распараллеливание многоблочных задач для SMP-кластера

Дана многоблочная программа на языке Fortran-DVM, использующая механизм подзадач DVM.

Требуется разработать и реализовать эффективный алгоритм автоматического отображения подзадач на процессоры; изменить способ кодирования операций отображения и запуска подзадач, чтобы обеспечить использование алгоритма автоматического отображения; сравнить характеристики выполнения исходной программы с ручным отображением и программы с автоматическим отображением.

4 Обзор существующих решений

4.1 Алгоритм сокращения критического пути (CPR)

CPR предложен разными авторами из голландского политехнического университета Delft и французского института INRIA. Сначала алгоритм был разработан для планировщика задач в многопроцессорных системах, где граф задач можно моделировать в виде ориентированного ациклического графа. Существуют и другие подходы для решения такого рода задач (TwoL, CPA, TSAS) [5], но CPR показывает самый приемлемый результат.

CPR можно применить для распределения многоблочных задач (при условии возможности построения ориентированного ациклического графа).

Рисунок 2. Иллюстрация ориентированного ациклического графа блоков

Определение

Критический путь (T): самый длинный путь в графе (от входа до выхода).

Верхний критический путь блока t (T_v ): самый длинный путь от входа до t

Нижний критический путь блока t (T_n ): самый длинный путь от t до выхода

P - количество процессоров в системе.

N(t) - Количество процессоров, выделенных для блока t.

Описание алгоритма

Шаг 1. Для каждого блока t_i выделен один процессор N(t_i ) = 1. Построить расписание.

Шаг 2. Пусть X – множество всех блоков, для которых выделено меньше P процессоров.

Шаг 3. Пусть блок t – блок, у которого сумма T_v + T_n максимальная.

Выделить для t дополнительный процессор, N(t) = N(t) + 1. Построить новое текущее расписание.

Если после выделения, новый критический путь T’ < T то T = T’, иначе N(t) = N(t) – 1 и блок t исключить из множества X и считать предыдущее расписание текущим.

Шаг 4. Повторяем шаг 3 пока X не пусто

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

Алгоритм эффективный, учитывает зависимости между блоками, но не рассматривает проблему назначения групп процессоров для конкретных блоков и составления расписания их прохождения.

4.2 Упаковка в контейнеры

Bin-packin это множество алгоритмов для решения задачи: объекты различных объемов должны быть упакованы в конечное число контейнеров так, чтобы минимизировать количество используемых контейнеров. В нашем случае упаковка в контейнеры используется для равномерного распределения задач по всем процессорам.

Упаковка в контейнеры без разбиения объектов

Имеем список объектов L=(a₁ , a₂ , …, a_n ) и их размеры s(a_i ) Є {1, 2, …, U}. Размер контейнеров V больше U, количество контейнеров m. Отсортируем список объектов по размеру в убывающем порядке. Первые m объектов упаковывать соответственно будем в m контейнеров. С остальными объектами действуем по принципу: упаковывать в контейнер, у которого занимаемого места меньше всего.

Упаковка в контейнеры с разбиением объектов

Существует два возможных варианта упаковки в контейнеры с разбиением объектов [4]: с сохранением и с увеличением объема данных. Будем рассматривать вариант с увеличением объема данных, так как после разбиения часто появляются дополнительные коммуникации между фрагментами.