автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Метод и средства планирования задач в неоднородной вычислительной системе

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ " КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ "

На правах рукописи

Фам Хокг Хань (Вьетнам)

УДК 681.324

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

Специальность 05.13.13 - Вычислительные машины, системы и сети.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Киев - 199?

Диссертация является рукописью.

Работа выполнена в Национальном техническом университете Украины "Киевский политехнический институт" на кафедре вычислительной техники.

Научные руководители: кандидат технических наук, доиент Симоненко Валерий Павлович доктор технических наук, Генрик Пьех (Польша)

Официальные оппоненты: доктор технических наук, профессор

Печурин Николай Капитоновнч

кандидат технических наук, доцент

Щербина Александр Андреевич

Ведущая организация: Институт проблем моделирования в энергетике НАМ Украины

Защита состойся £ 6 __ 1997 г. в 14 м часов на заседании специализированного Советзд 26.002.02 в Национальном техническом университете Украины "Киевский политехнический институт" (г. Киев, пр. Победы, 37, корп. 18, ауд 306)

Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения,-просим направить но адресу:

252056, г. Киев, пр. Победы, 37, Ученому секретарю НТУУ "КПИ"

с диссертацией можно ознакомится в библиотеке Национального технического университета "КПИ"

Автореферат разослан 1997 г.

Ученый секретарь специализированного совета кандидат технических наук^ доцент

М.Н. Орлова

АННОТАЦИЯ

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

Для достижения этой цели в диссертации решаются такие задачи:

1. Сравнительный анализ и классификация методов и алгоритмов планирования в распределенных вычислительных системах обработки данных и выделение особенностей и требования к системе планирования в НРСОД.

2. Разработка математической молсли системы динамического планирования в НРСОД. определение требований и критериев оптимизации задачи распределения при динамическом планировании в НРСОД.

3. Разработка алгоритма решения задачи распределения и оптимизации при динамическом планировании s НРСОД для выбранной модели системы динамического планирования.

4. Статистическое исследование и сравнение разработанного алгоритма с существующими для доказательства эффективности нового алгоритма.

1. Общую модель динамического планирования в неоднородных распределенных citcTeMav обработки данных.

2. Математическую постановку задачи распределения и оптимизации при динамическом планировании в НРСОД.

3. Утверждения и следствия, положенные в основу адаптивного алгоритма направленного поиска решения.

4. Алгоритм направленного поиска распределения и оптимизации при динамическом планировании в НРСОД.

5. Программные средства реализации адаптивного алгоритма направленного поиска, алгоритма мультианализа для решения задачи распределения в НРСОД.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Анализ развитии вычислительных систем в последних годах показывает что создание и применение такие стандарты для высокоскоростных связи, тз кис как: FDDI, 1IÍPP, SONET позволят строить глобальные ВС, объединяющие различные мощные удаленные вычислительные машины для совместной, эффективной к экономной обработки различных задач. Широкое применение таких систем как PVM, MPI, Express, Р4, Linda, Panda сдерживается достаточно большой долей высококвалифицированного ручного труда при подготовке программ атя исполнения в параллельной ВС.

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

как программы, процедуры, параллельные участки программ, отдельные блоки команд, команды и отдельные макро или микрооперации.

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

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

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

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

■ Научная новизна работы заключается в следующем: ' 1. Разработана обшая модель динамического планирования для неоднородных распределенных системах обработки данных.

2. Разработан новый подход к решению задачи распределения ресурсов и заданий и оптимизации ее решения при динамическом планировании дня НРСОД. где критериями оптимизации я&тяются время решения заданий (с учетом временных затрат на передачи данных) и время ответа заданий.

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

Практическая ценности результатов диссертационной работы состош к том, что применение предложенных методов и средств динамического планирования в НРСОД позволяет повыстить эффективности планировании и НРСОД, таких как Р\'М или 5шапКет

Достоверность утверждений и выводов подтверждается строгими теоретическими доказательствами И результатами статистического моделирования.

Апробаияя роботы. Основные н2у'!:;:.:с рсзулыаты диссертационной рабо-1Ъ1 докладывались на:

1. Десятой " Европейской конференции по моделированию" (!0,h European Simulation Mu',!iconlerencc-ESM'%), в т. Будапеше, Венгрия, 2-6 Июни 1996.

2. Третей " Международной конференции по Параллельным и Распределенным процессам, Техникам и Применениям " (3th International Conference on Parallel and Distributed Processing Techniques and Applications-PDPTA'96) в Калифорнии. США. 9-11 Августа 19%.

3. Олинацалтой " Международной конференции по Параллельным Процессам " (llI!l International Parallel Processing Symposium) в г. Женеве, Швейцарии, 1-5 Апреля 1997.

Публикации. По Teste диссертации опубликованы 4 научных работы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 145 страницах машинописного текста, содержит 90 рисунков, список литературы и а 190 наименований и дпух приложений.

Вй_В2ЯЯ£ШШ обосновывается актуальность темы диссертационной работы, формулируется цель и задачи исследования, основные положения , выносимые на защиту.

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

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

ОдшаКЙ ГЛЗ.Е£ описывается предложенный метод направленного поиска решения при распределении заданий и ресурсов в НРСОД, описываются пропел) ры алгоритма направленного лоиехз для решения проблем опшмшации и распределения, выполнено описание шагов алгоритма м>л!.!панализа для процедуры поиска назначения, выполнена оценка »рсм'чжой сложности алгоритма направленного поиска (АНП).

В^е1вещ^й.ХДЗ£ё представлена основз моделирования процесса планирования в НРСОД и результаты статистического исследования АНП и сравнительный анализ АНП с альтернативными алгоритмами- при планировании в НРСОД

В заключении приведены основные результаты работы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

• В параллельных вычислительных системах: многопроцессорных, многомашинных комплексах, сетях (локальных или глобальных) задача планирования для распределения заявок (заданий, процессов...) на подходящих ресурсах в сцстемс является одной из самых труднорешаемых задач в вычислительной теории и теории расписаний. На протяжении последних лет гигантские технологические достижения позволяют создавать мощные вычислительные системы, в которых можно обработать сразу большой поток разнотипных задач различными ресурсами. В таких системах построенных на высокопроизводительных элементах эффективность обработки высокораспараплельных задач во многом зависит от организации вычисления, то есть от того как и каким обра' зои надо управлять и распределять работы н ресурсы системы наилучшим образом. В целом, вычислительную систему и вычислительный узел в общем виде можно рассматривать с различной степенью детализации как совокупность ресурсов, а объекты планирования вычислений или "злдяшаГ на ресурсы могут быть представлены как программы, процедуры, параллельные участки программ, отдельные блоки команд, команды и отдельные ма'кро или микрооперации.

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

Классическая трехуровневая модель планирования вычислительного процесса приемлема в ВС с небольшим числом процессоров и состоит из 3 типов

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

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

Распределение заданий {работ, процессов) на ресурсы в системах массового распараллеливания (МПС-однородных системах) или в распределенных системах (РС-неоднородных системах) имеют следующую общую постановку : Система ресурсов эшхна грзфом системы где: . ш

• {Я|Д2, ...Дм}- множество вершин каждый элемент которого представляет один из N ресурсов системы и ^<=N1 (множество натуральных чисел), 1=1. .К

• Е(г={Е|,Ез.....Еа)- множество дуг каждый элемент которого представляет

связь одного ресурса с другим Е,=(К;,где и 0 2 с! 5 Ы2 .

• \УУК=) множество весов вершин, где М/УЯ^ИЕ^ИТ^. Для Vг— 1..N, КЕ,еч.Я+ (множество положительных реальных чисел) - характеристика ресурса ЯТ,е{0 и ЭТ4"! - состояния ресурсов.

• \УЕЯ={\\'ЕК|,\УЕ!12,...,\УЕКр |- множество весов дуг. Это множество можно представить в виде некоторой матрицы КС=КС[1Ле<Н+, где 1=1..М и ..Ы. Поток И заланнй, задан множеством (.! ,,.12,...,.1М}, каждый элемент которого предста.ляст одно из М заданий и .^РМ;, .Щ, }, где для

• ЛЧ.е N1 - номер задания,

• .)Е;е,.Н+ - объем работы задания.

• Л.,= {(К',ф|), ..., (Кч,<рд)}, где Я'еУц - ресурс с которым данное задание требует обмена данными, 1Р|е9!'1" - объем передачи, 1=1.-Я, чеЫ| .

• .)М,=|0 или И' )- маска задания, где И'е- номер ресурса, на котором желательно выполнять данное задание.

• Л'.е'Л* - приоритет данного задания.

При Оптимизации и Распределение, функшно А для измерения веса назначения задания 1, на ресурс И, (Я,еУк и VJ), в общем случае можно определить слел\юшмм образом:

Таблица 1

Классификация По Динамичности Статические (АС)

1 Динамические (АД)

2 Классификация по Особепостям Систем По Однородности для Однородныхг систем (АОС). для Нсднородных систем (АН С)

По Организации памяти с Обшей памятью (АСОП). с Распределенной памятью (АСРП).

По Степени Параллелизма Крупно-зернистое планированис(АКЗ) Средне-зернистое планирование(АСЗ) Мелко-зернистое планироьание(АМЗ)

3. Классификация во Характерам Заданий. Связанных Заданий (АСЗ). по Спискам (АСС)

Клайстерное Планирование В перед (АС КВ) Назад(АСК Н)

Несвязанных Заданий (АНЗ). Обычное (АНО)

Самостоятельное (АН С)

4 Классификация по Дисциплинам Безприоритетные(ДБ))

Приоритетные (ДП)

5 Классификация Т1 по Технике Неиг! Решение Бис Т2 ТЗ Т4 Сепепс Ьтеаппг 5!тша1юп ТЪеогу Т5 в гарЬ ТЬеогу Т6 Сой Рипсйоп

6 Классификация по организации Оп-Ипг, 0/[-Цпе О! 02 03 04 05 Об 07 08

Где:

01. Класическое Статическое Планирование:

02. Планирование с реконфигурацией в соотвествни виды ресурсов.

03. Статическое Планирование с Приоритетами.

04. Планирование по Параметрам.

05. Динамическое Планирование с Приоритетами.

06. Планирование о системах с обшей пзмятю.

07. Балансирование Загрузки и Адаптированное планирование. ОЗ. Планирование Распределением Загрузки.

л (Р.,, .',)= 5и - П р; > х Пс;'»I ¿Л" (2)

4-4 у.»

Где,

• П р>" " величина абсолютного приоритета назначения (Я^). Он вычисляется путем умножения величин всех К относительных приоритетов Р,"е1Л+ не только заданий но и ресурсов учитывающих выполнение некоторых требований - время ожидания заданий, работоспособность ресурсов

к

и Т.д.). Для Ук=1..К р' 5 Р<. р", поэтому т' 4 П р>'' 5 р" ■

1-)

ч . .

• ' " результат анализа всех Н обязательных требований, где С^ - степень выполнения обязательного требования х для назначения задания ^ на ресурс К,, С| ' е {0,1}. Например требования наличия канала передачи, необходимого объема памяти и т.д. если ресурс ^ удовлетворяет требования задания ^ и С',' =0 в противном случае.

• ' - результат анализа всех в оптимизирующих требований, где

О^ и (У <. Ой О' есть степень выполнения оптимизирующего требования у для назначения задания ^ на ресурс ^ ; Це9?+ и есть весовой коэффициент оптимизирующего требования у.

В нашей системе представленной мы имеем : *

о />■•' вычисляется с помощью приоритета задания где JPj=l/Twj=pj (

Ту^ есть время ожидания задания ^ в системе) и маски задания Ш<={0 или И*), Я'еУц

К

ПЛ"=И*Р] ,

М°. если 1*,= Ж, =11»

гае. И ^ есди ^ ^ е{о я«}

н

и с; ' вычисляется с помощью сравнения характеристики по коммуника-

1-1

ции задания Щ ={(11', «р]), .... (Я4. Фч) ) с множеством дуг графа системы

ресурсов Ед={Е), Е2.....Ео):

для : cq'=I, если ( Д')еЕк ;

СС, '=0, если ( Д'^Ец ;

я '

В конечном итоге 1~{с- '

И V l/)^' вычисляется как сумма обратной величины времени выполнения

у-1

Tejj и обратной величины времени коммуникаций Тсу с помощью: коэф-фицента REi=jt/ из его веса в WVR,; объема работы задания JEJ=e>; матрицы весов дуг в графе системы ресурсов RC[k,l|=py . гае k=l..N и 1=1..N; требований задания по коммутации JLi={(R,> <pi),..., (R4, <pq).

с

£ Л О/ определяется следующим образом:

Teg = si * ki ; Teg = £ (р,. ,) .

/ -1

Таким образом, мы имеем : « • ,

X Ly01;' ш +1Дси= 1/(6,* k, )+i/Z (ч>,* Рм) Из (2) мы имеем:

A(R,.JJ> = Su"=(|iJ*pJ>CM*[1-i-(eJ*kl) + 1-bi(vl-pu)3 (3)

Очевидно, что 5у t. О для Vi=l..N„ j=I..M, . Поэтому низкая граница значения функции измерения решений равна нулю: тГ(й(К„ i,))=0.

В том случае, если на данный момент между ресурсами i и I нет связи, RC[i,l] получает такое значение Pi j , что Tq j= ^ (♦ ,) > Xq , где Хо некоторое

заданное число. Число Хо есть порог для определения существования связи .между двумя ресурсами. Время выполнение Te,j имеет некоторую нижнюю границу Т®. Тогда верхняя граница диапазона изменения 5у определяется следующим образом:

sup(A(Ri, Jj))= (Н- oj* Р Oj)* [1 / Т 0 + 1/X01"W

Эта задача, в общем виде, в комбинаторной теории формулируется как задача назначения В общей пиле она является NP-полной. Однако, в данной постановке она сводится к задаче поиска максимального паросочетания во взвешенном двудольном графе.

Существует несколько полиномиальных методов для решения задачи назначения для взвешенного двудольного графа G=(Vr,Vj, Е, WE):

где, Vr={R„R2,...,Rn< ) и Vj=(J,,J2.....JM), •

Е ={Е,,Е2.....EdJ.Et =jR*,J*}, где R«6Vr и J'eVj,

где k=l..d , 0<dsN,xM. Наиболее известным алгоритмом решения этой задачи является Венгерский, включающий в себе подзадачу поиска максимального паросочетания для невзвешенного двудольного графа.

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

Если п матрице RJ[ij], i=l..N, j=l..N прафа G=(Vr,Vj,E), где yR={l,2,...N), Vj={l,2,...N|, существует решение А. мощностью n=N и существуют такие вершины p,q что :

RJ[p.q)=I.

RJ[pj]=0 V js{ l,..,N)\q и/или (I) RJl¡,q]=0 V ie(l,..,N}\p. (2)

Тогда эта пара (p,q) всегда участвует d решении Л, (p,q)sA. Если в матрице RJ[ij], i=l..N, j=l..M, 3FA (веер):

. FA=«R',q), (R:.q)..... (Rf.q)}, Rke{l,..,N), f sN, где RJ[Rk,qJ=l для

Vk=l..f и RJ|Rk,Jl]=0, VJk e{l,..,N}\q (3) или

• FA={(p,J'), (p,J;).....(p.JOl, Jk€{l,..,N}, 2<, f sN, где RJ[p,JkJ=l для Vk=l..f и

RJ[Rk,Jkl=0, У Rk e{l,..,N¡\ p. (4) тогда любая из вершин FA входит в один из вариантов максимального паросочетания, задача назначения не имеет полного решения и мощность максимального паросочетания M<N-f+l. Утверждение 3.

Если в матрице RJ[ij], i=l..N, j=l..N мы можем выделить такую подматрицу ММ размером T*S, где MM[k,l]=RJ[k,l], k=l..T, 1=(N-S+1)..N, где S+T>N и MM=Q (G - нулевая матрица), тогда задача назначения не имеет полного решения. (Рис 2.20а-в) Утверждение 4.

Если в матрице RJ[ij], i=l..N, j=I..N, можно выделить подматрицу MN[k,l], k=l..T, 1=(N-S+!)..N, где S+T=N и MN=0, тогда для Rje{l,..,(N-S)|, Jj s((T+l),..,N}: V (Rj, Jj) г А. И все эти (R¡, Jj) г А должны быть обнулены при поиске полного решения( Рис. 2.21.а-в). Утверждение 5.

Если в матрице RJlijl, i=l..N, j=Í..N, можно выделить несколько подматриц MN удовлетворяющих Утверждению 5, то все соответствующие симметричные им относительно главной диагонали подматрицы являются "конфликтными" и , должны быть обнулены. Доказательство аналогично доказательству Утверждения 5 и справедливо для каждой подматрицы отдельно.

Утверждение 6. Если в матрице RJ существует подматрица МТ такая, что V k=l.T , 1=(N-S+1)..N : кроме МТ[Т, (N-S+1)J=I все остальные элементы МТ[к,1]=0, где S+T=N+1 , тогда назначения (Т, (N-S+1)) является "ключевым" и всегда участвует в состав одного из вариантов решения.

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

Рис. 1 Схема алгоритма направленного поиска

Основой А.НП лгяается Вснгсрский меюд, "который имеет временную сложность 0(nJ), где п есть количество вершин графа исходной матрицы заданий-ресурсов JR Однако, как описано выше, для процедуры поиска максимального паросочетания используется разработанный алгоритм AMA смссто традиционного метода Кариа-Хопкрофта, который был использован в Венгерском методе. Временная сложность алгоритма Карпа-Хопкрофта известна, как O(nVîm) , где m есть количество дуг графа матрицы заданий-ресурсов JR. Но n i m й п2 , поэтому алгоритма Карпа-Хопкрофта имеет временную сложность 0(п2-5).

Для оценки временной сложности АНП, то есть Венгерского метода с использованием AMA вместо алгоритма Карпа-Хопкрофта, выполним:

• Оценку временной сложности Венгерского метода без алгоритма Карпа-Хопкрофта.

• Оценку временной сложности AMA отдельно.

А. Временная сложность Венгерского метода без алгоритма Карпа-Хопкрофта. Алгоритм АНП состоит из 4 главных процедур. Проводим оценку временной сложности для каждой из них :

(1) Процедура подготовки данных и поле поиска: согласно схемы процедуры в разделе, она имеет временную сложность (пг).

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

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

(4) Процедура определения новой линии поиски: согласно схемы процедуры в разделе, она имеет временную сложность (п+2лг) для маркировки и (Зп2) для перестановки. В итоге, ее временная сложность равна Y^ín+Sn1).

Кроме этого, имеется цикл из процедуры (4) в (3). Допустим что этот цикл имеет временную сложность Z . Так как Венгерский метод имеет временную сложность 0(nJ). Поэтому временная сложность процедур внутреннего цикла будет равна 0(n3)/Z. С другой стороны, эта временная сложность можно считать как max(X,Y). Так как в Венгерском методе, для процедуры (3) используется алгоритма Карпа-Хопкрофта, поэтому X^Oín'^m) или X=0(n2-5), Y=(n+-5nz). Отсюда, 0(n3)/Z =max(X,Y)=X=0(n'/2m) или 0(п2'5). , Таким образом, Z=0(n2'5/m) или 0(п°-5).

В итоге, временная сложность Венгерского метода без процедуры (3) (без алгоритма Карпа-Хопкрофта) является 0(пг + 2п+ 0(n°>5)[ n+5n2] > а в общем случае 0(п2 + 0(п°-5) х шах(Х, il2)). ¡¡.Временная сложность ASÍA.

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

формируются сше и вектора степеней вершин графа, то временная сложность этой процедуры увеличивается на 0[2п]. Тогда общая временная сложность выполнения этой процедуры 0|Е+2п]. При выполнении грубого анализа выполняется поиск изолированных вершин и для этого необходим одноразовый просмотр векторов ВСЗ и ВСР, что определяет временную сложность выполнення этого шага 0[п]. Выполнение шага 2 для поиска обязательных назначений имеет временную сложность 0[п] и в случае каждого обнаружения вершины со степенью "1" выполняется редукция исходного графа временной сложностью 0[2п1, а в случае единственного решения после выполнения п шагов может быть получено полное решение. Тогда временная сложность получения полного решения равна 0[п(п-1)/2+Е]. Общая временная сложность этой процедуры равняется 0[п+2п]=0[3п]. Сложность выполнения п'.лга 3 определяется сложностью алгоритма сортировки одномерного массива и сложностью анализа преобразованной МС и ее коррекции и равна 0{2nlogn+-E/'2+E/2j.

Таким образом, общая временная сложность AMA: XAMA=0[E+2n+n+3n+2nlogn+EI=0[2E+6n+2nIogn+EJ=Oi3E+2n(3+logn)l.

Ввиду того, что на общую оценку сложности алгоритма влияет сложность выполнения шагов 1 и 4 и значение Е на самом деле равна шив худшем случае равна и2, то сложностью остальных шагов можно пренебречь. Тогда сложность алгоритма AMA равна 0[E+nlogn] или O[m+nlognj. Однако анализ алгоритмов выполняющих поиск максимального паросочетания на основе теоремы Бержа, и примеров, с помощью которых обычно иллюстрируется работоспособность предлагаемых алгоритмов, позволяет сделать вывод, что для большинства вариантов, не требуется выполнение шага 4. и, следовательно, сложность описанного алгоритма получения решения можно уменьшить для этого вида графов до OfEJ при использовании списков инцидентности, а при использовании МС до 0[пг].

Таким образом, мы имеем временная сложность Венгерского метода в общем случае 0(n2 + n°-s х тах(Х, п2)) или 0(n2 + (n2-5/m) х тах(Х, п2)), где X = Хдма= O[m+nlogn] и п<т< п2. Тогда временная сложность АНП равна 0(п2 +n2-s/m х [m+nIogn]= 0(п2 +п25 logn/ni)=0(ii2-5logn) когда m-n или

O(n''5logn) когда гп=пг . Таким образом, временная сложность АНП равна O(n2-5logn), что меньше чем 0(п3).

Надо заметить что эта оценка производить теоретическим путем и O(n2,5logn) является время решения'в худшем случае, который имеет очень маленькую вероятность существования (<1/п2). Кроме этого, временную сложность AMA можно уменьшить за счет применения известных быстрых алгоритмов сортировки и исключения из алгоритма операций но перестановке строк и столбцов, а выполнять запоминание только их нового порядкового номера и выполнять косвенную адресацию.

Для подтверждения теоретических выводов и расчетной временной сложности алгоритма направленного поиска и алгоритма AMA (рис. 2) в работе приведены результаты работы моделирующей системы в сравнении с альтернативными алгоритмами. Основой исследования алгоритмов планирования в НРСОД, кроме моделирования системы • и действия алгоритмов-

пданиновщиков, яндяются пэр^мстры. которые из^ряются при последняя ын и. Для отражения исполнения каждого алгоритма-планировщика при планироса-нии, фиксируются следующие параметры: I

» время планирования (ВП): ТкЬ - время для составления расписания для N

свободных ресурсов и М ютовых заданий. • суммарное время выполнения (СВВ): Техе - общее время выполнения (включая временные затраты для коммуникации) М готовых заданий с помощью N свободных ресурсов и по составленному расписанию. » время ответа (ВО): ТГС5 есть сумма времени ответа для каждою задания, которое вычисляется как период времени от момента поступления задания в очередь на выполнения до момент его выполиення по полученному распи-

Рис. 2. Результаты сравнительного статистического моделирования зависимости времен« решения задачи назначения алгоритмами Карпа-Хопкрофта и AMA от размерности задачи

О Исследование зависимости времени планирования АНП ог степени неоднородности системы: На рис. 3. прел ставлены результаты исследования время планирования Т^ по алгоритму АНП и Венгерским методом с фиксированным размером ВС (п=20). При этом степень неоднородности системы изменяется от 0% до 100%. Результаты статистических испытаний показали что алгоритм АНП работает быстрее Венгерского метода во всех диапазонах Н, и чем больше степень неоднородности системы, чем больше разница времени планирования, Г! Исследование зависимости качества планирования (суммарного времени

выполнения) по атгоритму АНП от степени неоднородности системы: На рис. 4. представлены результаты исследования суммарного времени выполнения по алгоритму АНП и по Венгерскому методу с фиксированным размером (п=20). При этом степень неоднородности системы изменяется от 0% да 100%. Результаты исследования показали что качество расписании полученных по алгоритму АНП не хуже чем по Венгерскому методу. Однако эта разница является несущественной на всех степени неоднородности системы. Я Исследование зависимости времени ответа алгоритма АНП от степени Неоднородности Системы (рис. 5): Исследование времени планирования Т„, по алгоритму АНП я венгерском ме-

годом с фиксированным размером п=20. При этом степень неоднородности системы изменяется от 0% до 100%. Результаты исследования показали что Тге,-0 для всех значения степени неоднородное™ системы [0%-100%1 и для АНП и венгерского метода. То есть качество полученных расписаний по этому показателю является одинаковым «' оптимальным.

С1АВ1ШШЕ ЮШГК-СКОГО И СОЛ МЕТОДОВ

—ЕЗеигирсквв Метод -»- ООА._

Рис 3.

СРАВНЕНИЕ ЕЕНГЕУСКОГО И ООА МЕТОДОЙ

КШ)^-160001 паю 1200010000 вам вооо-

4С00-2000 о

С1«тт* Нсодхсфвдаос?*

—Вонхврскнй Мвгтод -«- ООЛ_

Рис 4.

В Исследование зависимости времени ответа алгоритма АНП от размерности системы:

Выполним исследование времени планирования Т„, по алгоритму АНП и венгерским методом с фиксированной степенью неоднородности 50%. При этом размерность системы изменяется от п=5 до п=50. Результаты исследования показали что Тгк>=0 для всех значения рассмотренных размеров системы {5-501 и для обеих АНП и венгерским методом. То есть качество полученных

расписаний по атому показателю является одинаковым и оптимальным.

СРАВНЕНИЕ Венгерского Метода а ООА

Рис 5

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

2. Выполнен анаша, исследованы особенности систем планирования параллельных вычислительных систем, сформулированы требования к системе планирования НРСОД, разработана обшая схема планирования.

3. Исследована модель системы планирования в неоднородной вычислительной системе, выполнена математическая постановка решения задачи планирования.

4 Предложен эффективный метол решения задачи динамического планирования в НРСОД для задачи распределения и оптимизации.

5 Разработан алгоритм направленного поиска (АНП), на основании модифицированного Венгерского метода, позволяющий с меньшей временной сложностью, выполнить распределение задач по ресурсам.

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

Основные результаты диссертации опубликованы в следующих работах

1. Pham Hong Hanh and Simonenko Valéry. Л new algorithm and simulation for task assignment in parallel distributed systems. Conference ESM'96, Budapest, 1996, pp. 95-99.

2 Pham Hong Hanh and Simonenko Valéry, Adaptation of algorithm for job-resurce assignment in heterogeneous distributed systems. Conference PDPTA "96, Sunnyvale, Caflifornia USA, Vol.2, pp. 835-S4, 1996.

it

3. Pham Hong Hanh and Simonenko Valery, Task Assignment for Scheduling Jobs and Resources in Parallel Distributed Systems, Journal Informatic and Kibernetic, Vol 12, N3, 1996, pp. 1-13.

4. Pham Hong Hanh, Valery Simonenko, Objective-Oriented Algorithmfor Job Scheduling in Parallel Heterogeneous Systems, 11th International Parallel Processing Symposium, pp. 127-145.

Фам Хонг Хань

"Метод и средства планирования задач в несшораддоЯ вьпясякгслыюЗ системе " Работой является рукопись на соискание ученой степени кандидата технических , наук по специальности 05.13.13. - Вычислительные машины, системы и сети.

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

Pham Hong Hanh

"New Method and Tccfotiqucs for Job Scbedolbg Li Heterogeneous Distributed Systems" This paper is the manuscript of the Ph.D. Dissertation in Computer Science, more preciously, in the specialty 05.13.13 - Computers* systems, networks, elements and units of computing systems and controlling systems.

This Ph.D. dissertation presents a new approach to solve the problem of job scheduling for parallel processing in heterogeneous distributed systems. The optimization goals are: (i) minimum total execution time including communication costs and (ii) shortest response time for all jobs. Kiev, 1997.

First, several classifications of scheduling algorithms by different criteria are provided. Second, a new scheduling scheme, which foe uses on the heterogeneity of the computing dfstributed systems is studied. Then, a new scheduling algorithm is built for job-resource assignments. The key idea of the new approach is the use of the Hungarian method, which provides a quick and objective-oriented search for the best schedule by the given optimization criteria. In addition, by modifying this method into so-called Objective-Oriented Algorithm (OOA), the scheduling time is decreased to 0(n(E+nlogn)) for finding the optimum schedule. The simulation results show us that OOA provides better solution quality while scheduling time is less than the existing methods.

Index Terms: Job scheduling, optimization algorithms, heterogeneity, parallel systems.

Автор

КОС, 199? p. Заыоъ.-ЛЛ9 тир.- №0