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

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

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

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

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

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

Название Расписание с ограничением предшествования для двух процессоров Входные данные Ориентированный ациклический граф Выходные данные Расписание минимальной длины, сохраняющее ограничение предшествования

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

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

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

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

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

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

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

При заданном уровневом расписании уровень i переходит на уровень i0 (i0 < i), если последний временной интервал, содержащий задачу уровня i, также содержит задачу уровня i0. Если последняя задача уровня i запланирована с пустым слотом, то считается, что уровень i переходит на уровень 0. Последовательность переходов уровневого расписания представляет собой список уровней, на которые происходит переход. Лексикографически первое расписание переходов – это уровневое расписание, последовательность переходов которого лексикографически больше любой другой последовательности переходов, полученной из уровневого расписания.

Для заданного графа G разбиением G на уровни является разбиение вершин G на два множества таким образом, что уровни 0..: ; k содержатся в одном множестве (верхней части), обозначенном U, а уровни k + 1; : : : ; L – в другом (нижней части), обозначенном L. Для заданного графа G и уровня i i-разбиение G (или разбиение на уровне i) формируется графами Ui и Li, определёнными следующим образом: Ui содержит все узлы x, такие что level(x) < i, а Li содержит все вершины x с level(x) > i. Заметим, что каждое i-разбиение определяет два разных разбиения по уровням в зависимости от того, назначаются ли вершины уровня i верхней или нижней части. Задача x 2 Ui называется свободной по отношению к разбиению на уровне i, если x не имеет предшественников в Li.

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

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

Полный выпуклый двудольный граф G представляет собой тройку (V, W, E), где V = {v\,..., vt} и W = {w\,... , wy) являются непересекающимися множествами вершин. Кроме того, множество ребер E удовлетворяет следующему свойству: если (vi;wj) 2 E, то (vq;wj) 2 E для всех q > i. Таким образом, далее предполагается, что граф является связным.

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

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

Когда число процессоров m произвольно, задача является NP-полной [ ]. Для любого m > 3 сложность остается неизвестной [ ]. Здесь нас интересует случай m = 2. Для случая двух процессоров было предложено несколько эффективных алгоритмов. Последовательные алгоритмы можно найти, в частности, в работах [2, 4, 5]. Первый детерминированный параллельный алгоритм был предложен Хельмбольдом и Майром [7], которые установили его принадлежность к классу NC. Ранее в работе [ ] был предложен рандомизированный алгоритм класса NC для решения этой задачи. Юнг, Серна и Спиракис представляют новый параллельный алгоритм для задачи составления двухпроцессорного расписания, который выполняется за время O(log2 n) и использует O(n3) процессоров на CREW PRAM. Алгоритм снижает количество процессоров алгоритма, приведенного в [ ], с O(n7L(G)2), где L(G) – количество уровней в графе предшествования, до O(n3). Оба алгоритма вычисляют уровневое расписание, которое содержит лексикографически первую последовательность переходов.

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

Теорема 1. Лексикографически первое наибольшее паросочетание полных выпуклых двудольных графов может быть вычислено за время O(log n) на машине CREW PRAM с O(n3/log n) процессорами, где n — количество узлов.

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

Теорема 2. Пусть дан граф предшествования G. Существует параллельный алгоритм для PRAM, который вычисляет все уровни, переходящие на уровень 0 в графе Li, и все задачи на уровне i - 1, которые могут быть запланированы вместе с задачей на уровне i, для i = 1; : : : ; L(G), используя O(n3) процессоров и O(log n) времени.

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

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

  Алгоритм Schedule
  0.	Предварительная обработка
  1.	Найти уровень i, такой что j U i j < n/2 и jL i j < n/2.
  2.	Сопоставить уровни, которые переходят к свободным задачам на уровне i.
  3.	Сопоставить уровни, которые переходят к свободным задачам в Ui.
  4.	Если уровень i (или i + 1) остается несопоставленным, попытаться сопоставить его с несвободной задачей.
  5.	Удалить все задачи, использованные для сопоставления переходов.
  6.	Применить пункты (1)-(5) параллельно к Li и модифицированному Ui.

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

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

Теорема 4 Существует алгоритм класса NC, который находит оптимальное расписание для двух процессоров для любого графа предшествования за время O(log2 n) с использованием O(n3) процессоров.

Применение

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

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

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

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

Любопытно, что вычисление лексикографически первого сопоставления для полных выпуклых двудольных графов принадлежит к классу NC, в противоположность результатам, приведенным в [ ], которые показывают, что многие задачи, определенные с помощью лексикографически первой процедуры на плоскости, являются 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)