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

I с . л <.■.!•;

АКАДЕМИЯ НАУК СССР Научный совет по комплексной пройлеме "Кибернетика"

На правах рукописи УДК 519.711.74

ДУДКО Алексей Львович

НЕБЛОКИРУЮЩИЕ КОММУТАЦИОННЫЕ СХЕМЫ С ДЕЦЕНТРАЛИЗОВАННОЙ НАСТРОЙКОЙ

л : -ч "'

'V

Специальность: 05.13.16 - применение вычислитель! .'. техники,

математического моделирования и математических методов в научных исследованиях Спо отраслям наук)

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

Москва - 1990

/ ' , 7 . /

Работа выполнена в Вычислительной центре Академии наук СССР

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

Официальные оппоненты: доктор технических наук, с.н.с. Горяшко А.П.

кандидат фкзико-магематических наук Буланже Д.Ю.

Ведущая организация: Институт проблем передачи информации , АН СССР.

Эащи^а состоится " " 1990 г. в

часов на ааседанни Специализированного совета Д 002.82.01 щ Научной соэете АН СССР по комплексной проблеме "Кибернетика" I адресу: 117333, Москва, ул.Вавилова, 40.

С диссертацией ыогно ознакомиться в библиотеке Научно! совета АН СССР по комплексной проблеме "Кибернетика".

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

Ученый секретарь Специализированного совета Д 002.82.01 какдкдат физико-математических наук// ;

- Г. П. Амирдхано!

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

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

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

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

- анализ существующих КС и режимов коммутации;

- разработка и исследование новых типов схем: частично сортирующих, обратно сортирующих и разделяющих;

- разработка и исследование новых типов неблокирующих в широко» смысле коммутационных схем с децентрализованной настройкой;

- сравнение новых схем с известными.

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

Научная новизна работы состоит в следующем:

- введены новые типы КС; частично сортирующие, обратш сортируювде и разделяющие;

- введены новые типы самонастраивающихся коммутационно элементов СКЭЗ;

- разработана теория, позволяющая получать новые типы КС и: известных сортирующих схем;

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

Практическая значимость и реализация результатов работы. Практическая значимость исследования состоит в том, чт разработанные новые типы КС обладают уникальным сочетание свойств и имеют в ряде случаев лучшие оценки сложности времени настройки, чем известные схемы. При больших значения числа входов/выходов новые схемы экономичнее по числ используемых' коммутационных элементов, чем известны сопоставимые с ними схемы. Результаты исследований использован в международном проекте "ПАМИР" (ВЦ АН СССР, Международна

Зазовая лаборатория по искусственному интеллекту при НТК САЮ, в райках которого они проводились.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались: на 14-ом Симпозиуме Словацкого кибернетического общества при Словацкой Академии ■¡аук "Кибернетика и информатика" СЧССР, Зубе реп, 1989), иа Международной научно-технической конференции СЧССР, Брно, 1988), на Всесоюзном семинаре "ЭВМ новых поколений и 1ерспективя их использования в народном хозяйстве" С Москва, 19893, на Международной конференции по комплексным научным фоектам КНП-1 и КНП-2 СЧССР, Смоленице, 1986), на семинарах (еадународноЯ базовой лаборатории по искусственному интеллекту фи ИК САН (ЧССР), Ш1Ш АН СССР, ИПС АН СССР, отдела Проблем искусственного интеллекта ВЦ АН СССР.

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

Структура и объем работы. Диссертационная работа состоит з введения, четырех глав и заклвчекия, содержащих 164 страницы [ашинописного текста, 51 рисунок, 18 таблиц. Список литературы клсчает 74 наименования.

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

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

В первой главе ■ введены основные свойства КС и дана лассификация КС С разделенные и неразделенные, пространственной пакетной коммутации, однонаправленные и двунаправленные, элкодоступные и неполнодостулные, ординарные и неординарные, грого неблокирующие ССНКС), неблокирующие в широком смысле ИШКСЗ, перестраиваемые СНПКС) и блокирующие СБКС)). Обобщены -феделения строго неблокирующих, неблокирующих з широком желе и перестраиваемых схем на одиночный, пачечный и разовый эжимы коммутации. Дан обзор существующих коммутационных схем

СКлосса, Кантора, Бенеша, Вакскана, минимальных полнодоступны: и сортирующих схем). Рассмотрены их особенности, достоинства ! недостатки. Дан обзор современных вычислительных систем построенных на основе коммутационных схем. Проведен анали: известных коммутационных схем, поставлена и обоснована задач; разработки новых неблокирующих в широком смысле ординарных i неординарных коммутационных схем, работающих в пачечном режим! коммутации с децентрализованной настройкой.

Во второй главе введены новые понятия и даны определена новым типам схем и коммутационных элементов СКЭ). Доказан! теоремы, устанавливающие связь между известными сортирующим! схемами и новыми частично сортирующими.

В п.2.1 введены понятия компактного распределения заяво! на коммутацию по полюсам схемы, компактного распределения паче! заявок и конкретные виды этих распределений КВО, КВ1, КУО Ш.

Дано определение схем типа SCN).

Определение 2.7. Сортирующие схемы, состоящие из КЭ1 i упорядочивающие на выходе . по возрастающим адресам заявки одновременно поступившие на все входы схемы, будем называт: схемами типа SCN3.

Целый ряд известных сортирующих схем являются схемам типа SCN).

На основе введенных режимов поступления пачек заявок дан! определения новых типов схем: частично сортирующих Ссхемы РСЮ ТОО, ОСЮ), обратно сортирующих Ссхемы RpCND, I^CN)) разделяющих Ссхемы ВрСМ), ВТСЮ).

Определение 2.8. Будем называть схему частично сортирующей, если при поступлении на ее входы заявок пачкам; после сортировки на выходы пачки поступают в режима: КВ0,КВ1,КУ0,КУ1 или в виде комбинаций этих режимов.

Определение 2.9 (2.103. Будем называть частично сортирующую схему схемой типа РСЮ СТСЮ), если при поступлени: на ее входы заявок пачками после сортировки на выходы пачк: поступают в режиме КВО СКВ1).

Определение 2.11. Будем называть частично сортирующу

хему схемой типа QCN), если при поступлении на ее входы заявок ачкаш на выходе схемы

1. Каждая пачка И( делится на две части и Н| такие, что если Dt еН°, и D4 eMj, если D4еН'.

2. М° поступают на выходы в режиме КВО.

3. HJ поступают на выходы в режиме КБ1.

В гл.4 рассмотрены иные частично сортирующие схемы NCN3, TNCN) и ОНСЮ.

Показано, что частично сортирующие схемы Р(Ю и ТСЮ

влявтся обощением сортирующих схем SCN), а схемы QCN)) -

Зодением схем РСЮ и TCN).

Определение 2.12. Будем называть схему обратно

зртирующей или схемой типа RpCN) CRj.CN)), если при поступлении

1 ее входы заявок пачками в режиме КВО СКВ1) и при этом таких,

го никакие их два адреса во всех пачках не равны между

эбой, т. е. D. , , , если i или j , каждый вход

Vi Va 11 1 а

семы, на который поступила заявка, соединяется с выходом,

«еюдим такой же номер, как и адрес заявки.

Схема RpCN) CRj.CN)) реализует преобразование обратное >му, которое реализует схема РСЮ СТСМ)).

Пусть на входы некоторой схемы поступают пачки заявок при этом задано каким-либо образом разбиение каждой пачки на »е и; и Н4" так, что Mt =Ht' U^".

Определение 2.13. Будем называть схему разделяющей или семой типа ВрСЮ СВТСЮ), если при поступлении на ее входы 1чек И "H'UMJ' в режиме КВО СКВ1), пачки Н4' поступают в режиме Ю СКВ1) на выходы схемы с номерами от 0 до N/2-1, а пачки Hj' в режиме КУ1 СКУО) на выходы схемы с номерами от N/2 до N-1.

В п.2.2. рассмотрены различные типы самонастраивающихся юичных коммутационных элементов. Для каждого КЭ приведен граф ¡реходов и таблица переходов соответствующего ему автомата, [исаны известные двоичные коммутационные элементы - КЭО и КЭ1 введены их обобщения - КЭ2-КЭ9.

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

- а -

синхронизации каскадов схемы.

В п.2.4. доказаны теоремы, устанавливающие связь меаду сортирующими и частично сортирующими схемами. Показано, что схемы нового типа (частично сортирующие схемы Р(Ю, ТС KD, QCN)) можно получить из сортирующих схем БСЮ путем замены КЭ1на КЭ2 СКЭ8), КЭЗ (КЭ9), КЭ4 соответственно.

Теорема 2.1. Если в сортирующей схеме SCN) заменить все КЭ1 на КЭ4, не меняя соединений между ними, т.е. топологию схемы, то получим схему QCN).

Теорема 2.2. Если в сортирующей схеме SCN) заменить все КЭ1 на КЭ2, то получим схему РШ.

Теорема 2.3. Если в сортирующей схеме SCM) заменить все КЭ1 на КЭЗ, то получим схему ТШ.

В третьей главе исследованы методы построения и настройки обратно сортирующих схем. Обратно сортирующие схемы типа К^СЮ и Rj(M) построены на основе разделяющих схем Вр(М) и В?(Ю, которые, в свою очередь, строятся из схем В"'(Ю, имеющих зеркально-симметричную топологию по отношению к схеме битонического сортировщика Бэтчера ВСЮ.

В п.3.1 доказаны теоремы о связи разделяющих схем ВрСМ) и ВТСЮ со схемой Бэтчера.

Теорема 3.1. Если на входы схемы ВСЮ, состоящей из элементов КЭ8 (КЭ9), поступают пачки заявок Н , где Н "H'IJHj', и пачки Mj поступают в режиме КВО СКВ1) на входы с номерами от О до il/2-l, а пачки Hf - в режиме КУ1 СКУО) на входы с кокерами от Н/2 до N-1, то на выходы схемы поступают пачки Mt в режиме КВО СКВ1Э.

Теорема 3.2. Пусть имеется схема В"'(Ю, состоящая из КЭ, которые могут находиться в трех состояниях а, Ь,с. Тогда эти КЭ могут быть настроены так, что схема функционирует как схема ВрСЮ CBTCN3X

Теорема 3.1 обобщает результат, полученный Бэтчероы, о свойстве битонического сортировщика преобразовывать .битоническую последовательность в монотонную. Теорема 3.2 не устанавливает каких-либо правил о настройке КЭ, составляющих схему В"1 СМ), для того, чтобы она функционировала как схема

- з -

ВрСЮ СВТСЮ). Эта теорема докапывает только возможность тако.1 настройки. Относительно КЭ утверждается только, что они долтшы иметь состояния а,b.c. Способы настройки схемы разрабатывается в следуюиих параграфах.

В п.3.2 выведены соотношения, которые позволяет вычислять для схем ВрСЮ СВТСЮЭ номера выходов (адреса), на которио должны поступить заявки, в зависимости от номеров входов, на которые они поступили. Эти соотношения используются для децентрализованной настройки схемы В"'CÍO, когда она используется в качестве разделявших схем ВрСЮ и ВТСЮ в п. 3.3.

В п.3.3 на основе выведенных ранее соотношений и свойств схемы В"'СЮ разработан такой метод настройки, которц;! обеспечивает ее функционирование в качестве разделяющей схемы ВрСМ) СВТСЮ).

Разработана структурная схема устройства, состоящего из приемо-передатчиков н процессорных элементов для обеспечения децентрализованной настройки схемы В"'СЮ. Устройство позволяет настраивать схему В"1 СЮ, как разделяющую схему ВрСЮ CB„CN)). Разработаны алгоритмы функционирования приемо-передатчиков и процессорных элементов, а такке структурная схема процессорного элемента. Таким образом, разработан метод конструктивного построения схем нового типа - разделяющих схем Вр(Ю (ВГСЮ). Каждый процессорный элемент функционирует автономно и не имеется какого-либо центрального блока управления. Настройка схемы В"1 СЮ в свою очередь происходит децентрализованно. Поэтому устройство в целом функционирует как схема ВрСЮ СВТСЮ) с децентрализованной настройкой.

В п.3.4 доказано, что обратно сортирующие схемы Р,рОО (RpCND) можно построить на основе разделяющих схем ВрСЮ (ВТСГО) путем декомпозиции на схемы с меньшим числом входов/выходов.

Теорема 3.3. Схема , построенная из схемы Вр(Ю (ВТСЮ) и двух схем RpCN/2) С Р^ С tí/2)), соединенных так, что

1. выход L схемы ВрСМ) CBTCN)) при 0<L<N/2-l соединяется с

входом схемы Rp CN/2) (Rj, CN/2)), имеющим такой se номер, i- i

2. выход L схемы ВрСЮ СВТСЮ) при N/2<L<N-1 соединяется с

входом схемы IL СN/23 (R_ CN/23), имеющим номер CN-1-L3,

г а

является схемой RpCN) CR^XN)).

Получены оценки числа точек коммутации и времени настройки для обратно сортирующих схем Rj,CN3 CRjCMDD.

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

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

Эти схемы получили название РРСЮ, ТТСЮ, QQCN3 и ОРТСЮ. Они образуют новый тип коммутационных схем, названный схемы DDCN).

Теорема 4.1. КС, построенная из двух схем PtCMJ и PaCN) путем соединения их выходов, имеющих одинаковые номера, является ординарной НШКС, функционирующей з пачечной режиме установления соединений с децентрализованной настройкой.

Эта схема получила название РРСЮ.

Аналогичные теоремы доказаны для двух схем ТСЮ и QCNJ.

Теорема 4.4. КС, построенная из схемы QCN) и схем РСН/2Э и TCN/2J, соединенных так, что

1. выход L схемы QCN) при 0SL5M/2-1 соединяется о выходом схемы PCN/2), имеющим такой же номер,

2. выход L схемы QCN) при N/2iLiN-l соединяется с выходом схемы TCM/2J, имеющим номер L-N/2,

является ординарной НШКС, функционирующей в пачечном режиме

- и-

установления соединений с децентрализованной настройкой.

Эта схема получила название ОРТСЮ.

Схемы РРСЮ, ТТСЮ, ШСЮ и ОРТ СЮ являются схемами с двусторонней настройкой, так как установление соединений мекду их полюсами4 происходит одновременно со стороны входов в направлении выходов и со стороны выходов в направлении входов. Два участка соединения "встречаются" друг с другом в середине схемы там, где соединяются выходы схем РСЮ, ТСЮ и ОСЮ.

Далее рассмотрены НШКС с односторонней настройкой.

Теорема 4.5. КС, построенная из схемы РСЮ СТСЮ) путем соединения ее выходов с входами схемы йрСЮ CRj.CN)), имеющим! одинаковые номера, является ординарной НШКС, функционирующей в пачечном режиме установления соединений с децентрализованной • настройкой.

Теорема 4.6. КС, построенная из схемы ССЮ и схем Rj.CN/2) и Rj.CN/2), соединенных так, что

1. выход Ь схемы (КЮ при 0<Ь<М/2-1 соединяется с входом схемы Rj.CN/2), имеющим такой же номер,

2. выход Ь схемы йСЮ при соединяется с входом схемы Rj.CN/2), имеющим номер Ь-М/2,

является ординарной НШКС, функционирующей в пачечном режиме установления соединений с децентрализованной настройкой.

НЖС с односторонней настройкой получили название РИСЮ, ТКСЮ и (ЖСЮ. Они образуют новый тип коммутационных схем, названный схемы БСЮ.

В п. 4.2 доказано, что неблокирующие в широком смысле неординарные коммутационные схемы, работающе в пачечном режиме установления соединений с односторонней децентрализованной настройкой, могут быть построены из частично сортирующих. схем РНСЮ, ТКСН) и ФО) и схем типа БСЮ. Эти схемы получили название РШСЮ, Т№)СЮ, и О!® СЮ. Они образуют новый тип коммутационных схем, названный схемы ОМСК).

Теорема 4.8. КС, построенная из схемы РНСЮ СТНСЮ, ОЯСЮ) путем соединения ее выходов с входами схемы ОСИ), является неординарной НШКС, функционирующей в пачечном режиме установления соединений с децентрализованной настройкой.

- 12 -

В п.4.3 получены оценки числа точек коммутации и времени ластройки новых. НШКС и проведено сравнение с известными схемами. Показано, что на основе разработанной теории могут ъ построена ИКС, более экономичные известных НШС и СНКС и пк'.'Ю'-¿но меньшее время настройки, чем ШКС, НШКС Клосса и СНКС Спри настройке нескольких соединений одновременно).

Ординарные НШКС ОСЮ и ЮБСЮ обладают одинаковыми коммутационными свойствами и различаются способами настройки. В ВСЮ - схемах с односторонней настройкой - пачки заявок поступают только на входы. Настройка ведется в направлении от входов к выходам. В ЭИСЮ пачки поступают на входы и на выходы схимы, а настройка ведется в двух встречных направлениях одновременно: от входов к выходам и от выходов к входам. Поэтому время настройки ОЭСМ) в два раза меньше настройки ОСЫ). Кроме того, схемы ЮСЮ строятся из двух частично сортирующих схем П'СЮ, ТСЮ, ОСИ)) и не требуют каких-либо дополнительных устройств. Для построения этих схем могут быть выбраны любые схемы ЭСЮ. Для построения схем ВСЮ используются схемы РСЮ, ТСЮ, ОСЮ и обязательно схемы Rj.CN) и Rj.CN), которые по своей топологии, хотя и являются схемами зеркально-симметричными• схеме БСЫ) - сортирующей схеме Бэтчера II, но имеют в своей конструкции столбцы приемо-передатчиков и процессорных элементов. Таким образом, схемы ЭОСЮ имеют более сложную конструкцию по сравнению с схемами ОСЫ) и вдвое большое время настройки, но их одностороняя настройка может в ряде случаев оказаться удобнее, чем двусторонняя настройка схем РОСЮ.

Неординарные схемы ОГО) по своим коммутационным свойствам не имеют аналогов среди других ШКС, В пачечном режиме коммутации эти схемы позволяют соединить несколько входов с одним выходом, если заявки на эти соединения попадают в одну пачку.

Из приведенных в п. 4.3. данных следует, что разработанные схемы настраиваются быстрее, чем СНКС Клосса при числе соединений в пачке порядка нескольких десятков, и быстрее, чем СНКС Кантора и НШКС Клосса при числе соединений в пачке порядка

нескольких единиц.

. - 13 -

Проведенный анализ показывает следующее. Используя разработанную в гл.2, гл.3 и гл.4 теорию, можно построить НЖ, обладающие сравнимыми или лучшими характеристиками, чем у известных схем. Так можно построить схемы более экономичнее, чем известные СНКС и НШКС Клосса Спри N>4096), и имеющие меньшей время настройки при числе заявок в пачке порядка нескольких десятков и единиц, соответственно. Заметим, что именно при больших N и при необходимости устанавливать одновременно много соединений и возникают проблемы построения КС, связанные с сложностью схемы и большим временем ее настройки. Экономичность, выражающаяся в меньшем числе точек, является следствием построения этих схем на основе одной из самых экономичных сортирующих схем - схемы Бзтчера (топологический фактор), а также применения децентрализованной настройки, реализуемой при помощи самонастраивающихся КЭ, т.е. КЭ с локальным устройством управления. Меньшее время настройки также достигается за счет применения децентрализованной настройки. В известных СНКС и НШКС отдельное соединение мозет быть построено быстрее, чем в разработанных схемах, но алгоритмы построения нескольких соединений одновременно не известны, и поэтому они должны строится последовательно. В разработанных схемах децентрализованная настройка позволяет реализовать пачечный режим, т.е. устанавливать любое число соединения одновременно, и при этом время их установления не зависит от их числа.

Построенные НШКС имеют большее число точек коммутации и время настройки, чем сортирующие схемы, которые являются ординарными НПКС, работающими в разовом режиме. Однако достоинством новых схем является то, что они работают в пачечном режиме, и, кроме того, схемы ОЖЮ являются неординарными. По сравнению с НПКС Бенеша разработанные схемы настраиваются в Н/1одИ раз быстрее. Более быстрая настройка разработанных .схем является следствием их большей аппаратной сложности.

Таким образом разработанные НШКС обладают следующим! полезными качествами:

- 14 - .

1. Экономичнее известных СНКС и НШКС Клосса при больших N.

2. Имеют меньшее время настройки, чем НПКС, НШКС Клосса и СНКС (при настройке нескольких соединений).

3. Работают в пачечном режиме коммутации. Этим свойством , не обладают известные НШКС и НПКС.

4. Схемы ОШО работают в неординарном режиме коммутации.

5. Настраиваются децентрализованно.

6. Состоят из двоич"ых КЭ.

Сочетание некоторых из этих качеств является уникальным и не встречается ни в каких известных КС, кроме однокаскадной кроссовой схемы, имеющей квадратичное число точек коммутации. Проведенный анализ показывает, что схемы БСЮ, ЮБСЮ и ОНСМЗ могут с успехом применяться в ГОС.

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

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

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

В заключении приводятся основные результаты исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

1. Определены новые типы схем: частично сортирующих СРСЮ,

ТСЮ, ОСЮ), обратно сортирующих (ИрСЮ, Rj.CN)), разделяющих СВрСН), ВТСЮ). Частично сортирующие схемы являются обобщение:/ известных сортирующих схем. Показано, что новые частично сортирующие схемы РСЮ, ТСЮ, ОСМ) можно получить из известиях сортирующих схем 5СЮ путем замены КЭ1 на КЭ2 СКЭЗ), КЭЗ СКЭ9), КЭ4 соответственно.

2. Исследованы методы построения обратно сортирующих схем РрСЮ (Rj.CN)). Доказано, что обратно сортирующие схе:.<ы могут быть построены из разделяющих схем ВрСЮ СВТСЮ)', а разделяющие схемы могут быть построены из схемы битонического сортировщика Бэгчера.

3. Обобщены свойства схемы битонического сортировщика Бэтчера, разработан метод децентрализованной настройки разделяющих схем.

4. Разработаны коммутационные схемы новых типов. Доказано, что новые неблокирующие в широком смысле ординарные схемы ЙССМ), работающие в пачечном режиме установления соединений с двусторонней децентрализованной настройкой, могут быть построены из частично сортирующих схем С РСЮ, ТСЮ, ОСЮ) и обратно сортирующих схем CRj.CN), Rj.CN)).

5. Доказано, что новые неблокирующие в широком смысле неординарные коммутационные схемы ОЫСЮ, работающие в пачечном режиме установления соединений с односторонней децентрализованной настройкой, могут быть получены из частично сортирующих схем СРНСЮ, ТНСЮ, Ш<СЮ) и схем типа ОСЮ.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Юибко А. Ь., Т.. Ир1ак 0. К1азШкас1а а

Ых!по1еп1е ргеро.)оуас1сЬ 51еИ шШргосезогоуусЬ росИасоуусЬ Б^етоу // КуЬегпеИка а 1пГогтаИка, 14 зутрогШт БКЗ рП БАУ.-2иЬегес, 1988. Р.296-300.

¿. Дудко А. Л., Совиш Ф. Проблемы коммуникации в современных вычислительных системах // Vedeckotechnicka konference. - Brno, .1988. Р. 33-34.

3. Дудко А.Л. Неблокирующие коммутационные схемы с децентрализованной настройкой // ЭВМ новых поколений и перспективы их использования в народном хозяйстве. - М. , 1989. С. 143-153.

4. Дудко А. Я.- Неблокирующие коммутационные схемы. - М.: ВЦ АН СССР, 1990. 68 с.

5. Глухи Л. , Дудко А. Л., Цибак Л. Специальный двухмикро-процессорный блок-ячейка для построения мультипроцессорных систем // Системы обработки знаний и изображений. Докл. конф. по комплексным научным проектам КНП-1 и КНП-2. - Чехословакия, Смоленице, 1983. С. 77-80.

6. Дудко А.Л. Неблокирующие коммутационные схемы. Отчет. -Братислава: Международная Базовая Лаборатория по Искусственному Интеллекту при ИТК САН, 1988. 110 с.

Ье<нф |ф»я МНИ, Краоюк» »армкниа», П