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

Российская Академия Наук Институт Проблем Управления

ргз од

2 . , ГЪЗ На правах рукописи

УДК 681.324

Клушин Юрий Сергеева

-1ЫЕ МЕТОДЫ ПРОГНОЗИРОВАНИЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ ЮЖНЫХ ПРОГРАММНЫХ КОМПЛЕКСОВ НА ПАРАЛЛЕЛЬНЫХ

КОМПЬЮТЕРАХ Ч

Специальность 05ЛЗЛЗ - Вычислительные машины, комплексы,

системы и сети 05ЛЗЛ6 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических

наук

Москва 199

Работа выполнена в Институте проблем управления РАН.

Научный руководитель - доктор технических наук, профессор

Игнатущенко В.В. Официальные оппоненты: доктор технических/ ; профессор Бочаров П.П. кандидат-технических наук ■ ; ■ . • Тепляков А.В. ■ ";:..• ■ •■ <■

Ведущая организация - Институт проблем передачи . ■ . . . даформации РАН ; .■

Защита состоится" " " . ---•■■■ "199 г. в__час.

на заседании диссертационного совета Д 002.68.01 Института проблем управления по адресу:

117342, г. Москва, Профсоюзная, 65. Телефон совета: 334-93-29. С диссертацией можно ознакомиться в библиотеке Инстшута проблем управления.

Автореферат разослан"_"__ "199 г,

Ученный секретарь диссертационного совета,

к. т.н.

Е.В.

Юркевич

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

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

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

параллельных . ВС для ответственных применений такого рода базируется на анализе структуры взаимосвязей

параллельно- последовательных задач (фрагментов) заданного набора и параметров его параллелизма. .

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

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

Формально под прогнозированием времени выполнения конкретного комплекса работ понимается стохастическая оценка времени Т его реализации (среднее значение, дисперсия, функция распределения 7) на параллельной ВС, а также определение вероятности выполнения комплекса за время, не большее заданного «директивного» времени Ттах.

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

задачу достоверной аналигаческой оценки времени ЕЫполне* каждого конкретного КВР на ВС априорно-до выбора структ} и конфигурации параллельной ВС либо до детальной разрабо программ КВР. . • ■ .

• Цель работы состоит в разработке математических "моде, функционирования многопроцессорных вычислительных систем (I на . задаваемых пользователем комплексах взаимосвязанных ра1 (КВР) со случайными временами их выполнения для априорной выбора конфигурации ВС или детальной разработки программ Ю высокоточной стохастической оценки времени выполнения задаю КВР. •• • ..

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

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

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

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

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

подвижными объектами на . . бортовых многопроцессорных вычислительных системах.

Апробация работы. Основные материалы работы докладывались на Ш-й Международной научно- технической конференции «Контроль и управления в технических системах»,г. Винница, 1995 • г., на Второй Украшгской конференции по автоматическому управлению «Автоматика - 95», г.' Львов, 1995 . г., на Международной конференции « Автоматизированные системы управления», г. Тбилиси, 1996 г. •

Публикации. Основное содержание диссертационной работы изложено в четырех опубликованных научных работах. '• '

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

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

. .. Во введении обосновывается актуальность и формулируется цель диссертационной работы.

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

- графовой модели заданного комплекса взаимосвязанных работ (КВР), характеризуемого специальными параметрами параллелизма;

- базовой модели функционирования однородной параллельной ВС на КВР, задаваемых пользователем.

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

Каждый программный комплекс, называемый комплексом взаимосвязанных работ (в данном случае - программных модулей), задается в виде простого ориентированного графа G(A,H) с конечным числом вершин N, где вершина cij е А соответствует j-й

работе 0=1,2,.а множество Н "дуг отображ информационно-логические зависимости между работами. Граф может иметь только одну входную, и одну выходную висячие ду соответствующие . "начальной".-- и "конечной" вершинам гра последние могут соответствовать . функционированию операциош системы ВС по инициации и завершению программного комплекса.

Работа О/ считается предшественником по отношению к . ая,- е< имеется дуга/ а/, а$) е Я; в этом-случае -. а5 является преемником отношению к о,. Каждая работа считается готовой к -выполнению, е< выполнены все ее предшественники, т.е. , граф. <Э .считае детерминировашным. ' " ' * ;

Готовые к выполнению работы ' образуют фронт работ Б очередь к процессорам параллельной ВС. В каждый момент времени одном процессоре может выполняться только одна работа. "

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

Известный подход к рассматриваемой задаче-, прогнозировш основывался на использовании упомянутых * выше парамет] параллелизма. КВР, задаваемого . пользователем;-.. эти- парамет рассчитываются в статике для каждого конкретного КВР следукж образом. ... ... .... ... .-. .

Принимается, что выполнение работы - на . процесс! завершается событием С*, если вофронт Р поступает / работ. ■.Событиям С( приписываются -вероятности их появления ' которые и являются параметрами параллелизма КВР; эти парамет определяются по графу КВР следующим образом: ' -'• •

/ шах

/=0 ' - ' V1 ' '

си =-ГГ—, 1 = 0,1 тих., . Сй = 1, ' ■•

... ...;■..-•-■ /=0.....; ... • '

где Су = 1, если по завершению работы с номером ] имеет место событие С1, и Су = 0 в противном случае.

Процесс выполнения КВР в параллельной ВС представляется математической моделью в виде однофазной СМО, состоящей из к-одинаковых обслуживающих приборов (ОП), на которых должен быть ' выполнен пул (П) из ТУ заявок (работ); при этом для буферизации очереди готовых к выполнению заявок (текущего фронта работ Я) имеется буфер емкостью N. Случайное время' обслуживания Ц каждой работы а} на любом из ОП распределено по'экспоненциальному закону с параметром ^Лj ~]/М[1]\. Однако в силу специфики подхода значения среднего времени выполнения и интенсивности обслуживания работ усреднялись, принимались одинаковыми для всех работ КВР и равными

N -

Еэд

Состояние СМО определяется числом работ, находящихся в пуле Пив системе (в буфере и на ОП) в текущий момент времени.

Верхняя оценка числа 8тах состояний СМО при выполнении КВР та N работ определяется выражением :

с _' Ш+Ъ

Расчет модели позволяет оценить среднее время выполнения заданного КВР и функцию распределения этого времени, . а в конечном счете позволяет определить вероятность выполнения каждого КВР за заданное "директивное" время. Т,пах.

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

-б-

1. Чрезмерная формализация и обобщенность модели КВР, которая описывается только числом работ N и параметрами параллелизма а;, "скрывая" конкретную структуру заданного КВР.

2. Одним и тем. же значениям N и ее, (а следовательно, одному и тому же прогнозу времени выполнения Т) . может соответствовать целый спектр конкретных структур КВР. В связи с . этим точность прогнозирования Т, по сравнению с имитационным моделированием реализации этих же КВР, изменяется в весьма широких, пределах. Введение же дополнительных параметров в графовую модель КВР (в частности, параметров критических путей в графе О и его подграфах) приводит к резкому усложнению математической модели в целом и к увеличению ее размерности при "неадекватном" увеличений точности прогноза. •

3. Как уже упоминалось, интенсивность обслуживания ¡л усредняется и принимается одинаковой для всех работ КВР. В реальных же КВР значения и соответственно ¡Л} могут отличаться весьма существенно (в частности, на порядки) как одно от другого, так и от своих усредненных значений М[1] и ¡л.

4. Определение параметров параллелизма а / через события С/для некоторых графов КВР может оказаться неоднозначным.

Во второй главе излагается и исследуется новый существенно более точный подход к проблеме прогнозирован» выполнения сложных программных комплексов на . параллельны; ВС- метод прямого стохастического моделирования.

Суть метода заключается в следующем.

Граф О заданного КВР описывается таблицей связности ег вершин. Таблица содержит N строк (по числу вершин графа (7), каждой из которых указываются номера работ (вершин), являющих« предшественниками и преемниками данной работы.

Процесс выполнения КВР представлен математической моделью виде однофазной СМО из к>2 однотипных ОП • с буфером Б д готовых к выполнению "работ' (текущий фронт Р)\ последи поступают из пула П, содержащего в исходном состоянии N раб< Модель функционирует в непрерывном времени. Случайное время ^

обслуживания любой работы ctj ' будем считать распределенными по .экспоненциальному; закону с параметром jUj- 1/M[tj, но в нашем случае значения ji¡ остаются различными для различных работ- в зависимости от конкретных значений MftJ.

В начальный момент времени в ' систему (буфер Б и обслуживающие прибора ОП) поступает из пула П одна заявка-"начальная" работа a¡, которая немедленно . j начинает обслуживаться на одном из ОП. По завершению обслуживания a¡ (в общем случае- а}) в ОП эта работа покидает систему, "передавая" свой номер jr в пул П, из которого выбираются в буфер Б те преемники работы cfj, которые оказались готовы к , выполнению (т.е., выполнены все их предшественники); номера этих работ однозначно устанавливаются по таблице связности вершин графа G.

Из буфера Б заявки выбираются случайным образом или по некоторой другой заданной дисциплине на обслуживание в незанятые ОП. СМО функционирует до тех пор, пока в пуле Пив системе не иссякнут заявки.

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

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

Пусть Т- время жизни системы (время выполнения КВР из N работ). Функционирование рассматриваемой СМО можно описать обрывающимся марковским процессом' (ОМП) X(t), t е [О, Т),над следующ!«! множеством состояний :

.. X={{m\íw-Jn);. m=0,N-l ; w= Q,N~2;N= TJ},. где (ii,...,iw);: Jn = причем- - номера работ,

ожидающих в буфере Б, w- число таких работ;//,...,/,, - йомера работ, находящихся: на' обслуживании в ОП, п- число этих работ; т-число работ в пуле в момент t.

. Начальным состоянием процесса Х(() является .состоя! Х(0)~(Ы-1;0,...,0;1,0,...,0), при. котором в пуле находятся N-1.раб буфер пуст, а на- обслужтшти в ОП находится работа с номеро! (т.е. работа аД

Процесс обрывается, т.е. переходит в поглощающее состоя! Х\Т)=(0;0;0) после завершения обслуживанщ на'ОП "коцечн< работы <зу; что свидетельствует о выполнении всех N ра( заданного КВР. ." .

Отметим следующую важную особенность предлагаемой модели

Представляется большим искушением исключить из модели бус| Б для работ КВР, . готовых к ' выполнению; ..и отслежкв; последовательность их назначения на ОП ' непосредственно структуре графа КВР; .это, очевидно, позволило' бы существо-упростить модель. Нетрудно показать, однако, что такой подход мой привести к нарушению "марковости" процесса. .

Для нашей модели заметам, что одновременно "в системе (Б,О могут находиться, только те работы КВР, . которые являю: параллельными, ' т!е. могут выполняться одновременно 'ох относительно другой.

Нетрудно убедиться, что любые две работы а} и являю: параллельными, ' если в графе О нет ' ни одного пути \ "начальной" вершины а1 до "конечной" вершины аД включающего с вершины' о,-и а:, ' ...,.;....

Очевидно, что чем больше. возможных наборов . взаим параллельных работ определено. для данного КВР, „тем больп количество состояний может иметь соответствующий, ОМП. Поэто верхнюю оценку -5* числа Я состояний процесса 'X моделирующего выполнение любого КВР из -Ы работ, -' мож определить по "максимально параллельному" КВР;в котором 1 работы, кроме "начальной" и "конечной" (т.е. N-2 работ), являют параллельными одна относительно другой, Мошю показать, что I этого случая ■ • • • . ■ . • .

к . ' •• ' - - 1=1 где , к- число обслуживающих приборов, к = 1, Лг-2;

Г1 (N-2)1 .

•" Для каждого заданного КВР -число 5" состояний ОМП Х(1) существенно зависит от конкретной структуры КВР, и потому в' общем - случае подсчет числа ¿> аналитическим путем не' представляется. возможным. Однако это число может' быть подсчитано в результате выполнения разработанного автором унифицированного алгоритма построения множества X состояний и матрицы <2 интенсивностей переходов процессах^.

Необходимость разработай . такого алгоритма вызвана следующей очевидной особенностью прямого стохастического моделирования: в отличие от моделирования выполнения КВР на основе параметров параллелизма , при рассматриваемом подходе поведение ОМП оказывается . "индивидуальным" для каждого конкретного КВР, ибо состояния и переходы процесса Х(1) определяются здесь конкретной структурой связей между работами КВР. Алгоритмизация и, следовательно, автоматизация построения X и <2 для любого КВР позволяет "уравнять" сложность подготовки исходных данных к решению задачи прогнозирования для обоих подходов: в обоих случаях необходимо задать графовую модель КВР, причем в нашем случае ' в виде таблицы связности вершин графа О. ■•-'"-•:

Известно, что марковский процесс, которым описывается функционирование СМО, считается заданным, ' если заданы или определены: ■•.'..-•

-хотя бы одно состояние процесса;

-алгоритм определения состояния: процесса, включающий построение вектора упорядоченных состояний

X— {Х1 ,Хъ---,Хр,...,Хч,... ,Х$};

-фущсция, определяющая интенсивность переходов меж состояниями: /(Хр,Х^>в, Хр, Хч е X.

В нашем случае, для рассматриваемого ОМП уже определе исходное состояние- X; =Х(0), соответствующее выполнена "начальной" работы а/ на одном из ОП .

Что касается функции /(Хр,Хд), то эта функция определяется основе анализа множества Е событий, которые метут произойти время Д ... -

Напомним, что рассматривается функционирование ОМП непрерывном ..времени, - т,е. при А?-»0, и.:'Потому - буд пренебрегать вероятностями завершения обслуживания -; заяв одновременно (за Д () - в двух и более ОП. Поэтому ; рассматриваемого ОМП множество Е состоит из . следующих да событий. •. . - - • .

Событие Е1. . Пусть ОМП находится. в некотор состоянии Хр = (пг,1 . За время А/ на одном из ОП вероятность ¡Л] (А/ )+0( А ?) завершается обслуживание работы 4 _/ е ]п; при этом работа а,- покидает. . систему,. освобождая один ОП; -число незанятых ОЛ оказываетсяравным к-п+1.;- ■ • -

По таблице связности . вершин графа • - ЬСВР однознач устанавливаются .конкретные номера, и число ..преемников рабо

яг,-, готовых к выполнению, = 0,/я; эти работы поступают из пула .I буфер Б. В пуле остаются т*=т-й работ, а в буфере оказываю-работы с номерами /'и,....л*-^ (число их равно м'+сГ), образующи

вектор /»-к*. . . ..... . -. . . - . ,

По заданному критерию К из буфера Б, на . обслуживание незанятые ОП выбираются работы из ¿» + <1, но не более к-п работ (т.е.. не более числа незанятых ОП). . - . •.„- • -. :

.В результате,такого . перехода - процесс ; оказывается Л некотором состоянии Хд=(т*;1ж*;]„'), д > р. Очевидно, что в этом слу интенсивность перехода ОМП из Хр в -Хч равна [л^ т.е. -.-■ ЛХр, Хд)= : - .... . ... - - • .

Заметим, что если процесс находится - в состоя!; ХР = («г;; »■;_/»), то событие Е1 будет происходи

ей раз, когда завершается обслуживание работы о, (] е ) из п г, выполняемых ОП.

Событие Е2. 'Ни на одном из N занятых ОП за А/ не лшггея •• обслуживание ' работ и, следовательно, ояние Хр - (т; /*>; _/'«) не изменится; тогда интенсивность выхода

•'•..• п десса из состояния Хр равна/{Хр , Хч)= ^ |лi .

../-1

Автором разработан алгоритм определения состояний сматриваемого ОМП при выполнении любого конкретного КВР. [астности, алгоритм включает процедуру определения работ, овых к выполнению, а также работ, выбираемых на обслуживание )П; по таблице связности вершин графа О при событии Е1 ¡ершения ; каждой работы КВР. Описание алгоритма приведено в гсертации; : : ' •

Важно отметить, что при использовании этого алгоритма грица (). интенсивностей переходов рассматриваемого ОМП Х(1) азывается нижней - треугольной матрицей; это позволяет »именять известные; рекурентные формулы П.П. Бочарова и >.В.Прейдунова (Университет Дружбы народов, г. Москва) для ючета начальных моментов времени до поглащения произвольного МП-'й - наиболее важное: такре построение матрицы <2 является гобходимым условием для огфеде^ен|1я (по методу тех же авторов) ункции распределения': времеЬи; Т въ^пчлнения КВР, а в конечном чете - для решения задачи прогнозирования в полном объеме. В .«¿сертации' показано; - ч+о разработанный метод прямого тохастического моделирования КВР позволяет решить еще одну 1ажную практическую задачу- весьма точно (до долей процента) щенивать и сравнивать эффективность самых различных дисциплин диспетчеризации работ КВР, готовых к выполнению,- по процессорам МВС (при' случайном - времени выполнения каждой работы) применительно к каждому конкретному КВР без какого-либо усложнения математической модели процессов. Конкретно оценивались дисциплины диспетчеризации: по скалярному критерию ранга вершин графа О, по составному критерию ранга и связности

вершины, а также случайный выбор работы из фронта готовы? выполнению работ.

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

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

Корректность метода и точность прогнозировав подтверждена, результатами имитационного моделирования тех процессов, но последнее требует существенно больших времени затрат из-за случайных значений длительности выполнении кажд работы КВР; , к тому же, восстановление функции - распределен времени Т выполнения КВР путем имитационного моделировав представляется практически невозможным. . ■ : - . •

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

Уменьшения числа состояний ОМП имеет целью: • а) более быстрый расчет стохастических оценок време реализации Т „ заданного КВР при незначительном (на едини процентов) увеличении погрешности прогнозирования; . ..

б) расширение спектра . рассматриваемых КВР (включают десятки и сотни работ)' за счет уменьшения числа состояний, которых может находиться ОМП. ' • , ■ • . .. .

Суть метода заключается в следующем. - .. Вершины, графа С(А,Н), который определяет ..заданный КЕ разбиваются по числу вершин на слои (ярусы), число кот9р: определяется числом вершин критического пути в этом графе.

Каждый слой представляет собой множество параллельных раб< которые.могут выполняться на ОП 'одновременно.-. — .............

. Заметим, что разбиение вершин графа по ярусам может быть неоднозначным.

Для математической модели процесса Х(1) это означает;, что пул работ П разбивается по числу слоев на Д пулов, где Д - длина критического пути в графе КВР.

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

• -значение Л может изменяться от 1 до

-/-количество слоев в "в окне просмотра" -может измениться от 1 • до/?; • . •

-Л-номер начального слоя в "окне просмотра";

-А+/-7гНомер конечного слоя в "окне просмотра".

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

Заметим, что при 1~И пояруснос моделирование сводится к прямому стохастическому моделированию выполнения КВР в целом, как это описано в предыдущей главе. • ■ - •

. В пределах каждого "окна просмотра" система функционирует по алгоритму, изложенному в главе 2. . . .

Функционирование СМО . описывается обрывающимся марковским процессом Х$) над ...множеством

состоянийX = {(/и;/*;/«)}• Напомним, что ^.включает номера работ, готовых к выполнению й ожидающих в буфере Б, а ]п включает номера работ, находящихся на. обслуживании в ОП. Однако теперь все работы, которые входят в ¡К, у„ , принадлежат слоям от И. до И+1-1. Это означает, следующее: пока не выполнены

все работы Л-го слоя, не могут вьшолнятьея работы ело последующих за слоем ¡1+1-1. , -...-.-. - г.. .

После выполнения всех работ ¡1-го слоя общее количество слс в "окне просмотра" снова доводится до.;/ (если не исчерпа множество слоев /?) и алгоритм, описанный в главе 2, повторяет) Таким образом; особенность функционирования . СМО заключает здесь в том, что в системе в каждый момент времени могут находа только работы, принадлежащие слоям с текущими номерами от А. ¡1-1-1. . , ...«.- . •■..• ..-Подробное описание алгоритма приводится в диссертации. •:■•... . Точность оценок поярусного -. стохастического: моделирован существенно зависит от того,- как вершины графа О распределены слоям. Исследования, которые были проведены в диссертат

показали, что большую точность результатов прогнозирования путем поярусного стохастического моделирования ' можно' получ* при использовании разработанного автором эвристич^скс алгоритма равномерного распределения вершин (работ) КВР ( графа по ярусам. Этот алгоритм базируется на понятии' степени свобода вершины (работы) о,-, определяемой числом ярусов, в которых моя быть размещена (может-"посетить") вершина о, - при ярус! параллельном представлении графа С. ' ■• ' ' '

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

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

UiropifÎMOJB.

Конкретно автором диссертации разработаны следующие программные модули:

•-модуль задания структуры графа КВР;

-модуль определения состояний обрывающего • марковского процесса при выполнении конкретного КВР;

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

- ' -модуль расчета среднего значения времени выполнения КВР.

Все модули запрограммированы на языке Turbo-Pascal 6.0 и реализованы на ЭВМ PC/AT,

• '' ■•■••"■■. Ч -ВЫВОДЫ. ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕС1ШЕ

РЕЗУЛЬТАТЫ.

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

В частности: '

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

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

При этом рассматриваемый подход позволяет воспользоваться известным методом для определения функции

распределения времени Т. выполнения КВР, .. а определение . эт< функции путем имитационного моделирования , . представляет практически невозможным. . . .. ■- ..

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

3. Прямое стохастическое моделирование позволяет весь; точно (до долей процента) оценивать и сравнивать эффективное самых различных . дисциплин управление ; ..параллельны! вычислительными процессами- критериев диспетчеризации работ К! по процессорам параллельной ВС (при случайном време; выполнения каждой работы)- применительно, к каждому, конкретно! КВР без какого-либо усложнения математической.модели. . - * ■

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

5. Показано, что использование поярусного стохастическо моделирования для графов КВР, имеющих вершины со степеняг свободы с1>], приводит к существенному уменьшению числа состоян процесса. по сравнению с прямым стохастическим моделированием.

При этом погрешность оценки среднего, времени выполнен КВР при поярусном стохастическом моделировании даже при мал< "окне просмотра" {числе анализируемых ярусов ...графа КВР) I-увеличивается лишь на единицы процентов.. •

6. Разработан эвристический. , алгоритм равномерно распределения работ КВР. (вершин графа в) по. ярусам (слоям) учетом числа обслуживающих приборов. Использование . это алгоритма позволяет уменьшить ' неоднозначность ' размещен] вершин .' графа <? по слоям для метода, поярусно стохастического моделирования, а в конечном', счете уменьши погрешность этого метода, приближая его по точное

эогнозирования к прямому стохастическому моделированию и к митационному моделированию выполнения КВР в параллельных ВС.

7. Все разработанные математические модели и алгоритмы ^программированы на языке Turbo-Pascal 6.0 и реализованы на ЭВМ ЗМ РС/АГ.

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

1. Игнатущенко В.В., - Клушин Ю.С. Прогнозирование идалнения сложных программных комплексов на параллельных омпьютерах: прямое стохастическое моделирование // Автоматика и глемеханика. 1994. М2, с. 142-157.

2. Клушин Ю.С. Прогнозирование выполнения сложных ? рограммных комплексов на параллельных компьютерах // Тез. ;окл. Второй Украинской конференции по автоматическому правлению "Автоматика - 95", г. Львов, 1995 г., т. 2, с. 100.

3. Клушин Ю.С. Мегод поярусного стохастического оделирования для прогнозирования сложных программных омплексов на параллельных вычислительных системах // Тез. ^окл. III Международной научно технической конференции контроль и управление в технических системах", г. Винница, 1995 , ч. 1, с. 227-228.

4. Игнатущенко В.В., Клушин Ю.С. Прогнозирование ыполнения сложных программных комплексов на управляющих араллельных компьютерах: точные методы // Научные труды Геждународного симпозиума "Автоматизированные системы правления", г. Тбилиси: изд. "Интеллект", 1996 г., с. 23-28.

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

По работам [1,4],опубликованными в соавторстве, личный ¡слад диссертанта состоит в разработке унифицированного тгоритма определения состояний ОМП, в анализе эффективности етодов диспетчеризации и проведении машинных экспериментов гатематические модели процессов разработаны с соавтором шместно).