Введение к работе
.'ОЛ і
iT,?U.V,fl І
Актуальность работы. Рилрниэ разнообразных задач реального зремени зависит от наличия развитого инструментария систем полунатурного «.«оделкрования <ГЛІ> , от урозня развития рысскопрсизоодигельных еычислительких сметем.. Вопросам создания таких систем поса яшени фундаментамьные исслядоязния, выполненные В.С.Бурцевым, В.В.Васильевым, G.О.Головкиным, В.П.Глушковым, А.Г.Г.одс1-!Сяым,Э.В.Ег5реиноз1-м, И.В.Задыхайло, Л.В. Каляевым, Ю.Г.Косаревым, В.Е.Котозин, В.Г.Лазаревым, B.B.JWiaccb'M, Г. И.Марчуком, Н.Н.Мирснкооым, Д.А.Поспелозым, И.В.Прангип"ЗИли, Г.Е.Пуховым, К.Г.СамоОаловым, В.Б.Смологшн, В.Г.Хороыавским и другими.
Для воспроиезедекия быстрспротекатуих процессов з реальном rmiis времени (РВ) используются многопроцессорные вычислительные системы РВ с программируемой архитектурой (МВС РВ), концепция которых разработана учеными Таганрогского радиотехнического института под руководством члена—корреспондента АН СССР А.В.Каляева. Современные наумныг исследования, проводимые в ТРТИ, связаны с разработкой и созданием программного и аппаратного ойрспїїчєния 1"!ЗС РВ, о частности, с разработкой и созданием средств эффективного плзнироогния заданий на многомодульном пространстве ресурсов, разработкой и созданием гибких операционных систем (ОС) реального премени, а также программируемых коммутирующих сред (КСР) для МВС РВ. ^ФСектизность МЗС ГВ, о частности; зависит от Функциональных возможностей, степени откр.ытости средств описания и управления заданиями, от степени интегрирозанности этих средств в Функциональную оболочку ОС такой МВС РВ, от наличия гибких надежных программно—аппаратных средств межкомпонентной коммутации. В нсстопщае время проблема разработки таких средств для МВС является актуальной.
Цель работы. Выбор принципов построения языковых средств описания и управления поведением компонент модельного пространства задач полунатурного моделирования, исследование свойств и основных закономерностей граоооой модели коммутационной среды, разработка методов и алгоритмов поиска произвольного маршрута на двоичной графовой модели коммутационной среды, разработка структуры адаптивной КСР^ удовлетворяющей требованиям поддержки межпроцессных взаимодействий в реальном времени для МБС большой размерности.
Цель диссертационной работы достигается путем использования общего многоуреэвнего объектно-ориентированного подхода к описание
структуры проблемных задач, методов асинхронного, синхронного, сборочного и концептуального программирования; построения об^еі Формализованной иерархической модели Функциональных конпомгнт прс странства задач ПЯ, компонент ресурсного пространства КОС РВ; выбора базового подкласса коммутационных сетей <КС) и разработка двоичной графовой модели, обобщающей основну? свойства этого подкласса КС; выбора способа представления структуры двоичной граОо-iurt модели КС; исследования свойств разомкнутого орнентироагнногс двоичного многоярусного графа (РОДПГ) при реализации на нам базовых перестановок формальными и экспериментальными методами; рагрь батки методоз и алгоритмов поиска произвольного маршрута ма РОДМГ разработки на основе предложенной модели структурных принципа! построения коммутирукцих устройств, нетидоз их настройки, анализе их Функционирования.
МеТОДЫ ИСС.ПЄДОВгіНИЙ. йЛЯ ДОСТИ2ЄНИЯ постйа-
ленной цели в работе использовались методы теории иерархически) вычислительных систем, теории'графов, теории множеств, теории «ас сового обслуживания, аналитического моделирования, математическа-г о. программирования.
Научная новизна. В процессе решения п&стаалн-ных задан были получены следующие основній научные результати.
Выбран комплекс принципов построения язшхшых средств описания и управления заданиями для параллельных ВВС реалькзго времен* который был положен в основу разработанной версии гшраллельмэге языка PPPL (Process Planning Parallel Language) для МЗС. РВ.
Бвеа&на и исследована двоичная графовая модель кеммутационкс? среды МЗС РВ, топологическая структура котррой является в достаточной мере обобщением топологических структур условно, неблокиру-!і4их многокаскадных КС» Разработаны алгоритмы построения такой модели. В результате проведенный исследований была теоретически доказана меблокируемость предложенной графовой модели при реализации на ней базовой совокупности перестановок. Разработаны алгоритмы реализации таких перестановок, отличающиеся регулярность» v простотой, реализацией указанных перестановок за один "проходи графа РОДМГ при параллельной передаче данных от каждого его входа к соответствующему выходу. Сформулированы оадачи разработки эффек тинным методов и алгоритмов поиска произвольных маршрутов в РОДМГ
Разработан метод наложения векторных маршрутных диаграмм, вар анты его графической и табличной интерпетации для поиска проиэоль ного маршрута в РОДМГ. Предложен квазистатический итерационный , алгоритм приведения заданной последовательности сдвигов к квазиоп
- у -
ти?4СГ,л>4сГ1, определенной на N1 яхолах граОа РОДЇ'Г, где* Ni^f ,N= 2*.
I Ргсрсйэтам р*:л структур коммутационных сетей, гре&ы cBs-asn *о-гс>;у.іх МохорСч-г^ ссотв»тстау>э=;^м подграфам РШМГ. Такутя сети пред-і;г.:>«а»*ї»я»і л/?я раэтм їз смч»^с.гмтелъ*-1!х систрах ГО типа SIMB, SMIMD. Гїрсдгсп'?ічм .алгоритмы настройки эти;: сетей. Предложены структурное гр^ї-ї-іили постро*?ния децентрализованной коммутационное среды, под-дгркиоак^эй различные способы коммутации как при детерминированных, так и при нодеторминиревлнкыи сыч 1СЯЄНИЯЧ на КВС РВ. При этом в качества кетода маршрутизации мспольоозен метод п<.-раятнс-~тной распределенной м«тршрутизацми, адаптированный к предложенным структурам двоичных многоярусных графой, к требованиям реального сре-К5ии. 1'Сспо.пьз-сэаниг* данного метода позволяет сократить вргмя межмодульного обмена, сбалансировать загрузку каналов связи коммутационной среды в услоъмях недетерминированных вычислений.
Практическая ценность работы состоит в следующем.
Разработана версия параллельного языка PPPL для МВС РВ. Гзед-лзг-^екый язык является перспективным средством описания и управления заданиями, их внутренними и внешними коммуникациями для МВС PS1 в котором интегрированы осиозные достоинства мно г сур ос нот объектно-ориентированного подхода к описанию структуры проблемных задач, методов асинхронного и синхронного, сборочного и концептуального программирования.
Лрактическая ценность предложенной двоичной графовой модели состоит, например, в том, что ей может быть поставлена в соогзетст— виє перспективная условно неблокирующая КС, отличающаяся высокой структурной надежностью, живучестью, имеющая логарифмические зависимости времени настройки маршрута, числа принадлежащих маршруту коммутационных элементов от числа входов/выходов в сети. При этом разработанный подкласс регулярных алгоритмов, реализующих на РОДМГ заданную ссвскупность базовых перестановок, может быть положен в оснозу алгоритмов реализации соответствующего подкласса примитивов языка PPPL, предназначенных, например, для выполнения операций сертировки множества объектов на мультиресурсах МВС РВ.
На основе предложенного двоичного многоярусного графа разработаны условно неблокирующие бинарные КС - УК1 ,УК2,УКЗ,У'К4. Указанные КС обеспечивают также быструю и бесконфликтную передачу данных с монотонными адресами, представляющими собой монотонные двоичные последовательности сдвигов. Разработка нзблокнруФ-чДЯ Сян&р-ная коммутирующая сеть - Ксп.
Практическая ценность предложенной децентрализованной кет яду-
тационнсяй сети состоит а том, что данная сеть скЗладаст пооыаскмой струїгтурной киаучьстьи, надєямоеть», обусловленными структурными характеристикаки ее меиэлем*?ктных связей, внутренней структурой , ее узлэзых элекамтсе, выбранным методы* маршрутизации. Кроме того, такай сеть поддерживает различные способы коммутации, что, в ко—' нечнзм итоге, гюаооляег сбалансировать оагруску ее каналов связи с условиях кедетермьмирсвакных вычислений. Экспериментально подтверждена целесообразность построения коммутационной среда КЗС РВ на база многопроцессорных мод/лей оперативной коммутации.
Полученные результаты применимы при создании многопроцессорных вычислительных систем реального врємски, Мй^ин баз данных, а также распределенных вычислительных систем и сетей.
Практическая реализация. Тематика исследований, выполненных в диссертационное: пабото, езязана с ьиучными направлениями кафедры МОП ЭВМ ТРТИ, к- .«»дры ВТ ТРТИ, НКБ "Миус" при ТРТИ, НИИ КБС при ТРТИ, в частности, с такими тснаии, кйн "Разработка и создание многопроцессорных вычислительных систем с программируемой архитектурой", "Разработка и создание высокопроизводительного сичі- -лительнзго комплекса", "Разработка принципі. -построения и сазда чия апп-фатна—микропрограммных средств о6»\н--. многопроцессорных Кіч*лл;?ксно—моделирующих систем о составе многомашинных моделируккцих комплексов".
Основные результаты работы были внедрены в НКБ "гіиус" при ТРТИ, где они были испольеова;4ы при разработке языковой оболочки описания и управления заданиями в СУПЕРАКСЕ.ЛЕРАТОРЕ для персональных ЭСМ, совместимых с IBM PC ( промежуточный отчет по НИ? U ГР 01.90.0 012919); при разработке сетей сортирозки данных в мааіи-не баз данных (промежуточной отчет по НИР N ГР 01.Є9.0 077937); при разработке модуля оперативной коммутации системы межмодульного обмена многопроцессорных комплексна—моделирующих систем РЗ, при проседеким макетирования данного модуля( итоговый отчет по №Р N ГР 01.G3.0 009463, Инп.И 02.66.0 03S6&0 ). Суммарный ожидаемой экономический эффект от внєдрєі-гия результатов работы составляет 47 тыс. 585 руб., что подтверждено соответствующим.актом о внедрении.
На запиту выносятся следующие положения:
комплекс принципов построения языка описания и управления изданиями для МЗС Р9;
структура двоичного многоярусного граоа связей коммутационной сети МВС РВ;
алгоритмы реаг»чзьции на двоичном многоярусном граве базовых перестановок ламных;
методы и алгоритмы поиска произвольного пути в разомкнутом ориентированном двоичном многоярусной граоеі метод наложения векторных марирутных диаграмм (графическая и табличная интерпретации метода), итерационный кэазистатический алгоритм поиска;
структуры и методы настройки бинарных коммутационных сетей;
структура коммутационной сети с децентрализованным управлением, поАдеркмоа»8!ей различные способы коммутации как при детерминированных, так и при недетерминированных вычислениях на гШС Р8,
Апробация работы. Основное содержание работы докладывалось и обсуждалось ия 1-м Всесоюзном совещании по автоматизированному проектировании программного обеспечения систем управления движущимися объектами) Харьков, ХАИ, их>нь, 19В7.-.); на Всесоюзном научно-техническом семинаре.кол. учен, и спец. "Информатика и вычислительная техника"( Москва, апрель, 1986 г.); на областной научно—технической конференции мол. учен, и спец. «Таганрог, ТРТИ, сентябрь 198& г.); на заседании научнотехнического семинара "Моде-лируюгцие и управлявшие многопроцессорные вычислительные системы" в рамках регионального семинара "Многопроцессорные вычислительные системы" (Таганрог, \-$<Б "Миус"? ивнь, 1985 г.).
Публикации. Основные результаты диссертации отражены в 14 печатных работах, из которых 5 опубликованы автором самостоятельно. Получено авторское свидетельство на изобретение.
Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка сокращений, использованных в тексте, списка литературы и приложения. Работа содержит 277 страниц машинописного текста, включая 60 рисунков, 5 таблиц, а такие список литературы из 1АЗ наименований. В приложении приведен пример описания типовой задачи средствами разрйботарнвго автором яггыка PPPL.