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

и%

^ ^ Н Академия Нар СССР

Ордена Легаша Институт ПроблеывУправлекий (Автоматики и Телемеханики)

На правах рукописи УДК 681.324

Маргалиташвили Ашран Александрович о

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ НА ЗАДАННЫХ КОМПЛЕКСАХ ВЗАИМОСВЯЗАННЫХ

РАБОТ

Специальность 05.13.13 - йгаслительные' машины, комплексы,

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

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

Москва 1990

/У/

Работа выполнена в Институте проблей управления (автоматики и телемеханики).

Л»

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

Игнатущенко В.В. Официальные оппоненты: доктор технических наук Бочаров П.П.

кандидат технических наук, с.н.с. Шурайц Ю.Ы.

Ведущая организация - Московский энергетический институт

Защита состоится и_" "с1990 г. в_час.

на заседании специализированного совета Д 002.68.01 Института проблей управления (автоиатики и телемеханики) по адресу: П7342, г. Москва, Профсоизная, 65. Телефон совета: 334-93-29."

С диссертацией можно ознакомится в библиотеке Института проблей управления (автоматики и телемеханики).

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

Ученный секретарь специали- .

зированного совета, доктор технических наук,

профессор ИШЩЕНК0 ,В.В.

иодая ХАРАКТЕРИСТИКА РАБОТУ альность проблеш. В настоящее врем эффективность вГрт|^Яй4>зования ЭВМ и, в частности, параллельных- вычислительных " "сястеи, оценивается нэ столько традиционными параметра»; производительности (скоростьс выпадания: различных операций, их сиесей, типовых вычислительных процедур),, сколько временем выполнения конкретных задач или их наборов.

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

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

Построение достаточно точных фораалыш моделей. наборса взаимосвязанных параллельно-последовательных работ, ассользуе-¡^х в качестве- "рэСочеЛ нагрузки" для формальных моделей

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

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

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

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

Достоверность научных положений, выводов ж практических рекомендацией подтверждена корректным обоснованием а анализом математических моделей рассматриваемых процессов, подтверждаь ЗИШ их результатами шютационных эксперименте«, а также результатами практического использования предлсвениа к

исследованных в диссертации моделей, методов и средств.

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

Практическая реализация. Разработанные и программно реализованные математические модели использовались для оцени? времени выполнения комплексов задач верхнего уровня проектируемой АСУ ТП атомных электростанций и задач управления сложными подвитыми объектами на многопроцессорных вычислительных системах типа ПС-3000.

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

Апробация работы. Основные материалы работы докладывались на Республиканской научно-технической конференции "Вопросы разработки и применения средств вычислительной техники на микропроцессорной базе для АСУ ТП" г. Тбилиси, 1988 г.. на второй Всесоюзной научно-технической конференции "1ивучесть и реконфигурация информационно-вычислительных и управляиза систем", 1988 г., на XI Всесоюзной_ совещания по проблемам управления, г. Ташкент. 1989 г.

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

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

д -

ЕСЩШШИЕ РАБОТЫ

Во_ Вдегаш зййсношвается актуальность ;и формулируется цель диссертационной'работы.

В первой главе привадится обзор научая фябот и на основе их анализа ставятся задачи диссертациошого .исследования.

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

Заданный програмный комплекс задач, который требуется выполнить на параллельной ВС, представляется в виде простого ориентированного графа G(A,D с конечным числом N вершин, где вершина а;А соответствует 1-й задаче < 1=1,2,...,!! ), в дальнейшем называемой работой, а множество Г дуг отображает информационно-логическую зависимость между работами(задачами). Граф G может иметь только одну входную и только одну выходную висячие дуги, соотвествущие "начальной" и "конечной" вершинам в графе программы; последние могут соответствовал функционированию операционной системы ВС по инициации и завершению кодекса задач.

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

Готовые к выполнении работы образует фронт работ F: если работе представлен процессор, то она исключается ira F.

Работа а считается работой - предшественником по отноое-нив к at, если имеется дуга (a. ,аа ) € Г; в эти* случае а,является работой - преемником по отнотешв к . Каждая работа а считается готовоЗ к вшшенав, если выполнены все ее работы - предЕЭстзэнвяки (т.е. вначале граф считается детершнирован-щц, без логических ветвленннй а цшсяоз на уровне работ).

Счнтгатся.что выполнение работы на процессоре завервается событием А , беля во фронт ? соступает v работ. Если на работе а сннхронззаруются несколько работ,то лиаь одна из шх ыогет завершиться событзем At, а остальные- событием А0,есдя не нпн-цянрувт других работ. Сказанное означает,что даже в днтергша-ровашш графе 'орограгаы без логических ветвлений н циклов на уровне работ,с априорно известным количеством предшественников а преемников каядой верошш,число работ i ,поступащп в F после завершения данной работы, козет являться случайной величиной . Для определенности и уиеньшешя разиарностн рассматриваемых «юделей вводится следущее ограничение : число работ-лре-енншеов лйоЗ ргботы а. не преийзэт трах.

Событиям А. приписывается вероятности ах появления а , аиегцае смысл параметров параллелизма грзф-т nporpcmi ; проще всего значення а исзно определить по формула :

Л, ___ . 3

\ =у î 1 = 0Î3; > = 5 Е - is (I)

где значение И. вырезает число тех вергш графа, котор&е завершаются событием к , в - общее число событий в графе G. Отмечается, что подсчет значений а. по формуле (I) является грубш в той сиысле, что не учитывает возысшнх (н упоаянутнх выше) несоответствий ыезду чнелоа преемников данкоЗ ргботы а чнелон работ, зшщйяруешх в ? после ез звверпешя.

Очевидно, что : 0-c^+i »о^ +2-a2-КЗ =1 ; показало, что а0 < 2аг * Заз; ао> а2+ aj9 откуда следует, что as< 1/3 ,

а < 1/2, а + а < 1/2 .

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

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

В связи с этим введен новый параметр комплекса работ к графа в - обобщенный коэффициент параллелизма: а = Н / Ик, где К - общее число вершин в графе С, а — число вершн (длина) его критического пути.

Очевидно, что а*> 1. Этот коэффициент мохкз представить и в следующем виде: а* = 1 + ) / Н., .Числитель во втором слагаемом выражения соответствует числу работ в графе й, которые могут выполнятся параллельно с работами критического пути.

Для более детального анализа влияния критического пути графа С на время выполнения заданного комплекса работ предлагается разделить множество событий ' {А > на два подмножества: {А }, соответствующее событиям до завершение работ, которые могут выполняться параллельно с работами ЮТ; {Ак1}, соответствующее событиям по завершению работ критического пути. Тем самый вводятся параметры параллелизма а и а для критотеского пути и подграфа Сг работ, параллельных, пс отношению к работал КП. Для этого аз графа 0 исключаются работы критического пути, а в оставшейся часпРграфа (которая и является подграфом С^) число событий А„. подсчитывается без учета событий, порождаемых работами КП для работ подграфа Сг.

Формулы для подсчета параметров параллелизма \ и \ принимают следующий вид:

хр кр

где М_ -соответствует количеству тех работ в подграфе Сп, которые завершаются событием -соответствует количеству

тех работ в критическом пути,которые завершаются событием Ау .

Если использовать нормировку параметров а^ н а. по длине критического пути, то установливвется очевидное соотношение между этими параметрами и обобщенным коэффициентом параллелизма а* графа Б:

«Шкр>.(0о ^ 41- ^ ♦ 3. ?£р) + нжр.(о. ^ +

с^ я г а, М 2Мяг ЗМ„э

+1, пй + 2' + 3' нг?) = иг?11 ' 1ВД та! +

Ль Л..2*».3*.», У^^А1*3^,^ н

^''Нкг'Н;:;. 'Нкр ' = -Ш,-= Жр" й '

Замечание 1. Для математической модели функционирования

МВК рассматриваемой в главе 3, будет использоваться следующая интерпретация событий А .наступанздх по завершению работ критического пути : •если работа КИ имеет q преемников среда работ подграфа С. (очевидно, а <1), то соответствующее ей событие А. интерпретируется как два' события- А* для инициации работ, относящихся подграфу Са,н для работ КП.

Это означает, что по заверщении каждой работы КП цщцщру-ется q работ, относящихся к граф" С^, с вероятностью а 1. Т.е. с вероятностью ао=ако+а..1 из подграфа будет инициировано 0 работ, с вероятностью а. =а {г- одна работа, и с вероятностью а =а - три работы. Вырагение (3) примет следующий вид:

з, „ а а а а

. тё 41. 2. + з. 4Н„.(0. %г +

т, а. 1Н1 а га за н +н ы

1&2* зёИнг? Чгай

♦пгг }--яг?---Пкр =

Иеаду а в существует следущая завзспкоэтъ:

* "Н---н--г: ' Г~ ТГ^' НЕр" 1Г ак> + тг"Ч.;

** - В .целой, параметры а ,а ,аП1.а^ представляют собой совокупность оценок параметров параллелизма графаС,различных по .сложности подсчета и точности, с использованием которых в главе 3 будут исследоваться различные - по точности и результатам математические модели функционирования МВК на заданном комплексе работ (соответствием графу Б).

Ранее предполагалось, что каждая работа может быть готова к выполнению после завершения обязательно всех работ-предшественников . Наличие же логических ветвлений между работами означает,во-первых,4то работа может быть включена во фронт ? после завершения не всех,а только части работ предшественников, а во-вторых - предполагает наличие альтернативных работ-преемников. Это соответствует включение в граф С элементов "ШШ -слияние" и "ИЛИ - разветвление", наряду с элементами "последо-' вательная цепочка", "И - разветвление и "И - слияние".

Появление логических ветвлений на уровне работ в графе & приводит к разделению его на множество подграфов К» с >,— таких, что при каздом выполнении комплекса работ реально будет выполняться только одна из версий комплекса, соответствующая одному из подграфов Слсг. Любой из подграфов Слог обязательно содержит "начальную"- и "конечную" варшиш графа С и не содержит логических ветвлений на уровне работ. Подграфы Слс, иогвт пересекаться, т.е. содержать общие варшны, вклотая "начальную" и "конечную" вершны графа й.

Для определения параметров Н,Н ,а\с1 ,ат ,а]£1 графа С с логическими ветвлениями на уровне работ а последующей оценки времени выполнения соогватствувдего еду 1 коавяякса работ предлагается два подхода.

Первый подход базируется на осреднении этих параметров по всей К подграфам С. ,графа С: к »

где Р, - вероятность выполнения I - го подграфа С.пг.

Другой подход направлен на определение "лучших" и "худших" из подграфов сеточки зрения времени выполнения соответствующих им версий комплекса работ на основе значений их параметров Н, ,!!.._, ,а , , ,. . Этот подход представ-

ляется целесообразным для исследования функционирования особенно управляющих МВК на задание« комплексе задач, ибо позволяет оценить наилучшее(минимальное) и наихудшее (максимальное) время реакции МВК в контуре управления. Принципиально важно, что при Таком подходе не требуется определения вероятностей альтернативных передач управления,а оценка наименьшего и наибольшего времени реакции МВК нозет быть полностью осуществлена на основе графовой модели заданного комплекса работ а математических моделей функционирования 13БК, рассматриваемых в гл.З.

Для того, чтобы корректно осуществлять селекцию "лучшее" л "худших" подграфов _, а в конечном счете - оценить минимальное и максимальное время выполнения работ графам с логическими ветвлениями,необходимо оценить меру влияния каждого из следующих параметров на вреня выполнения работ подграфа : количество Н. вершин подграфа, количество Яг ь вершин в КП подграфа, параметры парадгешзаа подграфа а", а , ,а.г. .а^. и чгсдо я сбслугЕваяза приборов (процессоров-МБК) .

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

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

Отметим, что подграф может содержать любые из рассмотренных выше- элементов: последовательные цепочки, разветвления и слияния типов И и ИЛИ.

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

Для исследования процесса выполнения комплекса работ (задач) предлагается математическая модель функционирования параллельных вычислительных ресурсов МВК в виде однофазной системы массового обслуживания без потерь, состоящей из п=2 одинаковых обслуживании приборов ОП и 0Пг(процессоров МВК}, с конечным набором (пулом) из N работ,и из буфера на г=Я мест, в котором формируется очередь готовых к выполнению работ - текущий фронт 1. Система функционирует в дискретном времени.

В систему поступает ^начальная* работа заданного комплекса, которая немедленно передается на выполнение в любой из 011. Предполагается, что время выполнения каждой работы в ОП является случайной величиной и распределено по геометрическому закону. В работе обосновывается выбор такого распределения.

Обслуживание < заявки на ОП завершается событием . А с вероятностью а , 0 5 I < 3, т.е. ц буфер из пула поступает с новых заявок, а обслуженная заявка покидает систему.

Текущее количество заявок, находящихся в системе (вне пула работ), определяется суммой числа заявок в буфере и не обслуживащих приборах.

Функционирование рассматриваемой СМО можно описать регулярной цепью Маркова по моментам г>Ь, V >0, над следующим пространство! состояний:

0 X Н И.а) : 1=СВивж! } , где

1-число заявок в системе, а ъ -число заявок в пуле.

Состояние х[1,зЗ соответствует случаю, когда в системе находится 1 заявок, а в пуле — г заявок. >та)(

Общее число состояний системы равно 5 = £ (N+1-141/23), где Ктах- максимально возможное число заявок11°системе.

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

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

Предложенная базовая математическая» модель позволяет исследовать функционирование- МВК 'на задание« комплексе взаимосвязанных работ при различных версиях выполнения ксашлекса и различных поведениях вычислительных ресурсов МВК, в частности: -принципиально на базовой модели ногат быть исследовано поведение любой из версия комплекса работ. Однако с точки зрения интересупиегп нас критерия качества - времени выполнения комплекса работ - предоставляется возможность исследовать функционирование МШ на "наилучших" и "наихудах" подграфах, чтобы получить оцеЕШ наименьшего я наибольшего временя выполнения заданного комплекса работ в целом;

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

быть вычислено среднее время выполнения набора "критически процессов";

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

Для учета влияния КП на время выполнения заданного комплекса работ предлагается другая математическая модель функционирования МВК. Рассматривается однофазная система массового обслуживания без потерь, состоящая из 2-х одинаковых обслуживающих приборов ОП' и 0Пг, из двух конечных пулов работ 1 и 2, в одном из которых изначально содержится N _ работ КП графа, а в другом М-И.„ работ, которые могут выполняться параллельно с работами критического пути, а также из буфера на г = II мест. Система функционирует также в дискретном времени.

¿Начальная* работа поступает в систему из пула. 1 работ КП и немедленно передается на выполнение в ОП . Время выполнения каадой работы в ОП является как й ранее, случайной величиной, распределенной по геометрическому закону с параметром Ь.

Выполнение "начальной" работы на ОП завершается инициацией 1 работ с вероятностью ¡\ , вычисляемой по (2), причем одна работа обязательно "вызывается" из пуле 1 работ КП, в 1-1 работ - из пула 2. Работа, инициируемая из пуле 1,поступает на обслуживание в ОП ,по завершении ее выполнения с вероятностью а снова инициируется очередная работа из КП на ОП и 1-1 работ - яз пула 2 и т.д.,- вплоть до исчерпания работ в пуле 1. Это означает, что до опустошения пула 1 имеет место а * 0.

Выполнение работ из пуда 2 на ОП. завершается событиями Лп. с вероятностями.а./, вычисленными по (2). 0

Текущее количество заявок, находящиеся в системе, определяется суммой числа заявок в буфере в на обслуживании в обоих

ОП. Максимальное число I? заявок, которые могут находиться в в»-"

системе при I =3, может достигать величины (1М1 ) г 2.

-

Функционирование рассматриваемой СМО можно описать регулярной цепью Маркова, по моментам b'h, v > 0, над следущиы пространством состояний: 1 = , з, ]: l=ü^„a, ; z 4НГ7ЛЗ; s, ^ГТО }, где

1 -числе заявок в системе, ъ_ -число заявок в пуле 2. ъ -число заявок в пуле 1.

Состояние x[l,z ,z ) соответствует случаю, когла в системе находится 1 заявок, в пуле 2 - з заявок, а в пуле 1 -з-1 заявок.

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

Учитывая структуру второй математической модели и весьма существенную роль параметра Н на время выполнения заданного комплекса работ, предлагается ввести "детерминированность" в обслуживании работ КП в точном соответствии с событиями,порождаемыми этими работам/: выполнению любой работа а КП ставится в соответствие не генерация работ с вероятностью > , а событие А , однозначно определяемое по структуре графе G.

В диссертационной работе анализируются погрешности этих математических моделей по сравнению с имитационными экспериментами. В частности,для рассмотренных в работе конкретных графов погрешность результатов базовой математической модели составила от 4 до 24?, погрешность математической модели с учетом критического пути - от I до 10£, а погрешность "детерминированной" модели - от I до 65;.

Из приведенных в диссертационной работе расчетных и зхпг -риментальных данных делаются следупцие вывода о зависимости времени выполнения любого заданного комплекса взаимосвязанных рз'от от рассматриваемых гнэкиегров шшексэ и снстнда c*V: = лужиБэная-И,!.' > , , - .i. ,п): производительность МШ. кивземая через асемя 5ЫЯ0ЛНвщ(Я заданного кощу-аксз рз£от,

является не только функцией числа N выполнявши работ и пропускной способности вычислительных ресурсов, но и функцией параметров каждого конкретного комплекса работ - его КП и па-„'аметпов параллелизма. Предложенные математические модели тозйсляют оценить меру взаимного влияния всех этих параметров ;-:з Т количественно, без восстановления зависимости функции Тх от каздого из указанных параметров в явном виде. Тем не менее возможна содержательная трактовка некоторых из этих зависимостей. I. Влияние количества работ N.

Увеличение обшего-числа N работ в комплексе приводит к практически пропорциональному увеличении времени его выполнения Т ,но значение коэффициента пропорциональности существенно зависит от значений а . Например, увелотение N в 1.5 раза вызывает увеличение Т от 35.7 % (для п=2) и 402 (для п=3) при максимально возможных значениях параметров параллелизма ) и до 502 - при а_ , .

2. Влияние длины критического пути N...

Представляется 'очевидным, что при N .>N/2 время

ьыполнения Т_ всего комплекса работ определяется, в основном, суммарным временем вшолнения работ критического пути даже при п=2 (не говоря уже о больших значениях числа обслукиващих приборов II). Отмечается, что чем больше значение Н при некотором фиксированном N. тем выше точность оценки времени Т выполнения комплекса взаимосвязаннчх работ.

3. Влияние параметров параллелизма.

Время выполнения комплекса взаимосвязанных работ может быть уменьшено, за счет их параллелизма, максимально на 40% при п=2, и на 57?! при п=3 (при максимально возможных значениях •ч , указанных выше), по сравнению с выполнением этого же комплекса работ на одном обслуживанием приборе.

Конкретные же значения уменьшения времени "выполнения комплекса взаимосвязанных работ с конкретными значениями параметров параллелизма может быть оценено только расчетом

предложенных математических моделей.

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

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

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

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

Исследование влияния длины очереди заявок, которые могут обслуживаться нз разных вычислителях, но с различной интенсивностью, проводится на основе базовой математической модели подсистемы обработки ИНК,состоящей из одного устройство управления-?^ двух специализированных вычислителей СВН скалярного )

-loti CB2 (векторного), и из буфера иежду 71 и спецвычнслителями.

В этой модели УУ считывает команда из оперативной памяти, деяифрирует н, формирует адреса и считывает операнды из занята. Готовые к выполнению заявки 1-го типа (скалярные) и 2-го типа (векторные) помещаются в буфер, а затем распределяются по спецвычислителям СВ1 и СВ2, причем в СВ1 поступает на выпоякйкс заявки 1-го типа, а в СВ2 - второго типа. Если требуемый для данной заявки вычислитель занят, то заявка помещается в общий буфе? глубиной на R мест.Заявка 2-го типа (векторного) имеет право поступить на выполнение и в скалярный вычислитель СВ1 в тем случае, если СВ1 свободен, в буфере отсутствуют заявки 1-го типа, а количество заявок 2-го типа в очереди стало больше некоторого порога К. Однако заявки 2-го типа обслуживаются на СВ1 медленнее,чем на "своем" СВ2.Для определенности принимается, что СВ1 - это общий вычислитель, который может выполнять как заявки 1-го, так и 2-го типа, а СВ2 - это спецвычислитель, выполняющий заявки только 2-го типа. Обслуженные заявки покидают систему. В случае заполнения буфера, УУ прекращает генерацию заявок(блокируется) до появления в буфере хо-л бы одного свободного места.Система функционирует в дискретном времени. Время обслуживания заявки принимается распределенным по геометрическому закону.

Функционирование рассмотриваемой СМО можно списать регулярной цепью мэркова Ev, ;->0, по моментам nh, над следущиы пространстве» состояний :

X = .{ I n,n,i,j ): n=S7R; m=öTE; где

n - количество заявок 1-го типа в буфере; m - количество заявок 2-го типа в буфере (n+ß=ÖTR): 1 - индекс состояний СВ1: 1=0 - СВ1 свободен. 1=1 - СВ1 обслуживает заявку 1-го типа, 1=2-СВ1 обслуживает заявку 2-го типа; j - ннлекс состояния СВ2: j=0 - СВ2 свободен, 3=1 - СВ2 работает (обслуживает *свов* заявку).

Общее число состояний равно: S - (R+2)(R+3) + К..

. -1Ï--

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

Сравнивались две практически целесообразные дисциплины управления заявками: I) заявки 2-го типа вообще не поступают на- CBI (что соответствует строгой специализации вычислителей на выполнение только "своих", соответствующих им заявок), и 2) заявки 2-го типа направляют на CBI, если их количество б очереди не меньше К- (OiR<R). Результаты исследования модели привели к следущш основным практическим выводом:

й!бор той или иной дисциплины диспетчеризации заявок 2-го типа может быть осуществлен только при известных статистических параметрах заявок и системы в целом, но при этих уело--видх эффект от правильного выбора дисциплины диспетчеризации ко®>т достигать десятков процентов.

В реальных многопроцессорных и вычислительных комплексах передача работ с вычислительных ресурсов одного типа на другой зачастую требует участия операционной система (ОС), что вносит дополи::-ельвые временные затраты на время выполнения задачи в целом. Такие "накладные расходы" на организацию взаимозависимых вычислительных процессов практически неизбежны в многом?-ианннх комплексах, состоящих из "центральной" машины и специализированной ЭВУ.

Для исследования влияния указанных'"накладных расходов" на выбор дисциплины диспетчеризации работ по двум обслуживающим приборам различного назначения* предлагается другая математическая модель. Отличие данной модели от базовой заключается во введении дополнительного обслуживающего прибора в СВ2.Поэтому обслуживание заявки 2-го типа спецвычкслителем СВ2 рассматривается как эрлакговское второго порядка, т.е. СВ2 можно представить в виде двухфазной СШ с отсутствием буфера между фазана. Обслуживание на первой фазе соответствует работе ОС ("накладам рзеходаа"), на второй фазе происходит собственно обслу-

«ивание заявки. Для упрощения анализа принимается, что Система

функционирует в непрерывном времени.

Пространством состояний марковского процесса, описывающего фунционирование данной ОЮ, является

2= { (n.m.i,J): CbnsR, Chm^R-n, 0*i.v2, 0iji2 } , где а - количество заявок 1-го типа в буфере; m - количество заявок 2-го типа в буфере in+nt=(J7R); i - индекс состояний СВ1: 1=0 - СВ1 свободен, i=i - СВ1 обслуживает заявку 1-го типа, 1=2-СВ1 обслуживает заявку 2-го типа; j - индекс состояния СВ2: 3=0 -СВ2 свободен, J=l- обслуживание ' заявки 2-го типа на первой фазе СВ2, J=2- обслуживание заявки 2-го типа на второй фазе СВ2.

Для исследования подели функционирования МВК с "накладными расходами" используется следующий критерий, по которому иохно судить oö эффективности той или иной дисциплины диспетчеризации: время пребыьания заявки в системе. Зга стационарная характеристика систем, как известно из теории СлЮ, является наиболее подходяией для исследования системы рассматриваемого тина, поскольку минимизация времени пребывания заявки в системе .'включающего время ее ожидания и время выполнения) призодат к более быстрому обслуживанию задачи в целом.

Цель исследования данной модели формулируется следующим образом: при каких значениях параметров системы целесообразно использование первой дисциплины управления заявками 2-го типа (К=К> или второй дисциплины (К=0).

Конкретно исследование в этом разделе направлено на выбор дисциплины диспетчеризации работ в иногоиашнных комплексах ЯС-3000/БС-2000, в которых фрагменты задач, состоящие в основной из скалярных вычислений, обрабатываются на УВК ПС-3000, выполняшем функции ведущей, центральной ЗШ, а векторно-нат-рачная обработка больших массивов инфорыацш эффективнее выполняется нэ UBK ПС-2000, ориентарованнш на групповую обработку акфоршцни. Для выполнения задания на ПС-2000 требуется

- г? -

включение ОС для подготовки, пересылки и приема пакета сообщений через канал ввода-вывода между ПС-3000 и ПС-2000.

Смысл исследования модели, рассматриваемой в данном разделе, заключается в поиске ответа на следущий вопрос: если для некоторой задачи известны соотношения скалярных и векторных Фрагментов или возможные граничные значения этих соотношений, если известны возможные размерности массивов, подлежала« групповой обработке, то какая из дисциплин диспетчеризации(К=Н или К=0) обеспечивает большую пропускную способность система при заданном или изыег"ннои среднем времени работы ОС по установлению связей между "центральной* и "ведомой" ЗШ ?.

На основе результатов расчетов модели делается едадушгё вывод для практического использования дисциплин диспетчеризации работ в неоднородных вычислительных комплексах: векторные Фрагменты налой размерности следует обрабатывать обвил вычислителем (СВ1), не теряя время на подготпку работы в СВ2. Размерности векторов, при которых их следует направлять на общий вычислительный ресурс, зависят от загрузки общего вычислительного ресурса и соотношения числа заявок 1-го и 2-го тиля во входном потоке. Поэтому для управления заявками требуется знать значения этих параметров.

ВЫВОДЫ, ТЕОРЕТИЧЕСКИЕ «'ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТУ

I.Разработана базовая графовая модель заданного комплекса взаимосвязанных работ <задач или их параллельно-последователь-шх Фрагментов), со случайным временем выполнения каждой работы, введено понятие параметров параллелизма комплекса работ и соотБбтствугоёго ¿«7 графа, разработаны формальные правила определения этих параметров для каждого конкретного комплекса.

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

3. Разработана графовая модель комплекса работ с логическими ветвлениями и циклами (на уровне работ), модифицированы правила определения параметров параллелизма такого комплекса.

4.Разработана базовая нестационарная математическая модель функционирования вычислительных ресурсов МБК в виде одноФазной системы массового обслуживания, позволялся оценить время выполнения комплексов взаимосвязанных работ (задач) с учетом количества работ в заданном комплексе, параметров их параллелизма и объема вычислительных ресурсов.

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

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

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

8. Разработана базовая математическая модель неоднородной вычислительной системы для оценки "границ целесообразности" применения предложенных дисциплин диспетчеризации.

9. Разработана математическая модель функционирования ногомашинного вычислительного комплекса с учетом временны! отерь ("накладных расходов") сна организации взаимодействия центральной" ЭВМ и специализированной ЭБМ(например,векторной) ля анализа эффекта диспетчеризации разнотипных работ по обеим ЕМ комплекса.

10. Аналитически показано, что выбор той или иной ;исцшшны диспетчеризации разнотипных работ мояет быть сутцествлен только при .известных статистических параметрах абот и их» обслуживания на различных ресурсах МВК; при этих словиях эффект от правильного выбора дисциплины испетчеризации (по критерию пропускной способности системы) озет достигать десятков процентов.

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

1. Борисенко В.М., -Аыбарцумян A.A., Маргалиташвили A.A.. рейдунов 'Ю.В. Аналитические оценки эффективности диспетчери-ации параллельных работ -в .многопроцессорных вычислггелышх истемах. // Деп. ВИНИТИ. -3375-В88.

2. Маргалиташвили АЛ. О жиянзи'отказов на эффективную роизводительность резервирована^ ьшяшроцассорных систем //

кн.: "Вопросы разработки-и применения средств -вычислительной ехшки на микропроцессорной базе для АСУ ЛТГ. Тезисы докл. еспубликанской научно-технической конференции. Тбилиси. 1988.

3. Маргалиташвили A.A., Аибарцумян A.A., Тепляков A.B., рейдунов Ю.В. ГрафоЕне модели комплексов взаимосвязанных абот. // Деп. ВИНИТИ• £587-BSQ.

4. йгнатущенко В.В., Маргалиташвили A.A. »йатематические одели анализа вивучести параллельных вычислительных яоыплек-ов. //В кн.:"1нвучесть и реконфэтурацяя шгфорцацйонно-вычис-ительннх и управляпш систем". Тезиса докладов.Второй Всесо-зкой научно-технической конфереящщ. Кши. 1988.

*

5. Игнатущенко В.В., Мзргалиташвили A.A., Тепляков A.B. 'Матемавпеские модели для анализа отказоустойчивости и0 живучести параллельных вычислительных систем в контурах АСУ П Тезисы докл. XI Всесоюзного совещания по проблемам управления. Ташкент. 1989.

6. Маргадиташвили А А. Анализ эффективности диспетчеризации параллельных работ для неоднородных многопроцессорных комплексов. // Сообщения АН ГССР. 134, Л2, май, 1989 г.

7. Маргалиташвили A.A. Математические модели для оценки времени выполнения комплексов взаимосвязанных работ. II Деп. ВИНИТИ. ÄI646-BS0.

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

По работам, опубликованным в соавторстве, личный вклад диссертанта состоит в следующем: в [I] предложены и аналитически оценены эффективность диспетчеризации параллельных работ ка МВК; в 131 разработаны графовые модели с логическими ветвлениями и циклами; в (4) и [5] разработаны и исследованы различные (по сложности и точности) математические модели для анализа живучести параллельных вычислительных систем.