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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РСФСР ПО НАУКЕ И ВЫСШЕЙ ШКОЛЕ Радиотехнический институт им- 8.Д.Калмыкова

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

ПЬЯВЧЕНКО Алексей Олегович

УДК 681.31:324

РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ И АППАРАТНЫХ СРЕДСТВ КОММУТАЦИИ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

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

системы и сети

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

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

/Таганрог ~ 1990

Работа выполнена ка кафедре МОП ЭВМ Таганрогского радиотехнического института им. В.й-Калмыкова

Научный руководитель — доктор технических наук, профессор Мелихов А.Н.

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

Ийколаев И.А. кандидат технических наук, доцент Божич В.И.

Ведущее предприятие - институт проблем моделирования в энергетике АН УССР, г.Киев.

Завита диссертации-состоится г.

в ____ часов на заседании специализированного совета Д 063.13.01

при Таганрогском радиотехническом институте им. В.Д.Калмыкова по

адресу: 347915, г. Таганрог, Некрасовский , 44, ауд. й-_____.

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

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

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

доцент В.А.Калачев

- з -

•'""i

,:,r.-,'¡ i ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

1Т.7ЦИЙ J

Актуальность работы- Ргг.'ение разнообразных задач реального гзремени эаэисит от иаличил развитого инструментария систем полунатурнаго ».«оделкрооания (ПИ) , от урозня развития рысскапрсиэводигелькых еычислительких систем.. Вопросам создания таких систем noca яшени Фундаментамьные иссла/;шзния, выпалнэннке В. С. Бурцевым, В. С.Васильевым, Е. О. Головкины:«, В.И.Глушковым, А.Г.Г,одсисяьгм,Э.В.Епреиноя1-м, И.В.Задыхайло, Л.В. Каляевым, Г.Косаревым, В. EI. Котозим, В.Г.Лазаревым, В.З^.Яипаовь'м, Г.И.Марчуком, Н.И.Мирснкооым, П.. Л_Посп^ лозым, М. В.Пранги'-зи/1'!, Г. Е-Пуховым, К. Г.СамоОаловым, В.Б.Смологшн, В.Г.Хоромавским и другими.

Для воспроисзедекия быстрспротекатчих процессов з реальном rmns времени (РВ) используются мнегопроисссорные вычислительные системы РВ с программируемой архитектурой (МВС РВ), концепция которых разработана учеными Таганрогского радиотехнического института под руководством члена—корреспондента ЛИ СССР А.В.Каляева. Современные научныг исследования, проводимые о ТРТИ, связаны с разработкой и созданием программного и аппаратного ойрспечсния 1"!ЗС РВ, о частности, с разработкой и созданием средстз эффективного планирования заданий на многомодульном пространстве ресурсов, разработкой и созданием гибких операционных систем (GC) реального времени, a также программируемых коммутирующих сред ÍKCP) для КВС PS. 5ф«ектизность МВС ГВ, D частности; ззоисит от Функциональных возможностей, степени откр.ытости средств описания и управления заданиями, от степени интегрирозанности этих средств в Функциональную оболочку ОС такой МВС РВ, от наличия гибких надежных программно—аппаратных средств межкомпонентной коммутации. В настоящая время проблема разработки таких средств для МВС является актуальной.

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

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

структуры проблемных задач, методов асинхронного, синхронного, сборочного и концептуального программирования; построения ойае; Формализованной иерархической модели Функциональных конпонгнт прс странства задач ПЯ, компонент ресурсного пространства КОС РВ; выбора базового подкласса коммутационных сетей <КС) и разработка двоичной графовой модели, обобщающей основные свойства этого подкласса КС; выбора способа представления структуры дво»1чной граОо-£ui"i модели КС; исследования свойств разомкнутого ориентироагнногс двоичного многоярусного графа (РОДМГ) при реализании на нам базовых перестановок формальными и экспериментальными методами; passpf батки методов и алгоритмов поиска произвольного маршрута на РОДМГ разработки на основе предложенной модели структурных принципе! построения коммутирующих устройств, истодоа их настройки, анализе их функционирования.

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

Научная новизна. В лр&цессе решения псстаал£н-ных задан были получены следующие основнъ:е научные результат«.

Выбран комплекс принципов построения языковых средств описания и управления заданиями для параллельных ВВС реалькзго ирслен: который был положен в основу разработанной версии пераллельмэге языка PPPL (Process Planning Parallel Language) для НЭП.РВ.

Введена и исследована двоичная графовая модель коммутационно;' среды МЗС РВ, топологическая структура когррой является в достаточной мере обобщением топологических структур условно, не^локиру-ii4nx многокаскадных КС. Разработаны алгоритмы построения такой модели. В результате проведенных исследований была теоретически доказана меблокируемость предложенной графовой модели при реализации на ней базовой совокупности перестановок. Разработаны алгоритмы реализации таких перестановок, отличающиеся регулярность» v простотой, реализацией указанных перестановок за один "проход" графа РОДМГ при параллельной передаче данных от каждого его входа к соответствующему выходу. Сформулированы оадачи разработки эффек тинным методов и алгоритмов поиска произвольных маршрутов в РОДМГ

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

-

ти?аа.PjwH, определонноН на N1 зхояах граоа Р0Д1Т, где» Ni^f , -

| Ргсрс&этам р*:л структур коммутационных сетей, г расы сп5»зей rfi.rrcyy.jx Msojiopc^rtj соответствуй-/»* подграфам РОДМГ. Такия сети пред-i»г.гядовкны для п см*»»-*:ямтельь-..»* систрах РО типа SIMD, SMIWD.

алгоритмы настройки этик сетей. Предложены структурные rp^i-^ivinu постро«?нмя децентрализованной коммутационной среды, лод-дгрзкиваи'.ггэй различные способы коммутации как при детерминирован-»¿ух, так и при недеторммнирсвднкых вычислениях на КВС РВ. При этом о к&чествр* метода иарирутиэации мспользозан метол в^-роптнсстной распределенной маршрутизации, адаптированный к предложенным структурам двоичных многоярусных графой, к требованиям реального времени. Нспо.гьсдеэан>?г» данного метода позволяет сократить время межмодульного оеЗнена, сбалансировать слгруску каналов связи коммутационной среды *з условиях недетерминированных вычислений.

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

Разработана версия параллельного языка PPPL для МВС РВ. Поед-лзггемый язык является перспективным средством описания и управления заданиями, их внутренними и внешними коммуникациями для МВС РЭ, в котором интегрированы основные достоинства много уровне гп объектно-ориентированного подхода к описанию структуры проблемны* задач, методов асинхронного и синхронного, сборочного и концептуального программирования.

Практическая ценность предложенной двоичной графовой модели состоит, например, в том, что ей мозгет быть поставлена в поогзетст— вие перспективная условно неблокирующая КС, отличающаяся высокой структурной надежностью, живучестью, имеющая логарифмические зависимости времени настройки маршрута, числа принадлежащие маршруту коммутационных элементов от числа входов/выходов в сети. При этом разработанный подкласс регулярных алгоритмов, реализующих на РОДМГ заданную совокупность базовых перестановок, может быть положен в основу алгоритмов реализации соответствующего подкласса примитивов языка PPPL, предназначенных, например, для выполнения операций сортировки множества объектов на мультиресурсах МВС РВ.

На основе предложенного двоичного многоярусного графа разработаны условно неблокирующие бинарные КС - УК!,УК2,УКЗ,УК4. Указанные КС обеспечивают также быструю и бесконфликтную передачу данных с монотонными адресами, представляющими собой монотонные двоичные последовательности сдвигов. Разработана неблокнруч&чД* Сингр-ная коммутирующая сеть - Ken.

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

тационнсяй сети состоит о том, что данная сеть скЗладаст поэыаенной стру!гтурмой киаучьсты», надеяноеть», обусловленными структурными характеристике«*! ее меиэлементных связей, внутренней структурой , ее узловых элекамтое, выбранным методом маршрутизации. Кроме тога -такай сеть поддерживает различные способы коммутации, что, в ко— ' нечном итого, гюзоолнег сбалансировать оагруску ее канл/.orj свази с условиях кедетермьмирсеакных вычислений. Экспериментально подтверждена целесообразность построения коммутационной срод»1 КЗС РВ на база многопроцессорных код/лей оперативной коммутации.

Полученные результаты применимы при создании многопроцессорных вычислительных систем реального иремски, м^'ин баз данных, а

/ "

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

Практическая реализация. Тематика исслэ-дований, выполненных в диссертационно;?': пабото, сиизана с »-¡аучными направлениями кафедры МОП ЭВМ ТРТИ, к« .¿дры ВТ ТРТИ, НКБ "Миус" при ТРТИ, НИИ КБС при ТРТИ, в частности, с такими темам-!, к-^к "Разработка и создание многопроцессорных вычислительных систем с программируемой архитектурой™, "Разработка и создание высокопроизводительного сыч^ длительного комплекса", "Разработка принципе1" построения и создачия епп^ратно—микропрограммных средств мнагопрацЕУСсорных к^ч-тл&ксно—моделирующих систем о состазе многомашинных модслируккцих комплексов

Осносныс результаты работы были внедрЕЬЫ в НКБ "Киус" при ТРТИ, где они были испс>_льс?аоа;*ы при разработке языковой оболочки описания и управления заданиями в СУПЕРАКСЕ.ЛЕРАТОРЕ для персональных ЭСМ, совместимых с IBM PC ( промежуточный отчет по НИ? N ГР 01.90.0 012919); при разработке сетей сортирозки данных в «¡'.айне баз данных (промежуточной отчет по НИР N ГР 01.£9.О 077937); при разработке модуля оперативной коммутации системы межмодульного обмена многопроцессорных комплексна—моделирующих систем РЗ, при проведении макетировании данного модуля( итоговый отчет по НИР N ГР 01.G3.0 009463, Инп.И 02.66.0 03S6S0 >. Суммарный ожидаемой экономический эффект от внедрения результатов работы составляет 47 тыс. 585 руб., что подтверждено соответствующим.актом о внедрении. На з а и и т у выносятся следующие положения:

- комплекс принципе») построения языка описания и управления отданиями для КЗС Р9;

- структура двоичного многоярусного граоа связей коммутационной сети МВС РВ;

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

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

- структуры и методы настройки бинарных коммутационных сетей;

- структура коммутационной сети с децентрализованным управлением, поддеркива»2!ей различные способы коммутации как при детерминированных, так и при недетерминированных вычислениях на КОС Р8,

Апробация работы. Основное содержание работы докладывалось и осуждалось на 1—м Всесоюзном совещании по автоматизированному проектировании программного обеспечения систем управления движущимися объектами) Харьков, ХАИ, их>нь, 1987г.); на Всесоюзном научно-техническом семинаре.кол. учен, и спец. "Информатика и вычислительная техника"( Москва, апрель, 1986 г.); на областной научно—технической конференции мол. учен, и спец. (Таганрог, ТРТИ, сентябрь 198А г.); на заседании научно-технического семинара "Моде-лиругоцме и управлитчие многопроцессорные вычислительные системы" в рамках регионального семинара "Многопроцессорные вычислительные системы" (Таганрог, |-|!<Б "Миус"^ июнь, 1985 г.).

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

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка сокращений, использованных в тексте, списка литературы и приложения. Работа содержит 277 страниц машинописного текста, включая 60 рисунков, 5 таблиц, а такие список литературы из 163 наименований. В приложении приведен пример описания типовой задачи средствами разрйботар^вго автором яггыка РРРЦ.

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

В первом разделе покарано, что ресурсное пространство (РЕСП) МБС РВ достаточно для решения на нем требуемо^ дачи ПМ (совокупности задач ПМ) с заданным качеством, если лшбо^ му А—объекту модельного пространства <К0ДП) задачи может быть поставлен в соответствие некоторый ЦВ-объект РЕСП МРП т^кой, что для данной пары объектов выполняется утверждение 1.

Утверждение» 1. Отображение А—объекта (1 Записи

зида ( 1.1)..(1.4 )) иерархии абстракций задачи ПМ на ннкотсрое югическое пространство ресурсов, которому сопоставлен ^К-ойийлт

- & -

q, (г) соответствующей структуры, обозначаемое q(h) q (z), яз-

V {*}, 1г

ляэтся качественным, если значение функционала структурно-Функциональной деформации удовлетворяет заданным критериям качества <К>( Под функционалом структурно—функциональной деформации (6Д> будем понимать некоторый Функционал вида

FDr = < optimum tFDijJJr,

{<h ^ где r- тип сопоставляемых параметров объектов, поименованных

в утверждении 1, FDij- локальный ОД, вычисляемый по отклонению значения соответствующего J-го параметра LR-объекта от сопостав— пенного ему значения i—го параметра данного А-ойьекта иерархии представления задачи ПМ. В простейшем случае, когда в качества критериев оптимизации <К>г используется минимаксный критерий, то оуикнионал г?римима(?т вил: FDг = { wiinmax€FDij> >г-

Сфопмулированэ проблема минимизации искажений, возникающих в процксгсс вшюлиьниа итерационного отображения структуры модельного пространства на пространство ресурсов МЗС РВ. При этом в подразделе 1.1 показано, что при определенных условиях проблема уменьшения искажений мояет быть сведена к проблеме взаимной лдал- ' тации модельного и ресурсного пространств на основе их автоматической или автоматизированной структурной перестраиеаемости по за-мдме?е заданным критериям. В рамках решения проблемы взаимной адаптации "сверху" сфсрмулировама прсблема обоснованного выбора принципов построения языка описания и управления заданиями для ИВС РВ. 3 р«мках решения проблемы взаимной структурной адаптации данных пространств "снизу" сформулирована задача разработки структуры адйптиенснл коммутационной среды МВС РЗ, удовлетворяющей требоеа— ь; 1 поддержки межпроцессных взаимодействий в реальном орем^ни.

Для >правления процессом полунатурного моделирования на отведенном пространстве ресурсов и описания структуры МОДП, его компонент необходим язык описания и управления заданиями <ЯОУЗI, удоз— летворяк^ип таким показателям, как понятность и надежность, гибкость, открытость, простота использования его средств, производительность создания заданий, обладающих сложной информационно-логической структурой; адаптируемость последних к изменению условий их реализации, в т.ч. , к изменению конфигурации ресурсного пространства вычислительной системы, к изменение целевой функции решаемой на ЮС задачи, состава алгоритмов со реализации. Крона того, средства ЯОУЗ должны предоставлять полыюзател» ооэможность включения а состав описания структуры конструируемого НОДП ране г? созданных ¿«еиэ^ломма-ориентироааннах моделей, возможность задания - олерацмшСгЮЙ системе ИВС правил ррг«¡ниэации взаимодействий комле,-

нт НОДП в процессе ПИ а темпе реального времени.

Качественный анализ показывает, что достаточно противоречивый мплэкс требований, предъявляемых к свойствам ЯЯУЗ, можно обеспе-1ть, если о основу процесса проектирования таких языковых средств 1лаяить следующую совокупность принципов! объектная ориентация эдств языковой оболочки; интеграция средств и методов концепту— ibHoro и сборочного программирования; модульность и кногоуровне-)сть языковых средств; интеграция средств и методов синхронного и :инхронного программирования; проблемная ориентация средств яоы-)СОй оболочки; ' аппаратизация наиболее используемых языковых >едств. Данные принципы были положены в основу разработанной вер-1и параллельного языка описания и управления заданиями — PPPL ( -ocess Planning Parallel Language)— для ИБС РВ. D качестве форельного базиса ¡языка PPPL выбраны формализмы логических языков •гацигикаций, основанные на исчислении предикатоп первого и зторо-з порядков. При этом основными конструкциями языка рвляютсп иден-•и&икатор объекта языка (атом) , предикатная функция ( Оункция-про-=дура ), формула, высказывание, предложение логического"вывода, омуль. Определены следующие разновидности модуля! атомарный мо— уль (модуль—задач* (КМ)) и састаснаП нпдульС модуль—команда (КМ), модуль-данные (ресурс) (МД) ) . В частности, средства ИМ позволяют адать единый интерфейс для различных прикладных пакетов прпграм-ных модулей, тексты которых описаны необязательно на одном и тон е языке программирования. Требуемая открытость, используемость и адежность введенных ппнятий обеспечивается введением в состав редств яэика различных ортогональных по Своим свойствен конструк— ороз. К последним следует отнести конструкторы логического и ре-урсивного вывода, командной переменной и переменной времени- Опи— амие БНО сведенных конструкций языка приведено о токсте подраезде— а 1.2 диссертационной работы, а также, например, в /1/. Язык PFPL редоставляет пользователя средства описания информационно—логиче-кой структуры задачи ПМ, их совокупностей с учетом управляющих вязей мзжду их компонентами; средства описания целевых и спуско— ■ых Функций компонент задач, их параметров; средства привязки про— Еессоз вычисления их компонент к общей временной диаграмме; средства описания задействованных ресурсов, правил их использования; :редства описания типа доступа к рвсурсам; средства описания направления потоков данных. Так лкбые ИМ, КМ некоторого задания по-редством логического высказывания могут быть постоянно, либо Dpe-(енно связаны с требуемыми ресурсами ИБС, объявленными предвари— ельно в тексте данного задания описателен памяти и/или описанные

- {О -

посредством СЩ. Доступ параллельных процгссоз к связанны»! с ними ресурсам шляется лиЗо монопольным, либо разделяемым. При необходимости с целью защиты разделяемого ресурса от несанкционированного доступа пользователь монет воспользоваться лябым из изоестных программно—аппаратных механизмов защиты ( "семафор", "монитор", "рандеву"), описав, например, в определителе такого ресурса соответствующие правила доступа к нему. Б качестве средства описания этих правил следует использовать введенный в языке конструктор логического вывода. Для описания однотипных параллельных процессов, выполняемых над одн шныж структурами данных введено понятие массовая операция. обенностям языка РРРЬ такке следует отнести

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

Во втором разделе в результате анализа топологических структур КСР многопроцессорных вычислительных систем большой размерности, объединяющих тысячу и более процессоров, был выбран подкласс условно неблокирующих многокаскадных комму.тиру-»¿ицих сетей (КС) , компоненты которого обладают наиболее близкими к требуемым свойствами. Введена и, исследована двоичная грасовая модель коммутационной среды МВС РВ, топологическая структура которой является в достаточной мерс обобщением топологических структур условно неблокирущих многокаскадных КС. Одной из разновидностей предложенной двоичной графовой модели является двоичный многоярусный граф (ДМГ) , содержащий N (1_+1> вершин, 1_=1_од М, топологическая структура которого удовлетворяет, определении 2.0.

Определение 2.0. Двоичным многоярусным графом называется такой граф во(V, и), нёсодержащий петель, в котором каждый 3-й элемент (_£(.— 1)-го яруса связан ребрами с К элементами

К ■ 11-го яруса ЛИ и грава Б0 так, что при I- четном и К=5

' ¡..и,

выполняется равенство р =-2 ;-2 ,0,+2 ,+2 , 'а при I. нечетном справедливы следующие высказывания (^К- ?= )( К=5 и ¡"——2 .—2 ,

и (^ =/<у> (К=3 и у =0,-2^ ) , где /¿=1,1-

при общем количестве ярусов, равном (Ц+1) ,^ = (_.— ближай-

шее большее ивлое.

Сформулированы такие основные свойства разомкнутого ориенти-

-а-

апнмсга гра£а Л.'Т С р'.с. 1. ), клч гкзлнодоступнссть», симнэтрич— сть и рс-'гулкркссть структуры свяэг?й, псстоякстоо мсщности про-сольноМ цепочки ссрсмн, ограниченность длим« пути, а такие соей-оа го/тизери,':нтссти еднига йЗр а структуры кодчт, двоичной здро-цки «дискчкый код с2Ср сэдногначмо определяет путь <р-^) в РОДМГ,

'' /1 I-

:<? ¿Зр-р—2 » ^«¿С^®» 1->> > свойства копирозания и множе— теннис™ иарягрутв* .-::^птг*рсго пути айда <р —>а ) п услопиях от— тстш-ы в граев прсве»дсн:-(ых путей.

Прпзодркч теоретические исследования своГ*сто и структурных эа-В результата прополг^нныи иссло-дозаний доказа— ), что ргссмттрилаеме.к кодаль нойлскируена при виполнекии рпд-т структур данных, таких клк симметричные перестановки: >лняя и обратная т¿¡сапкл, персста юака типа "бабочка", полная ин-?рснает перэст^-ко^ка; а т£кз*!э при кыгюлькгкии ряда раерпдно-реэер-гамы.-: ¡тг?рсстаиоас7к, перестс.1-*-ток со емщонием, с замещением, что, целом, и^лпется существенным для МПС РВ, рега^ющих задачи ПМ. Раз— ':":)т.'м;> алгоритмы реализации тлких п^р^стансоак, отличающиеся ре-'лкрнэстил и простотсй, р&а."изаци-"?й указанных перестановок за :нн "лрахэд" графа при параллельной передаче длмн-'Х от каждого ■о входа I; соотя&тстоу^этму его выходу. Данные алгоритмы могут

Структура ргночкгнутогс дззичмого много гнусно го графа

ярус О

ярус!

ярус 5

Рис. {.

Сыть полах.сны в основу алгоритме« реализации подкласс:а примитив (предикатных функций) ЯОУЗ, пр од назначенных для сыгюлчсьия, »-пример, операций сортирозки множества объектов н«1 мультиресурс МВС РВ посредством ео коммутационной среди. включение таких апг ратна поддержанных средсто о состав базовых примитииоз пс

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

Сформулированы задача разработки эффективных методов и алг ритмов поиска произвольных маршрутов в РСДМГ, а такие задача г иска доказательства праосмочностй существование основных полай ний выдвинутой гипотезы о неблокируемости на класса <№) п»гр становок соединительной сети, структура которой интерпретирез* указанным графом. ,

В третьем разделе на основе анализа классик ских способов представления структуры графов о памяти ЭВМ, с у«-том свойств РОДНГ разработан достаточно экономичный с точки зр ния затрат памяти способ хранения виртуальной усеченой структ^ графа с использованием базоиых векторных маршрутных диагр« (БВМЛ) варьируемой размерности. В общем случае, оценка затрат г ммти для предложенного способа равна ОС5^^ ). В качестве мето/ поиска произвольного маршрута в графе РОДМГ, задаваемом БВГ предложен метод наложения векторных маршрутных диаграмм, при э~ рассмотрены варианты его графической и табличной интерпретац» Идея поиска произвольного маршрута этим методам базируется на * пользовании основных положений леммы 3.1.

Л £ м м а 3.1. Если в графе 3 реализован путь (р1~>^1), кс рому соответствует маршрутный код 21: г' г^ • - -. г^ , то мекото[

путь ^p2—^q2) можно реализовать в графе 6 с маршрутным кодом )

2 2 2 2 Г. ... таким , что

^.-^-г/**/' , .< 3.1 >

где --- Ар = р1-р2, не равны О; г 2 , ,0,21

г1'1 з. 1 = Г71.

Следствие 3.1. Если У(-=0 , то и 1—ом ярусе в верш: при реализации на графе Е пути с кодом 22 существует конфл! с соответствующим маршрутом, код которого равен. 25, где индекс 8 общем случае может Сыть определен = p^ + , при

|>ри 3 > И, л = - (Ч, а при з О, то j = л !- N .

Пусть для любого пути вида <р|<->я(4> синтезирована совершен Й«г&Ториая маршрутнея диаграмм; 'СВМЯ> , содермащая коды всех м

рутоо, которыэ могут быть потенциально проложены в грасе РОДМГ между его р^ входом и q^ выходом. Рассмотрим краткое содэряание метода- В таблично заданной СВМД^ нового пути >qfc> выбирается

первая строка й для ках^дого проведенного маршрута из таблицы СМДПП вычисляется Vj по <?ормуле (3.1). Если при таких промежуточных вычислениях котя бы один из равен О, то рассматриваемая строка вычеркивается из таблицы СВМД^ . Затем из данной СВКД^ вы-езирается следу^ал за вычеркнутой строка, для которой повторяете* сесь цикл поиска конфликта. Описанные операции повторяются для исох остальных строк СВМД^ . Таким образом, в СВМД^ будут найдены вез свободнее о графе Р0ДГ1Г маршруты нового пути. В том случае, когда множество таких марцзрутез о СВМД^ равно О, то новый путь проложить невозможно. Если шэ множество непустое и количество его компонент больше единицы, то необходимо задать критерии выбора свободного маршрута из данного множества. Следует отметить, что если критерии поиска заранее. неопределены, то выбирается первый свободный маршрут и списке СВМД^. Маршрутный код выбранного маршрута пути Ср^—>q,.J кайлен.

На основе предложенного табличного метода наложения векторных мгрыруткых диаграмм разработан квазистатический итерационный алгоритм приведения заданной последовательности едзигев к квазиоптч-мгльной, определенней на N1 входах графа РОДМГ, где Niic N. Данный алгоритм был апробирован о итерационном и безитерационном режимах с использованием разработанного азтором пакета прикладных программ (ППП) "Я!—Net"- При -этом ППП "Bi-Net" предназначен лля генерации в памяти инструментальной 3SM предложенных в подразделе 2.2 двоичных многоярусных графовых моделей при различных N, кратных 2 и больших 4, для исследования и иллюстрации свойств грвфа а также-для проведения статистических исследований поряди неблокируемости соединительной сети, интеопретируемей РОДМГ. Программы пг.кета написаны на ЯВУ PASCAL в ОС RAFOS. При помощи данного ППП было проведено исследование кеблокируемости РОДМГ методом статистических испытаний для 16- Состаз смеси реализуемы:; пе-

рестановок был выбран таким образом, чтобы пути вида ( pi->qi )к, соответствующие i—м компонентам к—й последовательности CdSpJk, i=l9N9 не имели общих р, q и не подпадали под определения 2.1 ..2.14. Результаты проведенного эксперимента подтверждают правомочность основных положений выдвинутой гипотесы "о неблокируемости соединительного пути" при N, равном О, 16. При этом правомочно предположение, что для любых двух путей <pi->qi>, (pj->qj>, принадлежащих произвольной idSp> 9 заданной на N1 входах графа *J, где

N1^ 14, ее каазноптимальная реализация йудэт найдена оa конечное число проходов итерационного киагистатического алгиругтм&. В таком случае? пев N1 путей реализ атся по выбранным ьгр^рутам параллельно и бесконфликтно за IKLog^N) шагов передачи единицы информации че— pea соединительную сеть, интерпретированную грезой РОДНГ.

■В четвертом разделе Hdi баоэ дгеичных графовых моделей предложен ряд структур КС, одни из которых, например, У К15 УК2 , У КЗ , У К4 , по своим функциональным возможностям мзгут ёыть отнесены к классу условно нз£лок»-1руккад<1х многокаскадных сетей разовой коммутации <МКС РЮ, другие, например, Ксп /2/ — к классу неблокирующих МКС РК- Предложены алгоритмы настройки этих сетей. При этом длительность настройки предложенных КС ограничена верхней оценкой ( OÍLog^N) >, что лучше аналогичной оценки, например, для такой сети как PARM.

Условно неблокирующие банерные КС —УК1 ,УК2,УКЗ,УК4 отличают ел полнодоступностыо о условиях разовой коммутации, регулярностью внутренних ноиэлементных связей, множественность» .прокладываемых n/тей, свойством циклического сдаига передаваемой посредстооы КС информации, ограниченностью длины прокладываемого маршрута ( UILot^N) >, свойством копирования поступающих на входы сетей сигналов (кроме УК1), свойством двоичной адресации (двоичное значение сдвига dSp определяет виртуальный адрес абонента—приемника и кратчайший путь в сети между ее р—м источником и *q—м приемником ), свойством совмещения процесса параллельной настройки одних маршрутов с процессом параллельной( передачи информации по другим ранее проложенным маршрутам. Указанные КС обеспечизеют такяе быструю и бесконфликтную передачу данных с монотонными адресами, представляющими собой монотонные двоичные последовательности сдвигов. Количество коммутационных элементов (КЭ> в каждом из таких устройств ограничено величиной (N Log^N)/2,3/. Предложенные КС предназначены для работы с МВС РВ типа SIND, SMIND. Данные КС в достаточной степени технологичны. Так, предложенные КС,могут йыть разработаны в виде набора специализированных базовых кристаллов. При этом на каждом базовом кристалле такой матрицы коммутации размещается ряд КЭ ее j-ro столбца (СБИС2). Таким образом, если на кристалле размещен столбец матрицы коммутации,, состоящий из L элементов, то N-входовая КС может быть построена с использованием N кристаллов типа СБИС2, где N= 2¿ .

В подразделе 4.2 сформулированы структурные принципы построения децентрализованной коммутационной среды (КСР), поддерживающей раолич^ьк> способы коммутации как .при детерминированных, так

при недетерминированных вычислениях на МВС РВ. 8 основу сети такой КСР положен разработанный во второй главе граф ДМГ. зоышение эффективности использования каналов связи в КСР в уела— 1ях децентрализации управления сетью связи достигается за счет «теллекту ализации узловых элементов <Ю) сети , а также за счет довременного использования в КС нескольких способов коммутации, ¡?тода вероятностной распределенной маршрутизации. При этой метод »роятностной распределенной маршрутизации адаптирован к предложным структурам двоичных многоярусных графов, В качестве интел— актуального УЭ коммутационной среды МВС предложено использовать лльтипроцессорный модуль оперативной коммутации с программируемой зхитектурой. На такой модуль в процессе транзита через него инфор-щии возлагаются как транспортные (сетевые), так и функции, свя-*нные с промежуточной обработкой этой информации- Наличие е КС 1ких ресурсов позволяет коммутационной подсистеме МВС организо-ггь, например, конвейерную промежуточную обработку транзитных со— эщеннй. Целесообразность и эффективность применения УЭ указанной груктури подтверждена результатами макетирования, проведенного в *мках хоздоговорной НгЛР.

ЗАКЛЮЧЕНИЕ

Основное результаты диссертационной работы заключаются в еле— 'киуем. ...

1• На основе выбранного комплекса принципов построения языке— IX средств описания и управления заданиями для параллельных эы— 1слительных системах реального времени разработана оригинальная »рсия параллельного языка РРР1_ для МВС РВ.

2. Предложена двоичная графовая модель' коммутационной среды 1С РВ, топологическая структура которой является в достаточной ►ре обобщением топологических структур условно неблокирующих мно-жаскадных КС. Сформулированы основные свойства та>гой графовой »дели, выявлены основные закономерности реализации базовой сс— жупноСти перестановок на разомкнутом ориентированном двоичном югоярусном графе, проведены их теоретические исследования. & ре-льтате, доказана неблскируемость предложенной графовой модели и выполнении указанны* перестановок. Разработаны алгоритмы ре-.иЗации базовой совокупности перестановок структур дамныу на ДМГ, отличающиеся регулярностью и простотой, реализацией укаэзн-х перестановок за один "проход" графа при параллельной передаче нных От каждого его входа к соответствующему его выходу.

- lb -

Экспериментальным путем получено для N=* 8, 16 доказательств правомочности основных положений выдвинутой гипотезы о неблскнру

которой интерпретирована РОДМГ.

3. Разработан метод наложения векторных маршрутных диаграмм варианты его графической и табличной интерпретации для поиска пр иэвольного маршрута о графе РОДМГ. Предложен квазистатический ит рационный алгоритм приведения заданной последовательности сдвиго к квазиоптимальной, определенной на N1 входах графа РОДМГ, гд N1^ N, N= 2L -

4. На основе предложенного двоичного многоярусного графа раз работаны условно неблокирующие бинарные КС — УК1,УК2,УКЗ,УК4t Структура УК1 защищена АС N 1485261 " Устройство коммутации " Разработана бинарная коммутационная сеть, содержащая N (N—1) Ю обладающая перечисленными выше свойствами,, отличающаяся н&блокир вмостью q условиях несовпадения значений адресов абонентов—приемников ( личный вклад автора в разработку данной КС — 507, ) /2/.

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

трО£пваниям реального времени. Использование данного метода пс GOли/»о сократить время межмодульного обмена, сбалансировать зг грузку каналов связи КСР. Экспериментально подтверждена целесоо* разность построения коммутационной среды МВС РВ на базе многопрс цессорныи модулей оперативной коммутации.

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

1. П^язченко А.О. Параллельный язык описания и управления задан рми. Метод, рекомендации для етуд. вуз. по спец. "Бычислтельнс *еггника". -.flbRce: ИППМИМ, 1989.- 85 с. : ил. ( НТЦ по ВВС "Интеграл

2. Пьявч£н»еО А.О., Ромм Я.Е. 0 коммутационной сети для межпроцЕ ССрногс Обмена и ссртировки //Автоматика и вычислительная технии -Рига, 1990. - N1.

3. ft. £.1435261 СССР, 4G06F15/ 16 , Н04 . 09/00. Устройство хоммутац^ ' А-0.Пьрвч«нко (СССР).-N.4314563/24-24; Заязл. 0в.10. // Открь«ти$>л Ид&бретения.- Г1. - N 21. -С. 236-237

емости на классе С N!> перестановок соединительной сети, структур

СП ТРТИ 3Тлр 00 >990 г.