Планирование параллельных задач
Планирование параллельных задач (также называемое планированием параллельных заданий) . [1] [2] или планирование параллельной обработки [3] ) — задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования работы . В общей задаче планирования заданий нам даны n заданий J 1 , J 2 , ..., J n с разным временем обработки, которые необходимо запланировать на m машинах, пытаясь минимизировать период выполнения - общую длину расписания. (то есть, когда все задания завершили обработку). В конкретном варианте, известном как планирование параллельных задач , все машины идентичны. Каждое задание j имеет длины параметр p j и размера параметр q j , и оно должно выполняться ровно p j временных шагов ровно на q j машинах параллельно .
Велтман и др. [4] и Дроздовский [3] обозначим эту проблему через в трехпольной нотации, введенной Грэмом и др. [5] P означает, что параллельно работает несколько одинаковых машин; размер j означает, что каждое задание имеет параметр размера; C max означает, что цель состоит в том, чтобы минимизировать максимальное время завершения. Некоторые авторы используют вместо. [1] Обратите внимание, что проблема планирования параллельных машин — это частный случай планирования параллельных задач, когда для всех j , то есть каждое задание должно выполняться на одной машине.
Истоки этой постановки проблемы можно отнести к 1960 году. [6] Для этой задачи не существует алгоритма полиномиальной аппроксимации с коэффициентом меньшим, чем пока не . [ нужна ссылка ]
Определение
[ редактировать ]Есть набор из рабочие места и одинаковые машины. Каждая работа имеет время обработки (также называемая длиной j ) и требует одновременного использования машины во время его выполнения (также называемый размером или шириной j).
График назначает каждое задание к началу времени и набор из машины, на которых будет производиться обработка. Расписание возможно, если каждый процессор выполняет не более одного задания в любой момент времени.Цель задачи, обозначаемая состоит в том, чтобы найти расписание минимальной длины , также называемый интервалом времени расписания.Достаточным условием осуществимости расписания является следующее
.
Если это свойство удовлетворяется для всех моментов запуска, возможное расписание может быть создано путем назначения свободных машин заданиям в каждый момент времени, начиная с времени . [1] [2] Кроме того, количество машинных интервалов, используемых заданиями, и интервалов простоя на каждом временном шаге может быть ограничено . [1] Здесь машинный интервал — это набор последовательных машин максимальной мощности, при котором все машины в этом наборе обрабатывают одну и ту же работу. Машинный интервал полностью определяется индексом его первой и последней машины. Следовательно, можно получить компактный способ кодирования вывода полиномиального размера.
Вычислительная твердость
[ редактировать ]Эта задача является NP-трудной, даже если имеется только две машины и размеры всех работ равны. (т. е. каждое задание должно выполняться только на одной машине). Этот особый случай, обозначаемый , является вариантом задачи о разделах , которая, как известно, является NP-трудной.
При числе машин m не более 3, то есть: для вариантов и , существует псевдополиномиальный алгоритм по времени, который точно решает задачу. [7]
Напротив, при количестве машин не менее 4, то есть: для вариантов для любого , задача также сильно NP-трудна [8] (этот результат улучшил предыдущий результат [7] демонстрирует сильную NP-твердость для ).
Если число машин не ограничено константой, то не может быть алгоритма аппроксимации с коэффициентом аппроксимации меньшим, чем пока не . Это справедливо даже для особого случая, когда время обработки всех заданий равно , поскольку этот особый случай эквивалентен задаче упаковки корзин : каждый временной шаг соответствует ячейке, m — размер корзины, каждое задание соответствует элементу размера q j , а минимизация времени обработки соответствует минимизации количества корзин. .
Варианты
[ редактировать ]Было изучено несколько вариантов этой проблемы. [3] Следующие варианты также рассматривались в сочетании друг с другом.
Непрерывные работы : в этом варианте машины имеют фиксированный порядок. . Вместо назначения заданий какому-либо подмножеству , задания должны быть назначены непрерывному интервалу машин. Эта задача соответствует постановке задачи об упаковке полосы .
Несколько платформ. В этом варианте набор машин разделен на независимые платформы. Запланированное задание может использовать только компьютеры одной платформы и не может охватывать несколько платформ при обработке.
Формованные работы : В этом варианте каждая работа имеет набор возможных машинных счетчиков . За каждый счет , задание может обрабатываться на d машинах параллельно, и в этом случае время его обработки будет . Чтобы запланировать задание , алгоритм должен выбрать количество машин и назначьте j начальное время и чтобы машины за временной интервал Обычное предположение для такого рода задач состоит в том, что общая рабочая нагрузка задания, которая определяется как , не увеличивается для увеличения числа машин.
Даты выпуска : В этом варианте обозначены , не все задания доступны в момент времени 0; каждое задание j становится доступным в фиксированное и известное время r j . Это должно быть запланировано после этого времени.
Упреждение : в этом варианте обозначается , можно прервать уже запущенные задания и запланировать другие задания, которые станут доступны в это время.
Алгоритмы
[ редактировать ]Алгоритм планирования списка Гэри и Грэма [9] имеет абсолютное соотношение , как указали Турек и др. [10] и Людвиг и Тивари. [11] Фельдманн, Скалл и Тенг [12] заметил, что длина невытесняющего расписания, создаваемого алгоритмом планирования списка, на самом деле не превышает раз оптимальную продолжительность упреждающего цикла.Схема полиномиальной аппроксимации (PTAS) для случая, когда число процессоров является константой, обозначаемой , было представлено Amoura et al. [13] и Янсен и др. [14] Позже Янсен и Тёле [2] нашел PTAS для случая, когда количество процессоров полиномиально ограничено количеством заданий. В этом алгоритме количество машин полиномиально зависит от временной сложности алгоритма. Поскольку, как правило, количество машин выражается только в логарифмической величине размера экземпляра, этот алгоритм также представляет собой схему псевдополиномиальной аппроксимации времени. А -приближение было дано Янсеном, [15] что закрывает разрыв до нижней границы за исключением сколь угодно малого .
Различия между смежными и несмежными работами
[ редактировать ]В примере задачи планирования параллельных задач оптимальный период выполнения может различаться в зависимости от ограничения на соседство машин. Если задания можно запланировать на несмежных машинах, оптимальный период выполнения может быть меньше, чем в случае, если их приходится планировать на смежных машинах.Разница между смежными и несмежными графиками была впервые продемонстрирована в 1992 году. [16] на примере с задачи, процессоры, , и .Блондек и др. [17] изучил эти так называемые c/nc-разности и доказал следующие положения:
- Для возникновения ac/nc-разности должно быть не менее трех задач с
- Для возникновения ac/nc-разности должно быть не менее трех задач с
- Чтобы ac/nc-разница возникла, по крайней мере требуются процессоры (и существует экземпляр с ac/nc-разницей с ).
- Для возникновения разницы ac/nc длина несмежного расписания должна быть не менее
- Максимальная c/nc-разность по крайней мере и самое большее
- Решение о том, существует ли разница c/nc в данном случае, является NP-полным.
Кроме того, они выдвинули следующие две гипотезы, которые остаются недоказанными:
- Чтобы ac/nc-разница возникла, по крайней мере нужны задачи.
Связанные проблемы
[ редактировать ]Существуют связанные с этим проблемы планирования, в которых каждое задание состоит из нескольких операций, которые должны выполняться последовательно (а не параллельно). Это проблемы планирования открытых цехов , планирования поточных цехов и планирования цехов .
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Йоханнес, Берит (01 октября 2006 г.). «Планирование параллельных работ для минимизации времени выполнения». Журнал планирования . 9 (5): 433–452. дои : 10.1007/s10951-006-8497-6 . hdl : 20.500.11850/36804 . ISSN 1099-1425 . S2CID 18819458 .
- ^ Jump up to: а б с Янсен, Клаус; Тёле, Ральф. (01.01.2010). «Алгоритмы аппроксимации для планирования параллельных заданий». SIAM Journal по вычислительной технике . 39 (8): 3571–3615. дои : 10.1137/080736491 . ISSN 0097-5397 .
- ^ Jump up to: а б с Дроздовский, Мацей (2009). «Планирование параллельной обработки». Компьютерные коммуникации и сети . дои : 10.1007/978-1-84882-310-5 . ISBN 978-1-84882-309-9 . ISSN 1617-7975 .
- ^ Вельтман, Б; Лагевег, Б.Дж.; Ленстра, Дж. К. (1 декабря 1990 г.). «Многопроцессорное планирование с задержками связи» . Параллельные вычисления . 16 (2): 173–182. дои : 10.1016/0167-8191(90)90056-F . ISSN 0167-8191 .
- ^ Грэм, РЛ; Лоулер, Эл.; Ленстра, Дж. К.; Риннуй Кан, AHG (1979). «Оптимизация и аппроксимация в детерминированном секвенировании и планировании: обзор» (PDF) . Труды Института перспективных исследований по дискретной оптимизации и системным применениям Группы системных наук НАТО и Симпозиума по дискретной оптимизации . Эльзевир. стр. (5) 287–326.
- ^ Кодд, Э.Ф. (1 июня 1960 г.). «Мультипрограммное планирование» . Коммуникации АКМ . 3 (6): 347–350. дои : 10.1145/367297.367317 . S2CID 14701351 .
- ^ Jump up to: а б Ду, Цзяньчжун.; Люнг, Джозеф Ю.-Т. (1 ноября 1989 г.). «Сложность планирования систем параллельных задач». SIAM Journal по дискретной математике . 2 (4): 473–487. дои : 10.1137/0402042 . ISSN 0895-4801 .
- ^ Хеннинг, Сёрен; Янсен, Клаус; Рау, Малин; Шмарье, Ларс (1 января 2020 г.). «Результаты сложности и неаппроксимируемости для параллельного планирования задач и упаковки полос». Теория вычислительных систем . 64 (1): 120–140. arXiv : 1705.04587 . дои : 10.1007/s00224-019-09910-6 . ISSN 1433-0490 . S2CID 67168004 .
- ^ Гэри, MR; Грэм, Р.Л. (1 июня 1975 г.). «Границы многопроцессорного планирования с ограничениями ресурсов» . SIAM Journal по вычислительной технике . 4 (2): 187–200. дои : 10.1137/0204015 . ISSN 0097-5397 .
- ^ Турек, Джон; Вольф, Джоэл Л.; Ю, Филип С. «Приблизительные алгоритмы планирования распараллеливаемых задач | Материалы четвертого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам». dl.acm.org . дои : 10.1145/140901.141909 . S2CID 15607549 .
- ^ Людвиг, Вальтер; Тивари, Прасун (1994). «Планирование податливых и неподатливых параллельных задач | Материалы пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам» . Пятый ежегодный симпозиум {ACM-SIAM} по дискретным алгоритмам (SODA) : 167–176.
- ^ Фельдманн, Аня; Сгалл, Иржи; Дэн, Шан-Хуа (1 августа 1994 г.). «Динамическое планирование на параллельных машинах» . Теоретическая информатика . 130 (1): 49–72. дои : 10.1016/0304-3975(94)90152-X . ISSN 0304-3975 .
- ^ Амура, Абдель Крим; Бампис, Эврипидис; Кеньон, Клэр; Манусакис, Яннис (1 февраля 2002 г.). «Планирование независимых многопроцессорных задач». Алгоритмика . 32 (2): 247–261. дои : 10.1007/s00453-001-0076-9 . ISSN 1432-0541 . S2CID 17256951 .
- ^ Янсен, Клаус; Порколаб, Лорант (1 марта 2002 г.). «Схемы аппроксимации линейного времени для планирования гибких параллельных задач». Алгоритмика . 32 (3): 507–520. дои : 10.1007/s00453-001-0085-8 . hdl : 11858/00-001M-0000-0014-7B6C-D . ISSN 1432-0541 . S2CID 2019475 .
- ^ Янсен, Клаус (2012). «Алгоритм аппроксимации A (3/2 + ε) для планирования формируемых и неформуемых параллельных задач | Материалы двадцать четвертого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах». 24-й симпозиум {ACM} по параллелизму в алгоритмах и архитектурах, {SPAA} . дои : 10.1145/2312005.2312048 . S2CID 6586439 .
- ^ «Приблизительные алгоритмы планирования распараллеливаемых задач | Материалы четвертого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам». дои : 10.1145/140901.141909 . S2CID 15607549 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Блондек, Иво; Дроздовский, Мацей; Гинан, Фредерик; Шеплер, Ксавье (1 октября 2015 г.). «О планировании смежных и несмежных параллельных задач» . Журнал планирования . 18 (5): 487–495. дои : 10.1007/s10951-015-0427-z . ISSN 1099-1425 .