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

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

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 2, с. 50-56

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

УДК 519.86

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

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

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

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

БО1: 10.7868/80002338814020085

Введение. Одна из основных задач, возникающих при разработке программного обеспечения многопроцессорных вычислительных систем, в частности систем реального времени, заключается, во-первых, в создании математической модели, адекватной реальной вычислительной системе, и, во-вторых, в расчете с помощью этой модели режима функционирования системы, в результате которого получается расписание, показывающее, когда и какой программе должны быть выделены те или иные ресурсы ЭВМ.

Большинство задач планирования вычислений в многопроцессорных системах являются МР-трудными, и все известные точные алгоритмы их решения имеют переборный характер, а точных полиномиальных (эффективных) алгоритмов в настоящее время не известно. Число шагов переборного метода, как правило, растет экспоненциально в зависимости от размеров задачи. Поэтому при решении переборных задач больших размеров возникает необходимость в разработке приближенных методов. Для некоторых задач планирования вычислений в многопроцессорных системах удается построить эффективные (существенно менее трудоемкие, чем полный перебор вариантов) методы решения. Например, это удается сделать для задачи составления расписания с прерываниями без ограничений на частичный порядок выполнения работ. Однако число таких задач невелико.

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

1. Постановка задачи. Рассматривается вычислительная система, состоящая из т процессоров, и множество работ N = {1,п}, подлежащее выполнению. Время выполнения работы I на процессоре ]равно I = 1,п;] = 1,т. При выполнении работ не допускаются прерывания и переключения с одного процессора на другой. В фиксированный момент времени каждая работа может выполняться не более чем одним процессором, а каждый процессор может выполнять не более одной работы.

Под расписанием выполнения работ будем понимать разбиение множества N на т непересекающихся подмножеств

( т \

N1, N2, ..., N

N = и N; П N2 = 0 при а *у2

1=1 у

Работа 1

Г

Работа 2

Уровень 0

Процессор 1

Уровень 1

роцессор m

Работа n

Уровень n - 1

Процессор 1 ... процессор m.. .Процессор 1 ... \Процессор m ' ^ ' ^ Уровень n

Дерево расписаний

Работы из множества Щ приписываются процессору у и выполняются на нем одна за другой в произвольном порядке. Величина Q¡ = V — загруженность процессора у, у = 1, т, а тах} — это

длина расписания. Задача заключается в построении оптимального по быстродействию расписания, т.е. расписания минимальной длины.

Подобные задачи широко освещены в литературе. Отметим, например, такие методы, применяемые при их решении, как случайный и исчерпывающий поиск [1], методы математического программирования [2], метод ветвей и границ [3], муравьиные алгоритмы [4], поиск с запретами [5], вероятностные алгоритмы [6], генетические алгоритмы [7], мультиоценочный метод с калибровкой [8], различные эвристические алгоритмы [9, 10], алгоритмы агрегирования [10], а также методы решения минимаксных задач, изложенные в [11—14].

2. Метод ветвей и границ. Для решения поставленной задачи предлагается метод ветвей и границ, основанный на результатах работы [3].

2.1. Ветвление. Множество всех расписаний (их число равно mn) будем описывать в виде дерева расписаний, изображенного на рисунке. На нулевом уровне дерева находится корень, соответствующий множеству всех расписаний. На первом уровне располагается m вершин, при этом каждая соответствует множеству всех расписаний, в которых первая работа назначена на определенный процессор. На втором уровне дерева имеется m2 вершин. Каждая из них соответствует множеству всех расписаний, назначающих первые две работы на один или два определенных процессора. На n-м уровне дерева расписаний находится mn листьев, каждый из которых соответствует некоторому расписанию выполнения множества работ N.

Пусть xk — некоторый узел уровня k дерева расписаний, R(xk) — множество всех расписаний,

соответствующих этому узлу (т.е. множество расписаний, в которых работы 1, к назначены на

определенные процессоры), xJk+1 — узел уровня к + 1, к < n, связанный с узлом xk ребром, соответствующим процессору j. Наша цель — вычисление нижней и верхней оценок минимальной длины расписания на множестве R(xk). Имея эти оценки, можно применить стандартную схему метода ветвей и границ [15] (например, одностороннего или фронтального ветвления).

2.2. Нижняя оценка. Пусть Tjk, j = 1, m, — загруженность процессора j после назначения

первых k работ (т.е. Tjk — суммарная длительность работ из числа 1, к, назначенных на процессор j). Нижнюю оценку L(xk) минимальной длины расписания на множестве R(xk) будем вычислять следующим образом: L(xk) = max(L1(xk), L2(xk), L3(xk)), где L1(xk), L2(xk), L3(xk) — это нижние оценки, полученные следующими тремя различными способами.

Величина L1(xk) рассчитывается как следующий максимум: L1(xk) = max j^ Tjk. Если величины T1k, T2k, ..., Tmkхранить в виде обычного массива, то сложность вычисления L1(xk) составляет 0(m). (Здесь используется асимптотическое обозначение f(n) = 0(g(n)), которое означает, что

f(n) = O(g(n)) и g(n) = O(f(n)) [16].) Будем хранить эти величины в виде двоичной кучи (пирамиды) с максимальным элементом в корне [16]. Корню x0 дерева расписаний соответствуют величины T10 = 0, T20= 0, ..., Tm0 = 0 и L1(x0) = 0. Тогда сложность получения максимального элемента составит 0(1). Если работа к + 1 будет назначена на процессор j (т.е. если от узла xkв дереве расписаний перейти к узлу xJk+1), то будет получен новый массив T1k+1, ..., Tj_1,к + 1, T,k +1 + tk + 1 ■, Tj +1, к + 1, • •, Tm>k + 1. Для преобразования этого массива в кучу следует поднять элемент Tj>k +1 + + tk+ 1j до нужного уровня в куче. Сложность такой процедуры составляет O(log2m) [16]. В полученной куче в корне по-прежнему будет находиться максимальный элемент. Таким образом, зная L1(xk), можно вычислить L1(xJk+1) за время O(log2 m).

Величина L2(xk) рассчитывается как следующий максимин:

Lj^xk) = max min(T,k + tj).

i=k+1, n j=1, m

Если при этом используется обычный двумерный массив A с элементами aij = Tjk + tij, i =

= k + 1, n; j = 1, m, то сложность вычисления величины L2(xk) составляет O(mn). Будем хранить каждую строку массива A в виде двоичной кучи с минимальным элементом в корне. Для корня x0

дерева расписаний aij = tij, i = 1, n; j = 1, m. Тогда сложность вычисления величины L2(xk) составит O(n). Если работа к + 1 будет назначена на процессор j (т.е. если от узла xk в дереве расписаний

перейти к узлу xj+1), то из массива A следует исключить (к + 1)-ю строку, а в каждой оставшейся строке i увеличить элемент йц на величину tk+1,j. Для того, чтобы каждая строка массива A по-прежнему образовывала кучу, следует опустить элемент a^ + tk+1,j до нужного уровня [16]. Сложность такой процедуры составляет O(nlog2 m). Каждая строка массива A по-прежнему будет образовывать кучу с минимальным элементом в корне. Таким образом, зная L2(xk), можно вычислить

L2(xk+1) за время O(n log2m).

Величина L3(xk) находится по формуле

Щхк ) = -

m

f m n

Z Tk + Z min ^

^ j = 1 i = к+1 j=!•m

Величину min ttj определим сразу для всех i = 1, n до начала поиска нижних оценок. Тогда сложность вычисления величины L3(xk) составляет O(n + m). Перейдем в дереве расписаний от узла xkк узлу xk+1, k < n (т.е. будем считать, что работа k + 1 назначена на процессор у0). Тогда

m n

L (xk+1 ) = 1 Z Tjk + rk+1, j0 + Z min ty

y ' m „ j=1, m

k+U - mln h+u

V ] = 1

Таким образом,

Ц (х&1 ) = Ц(хк) +1 (1к

т V "" ] = 1, т

и с помощью данного рекуррентного соотношения, используя Ь3(хк), величина Ц3 (хк°+1) определяется за время 0(1).

2.3. Верхняя оценка. В качестве верхней оценки Н(хк) минимальной длины расписания на множестве Я(хк) возьмем длину расписания, в котором работы 1, к приписаны процессорам в соответствии с вершиной хк дерева расписаний, а работы к + 1, п — по следующему "жадному" алгоритму. Пусть уже определены работы 1, р (к < р < п), Тр — загруженность процессора у, у = 1, т, и тт(71 р + ¿р+1д,..., Ттр + = + ¿р+1,к. Тогда работар + 1 назначается на процессору0. Указанная процедура повторяется дляр = к, п -1. Сложность процедуры вычисления величины Н(хк)

составляет О(тп). В случае, когда процессоры идентичные (т.е. = при всех 1 < у2 < т), работа р + 1 приписывается процессоруу0, определяемому соотношением шт(Т1р,Т2р,..., Ттр) = Т]р.

В этом случае величины Т1р, Т2р, Ттрможно хранить в виде двоичной кучи с минимальным элементом в корне. Корню х0 дерева расписаний соответствуют величины Т10 = 0, Т20 = 0,., Тт0 = 0. Тогда при переходе от узла хк к узл

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

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