Параллельные алгоритмы для двухпроцессорного расписания с ограничением предшествования

Материал из WEGA
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Оптимальное расписание для двух процессоров

Постановка задачи

В общем случае при составлении многопроцессорного расписания с учетом предшествования задается набор из [math]\displaystyle{ n }[/math] задач, которые должны быть выполнены на [math]\displaystyle{ m }[/math] процессорах. Каждая задача требует ровно одной единицы времени выполнения и может запускаться на любом процессоре. Ориентированный ациклический граф определяет ограничения предшествования, где наличие ребра от задачи [math]\displaystyle{ x }[/math] к задаче [math]\displaystyle{ y }[/math] означает, что задача [math]\displaystyle{ x }[/math] должна быть завершена до начала выполнения задачи [math]\displaystyle{ y }[/math]. Решением задачи является расписание минимальной длины, указывающее, когда запускается каждая задача. В работе Юнга, Серны и Спиракиса представлен параллельный алгоритм (на машине PRAM), который решает вышеуказанную задачу для частного случая [math]\displaystyle{ m = 2 }[/math], то есть наличия двух параллельных процессоров.


Задача составления расписания с ограничением предшествования для двух процессоров определяется ориентированным ациклическим графом [math]\displaystyle{ G = (V, E) }[/math]. Вершины графа представляют задачи, выполняемые за единичное время, а ребра определяют ограничения предшествования между задачами. Если существует ребро от вершины [math]\displaystyle{ x }[/math] к вершине [math]\displaystyle{ y }[/math], то [math]\displaystyle{ x }[/math] является непосредственным предшественником [math]\displaystyle{ y }[/math]. Предшественник представляет собой транзитивное замыкание отношения непосредственного предшествования, а преемник – его симметричный аналог. Расписание для двух процессоров представляет собой распределение задач по временным единицам [math]\displaystyle{ 1, ..., t }[/math] таким образом, что каждой задаче присваивается ровно одна единица времени, на одну единицу времени назначаются максимум две задачи, и если [math]\displaystyle{ x }[/math] является предшественником [math]\displaystyle{ y }[/math], то [math]\displaystyle{ x }[/math] присваивается временная единица, меньшая, чем [math]\displaystyle{ y }[/math]. Длина расписания равна [math]\displaystyle{ t }[/math]. Расписание с минимальной длиной является оптимальным расписанием. Таким образом, задача состоит в следующем:

Название: расписание с ограничением предшествования для двух процессоров

Входные данные: ориентированный ациклический граф

Выходные данные: расписание минимальной длины, сохраняющее ограничение предшествования


Предварительные замечания

Алгоритм предполагает, что задачи разделены на уровни следующим образом:

(1) Каждая задача будет назначена только одному уровню

(2) Задачи, не имеющие преемников, будут назначены уровню 1

(3) Для каждого уровня [math]\displaystyle{ i }[/math] все задачи, которые являются непосредственными предшественниками задач уровня [math]\displaystyle{ i }[/math], будут назначены уровню [math]\displaystyle{ i + 1 }[/math]


Очевидно, что топологическая сортировка выполнит вышеуказанное разделение, и это может быть сделано с помощью алгоритма класса NC, который использует [math]\displaystyle{ O(n^3) }[/math] процессоров и [math]\displaystyle{ O(log \; n) }[/math] времени, см. [3]. Далее в статье предполагается, что разбиение по уровням задается как часть входных данных. Для удобства добавляются две специальные задачи, [math]\displaystyle{ t_0 }[/math] и [math]\displaystyle{ t^* }[/math], так что исходный граф может быть представлен как граф, образованный всеми задачами, которые являются преемниками [math]\displaystyle{ t_0 }[/math] и предшественниками [math]\displaystyle{ t^* }[/math]. Таким образом, [math]\displaystyle{ t_0 }[/math] является предшественницей всех задач в системе (фактически непосредственной предшественницей задач на самом высоком уровне [math]\displaystyle{ L(G) }[/math]), а [math]\displaystyle{ t^* }[/math] – преемником всех задач в системе (непосредственным преемником задач уровня 1).


Заметим, что если две задачи находятся на одном уровне, их можно составить в пару. Если же [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] находятся на разных уровнях, их можно составить в пару только в том случае, если ни одна из них не является предшественницей другой. Обозначим за [math]\displaystyle{ L(G) }[/math] количество уровней в данном графе предшествования [math]\displaystyle{ G }[/math]. Уровневое расписание планирует задачи по уровням. Точнее, предположим, что уровни [math]\displaystyle{ L(G), ..., i + 1 }[/math] уже спланированы, и на уровне [math]\displaystyle{ i }[/math] осталось [math]\displaystyle{ k }[/math] неспланированных задач. Когда [math]\displaystyle{ k }[/math] четно, эти задачи составляются в пары друг с другом. Когда [math]\displaystyle{ k }[/math] нечетно, [math]\displaystyle{ k - 1 }[/math] задач составляются в пары, а оставшаяся задача может (но не обязательно) быть сопоставлена с задачей более низкого уровня.


При заданном уровневом расписании уровень [math]\displaystyle{ i }[/math] переходит на уровень [math]\displaystyle{ i' }[/math] [math]\displaystyle{ (i' \lt i) }[/math], если последний временной интервал, содержащий задачу уровня [math]\displaystyle{ i }[/math], также содержит задачу уровня [math]\displaystyle{ i' }[/math]. Если последняя задача уровня [math]\displaystyle{ i }[/math] запланирована с пустым слотом, то считается, что уровень [math]\displaystyle{ i }[/math] переходит на уровень 0. Последовательность переходов уровневого расписания представляет собой список уровней, на которые происходит переход. Лексикографически первое расписание переходов – это уровневое расписание, последовательность переходов которого лексикографически больше любой другой последовательности переходов, полученной из уровневого расписания.


Для заданного графа G разбиением на уровни является разбиение вершин G на два множества таким образом, что уровни [math]\displaystyle{ 0,..., k }[/math] содержатся в одном множестве (верхней части), обозначенном [math]\displaystyle{ U }[/math], а уровни [math]\displaystyle{ k + 1\lt ...\lt L }[/math] – в другом (нижней части), обозначенном [math]\displaystyle{ L }[/math]. Для заданного графа [math]\displaystyle{ G }[/math] и уровня [math]\displaystyle{ i }[/math] [math]\displaystyle{ i }[/math]-разбиение [math]\displaystyle{ G }[/math] (или разбиение на уровне [math]\displaystyle{ i }[/math]) формируется графами [math]\displaystyle{ U_i }[/math] и [math]\displaystyle{ L_i }[/math], определёнными следующим образом: [math]\displaystyle{ U_i }[/math] содержит все узлы [math]\displaystyle{ x }[/math], такие что [math]\displaystyle{ level(x) \lt i }[/math], а [math]\displaystyle{ L_i }[/math] содержит все вершины [math]\displaystyle{ x }[/math] с [math]\displaystyle{ level(x) \gt i }[/math]. Заметим, что каждое [math]\displaystyle{ i }[/math]-разбиение определяет два разных разбиения по уровням в зависимости от того, назначаются ли вершины уровня [math]\displaystyle{ i }[/math] верхней или нижней части. Задача [math]\displaystyle{ x \in U_i }[/math] называется свободной по отношению к разбиению на уровне [math]\displaystyle{ i }[/math], если [math]\displaystyle{ x }[/math] не имеет предшественников в [math]\displaystyle{ L_i }[/math].


Вспомогательные задачи

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


Полный выпуклый двудольный граф [math]\displaystyle{ G }[/math] представляет собой тройку [math]\displaystyle{ (V, W, E) }[/math], где [math]\displaystyle{ V = \{ v_1, ..., v_k \} }[/math] и [math]\displaystyle{ W = \{ w_1, ... , w_k') \} }[/math] являются непересекающимися множествами вершин. Кроме того, множество ребер [math]\displaystyle{ E }[/math] удовлетворяет следующему свойству: если [math]\displaystyle{ (v_i, w_j) \in E }[/math], то [math]\displaystyle{ (v_q, w_j) \in E }[/math] для всех [math]\displaystyle{ q \ge i }[/math]. Таким образом, далее предполагается, что граф является связным.


Множество [math]\displaystyle{ F \subseteq E }[/math] является паросочетанием в графе [math]\displaystyle{ G = (V, W, E) }[/math] в том и только том случае, если никакие два ребра в [math]\displaystyle{ F }[/math] не имеют общей конечной точки. Наибольшим паросочетанием является такое паросочетание, которое не может быть расширено добавлением какого-либо ребра в [math]\displaystyle{ G }[/math]. Лексикографически первое наибольшее паросочетание – это наибольшее паросочетание, отсортированный список ребер которого является лексикографически первым среди всех наибольших паросочетаний в [math]\displaystyle{ G }[/math].

Основные результаты

Когда число процессоров [math]\displaystyle{ m }[/math] произвольно, задача является NP-полной [8]. Для любого [math]\displaystyle{ m \ge 3 }[/math] сложность остается неизвестной [6]. Здесь нас интересует случай [math]\displaystyle{ m = 2 }[/math]. Для случая двух процессоров было предложено несколько эффективных алгоритмов. Последовательные алгоритмы можно найти, в частности, в работах [2, 4, 5]. Первый детерминированный параллельный алгоритм был предложен Хельмбольдом и Майром [7], которые установили его принадлежность к классу NC. Ранее в работе [9] был предложен рандомизированный алгоритм класса NC для решения этой задачи. Юнг, Серна и Спиракис представляют новый параллельный алгоритм для задачи составления двухпроцессорного расписания, который выполняется за время [math]\displaystyle{ O(log^2 \; n) }[/math] и использует [math]\displaystyle{ O(n^3) }[/math] процессоров на CREW PRAM. Алгоритм снижает количество процессоров алгоритма, приведенного в [7], с [math]\displaystyle{ O(n^7 L(G)^2) }[/math], где [math]\displaystyle{ L(G) }[/math] – количество уровней в графе предшествования, до [math]\displaystyle{ O(n^3) }[/math]. Оба алгоритма вычисляют уровневое расписание, которое содержит лексикографически первую последовательность переходов.


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


Теорема 1. Лексикографически первое наибольшее паросочетание полных выпуклых двудольных графов может быть вычислено за время [math]\displaystyle{ O(log \; n) }[/math] на машине CREW PRAM с [math]\displaystyle{ O(n^3/log \; n) }[/math] процессорами, где [math]\displaystyle{ n }[/math] — количество вершин.


Предыдущий алгоритм используется для эффективного параллельного решения двух связанных задач.


Теорема 2. Пусть дан граф предшествования [math]\displaystyle{ G }[/math]. Существует параллельный алгоритм для PRAM, который вычисляет все уровни, переходящие на уровень 0 в графе [math]\displaystyle{ L_i }[/math], и все задачи на уровне [math]\displaystyle{ i - 1 }[/math], которые могут быть запланированы вместе с задачей на уровне [math]\displaystyle{ i }[/math], для [math]\displaystyle{ i = 1, ..., L(G) }[/math], используя [math]\displaystyle{ O(n^3) }[/math] процессоров и [math]\displaystyle{ O(log^2 \; n) }[/math] времени.


Теорема 3. Пусть имеется разбиение графа [math]\displaystyle{ G }[/math] на уровни вместе с уровнями в нижней части, в котором остается одна задача, которую необходимо составить в пару с какой-либо другой задачей в верхней части графа. Существует параллельный алгоритм для PRAM, который вычисляет соответствующие задачи за время [math]\displaystyle{ O(log \; n) }[/math], используя [math]\displaystyle{ n^3/log \; n }[/math] процессоров.


С помощью этих строительных блоков алгоритм для создания двухпроцессорного расписания с ограничением предшествования начинается с некоторой предварительной обработки, после которой производится адекватная декомпозиция, гарантирующая, что при каждом рекурсивном вызове параллельно решается ряд задач, число которых составляет половину от исходного. Эта рекурсивная схема выглядит следующим образом:


Алгоритм Schedule 

  0.	Предварительная обработка
  1.	Найти уровень [math]\displaystyle{ i }[/math], такой что [math]\displaystyle{ |U_i| \le n/2 }[/math] и [math]\displaystyle{ |L_i| \le n/2 }[/math].
  2.	Сопоставить уровни, которые переходят к свободным задачам на уровне [math]\displaystyle{ i }[/math].
  3.	Сопоставить уровни, которые переходят к свободным задачам в [math]\displaystyle{ U_i }[/math].
  4.	Если уровень [math]\displaystyle{ i }[/math] (или [math]\displaystyle{ i + 1 }[/math]) остается несопоставленным, попытаться сопоставить его с несвободной задачей.
  5.	Удалить все задачи, использованные для сопоставления переходов.
  6.	Применить пункты (1)-(5) параллельно к [math]\displaystyle{ L_i }[/math] и модифицированному [math]\displaystyle{ U_i }[/math].


Алгоритм Schedule останавливается, когда у соответствующего графа остается только один уровень.


Поправка и границы сложности для алгоритма Schedule следуют из предыдущих результатов, позволяя получить следующее заключение:


Теорема 4. Существует алгоритм класса NC, который находит оптимальное расписание для двух процессоров для любого графа предшествования за время [math]\displaystyle{ O(log^2 \; n) }[/math] с использованием [math]\displaystyle{ O(n^3) }[/math] процессоров.

Применение

Фундаментальной задачей во многих вариантах применения является разработка правильного расписания, удовлетворяющего набору ограничений. Назначение людей на рабочие места, встреч на соответствующие помещения или курсов на периоды выпускных экзаменов — все это разные примеры задач составления расписаний. Ключевым и критически важным алгоритмом в параллельной обработке является алгоритм, сопоставляющий задачи с процессорами. От производительности такого алгоритма зависит много свойств системы, таких как балансировка нагрузки, общее время выполнения и т. д. Задачи планирования значительно различаются по характеру ограничений, которые должны удовлетворяться, типу процессоров и типу желаемого расписания.


Задачи планирования с ограничениями предшествования для ориентированных ациклических графов имеют наиболее прямое практическое применение в задачах, возникающих при параллельной обработке. В частности, в системах, где вычисления разбиваются перед планированием на задачи примерно одинакового размера и вычисляется соответствующий частичный порядок между ними. Эти ограничения должны определять ориентированный ациклический граф (ациклический потому, что цикл в ограничениях предшествования представляет собой ситуацию «ловушки», которая не может быть разрешена).

Открытые вопросы

Представленный здесь параллельный детерминированный алгоритм для задачи составления двухпроцессорного расписания уменьшает количество процессоров, требуемое алгоритму Хельмбольда и Майра для этой задачи [7]. Однако границы сложности далеки от оптимальных: напомним, что последовательный алгоритм, приведенный в работе [5], использует время [math]\displaystyle{ O(e + n \alpha (n)) }[/math], где [math]\displaystyle{ e }[/math] – количество ребер в графе предшествования, а [math]\displaystyle{ \alpha (n) }[/math] – обратная функция Аккермана. Такой оптимальный алгоритм может иметь совершенно другой подход, в котором шаг выравнивания не используется.


Любопытно, что вычисление лексикографически первого сопоставления для полных выпуклых двудольных графов принадлежит к классу NC, в противоположность результатам, приведенным в [1], которые показывают, что многие задачи, определенные с помощью лексикографически первой процедуры на плоскости, являются P-полными. Интересно было бы показать, все ли эти задачи попадают в класс NC, когда они являются выпуклыми.

См. также

Литература

1. Attallah, M., Callahan, P., Goodrich, M.: P-complete geometric problems. Int. J. Comput. Geom. Appl. 3(4),443-462 (1993)

2. Coffman, E.G., Graham, R.L.: Optimal scheduling for two processors systems. Acta Informatica 1, 200-213 (1972)

3. Dekel, E., Nassimi, D., Sahni, S.: Parallel matrix and graph algorithms. SIAM J. Comput. 10,657-675 (1981)

4. Fujii, M., Kasami, T., Ninomiya, K.: Optimal sequencing of two equivalent processors. SIAM J. Comput. 17,784-789 (1969)

5. Gabow, H.N.: An almost linear time algorithm for two processors scheduling. J. ACM 29(3), 766-780 (1982)

6. Garey, M.R.,Johnson, D.S.: Computers and Intractability: A Guide to the theory of NP completeness. Freeman, San Francisco (1979)

7. Helmbold, D., Mayr, E.: Two processor scheduling is in NC. SIAM J. Comput. 16(4), 747-756 (1987)

8. Ullman, J.D.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384-393 (1975)

9. Vazirani,U.,Vazirani,V.: Two-processor scheduling problem is in random NC. SIAM J. Comput. 18(4), 1140-1148 (1989)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Параллельные_алгоритмы_для_двухпроцессорного_расписания_с_ограничением_предшествования&oldid=16155