Введение к работе
Актуальность проблемы. Производительность вычислительных систем (ВС) и сетей является однин из основных критериев их эффективности и качества, принимаемых во вникание при проектировании, производегве, определении и расширении конфигурации и настройке в процессе эксплуатации, т. о. на протяжении всего жизненного цикла ВС и сетей требуотся оценка их производительности. Целью оценки является получение информации о значениях индексов (показателей) производительности ВС или сети при заданных параметрах рабочей нагрузки и конфигурации системы. На начальном этапе проектирования ВС и сетей, когда анализируется большое множество возможных архитектур, наиболее притягательным и эффективным является аналитическое моделирование, обеспечивающее высокую скорость и минимальную вычислительную стоимость оценки показателей производительности, а также достаточно достоверное определение узких мест и основных факторов, влияющих на производительность.
Любую ВС или сеть можно представить как совокупность большого множества разнообразных ресурсов (вычислительных, информационных и коммуникационных) к запросов, возникающих в случайные моменты времени и конкурирующих за использование ресурсов, образуя очереди. Поэтому в качестве естественных аналитических ноделей ВС и сетей с начала 70-х гг. стали активно и широко использоваться сети взаимосвязанных очередей, называемые также сетями массового обслуживания. При таких моделях показатели производительности ВС или сети выражаются через стационарные вероятности л(1) состояний сети очередей, идентифицируемых матрицей длин очередей 1=|1 I заявок каждого класса j к каждому узлу і. Лля облегчения расчета стационарных вероятностей обычно предполагается экспоненциальность распределения вренон обслуживания во всех узлах сети очеродой. Большинство сетей очередей, моделирующих ВС, Являются замкнутыми с фиксированным числом заявок каждого класса; это связано с необходимостью ожидания ответа на запрос перед выставлением нового запроса.
В общем случае при анализе замкнутых экспоненциальных сетей очередей (ЗЭСО) требуется решать громоздкую систему уравно-
няі глобального баланса относительно стационарных вероятностей. Поэтому особое место средх моделе» ВС х сетей занимают иульти-плхкатквные ЗЭСО. стационарные вероятности которых описываются явной мультипликативной формулой: я(1) - G"1 у] к (1..)# где
к - простая функция от лляиы очередя заявок 1. класса j к узлу i, a G - функция разбиения (Ф?), приводящая к 1 сукну произведений к по всем возможным состояниям I и называемая также нормирующей константой. К настоящему времени мультипликативность доказана для широкого спектра ЗЭСО. применяемых для моделирования вс и сетей.
в отношении потребности в вычислительных ресурсах определяющее значена» в расчете показателей производительности имеет вычисление ФР. Когда число заявок N в ЗЭСО и/или количество ее узлов достаточно велико {эта ситуация называется случаем большой размерности), что является весьма характерным для моделей современных ВС х сетей, при вычислении ФР точным» методами возникают проблемы, связанные с чрезвычайно большой трудоемкостью и ресурсоемкость» расчетов, а также с необходимостью применения масштабирования , и многократного округления, которые могут вносить существенную погрешность.
Кардинальным способом преодоления возникших трудностей является применение асимптотических методов для анализа ФР. что дает возможность получать явные зависимости значений показателей производительности от параметров конфигурации ВС (или сети) к рабочей нагрузки,, отражающие характер влияния и степень значимости каждого из этих параметров на производительность. Простота получаемых формул и, следовательно; минимальные требования к вычислительным ресурсам, предъявляемые при расчете показателей ВС (сети) в целом или отдельных ее компонент по этик формулам, обеспечивают высокую эффективность при многопараметрическом анализе, обуславливающем многократное решение модели при различных сочетаниях входных параметров.
Ошибка получаемых асимптотических приближений для показателей производительности стремится к нулю при возрастании размерности ЗЭСО до бесконечности (Н->«). Однако на практике требуется оценивать значения характеристик ЗЭСО, хотя и достаточно большой, но все же небесконечной размерности N. поэтому вопрос
о конкретной виде зависимости ошибки получаемых приближений от размерности ЗЭСО является весьма актуальным. Этот вопрос не решается в большинстве из работ, посвященных асимптотическому анализу ЗЭСО, а без ответа на него нельзя предсказать оценку погрешности и, следовательно, быть уверенным в корректности получаемых результатов.
В этом отношении несомненное преимущество имеет метод Лапласа, позволяющий получать асимптотические приближения, непосредственно включающие в себя оценку порядка кх погрешности как конкретную убывающую функцию от размерности ЗЭСО N. Суть этого метода заключается, во-первых, в представлении формул вычисления ФР и характеристик мультипликативных ЗЭСО в виде интегралов Лапласа: 1---1 Р(х) expl-Ng(x)I dx; и во-вторых, в применении
классических методов асимптотического анализа этих интегралов для получения ведущего члена асимптотического разложения и оценки величины остальных членов, что дает в результате требуемое асимптотическое приближение, включающее в себя оценку погрешности. Ранее методом Лапласа анализировались лишь простейшие ЗЭСО, что обуславливалось недостаточной развитостью классических методов асимптотической оценки интегралов Лапласа, пригодных для использования лишь в некоторых частных случаях. Развитие метода Лапласа, проводимое в диссертации, позволит применять его для анализа почти произвольных мультипликативных ЗЭСО большой размерности.
Целью диссертационной работы является разработка методов асимптотического анализа показателей произвсдстельности современных ВС и сетей, моделируемых мультипликативными замкнутыми экспоненциальными сетями очередей большой размерности, на основе применения и развития метода Лапласа для радикального уменьшения трудоемкости и обеспечения малой погрешности оценок производительности ВС и сетей в широком диапазоне значений параметров их нагрузки и конфигураций.
Методы исследования. Основным методом анализа производительности ВС и сетей, применяемым в диссертации, является асимптотический метод Лапласа. Лля построения и точного анализа моделей ВС к сетей широко применяются различные методы теории систем и сетей кассового обслуживания ж комбинаторного анализа.
Наконец, при оценке интегралов Лапласа активно используются методы таких разделов математического анализа, как анализ бесконечных рядов, аналитических функций и квадратичных форм.
Научная новизна работы заключается в разработке комплекса новых математических методов оценивания показателей производительности современных вычислительных систем и сетей с различными архитектурами на основе обобщения элементов теории асимптотического анализа для расчета характеристик моделей большой размерности за счет применения и развития метода Лапласа в ориентации на получение асимптотических приближений, в явном и простом виде отражающих зависимость показателей производительности исследуемых вычислительных систем и сетей от параметров их конфигурации и нагрузки с заранее известной точностью.
Практическая ценность работы. Результаты асимптотического анализа, полученные в диссертационной работе на базе метода Лапласа, как обобщенных мультипликативных ЗЭСО, являющихся типовыми моделями ВС и сетей, так и конкретных моделей многопроцессорных и мнсготерминальных ВС, центра коммутации сообщений с секционированной буферной памятью и локальной сети архитектуры <клиент-сервер>, позволяют научно, обоснованно, с высокой точностью и минимальными вычислительными затратами решать такие важные задачи начального этапа проектирования ВС и сетей, как оценка сбалансированности архитектуры и конфигурации ВС и сети; определение «узких мест>, степени загруженности устройств ВС и сети и, следовательно, возможных источников повышения производительности, наряду с оценкой показателей производительности ВС и сетей, разработанные асимптотические, методы позволяют проводить сравнительный анализ и выбор стратегий доступа к неоднородным критическим ресурсам многопроцессорной системы, применяемым для синхронизации параллельных процессов, с учетом разнообразных особенностей ее архитектуры.
достоверность научных положений, математических теорем и утверждений, выводов и практических рекомендаций подтверждена корректным обоснованием и строгим асимптотическим анализом математических моделей рассматриваемых вычислительных структур; результатами точных расчетов моделей, а также имитационных и натурных экспериментов; результатами практического использова-
.' ( 'J 886T '41Y -vuuy) хвхеэ нгшчиехнггэяычв on йзнахвз-гігохга ссюзвза в-ст -
'{'і S86T 'HodojHHeac) «ічхех -эяэ єпнчігоіяиояьпа егийоээейойноасня» вконт "єаозоза н-g -
.' ( 'J Е86Т 09Н«ш/їГ) /от t/nxaaeed я mma вянтйГебэ И'аноігрогіи ои вяпнейойнон -єаозвза -
{'J Є86Х 'ff-edjHHHsu)
:XMnttHade<{:HOH Я X'ed^HSKes 'ХННН-ВПэаОЭ XKECJjftfatfS ВН ЧЗИІГВвГСҐ'ВИНОН
moptsd ттзхчігХеай я ввнежоїгон опяаоизо *ru.ogsd smnegodir?
яяносіїґвна о гшзігаягїахен яннЬаХахэхэахооэ OHoSwdoaxffoii 14x09 -sd яопнояігвігіваздіґ aoxax4if. вхЛхяхэня о.іо>ізеьясяф-онйаноя -ня олонэаояэон osshodu graigeh/t a RHodffeiio 'хнчхтгхэ хпннвигэаьоа -онк и йїіф'вй.іонои п вкинваомяіг9^ио 'йкггехгівззпїї пхтзхчиЛеал asxaasBd олаидвнчітеП' во anjexBdxo чхаыов'ойцо я ихвэ дохе uxHBHdaa oJoinu-sh-cHbadeu <вхэен вяне^> чхианпа оииаовеои 'аяігех -deooaff a xrMHBiop'Bde'Bd 'динвхсзшдиЗы хинзвьяхохцииз'в внивнвннйц '4d вн/Cjr gonHeaxsdBsr^aoj а -edeada3-xHekim> РкіЛхнвхяхй'й нхеэ дончігехиггзикгга-оннояігангіофня goHaebHxdBdsH иинеКеоэ «du ян-ааое -чионэи яітд nxogsd jonHOKtrexdassaH гивхчігЛєагї 'o-zox anoda axsoxxeosdised 50НЧІГ8МИНЯН adu ЭЯП XRHH«aodHdjaiHH »HH-B3odHX>ieodu оаонсииэе яномвгїа 9*Hefcred>ro3 аонкаахзоїшСз оияаоУэЛро охьихвн'еіі фаншона пиохзяоїґои н udffK ojOHdoooenoduojoHH ojs 'эм йаігеион ееяігентг охомовьяіошкяза ічнохек Mnrreidesoasr a anHH-EXCHjsdssd гчнявоєчи -оизи яіляр вниіґохаи а '«ииззо^ ниггаєих'вигіофни> nwH-Bdaodu иомзэь -анхех-оньХтзн йОлзн-еяиирХцова x-BMHsd в аежненцоціча 'HHfirBeazrBad 30HHHcdjodu за >пзн ЭЗЮТИЭУ "аханші ил(0ЯП) 8нквїВ90оЬ ияйях^ниом aodxiteti xi4HHuaodHdjeiH5j HX30H4irexaaoaeHodu иннэпо иииїГохви еих -ogsdesd adu нігпган аянейО!Шоа еоншш ааігоряш 'exogsd доннояпвх -йоззиїґ а агшнеь/Сігоп 'дахаз я за нхзончігахяіґоаеж^ц вгяігенв ruf -охам вянзаьяхохцнкзу *aoxBxi»Xesd эинэааэпя я клпвекивзл Bxahs-ed хи воиохеи хииээьихох -иияов я jjeueffoH HHni2xd933H» о хпннваоїгвиззя я хтешвжоїгїгасіц вин Международная конференция по локальным и городским сетям связи Международная конференция и Школа «Вычислительные сети -Э5> (Гурзуф, 1995 г.); а также на Всесоюзных и Носковских конференциях молодых ученых н специалистов. Публикации. В изданиях, рекомендуемых ВАК для опубликования научных результатов докторских диссертаций, непосредственно по теме диссертации опубликовано 25 печатных работ, в ток числе одна монография. Структура и обьем работы. Диссертация состоит из введения, восьми глав, заключения, списка литературы и приложения. Обший объем основной части работы составляет 234 страницы машинописного текста, 24 рисунка и 22 таблицы. Список литературы содержит 168 работ. Приложение, содержащее доказательства основных теорем и утверждений диссертация, занимает 101 страницу.Похожие диссертации на Асимптотический анализ показателей производительности вычислительных систем и сетей на основе метода Лапласа