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

КИЕВСКИЙ

Vi 3 Oft

ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

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

НЕ ИРА ВАЛЬВЕРДЕ М. АРТУРО (Перу)

• УДК 681.32

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

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

комплексы, системы и сети

АВТОРЕФЕРАТ

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

КИЕВ-1993

Работа выполнена на кафедре специализированных вычислительных средств Киевского политехнического института.

Научный руководитель: доктор технических наук, профессор Тарасенко В. П.

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

- кандидат технических наук, с. н. с. Цвелодуб О. В.

Ведущая организация - Институт проблем регистрации информации АН Украины /г. Киев/

Защита состоится 993 г. Вчасов на

заседании специализированного Совета Д 068.14.09 в Киевском политехническом институте.

Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения, просим направить по адресу: 252056, Киев-Бб, просп. Победы, 37, КПИ, Ученому секретарю.

С диссертацией можно ознакомиться в библиотеке Киевского политехнического института. -С/

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

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

доцент О. В. Вузовский

АННОТАЦИЯ

Г'-л-.'п настоя!",1;!! диссертационной работы является исследование и разработка методов структурно-алгор;;': ¡.^.ческой организации микропроцессорных устройств (1ШУ) систем пяредачи информации (СПИ), обеспечивающих передачу заданных объемов информации различных уровней приоритетности по каналам связи с требуемой достоверностью и быстродействием.

Для достижения поставленной цели решались следующие задачи:

- исследование и разработка методики оценки производи-телы.ост:! МПУ СПИ;

- исследование, разработ!« и оптимизация алгоритмов функционирования МПУ СПИ;

- разработка методики формализованного определения структурной организации МГУ СПИ;

• - исследование возможностей построения графо-аналитических моделей для оценки параметров процессу автоматического восстановления отказоустойчивых МНУ СПИ.

Автор выносит на защиту следующие основные положения:

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

2. Методику оптимального распределения функций центров коммутации пакетов (ЦКП) неаду микропроцессорными модулями (МПМ) , обеспечивающую минимизацию обмена информацией, передаваемой между модулями.

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

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

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

** С -

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

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

■р,,^СТР р .:s;1( o-'iJijeiiVHuH база с виде !Л1 и 1лПС определяет програмччую реализацию устройств СПИ, которая, в отличие от аппаратной, вносит существенные особенности и процессе проектирования устройств СПИ. К таким особенностям, например, относятся необходимость учета конкуренции процессов за ограниченный вычислительный ресурс; наличие нескольких асинхронных Параллельных процессов; ограничения на внутреннюю оперативную пчиять; приоритетность обслуживания информационных потоков и др. В связи с этим особую актуальность приобретает задача структурной организации и разработки алгоритмов функционирований микропроцессорных аппаратно-программных средств, вилолняю-сл* щгакции различных устройств СП!!. С этой задачей тесно связаны вопросы обеспечения отказоустойчивости и производительности таких средств. Решение указанного круга задач относится к области разработки методов проектирования функционально-ориентированных средств шчкелительзой техники и имеет больную практическую значимость.

Ну'УОДЬ! исследования.базируются на использовании аппарата вычислительной математики, теории цифровых ЭВМ и микропроцессорных систем, .теории графов, теории массового обслуживания, отдельных положений теорйи алгоригюв и др.

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

Основные научные результаты, представленные на завдту, заключаются в. следующем;

1. Разработана1методика Определения максимально возможней производительности 1ШС с функциями СП, фактической производительности' 1Л.ЗЮ при различных характеристиках потоков обращений к o6ir,eft памяти (ОП). позволящдя также проследить зависимости производительности ММГО от числа 1.31, связности выполняемых программ, производитёльности ОП. и МП

2. Прёдлокзна методика нахождения оптимального распределения функций ЦКП по 1Ш, при котором достигается минимальный обмен информацией между ними.

3. Изложена методика обоснованного выбора структурной организации.. 15ЯС. для СП и разработана модель СП в виде замкнутой

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

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

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

Апробация работы. Основные результаты исследований, отра-шшые в диссертационной работе, ■ докладывались и обсуждались на научно-технических семинарах кафедры специализированных вычислительных средств Киевского политехнического института (1991-1992 гг.) и на научно-технической конференции "Аппаратные и программные средства локальных сетей ЭВМ" в г. Киеве (1991 г.;

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

Структура и объем работы. Диссертационная работа состоит из введения, трех глав* заключения и списка литературы (162 наименования). Основное содержание работы изложено на Ш страницах машинного текста, работа содержит В>Л рисунков, и 2 таблицы.

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

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

, Вторая глава посвящена выбору микропроцессорных средств при проектировании устройств СПИ.-. Рассмотрены методики оценок

структурных и функциональных характеристик ММШ для центров коммутации, производительности ММПС с функциями связного процессора, а также изложена модель для оценки параметров процесса автоматического восстановления ОУСП МПУ СПИ.

В третьей главе рассмотрены определение объема локальной буферной памяти для канальных модулей сетевых процессоров СПИ и реализация алгоритма функционирования центров коммутации па-■ кетов СПИ в ММПС. Исследованы структурная организация связного процессора ЦКП СПИ и'способ организации страничной локальной памяти для управляющих модулей связных процессоров.

В заключении сформулированы основные результаты работы.

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

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

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

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

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

Анализ множества задач, выполняемых.устройствами СПИ, показывает, • что множество Г выполняемых функций целесообразно разбить на ряд Подмножеств Ш « р. Так могут быть выделены

1*1

Я'Чйов

- б -

подмножества сетевых Функций ^, связанных с передачей сообщений и управлением потоками и сетью в целом, терминально-пользовательских функций Е^., функций обмена с устройствами ввода-вывода (УЕВ) , управляющих функций £ , сервисных функций ^функций контроля и обеспечения надежности .

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

Специфическим устройством СПИ, обеспечивающих передачу й сеть обмена информации (СОИ), является подмножество функций . Состав его как количественно так и качественно, определяется типом устройств СПИ.

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

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

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

Базовым элементом для создания МПУ систем и сетей телеобработки информации является связные процессоры.

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

процессора, состоящая из трех групп функциональных модулей (ФМ). Каждый ФМ осуществляет аппаратную поддержку функций, реализуемых соответствующей подсистемой.

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

На этапе проектирования микропроцессорных устройств СПИ одной из важнейших задач является выбор некоторого ряда МП-семейств БИС. Такой выбор производится после определения класса структурных организаций устройства СПИ в микропроцессорном базисе.

Задача определения реальной производительности (быстродействия) является, как известно, актуальной еще со времени появления первых ЭВМ. Применительно к микроэвм и МП, повиди-мому, лучшим способом определения производительности является использование оценочных программ типа "bench-mark". Программа типа "bench-mark" - это программа решения на оцениваемом. МП такой задачи, которая по составу операций соответствует классу задач предполагаемого применения. Обычная длина "bench-mark" программы - 100... 200 команд. ( В ее составе обязательно должны быть операции по вводу и выводу информации. Важным достоинством процедуры выбора МП на основе "bench-mark" программ является то, что она не только определяет время решения задачи

на конкретном МП, но и обнаруживает достоинства и недостатки

/

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

Таким образом, предложенный способ на основе оценочной "bench-nark" программы позволяет определить значение быстродействия МП и сделать вывод о возможности использования данного МП в МПУ СПИ. ■

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

г*

использования ММПС в центрах коммутации (ЦК) обычно принимают такие условия

t< tj.< te. P(t) > Pt (U) > % (tp), или *

t^> t = min, (tj. ) < P(t) - max, где t - время реализации заданного набора функции (ЗНФ) с помощью ММПС, t^ - заданное время реализации ЗНФ, to - среднее время реализации ЗНФ на отдельном микропроцессоре, P(t) - вероятность реализации ЗНФ с помощью ММПС за время t, Р^ -вероятность реализации ЗНФ на заданное время tj, , и Fi (t0 ) -вероятность реализации ЗНФ. на отдельном микропроцессоре за время to .

Метод анализа MII-ситуации в ЦК. Основная идея метода заключается в нахождении оптимального уровня реализации ЗНФ, а также в определении временных и вероятностных характеристик МП-ситуации, которые позволяют судить об эффективности выбранной ММПС. ЗНФ может выполняться на следующих МП-уровнях (j -номер уровня): j - 1 - весь ЗНФ реализуется каждым микропроцессором без диспетчера; j - Z - часть ЗНФ реализуется на уровне дублирования, другая часть распределена между микропроцессорами и реализуется параллельно без диспетчера; j = 3 - то же, что и при j - 2, но с диспетчером; j - 4 - весь ЗНФ распределяется между микропроцессорами и реализуется с диспетчером; j =5, то же, что при j = 4, но без диспетчера.

Различные МП-уровни характеризуются различной эффективностью использования ММПС. В то же время, задавая определенные значения t^, и Р^ , можно выбрать субоптимальный или оптимальный МП-уровень, обеспечивающий выполнение главных условий: t < t^, и P(t) > ^ (t^.). Получены выражения 'для оценок времени и вероятности реализации ЗНФ в ММПС.

Методика определения оптимального МП-уровня. Если известен ЗНФ и характеристики ММПС t0 , Л/f М, N^' , tcj и заданы tß и Р^ , где Т^ - средняя наработка на отказ отдельного микропроцессора; М - число микропроцессоров в ММПС; Ncj - среднее число обращений к диспетчеру на j уровне реализации ЗНФ; te - среднее время работы диспетчера при обработке одной заявки, то оптимальный МП-уровень Определяется как результат выполнения следующего алгоритма:

1. Найти границы реализуемости 5НФ ^ < ^ и > 1о / М.

2. Рассчитать показатели I? для возможных уровней при

У « Ч ^

3. Проверить условие В > и выбрать допустимый уровень.

4. ВЫЧИСЛИТЬ

5. Определить минимальное время уровня по условию

у там, - ^ > 0.

6. Рассчитать показатели ^ для всех и выбрать оптимальный МП-уровень по условию ггах Я >

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

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

Максимальная производительность ММПС достигается при условии, что потоки обращений от МП к ОП регулярны и конфликты отсутствуют. (Тактическая же производительность зависит от случайных величин - интервалов Формирования каждым МП обращений к ОП и длительностей их обслуживания - распределенных, например, по экспоненциальному закону. Для многих технических типов ОП длительность обслуживания определяется циклом ОП и является постоянной величиной. Поэтому с инженерной точки зрения представляет интерес также оценка производительности ММПС, когда формирование обращений происходит в случайные моменты времени, а их обслуживание происходит за постоянное- время X • Заметим, что порядок получения оценок во всех трех вышеуказан-' ннх случаях одинаков и вытекает из следующего.

Получено выражение для оценки производительности ММПС

где 1 - индивидуальные потоки; То - среднее время выполнения одной команды любым МП в ММПС; 1 ср - среднее число обращений к ОП.

- 10 -

В регулярных потоках обращений интервалы между соседними обращениями каждого МП постоянны и равны Те /ц (q - связность программы по ОП). Количество МП, обслуживаемых ОП без задержки далее будем называть критическим. Для регулярных потоков это количество равно

1 кр - Т0 / ц?

Если 1 > 1цр , то образуется очередь из lgf МП, ожидающих обслуживания. При этом

Itp - 1 " Т0 / qr

Тогда производительность ММПС с функциями СП определяется

как

Vmax= j 1 ' то "Ри U Up,

(^1 / Ц% при 1 >

При фиксированной связности каждого МП по ОП максимальная производительность ММПС не зависит от числа МП.

В случайных потоках обращений к ОП с постоянным временем их обслуживания конфликтные ситуации возможны при любом числе МП. Среднее число МП, ожидающих обслуживания - lcp - 1 --Тв/ q<(i - Р0)

Тогда производительность ММПС с функциями СП определяется

как .

V - (1 - Рв ) / цх где FJ, - стационарная, вероятность отсутствия обращений к ОП.

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

Таким образом, изложенная методика позволяет определить максимально возможную производительность ММПС с функциями СП, фактическую производительность ММПС при различных характеристиках потоков обращений к ОП,• а также .проследить зависимость производительности ММГЮ от числа МП,' от связности выполняемых программ, от производительности ОП и МП.

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

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

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

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

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

1) ввод в СП - запись в ЛБП пакета со скоростью передачи в канале связи;

2) ожидание в очереди на отработку пакета процессором КМ;

3) обработка пакета процессором;

4) ожидание в очереди к выходному каналу;

Б) передача пакета в канал;

6) ожидание квитанции.

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

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

Для определения объёма памяти при допустимой вероятности отказа ^ последовательным изменением числа зон (И) можно найти минимальное I/*, удовлетворяющее условию Рк4 > Рл (Н*).

где Рв (№*) - вероятность отказа в приеме пакета в ЛБП КМ как

к,

- 12 -

функцию минимального числа зон Ы*

Объем одной зоны ЛБП КМ q может быть найден по первым, двум моментам распределения размеров пакетов и заданной вероятности переполнения ^ . Решение уравнения -

с^л)* и*4 ёкл 11 ¿и » Ра.

где Д ^ ^и - ; к - соответствует порядку рапре-

деления Эрланта, для целого ц определяет объем одной зоны ЛБЕ При ^ =0,97 предыдущее уравнение преобразуется к виду

1=о I /

Выражение 0 - N • ц определяет верхний' предельный объем ЛБП КМ СП.

Таким образом, использование замкнутой многофазной СМО как модели СП позволяет определить верхний требуемый объем ЛБП для канальных модулей связных процессоров.

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

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

Найти такое множество подграфов ,иа ) исходного

графа 6(Х,Щ, г - Т71 ( X - множество вершин, а и - множество дуг графа), которое обладало бы перечисленными ниже свойствами:

2. Х^ П Х?2 = Ф, г;пе Ф - пустое мнолгестЕО, г^ £ ;

а + , а* Я,

где если ТЪМеЯ*

УгМ)* [о, если 1Г2 Ci|x)tU9■

- веса 1-й и к-й вершин и * где N число вер-

сии). А У^ - соответствует объему памяти ММ. Заметим, что задача имеет решение, если

¿ЕЪ ■

Й ам

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

и

А

_ Щ-ЩЩЩ

где i - 1,М; М - число МПМ; '¿'({.к) - вес дуги.

Оптимальным решением поставленной задачи бу.эт такое ¡'но-*дство подграфов ЕдЛХч ), г = Гд*, исходного графа Е(Х,11), которое при выполнении условий 1, 2, 3 максимизирует 4.

Таким образом, предложенная выше методика позволяет найти оптимальное распределение функций ЦКП по' МПМ, при котором достигается минимальный обмен информацией между ним;!.

■ В данной работе исследована структурная организация связного процессора ЦКП СПИ. Эта структура микропроцессорных систем (МПС) в назначений СП должна соответствовать магист-' ральной Модульной ММПС с функциональным типом организации модулей, имеющей как ОП, так и локальную память (Л!) в отдельных тЙ1-ыодулях. В структуре имеются функционально-ориентированные МП-модули, которые обозначены следующим образом: КМ - каналь-п"? модули (линей::*") процессоры); ОМ,- обрабатывающие /" модули; .МВВ' - МП-модули ввода-вывода Сами функциональные ЬИ-подули состоят из МП, ЛП, аппаратных средств' сопряжения с

ОП, а также дополнительных устройств для сопряжения с- каналами связи (для Й,(), либо с устройствами ввода-вывода (для МВВ).

Для оценки качества структуры К(ЫПС (в назначении СП) будем использовать суиларную величину коэффициентов использования всех Ш. При этом коэффициентом использования i-ro Щ будем называть величину

Ь в hm Ш1

где t-i(t) - время занятости i-ro МП выполнением заданных функций на интервале (О,t). Структура СП состоит из М функциональных Ш-модулей и ОП. При этом каждая ЛП доступна лишь Ш со-ответствукщгго модуля и при обращении к ЛП конфликты ье возникают. Пусть р - вероятность заявки (обращения) к собственной ЛП, а времена подготовки (формирования) заявок е И и выполнения заявок в ОП и ЛП являются независимыми экспоненциально распределенными случайными величинами со средними значениями Тд,п , T0f¡ и ТЛП соответственно. Очевидно, что

Для определения представим структуру СП в виде закинутой сети, состоящей из трех систем массового обслуживания (СЫО). При атом СКЭ1 соответствует подготовке заявок в КП, СЫ02 - выполнению заявок в ЛП, СШЗ - выполнению заявок в ОП комплекса.

Постольку каждый Ш в составе МП-модуля мокзт обращаться лишь к своей ЛП, то СШ1 и СМ02 являются М-канальными CMQ без очередей, а СЮЗ - одноканалыюй СШ с ожиданием. Йз СШ1 с вероятностью р заявка попадает в CUC2, а с вероятностью q=l-p в СШЗ. Кз СМ02 и СМОЗ заяЕки с вероятностью, равной единице, возвращаются в СШ1. Пусть Д^' - интенсивность обслуживали.'! заявок в CMOj, (j =1, 2, 3), причем J¿ j - ТДя ?

~ Тдя , = ГйП ,

Тогда суммарная величина коэффициентов использования всех МП в СП, равная спеднему числу заявок КЬ , в СМ01, может быть найдена как .

Я = (А__

где

2) м = + иг +

число заявок в СкЬ). Шсдеднее выражение определяет верхнюю

оценку суммарной величины коэффициентов использования МП в СП

В данной работе предложен способ матрично-страничной организации ЛП для управляющих модулей связных процессоров СПИ. Сущность способа состоит в том, что все адресное пространство устройства контроля (УК), имеющее 2п" адресов (п - разрядность адресной шины МП), разбивается на одинаковых зон емкостью адресов каждая. Физическая ЛП выполняется в виде блоков или страниц емкостью в й11*11 слов. Каждой зоне адресного пространства ставится в соответствие несколько таких страниц ЛП (вместо одной страницы в нерасширенной ЛП), причем число страниц в отдельных зонах молит быть разным. В результате этого .ЛП УК приобретает конфигурацию матрицы, элементами которой являются страницы ЛП емкостью 2п'к слов. Матрица имеет определенное число столбцов и 21! строк, т. е. зон, причем все страницы одной зоны занимают один и тот же участок адресного пространства.

Таким образом, вмсеописанный способ, позволяет организовать матрично-страничную ЛП УК СП, емкость которой могдт быть во много раз больше прямо адресуемой (нерасширенной) Ж Кроме того, для увеличения емкости страницы ЛП можно две или больше зон ЛП объединить в одну, тогда матрично-страничная локальная память содержит страницы различной емкости.

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

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

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

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

- 16 -

ОУСП, при относительной простоте самой модели.

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

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

' 1. Швец Е. М. , Медведев С. Л, Нийра В. М. А. Схемотехническое проектирование высокопроизводительных станций локальных вычислительных сетей// Вестн. Киев, политехи, ин-та. Автоматика и электроприборостроение. - К. ,1992.- Вып. 29, с. 49-53.

2. Тихонова О. А. , Медведев С. Л , Нейра В. М. А. Зависимость характеристик волоконно-оптических сетей связи от параметров элементной базы//Вестн. Киев, политехи, ин-та. Автоматика и электропраборостроение. - К. ,1992. - Вып. 29, с. 45-49.

3. Еейра М. А., Тарасенко В. П. Структурная организация связного процессора центра коммутации пакетов.- Киев, политехи, ин-т, 1992. - 11 е.- Деп.в УкрИНГЗИ 03.12.92.- N 1884Ук92.

4. Нейра М. А., Тарасенко В. П. Модель для оценки параметров .процесса, автоматического восстановления отказоустойчивых связных процессоров. - Киев, политехи, ин-т, 1992. - 11 е.- Деп. в УкрИНГЗИ 03.12.92.- N 1885УК92.

5. Нейра М. А., Тарасенко В. П. , Швец Е. М. Оптимальная реализация алгоритма функционирования центра коммутации пакетов в мультимикропроцессорных системах// Вестн. Киев, политехи, ин-та. Автоматика и электроприборостроени^. - К., 1992. - Bin. 30, с.

6. Нейра М. А., Тарасенко В. П., Швец Е. М. Оптимизации мультимикропроцессорных средств для систем коммутации// Вестн. Киев, политехи, ин-та. Автоматика и электроприборостроение. - К., 1992.- Вып. 30, с.

7. Швец Е. М., Медведев С. Л , Нейра М. А. Выбор структурной организации высокопроизводительной специализированной станции локальной вычислительной сети и расчет ее основных характеристик. -Тез. докл. науч.-техн. конф. "Аппаратные и программные средства локальных сетей ЭВМ".- Киев, 1991.

Соискатель

ЩЮШ^З Ы. А. Нейра