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

М'Б оа

2 6 ФВ ^

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

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

Ляхов Андрей Игоревич

АСИМПТОТИЧЕСКИЙ АНАЛИЗ ПОКАЗАТЕЛЕЙ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ НА ОСНОВЕ МЕТОДА ЛАПЛАСА

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

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

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

Москва - 1996 г.

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

Россм1ско{

Официальные оппоненты:

доктор технических наук, профессор Бочаров П. П. доктор технических наук, профессор Брехов О.М. доктор технических наук, профессор Игнатущенко В.В. Ведущая организация - Институт проблем передач информации РА!

г.Москва

Защита состоится- "г. в часов на засе-

дании диссертационного совета № 2 (Д002.68.01) Института пробле; управления РАН по адресу: Москва, 117806, Профсоюзная ул. , 65. Телефон совета: 334-93-29.

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

Автореферат разослан 1996

г.

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

к. т. н. , с. н. с. Е. В. Юркевич

общая характеристика работы

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

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

В общем случае при анализе замкнутых экспоненциальных сетей очередей (ЗЭСО) требуется решать громоздкую систему уравне-

ний глобального баланса относительно стационарных вероятностей. Поэтому особое место сред* моделей ВС и сетей занимают мультипликативные ЗЭСО. стационарные вероятности которых описываются явной мультипликативной формулой: л(1) - G"1 у] icj( * где

<cj( - простая функция от длины очереди заявок 1.^ t класса j к узлу 1, a G - функция разбиения (Ф?), приводящая к 1 сукну произведений по всем возможным состояниям X и называемая также нормирующей константой. К настоящему времени мультипликативность доказана для широкого спектра ЗЭСО, применяемых для моделирования вс и сетей.

В отношении потребности в вычислительных ресурсах определяющее значена» в расчете показателей производительности имеет вычисление ФР, Когда число заявок N в ЗЭСО и/или количество ее узлов достаточно велико {эта ситуация называется случаем большой размерности), что является весьма характерным для моделей современных ВС ж сетей, при вычислении ФР точным* методами возникают проблемы, связанные с чрезвычайно большой трудоемкость*» и ресурсоемкостью расчетов, а также с необходимостью применения масштабирования , и многократного округления, которые могут вносить существенную погрешность.

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

Ошибка получаемых асимптотических приближений для показателей производительности стремится к нулю при возрастании размерности ЗЭСО до бесконечности (N->«°). Однако на практике требуется оценивать значения характеристик ЗЭСО, хотя и достаточно большой, но все же небесконечной размерности N. поэтому вопрос

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

В этой отношении несомненное преимущество имеет метод Лапласа, позволявший получать асимптотические приближения, непосредственно включающие в себя оценку порядка их погрешности как конкретную убывающую функцию от размерности ЗЭСО N. Суть этого метода заключается, во-первых, в представлении формул вычисления ФР и характеристик мультипликативных ЗЭСО в виде интегралов Лапласа: р(х) ехр£-Мд(х^ йх; ж во-вторых, в применении

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

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

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

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

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

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

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

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

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

ресурсоехкости.

Кроме того, результаты диссертационной работы былк использованы при создании иерархической информационно-вычислительной сети архитектуры «клиент-сервер» в Государственной Думе РФ. Применение асимптотических приблкх<ениЕ, разработанных в диссертации, позволило выявить «узкие места» первоначального варианта этой сети и определить стратегию ее дальнейшего развития.

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

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

Апробация работы. Основные полоиэння в результаты работы докладывались на следующих совещаниях, семинарах к конференциях

- 2-е Всесоюз. совещание «Автоматизация проектирования и конструирования» (Ленинград, 1983 г.} .

- Всосовз. конференция по проблемам создания ВЦКП и развития АСУ (Душанбе, 1983 Г. )?

-6-а Всесоюз. школа. «Многопроцессорные вычислительные системы» (Звенигород, 1385 г.);.

- Всесоюз. школы-семинары «ЕС ЭВМ-85» н «ЕС ЭВК-87» (Москва);

-2-я Всесоюз. конференция по актуальным проблемам информатики в вычислительной техники «Информатика-87» (Ереван. 1987г.);

- 13-я Всесояз. школа-семинар по вычислительным сетям (Алма-Ата, 1988 г.); ■ ■

- Международная конференция по локальным и городским сетям связи «ЬАЫ & МАЛ» (Киото, Япония, 1994 г.)/

- Международная конференция и Школа «Вычислительные сети -95» (Гурзуф, 1995 г.);

а также на Всесоюзных я Московских конференциях молодых ученых и специалистов.

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

Структура к объем работы. Диссертация состоит из введения, восьми глав, заключения, списка литературы и приложения. Общий объем основной части работы составляет 234 страницы машинописного текста, 24 рисунка и 22 таблицы. Список литературы содержит 168 работ. Приложение, содержащее доказательства основных теорем и утверждений диссертация, заникает 101 страницу.

основное содержание работы

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

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

- многопроцессорных ВС (МВС) с полносвязным интерфейсом (п. 1.1), с многошинной коммутацией и со спецпроцессорами (п. 1.2);

- многотерминальных ВС с развитой подсистемой внешней памяти (п. 1.3); .

- ИКС с разными алгоритмами распределения буферной памяти (п. 1. 4) ;

- локальной сети архктектуры «клиент-сервер» (п. 1. 5).

В п. 1. 1'показано, что основной моделью, используемой для оценки показателей производительности МВС с полносвязным интерфейсом, Н однородными процессорами и неоднородными модулями памяти является мультипликативная ЗЭСО П (И,т,р) с N заявками од-

п

ного класса, состоящая из центральной 13-станции и п групп од-ноканальных устройств (ОУ). Разбиение на группы осуществляется так, что группа 1е1,п состоит из ш^ ОУ, каждому из которых со-

ответствует одинаковый фактор нагрузки р4, равный отношению произведения параметра 15-станции X и вероятности доступа к интенсивности обслуживания ОУ. Приведены точные формулы расчета основных стационарных характеристик этой ЗЭСО: среднего числа Ьо заявок в центральном узле, отражающего среднее число активных процессоров Р^; среднего значения Ь" и дисперсии длины очереди к группе 1 модулей памяти (ОУ); среднего числа занятых модулей этой группы И,. Получены формулы, сводящие расчет ЗЭСО с несколькими 13-станцияни (включаемых в модели МВС для описания работы модулей локальной паняти) к анализу ЗЭСО Пп(И,т,р), что позволяет далее в диссертации рассматривать модели только с одной центральной 13-станцией. Прк рассмотрении МВС с неоднородными процессорами, разделенными на v групп, модель п (ы,ю,р) преоб-

п

разуется в ЗЭСО с V классами заявок, также состоящую

из 15-станции и п групп ОУ.

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

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

индексами производительности такой ВС являются: среднее время ответа на запрос с терминала; пропускная способность подсистемы ВП а целом я ее отдельных компонент, коэффициенты использования устройств ЭВМ, средние времена доступа к отдельным компонентам ВП и др. Для оценки этих индексов производительности М-терминальной системы в п.1.3 предлагается набор моделей, применяемых в зависимости от степени конфликтности доступа к КВВ я от наличия буферной памяти в устройствах управления. Показано., что эта модели эквивалентны ЗЭСО, состоящей из центрального узла в виде 13-станцни и множества СУ, после группировки которых получается ЗЭСО . Тот же вывод применим ив случае, когда терми-

налы неоднородны я могут быть разбиты на V групп, причем результирующая модель имеет вид (И,т,р).

В п, 1.1 описана модель ЦКС, позволяющая оценить эффективность таких алгоритмов динамического распределения буферной памяти (БП), как однородный пул равнодоступных буферов и секционная КП. Критерием эффективности является вероятность отказа в приеме сообщения из-за отсутствия свободных буферов. Показана эквивалентность этой модели ЦКС частному случаю ЗЭСО Пп(Л,а,р),

если БП - это однородный пул буферов, или П (N,55,р) при БП,.

У П

состоящей из V секций, причем вероятность отказа определяется из функции разбиения этой ЗЭСО.

Наконец, в п. 1.5 описывается модель локальной сети архитектуры «клиент-сервер», позволяющая оценивать такие показатели производительности, как коэффициенты использования и пропускные способности всех узлов РИВС для запросов от каждого узла-клиента (УК) и средние времена выполнения процессов. Основная часть УК - это персональные компьютеры, на каждом из которых может одновременно выполняться только один процесс. Показано, что разделяя эти УК на группы, а также объединяя в группы устройства памяти, модель локальной сети приводится к ЗЭСО, являющейся частным случаем ЗЭСО (N,55, р).

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

производительности МВС с многошкнной коммутацией и спецпроцессорами. Эти типовые моделк (наряду с их частными случаями, используемым»; в гл.1 для описания функционирования конкретных ВС и сетей) являются основными объектам« данного диссертационного исследования.

Общей и характерной особенностью этих моделей является их большая размерность, что обусловлено большим числом : а) процессоров к модулей панятк (порядка нескольких десятков или даже сотен) в современных МВС; б) УВЛ (порядка нескольких сотен) и терминалов (до нескольких тысяч) в современных многотеркиналь-иых ВС; в) линий связи к буферов (порядка нескольких сотен и даже тысяч) в современных ЦКС; г) процессов, обрабатываемых локальными сетями, к устройств их памяти. Большая размерность приводит к огромному числу возможных состояний этих ЗЭСО и практической неприменимости точных формул для их анализа.

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

Согласно этому методу формулы вычисления характеристик ЗЭСО представляются в виде интегралов Лапласа; в частности, любая стационарная характеристика Т ЗЭСО П^п(К,ш,р), такая, как средняя длина очереди, определяется выражением

где г>0; С(х)=»'0(х)ахр^-Кд(х)|; х=(хг,...Хд); т(х) - некоторая функция; О - ФР, также имеющая вид такого же интеграла Лапласа с исключением функции т(х) и заменой коэффициента А на Ао- Далее в гл.4 доказывается возможность получения таких интегральных представлений для типовой ЗЭСО, содержащей ОУ и УПИО и введенной в п.1.2. В исследуемых интегралов Лапласа вида (1): 1) п-мерная область интегрирования имеет вид угла

(1)

X = -{х: х( е О, 1=1,п; Е х, а р

2) д(х) имеет глобальный (на X) минимум в точке х, причем

Л

для любых х е X таких, что шах |х -х сопэЪ>0, выполняется условие

д(х) - д(х) ¡есопэ^О; (2)

п : к . ( 1 ) _ .. »

з) функция ро(х) имеет вид <ро (х) п х, » где Озк^сопв*:

I

=1,п, причем т(х)=сопзг:>0 и (х)=сопз^0.

Л

Упорядочим компоненты вектора х- следующим образом: х(«=0

и а^ ад/ах1 =сопб1:>0 при п, х^сопз^О я а^=0 при

Основная задача гл.2 состоит в оценке интеграла Лапласа в (1) с целью доказательства приближения

Т - |г + °(М_9Г)] Ао, (3)

т.е. относительная ошибка приближения Т » т(х)А /Ао составляет величину, порядок которой не более . Форма этого- приближения не зависит от значений параметров системы, а его погрешность зависит только от размерности N. поэтому получаемые приближения вида (3) естественно назвать непрерывными по отношению к изменению параметров системы. Задаче оценки интегралов вида (1) посвящено значительное количество работ, в которых: а) либо исследован одномерный случай (п=1) я приближение (3) доказано при х=сопз^О, а также при х=0 и сг =сопб1:>0; б) либо в многомерном случае предполагается г=0 и т.е. точка максимума х распо-

ложена внутри угла X и вдали от его границ. Кроме того, во всех этих работах предполагается аналитичность функции д(х), что также существенно ограничивает общность анализа.

Эта ограниченность классических методов асимптотической оценки интегралов Лапласа обуславливала возможность применения метода Лапласа лишь для простейших ЗЭСО. Поэтому в гл.2 проводится развитие этих методов, позволяющее значительно расширить область применения метода Лапласа и использовать его для асимптотического анализа моделей ВС и сетей, описанных в гл.1. Последовательно рассматривая случаи одномерной (п. 2. 2) и многомерно й (п.2.3) области интегрирования X, доказывается, что если: 1) функция д(х) удовлетворяет условию (2), в конечной окрестно-

сти Х0 точки х имеет непрерывные производные -е1д/<1х , 1=1,п, и dгg/dxldXJ> 1^=1уЕ, и является асимптотически ограниченной; 2) все диагональные миноры йей^В^ЦЬ^Ц} '.^ТТ )'

Ь

а2д

1) с!х,с1х^

, являются положительными величинами порядка 1;

3) в окрестности Хо функции т(х) и ?И1)(х) непрерывны и асимптотически ограничены, - то основное приближение (3) справедливо в общем случае с 7=1/2. А если к тому же г=0 и при для хеХо: а) функция д(х) имеет непрерывные производные: йгд/<3х <1х для

¿V

1=^+1,п и 3=1, а также Д Д для б) функции

I I л

х(х) и имеют непрерывные производные по всем х , 1-ЗГ7Е,

- то в приближении (3) Г=1-

Таким образом, метод Лапласа, развитый в гл.2 и применямый далее для анализа моделей ВС и сетей, обеспечивает получение приближений для их показателей производительности с заранее известным порядком ошибки, не превышающим величины Н"1 нлн Н~1/г.

В третьей главе метод Лапласа применялся для асимптотического анализа типовой ЗЗСО П (N,35,5) с N заявками одного класса,

Й

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

Задача асимптотического анализа решалась при последовательном усложнении структуры зэсо р^(К,п,р): скачала рассмотрен случай однородной нагрузки на все ОУ; затек - случай высокой нагрузки на все группы, когда средние длины очередей ко всем группам 1=1,п удовлетворяют соотношению Х^/И - 1; наконец, проанализирован общий случай наличия групп как с высокой, так и с нормальной (когда ь - 1) (или близкой к высокой) нагрузкой, т.е. случай неравномерной нагрузки. Ниже даются асимптотические приближения (полученные для общего случая) для следующих основных стационарных характеристик ЗЭСО Пп(К,ш,р): среднее значение и дисперсия <г как числа заявок в 18-станцни (1=0 и Ьо«=Рд),

так и длины очереди к группе 1«1,п, а также среднее число занятых устройств Л в каждой из групп 1=1,п.

Занумеруем группы ОУ:

где р^Ир^ т.е. группы 2/.. ,г+1 состоят у.з большого числа о У, а остальные группы упорядочены по убыванию нагрузки так, что

А г-и я

первая группа наиболее нагружена. Ввздвк параыетр ко=1+ Е Р,2,»

1*2

где значения определяются путем решения системы 1 - - Р,/[х+ I Р^] = О, 1=Т7г+1.

Обозначим также р1=шах(р1,<0) * 2,'1>= (а1~к_1)/(1~Р1/Р1) Для

1=2,г+1. Разрабатывая асимптотики для ФР и эе произзодных, через которые вычисляются показатели производительности, доказывается справедливость следующих асимптотических приближений:

Р^ = ^-/(и.Р,) = и/р1, 1=Т7п;

ДЛЯ групп с большим ЧИСЛОМ ОУ при р Я

= N р4г*/к0< 1=г7г+1,

а при Р1г<0 это приближение справедливо с заменой г' яа г11';'

для любой группы iel,r+2,n с малым числом ОУ такой,-что выполняется условие

1 - Р,/Р, ь const >0, (4)

справедливо

Ь] = [l+0(N"5)J ra^/tp^p—l) .

Наконец, при выполнении условий: а) (4) для всех 1ег+2,п и б) 1-ко/р1&сопз^О, когда группа 1 - <узкое место», т. е. коэффициенты использования ее ОУ асимптотически равны 1, имеем

Ь4= [1+0(1Г6)] N |(р1-1)/р1 -(р1 /р])г|1'

Для всех этих приближений значение 5 в оценке погрешности равно 1/2 в общем случае, а при выполнении условий Ц-ко/р1 )гсопзГ:>о

и (4) для всех 1бг+2,п: во-первых, имеем 6=1, а во-вторых, получаем приближения для дисперсий:

= ^1+01)Л (р(/р1) / (1-р1)2, 1ег+2,п,

причем в случае р <к. это приближение справедливо и для 1=1, а

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

Из полученных приближений следует, что при оценке показателей производительности группы ОУ с нормальной нагрузкой можно рассматривать эту группу как открытую систему кассового обслуживания, на вход которой поступает пуассоновский поток с интенсивностью, равной пропускной способности ЗЭСО С1 (Н,ю,£>). а при оценке показателей группы ОУ с высокой нагрузкой можно исключить из ЗЭСО П (Я,т,р} все группы с нормальной нагрузкой.

п

В п. 3.4 приведены обширные численные результаты анализа производительности КВС и многотерминальных ВС, иллюстрирующие: а) точность полученных приближений путем сравнения результатов, полученных асимптотическими и точными методами при различных количествах устройств в группах к разном распределении нагрузки по группам; б) работоспособность приближений при решении задач поиска *узких мест» системы. В частности, граничные условия, определяющие ситуацию, когда подсистема внешней памяти является «узким местом» нноготерминальной ВС, и полученные с помощью асимптотических приближений, подтверждены как точными методами, так и в ходе натурных экспериментов.

Объект анализа четвертой главы - типовая ЗЭС.с П с N однородными заявками, состоящая из п+1 узлов, причем узлы О,...,я -это УПИО, а узлы 4+1,..., п - это ОУ. УПКО О - центральный узел и вероятность поступления заявки из этого узла в узел 1 равна р . 1=1, п. Основными характеристики этой ЗЭСО. оцениваемые в этой главе, являются: средние длины очередей (I»,) к каждому из

узлов 1=1, п. пропускные способности УПИО (М^. коэффициенты использования ОУ {и1).

Учитывая требование сбалансированности ЗЭСО при большом N. в п. 4. 1 уточнен вид зависимости интенсивности обслуживания й (1 ) УПИО I от длины очереди 1(:

при Р1>к

о

Д, (1,) = С4 (И) С, (Х1=1,/Н) ,

(5)

где ^¡»сопэ-ЬХ), 1=0,у, а функция 9,(х,) неубывающая и непрерывная, причем д((0)=0. Аналогично для интенсивности обслуживания

ОУ 1 предполагается: и «^ИС , 1=43+1, п. В ток же разделе доказаны леммы о зависимости средних длин очередей в узлах ЗЭСО и их пропускных способностей от интенсивности обслуживания в некотором узле и числа заявок N.

Далее, в п. 4. 2 доказан ряд утверждений, позволяющих представить формулы вычисления ФР и стационарных характеристик в виде п-мерных интегралов Лапласа. Наконец, в п.4.3 проводится асимптотическая оценка этих интегралов на базе метода Лапласа и лемм п. 4. 1 для случая монотонно возрастающих интенсивностёй обслуживания всех УПИО, когда для любого 1=575: д^г) монотонно возрастает при г€[0, 1] и <3д1/<3г=сопз1:>0 при 1£гг=сопзЪ>0. В результате этой оценки доказаны теоремы, формулирующие асимптотические приближения для искомых характеристик. Эти приближения изложены ниже.

Занумеруем (без потери общности) ОУ таким образом, что

(1 >,

С /Р

ч

. ( 2 )

Введем вектора х<11=(х<1)

= (х

П 1\

|21,...,х^2|), являющиеся решениями,

<х.

) и

1 ч

соответственно, си-

о -1

= 1-х -. 1

стены уравнений и системы, состоящей из уравнений х0=1-х1~.

(б)

4-1

(6) И

Обозначим х(,1=1-х<1>-

; д (х )= V, где ^С,.,/?,^. „

ч ♦ 1

^ В центральной теореме 4. 1 доказано, УПИО 1=о7д справедливы приближения:

(7)

( 2 )

= ¡И-0(Ц-1/2)]

Нх

м

где 3=1, если д=п или

V

Л = с Я

0 ,

Приближения для коэффициентов использования ОУ имеют вид:

-х'" и х,2,=1-х

ч О 1

что для характеристик

(8) (9)

О, а иначе j=2.

о, = [1+0(Ы-1/2)] у^/с,

1=4+1,п.

(10)

где Уо = пи.п{Содо(х^11), V), а для средних длин очередей к ОУ -

Ь1 = [1+о(ы'1/2)] -[с,/(Р1Уо)-г| * (11)

пря любом . . . ,п> таком, что

кроме того, при и условии неравномерной нагрузки на все

0У, имеющем вид:

С¡/Р,-^ ^сопзЪ>0, 1=д+2Тп, (13)

когда ОУ q+l - «узкое место, справедливо приближение

V, -"[С

наконец, при равнокерно высокой нагрузке на ОУ, где

т. е. при Д >0, С /р =___/р и С /р -У=сопз1:>0, 1=Ъ+1,п,

когда 0У ч+1,...,-Ь - «узкие места», имеем

V, - \ - + о<н-,/г)].-

Если Д^ ^ ^сопэ^О и выполняется либо л=д+1, либо условие (13), то в приближениях (9) и (10) оценку 0(Ы"1/2) можно заменить на 0(е*сН), а если либо Д =сопз^0. либо а=0 и -Л =

4*1 ^ 4-1

—сопбЪ>0, то - на 0(к" ); кроме того, при любом из указанных условий в приближении (11) оценка 0(Ы~!/г) заменяется на 0(Н-1).

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

В пятой главе основным объектом асимптотического исследования является ЗЭСО, введенная в п. 1.2 в качестве обобщенной модели ядра М-процессорной системы с t группами спецпроцессоров и п группами частных шин и модулей памяти, из которых в п-г группах число шин достаточно для обеспечения полносвязного интерфейса. Исследуемая ЗЭСО с N заявками состоит из центральной 1Э-станции с параметром г В-М-станций, п-г групп ОУ и Ъ прианальных устройств, моделирующих, соответственно, группы модулей памяти с частными шинами и с полносвязным интерфейсом и t групп спецпроцессоров. Предполагается, что количества скалярных процессоров N. модулей памяти га и шин Ь в группах 1=1,г, ком-

мутируемых посредством частных шин. и спецпроцессоров в каж-

дой из групп 1=п+1,п+1 велики, в то время как число модулей па-няти та в группах, связанных с процессорами посредством полно-

евйэкого интерфейса, может быть как велико (при 1=г+1,гь), так

и мало (при 1=гь+1,п). Без потери общности занумеруем группы модулей памяти % спецпроцессоров так, чтобы выполнялись нераве-

нства: 1=2,г; Р^Рг 1=гь+2,п;

ь

1=п+2,п+^ где а^и^Ы; р^Уз /V; р( - факторы нагрузки, одинаковые для каждого из устройств группы 1 и, в частности, равные а/(га^,5 для 1=Т7г,п+Т7пТЕ. где р я и1 - соответственно, вероятность доступа к группе 1 и интенсивность обслуживания каждого из ее модулей памяти али спецпроцессоров.

Анализ этой ЗЭСО начался с применения метода Лапласа для получения асимптотической формы функции интенсивности обслуживания ц*м(1 ) каждой В-М-станции I. В п. 3. 1 доказано, что асимптотическое представление этой функции интенсивности имеет пороговый вид:

вк .. \ х /(а -гГ'+х ) при х 5 х* ,

« [1+0(6®")} 111 ' . 1 . 1 1

I N при Х) ,

где х^^/Н, х*=■■(о|-М_1')р1/(а1-Э1); 5 ®и =е" с " при ¡х^ ! =

=сопз-{:>0, а иначе Также пороговую интенсивность об-

служивания имеют многоканальные устройства, моделирующие группы спецпроцессоров, я (как показано в гл. 4) эквивалент по Нортону любой подсети, состоящей из множества УПИО и ОУ.

Поэтому в п. 5. 2, как и в гл.4, рассматривается обобщенная ЗЭСО П с N заявками, состоящая из УПИО и ОУ. но в отличие от гл.4 интенсивности обслуживания только части УПИО (с номерами О,,..,Ь-1) монотонно возрастают. а для остальных УПИО функции их интенсивностей имеют пороговый характер, т.е. для 1=Е7д в определении (5): ,'д (х )=г (х ) при х", где'г' - монотонно

возрастающая функция, а иначе д (х )=/?)-. Занумеруем УПИО Ь.....

Ч таким образом, что С & /р"з...з с /3 /р , и преобразуем систе-

Ъ Ь Ь Ч Ч <1

„ (!) ( 2 ) , кы уравнений; определяющие вектора х их следующим образом: в правой части (Б) д. заменяется на Г(, а в (7)

V = папК /3 /Р , С /Р >•

В теореме 5.2 доказана справедливость следующих асимптотических приближений: (9) для 1=о7д; (10) для 1=сн 1, п, (8) с j=;l для а=0,ч прь Д з 0, а иначе - с 1=2 дл« Г=о,Ь-1 я для о, удовлетворяющих условию

~ Уо " (14)

(11) для з.е{д+1, ... ,п) удовлетворяющих условию (12); наконец, если Д >0. У=£ {? /р , а условия (12) и (14) выполняются для

Ч ♦ 1 Ъ (1

всех, соответственно, 1=ч+1,п и 1=Н+Т7д. то

= [1+о(1г1/г)] N (<«;;;).

Также доказано, что в случае малой нагрузки, определяемом условием -Д =сопе1:>0, или высокой (Д =сопз*:>0) и неравноме-

Ч♦ 1 4*1

рной нагрузки, когда фактор нагрузкк на УПИО Ь или на ОУ д+1 (это УПИО или ОУ является <узкин местом») значительно больше, чем на остальные УПИО НТч к ОУ, исследуемая ЗЭСО О асимптотически эквивалентна ЗЭСО П или О , отличающимся от ЗЭСО Г2 тем,

о ь

что в ЗЭСО По все пороговые функции и (1 ) заменены на монотонно возрастающие у (1 )=НС>г (х =1 /И), з то время как в ЗЭСО

функции ц{ (1( ) заменены на д (3^) для 1=11+1,д, а УПИО - на ОУ с интенсивностью д А . Эта эквивалентность позво-

К 1 л п

лила (в указанных случаях), применяя результаты гл.4 для оценки характеристик ЗЭСО П и О , заменить в приближениях (9) - (11)

О

оценку погрешности 0(Н"1/2) на 0(ы"1) или 0(е~с").

Асимптотический эквивалент модели МВС с многошинной коммутацией и спецпроцессорами является частным случаем обобщенной ЗЭСО Г2. Поэтому, применяя результаты анализа ЗЭСО £1, в п. 5. 3 получены асимптотические приближения для основных показателей производительности МВС. В частности, для среднего числа активных (скалярных) процессоров и средних количеств занятых модулей памяти или спецпроцессоров Н (в каждой из групп), справедливо приближение

Р = N И /(т р ) = Г 1+0(1}"'/г) ] N V , 1=1, п+Т, (15)

- 1 - 1 ( ) ( 2 ) где V = / (р а ) , р , р , г „' }, а г находится из

С 1 1 г * 1 п ♦ ! О О

ь

системы уравнений

{1+ Т ар} г<г> = 1- ; »¿2>-г /[р^нГ'+г )], 1=1, гь.

^ 1=п* 1 > 1=1

Полученные приближения для средних длин очередей запросов скалярных процессоров к каждой из групп модулей памяти или спецпроцессоров в автореферате не приводятся. Из приближения (15) следует, что при V0~Р1/(Р1а1) «узким местом» МВС является число

шин в группе 1, при V =р"' - число модулей памяти в группе

ь

гь+1, а при V ~ число спецпроцессоров в группе п+1. Также

доказано, что модель данной МВС в достаточно широком ряде случаев асимптотически эквивалентна ЗЭСО вида О (N,¡¡¡,¡5) (являющим-

п

ся конкретизацией обобщенных сетей П или О ), что позволило (с

0

применением утверждений гл.3) не только доказать меньшую (чем 0(Ы"1/г)) погрешность полученных приближений для основных показателей производительности, но и получить асимптотические приближения для дисперсий как числа активных скалярных процессоров, так и длин очередей к каждой из групп модулей памяти или спецпроцессоров.

Численные результаты анализа производительности МВС с частными шинами, приведенные в п.5.4 для иллюстрации точности полученных приближений, показали возможность их успешного применения (с хорошей точностью) при выполнении условия большой размерности. При этом максимальная абсолютная ошибка приближений для среднего числа активных скалярных процессоров и средних количеств занятых модулей памяти или спецпроцессоров удовлетворительна и снижается с увеличением К, что согласуется с утверждениями и теоремами п.5.3, т.е. эти приближения непрерывны по отношению к параметрам МВС и применимы при любых их значениях. Наряду с иллюстрацией точности приближений, в п.5.4 дан анализ их работоспособности при решении задач выбора как минимального количества шин в каждой из групп, так и оптимального распределения шин по группам при заданном общем числе шин. Показано, что оптимальные распределения шин, найденные с помощью точных и приближенных кетодов, отличаются не более, чем на 1 шину.

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

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

Объектом анализа являлась МВС с большим числом процессоров N и процессов и множеством КР, разбитых на группы (КР одной группы статистически однородны), что позволило использовать для оценки производительности этой МВС асимптотические приближения, разработанные в гл.5. В п.6.2 разработана обобщенная сетевая модель этой МВС, позволяющая оценить производительность при различных стратегиях доступа к КР, при различных вариантах выбора КР из группы (выбор любого свободного КР или равновероятный выбор фиксированного КР), и отражающая архитектуру ядра реальных МВС, включая в себя совокупность разнородных АР, модели которых введены в пп. 1. 1 и 1. 2.

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

Цель анализа, проводимого в п. 6. 4 для ряда случаев, описа-иных ниже, состояла в доказательстве соотношения (Рд -Р )/И= = 0(Ы"1/г), где - значение Р^ при ЧС. Это означает, что ра-

зность между нормированными значениями Р для любой стратегии с

"1/2

блокированием и для ЧС не может быть больше, чем 0(Ы ), при любых значениях параметров системы, т.е. ЧС - почти (асимптотически) оптимальная стратегия для рассматриваемых случаев. Применяя приближение (15) для анализа обобщенной модели в случае использования ЧС для всех КР, доказана оптимальность ЧС в любом

из следующих случаев: 1) при нормальной нагрузке на МВС, когда среднее число процессов, обрабатываемых в квс, меньше числа процессоров; 2) при высокой нагрузке, если «узким местом», сдерживающим производительность НВС, является недостаточная пропускная способность наиболее нагруженной группы КР (из числа групп с калым числом КР или групп с выбором любого свободного КР) или группы АР; 3) число КР мало во всех группах КР с равновероятным фиксированным выбором или такие группы отсутствуют.

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

Общим объектом асимптотического анализа седьмой главы является типовая ЗЭСО П^(Й,гп,р) с V классами заявок, состоящая из центральной 13-сташии и п групп ОУ. Частными случаями этой ЗЭСО являются модели многопроцессорных и многотерминальных ВС с неоднородными процессорами и терминалами, модели ЦКС и сети архитектуры «клиент-сервер». Наряду с общедоступными группами ОУ, ЗЭСО Пп^(Ы,т,р) может включать также локальные группы, доступные только для заявок «собственного» класса. Поэтому группу ОУ удобно идентифицировать парой (3,1), означающей, что при ^0 эта группа локальна по отношению к заявкам класса з и имеет номер 1 среди таких локальных групп, а при j=0 эта группа общедоступна и имеет номер 1 среди общедоступных групп. Аналогично v классов заявок можно разбить на два типа-. тип 1 (узу первых классов) - имеющие «собственные», локальные группы ОУ, доступ-

ныв только для заявок данного класса,, а тип 2 (у—"-»/ последних классов) - не имеющие таких групп, т.е. поступающие только в общедоступные группы. Таким образом, в обозначения этой ЗЭСО: ' ■ •/мг) ~ вектор чисел заявок в .каждом кз клехсоя;

го=Г(тл. '1=1,^, j=l/w), гао1, .1=1,Ъо]

вектор чксел ОУ в каждой из групп, где Ь^ й Ь>о - это число групп ОУ, соответстаенко, локальных для класса j и общедоступ-

м

ных, причем V Ь = г»; и иго - число ОУ, соответственно, в

■А' " 01

локальной группе (3,1) и в' общедоступной группе (0,1);

Р=[ (Р}1г 'И^, (?>31, ±=Х<.Ь0) , 3=1,V] .

- матрица факторов нагрузки (отношений коэффициента посещения заявками класса j к интенсивности обслуживания) от каждого класса заявок 3 к каждой группе ОУ 1, т.е. р и <р^ - факторы нагрузки, соответственно, на локальную группу (зД) и на общедоступную группу (О, д.) от заявок класса 3.

Размерность этой ЗЭСО определяется общим количеством заявок N (т.е. Ы-ш) . Пронумеруем группы ОУ так, что пр>; любом

в группах (ЪД) с меньшими номерами (1=1,V ) число уст-

л

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

В п.7.1 оцениваются следующие основные стационарные характеристики ЗЭСО О (Н,т,р):

- пропускная способность Л* ЗЭСО для класса 3;

- средние длины очередей: Ь ^ - к локальным группам (3,1),

1=1,Ь^, 3=1,«, и - к общедоступным группам (О Д) , 1=1,Ьо,

по отношению к заявкам класса 3=1,V. ____

Представляя формулы вычисления этих характеристик и ФР в виде кратных интегралов Лапласа, путем оценки этих интегралов разрабатываются (теорема 7.1) следующие асимптотические приближении:

л] = м^о^г"), 3=17^; (1б)

Я ДЛЯ з = К=Т7^

ЪУ1 - [х+ООГ1'2)] N 1=^+1 ,Ьь. (17)

= ¡1-К>(Ц-1/2)^ Ы^^р^/Еа^О^г*)), (18)

где х'11' - множество таких индексов . что av,=const>0;

А п п 1

1*1

Яяя.Ь° , также справедливы приближения вида (17) я (18)

с Ь=0 и заменой на (р^. В этих приближениях:

= 1/Х* + N ^(г*) +

Б (г )ао при а иначе Я (г )=■ р г ;

3 . ■ 1 = 1 л

Л* - параметр 13-станцяи для заявок класса вектор г*«(2* , л Ь1

1=Т7ь~, является решением следующей системы уравнений:

П ...

1 - -

Далее доказывается теорема 7.2, формулирующая необходимые и достаточные условия возможности, замены ошибки 0(11"1/г) в приближениях (16)-(18) на 0(Л"')'.'■ и выводится следствие 7.1, позволяющее находить «узкие кеста> как для заявок определенного класса, так и для ЗЭСО в целом.

В п. 7.2 показано, как применить это следствие для поиска «узких мест» в локальной сети архитектуры «клиент-сервер», модель которой описана в п.1.5 и является частным случаем ЗЭСО О (Н,т,р). .. Там же даны численные результаты оценки влияния размерности на точность разработанных приближений, применяемых для анализа производительности этой локальной сети. Из этих результатов видно, что характер изменения погрешности приближений В точности соответствует теоремам 7.1 и 7. 2.

Другим частным случаем ЗЭСО Оа^(Ы,т,р) является модель ЦКС с V секциями буферной памяти (БП), описанная в п. 1. 4 и анализируемая в п.7.3. В этой модели каждому классу заявок соответствует единственное локальное ОУ. В отличие от пп.7.1 и 7.2, в данном случае основной целью асимптотического анализа являлась разработка приближений для вероятности отсутствия очереди к

каждому локальнону ОУ, являющейся оценкой вероятности отказа в приеме сообщения и секцию j. Оценивая интегралы Лапласа, представляющие формулы вычисления функций разбиения, доказана тео-рака 7. 3, содержащая совокупность приближений для вероятности Р^, справедливых при следующем условии сбалансированности цкс по производительности процессора и М выходных каналов:

__v

l-pi=const>0, i=0,M, при N = £ N -> ю,

j = i 1

где

V _

р =А/д , Л= Z А , р =A.pt / [ (1-F ) Д* ], i=l,M;

Я - интенсивность поступления сообщений в секцию j, состоящей из Nj буферов; д^ и - величию.!, обратные среднин временам процессорной обработки сообщения и его передачи по каналу i, происходящей с вероятностью р(; - вероятность неудачной передачи по каналу i. Как следствие из теоремы 7. 3, получены условия несбалансированности и гарантированной сбалансированности ЦКС по объему БП. В частности, ЦКС гарантированно сбалансирован по объему каждой секции j, когда Р^ = 0(е~с*), при выполнении следующего условия:

/ы -В Л -А Н"1 £ (l-pV'-l/N =const>0, j=l7v,

^ 1 = 0 ' где м

Bj = 1/д° +'1ЕР1-{1/д;| + F./td-F,)^,]}.

д^ и д*( - величины, обратные средним временам записи сообщения в j-ю секцию БП, ожидания подтверждения на него и задержки time-out при передаче по каналу i.

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

8 носьноЯ главе описывается методика оценки производительности ».нтзгрированных ЦКС ка базе асимптотического анализа. В п. 8. 1 проводится анализ особенностей реализации современных интегрированных ЦКС, имеющих и своем составе многопроцессорное ядро, развитую подсистему ВП л БП большого объема для приема поступающих сообщений; ставлтся задачи оценки производительности отдельных компонент ЦКС и всей системы в целом. Огромное число линий связи, подкличенных к ЦКС, я, как следствие, большой объем БП к весьма значитзльное количество устройств различных типов, составляющих ЦКС, обуславливают большую размерность моделей массового обслуживания, используемых для оценки производительность: ЦКС. Поэтому основной особенностью (и новизной) описываемой методики оценки производительности ЦКС и пакета АСИМЦКС как ее программной реализации, является то, что эта методика базируется на асимптотических приближениях для показателей производительности компонентов ЦКС, разработанных в гл.3, 5 и 7 путем примененкя метода Лапласа.

В п.8.2 описываются входные данные к алгоритмы расчета показателей производительности многопроцессорного ядра и обрабатывающего комплекса ЦКС с развитой подсистемой ВП, а также вероятности отказа и коэффициентов использования каналов связи. Построение зтих алгоритмов на базе указанных асимптотических приближений обеспечило: резкое снижение погрешности и возможность предсказания ее порядка; минимальное время расчета показателей производительности при программной реализации приближений и алгоритмов; легкость определения «узких мест» ЦКС.

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

Таким образом, методика оценки производительности ЦКС и

пакет АСИМПКС, разработанные под руководством автора в рамках Республиканской научно-технической программы «Информатизация России», являются практической реализацией разработанных в диссертаций асимптотических методов оценка производительности ВС ц сетей. .

Приложение к работе содержит доказательства основных теорем 8 матенатическкх утверждений диссертации.

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

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

В диссертации получены следующие основные теоретические и практические результаты.

1. Проведен анализ моделей таких разнообразных ВС и сетей, как: многопроцессорные ВС (МВС) с полносвязным интерфейсом, с многошинной коммутацией и со спецпроцессорами; многотермнналь-дае ВС с развитой подсистемой внешней памяти (ВП) ; центр коммутации сообщений (ЦКС) с разными алгоритмами распределения буферной памяти • (БП) ; локальная сеть архитектуры «клиент-сервер». Для этих моделей, представляющих собой мультипликативные ЗЭСО, приведены и разработаны точные методы расчета стационарных характеристик, являющихся оценками показателей производительности.

Показано, что рассмотренные модели обладают большой размерностью (с большим числом заявок и устройств) к являются частными случаями следующих двух типовых ЗЭСО: а) ЗЭСО, состоящей яз 13-станции и множества одноканальных устройств (ОУ), с одник (ЗЭСО О (Я,т,р)) или несколькими (П (Н,*п»р)) классами заявок;

П П*

б) ЗЭСО, состоящей яз ограниченного числа ОУ и устройств с переменной интенсивностью обслуживания (УПИО).

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

3. На основе метода Лапласа проведен асимптотический анализ типовой ЗЭСО П Ш,га,р) с однородными заявками, состоящей из

п

ХБ-станции и множества ОУ и являющейся моделью как КВС с полносвязным интерфейсом и однородными процессорами, так и многотерминальной ВС с однородными терминалами и множеством устройств ВП. В частности:

3.1. Разработаны асимптотические приближения с известной погрешностью О(И"1) или 0(И"1/г) для следующих основных стационарных характеристик ЗЭСО (1 (N,55, р): среднее значение и диспер-

п

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

3. 2. Приведены обширные численные результаты анализа производительности НВС и многотерминальных ВС, иллюстрирующие хо-

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

4. Для типовой ЗЭСО с N однородными заявками, состоящей из нескольких УПИО и ОУ, получены интегральные представления формул расчета эе основных стационарных характеристик. Проводя асимптотическую оценку этих интегралов на базе метода Лапласа, для случая монотонно возрастающих или пороговых интенсивностей обслуживания УПИО разработаны асимптотические приближения для искомых характеристик, имеющие малую погрешность и простой вид к применимые при произвольных соотношениях интенсивностей обслуживания и вероятностях переходов заявок между узлами.

5. Проведено асимптотическое исследование ЗЭСО, моделирующей ядро МВС с многошинное коммутацией и спецпроцессорами к включающей В-М-станции и многоканальные устройства. В частности:

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

5.2. Применяя результаты анализа типовой ЗЭСО с УПИО для оценки характеристик нодели МВС, разработаны асимптотические приближения для таких основных показателей производительности МВС, как средние значения и дисперсии числа активных (скалярных) процессоров и длин очередей запросов процессоров к каждой из групп модулой памяти или спецпроцессоров, а также средние количества занятых устройств в каждой из этих групп.

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

6. Применяя асимптотические приближения, полученные для показателей производительности ядра МВС, проведен сравнительный

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

7. На основе метода Лапласа разработаны асимптотические приближения для стационарных характеристик типовой ЗЭСО, состоящей из 13-станции к множества ОУ, с несколькими классами заявок, частными случаями которой являются модели многопроцессорных и многотермниальных систем с неоднородными процессорами и терминалами, модели ИКС я локальной сети архитектуры «клиент-

.сервер». Полученные приближения позволяют явно указывать на «узкие места» как для заявок определенного класса, так и для ЗЭСО в целом. Дана иллюстрация высокой точности и эффективности этих приближений на примера сети архитектуры «клиент-сервер». При анализе модели ЦКС асимптотические приближения разработаны для вероятности отсутствия очереди в наиболее нагруженной узле, которая является оценкой вероятности отказа а приеме сообщения из-за нехватки ЕП. Использование этих приближений позволило получить условия несбалансированности и гарантированной сбалансированности ЦКС по объему БП и эффективно решать задачи выбора минимально необходимого объема БП и его оптимального распределения по секциям.

8. Асимптотические метода анализа производительности ВС и сетей, полученные в диссертации, наиболее полно воплощены в методике оценки производительности и определения «узких нест» интегрированных ЦКС, имеющих в своем составе многопроцессорное ядро, развитую подскстечу ВП и БП большого объема "для приема поступающих сообщений. Кроме того, асимптотические приближения диссертации использованы при создании информационной сети архитектуры «клиент-сервер» в Государственной Думе РФ, а результаты диссертации, опубликованные в монографии » статьях, внедрены в учебный процесс Московского инженерно-физического института.

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

МОНОГРАФИЯ

1. Богуславский Л.Б., Ляхов А. И. Методы оценки производи- . тельности многопроцессорных систем. М. : Наука, 1992. 213 с.

СТАТЬ)! И ДРУГИЕ ПУБЛИКАЦИИ

2. Богуславский Л.Б., Коган Я. А. , Лукьянова Т.Д., Ляхов А. И. Система автоматизации оценки производительности мультипроцессорных вычислительных систем // Тр. XI Всесоюз. совещ. «Автоматизация проектирования и конструирования»: Тез. докл. М. : ИПУ. 1983. Ч. 1. С. 88-89.

3. Петросян Э.А. , Меграбял P.O., Акопджанян Ы.В., Ляхов А. И. Оценка эффективности и выбор структуры регионального ВЦКП // Всесоюз. конф. по проблемам создания ВЦКП и развития АСУ (Душанбе, 1933 г.). Тез. докл. М. :■ ВНИИП0У при ГКНТ СССР, 1983. С.211-215,

4. Ляхов А.И. Анализ эффективности различных структур сверхоперативной памяти в мультипроцессорных системах // Моск. гор. кокф. «Управление-84». Тез.докл. К. : ВНИКП0У при ГКНТ СССР. 1384. С.215-215.

5. Коган Я. А. , Ляхов А.И., Хажмурадов М. А. Расчет показателей производительности вычислительных структур асимптотическими методами. М., 1985. (Препр./ХФТИ; 85-23). 31 с.

6. Фатеев А.Е., Пороцкий С. К. , Ляхов А. И. Методика оценки комплексной производительности ЭВМ ЕС // Вопросы радиоэлектроники. 1985. Вып.З. С.42-49.

7. Назуркявичюс A.A., Пороцкий С.К., Ляхов А. И. Некоторые результаты экспериментального исследования комплексной производительности ЕС ЭВМ // Всесоюз. шк.-сен. «Разработка и применение в народном хозяйстве ЕС ЭВМ. (ЕС ЭВМ-85)». Тез. докл. М. НИЦЭВТ, 1385. Ч.Й. С. 93-96.

8. Коган Я. А. , Ляхов А.И.. Нерсесян С. Г- Оценка показателей производительности кэш-памяти в многопроцессорных системах //Тр. ЕЕ Всесоюз.шк. «Многопроцессорные вычислительные системы»: Тез. докл. М.: ИПУ, 1985. С.30-32.

S. Коган Я. А. , Ляхов А. И., Нерсесян С. Г«. Асимптотический анализ эффективности использования кэш-памяти в многопроцессорных системах //Автоматика и телемеханика. 1986. N°ll. С.142-151.

10. Фатеев А.Е., Пороцкий С.М., Ляхов А.И. Измерения комп-

лексной производительности ЕС ЭВМ и анализ возможностей ее по* вышения // Вопросы радиоэлектроники. Сер.ЭВТ. 1987. Вып. 5. С. 151-160.

11. Ломов Ю. С. , Коган Я. А., Ляхов А.И., Фатеев Л.А. Сетевая модель для опенки времени доступа к внешней памяти универсальных ЭВМ //XX Всесоюз. коиф. по актуальным проблемам информатики к вычисл. техники. Тез. докл. Ереван: Изд-во АН Арк. ССР, 1987. С.41-43.

12. Ляхов А. И. Методы оценки производительности вычислительных систем, описываемых моделями большой размерности // Всесоюз. шк.-сем. «Разработка я внедрение в народное хозяйство ЕС ЭВМ. (ЕС ЭВК-87)». Тез. докл. К.: НИЦЭВТ. 1987. Ч. Л. С. 128-131.

13. Коган Я.А.,.Ляхов А.И. Мультипликативное представление стационарного распределения для замкнутых сетей с пассивными и активными ресурсами //Автоматика я вычислительная техника. 1938. NÎ2. С.28-31.

14. Коган Я.А., Ляхов А.И. Асимптотический анализ производительности многопроцессорных систем с общими шинами // Автоматика и телемеханика. 1988. NÎ4. С.148-163.

15. Коган Я.А., Ляхов А.И. Асимптотический метод анализа замкнутых сетей очередей с неравномерной нагрузкой // XIII Всесоюз. шк.-сем. по вычислительным сетям. Тез. докл. Москва -Алма-Ата: Изд. Науч. совета АН СССР по комплексной проблеме «Кибернетика», 1988. Ч. XX- С.260-265.

16. Коган Я.А., Ляхов А.И. Асимптотический метод анализа замкнутых сетей очередей с неравномерной нагрузкой //Автоматика и вычислительная техника. 1989. NÏ4. С.42-48.

17. Ляхов А.И. Асимптотический анализ производительности вычислительных систем с разными типами устройств внешней памяти // Автоматика и телемеханика. 1989. HÎ9. С.167-177.

18. Ляхов А. И. многопараметрический анализ эффективности использования кэш-памяти на основе асимптотических кетодов // Автоматика и телемеханика. 1989. H^ll. С.155-165.

19. Ляхов А.И. Развитие нэтода Лапласа для асвкптотхчбской оценки характеристик замкнутых сетей очередей большой размерности / Препринт. М.: Ин-т проблек управления, 1990. 36 с.

20. Ляхов А. И. Асимптотический метод оценка вероятности

отказа для секционной буферной памяти центра коммутация // Автоматика а телемеханика. 1993. N29. С.109-124.

21. Ляхов А.И. Асимптотический анализ неоднородной сетевой модели многопроцессорных в многотерминальных систем // Автоматика а телемеханика. 1994. N<2. С.161-171.

22. BoguslavsJcy L.B., Lyakhov A.I., Sevcik К.С. Performance evaluation of client-server distributed inforraation systems // In Proc. Int. Conf. on Local and Metropolitan Communication Systems (LAN i KAN). Kyoto, Japan, Dec.1994. P.445-459.

23. Богуславский Л.Б., Ляхов А.И.. Шевчик К, С. Сравнительный аналкз стратегий доступа к критическим ресурсам в больших многопроцессорных системах на базе асимптотических методов // Автоматика х телемеханика. 1995. Н^г. С.125-140.

24. Богуславский Л.В.. Ляхов А. И. Опенка производительности распределенных информационно-вычислительных систем архитектуры «КЛИЕНТ-СЕРВЕР* // Автоматика я телемеханика. 1995. N^9. С. 160-175.

25. Богуславский Л.Б., Дрожжинов В.И., Ляхов А.И. Моделирование основных параметров функционирования компьютерной сети Государственной Думы //Междунар. конф. я шк. «Вычислительные сети - 95» (Гурзуф, октябрь 1995 г.). Тез. докл. М. : Изд. Науч. совета РАН по комплексной проблеме «Кибернетика», 1995. С.120-124.

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

В монографии [1] автору принадлежат главы 3-6, посвященные асимптотическому анализу замкнутых сетей очередей, а также разработка точных методов анализа модел* МВС с многошинной коммутацией (§2.4); предисловие я §4.1 написаны совместно с Л.Б.Богуславским. В работах [2,5,8,9,14-16,22,24] автор разработал асимптотические приближения для показателей производительности ВС я сетей, а в [23] - для сравнительного анализа стратегий доступа к критическим ресурсам больших МВС с учетом всего разнообразия аппаратных ресурсов. В [6,7,10] автору принадлежат результаты натурных экспериментов, в [3,11] - модели многотерми-

нальных.ВС, а в [13] - точные методы расчета характеристик ЗЭСО с пассивными и активными ресурсами. В [25] автор разработал алгоритмы расчета показателей производительности сети архитектуры «клиент-сервер» на базе асимптотических приближений.

ЗакЛЗ. Тир.100

117805, Москва ГСП-7, Профсовзная, 65 Институт проблем управления