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

Введение к работе

Актуальность темы. Проблема коммутации в вычислительных системах вообще и в вычислительных системах с про -граммируемой архите турой (МВС ПА), в частности, является акту -альной, несмотря на то, что к настоящему времени выполнено до -вольно много теоретических исследований и практических разрабо --ток, касающихся ее решения. Это обусловлено тем, что на коммутационную систему (КС) МВС ПА возлагается не просто задача образования требуемых связей, которая является достаточно слокяоіі сам:;, по себе ухе при относительно небольшом числе процессоров. КС ИВС ПА должны "уметь" не только автономно настраиваться па нужные соединения, но также и перестраиваться на новые соединения, восстанавливая разорванные неисправностями сгяги и поддергивая,тем самнм, определенный уровень живучести связей, 'даге говоря, КС МВС ПА должны самостоятельно репать проблему управления процес -сом установления и поддержания функционирования соединений. Из сказанного видно, что при создании КС МВС ?'.\-с$фоз:ї'?локет дать только комплексный подход к разработке сгрумгтри КС и методов управления ими, к выбору сложности КС/к о6єсїїс:?ііпю их живучести. Еще.одной важной компонентой, связанной с'решением этой проблемы, является введение в КС элементов интеллектуализации, в частности; определение трейоьаний к языку управления ко"!утацяеЗ высокого и

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

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

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

Известные КС не обладают совокупностью всех перечисленных признаков.

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

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

Целями работы являются:

- разработка новых принципов построения и организагии функ
ционирования КС, ориентированных на использование в МВС ПА;

- анализ эффективности реализации этих принципов в КС МВС ПА;
.- - разработка методов системного управления КС ЮС ПА;

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

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

1. проблемы коммутации в МВС ПА должны быть увязаны с проблемами исполнения алгоритмов;

2. любой алгоритм А из заданного класса алгоритмов &г

(на реализации которого ориентирована МВС ПА) должен быть принципиально исполним в МвС 1ІА;

3. при возникновении в МВС ПА неисправностей, вплоть до некоторого порогового их числа J\ , алгоритм, реализованный в ШС, должен продолжать исполняться без потери производительности. После превышения _\ алгоритм должен продолжать исполняться с некоторой потерей производительности;

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

5. алгоритмы' управления КС должны бнтв адаптированы таким

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

Таким образом, предметом и ее едования диссертации являются специфические КС для МБС ИЛ, в которых указанные выше задачи решаются на основе систегл:ого подхода.

В диссертации решаются следующие о с л с -в н н е' з а д а-ч и:

исследовать эффективность использования в качестве коммутационных систем МВС ПА КС линейного типа;

оценить сложность линейных КС, необходимую к достаточную для реализации в МВС ПА разовой коммутации (коммутации каналов);

исследовать способы повышения живучести КС МВС ПА;

разработать принципы'системного управления КС МВС ПА, допускающих переход от коммутации каналов к коммутации сообщений;

разработать принципы построения КС гяперкуокческого типа, раоотающих по' принципу-коммутации сообсений;

разработать эффективные процедур; маршрутизации в гипер -куоовых КС;

- разработать способы.введения в КС элементов интеллектуа
лизации. '

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

Для подтверждения основных положений диссертации проводи -лось моделирование на ЭВМ методом статистических испытаний.

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

Известные КС не позволяют решать указанные задачи в сово -купности и поэтому не могут быть непосредственно использованы I ЫВи Па.

В результате проведенных в диссертации исследований получе ны следующие основные результаты:

разработаны теоретические основы построения специфически КС, ориентированных на использование в МВС ПА;

разработаны и исследованы новые способы организации КС, пояучояы новые структуры КС, оценена их сложность при реализм»

ізличкнх принципов номлзтации;

с позиций системного подхода разработаны принципы орга -гзации, систем програгя.шроиания коммутации:, позволяющие пош -іть яивучесть и производительность КС и обеспечить удобное и зостое общение с пользователе?,!, синтезированы соответствующие ггорптмы;

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

рассмотрены бобмошгосги реализации в КС элементов яскус-гвенного интеллекта.

Итак, основные результаты диссертации связаш с розработ -ой новых структур КС, разработкой концепции построения систем рограАпшрования коммутации (и их адгоритштеск;,?о обеспечения), оэволявдих обеспечить эффективное управление коммутацией в !С А, а также - удобное'общение с пользователем.

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

тями, моделированием на ЭВМ, а также внедрением в разработках Ш МВС и других организаций.

Практическая ценность диссертационной заботы заключается в создании коммутационных систем для мвь Лл, ювшавдих эффективность вычислительного процесса за счет сокращения временных .затрат на обмен 'информацией мзгду блоками ШС ПА,-з такой организации структуры КС, которая ориентирована на ее реализацию в виде БИС и СБИС, в возможности веєдєния элементов ин -геллєктуализации КС и процесса общения с неЗ, а такке - в возможности использования полученных результатов в других системах, в том числе в системах передачи информации, в сетях-интегрального

обслуживан-ия и т.д.

Практические результата", полученные в диссертации, испол: зугатся при выполнении программы "Принципы создания универсалы го сверхпроизводительного суперлакронейрокомпьютера с програм руемой архитектурой и элементами искусственного интеллекта", : верзщенной приказом Государственного комитета по народному об] зозаяшз К 382 от 10.07.90 т., а также внедрены в разработках t делов НИИ МВС и подразделений НКБ "Миус" и ОКБ "Ритм" при TPTI

Апробация раб'Ь ты. Основные положения диссе]

тации докладывались, обсувдались-и нашли одобрение на 19 Междз народных, Всесоюзных, Всероссийских и региональных конференцю совещаниях и семинарах: Ш Всесоюзной конференции по однородны! вычислительным системам и средам, Таганрог, 1972; П Всесоюзне конференции по перспективам развития технической кибернетики, Москва, 1972; ГУ Всесоюзной конференции по аналоговой и аналої

цифровой вычислительной технике, Москва, I97S; 71 Всесоюзной і ференции "Математическое моделирование. Теория и метода гибрщ

них' вычислений, Таллин,. 1973; П Всесоюзном совещании по инфор* ционным сетям и автоматической коммутации, Москва, 1973; Всесс юзном совещании "Гибридные вычислительные машины и комплексы", Киев, 1974; ІУ Всесоюзной конференции по однородным вычислитед ним системам и средам, Киев, 1978; У Мекдународном семинаре "Е кладные аспекты теории автоматов", Болгария, Варна, 1979; У Вс союзной школе-семинаре "Распределенная обработка информации", Львов, 1885; Региональном семинаре " Принципы построения систе контроля и управления", Новочеркасск, 1985; Региональном семин ре "Передовой опыт автоматизации проектирования, диагностики и применения 'микропроцессорных систем", Киев,. 1987; Региональном семинаре "многопроцессорные вычислительные системы", Таганрог, 1987; УП Региональном семинаре по однородным вычислительным, ср дам и систолическим структурам, Львов, 1988;-Всесовзаом семина ьо однородным вычислительным системам и средам, Мосива,. 1988;

П Всесоюзной конференции по живучести и-реконфигурация вычислительных и управляющих систем, Киев, 1989; Региональной научно-технической конференции "Измерение характеристик сигналов с применением микропроцессорных средств, " Новосибирск, 1988; X Ре -гиональном семинаре по однородным вычислительным системам и систолическим структурам, Львов, 1989; Всесоюзном семинаре "Микропроцессора в системах контроля и управления", Пенза, 1989; Все --союзном 'семинаре "Многопроцессорные вычислительные системі", Таганрог, 1991, а также на семинарах НШ МВС при ТРТй в 1972, 1980, 1991 и 1992 г.г.

Публик-ации. Результаты, полученные в дассертаци.'/., нашли отражение в 71 наушой работе, среди них 3 монографии, 6 авторских свидетельств.

Структура и объем д и с с з р т а ц и о н-

ноС работы. Диссертация состоит из 8 разделов, включат введение и заключение; изложена на 302 строл-иг.-зх машинописного текста и иллюстрируется рисунками,- таблицами я графиками на 101 странице. Имеется список литературы (205 ма,1г,;-;-нораний) на 9, страницах и прилояение (на \\% страницах мап'лгописного текста и 54 страницах иллюстраций, таблиц и графиков). Общий объем дис-сертаци и 5«М с.

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

В разделе I проводится анализ проблемі коммутации в МЗС ПА,

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

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

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

использовать в качестве КС для МВС.

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

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

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

Раздел 5 посвящен разработке алгоритмов, о которых говорилось выше. Предлагаются новые средства выполнения эквивалентных

-II -

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

'В разделе 6 проводятся конкретные схемные проработки. Показывается, что большую часть преобразований, описываемых в разделе 5, можно и целесообразно выполнять -непосредственно в блоках памяти МЗС ПА. 3 частности, здесь естественно выполняются такие указанные выше "универсальные процедуры", как приведение матри -цы к. виду минимальной матрицы, выделение из графа однородных и квазиоднородных подграфов и др. Показывается, тго здесь же >,:оя -но осуществлять обработку нечетких данных.

Седьмой раздел (заключение) обобщает полученные в диссертации результаты.

Диссертационная работа дополняется разделом Приложение, который включает документы, подтверядажшие внедрение и использование результатов работы и 5 собственно приложений соответственно к подразделам І.І; 2.4.2; 2.4.4; 3.7 и 5.2.5.1.

3 Приложении I проводится анализ целесообразности использования в МВС ПА многокаскадных КС.

В Приложении 2 приводится программная система оценки елок -ности линейных КС.

В Прилояении 3 представлена программная система оценки сложности реализации в линейных КС различных перестановок.

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

В Приложении 5 приведен алгоритм распознавания изоморфизма однородных ориентированных 'графов степени два, дополняющий раз -

работки автора, касающиеся изоморфизма графов.

На защиту выносятся следующие основные н а у ч -н:ые положения:-

1. теоретические основы построения коммутационных систем для МВС ПА;

2. новые структуры КС МВС ПА;

3. концепция построения систем программирования коммутаций и их алгоритмическое обеспечение:

4. методика синтеза гиперкубовых КС и принцип маршрутизации сообщений в них; _ '

5. способы введения' элементов интеллектуализации в КС МВС ПА