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

РГ6 од

Санкт-Петербургский ордена Трудового, Красного Знамени институт точкой механики и оптики

На правах рукописи АЛИЕВ Шабудга Сираясуданович

УДК 681.324

МЕТОДЫ И АЛГОРИТМЫ СИСТЕМНОГО ПРОЕКТИРОВАНИЯ ЭВМ И СЕТЕЙ ПЕРЕДАЧИ ДАННЫХ С НЕОДНОРОДНОЙ НАГРУЗКОЙ

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

Автореферат

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

Санкт-Петербург - 1993

Работа выполнена на кафедре вычислительной техники Санкт-Петербургского ордена Трудового Красного Знамени института точно! механики и оптики

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

Т.И. Алиев

Официальные оппоненты: доктор технических наук, профессор

И.З. Панфилов

кандидат технических наук, доцент A.B. Данильченко

Ведущее предприятие: Ленинградский отраслевой

научно-исследовательский институт связ

Защита диссертации состоится "_"_ 1993 г. в "_

часов на заседании Специализированного совета К 053.26.04 Санкл Петербургского ордена Трудового Красного Знамени института точнс механики и оптики (197101, г. Санкт-Петербург, ул. Саблинская,14

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

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

Ученый секретарь Специализированного совета кандидат технических наук, доцент

J

В.И. иолдк.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Решение задачи проектирования сетей ЭВМ, как правило, пред-зтавляется в виде многоэтапного итеративного процесса автономного ! последовательного решения совокупности взаимосвязанных задач шализа и синтеза основных структурных компонентов сетей ЭВМ: \павных ЭВМ,сетей передачи данных (СГЩ) и терминальных сетей (ТС),

Системное проектирование ЭВМ, СПД и ТС важна проводить с гчетом таких существенных особенностей их функционирования, как ^однородность нагрузки и возможность применения приоритетных ¡тратегий управления (ПСУ) обработкой и передачей данных.

Актуальность темы диссертационной работы определяете.! необ-годимостью разработки методов и алгоритмов анализа и синтеза )Сновных структурных компонентов сетей ЭВМ, позволяювдх учитывать фиведенные особенности их функционирования, поскольку традицион-ше методы и алгоритмы исследования сетей ЭВМ ориентированы на >днородную нагрузку и, следовательно, не позволяют учитывать ¡еоднородный характер реальной нагрузки и использование ПСУ в гроцессе проектирования.

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

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

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

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

- разработка метода и алгоритма проектирования узлов коммутации (УК) з СПД с неоднородной нагрузкой с учетом ограниченной емкости буфера входных данных, возможности отказов поступающие сообщениям в приеме и ПСУ их обслуживанием;

- разработка методов и алгоритмов выбора пропускных способностей (ПС) каналов связи и распределения потоков (РП; в СПД с неоднородной приоритетной нагрузкой;

- разработка методики системного проектирования СПД с неоднородной нагрузкой, направленной на комплексное решение задач синтеза УК, выбора ПС, распределения потоков, и определения топологии СПД;

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

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

Научная новизна работы.

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

2. Разработаны метод и алгоритм проектирования УК с " учета* особенностей их структурно-функциональной организации,

3. Получены точные (в рамках принятых предположений) аналитические зависимости для временных характеристик обслуживания ъ СЩ неоднородных сообщений с учетом ПСУ их передачей по каналам.

4. Сформулирована и решена задача выбора ПС каналов СЦД с неоднородной приоритетной нагрузкой с учетом ограничений на временные характеристики СДЦ.

5. Разработаны методы и алгоритмы распределения неоднороден) потоков сообщений в СПД по критерию минимума средней зздерхю сообщений или максимума производительности СГЩ»

• 6. Проведены исследования влияния неоднородности нагрузки J использования ПСУ на результаты решения задач синтеза ЭВМ и УК, выбора ПС каналов и распределения потоков в СПД.

Практическую ценность работу представляют:

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

- методика системного проектирования СПД с неоднородной нагрузкой при наличии различных ограничений на средние времена пребывания в СПД сообщений разных классов.

- комплекс программ, реализующий в диалоговом режиме метода-ку системного проектирования СГЩ.

Реализация результатов работы. Результаты диссертационной работы внедрены в Ленинградском отраслевом научно-исследовательском институте связи (ЛОНИИС, г. Санкт-Петербург), в учеоном процессе по специальности 22.0? - "Вычислительные маыины, комплексы, системы и сети" на кафедре вычислительной техники (ВТ) Санкт-Петербургского института точной механики и оптики (ИТМО) и на кафедре вычислительных машин Одесского политехнического института, а также использовались в научно-исследовательских работах, выполнявшихся на кафедре ВТ ИТМО.

Апробация работы, Основные результаты диссертационной работа докладывались и обсуждались на 6, 7, 8 и.9-ой Белорусских школах-семинарах по теории массового обслуживания (Витебска 1990; Гродно, 1991; Брест, 1992; Минск, 1993), III и V Совещаниях по распределенным вычислительным системам и сетям массового обслуживания (Винница, 1990; Калининград, 1992).

Публикации. По материалам диссертации опубликованы -. 12 печатных работ. Основные компоненты разработанных программных средств сданы в Госфонд алгоритмов и программ.

Структура и объем работы. Диссертация состоит из введения, пяти глав, списка литературы (105 наименований). Объем работы -1 ДО страниц машинописного текста, 20 таблиц и 12 рисунков.

' КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрены характерные особенности и определены параметры структурно-функциональной организации сетей ЭВМ, выношен обзор и анализ моделей и методов исследования, проведена

S

декомпозиция общей задачи проектирования сетей ЭВМ, определен? цель работы и сформулированы основные ее задачи.

Среди характерных особенностей функционирования структурны! компонентов сети ЭВМ, в первую очередь, следует выделять: случайный характер функционирования; неоднородность вычислительно? нагрузки ЭВМ; многообразие информационных потоков в ТС и СИЛ, заключающееся в том, что сообщения в потоках разных типов характеризуются разными функциями распределения длин; наличие неоднородных ограничений на временные и/или вероятностные характеристики; использование ПСУ обработкой данных в ЭВМ, обслуживаш^ сообцений в УК и их передачей по каналам связи.

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

Используемые з работе точные и приближенные аналитические методы применяются, в основном, при решении зад^ч анализа, в то время, как численные и эвристические,- н задачах синтеза. Для аттестации приближенных методов используется имитационное моделирование на языке СР55-РС для 1ВМ РС.АТ.

Рассматриваемые в работе ПСУ реализуются на основе дисциплин обслуживания (ДО) со смешанными приоритетами (СП), обобщающих бесприоритетные (БП) ДО в порядке поступления и ДО с относительными (ОП) и абсолютными (АЛ) приоритета!®.

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

Из всего многообразия задач проектирования сети ЭВМ выделены и сформулированы задачи структурно-функционального синтеза ЭВМ, проектирования УК и топологической оптимизации СПД. Последняя, в

свою очередь, включает в себя следующие задачи: 1) выбор пропускных способностей каналов СПД при заданных топологии и стратегии маршрутизации; 2) распределение потоков в СПД при известных ПС каналов и топологии; 3) выбор ПС и РП при заданной: топологии СПД; 4) выбор ПС каналов, распределение потоков и синтез топологии при заданном ограничении на надежность СПД.

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

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

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

При проектировании ВС в качестве исходных . данных задаются параметры: 1) классов выполняемых в ВС прикладных программ (ПП) (интенсивности и коэффициенты вариации (КВ) интервалов поступления запросов на выполнение ПП разных классов, средние значения и КВ трудоемкости Ш); 2) файлов во внешней памяти системы (объем и средняя длина записи каждого файла, среднее число'обращений ¡Их к файлам]; 3) технических средств - накопителей на магнитных лентах (МАЯ), дисках (НМД) и каналов ввода-вывода (КВВ) - (емкости НМЛ и ЩЦ, скорости передачи данных при обмене с ними, средние значения времени доступа к дэнннм, стоимости устройств). Кроме того, при .

Г

проектировании ОПБС задается зависимость стоимости центрального процессора (ЦП) от его быстродействия, а для МПВС - быстродействие и стоимость стандартного ЦП.

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

Исследуемые ЗС моделируются неоднородной РСеМО, которая отображает структуру системы с точностью до отдельных устройств, а ее нагрузку - на уровне отдельных классов запросов, что обеспечивает высокую адекватность модели реальной системе.

Процесс проектирования ВС рассматривается как совокупность взаимосвязанных процессов структурного и фунгцконального синтеза, направленных на определение параметров структурной (быстродействие или количество Ш, количество НМЛ, НМД и КВВ, а также конфигурация связей между ними) и функциональней (способ распределения файлов до накопителям и ькбор ДО СП) организации ВС.

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

Основная особенность разработанного многоэтапного алгоритм; состоит в использовании на разных его этапах моделей с различно? степенью детализации; упрощенной в виде ОК и/или совокупности 01-СМО с, эквивалентной однородной нагрузкой - на этапе определения структурных параметров системы и детальной в виде РСеМО - нг этапе определения характеристик функционирования выбранкогс варианта структурно-функциональной организации системы. При эта для расчета РСеМО используются существующие приближенные метода, допускающие погрешность в оценке средних значений времени пребывания неоднородных запросов в пределах до 25%,

При синтезе МПВС в качестве модели многопроцессорной обработки данных рассматривается МК СМО )к /Ъ /И, где число !! обслухи-ващих. приборов соответствует количеству процессоров системы. ДЛ1 расчета такой модели используется приближенный метод, оснований

на сведении исходной Щ СМО к эквивалентной по проигводительност] —-» —.

ОК СМО Ы^/С^/! путем пересчетз быстр; йот ьнй приборов, а козффи

с-ч

вдент пересчета определяется из условия равенства времен ожидания запросов в МК к ОК СМО при однородной экспоненциальной нагрузке. •

■ Аттестация данного метода на имитационных моделях показала, что погрешности средних значений времени прерывания запросов разных классов при ДО ЕП не превышают 6%, а при ДО СП - 20% в интервалах (0.1+0.5) изменения загрузки и (0+2)- КВ длительностей обслуживания неоднородных запросов.

1 Задача проектирования УК при заданных параметрах (интенсивности поступления, трудоемкости обработки, допустимые значения среднего времени пребывания ' и* к-соос'щений к вероятности отказов в приеме я*, обусловленные полной занятостью буфера] сооб'дешй Я классов, обрабатываемых в УК, и ПСУ их обслуживанием состоит в определении минимальных значений числа процессоров заданного быстродействия и емкости буфера входных данных, обеспечивающих выполнение налагаемых временных и вероятностных

ограничений (k=i,И).

В качестве модели. УК используется МК СМО Ид/М/Н/2 а . ограниченным накопителем в предположении, что трудоемкости обработки сообщений разных классов в УК одинаковы и распределены по йкспо-венцигльному закону. Для расчета характеристик такой модели с учетом ДО СП существует точные методы, однако, сложность получаемых при этом для ик и (&=ТЛ) выражений на позволяет найти аналитическое решение сформулированной задачи проектирования УК, В этих условиях для ее решения был разработан эвристический алгоритм. На первых этапах алгоритма определяются верхние граница емкости буфера и числа процесорсз, а на последующих - производится последовательное уточнение выбранных значений.

С использованием разработанных алгоритмов установлено, что!

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

б) применение ДО СП позволяет уменьшить быстродействие или количество ЦП ВС, а также емкость буфера и число процессоров УК, по сравнению с ДО БП.

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

■ Известны: а) топология СПД, состоящая из Я узлов и M каналов (бесшумных и абсолютно надежных); б) стоимостные функции каналов;

в) параметры сообщений Н классов (матрицы интексивностей входных потоков6 среднее значение I и КВ длин сообщений класса й=ТТЙ)

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

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

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

различных каналах СПД, принятие которых позволяет моделировать —* —►

каналы в виде ОК СМО Н;./С;{/1, а СПД в целом - неоднородной РСеШ*.

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

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

2) стоимость Б сети при ограничении Т^Т* (обратная задача);

3) стоимость СПД при ограничениях 2'^Т* (й=0), где Тк -среднее значение времени доставки ^-сообщений;

4) стоимость 5 СПД при ограничениях (&=Т7"В), где Р(УЛ>1/*3 - вероятность превышения временем доставки ^-сообщений [^.соответствующего допустимого значения У*;

5) стоимость Б при сметанных ограничениях, когда налагаемые ограничения для одних классов сообщений являются средними, а для остальных классов - вероятностными.

Решение прямой и обратной задач выбора ПС каналов с использованием метода неопределенных множителей Лагранжа сводится к решению соответствуют« систем нелинейных уравнений. В качестве другого ¡возможного пути решения данных задач рассматривался путь сведения . исходной неоднородной нагрузки СПД к эквивалентной

однородной с последующим использованием существующих методов, полагая, что КВ v(t), i=TJI, длин однородных сообщений в каналах сети равны единице.

Проведенные исследования с целью сравнения результатов решения прямой задачи выбора ПС, полученных при неоднородной и эквивалентной однородной нагрузках, показали, что относительная разница ô между ПС каналов в двух вариантах в широком диапазоне изменения исходных параметров сети в большинстве своем меньше 5Î5 и лииь в отдельных случаях для отдельных каналов достигает 10%, Сравнение соответствующих оценок времени задержки Т показало, что относительная разница ô между ними возрастает с увеличением нагрузки сети, значений КВ vh (й=Т77?), среднего пути сообщений (при изменении топологии сети путем удаления каналов), степени неоднородности нагруби (разброс между средними длинами неоднородных сообщений) И может составить более 100%. С другой стороны, установлено, что если реальные КВ длин однородных сообщений ' в каналах сети близки к предполагаемым, т.е. v(i)«1 (i=О"), .то оценки Т в двух варианта* гт я чаются незначительно (5 <2S).

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

Соответствующие ^следования, проведенные для обратной задачи показали, что при ее решении, в отличие от прямой задачи, и при выборе ПС каналов необходимо учитывать неоднородность .нагрузки <а достигает 47%) тогда, как остальные результаты и вывода прямой и обратной задач аналогичны.

Использование ДО СП в прймой и обратной задачах выбора ПС каналов существенно влияет на эффективность функционирования СПД. Установлено, что количественная мера влияния ПСУ, определяемая как относительная разница между оценками задержки Т в прямой задаче и стоимости S в обратной задаче, полученными при рассматриваемой ДО и ДО БП, увеличивается с увеличением, нагрузки сети, значений КВ v (fc=ï7ïï), степени^ неоднородности нагрузки, среднего пути сообщений и может составить десятки процентов (до 90%). При

этом, применение ДО СП, где более высокий приоритет (ОП или АЛ) назначаете^ классу сообщений с.меньшим значением средней длины,

уменьшает, а - ДО СП о обратным порядком назначения приоритетов увеличивает оценку критерия эффективности по сравнению с ДО БП. В

этом смысле наилучшей ДО является ДО АЛ, а наихудшей - ДО АЛ.

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

усиливается (увеличивется относительное уменьшение Г или 5) при:

_ —>

уменьшении значений КВ vk (к-Т^Я); переходе к ДО СП; уменьшении загрузки сети сообщениями классов 2, 3,..., Н (если эта загрузка достаточно большая, то эффект может и не наблюдаться); увеличении усредненной по класам 2, 3,..., И длины сообщений; уменьшении среднего пуи сообщений (при изменении топологии сети путем добавления каналов); увеличении степени неоднородности нагрузки. При этом относительное уменьшение задержки Т и стоимости S может достигает 70% и 55% соответственно.

При решении задачи выбора ПС каналов при средних ограничениях на времена доставки неоднородных сообщений налагаемые ограничения по одним классам сообщений выполняются в виде строгих неравенств, а по другим, чаще всего по одному классу, названному "критическим", - в виде равенства в пределах заданной точности. Проведенные при этом исследования временных характеристик обслуживания сообщений в СПД позволили установить, что: а) для "критического" класса характерно минимальное значение отношения (Г*-^)/!^, где ifj, - среднее время ожидания в сети fc-сосбщений; С) при разшх уровнях нагрузки сети или используемых ДО СП "критическим" классом могут быть разные классы сообщений; в) если на каком-то диапазоне увеличения нагрузки сети класс h является "критическим", то на этом диапазоне время задержки Th остается неизменным, а время задержки Тк й-сообщений (k/h) увеличивается, если и наоборот, '

В задаче выбора ПС при средних ограничениях уменьшение стоимости сети за счет использования ДО'СП может составить более 403 от стоимости сети при ДО БП. При выборе ДО показателем, определяющим необходимость изменения приоритета k-сообщений, является отношение б^р1*-!^)/1^ чем меньше fife, т.е. чем "критичнее" класс, тем выше приоритет, назначаемый данному классу. Однако "критичность" классов или значения б ■ (к=Т7В) меняются при изменении нагрузки сети и таким образом при разшх нагрузках сети

наилучшими ДО могут быть разные ДО.

Методика решения задачи выбора IIG каналов сети при вероятностных ограничениях основана на сведении заданных ограничений к ограничениям i^-lT* (Ä=T7?I) на средние времена доставки'сообщений.

При этом значение Г* определяется из уравнения 1 ,) =S*

путем решения его относительно Здесь Fk(t,T) - функция

распределения времени доставки й-сообщений _ и , аппроксимируемая

по первому ГА и второму г начальным моментам данного времени в

зависимости от значения KB v('Ji,) = (Г};/^-1)'/г либо распределенном

Эрланга (при v(Z7 К1), либо гиперэкопонекциальнкм распределением.

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

В четвертой главе рассматривается задача оптимального распределения потоков в СПД с неоднородной нагрузкой, которая при заданных топологии сети, параметрах неоднородных сообщений, ДО СП и ПС каналов состоит в том, чтобы входные потоки каждого класса сообщений для каждой упорядоченной пары (n.m) узлов сети разделить между маршрутами, Еедудкми из узла-отггревигеля п в узел-адресат л (п,и=1,'?/) ;'ак, чтобы результирующая структура потоков в СЦЦ оптимизировала выбранный критерий эффективности функционирования при выполнении заданных ограничений.

Рассматриваются две постановки задачи распределения неоднородных потоков, в которых:

1) минимизируется время задержки Г при выполнении условия

д

сохранения потоков в СПД и ограничениях £ f[k)<Pl (1=Т7Я), где

eil

- поток й-сооСщений в t-ом канале сети; ' • я

2) максимизируется производительность сети У= 2 Л.1. при

к=1

ограничениях Г^^Г* на среда« времена доставки сообщений; здесь Л^- интенсивность суммарного внешнего потока k-сообщвний (&=1,Я).

■ Для решения сформулированных задач РП в СПД с неоднородной нагрузкой предлогеьтся модификации известного алгоритма отклонения потоков 'АОН). При минимизации времени задержки Г на каждой итерации мсоф-циг'. &%кного АОП отклонение некоторой части всех путевых (или :- чняльных) потоков й-сосСдений <&=Т73) до достижения

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

равенством Ь^^дТ/д?^* (1=0).

Метрика 1<*> характеризует линейную скорость возрастания задержи Г при бесконечно малом увеличении потока й-сообщений в 1-канале и, следовательно, маршруты, кратчайшие в этой метрике, являются наилучшими для снижения задержки Т.

В зависимости от доли отклоняемых потоков сообщений разных классов были рассмотрены две версии модифицированного АОП:

1) А-модификацич,в которой на данной итерации алгоритма отклоняются потоки только одного класса - класса, отклонение потоков которого дает максимальное снижение задержки Г;

2) Б-ЮмИфикация, в которой доли отклоняемых потоков отделяются одинаковыми для всех классов сообщений.

Однако, как показали проведенные исследования, относительная разница между оценками Тл и Гв, полученными с использованием соответственно А- и Б-модафккаций, не превышает 3% в широком диапазоне иьменения исходных параметров СПД. Хотя Т всегда меньше Г£1 Б-модификация АОП предпочтительнее с точки зрения необходимого для его реализации объема вычислений.

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

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

16) то ке, но с учетом значений КВ длин однородных сообщений, одинаковых для всех каналов сети;

2а) пересчет нагрузки производится на уровне отдельных каналов сети, приравнивая к единице значения КВ v(t) длин однородных сообщений в каналах.

26) то же, но с учетом КВ у(1), ЫО?.

Пересчет параметров в вариантах 2а и 20 производится на каждой итерации АОП. .•

Проведенный в широком диапазоне варьирования исходных данных задачи РП анализ сравнения оценок времени еадержки Г, полученных с использованием Известного АОП при разных вариантах пересчета

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

нагрузки сети, значений КВ ур , среднего пути сообщений,

степени неоднородности нагрузки, а также с уменьшением ПС каналов и для вариантов пересчета 1а, 16 и 2а может составить 25%, 55% и 60% соответственно, а для варианта 26 - 3% при ДО БП и более 507, при приоритетной нагрузке СПД.

Таким образом, в общем случае при решении рассматриваемой задачи РП необходимо учитывать неоднородный характер нагрузки. Однако при неоднородной нагрузке время сходимости АОП (в А- или Б-моди*икациях) значительно (на порядок и более) выше, чем при однородной нагрузке. В ходе проведенных исследований установлено, что хорошим компромиссом мевд эффективностью алгоритма с точки зрения времени, вычислений и точностью получаемых при этом результатов является следующий подход: маршруты передачи сообщений определяются при однородной нагрузке в - вариантах 2а и 26 пересчета параметров, а оценка средней задержки проводится с учетом неоднородного характера нагрузки, направляя неоднородные потоки сообщений по полученным в однородной срзде оптимальным маршрутам. При таком подходе для вариантов пересчета 2а и 20 значение 5у не превышает соответственно 2% и 5% На всем диапазоне изменения исходных данных тогда, как для вариантов 1а и 16 может составить 60% и 85Гь.

Уменьшение времени задержи Г за счет использования ДО СП может составить 50% и более от значения задержки Т при.ДО БП.

Алгоритм решения задачи распределения неоднородных потоков, где оптимизируется производительность сети при средних ограничениях Т^Т* (й=Т7?) представляет собой итерационный процесс совместного выполнения алгоритмов ограничения нагрузки (АОН) и отклонения потоков.

АОН, исходя.из выполнения ограничений Т^ъ опреде-

ляет максимальное значение производительности V,■ соответствующее текущему РП, причем изменение V проводится путем умножения штенсиЕНОстей входных потоков сообщений всех классов на один и тот же масштабный множитель р. В результате в сети появится "критический" класс Л, для которого соответсвуюсдее ограничение на время задержки выполняется в виде равенства, тогда как для остальных классов - в виде строгих неравенств. Дальнейшее увеличение производительности сети возможно только путем уменьшения

средней задержки сообщений "критического" класса. Для этого используется АОЙ, в котором равные доли путевых (или канальных) Потоков сообщений всех классов отклоняются на маршруты, кратчайшие в метрике дли ; каналов I т.е. на маршруты дакщие максимальное снижение времени задержи Тн сообщений "критического" класса. При этом средние задержи в сети сообщений остальных классов также изменяются, причем как в сторону уменьшения, так и в сторону увеличения.

■Алгоритм решения рассматриваемой задачи РП завершается, если на очередной его итерации выполнение АОН приводит к уменьшению текущего значения производительности сети'.

В четвертой главе приводятся также результаты имитационных экспериментов по аттестации принятых в третьей главе предположений о простейшем характере процессов поступления сообщений разных классов и независимости процессов их обслуживания в каналах сети. Установлено, что для СПД средней связности при простейших внешних потоках неоднородных сообщений значения • КВ интервалов их поступления в каналы сети лежат в интервале от 0.8 до 1.2, а соответствующие погрешности расчета временных характеристик Т и №=Т7й) не превышают 8% на всем диапазоне значений Средней загрузки сети. При этом времена передачи неоднородных сообщений в каналах СПД предполагались детерминированными.

Погрешности расчета временных характеристик Т и Тк {к-1,Н), обусловленные принятием предположения о независимости процессов обслуживания, как показали результаты аттестации, не превышают 15% в области значений загрузки сети до 0.5 и могут достигать 30% при увеличении загрузки сети до 0.8.

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

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

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

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

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

Разработанные методы и алгоритмы решения рассмотренных задач реализованы в виде комплекса программ автоматизированного пр01К-тирования, включающего в себя компоненты (программа) синтеза Бб» проектирования УК, выбора ПС каналов и РП в СПД.

Разработанные программные средства построены по модульному принципу и представляют собой открытые системы, возможности И функции которых при необходимости морут быть. расширены путем включения дополнительных программ. Все программы реализованы на языке Турбо-Паскаль версии 5.5 для 1ЕМ ?С АТ. ,

В каждом из компонентов комплекса программ предусмотрены следующие возможности.

1..Ввод исходных данных (КД) в рекиме диалога.

2. Контроль корректности ввода Щ с повторным запросом после

сообщения об ошибке значения некорректно введенного параметра.

3. Коррекция ИД путем выбора из "меню исходных данных" наименования (или номера) соответствующего параметра.

4. Сохранен,!- Щ на магнитном носителе.

5. Вывод результатов расчетов на экран и/или печать, а также их запись на магнитный носитель.

6. Варьирование параметров, входящих в состав ИД, с целью выполнения многозариантнкх расчетов.

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

Программы комплекса занимают соответственно 150, 25, 120 и 95 Кбайт оперативной памяти ЭВМ, а ограничения на область их применения составляют: максимальное число классов запросов или сообщений - 10; количество устройств комплектации или узлов СПД -не более 30; максимальное количество используемых при синтезе ВС файлов - 35^

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

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

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

. 3. Сформулирована и решена задача Выбора ПС Каналов СЦД с неоднородной npHOpHioMofi нагрузкой в постановках с однородными (на стоимость или срэдную задержку) й неоднородными (средние и/или вероятностные - на йремейа Доставки сообщений разных классов) ограничениями.

4. Разработали методы и алгоритмы распределения неоднородных потоков в СПД при выборе в качестве критерия эффективности средней задержки сообщений или производительности СПД (при ограничениях на средние времена доставки сообщзний).

5. Проведены исследования влияния неоднородности нагиузки и использования ПСУ на результаты решения задач синтеза ЭВМ и УК, выбора ПС каналов и распределения потоков в СПД и показана необходимость их учета в процессе системного проектирования.

6. Разработана методика системного проектирования СПД с неоднородной нагрузкой, направленная на определение топологии, дискретных значений ПС каналов, совокупности маршрутов передачи сообщений и синтиз узлов СПД при ограничениях на средние времена 1гребывашя неоднородных сообщений з СПД и надежность.

Разработанные методы и алгоритмы реализованы в виде комплекса программ автоматизированного проектирования. 1

По материалам диссертации опубликованы следующие работы.

1. Алиев Т.Н., Алиев Щ.С. Комплекс программ структурно-функционального синтеза систем приоритетной обработки данных// Математические метода исследования сетяй связи и сетей ЭВМ. Тезисы докладов. - Минск, 1990. - с.6-6. -

2. Алиев Т.И., Алиев Ш.с. Структурно-функциональный синтез проблемни-ориентиров-шшх систем//-Ш Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. - М., 1990. - С.99-100.

3. Алиев Т.И., Алиев Ш.С., Довгий П.С, Реализация методов исследования топологии вычислительной сети и оценки пропускных способностей каналов связи// Сети связи и сети ЭВМ как модели массового обслуживания. Тезисы докладов. - Минск, 1991. - с.7.

4. Алиев Т.И., Алиев Ш.С. Выбор пропускных способностей каналов связи сетей передачи данных с неоднородной нагрузкой (50910000404)// Алгоритмы и программы.- М., 1991,- J» Т/8.- С.8.

5. Алиев Т.И,, Алиев Ш.С. системотехническое проектирование вычислительных систем с неоднородной- нагрузкой (50910000405)// Алгоритмы и программы.- М., 1991.- » 7/8.- С.8.

6. Алиев Ш.С. Выбор пропускных способностей каналов связи в сетях передачи данных с неоднородной нагрузкой при относительных ограничениях на времена доставки (50920Q00063)// Алгоритмы и программы.- М., 1.332.- Л 1/2.- С.4.

7. Алиев Т.И., Алиев Ш. .. Сравнительный анализ выбора пропускных способностей каналов связи сетей передачи данных с неоднородной и однородной нагрусками// Сети связи и сети ЭВМ. Анализ и применен е. Тезисы докладов. - Минск, 1992. - С.3-4. ..

8. Алиев Ш.С. Выбор пропускных способностей каналов связи в сетях передачи данных с неоднородной нагрузкой при относительных ограничениях на времена задержек// Сети связи и сети ЭВМ. Анализ и применение. Тезигы докладов. - Минск, 1992. - С.7-8.

9. Алиев Ш.С. Модификация алгоритма отклонения потока в сетях с неоднородной нагрузкой// V Совещание по распределенным вычислительным системам И сетям (СЮ8-92). Тезисы докладов. - М., 1992. - С.86-88.

10. Алиев Т.И., Алиев Ш.С. Проектирование вычислительных систем с. неоднородной нагрузкой// Вычислительная техника в автоматизированных системах контроля и управления: Межвуз.сб.науч.тр. - Пенза: Изд-во Пенз. политехи, ин-та, 1992. - Вып. 22. - С.4-6.

11. Алиев Т.Н., Алиев Ш.С. Выбор пропускных способностей каналов связи в сетях передачи данных с неоднородной нагрузкой// Известия вузов. Приборостроение. - 1993. - Л» 1.- С.61-68.

12. Алиев Ш.С. Определение пропускных способностей каналов связи сети с неоднородной нагрузкой при вероятностных ограничениях// Математические методы исследования систем и сетей .массового обслуживания. Тезисы докладов. - Минск, 1993. - С.6.

Подписано к печати 27.04.93 г. Заказ 141 Тираж 100 экз.

Объем 1 ,п.л. Бесплатно.

Ротапринт. СПИТМО. ЮОООО, г. Санкт-Петербург, пер. Гривцова, М.