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

ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ Ш'ЧНО-ИССЛЕДОВЛТЕЛЬСКИй _ ЦЕНТР ЭЛЕКТРОННОЙ ВЬГЧИСЛИТЕЛЫЮИ ТЕХНИКИ

ДРУ2ЕНКК Шготор Игоревич

СЕТЕВЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ ШЧКСЛНТЕЛЫШ СИСТЕМ С ПЕРЕКРЫТИИ! РЕСУРСОВ

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

система и сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

РГ6 од

- 5 ДПР 1993

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

УД!( 681.3

Москва - 1993

Работа выполнена в ордена Трудового праскош знамени Научно-исследовательском центре электронной вычислительной техники (НИЦЭВТ)

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

сотрудник Пороцкий С.М.

Научный консультант - кандидат экономических наук, старший научный сотрудник Фатеев А.Е.

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

доктор технических наук, профессор Назаров С.В. кандидат технических наук Ляхов А.И.

Ведущая организация - Институт кибернетики АН Украины им. В.М.Глушкова (г. Киев)

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

на заседании специализированного совета Д 115.01.01 Научно-исследовательского центра электронной вычислительной техники по адресу: I13405, Москва, Варшавское шоссе, 125.

С диссертацией можно ознакомиться в библиотеке НИЦЭВТ.

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

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

Специализированного совета НИЦЭВТ, д.т.н., профессор

Е.О.Кузин

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

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

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

Одним из основных способов оценки качества функционирования вычислительных систем является аналитическое моделирование на базе сетевых методов - аппарата теории сетей массового обслуживания. В этой области прежде всего следует отметить работы отечественных ученых Башарина Г.П., Богуславского Л.В., Бочарова П.П., Вишневского В.Н., Литвина В.Г., Назарова C.B., Сигалова Г.Г., Панова С.Ф., а также зарубежных авторов Барда И., Клейнрока Л., Ла-венберга С.С., Лазовского Э.Д., Райзера М., Чанди K.M., Шввчика К. и др.

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

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

следуюцвм:

1. Проанализировать реальные ВС и выделить типовые особенности сетей с программным и аппаратным перекрытием ресурсов.

2. Исследовать суноствдоцие методы сетевого моделирования и сформулировать направл'Эцы: .;<р<рректлсго учета перекрытия.

3. Разработать новые ¿шоритмы точного расчета БС с перекрытием.

4; Усовершенствовать существующие приближенные методы моделирования совместного обслукивапия заявок в ВС.

5. Осуществить эффективную реализацию разработанных алгоритмов расчета БС с перекрытием ресурсов.

Объектом исследования являлись системы обработки информации, в которых использован принцип перекрытия ресурсов. В этот класс ВС входят практически все вычислительные системы на базе ЕС ЭВМ, многопроцессорные системы с разделяемой памятью, локальные сети по [»о дачи данных и т.д.

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

Научная новизна. Б работе решена задача разработки и комплексного исследования сетевых методов моделирования ВС с перекрытием ресурсов. В диссертации получены следующие новые научные результаты :

- разработана концептуальная схема многоуровнего перекрытия ресурсов и предложена классификация сетевых методов моделирования совмещенного обслуживания;

- получено точное матрично-мультишшкативное решение для сети с двухуровневым перекрытием ресурсов и разными типами совмещения;

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

Реализация и внедрение результатов. Разработанные методы внедрены в НИЦЭВТ (г. Москва), где использованы при проведении НИР и ОКР но разработке перспективных устройств и систем вычислительной техники. Результаты исследований и комплекс программ, реализующих сетевые методы, применялись в вычислительной лаборатории МГУ им. М.В. Ломоносова (г. Москва) и КГЦ "ИНИТ" (г. Каунас), на кафедре АСУ и ВТ в учебном процессе МГТА им. А.Н. Косыгина (г. Москва).

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

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

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

- Школе-семинаре молодых ученых и специалистов "Разработка и внедрение в народное хозяйство ЕС ЭВМ" (г. Киев, 1989);

- Конференции "Применение науки и техники для развития промышленности" (г. Каунас, 1990);

- Научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" (г. Одесса, 1990);

- Школе-семинаре молодых специалистов и ученых "Управление-91" (г. Алушта, 1991).

- xvi школе-семинаре по вычислительным сетям (г. Винница, 1991).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и четырех приложений. Общий объем основной части работы составляет 176 страниц машинописного текста, включая 36 рисунков и 5 таблиц. Список литературы содержит 100 наименований. Приложения занимают 40 страниц.

Содержание работы

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

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

- подсистемы внешней памяти с НМД без средства ускоренного определения положения записи при вращении и при аппаратной поддержке команды "поиск сектора";

- подсистемы внешней памяти с потоковым накопителем на магнитной ленте - IBM 34QO;

- многопроцессорной вычислительной системы (МВС) с шинной связью между процессорам! и модулями памяти;

- локальной comí передачи данных Tima Ethernet с множественным методом доступа, основанном на контроле несущей и обнаружении конфликтов.

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

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

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

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

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

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

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

Полная агрегация. Исходная сеть заменяется сложным узлом с единственной фазой обслуживания. Эта фаза обслуживания обобщает историю движения заявки: обслуживание и блокировка на каждом уровне.

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

итоге синтезированный узел 1-го (1=Т7£) уровня отразкает временную задергасу заявки на данном уровне совмещения.

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

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

Во второй главе вибрвна типовая локальная подсеть с перекрыта' ом росурсов п рассматривается задача построения точти. алгоритмов расчета. На основа построенной концептуальной кодоли с пэрэ-кры-пгом ресурсов предлагается структура исследуемой сети с двухуровневым совмещением, состоящая из и параллельных однолинейных узлов на первом уровне и одного многоканального узла второго уровня, m&moro и_ прябороп обслуживания. У зли первого уровня называются первичныгпг рэсурсаг.и (или первичной подсистемой), а параллелыше нриоорн единственного узла второго уровня вторичными ресурсам! (или вторичной подсистемой). Причем на первых m узлах выполняется автономное обедугпвоние заявки (первая фаза), л свободный канал (ю+1)-го узла захватывается только на время перокры-того обслукивапия (вторая фаза). Цэнтры обслуживания с номораю от 1 до т пмэют бесконечный буфэр для оглдагафьс заявок, а у (m+1)-го узла он равен нули. В качестве дисциплины оболухатваккл' для порвнх m узлов нринэта дисциплина FCFS (First Coma Piret Served - "первый пришел - первый обслужен"). Сеть замкнута, и с ней циркулируют п однородных заявок, а вероятность обращения к

_^ fS -V

узлу к (к=1,т) равна д,.>о ^ } qt.-l ]. Наедая заявка требует двухфазного обслуживания: первая фаза осуществляется автономно узлом k (к=Т7т) со средним f , а вторая фаза выполняется совместно узлом к н (т-и) со средним в , прячем длительности обслуживания заявки на фазах имеют экспоненциальный закон распределения. Кроме того, данная сеть характеризуется тремя видами совмещения ресурсов меиду первичной и вторичной подсистемами (перекрытие с прэрн-ванием - obbns, о очервдазацией - озарз и повторным обслуживанием - obkps). Для obrps сети дополнительно вводится" экспоненциально распределенное ьоемя повторного обслуживания со сродней Ьг (К :Г~~.7Т,),

Ток как исходная сеть не удовлетворяет теорема век?, то -л

нельзя решить стандартным математическим аппаратом точного расчета, поэтому с целью получения обозримых аналитических зависимостей точное решение получено для частного случая замкнутой сети, когда в-2, та=1. В этом случае вводится в рассмотрение случайный процесс ^(t), t>o> на векторном пространстве состояний D., где j={3,5,7) и отражает размер одного состояния, заключенного в вектор-столбец (3-OBBNS, 5-OBAPS, 7-OBRPS). Кавдое состояние имеет следующую структуру:

т

- OBBNS: *,(а1) = [(2,3), (1,1), (3,2)] ;

- OBAPS: W4(a1) = [(2,1),(2,3),(1,1),(1,2),(3,2)] ;

- OBRPS: X7(a1) = [(2,1),(2,3),(1,3),(1.1),(1,2),(3,2),(3,1)] 5 где элемент вектора *(а1) имеет вид (a,ß), что означает:

ai - количество заявок на обслуживание к узлу 1; если а1>0, то а1-1 в очереди, а одна заявка на обслуживании (количество заявок в узле 2 равно п-а1);

а - фэза обслуживания (О - нет обслуживания, т.е. а1=о; 1 -первая фаза обслуживания; 2 - вторая фаза обслуживания совместно с узлом 3; 3 - блокировка ур аа 1, так как узел 3 занят);

р - то же, что и а, только для узла 2.

Каждому вектор-столбцу я(I) (i=ü7ñ) ставится в соответствие вектор-столбец г (i) = (Pu»Pl2»«-' )т (i=TTñ), выражающий вероятность того, что процесс £(t) находится в состоянии »(i). Совокупность этих векторов обозначается через Р = (р(О),...,в> (п))т.

На заданном пространстве состояний (для всех трех сетей) случайный процесс £,(t) будет однородным марковским процессом (что обуславливается использованием соответствующего фазового пространства). Система уравнений глобального баланса для стационарного случая имеет вид ютр = где © - матрица интенсивностей перехода, а ® - нулевой вектор-столбец соответствующей размерности.

Выполняя группировку плотностей перехода по трем типам матриц: 0-<1) (K(i-1) переходит в »(i)), R(i) (*(i+i) переходит в «(i)) hs(í) («(i) переходит в «(i)), приходим к трехдиагональной блочной структуре матрицы ®т, в которой на главной диагонали расположены матрицы s(i), под ней - матрицу MD» а над главной диагональю - к(i). Такая блочная структура матрицы позволяет достаточно просто получить решение посредством исключения неизвестного вектора, начиная с и»(О) - прямое исключение,

- 9 -

f F(n) « ю(0)г(а-1), a>(0) = - s(n)4(n), P(i) = D(n-i)IP(i-1), ID(n-i) = - [s(i)+E(i)!D(n-(i+1))] CL (i).

1=гРГТТ.

или, начиная с o>(n) - обратное исключение,

f 0>(О) a W(0)IP(1 ), W(0) = - S (0)*R (О), P(i) = и(1)В>(1+.1 ), V(1) = - [s(i)+IL(i)(U(i-1 )) '«(i).

i=TTn=T,

где id и w есть операторы преобразования, a s(o)* и s{n)* -псевдообратные матрицы. Аналитический вид решения имеет вид:

1

в»( i) = -

или

STn У I |«><Ю

« —■' ksi

kan-i

o» (o),

Р(0)

rv- i

П«№)

k» J

f]vW

p(n), i=0,n,

0>(n)

где символ | обозначает правое матричное произведение (очередной элемент произведения относительно возрастающего значения пн-

-<

декса домножается справа от предыдущего результата, причем ¡~| =

к=о

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

На основании дальнейшего анализа приведенного выражения и конкретного вида матриц ¡L(i), и s(i) (i=o,n) получены сле-

дующие результаты:

- Вектор р(0) или 1Р(п) может быть выбран с точностью до постоянного множителя.

г Для сетей с obbns и obaps совмещением установлен факт существования равенства определенного множества ненормированных векторных вероятностей для двух последовательных значений числа заявок к (индекс 1) и к+1 (индекс 2) соответственно, т.е. для оввш сети ir(i)',>=jr(i)a' (1=сТЛГ=Т), а для obaps сети г (i )"'-¡p(t)<2> (i^TF1?) при кг?..

- На основе установленного факта предложены эффективные ре-курронтлие алгоритмы рпсчетч сетей с 0BBN5 и OBAPS совмещением

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

- Показано, что не существует рекуррентного алгоритма расчета сети с obkps перекрытием (для общего случая, как это было сделано для obbns и obaps сетей), в связи с чем для расчета этой сети можно использовать, например, алгоритм прямого исключения.

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

Метод полной огрегации. Применительно к сети с двухуровневым перекрытием моделью исходной сети является двухуровневая модель. Модель нулевого уровня - модель эквивалентного узла - представляется в виде графа размножения-гибели, отражающего по состоянию число заявок (к, к=07х), выставленных к (т+1)-му узлу. А на первом уровне находятся модели производительности ресурсов первичной и вторичной подсистемы в зависимости от количества заявок в них, что определяется величиной к.

Пропускная способность изолированной первичной подсистемы со средним временем обслуживания о^ нормируется относительно коэффициента (m-k)/m - т.е. на долю фактически незаблокированных узлов. При расчете же модели производительности вторичной подсистемы рассматривалась замкнутая СеМО, состоящая из к заявок и m однолинейных узлов (среднее время обслуживания bv) с нулевым вектором вероятности присоединения заявок к узлу, у которого компонента, соответствующая отсутствию заявок в узле, равна 1. В этом случае расчет замкнутой сети со случайными обходами узлов заявками выполняется модифицированным алгоритмом mva с зависимой нагрузкой.

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

- OBBNS: x=mln(n,m,m2), o.=i., а общее решение сводится' к методу прямого расчета.

- obaps: x=mln(n,ra), а ov=причем общее решение также сводится . к методу прямого расчета.

- OBRPS: x=n>in(n,mtn>2), а o^p^t + d-pj)^, где р' есть вероятность того, что на узле i выполняется первая фаза обслуживания, по отношению ко второй фаге. Эта вероятность рассчитывается через общую пропускную способность сети (^па) и среднее число пе-реобслуживаний. В итоге общее решение получается в виде одного нелинейного уравнения относительно Лпа.

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

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

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

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

В конечном счете модель исходной сети представляется в виде трехуровневой модели. На нулевом уровне находятся модели конкуренции за ресурсы соответствуюцих подсистем, определяемые через функции ф*а и ф** соответственно. В этих моделях ресурсы дополнительных подсистем (вторичной для Первой модели и первичной для второй) заменяются 13-станцией со средними и »»** соответственно («*'=<})"(а,«*)). Кроме того, во второй модели вторичная подсистема заменяется узлом, зависимым от нагрузки. Это связано с тем, что время ожидания доступа ко вторичной подсистеме зависит не только от количественных параметров, но и типа перекрытия, что может быть корректно учтено в модели изолированной вторичной подсистемы .

Модель изолированной вторичной подсистемы решается посредством расчета исходной сети в предположении, что заявки при занятости всех каналов (т+1 )-го узла обходят его (при оввмб и овкрб перекрытии) или становятся к нему в очередь (при оварэ перекрытии). Расчет модели первого уровня выполняется для числе заявок от 1 до т1п(п,п),т2). При этом для более корректного учета времени обслуживания (т+1)-го узла оно рассчитывается аналогично модели производительности ресурсов вторичной подсистемы метода полной агрегации, что и составляет модель второго уровня.

Таким образом, для оввиэ и ОБАРв сети модели уровня 1 и 2 рассчитываются однократно, а решается только основное нелинейное уравнение, задаваемой моделями нулевого уровня. В случае же ОВИРЗ сети необходимость учета общей пропускной способности ) привода! к системе из двух ««линейных уравнений (основного и для

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

Необходимо отметить, что реализация метода горизонтальной агрегации основана ня модели суррогатов, предложенной для расчета только систем с obaps перекрытием. В диссертации эта модель развита в направлении расширения области применения (для трех типов перекрытия) и на случай многоканальности (ш+1)-го узла. При численном расчете вместо метода простой итерации, предложенного в модели суррогатов для решения системы из двух нелинейных уравнений (определяемой двумя функциями ф*а и ф** по отдельности), используется метод Ньютона-Рафсона с приближенным вычислением матрицы Якоби, вырождвпцейся в одну производную по одному основному уравнению (сведенному из двух исходных) для obbns и obaps сети. Это позволяет получить квадратичную сходимость по сравнению с методом простой итерации, который, к тому же, не всегда сходится к решению.

Uemoö вертикальной агрегации. На основе этого подхода исходная сеть аппроксимируется .n-узловой СеМО, синтезированные узлы которой отражают временную задержку заявок в разделяющемся входном потоке исходной сети, связанную с их обслуживанием в i-ом узле по полному циклу (первая фаза, блокировка и вторая фаза обслу-аивания). Поэтому среднее время обслуживания в i-ом узле определяется выражением

1 = f + В + в.,

I V t I

где в^ есть среднее время блокировки 1-го узла.

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

*"вп = Фв8(аДва>' где а, как и ранее, это вектор параметров, уникально определяющих

исследуемую сеть, а d> - функция, вычисляющая А. на основе ме-

Ii et ВЭ

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

Расчет для всех трех типов сетей основан на представлении

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

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

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

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

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

~ i4 -

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

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

. ХиЛ = Фпд(а.Хпд),

где а, как к ранее, это вектор паракетроз, уникально опрвделя5;>щих

исследуемую сеть, а <ь - функция, вычисляющая на основе ме-

Дд ИД

тода полной декомпозиции. Тем самым исследуемая сеть представляется одноуровневой моделью полностью декомпозированной сети, состоящей из (т+1)-сй псэвдооткрытой СМО.

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

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

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

Проведенное исследование позволяет сделать следующие выводы.

- Для экспоненциальной сети с ОВВКБ перекрытием при тг=1 (и соответствующего obeps совмещения) метод полной агрегации дает точное решение (что следует из отсутствия последействия экспоненциального закона распределения фаз обслуживания ).

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

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

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

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

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

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

В последнем разделе подтверждается корректность предложенных методов учета перекрытия ресурсов при решении задачи по оценке различных вариантов синхронизации процессоров в МЗС с общей оперативной памятью. При этом рассматриваются два основных подхода к синхронизации: через семафоры, расположенные в оперативной памяти, как это реализовано в Sequent Symmetry, и через изолированные семафорные регистры, как это сделано в. ЕС II9I. Применительно к ЕС ПЭТ предлагается эффективный алгоритм поддержания приоритетной очереди процессоров, реализуемый программно на процессоре-мониторе .

В диссертации посредством аналитической модели с двухуровневым совмещением'проанализированы следующие типы синхронизации. Для Sequent Symmetry:

- сгшнинг на команду test-and-set;

- спининг на кэширований вариант teBt-and-eet;

- спин с задержкой;

- алгоритм явной очередизации. Для ЕС II9I:

- спининг на гипотетическую команду test-and-set;

- спининг на аппаратную реализацию команды BSSM;

- спининг на программную реализацию команды BSSM;

- предлагаемый алгоритм поддержания приоритетной очереди.

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

Относительно МВС, обеспечивающих мощную аппаратную поддержку синхронизации (как это сделано, например, в ЕС II9I) для любых размеров критических секций абсолютное превосходство имеет аппаратная реализация команды BSSM, при этом отказ от хранения семафоров ь оперативной памяти дает существенное увеличение в производительности по сравнению с типовым вариантом спина на команду test-and-set (полезная работа процессора может вырождаться в спининг ). Если же основного набора из 32-х семафорных регистров недостаточно, то вместо программной реализации команды BSSM лучше использовать предлагаемый алгоритм поддержания приоритетной очереди.

Основные результаты работы

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

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

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

2. Для модели с двухуровневым совмещением и тремя тташ перекрытия полуЧейо точное матрично-мультипликатиЕНое решение отно -сительно векторного состояния сети. Выведет аффективные рекуррентные алгоритмы расчета сети с прерыванием и очере^геацией.

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

4. Корректность предложенных алгоритмов подтверздена при решении задачи по оценке различных алгоритмов синхронизации процессоров в ВС с общей оперативной памятью, что использовано при сопоставлении разных вариантов реализации ЕС II9I.

Публикации. Содержание диссертации и основные результаты изложены в работах:

1. Новриго Ф.Л., Фатеев А.Е., Дружинин В.И, Эффективность совместного использования ресурсов вычислительных систем /./ Препринт 92-19. - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины. - 1992. - 30 с.

2. Об аналитическом моделировании систем обработки данных в условиях повышения требований к их экономическим показателям /' Черемисинов В.М., Фатзев А.Е., Пороцкий С.М., Дружинин В.И. // Вопросы радиоэлектроники. Сер. ЭВТ. - 1992. - Вып. 7. - С. 69-70.

3. Fateyev А.Е., Porotskiy S.M., Drujinin V.I. Comparative evaluation of approximate methods for modelling of network systems // Perform. Eval. Rov. - 1991. - V. 19. - N 2. - P. 44-48.

4. Дружинин В.И.., Пороцкий С.М. Развитие метода перерасчета задержек для расчета сетей массового обслуживания с совместным использованием ресурсов // Автоматика и телемеханика. - 1992. - № 10. - С. 89-96.

5. Дружинин В.If. Анализ вычислительных структур с совместным использованием ресурсов // Вопросы радиоэлектроники. Сор. 9В7. -1992. - Вып. I. - С. 38-43.

6. Дружинин В.И. Точные алгоритмы расчета сетей с дьуууу-ь

невым перекрытием ресурсов // Вопросы радиоэлектроники. Сер. ЭВТ.

- 1992. - Вып. 5. - С. 61-76.

7. Дружинин В.И. Развитие алгоритма MVA для расчета сетевых моделей вычислительных систем // Вопросы радио&лектроники. Сер. ЭВТ. - 1992. - Вып. 7. -- С. 3-8.

8. Фатеев А.Е., Пороцкий G.M., Друюшин В.И. Сравнительный анализ приближенных методов моделирования вычислительных систем // Управляющие систеш и мааины. - 19Э1. - J» I. - С. 52-61.

9. Фатеев А.Е., Пороцкий С.М., Дружинин В.И. К вопросу о сопоставлении методов оценки эффективности вычислительных систем // Управляющие системы и машины. - 1992. - * 1/2. - С. 65-71.

10. Фатеев А.Е., Пороцкий С.М., Дружинин В.И. Оценка точности и трудоемкости некоторых методов моделирования вычислительных систем // Вопросы радиоэлектроники. Сер. ЭВТ. - 1989. - Вып. 3. -С. 95-105.

11. Дружинин В.И. Аналитические модели точного расчета сетей» с блокировками и совмещением ресурсов // Тез. докл. Школы-семинар "Разработка и внедрение в народное хозяйство ЕС ЭВМ (ЕС ЭВМ-89)".

- 198Э. - Киев. - С. I89-I9I.

12. Дружинин В.И., Пороцкий С.М. Алгоритмы расчета сетей с совместным использованием ресурсов // Тез. докл. XVI Школы-семинар по вычислительна™ сетям. Часть I. - 1991. - Москва-Винница. - С. 18-23.

Личный вклад. Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работе I выполнен анализ реальных вычислительных систем с перекрытым обслуживанием, дана схема ь-уровнего совмещения и предложена классификация методов с выделением декомпозиционных подходов корректного учета совмещенного обслуживания. В работе 2 разработана классификация методов. В 3, 4, 8, 9 и 10 работах - участив в выводе аналитических формул и проведение экспериментов. В работе 12 - участие в формулировке выводов и проведение экспериментов.

Инв. " 39-261, от ТГ).С3.93. Доп. ряэм. 70 э!(з. по з/н bJiCS - f/uysM-от ГС.03.93.