Планирование параллельных задач

Планирование параллельных задач (также называемое планированием параллельных заданий) . ^[1]^[2] или планирование параллельной обработки ^[3]) — задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования работы . В общей задаче планирования заданий нам даны n заданий J ₁ , J ₂ , ..., J _n с разным временем обработки, которые необходимо запланировать на m машинах, пытаясь минимизировать период выполнения - общую длину расписания. (то есть, когда все задания завершили обработку). В конкретном варианте, известном как планирование параллельных задач , все машины идентичны. Каждое задание j имеет длины параметр p _j и размера параметр q _j , и оно должно выполняться ровно p _j временных шагов ровно на q _j машинах параллельно .

Велтман и др. ^[4] и Дроздовский ^[3] обозначим эту проблему через $P|size_{j}|C_{\max }$ в трехпольной нотации, введенной Грэмом и др. ^[5] P означает, что параллельно работает несколько одинаковых машин; размер _j означает, что каждое задание имеет параметр размера; C _max означает, что цель состоит в том, чтобы минимизировать максимальное время завершения. Некоторые авторы используют $P|m_{j}|C_{\max }$ вместо. ^[1] Обратите внимание, что проблема планирования параллельных машин — это частный случай планирования параллельных задач, когда $size_{j}=1$ для всех j , то есть каждое задание должно выполняться на одной машине.

Истоки этой постановки проблемы можно отнести к 1960 году. ^[6] Для этой задачи не существует алгоритма полиномиальной аппроксимации с коэффициентом меньшим, чем $3/2$ пока не $P=NP$ . ^{[ нужна ссылка ]}

Определение

Есть набор ${\mathcal {J}}$ из $n$ рабочие места и $m$ одинаковые машины. Каждая работа $j\in {\mathcal {J}}$ имеет время обработки $p_{j}\in \mathbb {N}$ (также называемая длиной j ) и требует одновременного использования $q_{j}\in \mathbb {N}$ машины во время его выполнения (также называемый размером или шириной j).

График назначает каждое задание $j\in {\mathcal {J}}$ к началу времени $s_{j}\in \mathbb {N} _{0}$ и набор $m_{j}\subseteq \{1,\dots ,m\}$ из $|m_{j}|=q_{j}$ машины, на которых будет производиться обработка. Расписание возможно, если каждый процессор выполняет не более одного задания в любой момент времени.Цель задачи, обозначаемая $P|size_{j}|C_{\max }$ состоит в том, чтобы найти расписание минимальной длины $C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})$ , также называемый интервалом времени расписания.Достаточным условием осуществимости расписания является следующее

$\sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}$ .

Если это свойство удовлетворяется для всех моментов запуска, возможное расписание может быть создано путем назначения свободных машин заданиям в каждый момент времени, начиная с времени $t=0$ . ^[1]^[2] Кроме того, количество машинных интервалов, используемых заданиями, и интервалов простоя на каждом временном шаге может быть ограничено $|{\mathcal {J}}|+1$ . ^[1] Здесь машинный интервал — это набор последовательных машин максимальной мощности, при котором все машины в этом наборе обрабатывают одну и ту же работу. Машинный интервал полностью определяется индексом его первой и последней машины. Следовательно, можно получить компактный способ кодирования вывода полиномиального размера.

Вычислительная твердость

Эта задача является NP-трудной, даже если имеется только две машины и размеры всех работ равны. $q_{j}=1$ (т. е. каждое задание должно выполняться только на одной машине). Этот особый случай, обозначаемый $P2||C_{\max }$ , является вариантом задачи о разделах , которая, как известно, является NP-трудной.

При числе машин m не более 3, то есть: для вариантов $P2|size_{j}|C_{\max }$ и $P3|size_{j}|C_{\max }$ , существует псевдополиномиальный алгоритм по времени, который точно решает задачу. ^[7]

Напротив, при количестве машин не менее 4, то есть: для вариантов $Pm|size_{j}|C_{\max }$ для любого $m\geq 4$ , задача также сильно NP-трудна ^[8] (этот результат улучшил предыдущий результат ^[7] демонстрирует сильную NP-твердость для $m\geq 5$ ).

Если число машин не ограничено константой, то не может быть алгоритма аппроксимации с коэффициентом аппроксимации меньшим, чем $3/2$ пока не $P=NP$ . Это справедливо даже для особого случая, когда время обработки всех заданий равно $p_{j}=1$ , поскольку этот особый случай эквивалентен задаче упаковки корзин : каждый временной шаг соответствует ячейке, m — размер корзины, каждое задание соответствует элементу размера q _j , а минимизация времени обработки соответствует минимизации количества корзин. .

Варианты

Было изучено несколько вариантов этой проблемы. ^[3] Следующие варианты также рассматривались в сочетании друг с другом.

Непрерывные работы : в этом варианте машины имеют фиксированный порядок. $(M_{1},\dots ,M_{m})$ . Вместо назначения заданий какому-либо подмножеству $m_{j}\subseteq \{M_{1},\dots ,M_{m}\}$ , задания должны быть назначены непрерывному интервалу машин. Эта задача соответствует постановке задачи об упаковке полосы .

Несколько платформ. В этом варианте набор машин разделен на независимые платформы. Запланированное задание может использовать только компьютеры одной платформы и не может охватывать несколько платформ при обработке.

Формованные работы : В этом варианте каждая работа $j\in {\mathcal {J}}$ имеет набор возможных машинных счетчиков $D_{j}\subseteq \{1,\dots m\}$ . За каждый счет $d\in D_{j}$ , задание может обрабатываться на d машинах параллельно, и в этом случае время его обработки будет $p_{j,d}$ . Чтобы запланировать задание $j\in {\mathcal {J}}$ , алгоритм должен выбрать количество машин $d\in D_{j}$ и назначьте j начальное время $s_{j}$ и чтобы $d$ машины за временной интервал $[s_{j},s_{j}+p_{j,d}).$ Обычное предположение для такого рода задач состоит в том, что общая рабочая нагрузка задания, которая определяется как $d\cdot p_{j,d}$ , не увеличивается для увеличения числа машин.

Даты выпуска : В этом варианте обозначены $P|size_{j},r_{j}|C_{\max }$ , не все задания доступны в момент времени 0; каждое задание j становится доступным в фиксированное и известное время r _j . Это должно быть запланировано после этого времени.

Упреждение : в этом варианте обозначается $P|size_{j},r_{j},{\text{pmtn}}|C_{\max }$ , можно прервать уже запущенные задания и запланировать другие задания, которые станут доступны в это время.

Алгоритмы

Алгоритм планирования списка Гэри и Грэма ^[9] имеет абсолютное соотношение $2$ , как указали Турек и др. ^[10] и Людвиг и Тивари. ^[11] Фельдманн, Скалл и Тенг ^[12] заметил, что длина невытесняющего расписания, создаваемого алгоритмом планирования списка, на самом деле не превышает $(2-1/m)$ раз оптимальную продолжительность упреждающего цикла.Схема полиномиальной аппроксимации (PTAS) для случая, когда число $m$ процессоров является константой, обозначаемой $Pm|size_{j}|C_{\max }$ , было представлено Amoura et al. ^[13] и Янсен и др. ^[14]Позже Янсен и Тёле ^[2] нашел PTAS для случая, когда количество процессоров полиномиально ограничено количеством заданий. В этом алгоритме количество машин полиномиально зависит от временной сложности алгоритма. Поскольку, как правило, количество машин выражается только в логарифмической величине размера экземпляра, этот алгоритм также представляет собой схему псевдополиномиальной аппроксимации времени. А $(3/2+\varepsilon )$ -приближение было дано Янсеном, ^[15] что закрывает разрыв до нижней границы $3/2$ за исключением сколь угодно малого $\varepsilon$ .

Различия между смежными и несмежными работами

В примере задачи планирования параллельных задач оптимальный период выполнения может различаться в зависимости от ограничения на соседство машин. Если задания можно запланировать на несмежных машинах, оптимальный период выполнения может быть меньше, чем в случае, если их приходится планировать на смежных машинах.Разница между смежными и несмежными графиками была впервые продемонстрирована в 1992 году. ^[16] на примере с $n=8$ задачи, $m=23$ процессоры, $C_{\max }^{nc}=17$ , и $C_{\max }^{c}=18$ .Блондек и др. ^[17] изучил эти так называемые c/nc-разности и доказал следующие положения:

Для возникновения ac/nc-разности должно быть не менее трех задач с $q_{j}>1.$
Для возникновения ac/nc-разности должно быть не менее трех задач с $p_{j}>1.$
Чтобы ac/nc-разница возникла, по крайней мере $m=4$ требуются процессоры (и существует экземпляр с ac/nc-разницей с $m=4$ ).
Для возникновения разницы ac/nc длина несмежного расписания должна быть не менее $C_{\max }^{nc}=4.$
Максимальная c/nc-разность $\sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)$ по крайней мере $5/4$ и самое большее $2.$
Решение о том, существует ли разница c/nc в данном случае, является NP-полным.

Кроме того, они выдвинули следующие две гипотезы, которые остаются недоказанными:

Чтобы ac/nc-разница возникла, по крайней мере $n=7$ нужны задачи.
$\sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4$

Связанные проблемы

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

Ссылки

^ 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 .

[Johannes-1] 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 .

[PPTAS-2] Jump up to: ^а ^б ^с Янсен, Клаус; Тёле, Ральф. (01.01.2010). «Алгоритмы аппроксимации для планирования параллельных заданий». SIAM Journal по вычислительной технике . 39 (8): 3571–3615. дои : 10.1137/080736491 . ISSN 0097-5397 .

[:0-3] Jump up to: ^а ^б ^с Дроздовский, Мацей (2009). «Планирование параллельной обработки». Компьютерные коммуникации и сети . дои : 10.1007/978-1-84882-310-5 . ISBN 978-1-84882-309-9 . ISSN 1617-7975 .

[4] Вельтман, Б; Лагевег, Б.Дж.; Ленстра, Дж. К. (1 декабря 1990 г.). «Многопроцессорное планирование с задержками связи» . Параллельные вычисления . 16 (2): 173–182. дои : 10.1016/0167-8191(90)90056-F . ISSN 0167-8191 .

[initial_specification-5] Грэм, РЛ; Лоулер, Эл.; Ленстра, Дж. К.; Риннуй Кан, AHG (1979). «Оптимизация и аппроксимация в детерминированном секвенировании и планировании: обзор» (PDF) . Труды Института перспективных исследований по дискретной оптимизации и системным применениям Группы системных наук НАТО и Симпозиума по дискретной оптимизации . Эльзевир. стр. (5) 287–326.

[6] Кодд, Э.Ф. (1 июня 1960 г.). «Мультипрограммное планирование» . Коммуникации АКМ . 3 (6): 347–350. дои : 10.1145/367297.367317 . S2CID 14701351 .

[strongHardness-7] Jump up to: ^а ^б Ду, Цзяньчжун.; Люнг, Джозеф Ю.-Т. (1 ноября 1989 г.). «Сложность планирования систем параллельных задач». SIAM Journal по дискретной математике . 2 (4): 473–487. дои : 10.1137/0402042 . ISSN 0895-4801 .

[4machines-8] Хеннинг, Сёрен; Янсен, Клаус; Рау, Малин; Шмарье, Ларс (1 января 2020 г.). «Результаты сложности и неаппроксимируемости для параллельного планирования задач и упаковки полос». Теория вычислительных систем . 64 (1): 120–140. arXiv : 1705.04587 . дои : 10.1007/s00224-019-09910-6 . ISSN 1433-0490 . S2CID 67168004 .

[9] Гэри, MR; Грэм, Р.Л. (1 июня 1975 г.). «Границы многопроцессорного планирования с ограничениями ресурсов» . SIAM Journal по вычислительной технике . 4 (2): 187–200. дои : 10.1137/0204015 . ISSN 0097-5397 .

[10] Турек, Джон; Вольф, Джоэл Л.; Ю, Филип С. «Приблизительные алгоритмы планирования распараллеливаемых задач | Материалы четвертого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам». dl.acm.org . дои : 10.1145/140901.141909 . S2CID 15607549 .

[11] Людвиг, Вальтер; Тивари, Прасун (1994). «Планирование податливых и неподатливых параллельных задач | Материалы пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам» . Пятый ежегодный симпозиум {ACM-SIAM} по дискретным алгоритмам (SODA) : 167–176.

[12] Фельдманн, Аня; Сгалл, Иржи; Дэн, Шан-Хуа (1 августа 1994 г.). «Динамическое планирование на параллельных машинах» . Теоретическая информатика . 130 (1): 49–72. дои : 10.1016/0304-3975(94)90152-X . ISSN 0304-3975 .

[13] Амура, Абдель Крим; Бампис, Эврипидис; Кеньон, Клэр; Манусакис, Яннис (1 февраля 2002 г.). «Планирование независимых многопроцессорных задач». Алгоритмика . 32 (2): 247–261. дои : 10.1007/s00453-001-0076-9 . ISSN 1432-0541 . S2CID 17256951 .

[14] Янсен, Клаус; Порколаб, Лорант (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 .

[15] Янсен, Клаус (2012). «Алгоритм аппроксимации A (3/2 + ε) для планирования формируемых и неформуемых параллельных задач | Материалы двадцать четвертого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах». 24-й симпозиум {ACM} по параллелизму в алгоритмах и архитектурах, {SPAA} . дои : 10.1145/2312005.2312048 . S2CID 6586439 .

[16] «Приблизительные алгоритмы планирования распараллеливаемых задач | Материалы четвертого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам». дои : 10.1145/140901.141909 . S2CID 15607549 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[contiguousVSnoncontiguous-17] Блондек, Иво; Дроздовский, Мацей; Гинан, Фредерик; Шеплер, Ксавье (1 октября 2015 г.). «О планировании смежных и несмежных параллельных задач» . Журнал планирования . 18 (5): 487–495. дои : 10.1007/s10951-015-0427-z . ISSN 1099-1425 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

v т и оптимального планирования работы Проблемы
Одноэтапные работы	Одна машина Идентичные машины Униформные машины Несвязанные машины
Многоэтапные работы	Параллельные задачи Открыть магазин Поточный цех Магазин вакансий
Цели оптимизации	Макеспан Ранность Опоздание Опоздание Пропускная способность
Другие требования	Интервальное планирование Правдивое планирование работы