Автоматика и телемеханика, № 3, 2015
А втоматизированные информационно-управляющие системы, системы управления производством
© 2015 г. М.Г. ФУРУГЯН, канд. физ.-мат. наук (rtsccas@yandex.ru) (Вычислительный центр им. А.А. Дородницына РАН, Москва)
ПЛАНИРОВАНИЕ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ АСУ РЕАЛЬНОГО ВРЕМЕНИ С ДОПОЛНИТЕЛЬНЫМ РЕСУРСОМ
Рассмотрена задача составления допустимого расписания с прерываниями в многопроцессорной АСУ реального времени в случае, когда заданы директивные интервалы, процессоры могут иметь произвольные производительности, а длительности выполнения работ линейно зависят от количества выделенного им дополнительного ресурса. Разработаны алгоритмы, основанные на сведении исходной задачи к задаче о потоке минимальной стоимости и к задаче линейного программирования.
1. Введение
Одной из наиболее важных составных частей математического и программного обеспечения, используемого для разработки и функционирования сложных технических объектов, являются алгоритмы распределения ресурсов в многопроцессорных АСУ. Примерами являются системы жесткого реального времени, которые находят широкое применение при испытаниях самолетов, при разработке систем космической обороны, конвейерные и транспортные системы, системы экономического и экологического мониторинга и системы других областей человеческой деятельности. Системы жесткого реального времени - это такие системы, в которых задания должны быть выполнены в строго установленные директивные сроки, не подлежащие нарушению. Для функционирования таких систем необходимо иметь заранее составленное расписание их работы, которое показывает, какие ресурсы и когда выделяются каждому программному модулю. С ростом информационных потоков и появлением новой многопроцессорной вычислительной техники актуальность таких задач возрастает и появляются новые задачи.
В настоящей статье рассмотрена задача составления допустимого расписания с прерываниями в многопроцессорной АСУ в случае, когда заданы директивные интервалы, процессоры могут иметь произвольные производительности, а длительности выполнения работ линейно зависят от количества выделенного им дополнительного ресурса. Разработаны алгоритмы, основан-
ные на сведении исходной задачи к задаче о потоке минимальной стоимости и к задаче линейного программирования.
Подобная задача для случая, когда процессоры имеют одинаковые производительности и дополнительный ресурс отсутствует, рассматривалась в [1] и была сведена к задаче о максимальном потоке в сети специального вида. Задача с произвольными процессорами и произвольными директивными интервалами рассматривалась в [2], а задача с произвольными процессорами и одинаковыми директивными интервалами - в [3]. В [2, 3] дополнительный ресурс не рассматривался. Задача минимизации времени выполнения сетевого комплекса работ, когда длительности выполнения работ являются функциями от вектора распределения ресурсов, а число процессоров не ограничено, рассматривалась в [4] и была сведена к задаче нелинейного программирования. Задача с дополнительным ресурсом и идентичными процессорами рассмотрена в [5].
2. Постановка задачи
Рассматривается вычислительная система, состоящая из т процессоров Ь типов. Производительность процессоров ¿-го типа равна в], а их число составляет т] (¿' = 1, 2,... , Ь, ] т] = т). Имеется множество заданий (работ) N = {1, 2,...,п}. Предполагается, что в каждый момент времени каждый процессор может выполнять не более одного задания, а каждое задание выполняется не более чем одним процессором. При выполнении заданий допускаются прерывания и переключения с одного процессора на другой. Предполагается, что прерывания и переключения не сопряжены с временными затратами. Для задания г € N установлен директивный интервал (Ь^, /¿] (т.е. работа г может выполняться только в этом интервале). Помимо процессоров в системе имеется дополнительный ресурс невозобновляемого типа. Суммарное количество этого ресурса составляет К. Если заданию г выделено г единиц дополнительного ресурса, то объем работы процессоров по выполнению задания г составляет Qi = ( — aiг^ где
(1) (2)
П € [0, Г г ], г = 1, 2,..., п, < К,
гем
где ,Гг - заданные величины, аг > 0, ( > 0, 0 ^ Гг <(1г/аг. Таким
образом, Qi € [( — агГг, (г], причем ( — агГг > 0. За время т процессор ¿-го типа выполняет объем работы в]т. Если задание г, имеющее объем Qi, выполняется процессором ¿-го типа в течение интервала времени Т] = 1,2,..., Ь), то Qi = вjТ]. Требуется найти такое распределение ре-
сурсов (г0, г0,..., гП), при котором существует допустимое расписание (т.е. такое расписание, при котором каждая работа полностью выполняется в своем директивном интервале), или установить, что такого распределения ресурсов не существует. При этом распределение ресурсов (г0, г0,..., гП) должно удовлетворять ограничениям (1), (2). Кроме того, требуется найти минимальную
величину К дополнительного ресурса, при которой допустимое расписание существует.
Рассмотрим примеры подобных задач. В первом примере все процессоры идентичные. В этом случае обычно каждое задание г характеризуется не объемом, а длительностью ¿¿, которая зависит от величины энергопотребления гг для этого задания: ¿г = Л — аггг. Общий объем энергоресурсов для всех заданий ограничен величиной К. Во втором примере каждому заданию г выделяются дополнительные средства г^ на приобретение специализированных процессоров (которые могут быть использованы только для выполнения конкретного задания), что снижает объем работы основных процессоров по выполнению данного задания. В третьем примере, аналогичном второму, помимо основных станков (процессоров), имеется денежный фонд в размере К для приобретения дополнительных станков или найма рабочей силы для выполнения работы г, что снижает объем работы, выполняемой основными станками.
3. Задача с одинаковыми директивными интервалами
Предполагается, что директивные интервалы всех работ совпадают. Без ограничения общности можно считать, что Ьг = 0,/г = ^ (г € N). Как следует из [3], необходимым и достаточным условием существования допустимого расписания в этом случае является выполнение неравенства Егем Яг ^ тз, или Егем (Л — агп) ^ тз,
Егем аггг ^ Егем Л — ^ Е5=1 т5. Пусть £¿ем ^—^ Е*=1 т55 = В. Тогда задача заключается в поиске такого распределения ресурсов (п, г2,..., гп), которое удовлетворяет системе ограничений
^агГг ^ В,
гем
(3) £ Гг < К,
гем
гг € [0, гг], г = 1, 2,..., п.
Таким образом, допустимое расписание существует тогда и только тогда, когда задача линейного программирования (3) имеет решение. Если задача (3) имеет решение (г0, г0,..., гП), то, определив Я0 = Лг — агг0 (г € N) и применив алгоритм, описанный в [3], найдем допустимое расписание. Вычислительная сложность алгоритма Кармаркара решения задачи линейного программирования для случая, когда число ограничений не превосходит числа переменных п, составляет 0(п4'5 ^2(пТ)), где Т - максимальное значение числового параметра. В задаче (3) п переменных и п + 2 ограничений. Вводя две фиктивные переменные, получаем, что вычислительная сложность решения задачи (3) составляет 0(п4'5 ^2(пТ)), где Т - максимальное из чисел аг (г € N), В и К. Сложность алгоритма, описанного в [3], составляет О(п). Таким образом, описанный алгоритм является полиномиальным.
Определим минимальное количество Ктщ дополнительного ресурса, при котором допустимое расписание существует. Рассмотрим задачу линейного
программирования
R — min, J^airi > B,
ieN
(4) ^ ri ^ R,
ieN
ri G [0, r], i = 1, 2,... ,n, R > 0.
Если задача (4) разрешима, то каждому ее решению (r0, r0,... , r00) и Rmin соответствует допустимое расписание, а Rmin - минимально допустимое количество дополнительного ресурса.
4. Задача с произвольными директивными интервалами
Теперь предположим, что директивные интервалы (bi, f ] произвольные. Покажем, что в этом случае исходная задача может быть сведена к задаче о потоке минимальной стоимости. По аналогии с тем, как это сделано в [2], построим потоковую сеть G = (V, A) (см. рисунок) c источником s и стоком t (V - множество узлов сети, A - множество дуг).
Пусть y0 < y1 < ... < yp (p < 2n) - разные по величине значения bi, f (i G N). Определим интервалы Ik = (yk-i, yk] (k = 1, 2,... ,p). Сеть G пред-
ан
Потоковая сеть G.
Дуга L и С
(s, Wi) di Oj^TÍ di -1/Oj
(wi, Qkj) 0 (sj ~ Sj+i)Ak 0
(Qkj, Ik) 0 Ak Ег=1 (si ~ s'+i) 0
(h,t) 0 Afc Ej=i чтз 0
(t, s) 0 EieW di 0
ставляет трехдольный граф с дополнительными источником s и стоком t. Первый уровень графа состоит из вершин Wi (i € N), соответствующих заданиям (будем называть их вершинами "задания"). Второй уровень состоит из вершин qkj (k = 1, 2,... ,p; j = 1, 2,... ,t), которые соответствуют всем возможным комбинациям различных типов процессоров и интервалов (будем называть их вершинами "процессоры-интервалы"). Третий уровень состоит из вершин Ik (k = 1, 2,...,p), соответствующих интервалам (назовем их вершинами "интервалы"). Таким образом, множество вершин V = = |s,t,wbw2,...,wra ,qkj (k = 1, 2, . ..,p; j = 1, 2,...,t), Ii, I2,..., Ip}, где узел wi соответствует работе i € N, узел qkj (k = 1, 2,... ,p; j = 1, 2,..., t) -интервалу (yk-i,Vk] и процессору j-го типа, а узел Ik - интервалу (yk-i,Vk] (k = 1, 2,... ,p).
Источник соединен дугами со всеми вершинами "заданиями". Каждая вершина "задание" соединяется со всеми вершинами "процессоры-интервалы", которые отвечают за те интервалы, на которых это задание выполнимо. Каждая вершина "процессора-интервала" соединена дугой с соответствующей вершиной "интервал". Все вершины "интервалы" соединены дугами со стоком t. Кроме того, вводится возвратная дуга, направленная из стока в источник. Таким образом, множество A состоит из следующих дуг: (s, Wi) (i € N); (wi, qkj) (i € N; k = 1, 2,... ,p; j = 1, 2,..., t) в случае, если Ik С (bi, fi] (отметим, что для любых k (1 ^ k ^ p) и i € N интервал Ik либо не пересекается с интервалом (bi, fi], либо целиком лежит в нем); (qkj, Ik) (k = 1, 2,... ,p; j = = 1, 2,..., t); (Ik,t) (k = 1, 2,... ,p); (t, s). Пусть Ak = Vk - Vk-i - длина
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.