Введение к работе
Актуальность теш. В середине вОх годов сложившийся все-, лтрцца оборот средств индустрии обработки данных составлял около Со.' процентов й стоимости хірограшното обоспочотія и 15 процентов п стоклоота , ешіврйїїріі. 3 SOx годах удольшй вес стоимости аппаратуры продолжал сажаться, я, кроме того, яспо выявилась . тенденция к снижолш стойкости .единица прироста производитель-коота аппаратура л-пошиошт стоимости абсолютной едиігацм произ-водятелкіости программ. ' Диссертационная работа посвящена проблемам-, айектавяосги использования программами ресурсов вмчкедк-' їо'лблмх-.Ьзстом.' '.'
Проблема/оизшсй.-а^фокишію'стк фущсщошфовавяя является одной из' наиболее "вахнюс - в 'теории вычислительных' систем. Наиболее значим6--проЛ»еМ9 ;зффзктивяастя' проявляется в новэйик виеока-скорсстннх сястзмах, к числу'которых относятся: системы'реального времени,-система культа - медиа,. распрэдвдашшв'компыиерпив системы.-с параллельной : и ксгардшировашоЛ обработкой, трэне-'пьстервце-системы і -сиет'еш с волоконно - оптической связьв 'И оптозлектроншо' ЇШПКГСЗрЦ.
Появлений новшс иафортацшввш: технологий делает- актуальним разработку нових методов ода- за эйрекйаеносгя фувздяопаровапая ВС, более полно' учтгюащах повне. яозтщюст аппаратуры и прсграмтеого- сббсйэчопия.
.,. Область прлмаае'пил результатов анализа эффективности и про-, йзвбдктаякіости . програш' достаточно яирока. Вта результаты ппаздалютсй почти -везде';'- гд'э''пршеняются программи, з более точко і - везде,; - - где шслвдствяя неправильных реаонга' ощутимо, Стїозівзаится ва-зйіе'ктйвнйси;. В первую очередь это относится к сйстг.шщм. ітрограммаи, в некоторых,случаях, прикладное програшное . обеспечение пГакайС'. требует проверки л временной сшщфкощщ. Анализ проййводдальтюста подабамх-программ особенно необходим. Часто пр^лп^екїк^іззниіг структур, программного обеспечения всэвдаавт oirrafeaiisbaie _задача. ' ' ' - ;
<^офф^і^'(^^;-р^вішф&і$ ж проазводятольпости играет в' твх^зШфзШтш^ вачдмівтельшй . іймшго^сах и системах рееяьпзго. ;вршэнй... Програшшйт , рэзляэепдя алгоритмов требует іфйвлаченяйшйШ . ресурсов ЭВД, ЇШшоіївШ ресурсом является
процессорное время. Оценка времени реализации алгоритма осойоо значение шэет для специализированных вычислителей. В том случао, когда система реализуется как споциализировавлая, алгоритмы оказывают существенное влияние на структуру и состав аппаратуры. Принципиальную важность эта оценка имеет такеє для систем сального времена.
Развитие средств телекоммуникации и средств связи привело к .использованию средств и методов удаленного доступа к датшм и программному оОеспвченша. С практикой распределенной обработки сталкиваются многие люда и коллективы. К сферо производительности программ в системах с распределенной обработкой относится целый рад задач анализа н оптимизации (в том число структурная и параметрическая).
Рассматриваете вопроси имеют отношение не только к взаимо
действию программ и аппаратуры, их использование оправдано при
рассмотрении взаитдейс-лья программ с конкретной программно -
аппаратной средой: п этой области, обцепранято их использование к
задачвм нсследования стратегий замащення страниц в системах с
виртуальной память», к задачам анализа использования пулов
ресурсов, к задачам, имзкщим отношение к базам данных ер специ
альной структурой и особыми методами тюковки и храпения инфор
мации. "'.'
Широкий класс приложений можно аайти практически в лйбой области теории вичислительных.систем. '
Разрабатываемая в диссертация проблема: направлена на решение актуальной научной задачи, имеющей ваавра народно -хозяйственное значение, и тесно связана с планом научных работ ЫГТУ им Н.Э. Баумана
Теоретические вопросы и программные системи, вклшающне в себя еналитяческиэ, иматационшо и ощшизационше модели разрабатывались автором лично я при его непосредственном участии в рамках госбвдветвнх и хоздоговорных НИР, в работах, проводившихся по постановлениям Правительства, по "Координационнсвду . плану научяо-исследоваї-льсішх работ вузов в области вычислительной техники" на І98І-І985 и І986-І9Ч0 гг., а также ' в соответствии с программоїі №шв*'за СССР "Автоматизация научных исследований" на 1986 - Ї990 гг.
Цольи работы является создание н рсзрєботіг научных сенов построения формальних методов повышения зффоістшщоста фуккциоии-рова».ля ярооктируошлс и модэрвизируемяс быстродействующих шчи-елэтольшх снегом яа оснопо едшюго методологического подхода.
Важным аспектом исаяодовапия является фортрова'.та и разработка на основании сбобгдешїл предшествующих исслэдовепий система-тичоских регулярних мотодоп для рзиеїшя задач анализа производл-таяыюсти и эффективного построения структур процессов обработки информации.
На затяту в'мюевтея следувдие далояеияя:
основные концепции а методы формального подходе к классификации процессов в ВС на основе выделения в процессах вероят-їостпо - логических структур;
вороятяастшге модали схем (операторов) структурного арог-зошировзняя я правила композиции структур для поиска обобщенного яшния;
схема яэструт^гурного взаимодействия програй* па осново:
вероятностных моделей пароходов с зависимостью от маїшірутов» порядка сбре*откя, влзженностя и цякяячшиигн повтореная,
вероятностных схем вззимэдвйствия параллельно - ис-палншш: процессов'»
' — вероятностных схем процессов общего вида с циклами, перекрестными ссылками» взаимодействующими парадлельшйса угасткаш, а также прямой я коевзнпой рекурсией;
- вероятностные схемы рздовня задач оценки потребления '
есурсов крдгренмямя с учетом возможности использования
Ертуальнои структура процессов для управления эффективностью
сцолнэния;'.-..'
- ярограммннэ средства для решения практических задач с
ззользованяай разработ яшя в дассертацин методов, включавдне в
эбя )вдзлируп$а& програш* общего назначения, о таюю
іадиткчзсігав, ийзтацгонше' и оптимязационныв программные модели.
Штоди теорвтачосках исследовании.
. . - 3 -
Проблема исследования эффективности и анализа индексов производительности программ решается с привлечением методов теории стохастических систем, случайных процессов, теории вероятностей и математических методов исследования операций. Основним математическим аппаратом в работе являет-я преобразование Лапласа и теория производящих функции. В работе используются линейные и не-линеишэ оптимизационные задачи, програмная имитация и имятаци-ошо - оптимизационный подход.
Научная доятазна работы.
Научные положения, вынесенные на защиту, позволяют рассматривать широкій класс вычислительных ароцэссов, оценка производительности которнх проводится для выработки методов. и рекомендаций, направленных на повышение эффективности их исполнения. Првдлогввн г теоретическш методы, основанные на использования вароя-дастно - логических структур процессов, являются самостоятельными, в обобщенной форме обитают широкий класс процессов, и впервые рассмотрены в работах автора.
Разработанные правила продукции и композиция вероятностно -логических структур, основанії не схемах структурного подчинения и ветвления процессов в вычислительных системах. Ш использование позволило описать новый вид дискретно - пепрэрывных "вероятностных процессов, характеризухадйся учетом возможности запг шания истории развития, наличием вложенных, случайное число, раз, повторяемых участков,; вошжность» перекрестных переходов, с прядай или косвенной рекурсией.
Введенные в работе структурные инварианты позволят1 точно описывать вероятшстиыа я детврашированшэ модели для получения мшжоста&явж оцевок поведения изучавших процессов.
диалкз литературных источников показывает, что рассматриваемые пройдены обсуждается во маогих арилогвниях теория вычислительных систем, о атом смысле работа созвучна современным направлениям исследований производительности и эгМективюсга. От имеющихся' публикаций пред еженная работа отличается единым Мйтедологиче^ким подходе... широкша классом рассматриваемых ароцоссов, полнотой получаяных результатов и высокой степенью
« 4 -
Практическая значимость работа.
Практическая значимость работы определяется классом задач для которых могут использоваться ее результата. Задач:*, к которым прйлоаама теория ВЯС относятся к классу задач метрической теорій вычислительна*: систем п служат для оценки архитектурных решение в ЭВМ, комплексах, сетях- к система::.
Практически работа направлена ка выявление узкие мест, прогнозирование поведения индексов производительности, сравнение результатов,сдактурпых решении» цереструктурирование процессов с дельв пойїягашія Бйа-твэпости исполнения в конкретной программно - аппаратной среде. .
. Теоретические, результата,- полученные в работе, касаются сопросов зффэктЕвкого построения внутренней структуру процессов обработка , Шїфор>лдаи, при 'таком' подходе, эффективность рассматривается с -точки зрзпйя исйолшюмого процесса. Это -- та область теории вычислительных систем, к которой относятся работа соискателя.
Теорэтическиэ результата н программные средства нашли прмэненио в практике проектирования п научных исследований в ряде предприятий ("Пакет прикладних програм,» для катергктивлого моделирования нвформгініонши процессов" получил первую премии Всэсоезеого конкурса на лучшие разработки в области Автоматизированных Систе?< для научных исследований).
Структурно работа состоит из Введения, 7 глав. Заключения и v приложений. Первые две главы относятся к обзору состояния проблеми й формулировке зада'" исследования. Полная формулировка задачи дается в конце второй глави, после того как сделаны все необходимые определения и очерчен круг нерешенных проблем.
Главы с 3 но 7 включительно посвящены содержательной части работы. 3 приложения вынесены основные форг,<улы и соотнесения, необходимые списания разработанных программных систем.
Внвдренив и практические исследования выполнялись по планам звучно исследовательских работ кафедры ЭВМ я систем МРТУ им. Н.Э. Баумана, а также самостоятельно автором при работе над миографией "Йатаматичвсккз. (взтода оценки эффективности и
производительности программ". Практические результаты в виде котодик и программных систем, разработанных автором и нод руководством автора, при его непосредственном участии, внедрена в ИЩА. ШШСА, ЕР1ВШСУ» ИШ, ЕРНШСС,
Результаты работ использованы л ряде учабянх курсов в ЫГТУ.
Адпробания работы. Осаовниэ теоретические положения и практические результате обсуздались за 7 всесоюзных и республиканских научно - технических конференциях.
Публикапм. Основшо положения работы опуСликовашт 22 работах-, включая 2 учебных пособия и I монографию- (в' печати); а также в научно - теэишчвских отчетах»
Объем работы. Содержание изложено, на зі* страницах машинописного текста, содержит 76 рисунков и таблиц; содаряпат список литературы из 144 наименований и приложения. .
В первой главе на основе анализа літературних источников формулируются задачи и цель работы.
Задачи анализа
Время.
Различные штока исходных данных при реализации алгоритма приводят к виполненав Различных его ветвей, что даяяэт длительность реализации. Зависимость времени исполнения от исходных данных приводит к необходимости изучения вероятностных характеристик времена реализации; математических ожидании и дисперсий, йатвгрйльвой оценкой времени реализации является ого закон распределения
Распределение времена реализации являотся первым объектом для изучения. Верояг'эстяая постазовка проблемы анализа распредштпг'я времена ..сполнания, представляет собой порву» задачу, большшство рвззмьтатш приводится в литературе именно для этого случая. В частности заметим, что в случае -возможности
-6- -'..'
.*
явного перечисления небольшого количества маршрутов и задержках, извэстнах для квздого узла алгоритма, рзсь.-едолопиэ времени, исполнения будот иметь вид:
HsO-Vm^i-obf У t(U)< х j
где я ,1» ,;..ml...m - вероятность выбора маршрута і\» a n количество маршрутов, tju.) - задержка в i> узлах яа маршруте. Рошепиэ задачи основано на поведении случайных сумм случайных величин.
Память.
Реализация многих программ, особэнно в системах с
ограничениями аз падать, весьма критична по времени к
удовлетворения запросов на выделение памяти. Запроси на память
обрабатываются с некоторой задержкой» связанной с работой
программ распределения памяти и ожиданиями, связанными с
освобождением другими программами или собственным программным
модулем требуемого объема памяти. Зероятдостная структура
процесса вичислений привода' к появлэзш» случайного числе
запросов из память как по их числу, так я по суммарному
требуемому объбау. "агам образом в некоторый шбрзшый момент
временя нлз в некоторой звдаь .ой точке аягоряяка, программа моют
та в обідам случае распределенный произвольным образом объем
занимаемой пйяятк; '
V(x)=Pr[V Оценка вероятностных характеристик используемой, неияти во многом, схожа с оценкой времени реализации:" VCx)= VrnProbf VW Основное отличив заключается в то?,*, что отдельные слагаемые могут входить в выражения типа (1) вв только со вязком "+", но и имея отрйцзтвльноо зн8,бни&. В то se вреия сбдий объем памяти, занимаемо» проградаой зависит от текущего распредеяашя памяти, поэтому в задачах оценка объема са?ягя додам бодав широко использоваться усшзнш распределения, и большее внимание долало уделяться особенностям структури алгоритма. Запросы н потребление ресурсов. Похожие методы применяются для исследования взаимодействия алгоритмов с подсистемами управления jecypcaMU. Вопроси оценка . .лияния процессов' ввода-вывода на длительность реализации алгоритма, оценки нагрузки, вносимой алгоритмом на подсистемы ВВ, распределение' этой нагрузки по времени реализации, оценки распределений интервалов между обращениями к УВ^, в совокупности относятся к этой задаче. Ее особенность состоит в необходимости изучения поведения распределений накопленных сумм между выбранными точками в струї -уре алгоритма. . Анализ взаимодействия алгоритма с УВВ позволяет оценить правильность решений при выборе методов буферизации, снизить время решения при имеющихся ограничениях на объемы буферных областей, оценить условия работы УВВ. метода решения этих трех задач должны быть основаны на достаточно общих вероятностных предположениях, систематизированы и формализованы. Основным объектом исследования является вероятностно логическая структура алгоритма, вад .эни« которой ведется для оценки распределений времени исполнения, используемой памяти, параметров нагрузки на подсистемы управления ресурсами. Формирование подхода к исследованию проводится на основе базового понятия структуры процесса. Во второй главе формально определяются вероятностно логические структуры fMC) и формулируется задача анализа процессов в ВЛС. Вероятностно - логическая структура определяется как сеть, вершины которой количественно п качественно характеризуют способ потребления программой ресурсов, а дуги задают порядок и правила измонеїшя этого способа. Для представления сетей в работе вводятся вершины gi+gio, и ДУГИ р Н к ТИПОВ. Качественно вершины и дата определяется типом, количественно - спецификацией типа. Способ объединения вершин в сети задаются правилами продукции. Правила продукций не зависят от спецификаций - в - вершш и дуг. После введения правил продукции во второй главе вводится определение ЗЛО - сети. Определение. ВДС- сетью пазиваотся взвешешшй орлентїпхшашшй граф a=cv,s>, где v - множество фулкционэлькнх вершш типа glvgio, соедшзешшх р- иля>-дугами в соответствии с правилами ПрОДуїСЦЖІ ВОрЗГЛН Р=Ср,-4-Р7>- Яусгь а-ВЛС-сэть с множеством вэршия v it дуг S. Обозначим а множество верши, не включенных в а.; Это множество представляет собой впевнюю среду алгоритма. Определение пути. ПУТЬ - последовательность ВВрЛЯН , ПОЯВЛЯЮЩИХСЯ В '38Д8НВШ обходе алгоритма, соединенных дугами с не нуле вым весом: P=Cv. ,(d(i1,i2!),vi ,(d(i2,i3)),...,(d(ln_1,inn,vJ ). 12 Г) С(Р)-последовательность, задаваемая опрэделошшм путем, называется порожденной путем р п-1 С(Р5 = П С.,, ,11) , k-I d(Vxk + l ' определяет достижимость вершины vi из вершины vt . Вес пути W(pj полпоствю задается весом его вершин л определяется как сумма весов, появляющихся в нем вершш. UP) W(P)=y U( J(V здесь - v(p,i) вёраипа, стопідая па і-тл места в р; - up) - общее количество вершин в дута р. Маршрутом m(vx,v2) в ВЛС-сота называется множество путей K ТаїОХ, ЧТО VtP.ll^Vj, Я V Задача анализа ВЛС- сетей. Пусть А-ВлС-сеть с множеством вершин v я дуг s, а P-tv ,(d x * n путь, такой, что C(P)= Пс , uj*0. необходимо определить UP) Задача анализа ВЛС-сетей сводится к опрвделешт весе w А. В третьей главе начинается разработка методов анализа процессов в ВЛС. Задачи анализа рассматриваются по следу идей схеме; ПГГроцессы. структура которых удобно задается блок- схемами, обладают ярко зирахенными свойствами стохас. ічееких систем. Характер обработки задач во многом зависит от структуры аяго-тмов, возможности их распараллеливания, .способов взаимодействия с подсистемами ввода-вывода, распределения памяти и каналами компьютерной коммуникации. Эти процессы, являясь стохастическими, соответственным образом влияют на обработку программ. 2)Вероятностно- логическая структура, является следствием блочной структуры алгоритма и случайного характера его выполнения. Вероятностные свойства долош быть назначены блок схеме алгоритма с учетом логики его исполнения. Этот процесс носит названиеспецификации ВЛС. 3) Алгоритма изучаются в работе с точки зрения реализуемых ими случайных процессов. Основные решаемые задачи сводятся к определению распределений длительности реализации алгоритма, райдрэдаоеяия объемов используемой аамята, распределений штрв&йов ва запросы'к вчоду - выводу. Самостоятельный интерес * 1-0 - представляет совместное pa определенно указанных величин. Бодылшство результатов анализа В "О получоио із вида преобра- 30ВРІЕГЯ рЗСПрОДеЛЗВДЙ, ПОЗЕОЛЯЩЩИХ НгПОСреДСТБВПЯО ПОЛУЧИТЬ MST3- матичвекно ожидания и дисперсіш, а также болво шсогаш моменты распределений исследуемых величин. Задача анализа процзеса обработки, модояируемого ВЛС іюхлт бить првдетавлена в виде композиции отдельных подзадач, токих как: -Анализ операторов. ', -Анализ параллельных процессор. -Апализ участков с взаимными переходами. Решения полученные для отдельных участков ВЛС затем могут быть объединены для структуры в целом. Композиция решений .для задачи анализа операторов рассмотрена в третьей главе. К атому раздав относятся: а)прэобразованил Лапласа плотностей распределения результк-рупдего веса для схем структурного програ?,агаропеш!л: а. і композиции операторов Ч(г.) = a(e)b(s) а.2)опзраторов выбора и альтернативи a(s)-ra(s)+(l-r)S(s); N 'Т2І а.з)итераций Если ft (z >~ производящая функция числа повторений k(o=vki,+k2z2* У Vі , 1=0 то, преобразование Лапласа плотности распределртия i(B)=k(5(-.)) Здесь использованы, обозначения: Я(э)- прэобразованио Лапласа - XI - плотности распределения веса результирующей вэриивд; a(s), S(s), q(s) - преобразования Лапласа плотностей распределения; г, rt, kt - вероятности. ь)результаты для цшслов с произвольным числом повторений и условным прекращением сычислеша. Цикл с пост-условием ~ выходом вперед: Преобразование Лапласа плотности распределения I I - r(b/q j если обозначить то преобразование Лапласа плотности распределения для цикла с пост - условием и выходом назад будет t(s)= r(s)qfc(qP В использовании:: обозначениях р - ьороятяость выхода из цикла, a q=i-p вероятность его продолжения нормальным образом. В третьей главе также получены р лев^я для цикла с пред -условием и различными виходаш, для циклов с различной структурой условия в группе операторов охваченных циклом. Получены формулы для первых двух моментов в рассмотренных операторных схемах. Рассмотрены эквивалентные преобразования циклов для случаев условного выхода. В третьей главе рассмотрены задачи, демонстрирующие возможности рассматриваемого подхода для получения мнохаствешшх оценок индексов производательноота и зффоктившста представляемых процессов. Показана применимость использованного подхода для анализа детерминированных процессов. Четвертая глава посвящена анализу параллельных процессов. В этой связи рассматриваются прої; ссы с пр крещением исполнения в момент исполнения наиболее длительного из процессов, процессы с прекращением вычислений в момент прекращения наименее длительного ироцесса и процессы с условным прекращением параллельного выполнения при достижении некоторого условия. Подход к анализу основап па основном соотношении для прообразозаний Лапласа плотностей р?"пределеьгШ длительностей исполнения (весов) параллельных ветвей ї*-{в ^преобразование Лапласа плотности распределения; для случая прекращения вичислений в момент завершения максимального по длительности процесса; и соотношении, связывающем преобразования Лапласа для процесса минимальной и максимальпой длительности? х"(5}-преобразованиэ Лапласа плотности распределения для случая прекращения вичислений в момент завершения минимального по длительности процесса. В четвертой главе рассмотрены различные частные случаи решения для преобразования Лапласа результирующего распределения веса исполняемого параллельного участка. Ниже приводится случай произвольно - распределенной яяущ ь, и вотви а с преобразованием Лапласа» задаваемым рациональной функцией. а*(в)«ь(в) + здесь a .ej - корни знаменателя, kt- соответсївувдая і-ну корню кратность. . . Математическое ожидание для процесса, звве'-чаодегося в момент окончания максимальной по продолжателыгости исполнения параллельной ватші т -ь + В четвертой глава, рассмотрено обобщение решения на произвольное количество параллельных ветвей. Виведеш соотношения для момонтов распределения веса результирующей вершины, рассмот-репы приближенные решеьля задачи о параллельных процоссов.. основанные на тсгальзованаи схемы т - дамэнтной ятті»ксщ.шцет распределений в классе раийональнш: фущсида. Для рокения задачи .«> - моментной аппроксимации использовано введеішоо в работе представление гиперорлангов'отх распределений с ію:.ющью регулярного разложения с единственным акспонзнциальным этапом, повторяемым случайное число раз ^ С(*)= s х п,-у к '—^ , здесь N СА>Э, i=l,2...N5 У" СА=1, а - производящая функция числа повторяемых этапов *<*>Ic4i-z А. 1 Я. і * Последнее представчение позволило свести задачу m моментной ешпроксимации к основной задаче линейного программирования . На примере задач о борной области и вычислениях, о статической структуре програ: м и динамической памяти показано использование полученных соотношений для решения задач оценка производительности и повышения эффективности. В пятой главе рассматривается анализ вероятностних переходов в программах. Рассматривается процвссц я фрагментах ВЛС с многими точкам. входа и вихолп, параллольгшмл участками, уча^гками с зависимыми повторениями и циклически повторяемый! маршрутами. В качество базовой рассматривается схема с одним поглощающим состоящим, произвольно - распределенным времонем пробивания процесса в состояниях и марковской матрицей переходов. Система уравнений для преобрасовзшій Лапласа плотностей распределения времени лслолншшя боа учпта оэлзржзтс по переходах: ^<*>--^<»)*,,Ло9 І-1 j=l,N-l. Диалогичнал система мозжт бить составлена и для случая, необходимого учета времени на переходах. Показан переход к системам относительно математических ожиданий и дисперсия. Обобщение понятая состояігал приводится для случая с несколькими поглощающими состояниям. Система для преобразований Лапласа (несколько поглощающих состояний) имеет вид aJ.J<m> VJ. 1; здесь J Ъ,о<*> которих J .> - МНОЗиОСТВО состояний, для является достижимым. Пределы \± j(b) при s-»0 определяют і роятноста процесса, начавшегося в і-м состоянии состоянием J. В пятой главо выведены системи уравнений для вероятностей поглощения и система для математических дисперсий. Дальнейщие оОоОчшния кйсьйтсл невозвратных состояния и групп поглощающих состояний. В работе выведены: распределение ( преобразование плотности) времена до первого попадания процесса в 3"' поглощения вычисления ожаданий и {i:,J2,J состояние с номером fc G=(i, .і ), npimajwessisse груш» поглощающих состояний g; системы, описывающие поведение преобразований Лапласа в грушах поглощающих состояний; И далее - преобразование Лапласа плотности распределения перехода к-л в МПОЖОСТВЄ G. >2- \ А (, k.k* : ь(.)- іійіі- 1 - ak(s4,k Пользуясь подобными методами можно описывать поведение процесса как в переходном режиме (до попадання в ' группу поглощощих состояний), так .. в стационарном (в группе поглощающих состояний). Далее в пятой главе рассматривается вероятностная схема с процессом переходов, отличающимся от марковского. К подобным процессам относятся циклически - повторяемые участки программ с потреблением ресурсов (путем исполнения), зависимым от номера повторении. Для подобного процесса виведено соотношение, определяшцее матрицу преобразований Лапласа длительностей переходов после цикла с произвольным числом повторений TfO-Jk^te^kCnCs)!, ї=0 здесь п"-матрица преобразований. Лапласа длительностей п шагового перехода, для которой показано П<п+1>(.)-Й(п)С«)П<.)-ВР+1(.).п-о.1,2... На основе полуденных соотношений выведено преобрас лвание Лапласа плотности распределения веса эквивалентнс^ верзилы: i"=i . . . Здесь v-вектор стартовых вероятностей, а в - единичный вектор -столбец. В работе показано Использование полученных соотношений для оценки эффективности на примере задач: о потоке заданий (для оценки потребления разнородных ресурсов): об ошибке в алгоритме (вероятности, число шагов и время до появления определенной оилбкп). Также рассмотрены другау задачи. Б шестой глава рассматривается более общая вероятностная схема. Дальнейшее обобщение процесса достигается за счет расширения понятия состояния, введения групп состояний, рассмотрения параллельных участков с более сложной логикой организации. В подобных схемах рассматриваются общие случаи условных выходов из циклически повторяемых участков (в том числе с зависшими повторениями), рассматривается прямая и косвенная рекурсия в программах и связанные с ее появлением уравнения, опиши. т& поведение процессов в ВЛО. Несколько альтернативных выходов из цикла с прозе эльным числом повторений. Определение преобразований Лапласа распределения длительностей (веса) при завершении участка по заданному маршруту. Мрш) . Вероятности завериения участка на заданном маршруте: V р — Рекурсия в программах и уравнения в задачах о циклах с произвольным числом повторений. 3 работе показано существование уравнений и систем уравнений, описывавших процессы с прямой и косвенной рекурсией. Прямая рекурсия с бесконечным уровнем вложенности: -l(e)»Mpa(»)+qb(B)a(a)) Косвенная рекурсия с бесконечным уровнем вложенности: - і? - ( m l-q.=) p. . ,Viel..m Выше использованы обозначения: - ax(s) - преобразование Лапласа длительности исполнения процесса иА(з) - преобразование Лапласа распределения длительности перехода на участке без рекурсивных обращений, ях - соот-ветствувдая вероятность продвижения; 7j(s) - лрообразованио Лапласа распределения длнтелъгїсти перехода нэ участке с (косвенно) рекурсивным обращением к процессу j; р± .- соотвотствутацая вероятность выбора j-ro путл. Рекуррентные соотношения для случая процесса с ограниченным уровнем вложенности. T(iis)=k(pa(s)+qb(s)a(i + l;s)) ^((д;5)=к(р2(5)+ЧЬ(Б)) Здесь использована обозначения 'Uus) - для преобразования Лапласа плотности распределения времени исполнения процесса на уровне вложенности ie 1.-N. Для оценки поведения процесса необходимо определить ЯхО;*)=Я(в). Для всех рассмотренных схем приводятся соотношения для моментов распределения веса аквивалентных вершин. В иестой главе -аюш рассматривается обобщение класса вероятностных процессов в ВЛС. Последняя задача, по сути являясь задачей композиции отдельных репышй, обобщает проблему анализа в целом, представляя Формальную систему правил для описания вероятностных структурно -инвариантных процессов В ВЛС. Для пояснения изложенных положений уместно привести пример гипотетической структуры с выведэнным структурш-ишариантным определением процесса в ВЛС. - 1Є - __*_ ^ і. Ч/> > йч^'У а~ -с* ->J1-J >г Ач 5 " <> *'*. «Xw *«іьі<і і*' ^ П^ЛІ *1 m. hn.i Bepasrwerw» - лвгичеснм-спукїуя» В сольной главе рассматриваются оптимизационные и шита-' циогоше Задачи, использующие вероятностно - логические структуры процессов для решения задач оцеш;и производительности и повышения эффективности. Результата анализа вероятностно-логической структуры алгоритмов могут быть использованы для .решения задач повивіопия производительности. Такие задачи часто являются оптимизациошщш и относятся либо к настройке параметров ШО, либо і структуро процесса обработки. Часто постановку оптимизациошшх задач приходится производить с учетом описания структурно - инвариантного процесса потребления ресурсов совместными распределениями вараятноете? Совместные распределения вероятностей для множества исполъзуемих ресурсов, является основой для стоимостных расчетов, или, в болев общем виде, - основой для ' построения оптимизационных моделей. В этой связи в работе рассматриваются некоторые оптимизационные задачи, позволяющие определить, касаащийся ВЛС подход к проблемам структурной оптимизации в вопросах, связанных ' с производительностью. 1)0сновной изучаемый в этом контексте вопрос мозшо сформулировать так: какая виртуальная ВЛС обеспечивает максимальную производительность (минимальную стоимость исполнения), яа данной установке ? Решение этого вопроса тесно связано с производительностью аппаратуры и собственно ВЛС програш. а Щонятие виртуальная ВЛС формулируется в работа с учетом результатов оптимизация структуры в системах массового обслуживания: СМО с обратной связью и СМО с несколькими обслуживащиш аппаратами. ь)в случае рассмотрения ВЛС как структуры виртуальной машины потока данных моаго утверадать: ь.і )для допустимого множества исходных данных и конкретного характера поступленния данных в виртуальную машину, существует виртуальная ВЛС, обеспечивающая наиболее эффективный режим обработки; ь.2 )структурно-независимые параметры виртуальной ВЛС шгут бить установлены методами нелинейной оптимизации. 2)Структурная оптимизация ВЛС применяется во многих приложениях, в частпоста в вопросах оргаїшзаціш операциошшх систем ( программа ввода - виводи (в том число для объектно -ориентированных систем), организации виртуальной память, построения систем с распределенными данными и программным обеспечением). В этом случае речь вдет о использовании ВЛО для пераструктурирования программ. Пореструктурігроваїшо приводит к оаіутимому выигрышу в эффективности в случае пропвленші пришила локальности (Для распределенных систем в размещении программ и ..чанных). Пероструктурирование имеет смысл для программ исполняемых достаточно часто. ''. таїсим программам относятся программы, составляющие ядро операционных систем, системные утилиты, компиляторы, программы, поддерживающие коммуникацию в расприделешшх си,темах. Иногда имеет смысл переструктурировать распределеннув базу данных или создать дополнительные копии ее подструктур. Одна из задач, связанных со структурой может быть сформулирована в форме задачи о переносе работы в ВЛО. Пусть задана сеть acv,s>,где v = {vi,v2, vn> - множество вершин, a s множество связей. На сети определены маршруты: P1(V(i,l),V(i,lJ...V(K(i),D), i=l,2...М. I)Система относительно математических ожиданий і^.р.,...?,,, - f р= {Р^,Р2...р"м} задает вектор математических ожиданий длительностей исполнения путей; 2)Система относительно діпп&рсий Dpi,Dp2 DpM - f OitF|D,a1*k1b1.a2+k2b2....eN*kMbN}-0 1 1=1,2. ..Г1 D=CDpi,Dp2 Dp|1) задает вектор диснорсяи. На объем переносимой работы накладывается ограничение: ^+5.,+ ...+5^0 критерий минимума среднего взвєшешюго веса путей : критерий минимума * +ка : 1/2 Критерий "а" позволяет учесть стоимость использования ресурсов сt. Критерий "ь" учитывает разброс данных относительно математического оаидания, что дозволяет рассматривать . его как оСаспачкващяй шпшгальное средчае вреші в условиях акстрэ- КОЛЬШХ E8J*py30K. 3)форкализацгя програчвд, привязанной к некоторой аппаратной среда, «вягена с представлением гадаощрувдих ВС в видэ систем щи сетей весового сбелуетпания. Сета ВЛС позволяю рассматривать взаимодействие алгоритма с аппаратурой как взаащдей-стше системы кассового обслуживания а нагрузки. Совместное ис-сдадоэанвб моделей ВС в алгоритма проводится как аналитически, так и с подащь» имитационных или- гибридннх моделей. - Метод имитационного моделирования для анализа и настройки аффектишоста процессов обработки- информации существенно дополняет аналитические метода рассмотренные выше. Во многих приложениях программная имитация является единственнш пригодным методом для решения задач анализа, ', структурной оцашсі и шоора, оптимизации и настройки систем. В работе, на база разработавши системы моделирований,, исследуется использование модвдирущвх програш для раненая оптимизационно -имитационных задач. Особенностью $ рмируемого подхода является совместное применение для исследования как аналитических, т«~< и имитационных моделей. Последнее требование делает веобгодамым наличие в система модэлароЕьння объектов и средств управления процессом . щдэдировадал, обесн&чнвавдих достаточно высокую степень форшшшцаа весдадуешх процессов. С другой сторона, юойодймым является обеспечений системи ноделировашщ средствами сопрякешя'_..;' с ыатеаатяческима в отшизащюшама библиотеками, программами - для численных расчетов, статистической обработки результатов ' ' эксперимента. Эти требования в известной степени являются прота-шрачпвуга,. .its ишюлієееє а pastas работа позволило создать систему нодеяфоввяия, обладакдув достаточно вигасим уровне- формализма для'сшскэшя трудоешіоста з разрасотио я программировании моделей, ш оо&сгачнваэдую в то зм время гибкость использования.програмишк средств л современник матоматичеысих библиотек. Для системи моделирования разработаны и реализованы средства автоматического сбора и лэрвячиой обработки статистики, средства отладки» диагностики ошибок и встроенный диалог для наблвдеїшл за динамикой цоъэдепия модели и управления процессом моделирования. Пример модели для исследования кшрдинированпого продвижения запросов в шогоканалъпои системе .гряводится ниже. program AssTest2; uses SIMPAG, DIALOG, CRT; Var PROC j PSTORACE; a і PQUEUE; KewSTORAGEC PROC, ' PROC '",5>; InitCreateC1, О; wliile SYSTIME < 1000 do begin case SYSEVEKT оГ 1 > CrealuC...>; Z t bog in TRANS".PIC11 I» truncCRandABC3,10,Vll»>; SplitCTRANS*. Pill 1,3) j end; 3 t pegln XnQwueCQ); Trans*.Prl21 a« RandexpC. ...Ї} end; t EnterCProc>; » DelaytCMlnCTrans^.Prlll.Deita»; a * bt-gir» teaveCРгоеЭJ if Tr»f»~.Prltl « О then Hexl <0>j 7 « if Trans*. PRT PrtyHax thun KextCOi else . b«?gi n If RaiuJOlCVim < O.OOl I.hen begin < ОЕЯбКа > Trans~.PrI13 s« Oj Par inAnsC PARKS, 1 > ; PriorityCPrtyKax>| else D' ffer; end; t HextC4>; t AssembieCTrans'".Pit 11); 10 I if TRANS". PRTK О Pi tyttax then OutQueueCOJ} 11 : Destroy; **nd; Ислвдованив возможностей разработанной . при вшкишвшшк дассертацйош«й работа системи моделирования, ее использование при выполнении ряда НИР, а также опыт применения спетот моделироваїшя другими предприятиями н организациями показали надежность разработанной системы, эе виажоо.по сравнешш с существующими системами моделирования быстродействие, удобная программный интерфейс и достаточный уровень нре ^аботки управляющих структур система для представления моделей эффективности процессов в вычислительных системах. ОСНОНШЕ РЕЗУЛЬТАТЫ РАБОТ!! В диссертационной работе решена крупная научная проблема разработки методов исследования и создания средств повышения эффективности функционирования вычислительных систем, имэщоя большое теоретическое и прикладное значение во- многих : областях . теории вычислительных систем. В работе показана применимость научных положений диссертации для широкого споктра приложения с применением еджкнч> методологиче< :сого подходе. 3 процессе выполнения работы автором получены сладущп» основино результати: 1)На Сазе обобщения работ в области оценки эффективности, анализа производительности и-организации вычислений азтором рассмотрена Вероятностно - Логические-- Структури (ВЛС), как класс объектов, отря'я»щих особенности взаимодействия отдельных про-грамм и аппаратуры с учетом случайного характера развитая процессов. 2)"^ работе показано использование разработоншіх в класса ВЛО методоп для решения широкого, класса задач организации вычислительных процессов, а также для решения ряда проблем, связанных с вибором структуры технических сродств и структур программного. обеспечения. 3)С использованием разработанных методов показана еоз!,юж-пость управления показателями эффективности исполнения системних процессов за счет выбора их виртуальной структури.. Использование в качества сбобщг гаого показателя эффективности стоимостного хри""»рпя даст возмоаюсть учета экономически»- показателей функционирования проектируемых дати модернизируемых систем. 4)На основа разработанных моделей показана применимость ВЛС для решения задач анализа индексов производительности и оценки зіМективиости исполнения програш построенных по схемам структурного пріфаммирования, получены соотношения, учитывающие прездевремепков завершение циклов и перекрестные перехода. 5)Шказана возможность использования ШЮ для определения ізирокого класса детаршийрозашшх и ввроятиостних моделей процессов обработки ипфораацня, за счет определения на вероятностно - логических структурах вероятностного процесса с "памятыг о предыдущей истории, влозгеяпнш переходами, прямой и косвашгай- рекурсией. S)B рамках аспользованяих формализмов, показаны способи обобщения решения для случ я композиции отдельных моделей структур, а тага» способы использования обобщенного руления для получения множественных оценок изучаемого процесса. 7)Дяя решения практических задач разработаны и исследованы - га програйте средстве построения имитациояных моделей, отлкча-нщнеся от икогацихся машинной ыезазксдаосгь» (переносимостью) сравнительно боле з высоким быстродействием; а такта оригинальные аналитические, имитационные и оптшгазационкыо программные модели, широко исаользуицие возмо;шости современных математических библиотек. " . . 8)Всв результата диссертация в виде методик и программных састем внадрзіш в практику каучко - последовательней: работ предприятий НЙИАА, НЕИСА. ЕРНИИММ, ЕРНШОУ, ЕРІ5ИС, а такхо используются и учебном процессе. Степень обоснованности научных полоаонаа, заключопия и выводов подтверждаются болыл»; объемом ешолиэншх теоретических исследований: для подтверждения подученных аналитических соотношений использовались различные подхода. Сравнению результатов и проверке их правильности в работа отведено особое место. Получокше разработанными .методами результати сравнивались с' имеющимися, опубликованными и печати отечествешиш и зарубззвимл , учеными. Ссылки на публикации, приводятся в тексте диссертации. В использовании программных средств имеется накоплении!! опит их эксплуатации, который показывает нзде&пость разработанных программ к возможность их использования для реиешя сложных задач оценки ОЗфЙКїИ^НОСТИ.. Основные положения дисортзида отражены в следующих работах. і. Виноградов В.Й., Марков А.А., Попов А.К. моделирование специальных распределений // Вычислительная техника. -U., """*76, -с. 49-53.-(Тр. ШГУ„ «217). г. Марков А.А., Маркосяп М.В. Вопросы исследования структур памяти.- В к.: Развитие теории и техники средств хранения ш4ормацпиі Тезиси докладов всесоюзн.коиф, -М.-Рига, 1980, С.72-7Б. з. Марков А.А., Каркосян М.В. Выходящий поток системи массового обслуживания// Исследование и проектирование упрашяащях вычислительных комплексов.-Ы., 1982, -с.П-ЛЗ..-(Тр. ВЗГШ/ШЗ) «. Парков А.А., Маркосян М.В. Интерактивная '.система исследования одного класса вычислитеяьшге процессов/ МВТУ. им. Н.Э. Баумана.-М., 1983. -32 с- Д&п. в ПИИЭИР 10.03.83, Я 3-7239. 5. . Марков А.А., Тархвняп А.Г. Использование системи Марков А.А., Тархонлн А.Г. Концептуальная схема бази моделей систем» иерархического проектирования информационно - внчис-литолышх систем// Проектирований вычислительных w-mm и систем.-Рязань, 1987. -с.П4-П7.-(Межвуз. сборник научних '.-рудов). Марков А.А. Стратегия хранении и замещения данных в объентпо - ориентированных мультипроцессорных ВС// Управляюче мульти-микропроцессорные системи. -U.: МИРЭА , 1987.-с.65-71. -(Межвуз. сборник научных трудов). е. Марков А.А., Пирумов Н.Р., Гудзенко Д.В. Применение общецэлевоя системы имитационного моделирования СИМПАС в полунатуршис моделях //Техническое .и програьмюе обеспечение шгалвксав полунатурного моделирования: Тез. докл. Всесохш. и.-т. конф. -Москва, 1988, с.П-14. *?. Марков А.А., Тархшян А.Г. Экспертные оценки в имитационном моделировании информационно вычислительных систем/ЛЮТ" тциошше эксперименты о моделями сложных систем: Таи. ДОКЛ. IV Всесошн.н.-т. школи цикла "Системы управления и методы их моделирования". -Калининград, І98У. с.37-39. ю. Марков А.А.., Пирумов Н.Р. Использование метода макромодвлэй І2. Марков А.А., Пирумов Н.Р., Гудзенко Д.Ю. Общецвлевэя система имитационного, моделирования на Паскале /НОТУ им.' Н.Э. Баумана.~ М., I989.TII0 С. -Деп. В ВИНИТИ 15.08.89, .Я 5500-В39. із. Марков А.і.і,. Медведев Н.В. Моделирование технических систем с использованием языков високого уровня» Учзбн. пособие по курсу - 7.7 - "Моделирование технических систем" .-ГЛ.:Изд.-во МГТУ,' І99І.-30 с. 14. Марков Д.А., Пирумов Н.Р. Применение макршоделой е опти 15. Марков А.А., Тарханян А.Г. Расширение возможностей Петров В. Я., Марков А.А-, Маркосян .М.В. Иерархический иатод исследования структур вычислительных систем к ко'яшокг-ш// исследование и проектироваїше 'управляющих ' вичшхгалелъаых комплексов.-М., 1930, -с.6І-Є6.-(Тр. ЮПИ, #128) . Петров В. Я., Марков А.А., Маркосян И.В., Определение параметров потоков в системе // Исследование и проектирование управляющих вычислительных комплексов.-М., 1980, -с.66-69.-(Тр. юпи, тгвУ - їв. Петров В.Я., Марков А.А., ' Маркосян М.В,- Исследование промежуточных потоков в многофазных системах ' . массового обслуживания //_ Исследование и проектирование увтяшлящах внчислителышх комплексов.-М., IS80, -с.28-32.-(Тр. ЮПИ, Щ8) if- Сурков Л.В.,. Марков А.А., . Медведев Н.В. Моделиррващіз' информационно - вычислитольныж систем на', языке gpss» Учабн. пособие по курсу "Вычислительные системы".-М-:МВТУД986.-31с. Марков А, А. Операторные 'методы анализа производительпости нрограіям/МГТУ им. Н.Э Баумана. -Вив. й\К3721&\- Ы.,1993. -207 с, Марков А,А. Программная 'имитация информационных процессов ЛИ им. Н.Э Баумаїи.- Ипв. й W36775. - 11.,1932. -221, С.' .
W(P)=V WfV(P,i>>, для V Vj є* Ч Л
1^1 k
р.= И Х=тахС\.>.
jt«)L*j,A,jte>> (iJ)»
L jrl
і от момента начала до завершения;
Я'*Д*У "V
Its*-
С.Р. * Г » min (а )
F * min (Ь)
HowGUEllF.C Q,* Q };
end; . ;.'.--
SO ! for I := 1 to TRAMS. PI [11 do
end;
имитационного моделирования ШЛИ С для решения оптимизационно
иштционтк задач/ МВТУ им. Н.Э Баумана. -М., 1987. -24 с. Ден.
В ВИНИТИ 10.12.87, В 8630-В87.
. для моделирования разномасштабных. систем //Имитационные
зкогорюцептн с. моделями сложных систем-. Tea. докл. w
Всесоюзн.я.-т. школы цикла "Системы управления и метода их
моделирования".- Калининград, 1939. С.І4-ІЄ.
„її. Марков А.А., Пирумов Н.Р., Гудзенко Д.В. Графический
процессор для представления структур Технических систем и
.формирования их моделей //Математическое . обеспечение систем с
машинной графикоа: Тез. доісл.. у научно - техн. семинара, -Ижевск,
I988r с,24-2в. ..-:'. *
мизационно - имитационных задачах.-В.існ.: Крупномасштабные систо
ла. Моделирование развития и фуякцаоїшровашл. -Ы.:11зд.-ш- ИПУ,
I9S0. с.88-94.
имитационного моделирования при использовании . методов
искусственного интеллекта//Техпичёские средства и ма- матическоо
обеспечение ЭВМ и систем.-Ереван.: ЕРГО1, І99І.- с. 79-83. -(Ыежв.
сб. нвучн. трудов)