научная статья по теме К ГИПОТЕЗЕ СИТТЕРСА-ФИШКИНА Автоматика. Вычислительная техника

Текст научной статьи на тему «К ГИПОТЕЗЕ СИТТЕРСА-ФИШКИНА»

Автоматика и телемеханика, № 7, 2015

Системный анализ и исследование

операций

© 2015 г. А.С. КОЗЛОВ (cldmen@yandex.ru) (Институт математики им. С.Л. Соболева СО РАН, Новосибирск)

К ГИПОТЕЗЕ СИТТЕРСА-ФИШКИНА

Рассматривается вопрос о минимальном числе миграций в оптимальном расписании задачи Pm | pmtn(delay = d) | Cmax на параллельных машинах с разрешенными прерываниями и константной задержкой при миграциях работ. В частности, рассматривается гипотеза Ситтерса-Фишкина о том, что для любого примера задачи существует оптимальное расписание с не более чем m — 1 миграциями, где m — число машин. Гипотеза была подтверждена в [1] для случая m ^ 3. В данной работе получено подтверждение гипотезы в случае четырех машин.

1. Введение

Задачи на моделях с параллельными машинами очень популярны в теории расписаний. Суть таких моделей в том, что каждая работа может выполняться на любой машине. Настоящая статья посвящена задаче Pm | pmtn(delay = = d) | Cmax. Для заданного набора работ J1,... ,Jn c целочисленными длинами pi,... ,pn требуется составить расписание наименьшей длины на m идентичных параллельных машинах. Поскольку разрешены прерывания работ, то выполнение каждой работы может быть разбито на конечное число фрагментов (необязательно целочисленных), причем каждый такой фрагмент может выполняться на любой из машин. При этом требуется, чтобы никакие два фрагмента на одной машине (как и никакие два фрагмента одной работы) не выполнялись одновременно. Если выполнение работы переносится с одной машины на другую (работа мигрирует), то до момента возобновления этой работы должно пройти не менее d единиц времени. Можем считать, что d — время, затрачиваемое на транспортировку.

Эта задача возникает, например, в ситуации с несколькими параллельными процессорами. Допустим, нужно выполнить n различных вычислительных задач на m параллельных процессорах. Чтобы перенести выполнение задачи с одного процессора на другой, нужно перенести данные, полученные в результате работы первого процессора, на второй процессор, а это требует d единиц времени. Значит, выполнение задачи может быть возобновлено на втором процессоре только через d единиц времени после прекращения ее выполнения на первом процессоре.

Известные результаты.

Задача P | pmtn(delay = d) | Cmax (отличающаяся от Pm | pmtn(delay = = d) | Cmax тем, что в последней число машин m не является частью входа) рассматривалась в [1], где была показана ее NP-трудность в сильном

смысле. В той же статье было доказано, что для любого примера данной задачи существует оптимальное расписание, в котором каждая машина работает без простоев вплоть до момента окончания своей работы. Кроме того, была сформулирована следующая

Гипотеза 1. Для любого примера задачи Рт |ртШ((е1ау = () | Стах существует оптимальное расписание с не более чем т — 1 миграциями.

Эта гипотеза в той же статье была доказана для т = 2 и т = 3. Приведены примеры с произвольным числом машин, показывающие неулучшаемость (достижимость) данной оценки на минимальное число миграций. Иными словами, доказано неравенство f (т) ^ т — 1, где функция f (т) определяется равенством f (т) = 8ир/е1т М1дтаИопз(1), 1т обозначает подмножество т-машинных примеров, а МгдтаЬгопв(1) задает минимальное число миграций в оптимальном расписании для примера I. Гипотеза предполагает, что указанное неравенство должно выполняться как равенство: f (т) = т — 1. В данной работе эта гипотеза доказана для случая четырех машин.

2. Предварительные понятия и обозначения

Базовой компонентой всякого оптимального/допустимого 'расписания выполнения работ на машинах является распределение работ по машинам. Дадим определение этого понятия в терминах распределения работ по "контейнерам".

Определение 1. Пусть имеется т контейнеров К\,..., Кт, где контейнер Кг характеризуется вместимостью Уг. Имеется N работ ... ; работа Jj имеет заданный объем pj. Распределением работ по контейнерам называется объект, задаваемый двумя компонентами: (а) разбиением каждой работы на не более чем т частей (которые будем называть "кусками"; к-й кусок работы Jj задается своим объемом рк), и (в) назначением полученных кусков работ контейнерам. При этом разбиение работ и назначение кусков контейнерам должны удовлетворять следующим требованиям:

(a) суммарный объем кусков каждой работы должен быть равен ее объему;

(b) разные куски каждой работы назначаются на разные контейнеры;

(c) суммарный объем кусков, назначенных контейнеру, не должен превышать его вместимости.

Определение 2. Распределение работ Р будем называть последовательным, если оно строится следующим трехшаговым алгоритмом.

Шаг 1. Упорядочиваем контейнеры согласно заданной перестановке п = = (К%1 ,-..,Кгт).

Шаг 2. Задаем последовательность работ а = (Jj1,..., JjN) и ее разбивку на две части: левую (ае = (Jjl,..., JjN,)) и правую (аг = ,..., JjN)).

Шаг 3. Последовательно заполняем контейнеры в порядке п работами из левой части по следующему правилу: берем очередную назначаемую работу (Jjx) и самый левый из еще не заполненных контейнеров (т.е. контейнер Кгу, имеющий положительную остаточную вместимость V'[ > 0). Если pjx ^ V'[, то работа состоит из единственного куска, назначаемого на данный контейнер. Уменьшаем VI на величину pjx и берем следующую работу из заданной

последовательности. Если же pjx > У^, то назначаем на данный контейнер кусок текущей работы объемом у^. Остаточный объем работы Jjx уменьшается на у^, а для заполнения берем следующий контейнер из п, куда продолжаем распределять работу Jjx.

Аналогично заполняем контейнеры с другого конца последовательности п работами правой части, просматриваемой в обратном порядке: JjN, JjN_1,....

В случае, когда последовательность работ не разбивается на две части (т.е. состоит только из "левой" части), распределение работ будем называть односторонним.

3. Доказательство гипотезы в случае трех машин

Так как основой для доказательства гипотезы в случае четырех машин является представленное в [1] доказательство этой гипотезы для случая трех машин, то имеет смысл подробно ознакомиться с последним.

Теорема 1 [1, с. 95]. Для любого примера задачи P3 | pmtn(delay = = d) | Cmax существует оптимальное расписание с не более чем двумя миграциями.

Доказательство. Общая идея доказательства (используемая далее и в доказательстве теоремы 2) состоит в перестройке произвольно выбранного оптимального расписания S для m машин в «нужное» оптимальное расписание S' с не более чем m — 1 миграциями. Перестройка осуществляется трехшаговым алгоритмом. На первых двух шагах распределяем работы по машинам, а на третьем шаге на основе полученного распределения строим расписание S'.

Шаг 1. Берем произвольное оптимальное расписание S длины OPT и находим в нем распределение работ по машинам. В расписании S есть работы, которые мигрируют (назовем их мигрирующими), и те, которые не мигрируют (назовем их немигрирующими). Немигрирующие работы в итоговом расписании S' будут выполняться на тех же машинах (рис. 1). Вычисляем нагрузку Li каждой машины Mi немигрирующими работами и определяем для нее контейнер Ki вместимостью V = OPT — Li. (Контейнеры будут предназначены для распределения в них мигрирующих работ.) Нумеруем контейнеры (и соответствующие им машины) по невозрастанию их вместимостей:

Vl > V2 2 ••• 2 Vm.

2 1 3

Рис. 1. Распределение немигрирующих работ по машинам.

Шаг 2. Заново распределяем мигрирующие работы по контейнерам, для чего сначала нумеруем все мигрирующие работы по невозрастанию их длительностей: рх ^ • • • ^ р^, где N — число мигрирующих работ. Находим одностороннее распределение Р последовательности J\ ^... ^ JN мигрирующих работ по контейнерам, поставленным в порядке п: К2 ,К\ ,Кз (как показано на рис. 2).

2 1 3

Рис. 2. Последовательное распределение мигрирующих работ по трем машинам.

Шаг 3. По распределению P строим "почти допустимое" расписание S(P) длины OPT для исходного примера.

Для каждой работы Ji, имеющей в P ^ 1 миграций, вычисляем максимально возможное время ее задержки: di = (OPT — pi)/^i. Выполняем куски работы Ji (в объемах, найденных в P) на тех машинах, в чьи контейнеры они были распределены в P, согласно последовательности п. При этом интервалы времени выполнения ее кусков последовательно отделяем друг от друга на величину задержки di. (Как нетрудно видеть, первый кусок каждой мигрирующей в P работы в этом расписании стартует в момент 0, а последний заканчивается в момент OPT.)

Все остальное рабочее пространство на машинах в интервале [0, OPT] свободно заполняем остальными работами (не обращая внимания на возникающие при этом прерывания), но с соблюдением их установленного распределения по машинам: для немигрирующих работ — согласно их распределению в расписании S, а для мигрирующих в S, но не мигрирующих в P — согласно их распределению в P.

Замечание 1. Построенное расписание S(P) обладает следующими свойствами. Его длина равна OPT (по построению) и оно задает не более m — 1 миграций, порождаемых распределением P. Его "почти допустимость" означает, что в нем выполнены почти все ограничения на допустимое расписание, кроме, быть может, ограничения на миграционную задержку (которая может нарушаться для какой-то из мигрирующих в P работ). При этом если мигрирующая в P работа Ji имеет не более одной миграции, то соблюдение ею ограничения на миграционную задержку вытекает из неравенства di = = OPT — pi ^ d, выполняющегося для любой мигрирующей в S работы. Таким образом, если в распределении P никакая работа не имеет более одной миграции, то расписание S(P) полностью допустимо.

Задача последующего доказательства — убедиться, что расписание Б(Р), построенное для случая трех машин, полностью допустимо.

Из приведенного выше замечания следует, что достаточно рассмотреть случай, когда в распределении Р имеется работа ^), делящаяся на три части (т.е. щг = 2). Ясно, что такая работа единственна. Более того, в Р имеется лишь одна мигрирующая работа. Поскольку она полностью заполняет контейнер К\ (стоящий вторым), ее длина удовлетворяет неравенству рг >У\, откуда следуе

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком