В. А. Костенко мгу им. М. В. Ломоносова Россия, 119899, Москва, гсп-3, Воробьевы горы, мгу, ф-т вмиК icon

В. А. Костенко мгу им. М. В. Ломоносова Россия, 119899, Москва, гсп-3, Воробьевы горы, мгу, ф-т вмиК



Смотрите также:
В. А. Костенко 119899, Москва, гсп-3, Воробьевы горы, мгу, 2-й учебный корпус, ф-т вмиК, тел...
Монархическое движение в россии: 1905-1917 гг. (На материалах уфимской губернии)...
С. А. Остроумов Биологический факультет мгу им. М. В. Ломоносова, кафедра гидробиологии, Москва...
Программа учебного курса Инженерная геология, часть 2...
П. М. Михеев Московский государственный университет им. М. В. Ломоносова...
Роль информационно-коммуникационных технологий в развитии международного бизнеса...
Управленческая отчетность коммерческого банка...
Xvi международные рождественские образовательные чтения...
Славяне и финны на северо-западе древнерусского государства...
Эволюция функциональных принципов гражданского процесса...
Чехов и проблема идеала (Смена этико-эстетической парадигмы на рубеже XIX xx веков)...
Методология западного религиоведения второй половины XIX xx веков...



скачать
УДК 519.852.6


ПОСТРОЕНИЕ РАСПИСАНИЙ ПРИ СОВМЕСТНОМ ПРОЕКТИРОВАНИИ АППАРАТНЫХ И ПРОГРАММНЫХ СРЕДСТВ ВС РЕАЛЬНОГО ВРЕМЕНИ.



В.А. Костенко

МГУ им. М.В. Ломоносова

Россия, 119899, Москва, ГСП-3, Воробьевы горы, МГУ, ф-т ВМиК

e-mail: kost@cs.msu.su


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

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


CONSTRUCTION OF SCHEDULES IN JOINT HARDWARE AND SOFTWARE DESIGN OF REAL-TIME COMPUTER SYSTEMS

V.A Kostenko, CS dept., MSU, Vorobyovy gory, GSP-3, Moscow, 119899, Russia, e-mail: kost@cs.msu.su

Abstract. Different approaches to construction of scheduling algorithms in joint hardware and software design are investigated in the paper. For the purpose of construction of iterational scheduling algorithms, explicit and parametric schedule representation methods and schedule correction operations are considered. As explicit, as parametric schedule representation methods allow the construction of iterational algorithms which provide for transition from any correct schedule to the optimal one in O(number of jobs to schedule) iterations.

^ Key words: computer systems, schedule construction, optimization methods, combinatorial optimization.


1.Введение



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

Основной особенностью задачи построения расписания при совместном проектировании аппаратных и программных средств вычислительных систем (ВС) является то, что расписание строится одновременно с синтезом архитектуры. При выборе методов построения расписания при совместном проектировании аппаратных и программных средств кроме точности и вычислительной сложности методов, следует основное внимание уделять:

  • универсальности методов в классе допустимых архитектур ВС, которые могут быть получены в результате синтеза;

  • совместимости методов построения расписания и методов выбора оптимальных параметров архитектуры ВС;

  • возможностям методов строить расписания для архитектур ВС с различным уровнем детализации.

В работах [1,2] показано, что почти все задачи построения расписаний являются NP-полными. В данной работе на вариантах постановки задач построения расписаний, для которых существуют полиномиальные алгоритмы, останавливаться не будем. Отметим, что большинство таких задач являются практически вырожденными, поскольку на исходные условия накладываются жесткие ограничения: тип исходного отношения частичного порядка на множестве процессов – лес или пустое множество, число процессоров менее трех, одинаковая вычислительная сложность процессов, дополнительные ресурсы не допустимы, допустимость прерывания выполнения любого процесса и возобновление его выполнения на любом из процессоров ВС. Данным ограничениям большинство реальных ВС и программ не удовлетворяют.

NP-полнота задач построения расписаний обусловила широкое применение для их решения эвристических алгоритмов, основанных на жадных стратегиях, и итерационных алгоритмов: генетические и эволюционные алгоритмы, алгоритмы имитации отжига, алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением), алгоритмы детерминированной коррекции расписания. В работе расматривается проблемы построения алгоритмов и их эффективность для решения задачи построения расписания при совместном проектировании аппаратных и программных средств ВС.

^

2.Инвариант поведения программы, расписание



Инвариант поведения программы

Следуя [3], обозначим поведение программы Bh(PR) и определим Bh(PR) следующим образом: Bh(PR)=(PR)},{R(PR)}>, где S – множество всех возможных шагов процессов в допустимом диапазоне входных данных программы, {R(PR)} - отношения, определяющие частичный порядок на множестве шагов каждого процесса, {R(PR)} - отношения взаимодействия между процессами.

Шаги процесса определяются последовательностью взаимодействий с другими процессами [3]. Назовем рабочим интервалом процесса внутренние действия процесса между двумя последовательными взаимодействиями с другими процессами. Каждый рабочий интервал процесса по существу является реализацией соответствующего шага процесса.

Для задачи синтеза архитектур будем использовать одну историю поведения программы H(PR)Bh(PR) [3]. Для H(PR) отношение {R (PR)} является отношением полного порядка, а множество S сужается до множества шагов, которые делают процессы для конкретного набора входных данных. Bh(PR) может быть сведено к H(PR): для программ поведение которых не зависит от исходных данных; программ в которых любой процесс имеет не более одного рабочего интервала; или использована наиболее “сложная” история или искусственно построенная история на основе Bh(PR).

H(PR) можно представить ациклическим ориентированным размеченным графом. Вершинам соответствуют рабочие интервалы процессов, дугам ={ik=(pi,pk)}(i,k)Î(1...N) - связи, определяющие взаимодействия между рабочими интервалами из множества P (определяются объединением отношений {R(PR)}, {R(PR)}). Где Ni - число рабочих интервалов в i-ом процессе, K - число процессов в программе PR, N=N1+N2+…+NK - мощность множества P. Чередование рабочих интервалов различных процессов, назначенных на один и тот же процессор, допустимо, если не нарушается частичный порядок, заданный . Отношение ik представляется следующим образом: если , то рабочий интервал pi, необходимо выполнить до начала выполнения рабочего интервала pk. На накладываются условия ацикличности и транзитивности. Каждая вершина имеет свой уникальный номер и метки: принадлежности рабочего интервала к процессу и вычислительной сложности рабочего интервала. Вычислительная сложность рабочего интервала позволяет оценить время выполнения рабочего интервала на процессоре. Дуга определяется номерами смежных вершин и имеет метку, соответствующую объему данных обмена. Объем данных обмена для каждой связи из позволяет оценить затраты времени на выполнение внешнего взаимодействия.

При сделанных выше допущениях используемый инвариант поведения программы будет частным случаем (одна история) инварианта поведения программы, определенном в [4]. Используемый инвариант поведения определим:

1. Множеством рабочих интервалов процессов, составляющих программу:



Нумерация рабочих интервалов является сквозной и удовлетворяет условиям полной топологической сортировки. Каждый рабочий интервал имеет метку принадлежности к процессу.

2. Частичным порядком на P: ={ik=(pi,pk)}(i,k)(1...N);

3. Вычислительной сложностью рабочих интервалов: ;

4. Объемом данных обмена для каждой связи из : {vik}(i,k)(1...N);.


Расписание

Расписание является комбинаторной структурой - заданы два множества: рабочих интервалов и процессоров:

  • между множествами рабочих интервалов и процессоров определено отношение привязки – определяет распределение рабочих интервалов по процессорам (данное отношение является всюду определенной функцией на множестве рабочих интервалов), в дальнейшем привязка;

  • на множестве рабочих интервалов определено отношение частичного порядка, в дальнейшем порядок.

Различные варианты расписания могут быть получены изменением этих отношений в заданных ограничениями пределах.

Модель расписания выполнения программы определим набором простых цепей и отношением частичного порядка HP на множестве P: HP=({SPi}i=(1...M),HP). Где {SPi}i=(1...M) -набор простых цепей (ветвей параллельной программы). Они образуются рабочими интервалами процессов, распределенными на один и тот же процессор (M – число процессоров в ВС). Отношение частичного порядка HP на множестве P для HP определим как объединение отношений: HP=c1M, i - отношение полного порядка на SPi, которое определяется порядковыми номерами рабочих интервалов в SPi; c - набор секущих ребер, которые определяются связями рабочих интервалов, распределенных на разные процессоры. Если рабочие интервалы pi и pj распределены на разные процессоры и в существует связь ij, то она определяет секущее ребро в HP. На HP накладываются условия ацикличности и транзитивности.

Модель расписания можно рассматривать как граф HP, вершины которого имеют дополнительную метку “номер списка”, а дуги определяются отношением HP или как граф H, вершины которого доразмечены двойками: {“номер списка”, “порядковый номер вершины в соответствующем списке”}. В модели HP сохраняются нумерация вершин, дуг и их метки заданные в модели поведения программы H.

Таким образом, расписание выполнения программы определено, если для каждого рабочего интервала из множества P заданы: 1)привязка к одному из списков SPi, i(1...M); 2)порядковый номер в соответствующем списке.

Выделим два способа представления расписания:

  • непосредственное представление - для каждого рабочего интервала значения привязки и порядкового номера заданы явно;

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

В дальнейшем при рассмотрении свойств расписаний в некоторых разделах будет использоваться ярусная форма представления расписания. Любое допустимое расписание HP в силу ограничения “отношение HP ациклично“ представляет собой ациклический ориентированный граф. Любой ациклический ориентированный граф всегда может быть представлен в ярусной форме [5]: на одном ярусе могут находиться лишь вершины не связанные транзитивным отношением частичного порядка; предшественники всегда находятся на более высоком ярусе (с меньшим номером), чем последователи. Верно также и обратное, если ориентированный граф представлен в ярусной форме, то он является ациклическим. Ярусная форма называется канонической, если вершины распределены по ярусам таким образом, что для любой вершины на предшествующем ярусе имеется непосредственный предшественник. Ярусной формой максимальной высоты будем называть такую ярусную форму, у которой на каждом ярусе находится не более одной вершины.


^ Ограничения на расписание

Расписание HP является допустимым, если выполнены следующие ограничения:

1. Каждый рабочий интервал должен быть назначен на процессор (в SPi):

.

2. Каждый рабочий интервал должен быть назначен лишь на один процессор (в один SPi):

.

3. Частичный порядок, заданный в H должен быть сохранен в HP: .

4. Расписание HP должно быть беступиковым. Условием беступиковости является отсутствие контуров в графе HP:

.

5. Все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор (в один и тот же SPi):



Ограничения 1-4 являются обязательными для любого варианта постановки задачи. Они обеспечивают сохранение инварианта поведения программы, определяемого H, и интерпретируемость расписания. Ограничение 5 запрещает возобновление работы процесса после прерывания на другом процессоре, что соответствует способу организации параллельных вычислений в большинстве ВС. В дальнейшем будем говорить, что расписание допустимо , если оно удовлетворяет ограничениям. Нижний индекс в указывает ограничения налагаемые на расписание.

^

3.Задача построения расписаний



В задачах совместного проектирования аппаратных и программных средств ВС при построении расписания обычно минимизируется время его выполнения T при заданных ограничениях на аппаратные ресурсы (ВС мягкого реального времени) или время выполнения ограничивается TTdir при условии использования необходимого минимума аппаратных ресурсов (ВС жесткого реального времени). В качестве меры эффективности расписания могут быть использованы и другие критерии [1]: среднее взвешенное время завершения, время ожидания обслуживания, среднее количество процессов, выполненное на заданном временном интервале.

В дальнейшем для определенности будем рассматривать время выполнения расписания: T=f(HP,HW), где HP– модель расписания, HW- модель архитектуры ВС. Оценка значения T для конкретных вариантов решения задачи может быть получена совместной интерпретацией моделей HP и HW. Функция T=f(HP,HW) задана алгоритмически [6]: правилами/алгоритмами ее вычисления, т.е. ее аналитическая структура не может быть использована для организации поиска оптимального решения.

Выбор наиболее подходящего метода решения как правило определяется сложностью функции T=f(HP,HW). Сложность функции T=f(HP,HW) будем характеризовать:

  • размером моделей HP,HW:

  1. HP: число рабочих интервалов (N), число процессов (K), мощность исходного отношения порядка (),

  2. HW: число процессоров (M), число разделяемых ресурсов (MEAS), число уровней памяти (MMEM), число вызываемых системных процессов (MSYS);

  • cтруктурой модели H:

  1. тип ,

  2. дисперсия ;

  • учетом возможных временных задержек:

  1. tEP, tD,

  2. tEP, tD, tEAS,

  3. tEP, tD, tEAS, tSYS,

где временные задержки, обусловленные: tEP- занятостью процессоров, tD- ожиданием завершения предшественников, tEAS- ожиданием получения доступа к разделяемым ресурсам и tSYS- задержки вносимые логической средой и доступом к памяти, которые не могут быть учтены статически;

  • законом распределения значений T: i=(Ti). Значение функции (Ti) равно относительному числу вариантов расписания для которых значение функции T=f(HP,HW) равно Ti.


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

1)абстрактный,

2)системный,

3)уровень регистровых передач.

Учет возможных временных задержек определяет точность вычисления значений функции T=f(HP,HW) для различных классов архитектур и уровней их рассмотрения. Например, для полносвязной архитектуры достаточно учитывать лишь задержки tEP, tD, а для архитектур с коммутационной средой, в которой возможно ожидание получения канала связи, учет лишь tEP, tD будет приводить к неточным оценкам значения ^ T.

Возможный широкий спектр характеристик сложности функции T=f(HP,HW) обуславливает широкий спектр используемых алгоритмов.

^

4. Жадные алгоритмы



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

1. Подзадача заключается в распределении i-го рабочего интервала в расписание, содержащее (i-1) рабочий интервал. Для решения задачи полного составления расписания HP требуется решить N таких подзадач, где N - число рабочих интервалов в программе. В каждой подзадаче число возможных вариантов ее решения равно M0, где M0 - число возможных мест размещения i-го рабочего интервала.

2. Строится максимально параллельное расписание - время инициализации каждого рабочего интервала определяется готовностью его к выполнению (выполнены все предшественники). Подзадача заключается в ликвидации одного процессора и распределении его процессов по оставшимся процессорам. Для решения задачи полного построения расписания HP требуется решить M-M таких подзадач, где M - число процессоров в ВС для которой строится расписание, M - число процессоров для максимально параллельного расписания. Каждая подзадача заключается в решении NS- следующих подзадач: распределение рабочего интервала, принадлежащего ликвидируемому процессору, в один из оставшихся процессоров, где NS- – число рабочих интервалов в ликвидируемом процессоре. Всегда справедливо NS-. Число возможных вариантов решения подзадачи распределения рабочего интервала всегда меньше N.

То есть, при данных способах разбиения задачи составления расписаний на подзадачи, оптимальное решение каждой подзадачи может быть получено за полиномиальное число шагов, например, полным перебором возможных вариантов решения. Число подзадач также полиномиально. Жадные алгоритмы, использующие второй способ разбиения задачи, могут иметь более высокую вычислительную сложность, по сравнению с алгоритмами, использующими первый способ (верхняя оценка сложности алгоритмов соответственно равна O(N2) и O(N3-N2M)), но они применимы и в случае, когда процесс может иметь более одного рабочего интервала и на расписание наложено ограничение “все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор”.

Жадные алгоритмы предполагают выбор для подзадач локальных целевых функций, которые не имеют глобального характера. Cвойства 1,2 (полученные при исследовании алгоритмов [7-13]) ограничивают применение жадных алгоритмов лишь для архитектур или уровней рассмотрения архитектуры для которых целевая функция T=f(HP,HW) достаточно точно задается лишь при учете задержек tEP, tD.

Свойство 1. Для жадных алгоритмов решения NP-полных задач составления расписаний не существует единой для всех подзадач локальной целевой функции, приводящей к наилучшему варианту расписания, получаемого алгоритмом.

Свойство 2. Для жадных алгоритмов решения NP-полных задач составления расписаний влияние на качество расписания используемых локальных целевых функций возрастает с ростом сложности функции T=f(HP,HW) по учитываемым временным задержкам.

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

В работах [1,14] отмечена подверженность жадных алгоритмов построения расписаний аномалиям: улучшение параметров ВС и программы, для которой составляется расписание, может приводить к увеличению времени выполнения расписания. В [14] приведены примеры, когда списочный алгоритм получает худшее по времени выполнения расписание при: 1)увеличении числа процессоров 2)уменьшении длительности выполнения рабочих интервалов 3)снятие ограничений на порядок следования рабочих интервалов 4)уменьшение длительности внутренних простоев процессоров. По крайне мере, одной из причин подверженности жадных алгоритмов аномалиями может быть свойство 1.

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

^

5. Итерационные алгоритмы



Итерационные алгоритмы можно разбить на два подкласса:

  • алгоритмы, опирающиеся на метод проб и ошибок: генетические и эволюционные алгоритмы [6, 15-18], алгоритмы имитации отжига [19,21], алгоритмы случайного поиска (ненаправленного, направленного, направленного с самообучением) [20,21];

  • алгоритмы детерминированной коррекции расписания.

Схематично работу этих алгоритмов для решения задачи построения расписания можно представить следующим образом:

  1. Задать начальное приближение HP0, k=0.

  2. Вычислить целевую функцию f(HPk,HW) и проверить выполнение ограничений (если в п.3 возможно получение ).

  3. Получить HPk+1=D({HPi},{f(HPi,HW)},Prk:i(1,,k)).

  4. Если критерий останова не достигнут, то k=k+1 и перейти к п.2; в противном - завершить работу алгоритма.

Где, ^ D – некоторая стратегия коррекции текущего расписания, Prk – параметры стратегии (для ряда стратегий, возможно, их изменение в ходе работы алгоритма).

Алгоритмы, опирающиеся на метод проб и ошибок, содержат элементы случайного выбора привязки и порядка, что дает возможность получать информацию о их влиянии на значения целевой функции и ограничений. Данная информация используется для адаптации алгоритма (в ходе его работы) к закону влияния привязки и порядка на значения целевой функции и ограничений. Кроме возможности адаптации к решаемой задаче, алгоритмы, опирающиеся на метод проб и ошибок, наиболее полно удовлетворяют требованиям, к свойствам алгоритмов построения расписания при совместном проектировании аппаратных и программных средств ВС: 1)возможностям методов строить расписания для архитектур ВС с различным уровнем детализации; 2)универсальности методов в классе допустимых архитектур ВС; 3)совместимости методов построения расписания и методов выбора оптимальных параметров архитектуры.

Данные особенности алгоритмов обеспечивают эффективность их использования на системном уровне проектирования: определение числа процессоров, “типа” каждого процессора, топологии и характеристик компонентов (задержка, арбитраж и маршрутизация) коммутационной среды, распределение памяти (тип – ПЗУ/ОЗУ, объем, способ доступа – локальная/разделяемая, циклы считывания/записи) и построение расписания выполнения прикладной программы.

Алгоритмы детерминированной коррекции расписания для своего построения требуют некоторых априорных сведений о влиянии привязки и порядка на значения целевой функции и ограничений. Это обуславливает специализацию методов на конкретный класс архитектур ВС. Однако, для уточнения расписания (локальной оптимизации расписания) можно предложить алгоритмы детерминированной коррекции расписания исправляющие “плохие” фрагменты расписания и не использующие априорные сведения о влиянии привязки и порядка на значения целевой функции и ограничений. Если некоторый рабочий интервал находится длительное время в состояниях - ожидание данных от других рабочих интервалов или ожидание получения разделяемого ресурса, то можно попытаться уменьшить время нахождения рабочего интервала в этих состояниях путем изменения расположения в расписании рабочего интервала или его непосредственных предшественников. То есть, работа алгоритма основана на использование информации о “плохих” фрагментах расписания, которая может быть определена при анализе динамики функционирования ВС. Такое построение алгоритмов детерминированной коррекции расписания позволяет устранить их узкую специализацию на конкретный класс архитектур ВС. Основная область эффективного применения алгоритмов детерминированной коррекции решений – уточнение расписаний на уровне регистровых передач при решении задачи уточнения деталей реализации ВС с учетом элементной базы и системного программного обеспечения.

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

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

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

Использование в итерационных алгоритмах системы операций преобразования расписаний, допускающей получение расписаний , приводит к необходимости введения в функцию T=f(HP,HW) слагаемых отвещающих за штрафы при нарушении ограничений 1-5. При этом возникают проблемы корректной оценки значений T для неинтерпретируемых расписаний и искажения пространства решений.

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

^

6. Непосредственное представление и операции преобразования расписания



Бинарное непосредственное представление расписания

Расписание задается: матрицей привязки Y(HP)NM и матрицей смежности X(HP)NN графа HP, где элемент матрицы определяется:



^ M – число процессоров в ВС, N – число рабочих интервалов в H. Недостатком данного представления является большое число бинарных переменных - N2+NM.


Целочисленное непосредственное представление расписания

1. Расписание задается матрицей Y(HP)NM, где элемент матрицы определяется: ,

c – порядковый номер рабочего интервала pi в SPj. При данном способе представления расписания число целочисленных переменных равно NM.

2. Расписание задается: вектором привязки Y(HP)K и вектором порядка X(HP)N, где i-й элемент вектора Y(HP)K равен номеру списка в который назначены рабочие интервалы i-го процесса, а i-й элемент вектора X(HP)N равен порядковому номеру рабочего интервала в соответствующем списке. При данном способе представления расписания число целочисленных переменных равно K+N.


^ Операции преобразования расписания

Возможны следующие варианты отличия расписаний HP и HP друг от друга: 1)расписания HP и HP отличаются лишь порядком рабочих интервалов как минимум в одном SPj; 2)расписания HP и HP отличаются привязкой рабочих интервалов.

Введем соответствующие операции преобразования расписаний, позволяющие устранить указанные варианты отличия: O={O1,O2}. Операции O1,O2 определим для целочисленного непосредственного представления расписания. Операции будем определять при предположениях: каждый процесс имеет не более одного рабочего интервала или при условии, что на расписание не накладывается ограничение 5. После теоремы о функциональной полноте системы операций O={O1,O2} и получении условий их применимости покажем возможность снятия указанных предположений.

Операция изменения порядка рабочих интервалов в одном списке:



Операция изменяет порядковый номер рабочего интервала pi в списке SPm (порядковый номер рабочего интервала становится равным c) и корректирует порядковые номера соответствующих рабочих интервалов в данном списке. NSm – число рабочих интервалов в списке SPm.

Операция изменения привязки рабочих интервалов:



Операция переносит рабочий интервал pi из списка SPm в список SPk (порядковый номер рабочего интервала становится равным c) и корректирует порядковые номера соответствующих рабочих интервалов в списках SPm и SPk.

Теорема 1. Если HP и HP произвольные допустимые варианты расписания (), то существует конечная цепочка команд , переводящая расписание HP в HP, такая, что все K промежуточных расписаний являются допустимыми и K2N.

Следствие 1. Существует стратегия перехода от произвольного допустимого расписания к оптимальному расписанию, такая, что длина цепочки команд , переводящей произвольное допустимое расписание в оптимальное, не превосходит значения 2N (K2N) и все K промежуточных расписаний являются допустимыми.


Условия применимости операций не нарушающие ограничений на HP

Расписания HP будем представлять в ярусной форме максимальной высоты. Получим интервал значений параметра c при применении операции O1/O2 к рабочему интервалу (нижний индекс – номер рабочего интервала в H, верхний – номер яруса на котором расположен рабочий интервал). Обозначим через - множество непосредственных предшественников рабочего интервала (всегда выполняется k<i и l<s), - множество непосредственных последователей рабочего интервала (всегда выполняется k>i и l>s). Операция - получает максимальный номер яруса, на котором расположен один из непосредственных предшественников рабочего интервала , для рабочих интервалов, не имеющих предшественников lin=0 (нулевой ярус всегда пуст). Операция - получает минимальный номер яруса, на котором расположен один из непосредственных последователей рабочего интервала , для рабочих интервалов, не имеющих последователей lout=N (N – число ярусов в HP, для ярусной формы максимальной высоты число ярусов всегда равно числу рабочих интервалов). Тогда, рабочий интервал может быть размещен в любой из списков SPj на любой из ярусов из интервала lin<s<lout. Если выбранный ярус занят, то осуществляется коррекция ярусной формы путем соответствующего сдвига ярусов.

Пусть рабочий интервал переносится в SPj или изменяется его порядковый номер в этом списке. Разобьем множество SPj на три подмножества: - множество рабочих интервалов из списка SPj, находящихся на ярусах, расположенных выше яруса (lin-1); - множество рабочих интервалов из списка SPj, находящихся на ярусах ; - множество рабочих интервалов из списка SPj, находящихся на ярусах, расположенных ниже яруса (lout+1). Параметр c при размещении рабочего интервала в SPj может принимать следующие значения, не нарушающие ограничения на HP (индекс j для PIN, PI, POUT будем опускать):



PIN


PI

POUT

C

1

PIN=

PI=

POUT=

c=1

2

PIN=

PI=

POUT

c=1

3

PIN=

PI

POUT=



4

PIN=

PI

POUT



5

PIN

PI=

POUT



6

PIN

PI=

POUT=



7

PIN

PI

POUT=



8

PIN

PI

POUT



Указанные выше интервалы значений параметра c не нарушающие ограничения на HP могут быть расширены, если ярусная форма максимальной высоты будет приведена к такому виду, что все рабочие интервалы SPj, которые не находятся в отношении транзитивного порядка с непосредственным предшественником рабочего интервала , находящимся на ярусе lin, и расположены на ярусах с меньшими номерами чем lin, будут перенесены на ярусы с номерами большими чем lin. Аналогичное преобразование ярусной формы может быть осуществлено и для непосредственного последователя рабочего интервала , находящимся на ярусе lout.


^ Возможность снятия условий: каждый процесс имеет не более одного рабочего интервала или на расписание не накладывается ограничение 5

Поскольку, при доказательстве теоремы 1 и получении условий применимости операций O1/O2 использована ярусная форма максимальной высоты (на каждом ярусе находится лишь один рабочий интервал), то полученные результаты легко могут быть обобщены на случаи когда: каждый процесс может иметь более одного рабочего интервала или на расписание накладывается ограничение 5. При перемещении рабочего интервала из одного списка в другой, перемещаются также и все рабочие интервалы процесса, которому принадлежит перемещаемый рабочий интервал, но при этом остаются на прежних ярусах. В результате получаем ярусную форму нового расписания, и, следовательно, полученное расписание удовлетворяет ограничениям 1-5.


^ Операции преобразования расписания в алгоритмах имитации отжига и случайного поиска

Получение расписания на очередной итерации алгоритма может быть осуществлено как случайный выбор:

  • рабочих интервалов, к которым следует применить операцию из набора {O1,O2}, диапазон номеров интервалов: [1,…,N];

  • типа применяемой операции O1/O2 (если операция O2 выбрана для применения к рабочему интервалу некоторого процесса, то для остальных рабочих интервалов этого процесса могут применяться лишь операции O1);

  • параметра операций c из интервала, определяемого условиями применимости операций, не нарушающими ограничений на HP;

  • для операции O2: списка , в который переносится рабочий интервал.

Длина шага равна числу применяемых операций .

^

7. Параметрическое представление расписания



Параметрическое представление расписаний с использованием приоритетов

Расписание задается вектором YN+K :







K - число процессов в H, Ni – число рабочих интервалов в i-ом процессе, - число рабочих интервалов в H.

Параметр содержит номер процессора, на котором выполняются рабочие интервалы i-го процесса, т.е. параметры однозначно определяют распределение рабочих интервалов по SP (привязку). Параметры могут принимать значения от 1 до K. Если значения всех параметров равны, то все рабочие интервалы выполняются на одном процессоре, если все значения различны, то рабочие интервалы каждого процессора выполняются на своем процессоре. В силу ограничения 5, максимальное число не пустых процессоров равно числу процессов K в H. Параметры используются алгоритмом восстановления расписания (определение отношения полного порядка в каждом SPi) в качестве приоритетов рабочих интервалов.

При данном способе представления расписания число целочисленных переменных равно N+K.

Для описания алгоритма восстановления, множество рабочих интервалов разобьем на три подмножества: . P1 - множество рабочих интервалов распределенных в SP (определен порядковый номер рабочего интервала) алгоритмом восстановления на предыдущих шагах; P2 - множество рабочих интервалов, у которых все предшественники принадлежат P1; P3 - множество рабочих интервалов, у которых хотя бы один из предшественников не принадлежит P1.

^ Алгоритм восстановления строго порядка рабочих интервалов в SP (A1).

1. Начальное разбиение множества P:

P1=; - множество рабочих интервалов в H без предшественников; - - множество рабочих интервалов в H, у которых имеются предшественники.

2. Находим в P2 рабочий интервал с наименьшим значением параметра (если таких интервалов более одного, то выбираем интервал с наименьшим номером):

  • размещаем его в конец соответствующего списка SP (номер списка определяется значением параметра );

  • переносим его из P2 в P1.

3. Проверяем P3 с целью возможности переноса рабочих интервалов в P2:

если есть рабочие интервалы, у которых все предшественники принадлежат P1, то переносим их в P2.

4. Если P2, то к п.2, иначе завершить работу.


Утверждение 1. Алгоритм A1 восстановления расписания по его параметрическому представлению YN+K получает расписание и расписание восстанавливается однозначно.

Теорема 2. Любое допустимое произвольное расписание может быть задано параметрическим представлением с использованием приоритетов (YN+K) и однозначно восстановлено алгоритмом A1, если допустимая верхняя граница L значений параметров больше или равна числу рабочих интервалов (LN).


Операции преобразования расписания

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

  • параметры могут принимать целочисленные значения в диапазоне [1,…,K],

  • параметры могут принимать целочисленные значения в диапазоне [1,…,L],

  • количество изменяемых параметров может изменяться от 1 до N+K.

Операции преобразования параметрической формы представления расписаний, удовлетворяющие условиям 1-3 при использовании алгоритма восстановления A1, будут получать расписания , что следует непосредственно из утверждения 1. Из теоремы 2 следует, что данные операции преобразования расписания и алгоритм восстановления A1 позволяют получить любой допустимый вариант расписания.

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

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


Параметрическое представление расписаний с использованием характеристик рабочих интервалов

Расписание задается вектором YK :



Параметр содержит номер процессора, на котором выполняются рабочие интервалы i-го процесса, т.е. параметры однозначно определяют распределение рабочих интервалов по ^ SP (привязку). Параметры могут принимать значения от 1 до K. При данном способе представления расписания число целочисленных переменных равно K.

Алгоритм восстановления A1 вместо значений параметров в качестве приоритетов может использовать характеристики рабочих интервалов: вычислительную сложность рабочего интервала, число непосредственных последователей, число непосредственных предшественников, априорно заданные приоритеты. Для данного способа параметрического представления расписания справедливо утверждение 1, однако, теорема 2 не выполняется. При построении алгоритмов оптимизации, использующих данный способ представления расписания, следует обращать внимание на принципиальную возможность получения расписания с требуемым качеством.

8. Заключение



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

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

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

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

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

^

Список литературы





  1. Теория расписаний и вычислительные машины/ Под ред. Э.Г.Коффмана. М.: Наука, 1984. - 334с.

  2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир, 1982. - 416с.

  3. Смелянский Р.Л. Модель функционирования распределенных вычислительных систем// Вестн. Моск. Ун-та. сер 15, Вычисл. Матем. и Кибернетика. 1990, No. 3, стр. 3-21.

  4. Смелянский Р.Л. Об инварианте поведения программ // Вестн. МГУ, сер. 15, Вычислительная математика и Кибернетика, 1990., No. 4, С. 54-60.

  5. Воеводин В.В. Математические модели и методы в параллельных процессах. – М.: Наука, 1986.

  6. Костенко В.А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации// Труды IV Международной конференции "Дискретные модели в теории управляющих систем" (19-25 июня 2000 г.) – М.: МАКС Пресс, 2000., С.49-55.

  7. Костенко В.А. Метод автоматизированного синтеза параллельных программ для вычислительных систем с MIMD архитектурой// Программирование, 1993., No. 1, стр. 43-57.

  8. Костенко В.А. Автоматизация составления параллельных программ для вычислительных систем с MIMD архитектурой// Кибернетика и системный анализ, 1995., No. 5, стр. 170-179.

  9. Костенко В.А. Задачи синтеза архитектур: формализация, особенности и возможности различных методов для их решения// Программные системы и инструменты. Тематический сборник. - M.: МАКС Пресс, 2000., № 1, С.31-41.

  10. Подгорный С.А., Смелянский Р.Л. К вопросу синтеза структуры вычислительных систем на основе поведения программ// Вопросы организации программного обеспечения и принятия решений. МГУ, 1993.

  11. Костенко В.А., Романов В.Г., Смелянский Р.Л. Алгоритмы минимизации аппаратных ресурсов ВС// Искусственный интеллект (Донецк), 2000., No2, С.383-388.

  12. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод комбинирования эвристик для решения комбинаторных задач упорядочивания и распределения ресурсов// Информационные технологии, 1997., N 2 - С.29-32.

  13. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации// Информационные технологии, 1999, N 1 – С.2-7.

  14. Шахбадзян К.В., Тушкина Т.А. Обзор методов составления расписаний для многопроцессорных систем// Записки научных семинаров ЛОМИ – Л.: Наука, 1975., т.54 – С.229-258.

  15. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.

  16. Zbigniev Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs// Third, Revised and Extended Edition – Springer, 1999.

  17. Костенко В.А., Смелянский Р.Л., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов// Программирование, 2000., №5, С.63-72.

  18. Обозрение прикладной математики. Серия “Методы оптимизации”. Эволюционные вычисления и генетические алгоритмы// Т.3, выпуск 5. - 1996.

  19. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика.- М.: Мир, 1992.

  20. Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.

  21. Костенко В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС// Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (30 октября - 2 ноября 2000., г. Черноголовка). -М.: Изд-во МГУ, 2000., С.123-127.




Скачать 302,88 Kb.
оставить комментарий
Дата29.09.2011
Размер302,88 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх