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

¡-I К, V I к ч> °

ШИСТЗРСТВО НАУКИ, ВЫСШЕЙ ШКОЛЬ! И ТЕХНИЧЕСКОЙ ПОЛИТИКИ 1ганрогский радиотехнический институт им.В.Д.Калмыкова

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

К0ДАЧИГ08 Виктор Идьич

УДК 6в1.324.С2(043,3)

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

ПРОГРА'ДШРУЕМОЙ АРХИТЕКТУРОЙ

иеииальность 05.13.13 "Вычислительные машины, комплекс«, система и сети"

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

Таганрог-1993

Г-

БИЬЛ'лО >

Работа выполнен^ в Научно-исследовательском институте многопроцессорных вычислительных систем при Таганрогском радиотехническом институте им.В.Д.Калмыкова

Официальные оппоненты: члзн-корреспондент РАЕН, д.т.н..профессор Топопьский Н.Г. доктор технических наук, с.н.с. Малюгин В.Д. доктор технических наук, доцент Бояич В.И.

Ведущее предприятие: Институт прикладных проблем механики и математики АН Украины

Защита состоится 1993г.в 14.00 часов на заседании

специализированного совета Д 063.13.01 по защите диссертации на соискание ученой степени доктора технических наук при Таганрогском радиотехническом институте имени В.Д.Калмыкова по адресу: 347928, Таганрог, Ростовской обл., ул.Чехова, 2, НИИ МВС ар ТРЗИ, конферэни-эал.

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

Ученый секретарь с пе £ша ли зированяого совета к.т.н.,с.н.с.

Калачев В.А.

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

Актуальность темы. Проблема коммутации в вычислительных системах вообще и в вычислительных системах с про -грашируемой архите турой (МВС ПА), в частности, является акту -альной, несмотря на то, что к настоящему времени выполнено до -вольно много теоретических исследований и практических разрабо -ток, касающихся ее решения. Это обусловлено тем, что на коммутационную систему (КС) МВС ПА возлагается не просто задача образования требуемых связей, которая является достаточно сложной саге, по себе ухе при относительно небольшом числе процессоров. КС ИВС ПА должны "уметь" не только автономно настраиваться па нужные соединения, но также и перестраиваться на новые соединения, восстанавливая разорванные неисправностями сеяги и поддергивая,тем самям, определенный уровень живучести связей, '^йче говоря, КС Г,©С ПА должны самостоятельно реиать проблему управления процес -сом установления и поддержания функционирования соединений. Из сказанного видно, что при создании КС [ЛВС аЭДЫ'?гложет дать только комплексный подход к разработке еггут- ;;т;у КС и методов управления ими, к выбору сложности КС/к обеспс:?1пто их живучести. Еще.одной важной компонентой, связанной с'решением этой проблемы, является введение в КС элементов интеллектуализации, в частности; определение требований к языку управления ко"ЗтациеЗ высокого и сверхвысокого уровней, разработка самого этого языка, организа -ция структуры КС на основе иерархичности, многосяойности, обеспечение принципиальной возможности перехода к неа.тг.у'этмической обработке информации в МВС ПА.в целом путем обработки нечеткостей,-адаптации к решаемой задаче и т.д.

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

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

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

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

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

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

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

- анализ эффективности реализации этих принципов в КС МВС ПА;

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

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

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

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

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

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

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

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

5) алгоритмы' управления КС должны быть адаптиронаны таким образом, чтобы они могли исполняться с помоиыо самой ШС ПА.Причем эти алгоритмы по возможности должны организовываться как модификации некоторых "универсальных" процедур.

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

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

ч и:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пличных принципов коммутации;

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

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

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

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

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

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

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

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

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

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

ных'вычислений" Таллин,. 1973; П Всесоюзном совещании по инфорь ционным сетям и автоматической коммутации, Москва, 1973; Всесс юзном совещании "Гибридные вычислительные машины и комплексы", Киев, 1974; 1У Всесоюзной конференции по однородным вычислите; ним системам и средам, Киев, 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 гга.к.онаваний) на 9. страницах и приложение (на страницах ма?;*тописного текста и 5М страницах иллюстраций, таблиц и графиков). Общий объем дис-сертаци и 5 «М с.

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

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

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

строящаяся по тиду"многомерные" решетки - гиперкубоподобные КС.

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

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

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

/

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

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

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

_ц -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

■ I. Анализ проблемы коммутации в многопроцессорных вычисли -тельных система;-: с программируемой архитектурой.

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

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

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

НовиЯ класс проблем возникает, если Исходная задача зада -на не в виде сети процессоров, а в виде алгоритма.

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

• Дяя КС ЫВС ПА важны также такие ахаражтерястиви, как пара- ' щиваемость, способ получения настроечной ин^ярьзацяи, регуляр -ность структуры, а также сложность КС и ее кнвучвсть.

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

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

тями и способностями в наращиванию, а также большей живучестью. Это так называемые линейнйе КС, предложенные автором еще в 1969 году.

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

Модель МВС ПА в общем о точки врения коммутации это пятерка

^^ *<{р}*Р, * ^ гсе> ,

где ^р^ - множество операторов, определяющих порядок распо ■ лонения групп элементов - стандартных блоков, - множество операторов, определяющих характер объединения их в группы; V/ граф связей между группами элементов (блоками), V/*"*- граф свя -зей между группами стандартных блоков.

- модель стандартного блока. Она аналогично V/ определяет порядок объединения групп элементов МВС ПА в одинаковые (стан -дартные) группы - блоки.

Линейная модель ограничивает множества /рJ и ¿Р операторами линейного порядкаг Графы же и могут быть любыми регулярными графами, не обязательно одинаковыми (как в ба -зовой модели линейной КС, где они являются частью двумерной ре -шетки). В" диссертации синтезируется несколько разновидностей линейной КС, строящихся на основе различных графов V/ и IV , повазнвапцих, что линейные КС легко и естественно объединяются в Еерархитаскке структуры и модифицируются в многослойные построения. Рассмотрены такие способы увеличения комбинаторных свойств линз&шх КС на основа перехода от стпувтда двушрвоЗ решетни к

-

многомерным решеткам.

2. Коммутационные системы линейных МВС ПА

Общая идея построения линейках КС проста: б матричный коммутатор в промежутках между шинами добавляются такие же ключи, что стоят на пересечении вертикальных и горизонтальных шин (а дальнейшем такие элементы в отличие от элементов коммутации называются "разрывши" или "коннекторами"; шина с коннекторами -называется "линейкой"). Это позволяет образовывать ча одной ли -нейке более одной связи между внешними полшшя? КС. Кроме того, :>десь в принципе возможен обход неисправностей путем перехода с одной линейки на другую. Структура КС остается однородной, что облегчает ее микроэлектронную реализацию.

Возникает вопрос: сколько линеек ( £ ) необходимо и до -статочно для образования произвольных соединений зсел /V С - входовых процессоров МЗС ПА.

В диссертации рассматривается несколько подходов я решению этой задачи. Однако, все они не дают- общего аналитического ре -шения. В связи с этим'для оценки' £ был привлечет -летэд Монте-Карло. Общая схема эксперимента такова. Генерируется серия из К случайных графов для конкретного С и /У . Кягдна граф подвергается такому преобразованию, при котором, его г -'ализация в ли -нейной КС требует минимального числа линеек. В результате имеем К значений. Максимальное из них принимается за оценку £ для пары с, А/ . Таким образом получены графики функции

£ - £ (с) /V) для с =1-5, 1000. Сравнение значе-

ний функции . {{с, А/) с оценкой для матричных '¿о'лыутаторов 0{сА/г') показывает, что сложность линейных'КС действительно меньше, чем у матричных коммутаторов..Оно меньше и по сравнению с многокаскадными Условно-неблокирующими схемами разовой неодинарной коммутации ( 0(с//вер о//) ). Особенно большой эффект дд-стигаатся при'ориентацйи ЮС ПА на решение конкретных классов задач. Так, для реализации связей в сетях из специализированных процессоров - цифровых интеграторов девяти линеек достаточно.

для решения любых дифференциальных уравнений и систем алгебраических уравнений до пятого порядка. В общем несложно реализуются в линейных КС и перестановки: число лигееа ^ , требуемое для их образования таково, чте «/V,

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

Большое внимание уделяется в диссертации рассмотрению од -

Г

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

Сравнение узловых и "дублированных" КС (т.е. таких, в которых каждый элемент многослойно дублирован) показывает, что узловые КС "лучше" дублированных.

В диссертация предлагаются конкретные'способы организации

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

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

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

• 3. Гиперкубовые й гиперкубоподобные КС МВС ПА

Сеть "гиперкуб" (ГК) известна с конца 7С-х годов; в начале 80-х годов описаны сети "куб циклов", "обобыс'пшй гиперкуб" и др. В настоящее время ГК »- наиболее связные известные структуры, позволяющие объединять процёссоры в реальные- многопроцессорные1 сио -темы. Основных недостатков у так организованных систем три. Во-первых, это прямая зависимость числа межпроцессорных связей от числа процессоров (размерности ГК). Б.о-вторых, необходимость синхронизации работы процессоров. В-третьих, возможность блокировок. Главной причиной,ограничивающей широкое применение ГК-струк-тур, остается сложность блока маршрутизации.'

В диссертации предлагаются ноше эффективные'решения, позволяющие облегчить решение'этой проблемы. Другая задача, решаемая в связи с ГК КС, - как быть при возникновении в ГК неисправное •-тей в его ребрах? И, наконец, третьей из рассматриваемых в дис - -сертации задач, касающихся ГК-структур, является попытка систематического исследования способов построения ГК на. основе различ -

них "правильных11 и "полуправильных" многогранников. Отличительным признаком всех этих построений является отказ''от двоичной нумерации вершин и связан-ых-с ней ^процедур' иаршрутдзации (трансляции).

Особенность -изложения основных результатов исследования ГК-структур является язык их представления:-там, где ¡вто возможно используются двумерные ("расплющенные") графовые Модели мно ■ гомерных многогранников. Это позволило избегать сложных матема • тических описаний, обычно используемых для характеризации структуры и свойств различных ГК. В' качёстве основы -указанных пЪстро! ний в диссертации принята графовая модель многомерных*кубов,введенная автором в его кандидатскбй диссертации еще в 1971 году. Эта модель представляет собой вложенные друг в друга "четверки циклически соединенных вершан; сами циклы, соединены друг с дру ■ гом по принципу полного графа. Нумерация вершин сплошная: во внешнем цикле, начиная с левого верхнего угла, все вершины нуме-

Ч

руются подряд от I до 4; аналогично нумеруются вершины первого вложенного в него' цикла (от 5 до 8) и т.д. При этом связи между вершинами разных циклов, определяются так: -для любой ¿'-вершины ( ¿' = 1,4/?. , м, -газмерность куба) существуют ребра ( /

для 4*.

к=причем £ = I для всех /■^•бч и 4 ли «¿4

. Вели принять число вершин в циклах равным К ( К > 4),. то аналогично можно построить множество псеЕДокубов. очевидно,-степень вершин в обоих случаях зависит от

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

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

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

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

J, - х ■ _

В результате^, проведенных''исследований строятся ноше Госструктуры и удобные в реализации процедуры маршрутизации." В итоге предоставляется возможность по заданной'четверке параметров: .-сложность ГК, время обмена сообщениями, допустимая степень вер -шин,^' -выбрать наиболее эффективную ГК-сТруктуру КС.'

4. Концепция управления- коммутацией процессоров в КС линей- .' ных МВС ПА.

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

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

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

Развиваемая в . диссертации концепция управления коммутацией исходно предполагает системный подход к решению указанных задач. (Они образуют список Ы*). Он связан с удовлетворением набора системных-принципов (они приведены выше в подразделе "цёли работы"). »

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

- переразмещения процессоров или. их групп относительно входов (выходов) КС;

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

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

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

1. МПС строятся из однотипныж элементарных процессоров (Пр ) блоков памяти (БП).

2. Группы из/l^ Пр и БП объединяются в одинаковые мультипроцессоры СМПр ) с помощью локальной KCl.

3. Все/У/^е объединяются друг с другом в единую систему с помощью КС2.

Общий подход к решению задач в МПС таков: путем настройки групп элементарных процессоров образуются микрокоманды функций некоторого базиса, которые "умещаются" пределах одного мультипроцессора; с помощью таких же процессоров соседних мультипро-' -цессоров "набирается", решение задачи. Причем в качестве исходного задания используется граф-схема.алгоритма, а ее реализация в МПС осуществляется с помощью, системы программирования коммутации (СПК), которая предоставляет пользователю возможность в'ре жиме диалога влиять на процесс и.качество исполнения алгоритма в МПС. Эффективность же исполнения алгоритма гарантируется тем,что он распараллеливается. В диссертации предлагаются дополнительные способы ее увеличения за счет уменьшения числа пересылок "между элементами как внутри Afflp , так и на уровне самих /*}/7р . Воз-. можности этого заключаются в следующем.

Пусть Р(- - обобщенный функциональный оператор l -го шага (i -го яруса ярусно-параллельной формы) алгоритма; /(. = J

- оператор обобщенного считывания l -го шага, где Я Cr - обоб -■ щенный оператор считывания из процессоров ( С -1)-го шага, а

- из ЗУ. Пусть v// ~ - оператор'обобщенной записи

i -го шага, где wf-, - оператор обобщенной записи в процессоры (1 +1)-го шага, а "^Уд - в ЗУ. Пусть, наконец, С( - оператор обобщенного обмена Между БП. • '

- ~¿a-

Тогда один такт работы МПС можно описать так:<^' -Я^Р,'} а процесс исполнения алгоритма выглядит так:

К р< Ч С, .

1й иЫКг

'лктически же структура МПС допускает более эффективные дисциплины исполнения:

АлР^ь... \fi-uPt р-* л • • • ; ■

с. с,. Я' С, ^ о

-_*---^---ЯЦ Я32

шлг .—,—^ -г-

/4iuclz ¿ 4UATI 3 ¿¿саг

Каждая из этих дисциплин реализуется в МПС со своими сложностями.

В общем на СПК возлагаются следующие функции (считается, что уже выбран метод решения задачи и сформирован алгоритм решения):

' - предварительная оптимизация алгоритма;

- покрытие алгоритма операторами базиса;

- распараллеливание;

- оптимизация (отображение в КС);

- параллельная настройка КС;

- исполнение, алгоритма;

- сервис: укрупнение - разукрупнение; изменение степени параллельности, перепокрытие; перестроение связей; топологические преобразования ГСА; эквивалентные преобразования ГСА; эквива -лентные преобразования JTCA; диалог с пользователем; контроль связей.

Таким образом, система воспринимает на входе алгоритмы, задан -ные в виде операторных алгоритмов (граф-схем (ГСА)или логических, схем -|ЛСА). алгоритмов), преобразует их к виду, удобному к pea -лизании в МПС, управляет кок/;тацией при их исполнении в МПС," в ". том числе и при деградации системы, обеспечивает диалог с поль. зователем.

. Под преобразованиями алгоритмов имеются в виду две группы эквивалентных преобразований:

- упрощение логической и функциональной частей ЛСА;

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

Б связи с этим описанные выше системные'' принципы (см.подраздел "цели работы) можно перефразировать следухщм образом.

Принцип I. Перед отображением алгоритма в МПС eró целесообразно оптимизировать.

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

Принцип 3. Процесс получения настроечной информации и управ- • ления обменами между /Jp и БП поручается одной и той же системе - СПК.

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

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

алгоритма в МПС,~

® 1

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

- обеспечение пространственной коммутации до тех пор, пока это допускают ресурсы КС;

- передачу функций управления коммутации системе программирования коммутации (СПК);

- осуществление при возникновении в КС дефицита .коммутационных ресурсов перехода ít коммутации сообщений.

Учет возможностей и особенностей реализации этих' положений в СПК показывает следующее:

- в качестве входного языка СПК южно (целесообразно, удобно пользователю) использовать язык ЛСА;

- дисциплины исполнения алгоритмов можно организовать та -> ким образом, чтобы совмещались процесс выполнения этапов (яру -сов ярусно-паралледьной формы алгоритмов и обмены типа/¡р ; Пр •■> БП; БП -»■ Пр; Ш -*■ БП. Это сокращает общее вре -мя исполнения алгоритмов; 'С * '

- эквивалентными преобразованиями ЛСА можно еще более повысить эффективность исполнения алгоритмов.

В диссертации выделяется список $ таких преобразований. Часть из них известна, другие вводятся впервые.

5. Метода представления и оптдаивацаи алгоритмов с точки . зрения коммутации в МВС ПА.

Имеются в виду два вида алгоритмов: прикладные и системные. Причем среди системных выделяются те' алгоритмы СПК, которые пре -

образуют прикладные алгоритмы к виду, удобному для исполнения в МВС ПА с точки зрения коммутации.

Выше было выделено два типа таких преобразований: эквива -лентные преобразования логических схем алгоритмов (ЛСА) и топологические (графовые) преобразования граф-схем алгоритмов (ГСА).

В диссертации вводится расширение исчисления А эквивалентных (равносильных)/преобразований ЛСА Янова-Ершова, позволяющее выполнять специфические преобразования ЛСА, оптимизирующие связи, улучшающие исполнимость, живучесть и т.д. Это расширение касается, функциональной части алгоритмов. '''

вводятся- аналоги логических аксиом ^ :

- правило смены + и - стрелок;

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

и также аксиомы топологических преобразований:

- правила укрупнения - разукрупнения функциональных опера-^ торов;

- правила переноса выходной стрелки на вход.

Рассматриваемые в диссертации топологические пр'еобразова -пия ГСА имеют одну особенность, предопределяемую принципом 5 (см.подраздел "цели работы"):- они используют или являются модификациями некоторых "базовых" процедур.

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

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

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

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

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

6. Некоторые особенности реализации КС и систем программирования коммутации КО МВС ПА.

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

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

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

Здесь же показывается, как ведется предварительная обработка нечетких данных, такая как выполнение операций дизъюнкции, конъюнкции, импликации, отрицание, "штрих Шеффера", "стрелка Пирса" над нечеткими переменными в нечеткой логике Заде.

Заключение

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

КС многопроцессорных систем различного назначения принято [елить на два класса: сети межсоединений и процессорные структу->н. Этому делению в теории связи соответствуют КС с коммутацией шалов -1 КС с номтлутачг";й сообщений.

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

Среди КС типа "процессорная структура" обращают на себя нимание сети типа "гиперкуб", "куб циклов","обобщенный гипер -уб" и изоморфные им сети и подсети.

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

Развиваемые в диссертации подходы к управлению линейными КС • :нованы на следующих посылках:

- до тех пор, пока это возможно, в КС обеспечивается режим • »ммутации каналов;

- при возникновении дефицита коммутационных ресурсов осуще-'вляется переход к режиму коммутации сообщений;

- основные функции управления коммутацией возлагаются на стему программирования коммутации (СПК).

и этом в качестве исходного языка (входного языка СПК)"исполь-ется язык логических, схем алгоритмов (ЛСА). Для повышения эф -ктивности коммутации эти алгоритмы предварительно приводятся к'

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

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

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

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

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

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

Результаты, полученные в диссертации, используются при вы -полнении программы "Принципы создания универсального сверхлроиз-водительного супермакронейрономпьютера с программируемой архитектурой и элементами искусственного интеллекта", выполняемой в НИИ T.TBG в соответствии с приказом Государственного комитета по народному образованию JS 482 от 10.07.90, в разработках НКБ "МИУС" и ОКБ "РИПЛ" при ТРТИ и в учебном процессе специальности 22.04 ТРТИ

Результаты диссертьд..; опубликованы в следующих работах.

I. КодачигоаВ.И., Витиска Н.И., Кравченко A.B. Цифровая интегрирующая. структура с пространственно-временной коммутацией ин-

формационных каналов.//Мат.3 Всес.конф.по однородным вычисли -темным системам и средам, Таганрог, 1972.

2.,Кодачигов В.И., Витисна Н.И. и др. Построение систем коммутации информационных каналов 0ЦИС.//Мат.З Всес.конф. по однородным вычислительным-системам и средам, Таганрог; 1972.

3. Кодачигов В.И. О построении и организации настройки коммутирующих сред 0ЦйС.//Мат.З Всес.конф. по однородным вычисли -тельным системам и средам, Таганрог, 1972.

4."Кодачигов В.И.Кравченко A.B.,06 одной задаче декомпо -зиции графов п ее пользовании для оптимизации ОВДС с пространственно-временной коммутацией информационных каналов.//Мат.3 Всес. конф. по однородным' вычислительным системам и средам, Таганрог,

. 1972.

5. Кодачигов В.И., Витиска Н.И. Об одном способе управления mhoiокаскадными системами коммутации.//Тез.докл.2 Всес.конф.До >-стияения и перспективы развития технической' кибернетики. - М. :

• 1972. '

6. Кодачигов В.И., Кравченко A.B. О построении специальных, видов 0ЦИС.//Тез.докл.2 Всес.конф. Достижения и перспективы развития технической кибернетики., - М.: 1972. .

7. Кодачигов В.И., Кравченко A.B. О возможности построения -

. ОЦИС с пространственно-временной передачей приращений.//Сб.Однородные вычислительные и интегрирующие системы, Таганрог, 1973.

. 8. Кодачигов В.И., Кодачигов И.А. Алгоритм распознавания изо-морфизма-однородных'ориентированных графов степени два.//Межву -зовский тематический сб.Однородные цифровые вычислительные и интегрирующие структуры, Таганрог, 1973, вып.Г.

9. Кодачигов В.И., Кравченко A.B. Некоторые вопросы нЕхлрой-ки связей .в вычислительных структурах на основе цифровых инте -граторов.//МатЛО Всес.конф. по аналоговой и аналого-цифровой вычислительной технике. - М., 1973.

10. Кодачигов В.И,.,-Кравченко A.B. О выборе типа и сложности | интегрирующей структуры, оперирующей с разделенной во времени информацией в каналах связи*//Мат.У1 Всес.совещания Математическое .

моделирование, теория и методы гибридных вычислений, Таллин,

1973.

11.' Кодачигов В.И., МакаревичО.Б, и др. Разработка модуля коммутации коммутатора общей памяти.//Регистрация НИР, 1983.

12. Кодачигов В.И., Кравченко A.B., Витиска Н.И. Плоские каскадные коммутационные схемы на основе четырехполюсных коммутирующих элементов для построения логических i вычислительных структур.//Изв.СКНЦЗШ, Ростов, 1973. ' ,

13. Кодачигов В.И., Кравченко A.B., Витиска Н.И. О выборе типа и сложности ОЩС при реализации практических сетей "чгегра-торов.//Тез.докл.2 Всес.сов. по информационным сетям и автоматической коммутации. М., 1973.

14. Кодачигов В.И., Витиска Н.И. Модульная реализация каскадных коммутационных систем цифровых интегриручщих структур.//Межвузовский тематический сб.Однородные цифровые вычислительные и интегрирующие структуры, Таганрог, 1975, вып.З.

т

15. Кодачигов В.И., Витиска Н.И. О построении многокаскадных коммутационных схем для цифровых интегрирующих структура/Межвузовский тематический сб.Однородные цифровые вычислительные и интегрирующие структуры, Таганрог, 1975, вып.5.

16. Кодачигов В.И., Зайко Ю.Г. и др. Коммутатор операцион -ной памяти с параллельно-последовательной организацией каналов и о произвольно назначаемыми приоритетами.//Вопросы р/з, серия ЭВТ, 1973, еып.1.

17. Кодачигов В.И., Витиска A.B., Макаревич О.Б. Об исполь -аовании каскадных схем в коммутационных системах цифровых инте -грируших структур.//Межвузовский тематический сб.Однородные цифровые вычислительные и интегрирующие структуры, Таганрог, 1973, вып. 2.

18. Каляев A.B., Кодачигов В.И. и др. Использование каскад -ных коммутационных систем в цифровых интегрирующих структурах.// Тезисы докладов 2 Всесоюзного совещания по информационным сетям и автоматической коммутации, Ч, 1973.

19. Кодачигов В.И., Кравченко A.B., Витиска Н.И. О возможности построения двумерных каскадных коммутационных систем.//Тезисы докладов 2 Всесоюзного совещания по информационным сетям и автома -тическоЯ коммутации, М., 1973.

20. Каляев A.B., Кодачигов В.И., Витиска Н.И. Коммутационные схемы с петлевыми соединенными входов и выходов для цифровых ин-. тегрируюащх структур.//Сб.Информационные сети и их структура, Ч., Наука, 1'ШПи, 1976. ■

21. Кодачигов В.И. и др. Электронный искатель-разъединитель. //АС СССР % 499665, БИ № 2, 1976.

22. Кодачигов В.И., Каральник М.Б. Ре.'жимы управления кокмута-цией процессоров в МВС ПА.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1987.

23. Кодачигов В.И., Каральник М.Е. Управление в функционально надежных мультипроцессорных системах релейной защиты.//Сб.Средства и системы управления в технике и технологии, Новочеркасск, 1988.

24. Кодачигов-В.И., Макаревич О.Б., Витиска Н.И. и*др. Исследование .методов управления ОЦИС.//Рег.НИ? № 7I00I076,

инв.й B43I925, 1976. ,

25. Кодачигов В.И., Макаревич О.Б. и др. Разработка-коммутатора оперативной памяти и исследование алгоритмов и задач диспет-чирования в многопроцессорных системах.//Per.НИР 77017332, инв.К B64I770, 1978.

26. Кодачигов В.И., Макаревич О.Б. и др. Разработка и исследование элементов ОЦИС на ИС с средней и большой степенью интегра -ции.//Рег.НЙР № 77017332, инв.№ B64I770, 1978.

27. Кодачигов В.И., Кодачигов И.А. Алгоритм выделения квазиоднородных блоков из сетей, размещаемых в двумерных одногэдп структурах.//Изв.АН СССР. Автоматика и телемеханика, 1974, №

28. Кодачигов В.И., Кодачигов И.А. К проблеме выделения бло -ков, совпадающих с топологическим рисунком двумерных однородных структур из размещаемых-в них логических сетей (сетей процессо -ров).//Межвузовский тематический сб.Однородные вычислительные и интегрирующие структуры, 1975, вып.4.

29. Кодачигов В.И. К проблеме сокращения объемов памяти и настроечной информации однородных структур с индивидуальной настройкой элементов.//Межвузовский тематический сб.Однородные вычислительные и интегрирующие струнтурн, Г975, выи.4.

. 30. Кодачигов В.И., Витиска H.H. Выбор оптимальных параметров одного класса разделенных каскадных коммутационных схем.// Мат.Всес.совещания Гибридные вычислительные машины и комплексы, Киев, 1974. >

31. Каляев A.B., Кодачигов В.И., Витиска Н.И. О построении неразделенных систем для. реализации графов коммутации интеграторов.//Мат. Всес. совещания Гибридные вычислительные машины и ком -плексы, Киев,.1974.

32. Кодачигов В.И., Макаревич O.E.; Витиска Н.И. Электрон -ный искатель-разъединитель.//АС СССР, № 422I0I, БИ № 12, 1973.

33. Кодачигов В.И., Витиска Н.И. Электронный искатель-разъединитель.//АС СССР, й 4355Л, БИ й 25, 1974.

34. Кодачигов В.И., Витиска Н.И. Ячейка многокаскадной ком -мутационной системы.//АС СССР, )« 5II578, БИ й 7, 1975.

35. Кодачигов В.И., Зайко Ю.Г. и пр. Некоторые варианты коммутаторов общей памяти для. .мультипроцессорных систем.//Вопросы

-р/з, серия ЭВТ, 1978, вып.7.

36. Кодачигов В.И., Платонов В.А. и др. Теория однородных вычислительных и коммутирующих структур.//Per.НИР № 740I923I, 1976.

37. Кодачигов В.И., Витиска Н.И., Денисенко Н.И. Исследова -ние.принципов построения коммутационных систем и сред 0ЦИС.//Рег. НИР № 760I930I, 1977.

38. Кодачигов В.И., Каляев A.B. и др. Исследование коммута -ционных систем и сред ОЦИС.//Рег.НИР № 71001076, инв.Й Б223772, 1977.

автором диссертационной работы получены следующие результаты: сформулированы принципы пост^ния линейных КС и строящихся, на их основе иерархических к.'!'».рационных структур; разработаны принципы управления коммутацией в них; определена методика синтеза

опубликованных в соавторстве,

- S3 -

и оценки сложности многокаскадных КС.

39. Кодачигов В.И. Размещение сетей процессоров в плоских МВС на основе использования стандартных графов коммутации.//Сб. Многопроцессорные вычислительные структуры, Таганрог, 1982.

40. Кодачигов В.И. К проблеме размещения сетей процессоров в плоской МВС.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1981.

41. Кодачигов В.И. Принципы построения узловых коммутационных структур.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1983. .

42. Кодачигой В.И. Об одном подходе к решению задач топологического преобразования графов.//Межвузовский тематический сб. Автоматизация проектирования РЭА, Таганрог, 1983.

43. Кодачигов З.И., Бондарев А.И. Минимальные матрицы и некоторые их применения для проектирования структурно сложных уст -ройств.//Межвузовский тематический сб.Автоматизация программиро- ■ зания, проектирования и конструирования, Таганрог, 1982.

44. Кодачигов В.И. Системы программирования настройки ШС.// Сб.Многопроцессорные вычислительные структуры, Таганрог, 1982.

45. Кодачигов В.И. Электронная коммутация информационных каналов. //Под ред.Каляева A.B. - Ростов н/Д.: Изд.Р1У, 1983.

46. Кодачигов В.И., Витиска Н.И. и др. Об использовании ка -скадных'схем в коммутационных системах ВДМ.//Сб.Однородные вы -числительные и интегрируемые структуры, Таганрог, 1974.

47. Кодачигов В.И. К проблеме выбора типа и сложности коммутационных структур для ШС.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1985. .

. 48. Кодачигов В.И. Об управлении коммутацией процессоров в МВС ПА.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1986.

49. Кодачигов В.И., Чернов В.Н. Управление потоками информации в МШС, управления движением.//Сб.докладов- семинара МБС-87.

50. Кодачигов В.И. Системное обеспечение коммутации процессоров в МВС ПА.//Тез.докладов У Всес.школы-семинара РОИ, Львов, 1985. • '■ •

51. Кодачигов В.И., Каральник М.Е. Режимы управления коммутацией процессоров в МВС ПА.//Сб.Многопроцессорные вычислительные .структуры , Таганрог, 1987. 1

.52. Кодачигов В.И., Каральник М.Е. Управление в функционально надежных мультипроцессорных системах релейной запиты.//Сб. Средства и системы управления в технике и технология, Ново -черкасск, 1938.,

53. Кодачигов В.И., Каральник М.В. Способы управления вычислительным процессом в ММПС гибких релейных зашит.//Сб.Известия СКНЦ ВШ,серия техн.науки, 1987, № 4.

54. Кодачигов В.И., Кодачигова Л.К. Оценка сложности (с//)-графов.//Сб.Автоматизация проектирования РЭА, Таганрог, 1988.

55. Кодачигов Б.И. Некоторые особенности построения систем автоматизированного программирования настройки в ММПС.//Сб. Многопроцессорные'вычислительные структуры, Таганрог, 1989.

56. Кодачигов В.И. ,'Ввтеев Г.Н. и др. Принципы улучшения систем программирования настройки МВС ПА.//Препринт $ 17-88, ШШМ, Систолические вычислители, Львов, 1988.

\

57. Кодачигов В.И. Принципы системного управления коммутацией и настройкой в МВС, ПА.//Тезисы докладов Всес.семинара ОВС и СС, Москва, 1988.

58. Кодачигов В.И. Однородная вычислительная среда как средство параллельной трансляции программ для коммутирующих структур МВС.//Тезисы докладов Всес.конференции ОВС и СС, Москва, 1988.

■ 59. Кодачигов В.И., Каральник М.Е. Оптимизационные возмог -ности алгоритмов эквивалентных преобразований "сетей процессов, ; реализуемых в МВС.//Тезисы.докладов П Всес.НП конференции Живу- -честь и ревонфигурация..кйч,...и.1:аионно-вычислительншг и управляи--цщх Систем, Киев, 1989.

60..Кодачигов В.И., Каральник М.В. Построение процедурно-

аппаратных релейных защит.//Тезисы докладов региональной конференция Измерение характеристик сигналов с применением микро -машинных средств, Новосибирск, 1988.

61. Кодачигов В.И., Каляев A.B. и др. Системы программиро -вания коммутации з линейных мультипроцессорных системах.//Препринт № 13-91, НТЦ, Интеграл, -Львов, 1990.

62. Каляев A.B., Кодачигов В.И. и др. Об одном подходе к построению КС для ЖС.//Сб.Многопроцессорные вычислительные струк- • туры, Таганрог, 1990.

63. Кодачигов В.И., 1Узин В.Ф. и др. -О расширении оптимизационных возможностей эквивалентных преобразований сетей процессоров, реализуемых в МВС.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1990.

64. Кодачигов В.И., Каральник М.Е. Универсальная КС.//Тезисы доклада Всес.семинара Микропроцессоры в системах контроля и управления, Пенза, 1989.

65. Кодачигов В.И., Ввтеев Г.Н. и др. Программная-система кодирования графов коммутации сетей^ реализуемых в ОВС.//Тезисы доклада X семинара по ОВС и СС, Львов, 1989.

66. Кодачигов В.И., Карелин В.П., Мелихов А.Н. Устройств© анализа-нечетких данных.//АС СССР, Л 1683004, 1991.

67. Кодачигов В.И., Карелин В.П., Мелихов H.A. Устройство для выделения экстремального числа.//АС СССР, !Ь 1590999, 1990.

Среди работ ^39-67^ в работах, опубликованных в соавторе'"^, автором диссертации получены следующие результаты: предлокочм принципы организаций систем программирования коммутации МВС; разработаны алгоритмы их работы.

68. Каляев A.B., Кодачигов В.И. Гип'еркубовие систеш комлу -тации многопроцессорных систем.//Препринт $ 14-91, НТЦ Интеграл, Львов, 1991.

69. Каляев A.B., Кодачигов В.И. Об одном подходе-к построению КС для МВС.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1990.

ТО. Каляев A.B., Кодачщчэв В-.И. Об организации КС статического типа.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1991.

71. Кодачигов В.И. Об оценке коммутационных возможностей и живучести одного типа гиперкубовых КС.//Сб.Многопроцессорные вычислительные структуры, Таганрог, 1992.

Среди работ /б8-71J в работах, опубликованных в соавторстве, автором диссертации получены следующие результаты: предложены структуры гиперкубоподобных КС; оценены их аппаратурная и временная сложность; разработана процедура маршрутизации.

ОП ТРТИ. За*Тир. 4СО 199« г.