Статический режим назначения вершин графа по MPI-нитям предполагает наличие файла расписания. В системе «PARUS» предусмотрена специальная программа, строящая данный файл, которая называется graph2sch.
Под расписанием будем понимать вектор S элементов snodei = (procj, ranknodei), где procj ∈ Procs, nodei ∈ Nodes, ranknodei — порядковый номер вершины при вызове её на MPI-нити. Размерность вектора совпадает с числом вершин в графе.
Для расписания определена функция вычисляющая время исполнения полученной параллельной программы. Данная функция вычисляется следующим образом: GlobalTime(S) = max(Tnodei + τnodei), ∀nodei ∈ Nodes. Tnodei — момент времени, с которого необходимо начать исполнять вершину графа на MPI-нити с номером proci. τnodei = NodeTime(nodei, procj, Tnodei) — функция, определяющая, как долго будет исполнятся вершина, если она будет запущена в момент времени Tnodei MPI-нитью procj.
Tnodei = StartTime(nodei, ranknodei, procj) — является функцией, имеющей рекурсивный характер. Поскольку назначение вершины на MPI-нить необходимо производить строго по окончанию работы тех вершин, от которых данная вершина зависит, то для подсчёта времени старта вершины мы вынуждены вычислить все времена окончания этих вершин. Для вычисления StartTime определим множество «предков» Parents(nodei) для вершины. В это множество входят все вершины, из которых существуют рёбра, входящие в вершину nodei. Предполагается, что родительские вершины уже закончили свою работу к моменту распределения nodei на MPI-нить, в противном случае множество Parents не определено и расписание не допустимо. StartTime для вершины графа вычисляется следующим образом:
| StartTime = |
{ |
Parents(nodei) = ∅, 0 |
} |
, ∀parentj ∈ Parents(nodei) |
| Parents(nodei) ≠ ∅, max(Tparentj + τj) |
Порядок вызовов вершин на MPI-нитях влияет на то, возможно ли вообще вычислить функцию
StartTime. В случае невозможности вычисления данной функции расписание считается недопустимым.
Время исполнения вершины графа вычисляется следующим образом: NodeTime = ExecTime(nodei, procj) + TransferTime(InputEdges(nodei), procj), ExecTime и TransferTime были рассмотрены ранее. Основная особенность — неявная зависимость функции TransferTime от момента назначения вершины на MPI-нить Tnodei. Функция TransferTime вычислима только в том случае, если все необходимые данные по входящим в вершину рёбрам уже наработаны. Иными словами, все вершины графа, от которых зависит данная вершина, к моменту вычисления функции должны быть назначены на одну из MPI-нитей и должны там доработать, то есть получить результаты и сформировать данные, передаваемые по рёбрам.
Цель алгоритма — каким-либо образом приблизится к минимуму функции GlobalTime, перебирая всевозможные допустимые расписания, то есть найти Sopt = argmin(GlobalTime(Si)), Si ∈ Ξ, здесь Ξ — множество допустимых расписаний. При поиске расписания, близкого к оптимальному, мы варьируем порядок запуска вершин: параметр ranknodei, а так же MPI-нить procj, на которой будет запущена вершина.
Задача построения расписания, близкого к оптимальному, решается при помощи генетического алгоритма. В качестве хромосомы или особи используется одно из допустимых расписаний. Популяция — некоторое подмножество множества допустимых расписаний. Функция качества одного из расписаний — это предполагаемое время исполнения программы по данному расписанию: функция GlobalTime. Мутации производятся следующим образом: случайным образом в случайной позиции хромосомы изменяется изменяется либо порядковый номер на MPI-нити, либо сам номер нити, либо и то и другое вместе. Количество мутаций регулируется параметрами программы. Скрещивание особей производится в одной нескольких точках. Каждая точка ищется при помощи датчика равномерно распределённых на отрезке случайных величин. Количество точек в которых производится скрещивание определяется параметрами программы. Скрещивание производится таким образом, что хромосомы меняются элементами расписания относящимися к одной вершине графа целиком. Для 2-x расписаний Si, Sj обмен производится так:
si, nodek = sj, nodek, sj, nodek = si, nodek; si, nodek ∈ Si; sj, nodek ∈ Sj.
В силу сравнительно высокой вычислительной сложности функции качества, в данном случае полностью заменять следующее поколение особей и вычислять для всех них значения функции качества довольно тяжёлая задача. Вместо этого используется параметризованный генетический алгоритм, при котором на каждом шаге, порождается случайное число особей, полученных путем скрещивания или мутации родителей (родителя).
В момент старта алгоритма случайным образом порождается некоторое количество особей. Начальное количество можно задавать параметрами программы. Далее, над частью особей популяции производится операция мутации. Затем, в популяции выбирается множество пар особей для проведения скрещивания. В результате такого подхода мутантные особи могут стать родителями для скрещиваемых особей. Старые, неизменённые хромосомы оставляются наряду с появившимися новыми. Из всей пополненной популяции выбираются лучшие особи. Лучшие особи — те, у которых значение функции качества меньше значения её у остальных особей. Число отобранных особей не должно превышать значение, указанное в настройках программы. Для оставления в популяции и особей с не столь хорошей функцией качества лучшие особи отбираются с учетом случайного «штрафа».
Алгоритм останавливается в случае незначительного изменения значения функции качества между 2-мя соседними по времени популяциями. Величина изменения функции качества задаётся в настройках программы. Другой причиной остановки может служить исчерпание отведённого количества итераций. Как результат работы алгоритма, выбирается особь с наилучшей функцией качества в последнем поколении.
Все генетические операции производятся таким образом, чтобы не получалось недопустимых расписаний. Все особи с недопустимым расписанием удаляются и операция повторяется снова.
Все параметры, указываемые построителю расписания, указываются в .ini файле.
Формат ini-файла
Генетический алгоритм построения расписания назначений вершин графа по MPI-нитям
Главная страница
Руководство