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

РГ8 ОД

Московски! о^денз Ленина, ордена Октябрьской револвдша ] 1\ 1110 На ордера Трудового Красного Знаиени государственный технический университет им Н.Э. Баумана

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

Марков Аркадий Алексеевич

УЖ 681.3

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

05.13.13 Вычисли-» илыпш наиьпш, комплексы, системы я сити.

Автореферат диссертация ня coi исашв ученой степени докторе технических наук

МОСКВА. 1993 г.

РаОота выполнена в Московском государственном технической ушшэрсигете им Н.Э. Баумана

Официальные оппонента: доктор техкичягких нпук, _прпфяг.опр Спирит,ей А.Я

доктор ТЯХМУТОРГКУ1Г Hnyif,

__nppfecxop Плоткин А. Л.

доктор технических няук. _просЕпгсопр.Цпшв Ю.А_____

Ведущая организация: НИИ "ВОСХОД"_

&8ЩИТЭ состоится " 1993 г. в чес. на

заседании специализированного совета Д053.15.03 при Московском государственном техническом университете по адресу: 1СГ7005. Москва, 2-я Бауманская ул. д. 5.тел.:___

С диссертацией можно ознакомиться в библиотеке ЫГТУ. Просим принять участие в работе совета ала прислать отзыв в одном акзедалярэ, заворвтшй печатью организации.

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

Учаннй секретарь ^

споциализированного совета С.Р. Иванов

0Щ4Я ЗШУ1£!ГЕШСТШ{А РАБОТЫ

Актуальность так?!. В середине) СС'х годов олохне'лтгйсл исо-шрхшй оборот средств индустрии обработай давних составлял около Со.' процэхпот й стоимости программного обоспочотгя и 15 процентов п стоя?«®«!. ¿шгар^гури. 3 годах • удольшй вес стоимости аппаратур! продолжал сшкзться, н; кроме того, ясно впялилась . тенденция к снажопш стойкости .единицы прироста производительной',-',1 аппаратура л-пошиошт стоимости абсолютной вдипицн производительности программ. ' Диссертационная работа тосвяз.эна проблемам-, оф|бктшзяостй использования программами ресурсов вычисли-5олыяЬс-.Ьзстом.' '

■ Проблема одвшга.аффокгтапости фущадонировашя является одной из'' наиболее вгкянх - в 'теории вычислительных' систем. Наиболее значимо--проЛйём9 эффективности' проявляется в новэйик высока-скароста системах, к числу которых относятся: сйстзга'реального врешш, - систзш мулъта - медиа, распрэдодэщшэ' комшлоггорпно спстом< с параллельной : и ■ ксгардааировапяоЛ обработкой, транс-пьэторвце-системы4 сиетёш о водок евро - оптической связью 'я оптозлектроншо Еоьшьэтарц»

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

.Область примоайшя результатов анализа эффективности и про-, йЗЕОдктэльшста йрогракч достаточно трока, вга • результаты щ&тшяся почти взздо, гдо применятся программы, з болею текло 4. -' паздв, - • где последствия неправильных реаоига' ощутимо, скозиваится йа • з^фйоттости. В ■ первую очередь это относится к систа?шм аро?рзг.мам, в некоторых,случаях, прикладное програшисе . ОбаСЕёчйзне ча-ой тробуот проверки а временной сшцифпсещщ. Анализ произкдаиольуости подобамх- программ особенно необходим. Часто при прооктирова!шя структур , прогремт-гаого обеспечения всэшшавт дти^аШ^в.задёод.

Ораауа- рЬлья хфовэдоАЯТОльшети играет в спецшзжз^ввашн ьптматольшя .коглшщеэх и системах реального вррнэпя. Прогрвтт'я .рэзлиэеция алгоритмов треоувт щшдвчовж шоГиК ресурсов ЭВД, Важнейшим" ресурсом является

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

Принципиальную важность эта оценке имам такх» для систем сального времена.

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

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

Широкий класс приложений можно найти практически в любой-области теории: вычислительных.систем. '

Разрабатываемая в диссертации проблема: направлена на решение актуальной научной задачи, имеющей паяное народао -хозяйственное значение, и тесно связана с аланом научных работ МГТУ им Н.Э. Баумана

Теоретические вопросы и программные системы, вклотающне в себя внадютическиэ, имитационные я оптимизационные • модели разрабатывались автором лично я при его непосредственном участии в рамках госбвдветвых и хоздоговорных НИР, в работах, проводившихся по постановлениям Правительства, по "Координационно;,(у . плану научяо-исследова^льских работ вузов в области вычислительной техники" на 1981-1985 и 1986-1940 гг., а также ' в соответствии с программой №шв"за СССР "Автоматизация научных исследований" на 1986 - 1990 гг.

Цалын работы является создание н рсзребо-пг ппучнш: ссиоп построения форм&пышх методов повышения зффоктшщости фушедаони-роп.-.^л ярооктируошлс И МОДОрШ13Иру8М£К биСТрС'ДЭЙСТВУШЛХ вычислит вяьвих актом на оснопэ одяногэ мэ то доле гич о с кого подхода.

йгше/ч аспектом исследования является формирование и разработка на основании сбоЗгдтшл предшествующих исслэдовепиа систематических рогуляршх методов для решения задач ашишза производи-таяьпости и эффективного построения структур процессов обработки информации.

На звшгу в'мюевтея следунцие далояеияя:

- основные концепции а метода формального подходе к клас-яфшецяи процэссов в ВО па основа выделения в процессах вероятностно - логических структур;

- вероятностные модели схем (операторов) структурного прог-зошарованяя я лрааола тошозиции структур для поиска обобщенного эешния;

- схода неструктурного взаимодействия программ па основа:

— вероятностных моделей пароходов с зависимостью от маршрутов► порядка сбре*отки, вясаеишсти и цякяячномгн повторалиЯ,

— вэроятлостпых схем взэимэдвйсшш парадпальпо - ис-ПОЛШЗШЕ процессов'*

' — вероятностных схем процессов общего вида с циклами, шро!србсишш ссылками» взаииодойствущшя! параллельными угасткаш, а такта прямоЯ я косвэнпоЯ рекурсией;

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

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

Натодн теорвтачоекпх исследований.

- з -

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

Научная доятаяиа •работа.

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

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

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

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

осю-бщошш.

Практическая значимость работы.

Практическая значимость работы определяется классом задач для которых могут использоваться ее результаты. Задач:*, к которым прйяогвма теория ВЯС относятся к классу задач метрической теории * внчяслктелыгах систем п служат для оценки архитектурных ре ¡лепит. в ЭВМ, комплексах сетях к системах.

Прэктичоста работа дапрэвлэнэ на выявление уз гас мест, проггозировгнпэ повзлогщя яцпйксоз производительности, сравнение розультатбв сдактурных решений, переструктурировакие процессов с дельи пой!®аш1Я Бйэ-тгашсти исполнения в конкретной программно - аппаратной сраде. .

. Теоретические', результаты,- .полученные в работа, касаются вопросов зффэктшкого построения внутренней структуры процессов обработки . ш1фор,!адап, при 'таком' подхода, зффзх-сткзнссть рассматривается с точи! зрзяш исйолыяэшго процесса. Это -- та область теория вычислительных систем, к которой относятся работе соискателя.

Тоорэтическиэ результата н программные срэдетва нашли врмэнениэ в практике проектирования п научных исследований в ряде предприятий ("Пакет прикладных программ для интерактивного шделпровашя инЗ^рмацаоншз процессов" подучил первую премии Безсоюзного конкурса на лучшие разработки в облаете Автоматизированных Спетом для научных исследований).

Структурно работа состоит из Введения, 7 глав. Заключения и 4 приложений. Первые две главы относятся к обзору состояния проЗлэмц я формулировке зада'" исследования. Полная формулировка задача дается в копцэ второй главы, после того как сделана все яообходяшэ определения и очерчен круг нерешенных проблем.

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

Енвдрешв и практические исследования выполнялись по планам ааучво исследовательских работ кафе/фи ЭВМ я систем МРТУ им. Н.Э. Баумана, а такав самостоятельно автором при работе пад монографией "Натоматичоскка метода оценки дефективности и

производительности программ". Практические результаты в виде котодик и программных систем, разработащшх автором и нод руководством автора, при его непосредственном участии, внедрена в НЙИАА, НЙИСА, ЕРШЙАСУ» ЕРШИШ, ЕРНШСС,

Результаты работ использованы ряде учабго« курсов d ЫГТУ.

Адпробадая работа. Осаовднэ теоретические положения и практические результаты обсуждались за 7 всесоюзных н республиканских научно - технических конференциях.

Публикации!. Основные положения работы опу&шковашт 22 работах*, включая 2 учебных пособия и I монографтг (в' печати); а также в научно - технических отчетах»

Объем работы. Содержание изложено, на 3ii страницах машинописного текста, содоржот 76 рисунков и таблиц; ссдорэяат список литературы из 144 наименований и приложения. .

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

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

Задачи анализа

Время.

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

1»*)»РгП<нЗ.

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

явного перечисления небольшого количества маршрутов и задержках, извэсганх для квздого узла алгоритма, рзо^еделопие времени, исполнения будет имзтъ вид:

Т(х)«У^т11'го1»^ ^ Ы11{)< * J

где а ,т .'...л^...т - вероятность выбора маршрута М^, а N количество маршрутов, - задержки в ^ узлах на маршруте. Рэшепио задачи основано на поведении случайных сумм случайных величин.

Память.

Реализация многих программ, особэнно в системах с ограничениями па память, весьма критична по времени к удовлетворении запросов на выделение памяти. Запросы нз память обрабатываются с некоторой задержкой» связанной с работой программ распроделзния памяти и ожиданиями, связанными с освобождением другие: программами или собственным программным модулем трзбузмого объема намята. Зероятиостная структура процесса вычислений приводит' к появлений случайного числе запросов из память как по их числу, тек я по суммарному требуемо^ сбъоау. "а;аы образом в некоторый шОрзшшй момент временя юн в некоторой звдаь .ой точке аягорвияа, арогражз моют имзи» в общ;ам случае распределенный произвольным образом объем занияазшй памяти; *

Оценка вероятностных характеристик используемой неияти во многом, схожа с оценкой времена реализации;*

УСх)= УтРгоЬГ я 1

Основное отличие заключаэтея в то?.«, что отдельные слагаемые могут входить в выражения типа (и не только со знаком *+"„ но и имея отрНцзгаяьнов знэ»бни&, В то згэ врвш общй объем памяти, вгнздаешй нрогредаой газгеот о* тэкуг^вто распределения памяти, поэтому в задачах оценка объема стяги дата бодав пироко использоваться устзнда распределения, и большее внимание должно

уделяться особенностям структуры алгоритма.

Запроси н потребление ресурсов.

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

Метода решения этих трех задач должны быть основаны на достаточно общих вероятностных предположениях, систематизированы и формализованы.

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

Формирование подхода к исследованию проводится на основе базового понятия структуры процесса.

Во второй главе формально определяются вероятностно логические структуры ГВЛС) и формулируется задача анализа процессов в ВЛС.

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

Для представления сетей в работе вводятся вершины ол+бю, и дуги р и к типов.

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

- в -

вершин и дуг. Поело введения правил продукции во второй главе вводится определение ЗЛО - сети.

■ Определение. ВДС-сетью называется взвешекпий ориентированный • графА=су,э>, где V - множество функциональных вершил типа бь-.вю , соединенннх р-или. к-дугаш в соответствии с превши?® продукцж! вортш р=Ср,-4-р7>-

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

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

12 п

С(р)-последовательность, задаваемая определенным ■ путем, называется порожденной путем р

п-1

с(р) = пс... . ,11) ,

определяет достижимость вершины vi из вершины .

Вес пути полпоствю задается весом его вершин и

определяется как сумма весов, появляющихся в нем вершин.

ир>

здесь - У(р,1) вёраина, стоящая па 1-м места в р; - ир) - общее количество вершин в цуга р. Маршрутом н(ух,у2) в ВЛС-сота называется множество путей

таких, ЧТО я У(Р,1ЛРП=У2 и v УСР.к))^ для 1<к и v

у(р,к))^2 к < цр),

Задача анализа МС - сетей. Пусть а-ВлС-сеть с множеством вершин v я дуг з. а

ря(у .ыи^)),* .МС12Д3>>.....(а(хп.1,хп)),у1 ).

А * п

путь, такой, что

п-1

с(р)=Пс ,(1)^0,

к*1 к' к 1 >

необходимо определить

мр>

для v еа «и а к

Задача анализа ВЛС-ситей сводится к определению весе и<р), для любого заданного пути, начинающегося и заканчивающихся в а ч>

а.

В третьей главе начинается разработка методов анализа процессов в ВЯС.

Задачи анализа рассматриваются по следующей схеме;

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

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

3) Алгоритмы изучаются в работе с точки зрения реализуемых ими случайных процессов, Основные решаемые задачи сводятся к определению распределений длительности реализации алгоритма, радоуэдедаяия объемов используемой намята, распределений вдтере&к® на запросы к вчоду - выводу. Самостоятельный интерес

представляет совместное распределешо указавших величин.

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

Задача анализа процесса обработки, модояируемого ВЛС мохлт бить представлена в виде композиции отдельных подзадач, таких как:

-Анализ операторов. -

-Анализ параллельных процессов.

-Анализ участков с взаимными переходами. Решения полученше для отдельных участков ВЛС затем могут бить . объединены для структуры в целом.

Композиция решений да задачи анализа операторов рассмотрено в третьей главе.

К атому разделу относятся:

а)прообразования Лапласа плотностей распределения результк-рупдего веса для схем структурного програг.амропония:

а.1)кошозицни операторов

Я(в) = а (з )Ь (з )

а.2)опзраторов выбора и альтернатива

а(з )=га (я)+ (1-г )ь (з );

N

1=1

а. 31 итераций

Если мг)- производящая функция числа повторений

а>

1=0

то, преобразование Лапласа плотности распределения

плотности распределения веса результирующей вэриины; a(s), S(s), q(s) - преобразования Лапласа плотностей распределения; г, rit к - вероятности.

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

условным прекращением сычислеша.

Цикл с пост-условием - выходом вперед:

Преобразование Лапласа плотности распределения

*(•) - k(q ♦ р 1 -

I 1 - r(b/q

если обозначить

то прообразовакиэ Лапласа плотности распределения для цикла с пост - условием и выходом назад будет

t(s)= r(s)qk(qP<a>)< 1 r(«)q )■ ^

1 - г (s )q - p?(e)Cr<s)qi\qr(s))>

В использовании:: обозначениях р - ьороятность выхода из цикла, а q=i-p вероятность его продолжения нормальным образом.

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

Четвертая глава посвящена анализу параллельных процессов.

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

Подход к анализу основан па основном соотношении для преобразований Лапласа плотностей р?"яродолей,ш длительностей исполнения (весов) параллельных ветвей

Cj+joa C2+joj

C1-j£3 ' C2"-Íí0

'i* {s }-нрво5разовашю Лапласа плотности распределения; для случая прекращения вычислений в момент завершения максимального по длительности процесса;

и соотношении, связывающем преобразования Лапласа для процесса минимальной и максимальной Длительности;

а"(5)-преобразоваш19 Лапласа плотности распределения для случая прекращения вычислений в момент завершения минимального по длительности процесса.

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

а*"{в)«ь(в) +

здесь

i-i

F (m) =Г -i-,._±— 1

1 l (S-4i)m кг-i

а - корни знаменателя, )<1- соответствующая 1-му корни кратность. . .

Математическое ожидание для процесса, зввэ'-чаодегося в момент окончания максимальной по продолжительности исполнения параллельной ветви:

т —

1 -ь +

к .-1

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

N ^ 1 оо 1

■С(*)=][ с. - п -у .

(ы-х ? 1 г* (5*х> здесь м

1=1,2...N5 ^ а=1

а - производящая функция числа повторяемых этапов

I . гр .л.

где

А.

р.=- И Х=тахС\.>.

1 \ I 1

Последнее нродстан пение позволило свести задачу т

шмонтной аппроксимации к основной задаче линейного программирована« .

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

В пятой главе рассматривается анализ оероятнзстшх переходов в программах.

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

Система уравнений для npeoCpssoBaiiitfl Лапласа плотностей распределения времени исполнения бэз учотз оэдержзтс по переходах:

м

j=l,N-l.

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

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

Система для преобразований Лапласа (несколько поглощаи>щх состояний) имеет вид

aJtJ(.) - ¡jtoZtj.i^.jl»). UeO.

Viel

^j.jt") " l!

здесь J = ,j2,j3,... > - множество состояний, для которых о является достижимым.

Пределы j(s) при s-»0 определяют i роятноста поглощения процесса, начавшегося в i-м состоянии состоянием J.

В пятой главе выведены системы уравнений для вычисления вероятностей поглощения и система для математических ожиданий и дисперсий.

Дальнейшие о60040шш касается невозвратных состояний и групп поглощающих состояний. В работе выведены: распределение С преобразование плотности •) времена до первого попедаыня процесса в состояние с номером fc с G=(i1-i2----принадлежащее группе

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

\ А

ак<5Ч,к

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

Далее в пятой глава рассматривается вероятностная схема с процессом переходов, отличающимся от марковского.

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

га 1=0

здесь п"-матрица преобразований. Лапласа длительностей п шагового перехода, для которой показано

П(п+1 >(* )=Й(П) (• )П(Е )=П"+1 ),п=о, 1,2...

На основе подученных соотношений вьшедеш ыреобрас звание Лапласа плотности распределения веса эквивалентной вершшш: к>

1=1 . Здесь у-веетор стартовых вероятностей, а в - единичный вектор -столбец.

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

1

(вероятности, число шагов и время до появления определенной оилбкп). Также рассмотрены друга« задачи.

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

Несколько альтернативных выходов из цикла с произ эльным числом повторений. Определение преобразований Лапласа распределения длительностей (веса) при завершении участка по заданному маршруту.

к<»ш>

ф1(9)

п г-

ж

1 - РшШ(б)к(рши(5))

1 - рыш<*)

Вероятности заверивши участка на заданном маршруте:

V V

1 - Ри)к<Рц> 1 ~ Рм

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

3 работе показано существование уравнений и систем уравнений, описывавших процессы с прямой и косвенной рекурсией. Прямая рекурсия с бесконечным уровнем вложенности:

-1(»)-Мра(»)+чь(Б)а(»)>

Косвенная рекурсия с бесконечным уровнем вложенности:

( m

= ^(qjW^s)^ р. ^.(^^(s))

J2, -í:=1

l-qx = ^ .m

Jrl

Выше использованы обозначения:

- 'íi (•>) - преобразование Лапласа длительности исполнения процесса t от момента начала до завершения;

- ы^«) - преобразование Лапласа распределения длительности перехода на участкэ без рекурсивных обращений, - соот-ветствущая вероятность продвижения;

- у. (s) - преобразование) Лапласа распределения длителъг чета перехода нэ участке с (косвенно) рекурсивным обращением к процессу j; pí соответствующая вероятность выбора j-ro путл.

Рекуррентные соотношения для случая процесса с ограниченным уровнем вложенности.

T(i¡s)=k (pa(s)+qb(s)%(i + l;s))

Здесь использованы обозначения > - для преобразования Лапласа плотности распределения времени исполнения процесса на уровне вложенности ie i..n.

Для оценки поведения процесса необходимо определить

Для всех рассмотренных схем приводятся соотношения для моментов распределения веса вквивалентннх вершин.

В постой главе -arate рассматривается обобщение класса вероятностных процессов в ВЛС.

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

Для пояснения изложенных положений уместно привести пример гипотетической структуры с выведенным структурно-инвариантным определением процесса в ВЛС.

- ie -

a - h. q »1st - c.nyudi'çbi еедомм згаернеи. Еем a - с.s.. то преобразование Ааиаса тотности se рактеигачкз

fls> - npeaSpesoeaee Лапласа iwarfacn« рашмавлачт' длнгежмвеп мзтоянвния ajrff'jíira,

- - -реевразееэма Ian jaca ели яигзлсспг pacrr редеть-ил йляальиесп» мт>лнг*яд цчаотяэ.

Us), Krt - щямжижвг функции распреюдаля «пел» псетсре«>'й ................. '

pw.î Bepasïwerw» - л®г»«еим-спщк»у»

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

Результата анализа вероятностно-логической структуры алгоритмов могут быть использованы для .решения задач повцеэпия производительности. Такие задачи часто являются оптимизационными и относятся либо к настройке параметров ВЛС, либо I структуре процесса обработай.

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

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

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

Х)0сновной изучаемый в этом контексте вопрос можно сформулировать так: какая виртуальная ВДС обеспечивает максимальную производительность (минимальную стоимость исполнения), ва данной установке ? Решение этого вопроса тесно связано с производительностью аппаратуры и собственно ВЛС программ.

a)Понятие виртуальная ВЛС формулируется в работа с учетом результатов оптимизации структуры в системах массового обслуживания: СМО с обратной связью и СМО с несколькими обслужнващиш аппаратами.

b)в случае рассмотрения ВЛС как структуры виртуальной машины потока данных можно утверждать:

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

2)Структурная оптимизация ВЛО применяется во многих

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

В этом случае речь вдет о использовании ВЛС для пераструктурирования программ. Пор&структур1фовшшо приводит к ощутимому выигрышу в эффективности в случае проявления пришила локальности (Для распределенных систем в размещении программ и данных).

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

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

Пусть задана сеть асу,»,гдэ V = {VI,42, VN} - множество вершин, а б множество связей. На сети определены маршруты:

р1(у<1,1),у(1,1)...viк(1),1)), 1=1,2...м.

1)Система относительно математических ожиданий р1,р2. . . Рп -

i 1=1,2...м

р= {р^ ,Р2.. .р^) задает вектор математических ожиданий длительностей исполнения путей;

2) Система относительно дн люрснй ор1,ор2.....орм -

Г 01^|В1а1+к1Ь1.а2 + к2Ь2....вы+кмЬм}-О 1 1=1,2...«

в=спр1,ор2.....ор|1) задает вектор диспорсай. На объем переносимой

работы накладывается ограничение:

ь1+ь2+...+ьн=0

критерий минимума среднего взвешенного веса путей : 4 м

I

С^Р^ Г •» (а)

критерий минимума * пч-ка

м , м

iv. {!■

1/2

Критерий "а" позволяет учесть стоимость использования ресурсов .

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

3>форкализацгя программы, привязанной к некоторой аппаратной среда, даягена с представлением ©пкцяощруйцгн ВО в виде систем ащ сетей массового оболуетпэяия. Сети ЗЛС позволим рассматривать взата*одойствиэ алгоритма с аппаратурой как взаимодействие системы кассового обслуживания а нагрузки. Совместное ис-сладоэаш* моделей ВС и алгоритма прозодатся как аналитически, так н с помощь» имитационных или- гибридаах моделей. -

Метод имитацкогшого моделирования для анализа и настройки зффективдаста процессов обработки- информации существенно дополняет аналитические метода рассмотренные выше.

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

Особенностью $ рмируемого подхода является совместное применение для исследования как аналитических, & имитационных моделей. Последние требование делает необходимым наличие в систем» модалгароЕшия объектов и средств управления процессом шдздкровапйл, обэсн&чиваищих достаточно высокую степень форшшшцаа вссдадуешх процессов. С другой сторона» необходимым является обеспечений система моделирования средствами сопряжения с штааатячаскима в оптЕмизацвшшдш библиотеками,, программами для численных расчетов, статистической обработки результатов

.'жсиоримэнта. Эти требования в известной степени является прота-шречпвуга,. us шлолненЕэ a pastas работы позволило создать систему моделирования ^ обладакдув достаточно вы'гаспм уровне- ■ формализма для отекания трудоемкости з разработке я программировании моделей, я об&спэчиваэдую в то а» время гибкость использования , программных средств и современных матоматичесгап библиотек.

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

program AssTest2;

uses SI MP AS. DIALOG, CRT; var PROC j PSTORAGE;

a 1 PQUEUE;.......

KewSTORAGEC PRQC, ' PROC *,S>i HowGUEllF.C Q»* Q "3; I nitCreateCl ,0; wliile SYSTIME < 1000 do begin case SVSEVEJfT оГ

1 > CrealuC.

2 t bog In

TRANS".Mill truncCKandABC3,10,Vll]5>i

Spl i l СTRANS". PI [ U , Э) J end;

3 i И)1п

I nQue-traC Q1;

Trans".Prtai > « RandexpC. . ..); end;

4 t EnterCProcJ;

5 » DelaytCKinCTrans".PrIl>,Deita»;

a » bpgir»

L»w(Frac>;

if Tr»f»~.Prltl « о then Них I <0>j

end; . ,v-

7 « if Trans*. PRT * PrtyHax thfii MextCOi

els» .

bogi n

If RaiuJOlCVim < 0.001

I.hen begin < ОЕЯбКЗ > Trans^.Prl 1 3 s « Oj Par inAnsC PARKS, 1 > ; PrlorityCPrtyKaxJ; NextCQJ;

end

else D' f f er;

entl;

8 t HextC«;

9 t AssembleCTrans^.PIl11);

10 I if TRANS*. PRTlf <> Pltyttax then

SO ! for I 1 to TRAMS. PI 111 do

OutQueueCQi;

11 : Destroy; end;

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

ОСКОНШ РЕЗУЛЬТАТЫ РАБОТЫ

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

лаучкгх положений диссертации для широкого спектра приложения с применением единого методологиче( :сого подходе.

3 процессе выполнения работы автором получены слодущи« основные результаты:

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

2Р работе показано использование разработанных в класса ВЛС методов для решения широкого класса задач ">рганизации вычислительных процессов, а также для решения ряда проблем, связанных с выбором структуры технических средств и структур программного, обеспечения.

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

. фуксционирования проектируемых даши модернизируемых систем.

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

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

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

7 )Ддя решения практических задач разработаны и исследованы

- ?•>

программа« средстве построения имитациояннх моделей, отличавшиеся от имеющихся машинкой незавксжосгъ» (пвреносшлоетьа) сравнительно болез высоким быстродействием; а такта оригинальные аналитическиа, аштациопше и оптижсзйционныо программные модели, широко исаольэлацие возможности современных математических библиотек. " .

8)Все результата диссертация в виде методик и программных систем внедрены в практику каучко - последовательней: работ предприятий НЙИАА, НЕ5СА. ЕРНШ5ММ, ЕРНИЙАОУ, ЕРШЙС, а такхо используются в'учебном процесса.

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

Полученные разработанными методам;? результаты сравнивались с' имеющимися, опубликованными к печати отечественными и зарубззвымл учеными. Ссылки на публикации. приводятся в текста диссертации.

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

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

1. Виноградов В,И.„ Марков A.A., Попов А.К. Моделирование специальных распре делений // Вычислительная техника. -М., """^б, -с. 49-53.-(Тр. ШГУ, «217).

г. Марков A.A., Маркосяы U.E. Вопросы исслэдовання структур памяти.- В к.: Развитие теории и техники средств хранения шфорыацдт Тезисы докладов всасоюзн.ковф, -М.-Рига, 1980, C.72-7S.

з. Марков A.A., Иаркосян М.В. Выходощяй поток системы массового обслуживания// Исследование и проектирование управляющих вычислительных комплексов.-Ы., 1982, -c.II-^I3.-(Tp. ВЗГШ/ШЗ)

Парков A.A., Маркосян М.В. Интерактивная -.система исследования одного класса вычислительных процессов/ МВТУ. им.

Н.Э. Баумана.-M., 1983. -32 е.- Деп. в 1ШИЭИР 10.03.83, Я 3-7239.

5. . Марков Д.А., Гарханян А.Г. Использование системы имитационного моделирования ИТШЛС для решения оптимизационно имитационных. задач/ МВТУ им. II.Э Баумана. -M., 1987. -24 с. Ден. В ВИНИТИ 10.12.87, № 8630-В87.

6. Марков A.A., Тархонян А.Г. Концептуальная схема бази моделей систем» иерархического проектирования ин&эрмациошю - вычислительных систем// Проектирование вычислительных мнлш и систем.-Рязань, 1987. -с.П4-П7.-(Межвуз. сборник научных трудов).

7. Марков A.A. Стратегии хранения и замещения данных в объектпо - ориентированных мультипроцессорных ВС// Управляющие мульти-микропроцессорные систем«. -П.: МИРЭА , 1987.-с.65-71. -(Межвуз. сборник научных трудов).

•е. Марков A.A., Пирумов H.Р., Гудзенко Д. В. Применение общецэлевой системы имитационного моделирования СИМПАС в полунатурних моделях //Техническое .и программное обеспечение шяшексов полунатурного моделирования: Тез. докл. Всасодан. н.-т. конф. -Москва, 1988, с.П-14.

ч. Марков A.A., Тарханян А.Г. Экспертные оценки в икитацнонпом додолированш информационно вычислительных систем/ДШ- тциошша эксперименты о моделями сложных систем: Tau. докл. iv Всесовзн.н.-т. школы цикла "Системы управления и методы их моделирования". -Калининград, 198У. с.37-39. 10. Марков A.A., Пирумов Н.Р. Использование метода макромодвлой . для моделирования разномасштабных. систем //Имитационные зкошрщентн с. моделями сложных систем-. Тез. докл. tv Всесовзн.я.-т. школы * цикла "Системы управления и метода их моделирования"Калининград, 1939. с.14-16. „Ii. Марков A.A., Пирумов Н.Р., Гудзенко Д.В. Графический процессор для представлен®» структур Тс.ашческих систем и формирования их моделей //Математическое . обеспечение систем с машинной графшсоЯ: Тез. докл.. v научно - техн. сяминара. -Ижевск, 1988, с.24-25. .. •. *

12. Парков A.A., Пирумов Н.Р., Гудзенко Д.Ю. Обтецелевзя система имитационного моделирования на Паскале /ШШ' им. Н.Э. Ваумаиа.--М., 1989.-II0 С. -Деп. В ВИНИТИ 15.08.39, M 5500-R39.

13. Марков A.A.,. Медведев И.В. Моделирование технических систем с использованием языков высокого уровня» Учзбн. пособие по курсу

- 7.7 -

"Моделирование технически систем" ,-М. iИзд.-во МГТУ,' 19ЭХ.-30 с.

14. Марков A.A., Пируыов Н.Р. Применение макроиоделой в опти-мшзодаонно - имитационных задачах.-В.ich.: Крупномасштабные системы. Моделирование развития и функционирования. -Ы.:Изд.-Во- ИПУ, 1990. с.88-94.

15. Марков A.A., Тарханян А.Г. Расширение возможностей имитационного моделирования при использовании . методов искусственного интеллекта//Техпичёские средства и ма- матическоо обеспечение ЭВМ к систем.-Ереван.: ЕРШ1, 1991.- с. 79-83. -(Можв. сб. научи, трудов)

16. Петров В. Я., Марков A.A., Маркосян М.В. Иерархический иэтод исследования структур вычислительных систем к ко'яшокг^в// Исследование и проектирование 'управляющих ' вычислительных комплексов.-М., 1930, -с.61-66.-(Тр. ЮПИ, &I23) .

17. Петров В. Я., Марков A.A., Маркосян М.В., Определение пара-котров потоков в системе // Исследование и прозктйрованио управляющих вычислительных комплексов.-М., 1980, -с.66-69.-(Тр. ЮПИ, Я23) • -

ib. Петров В.Я., Марков A.A., ' Маркосян М.В,.- Исследование промежуточных потоков в многофазных системах ' . массового обслуживания //. Исследование и проектирование ■ упрьшпоада вычислительных комплексов.-М., 1980, -с.28-32.-(Тр. ЮПИ, И23)

I1?. Сурков Л.В.,. Марков A.A., . Медведев Н.В. Модолировзшз информационна - вычислительных систем на языке gpss» Учабн. иособио по курсу "Вычислительные систеш".-М.:ШТУ,138в.-31с.

го. Марков A.A. Операторные 'методы анализа производательпости ирограмм/МГТУ им. Н.Э Баумана.-йш. №37215.- М.,1393. -207 е.,

21. Марков A.A. Программная •имитация информационных процессов /МГТУ им. Н.Э Бауман.- Ипв. й Ш6775. - Н. ,1992. -221 С.

Содержание работы нашло отражение и в других печатных и рукописных работах соискателя ( работа : Марков Д.А- Математические методы оценки эф^екготгости и . производительности программ. -Ы: Изд-во'МГТУ, 1992.- 210 с. находится в ючатя). .

Подо.к печати "Р2 (?-S~I993 г.Объом л .ч. п.л.ааказЗЗ^'.Тираа 100 Гипограф1я МГТУ; 2-я Бауманская ул. д. I: