Авторы: А.С. Куренев, В.П. Симоненко
В данной статье описан алгоритм статического планирования для многопроцессорных и Grid систем. Задача планирования сводится к поиску плана распределения задач по ресурсам с минимальным количеством вычислительных узлов с минимизацией времени решения. В этой статье предложен алгоритм пошагового конструирования, позволяющий уменьшить время планирования, за счет применения принципа одновременного прохода планировщика «сверху» и «снизу».
В настоящее время ведутся активные исследования в создания инфраструктуры, которая обеспечивает надежный, устойчивый и недорогой доступ к высокопроизводительным вычислительным ресурсам. Такой инфраструктурой являются Grid-системы. Так же в данный мо-мент в Украине эффективно развивается Украинский Академический Grid. Одной из актуальных задач в подобных системах является такое планирование заданий, которое позволяет наиболее эффективно использовать ресурсы вычислительной среды. В данном случае под планированием понимается распределение поступающих на вход заданий, подготовленных для параллельного выполнения на имеющиеся ресурсы. Целью планирования является определение эффективности распределения заданий при использовании различных критериев.
На данный момент разработано множество различных алгоритмов статического планирования [1], однако всем им присущ существенный недостаток, они требуют выполнять полное сканирование графа, причем зачастую несколько раз, что существенно замедляет работу самого планировщика. Большинство планировщиков для Grid систем, таких как, FCFS, SJF [2] просто выделяют определѐнное количество ресурсов под задачи, не выполняя оптимизацию внутри самих задач, что бы дало не только предпосылки к уменьшению времени самих выполнения задач, но и к более эффективному использованию ресурсов.[3]
Целью данной статьи является разработка нового алгоритма пошагового конструирования, позволяющего уменьшить время планирования, за счет применения принципа одновременного прохода планировщика «сверху» и «снизу».
Исходная задача поступает в систему в виде ориентированного ациклического графа (DAG) [4] задачи в ярусно-параллельной форме. Граф задается в виде множества:
G = {N; E; W; C},
где N – множество вершин графа; Е – множество дуг (переходов между вершинами); W – веса (вычислительная сложность) вершин; С – веса (время коммуникации) дуг.
Для определения порядка запуска задач используется представление графа в виде матрицы связности: значение элемента матрицы указывает вес пути из одной вершины в другую, если такой существует. Эти значения также указывают зависимость одной задачи от другой.
При планировании необходимо учитывать условие предшествования. Задача готова к выполнению, когда все зависимости разрешены.
Для первой разрешeнной задачи время запуска считается 0. Для остальных выбирается максимальное из всех определенных при разрешении зависимостей, таким образом, ко времени запуска задачи все ее предшественники будут выполнены, и время на пересылку данных учтено.
Таким образом, основной задачей планирования [5] является построение распределение (план) задач по доступным ресурсам так, чтобы минимизировать время выполнения приложения и использование ресурсов.
На первом шаге алгоритма строится базовое решение. Под базовым решением понимается выделение отдельного процессора для каждой задачи. Такое решение используется в качестве основного, от которого производится поиск лучшего решения.
Основными атрибутами, по которым осуществляется планирование для DAG, являются t-level и b-level [1,6].
t-level – это самый длинный путь от начальной вершины до данной вершины ni , без учета веса ni. Путь считается путем сложения всех весов вершин и пересылок, через которые он проходит. Этот параметр так же отражает наименьшее время начала вершины. T-level для i-й вершины вычисляется по следующей формуле:
tlevel(ni)= max (tlevel(nm)+ wm + cm,i),
где nm=pred(ni) – предшествующие вершины, wm – вычислительная сложность, cm,i – временные затраты на коммуникацию.
b-level - это самый длинный путь от вершины ni до исходной. Так же выделяют статический b-level, в котором не учитываются пересылки. B-level для i-го узла вычисляется по формуле:
blevel(ni)= wi + max (blevel(nm)+ cm,i),
где nm=succ(ni) – последующие вершины, wi – вычислительная сложность, cm,i – временные затраты на коммуникацию. А статический b-level вычисляется по формуле:
sblevel(ni)= wi + max (sblevel(nm)),
где nm=succ(ni) – последующие вершины, wi – вычислительная сложность.
Стоит отметить, что данные необходимо вычислять на каждом шаге алгоритма только для тех вершин, которые находятся на последующем уровне, при нисходящем планировании, и тех, которые находятся уровнем выше при восходящем. Это позволяет исключить повторное полное сканирование графа, что значительно ускоряет процесс планирования.
Обозначим множество вершин, принадлежащих k-му уровню:
nk={nki}, i=1,mk,
где nki – i-я вершина k-го уровня, mk – количество вершин на k-ом уровне. Если вершина nki имеет единственную инцидентную ей дугу e, и вершина nk-1i так же имеет единственную дугу e инцидентную ей, то вершины nki и nk-1i необходимо кластеризовать.
При нисходящем планировании на каждом шаге алгоритма выполняются следующие действия:
При восходящем планировании на каждом шаге алгоритма выполняются следующие действия:
Для кластеризованных вершин, находящихся в одном узле, время затрачиваемое на коммуникацию приравниваем к 0.
Так же при планировании стоит учитывать вершины, обладающие свойствами неявной транзитности, т. е.для nki вершины выполняется неравенство:
tlevel(nki) ≥ min(tlevel(nk+1j)).
Такие вершины при планировании могут быть кластеризованы с вершинами, находящимися на более низком уровне, чем k+1. Зачастую это может привести к уменьшению ресурсов, требуемых для текущей задачи. Такую вершину целесообразно перенести на другой уровень для кластеризации, если выполняется соотношение:
ntlevel(nki) ≤ max(tlevel(nkj)),
где ntlevel – tlevel для нового уровня.
Выполним планирование при помощи данного алгоритма для графа, представленного на рис. 1.
Рисунок 1. Исходный граф
Выполним построение базового решения, выделив каждой задаче по отдельному ресурсу R (рис. 2).
Распределим вершины по уровням:
n1= {1}
n2= {2,3,4,5}
n3= {6,7,8}
n4= {9}
Стоит отметить, что вершина 5 обладает свойством транзитности, поэтому она может находиться как на втором уровне, так и на третьем и четвертом.
Рассмотрим для вершины 1 (рис.3):
Из всех вершин второго уровня наибольший t-level имеет вершина 2:
ntlevel(n2)= 1 + 4 = 5
Поэтому вершину 2 кластеризуем с вершиной 1.
Теперь рассмотрим шаг для восходящего планирования (рис. 4).
Вершина 8, находящаяся на третьем уровне имеет наибольший b-level, поэтому она кластеризуется с 9 вершиной. Для вершин, которые находятся на одном ресурсе время, затрачиваемое на коммуникацию, приравниваем к нулю. В результате в начале следующего шага диаграмма будет выглядеть, как представлено на рис. 5.
Переходим на следующий уровень и для каждой вершины выполняем аналогичные действия. После выполнения шага 2 при нисходящем планировании получим диаграмму, представленную на рис. 6., в начале следующего шага диаграмма будет выглядеть, как представлено на рис. 5.
Переходим на следующий уровень и для каждой вершины выполняем аналогичные действия. После выполнения шага 2 при нисходящем планировании получим диаграмму, представленную на рис. 6.
|
Рисунок 2. Базовое решение |
Рисунок 3. Диаграмма Ганта. Шаг 1 (нисходящее планирование) |
При выполнении шага для восходящего планирования берем во внимание свойство транзитности вершины 5. Т.к. ее можно кластеризовать с вершиной 1, то проверим, выполняется ли условие целесообразности данного действия:
ntlevel(n45) ≤ tlevel(n49),
ntlevel(n45) = 9; tlevel(n49) = 15,
Т.к. 9<15, то вершину 5 стоит кластеризовать с вершиной 1.
Результирующая диаграмма Ганта представлена на рис. 7.
В результате время выполнения, по сравнению с базовым решением сократилось на 30%. Для данного примера, описанный в данной статье алгоритм, показывает очень близкий к наилучшему результат, в сравнении с другими существующими алгоритмами [3], не только по критерию минимизации процессорного времени, затраченного на выполнения задачи, но и по количеству необходимых шагов (итераций) для осуществления планирования.
|
Рисунок 4. Диаграмма Ганта. Шаг 1 с (восходящее планирование) |
Рисунок 5. Диаграмма Ганта. Конец шага 1 |
|
Рисунок 6. Диаграмма Ганта. Шаг 2 (нисходящее планирование) |
Рисунок 7. Диаграмма Ганта. Результат |
Для достижения лучших результатов планируется использовать в данном алгоритме методы, позволяющие оптимизировать планирование за счет дублирования вычислений на различных ресурсах, что даст предпосылки к уменьшению временных затрат на коммуникации, что в свою очередь может привести к сокращению времени выполнения всей задачи.
