научная статья по теме ОПТИМАЛЬНАЯ КОРРЕКЦИЯ ДИРЕКТИВНЫХ ИНТЕРВАЛОВ В ЗАДАЧЕ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНОГО РАСПИСАНИЯ С ДОПОЛНИТЕЛЬНЫМ РЕСУРСОМ Кибернетика

Текст научной статьи на тему «ОПТИМАЛЬНАЯ КОРРЕКЦИЯ ДИРЕКТИВНЫХ ИНТЕРВАЛОВ В ЗАДАЧЕ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНОГО РАСПИСАНИЯ С ДОПОЛНИТЕЛЬНЫМ РЕСУРСОМ»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 2, с. 107-116

СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

УДК 519.86

ОПТИМАЛЬНАЯ КОРРЕКЦИЯ ДИРЕКТИВНЫХ ИНТЕРВАЛОВ В ЗАДАЧЕ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНОГО РАСПИСАНИЯ

С ДОПОЛНИТЕЛЬНЫМ РЕСУРСОМ

© 2015 г. М. Г. Фуругян

Москва, ВЦ РАН Поступила в редакцию 15.09.14 г., после доработки 25.10.14 г.

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

Б01: 10.7868/80002338815020055

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

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

Подобная задача составления допустимого расписания с прерываниями для случая, когда процессоры имеют одинаковые производительности, дополнительный ресурс отсутствует, рассматривалась в [1] и была сведена к задаче о максимальном потоке в сети специального вида. Задача с произвольными процессорами и произвольными директивными интервалами описана в [2], а задача с произвольными процессорами и одинаковыми директивными интервалами — в [3]. В обеих этих работах дополнительный ресурс не рассматривался. Задача минимизации времени выполнения сетевого комплекса работ, когда длительности выполнения работ являются функциями от вектора распределения ресурсов, а число процессоров не ограничено, исследована в [4] и была сведена к задаче нелинейного программирования. Задача построения допустимого расписания с дополнительным ресурсом и идентичными процессорами рассмотрена в [5], с произвольными процессорами — в [6], а задача оптимальной коррекции директивных интервалов в случае идентичных процессоров — в [7]. Некоторые методы построения расписаний без прерываний, основанные на имитационном моделировании, описаны в [8], а основанные на муравьи-

ных алгоритмах — в [9]. Кроме того, в некоторых случаях подобные задачи сводятся к минимаксным задачам, методы решения которых приведены в [10—23].

1. Постановка задачи. Рассматривается вычислительная система, состоящая из т процессоров ? типов. Производительность процессорову-го типа равна sj■, а их число составляет т,

(у = 1,?; т1 + ... + т( = т). Предполагается, что ^ > > ... > st. Имеется множество заданий (работ) N = {1, п}. В каждый момент времени каждый процессор может выполнять не более одного задания, а каждое задание выполняется не более чем одним процессором. При выполнении заданий допускаются прерывания и переключения с одного процессора на другой. Предполагается, что прерывания и переключения не сопряжены с временными затратами. Для задания , е N установлен директивный интервал (Ь¡,(т.е. работа , может выполняться только в этом интервале). Помимо процессоров в системе имеется дополнительный ресурс не возобновляемого типа. Суммарное количество этого ресурса составляет Я. Если заданию , выделено г, единиц дополнительного ресурса, то объем работы процессоров по выполнению задания I составляет = — а ¡г, где

Г е [0, Г ], I = й, (1.1)

X Г < Я, (1.2)

! е N

а¡, й, г — заданные величины, а,> 0, > 0, 0 < г < /а1. Таким образом, е [й, — а,Т-, й ], причем — аг > 0. За время т процессору-го типа выполняет объем работы sj■т. Если задание ¡, имеющее объем 0,, выполняется процессором у-го типа в течение интервала времени т,, у = 1,1, то

= 51т1 + ... + ^х(. Требуется найти такое распределение ресурсов (г10,г20,..., гп°), при котором существует допустимое расписание (т.е. такое расписание, при котором каждая работа полностью выполняется в своем директивном интервале), или установить, что такого распределения ресурсов не существует. При этом искомое распределение ресурсов должно удовлетворять ограничениям (1.1), (1.2). В случае, когда указанного распределения ресурсов не существует, требуется определить директивные интервалы (Ь¡, /], при которых допустимое распределение ресурсов существует и величина шах/ - / : I е N1 принимает минимальное значение.

Рассмотрим некоторые примеры подобных задач [6]. В первом примере все процессоры идентичные. В этом случае обычно каждое задание , характеризуется не объемом, а длительностью которая зависит от величины энергопотребления г, для этого задания: = й, — а,г,. Общий объем энергоресурсов для всех заданий ограничен величиной Я. Во втором примере каждому заданию I выделяются дополнительные средства г, на приобретение специализированных процессоров (которые могут быть использованы только для выполнения конкретного задания), что снижает объем работы основных процессоров по выполнению данного задания. В третьем примере, аналогичном второму, помимо основных станков (процессоров) имеется денежный фонд в размере Я для приобретения дополнительных станков или найма рабочей силы для выполнения работы , что снижает объем работы, выполняемой основными станками.

2. Задача с одинаковыми директивными интервалами. В этом разделе предполагается, что директивные интервалы всех работ совпадают. Без ограничения общности можно считать, что Ь, = 0,/, = ¥( , е Щ. Как следует из [3, 7], необходимым и достаточным условием существования допустимого расписания в этом случае является выполнение неравенства

X Qi ± Р X т,Ь

¡е N 1 - 1

или

X (^ - а г) ^ РX ,

1Е N 1 -1

Xа г > Xа '- Р X тл.

¡Е N ¡Е N 1 - 1

Пусть

X - ¥ X тзвз = В •

I е ^ 1 - 1

Тогда задача заключается в поиске такого распределения ресурсов (гь г2, ..., ги), которое удовлетворяет системе ограничений

X ar > B,

i е Ж

X Т < R, (2.1)

i е Ж

г, е [0, Т ], i = 1, n.

Таким образом, допустимое расписание существует тогда и только тогда, когда задача линейного программирования (2.1) имеет решение. Если задача (2.1) имеет решение (r/0,r20,..., rn0), то,

определив Q0 = d( - arf, i е Ж, и применив алгоритм, описанный в [3], найдем допустимое расписание. Вычислительная сложность алгоритма Кармаркара решения задачи линейного программирования для случая, когда число ограничений не превосходит числа переменных n, составляет O(n45 log2(nT)), где T — максимальное значение числового параметра. В задаче (2.1) имеются n переменных и n + 2 ограничения. Вводя две фиктивные переменные, получаем, что вычислительная сложность решения задачи (2.1) составляет O(n45 log2(nT1)), где T1 — максимальное из чисел а, i е N, B и R. Сложность алгоритма, описанного в [3], составляет O(n).

Определим минимальное количество Rmin дополнительного ресурса, при котором допустимое расписание существует. Рассмотрим задачу линейного программирования

R ^ min

(,..., rmR)

X an > B,

i e Ж

X n ^ R, (2.2)

i e Ж

r/ е [0, r ], i = 1, n,

R > 0.

Задача (2.2) имеет решение. Каждому ее решению (r10,r20,..., rn°), Rmin соответствует допустимое расписание, а Rmin — минимально допустимое количество дополнительного ресурса. Вычислительная сложность решения задачи (2.2) составляет O(n45 log2(n T2)), где T2 — максимальное из чисел а, d/a,, i е N, и B.

3. Минимизация общего директивного срока. Теперь будем предполагать, что количество ресурса R в системе фиксировано, а директивный срок может изменяться, за счет чего будет достигаться существование допустимого расписания. Как и в разд. 2, предполагается, что директивный интервал каждой работы совпадает с интервалом (0, F], а величина F минимизируется. В этом случае решается следующая задача линейного программирования:

F ^ min ,

(Т/,..., r„,F)

t

X airi+FX mJsJ - Xdi,

(3.1)

X r * R,

i e Ж

T e [0, r ], i e Ж.

"задания" "процессоры-интервалы" "интервалы"

Рис. 1. Потоковая сеть О

Задача (3.1) имеет решение. Каждому ее решению (г10, г20,..., гп°), соответствует допустимое расписание, а ¥т1п — минимально допустимый директивный срок при фиксированной величине ресурса Я в системе. Применив алгоритм упаковки [3], получим окончательное решение в виде допустимого расписания. Вычислительная сложность решения задачи (3.1) составляет

0(п451о§2(пТ3)), где Т3 — максимальное из чисел а,, / а¡, I е N, X , т и Я.

¡е N

4. Сведение исходной задачи к задаче о потоке минимальной стоимости. 4.1. Произвольные директивные интервалы. В общем случае, когда директивные интервалы произвольные, по аналогии с тем, как это сделано в [2, 6], построи

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

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