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

/г- U h J

Мюяетврстм laja;, sacattщчрхш я твхяивсм! пелмтжк* > PaeertcK» мм . ..

Тагаарвгскшараднотехнжчвскж* *но«*ту* В«Д. Калшквм

На правах рукяпжсн

BITICKA Hùual Кшпп

Щ 681*3.01(02)

ОСНОВЫ ЯОСТРОШЯ К ЛГРАВХВНЖЯ КАСКАДНЮИ СИСТЕМ« HBOJOtHAPHOa КОММУТАЩИ В ЙНОГОПРОЦВСйОРНЫХ вычжаятккных ИАОНАХ

/ •

Спецжыьиостъ: 05.13.13 - вычкслштмышв киты.

комплексы, сжстемы мсвтм"

жкесвртац»* на соксканя*. ученее степени , ' доктора твхничвсхк наук .

Таганрог - 1992

Работа выполнена на кафедре "Прикладной математики и вычислительной техники" Днепродзержинском индустриального института имени М.И.Арсеничева

Официальные оппоненты:

доктор технических наук, профессор Додонов А.Г.

член-коррзспондент РАЕН, доктор технических наук, профессор Топольский Н.Г. -

доктор технических наук, профессор Кравченко П.П.

Ведущее предприятие: Институт проблем управления, г.Мое; Защита диссертации состоится

..¿у» ¿>•9 ¿992г. •

М*

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

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

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

Автореферат разослан " " & В 1992г.

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

(СУ/^.; '»сННАЯ ИМ Б >I /и.' ! ¿ь Д

^ксг-^таачВ

•)БЗАЯ ХАРАКТЕРИСТИКА РАБОТЫ

А к i у я л ь н о с : ь ? е м ы. Создание мощных вычисли-¡льных средств с параллельными принципами обработки потоков шных коордкнадьчо зависит от эффективной организации э них )ммутаиионных структур. Последние а своей развитии претерпели [д изменений: первоначальная матричная организация структур (внила.-ъ структурами с более сложными связями; иерархическими !Тодаи1-, взращивания их емкости. Исследование в последнее вре-1 коммутационных структур со сложными связями (гиперкуб, онегз-зти, тасовщик с обменом,флипп-сети и т.д.) показали перспок-иность йх использования в пара.": л ель них 01ЗМ с большим числом зоцсссоров и блон.оз памяти. Однако данные структуры из-за 6-.о-*руемостн связей при одновременной работе большого числа вы-юлителей резко усложняют и удлиняет процессы управления, сг-шичиваст универсальность параллельных вычислительных ерэдетз, 1ижавт роль аппаратных средств при распараллеливании отобра-1емых алгоритмов в многопроцессорных 23Н (МЭВМ).

Дальнейшее развитие параллельных-вычислительных систем я дстем управления производственными процессами в народном хс-пчетве долхно быть неразрывно связано с развитием з них с.юз-коммутационных структур, распредёлявцих одновременно боль-потоки информации по неблокируемым или по непересехаоцккся гналам. Организация в данных структурах не один арных или ве'твя-кхся путей движения информации, т.е. от лвбогс процессора г. ^скольким, приобретает ваяное значение при отображении в н;;о-эпроцессорных ЭВМ параллельных вычислительных алгоритмов, ^ги гом репение проблемы создания оптимальных структур неоди;;1рной эимутацин позволит з моаных ЗБИ увеличить предельное число апаллельно и независимо работающих процессоров.

Следует отметить, сложность решения данной проблемы в ^чнслнтельноЯ технике ранее приводила к тону, что з теории и а практике наибольшее распространение получали методы синтеза труктур неодинарноЯ коммутации и их управления с ограниченны-и функциональными к '¿скбкиатеркийа эозчо*"лстями. Данные огра-ичения балн превде зеего направлены на уменьшение числа связей еаду процессорами, исследовательным характером организация зязей между процессорами, длительным процессом настройки кана-

лов. 3 свов очередь, разрабатываемые и многопроцес-

сорное 1 , имея в своем составе упрощенные коммутационные с-оу ~:уры, в большей степени были ориентированы на решение узкого >руга задач. Поэтому в них не требовалась параллельная настройка групповых каналов в процессе выполнения вычислительных оперч„ий, т;к как смена программ происходила редко, а скорость их предварительной настройки не влияла на производительность систем з целом. Ряд вопросов, связанных.с построением оптимальных коммутационных структур в подобного типа вычислительных системах, и методов децентрализованного управления в них по автоматической реализации одиночных соединения, согласно заранее за- ' данной программы, .нами свое отражение в работах отечественных и зарубежных ученых.

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

Если к этому учесть, что в мощных вычислительных системах непрерывно увеличивается число параллельно работающих процессоров, эы целительных ячеек и блоков памяти, а их техническая реализация неразрывно связана с внедрением больвнх и сверхбольвих интегральных схем (БИС й СБИС), то проблема синтеза неблокирув-екх программируемых структур неодинарной коммутации для распараллеливания обработки всевозможных граф-схем алгоритмов в МЗВМ является олной из центральных проблем. Таким образом, можно сделать в*вод о том, что назрела важная необходимость в решении научной проблемы, имеввей народно-хозяйственное значение, а именно, проблемы разработки основ теории оптимального построение и управления программируемых структур неодинарной коммутации пр| создании многопроцессорных систем с предельным числом параллельно связанных и работавших процессоров, определяемых десятками и :ст«ями тысяч элементов в структурах, а также с универсальными

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

Диссертация классифицируется'как теоретическое обобщение я ювенив крупной научно-техническое: проблемы по созданив оптимально многокаскадных устройств параллельное ■ неодинарной коммута-ю« программируемых каналов в новых классах моцных вычислительных !кстем с параллельной трансляцией я универсальной архитектурой ия, обработки информации. в виде графов или семантических сетей.

Цел ь в . и с с л е д о в а/н и я является разработка «етодов структурного синтеза сетей н схем с ограниченным числом каскадов для неодинарной'коммутации,- обеспечивавяих при этом распараллеливание процессов управления, неблокяруемость связей :ри пространственно« и пространственно-временном распределении ютоков данных между десятками и сотнями тысячами процессорами и блоками памяти в мощных вычислительных системах и содержащих расход оборудования, соизмеримого с теоретическим минимумом; создание- аппаратных средств на основе БИС и СБИС для оптимальной реализации структурно-сложных пространственных и пространственно- . временных устройств коммутации при параллельном поиске я фиксации неблокарувщих,групповых каналов в темпе выполнения вычислительных операций многопроцессорных ЭВИ. " ' ,

6 диссертации разрабатывается, исследуется и задияавтея сле-дуоцне основные научный положения:

- методы синтеза ма^окаскадных схем неодинарной коммутации, обеспечивавших па(>аллельные и яеблокирувние связи в универсальных моделях многопроцессорных ЭВИ при потоковой обработке информация, представляемой в виде графов алгоритмов;

- алгоритмы дискретной оптимизации параметров синтезируемых каскадных схем неодинарной коммутации и на его основе инженерная методика выбора оптимальных структур коммутаторов для 14ЭВМ й предельным числом 2*^ +-2^ процессоров в них;

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

- методы синтеза временных п пространственно-временных коммутационных устройств МЗЗЦ с асинхронными принципами передачи данных и обработкой информации ¿ каналах;

- алгоритмы работы, устройства и структуры параллельных вычислительных и транспьзтерных систем, построенных на:основе не- •

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

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

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

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

Принципиальный вклад в развитие устройстз параллсяиисЕ: и неодинарной коммутации, высокопроизводительных МЭВМ и сметем управления с их примененном составляют:

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

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

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

процессоров в универсальных архитектурах вычислительных сис-

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

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

сравнение с прототипами увеличение быстродействия и помехо-тойчивости в.1,5 раза;

- усовершенствованные методы и устройства децентрализованно управления в многокаскадных коммутационных схемах, в кото-х достигается по сравнение с прототипами повииение скорости иска и фиксации каналов в 2-2,5 раза;

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

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

> раза, обеспечивается уменьвение задержек и времени настройки

в 2C_I раз, где С - 2,3,...;

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

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

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

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

ш настройкой в процесса выполнения параллельны* ветаел уемых градов задач в вычислительных системах, прячем сксресть |Тобрадения задач в 1,5» 2 раза выше, чем в сун'зствуяв'лх много-:роцессорных структурах.

Синтезированы сортирувяие коннутационные элементы, на оско-1в которых продложена схема транспьвтера, осуществлена р&зраСстиг шогопроцессорных гранспьотерных систем с иерархическими припылами наращивания и в них реализованы алгоритмы динамического 1Тобрапония программ реааемых задач. Разработанные аппаратное :редства в сочетании со специально созданным программным обеспа-[ением для распараллеливания алгоритмов позволяет на порядок ус-:орнть и упростить процессы параллельного программирования, сая-(анных с размещением н выполнением задач на многомодульных вы-[ислнтельных системах.

■ Впервые разработаны и отмакетированы многопроцессорные ует-юйства формирования н анализа семантических сетей, в которых ¡одеряатся динамические многокаскадные коммутационные сети, покроенные на основе логических модулей, обладавших свойстзс* ав-гоматичоски исклвчать блокировочные состояния. Поэтому при уменьшении з усеченных сетях числа каскадов приблизительно в 2 раза, юстигаптся почти такка но комбинаторные свойства, как и в уо-ювно неблокируваих сетях разовой коммутации. Одновременно о этим в продлокенных сетях на специально разработанных логическ/и <одулях обеспечивается независимая н параллельная групповая на-:тройка связей, а также совмецавтся мультипроцессорные и >.'у.п«г>-трограмнные формы обработки графов семантических сетей.

' В диссертационной работе показано, что разработанные коммутационные устройства целесообразно использовать также в миого-троцессорнах вычислительных структурах типа цифровых олнорогнах :еток, орнонтнрованных на ревение задач математической физики, ¡'правление давлением в роботогвхнических комплексах, прогнозирование нагрева, автоматический контроль и диагностику, сэтях сек-зг-ЗЗН» Зяояаннэ в ких автономных коммутационных устройств поз-золяет повысить для всей системы надежность п ьачестпс, гон'^сть и производительность, обеспечивает адаптации структурно-сложних устройств при возникновении аварийных ситуаций.

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

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

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

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

Результаты диссертации внедрены в организациях Р-бб^й и АП41 при создании микросхемы волнового коммутатора и цифровой пространственно-временной коммутационной системы.в НПО ''Красная Заря" при создании опытного образца системы телеобработки и коммутации (СТОК); в научно-исследовательском институте микроэлектронных вычислительных структур Таганрогского радиотехнического института при создании коммутационной системы в параллельном процессоре ЕС 2703 и при выполнении гос-бвджетной темы "Разработать теорив однородных вычислительных и хоммутирувбих структур". Были разработаны, изготовлены и в лабораторных условиях испытаны макеты многокаскадных коммутационных

груктур. для ЭВМ о интерпретацией языков высокого уровня и для 1теллектуальной решавшей системы. Испытание макетов доказало эзможность параллельного и группового поиска и фиксации каналсз параллель*.::х вычислительных системах, показало принципиальнуз эавильность принятых решений посозданио многокаскадных струк-грс децентрализованными принципами управления в высокопроизво-чтельных вычислительных системах. Созданные макеты внедрены у 1казчнков, т.е. в Институте кибернетики АН УССР и межотраслевой 1учном центре технологии программирования, г. Киев. Эффектив-зсть использования н внедрения результатов подтверждается соот-этствувдймн актами, представленными в приложении.

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

Апробация работы. Основные положения диссер-ационной работы докладывались и обсуждались на I Зсесонзной ежференцми "Однородные вычислительные среды н систолические груктуры" (г.Львов, апрель 1990г.), I Всесоозной околе-семинаре Современное состояние теории и разработки программного обеспечо-ия СУ с ЭВМ" (Москва-Самарканд, октябрь 1990г.), на У1 Зсесоиз-вй нколе-семинаре "Распараллеливание обработки информации" [•.Львов, май 1987г.), на ХП семинаре по однородным вычислитель-т средам и систолическим структурам (гЛьвов, апрель 1991г.), г Республиканской конференции "Робототехническне системы для ромынленных технологических процессов" (г.Воровиловград, сен-ибрь 1985г.), на Всесоозной конференции "Теория адаптивных сис-зм и.ее применения" (г.Ленинград, май 1983г.), на Республиканском семинаре "Преобразователи и приборы для измерения температу-а" (г. Киев, ивнь 1978г.), на республиканской конференции "Эр-атическне системы,- передача цифровой информации и микропроцес-орная техника" (г.Киев, декабрь 1982г.), на 1У Всесовзнон сове-по «ифопмя111ионным сетям (ВСЙС-4) (г.Москва, ноябрь 1981г.), а У междунарбдном семинаре "Прикладные аспекты теории автома-ов1" (г.Варна, май 1979г.), на УШ международной конференции Система, допускавцие неисправности, н диагностика" (г.Катовнцы, 1$3>. '85, 1985г.)..

Публикации по работе. По материалам диссертационной работы опубликовано 46 печатных работ, среди которы 22 авторских свидетельства.

Структура раболы. Диссертация сост(.лт из введения, вести разделов и заключения на 233 страницах маиинописног текста, иллюстрируется рисунками и таблицами на 127 страницах. Имеется список литературы 211 наименования на 22 страницах и при ложение на 98 страницах. Общий объем диссертации 505 с.

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

В первом разделе диссертации анализируются нарациваемые структуры и характеристики современных систем электронной коммутации в параллельных SSM, определяются параметр! для сравнительного анализа и выдвигаются основные критерии оптимизации систем неодинарной коммутации при реализации их на БИС и СБИС, доказыва ется необходимость введения в параллельные модели многопроцессор них ЭВМ систем неодинарной коммутации с децентрализованными и групповыми принципами настройки каналов, формулируются задачи диссертационной работы.

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

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

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

В четвертом разделе разрабатывается и ксследуптся аягорит-ы и на их основе децентрализованные устройства управления мно-окаскадными коммутационными сетяин (МКС), отличавшиеся от нз-естных ускоренными процессами настройки как одиночных, так и ■рупповых каналов в' дкнамкко выполнения вычислитольних операций I ДЗС, автоматическим истечением блокировочных состояний при ¡еализацка произвольных перестановок и динамическим обнаруженной и исправлением сбоев, доказывается теорема для формирования :онтрольннх сунн, позволявших обнаруживать и исправлять на МКС ¡•разовый ревкиом установления путей одиночные и двойные сбоя, ¡интезируется система исправления сбоев в ККС, построенная на ;пецмальннх двакчных коммутаторах.

3 пятом разделе анализируется.вопросы, связанные с организацией параллельных неблокпрувщих коммутационных структур, наиболее приспособленных к параллельному отобрааошга графов резаеиих аадач а темпе трансляции программ в ПВС, нсслвдуптся параллоль-ше методы неодикаркой настройки в неблоккруп^их сортярувцкх регистровых структурах, моделирувцих сети Каутца, Бэтчера, на основе реализации нзодинарных соединений в сортнрувцнх сетях синтезируется регистровая коммутационный элемент (РКЗ), который расширяет функциональные вознолшостк трансцьвтеров и ячеек раз-яичннх типов однородных вычислительных сред (ОЗС), обеспечивая в них аатонатнческуп трассировку каналов, предлагается для >рор-мирования и анализа графов нодель ПВС, з основу которой положена блокирувщая'динамическал дельта-сеть, т.п. ЛМКС. для котопой скнтезируотся коммутационные модули (КМ), различными ояоеобаки автоматически исключавшие блокировочные состояния при го/ппозом и индивидуальном искании каналов.'

¡5 есстои разделе показываптся облас*к использования скнте-

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

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

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

2.1. Анализ.проблем коммутации множества процессоров . параллельных ЭВМ

Основной тенденцией в развитие электронной коммутации при создании многопроцессорных ЭВМ - это усложнение характера связ< между больикм количеством процессоров, ростом числа связей, те,' пом их реализации в процессе выполнения группы параллельных во вей алгоритмов, маршрутизацией каналов от больного числа процо соров к блокам памяти, возможность нх пересечения. Поэтому от способов реализации программ соединений в системе коммутации з вксят оо комбинаторные свойства (полнедоступность, неблокируе-мость, сложность и структурная организация схема коммутации,' скорость настройки каналов н быстродействие при передаче ннфор мацни по ним). При этом программы коммутации могут быть извест заранее, до протекания вычислительных процессов. Данный характ реализации программ коммутаций внроко известен в МЭЗМ с програ мируемой архитектурой. В связи с этим все соединения программ фиксируется и разрушается одновременно в схеме коммутации, кот рая совместно'с устройством управления работает в разовом или статическом режиме.

"^Параллельные модели МЭВМ, реализуемо непрерывную обрабоп графов потоков операндов илв потоков команд, требует в своей £ хитвктуре конвутационнхх структур (КС), в которых требуется и:

;енять соединен;:* в программе по ходу выполнения вычислительных роцессов, т.е. динамических КС, работавших, как в одиночном, так ; в пакетном или в групповой режимах. При этом программы комму-ациа в отличне от телефонии содержат не только списки для попар-:0г0.(одинарного) соединения абонентов (процессоров, блоков па-1яти, вводных-и выводных устройств), но и для неодянарных (ветвя-[ихся) связей, т.е. когда'вход КС подсоединяется к различному юдмножеству выходов. '

Характер данных связей должен отличаться устойчивостьв в те-[ение репения соответствуешь ветвей графа и обязательной реали-1ацией в данный момент, т.е. исклвчавтся блокировочные состояния. ; другой стороны, коммутационные процессы выполнявтся синхронно ! вычислительными, а это выдвигает особые требования на быстродействие при настро'йке на программы соединений. Таким образом, в !арал*ельных моделях МЭЗН эффективны неблокируваие структуры нео-(инарной коммутации, обеспечивавшие максимальное распараллеливало вычислительных процессов.

Главными критериями при их проектировании должны бить: нини-¡альные затраты на оборудование (число коммутационных элементов !КЭ),' коммутационных модулей, выполненных в виде БИС), максимальна скорость при отображении каядой программы соединений з схеме соммутацик, уменьпенце задержек в каналах связи и нх равенство по ¡лине,'обеспечение максимальной надежности з функционировании отельных блокрв и всей системы в целом.

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

з&ння каскадных КС н определить области их использования в параллельных вычислительных системах (ПВС).

2.2. Оптимальное построение многокаскадных устройств

неодинарной коммутация'при пространственном -разделение каналов

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

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

Пусть граф 6 неодинарной коммутации содержит L ( Ь *1,Я) непересекавщихся ветвящихся связей, реализацию которых требуете; выполнять независимо и параллельное Тогда простейвий способ их реализации может быть получен через группу из М/г* параллельно соединенных по JT входам многокаскадный схемам-концентраторам, каждая из которых для организации ветЕленк{5 имеет дополнительны каскад в виде отдельного коммутатора. Такой первый тип схем нео динарной коммутации является структурно избыточный, требует для своей реализации не менее, чем , , \ JL_

WgCSH)- ^ (-щткУ" ■

КЗ при г= М/И/f . Уменьшить здесь аппаратные затраты при с обладании параллелизма в настройке можно за счет переноса процессов одинарной коммутации из предпоследнего $ -го каскада в ( $ + 1)-й, совмещая в нем одинарнув коммутацию с неодинарной. В результате нетрудно построить на Jf входов н т± выходов несимметриннув трехкаскаднув базовув схему, в которой несимметричность связана с тем, что между вторым и третьим каскадом hci перемешивания межкаскадных связей, так как последний каскад всегда представляет один коммутатор. Объединяя параллельно по J входам МJmi базовых схем, пплучин второй тип неблокирующих структур с Я входами и М выходами, расход оборудования в коте рых снижается. Так при S я 3 он составляет

= -fñz)> при S = 5 -

,„i , v .., vv ГТЬ . mz ^ rrtz гпч \

яализ соотношений показал, что на практике имеет смысл исполь-овать такие схемы с числом каскадов не более семи. Особенннойтьв много типа схем является то, чуо в них на ( S -I)- каскада* эстаточно выполнять режим свободного искания IP, а на последней ,-том каскаде - режим индивидуального искания I I. ОтсвДа был элучен алгоритм распараллеливания управления в данных схемах.

Если проанализировать граф 6, то нетрудно убедиться в том, го он содержит совокупность прадеревьев G¿ (Ej ), где B¿ ■ i . При образовании лвбого I -гэ прадерева Si (E-t ) с (1<К -N) дугами из верпины окажутся во множестве В ров-

з (K-I) изолированных (незадействеваяных) вериин тогда и только эгда, когда Б =Е" *N. Таким образен, если использовать изоли-званные вершины В ^ , то каждое i -в прадерево ножно пред-гавить простой цепьп, у которой начальная вераина, проме-гточными служат вераины из множества В ¡f и В , а конечной зляется последняя веримна из В'{ . Длй КС считаем В* - множество <одов, а Е" - множество выходов. С учетом этого лвбой граф £ зи равенстве входов и выходов представляется двудольным графом

, нмевннм у каждой вершины два ребра. Следовательно его :егда можно разложить ив два подграфа Cj к G2 , соответствувцио унарной коммутации. Приводится алгоритм такого представления, гс^да формулируется следувщал теорема; если многокаскадная разо-1Я схема Ур(т»1, п. , г* ) содержит m » 2(Ц подсхем одинарной ¡ммутации, то она является неблокируввей для неодинарной разо-)й коммутации.

Данный тип схем требует КЗ WH (S)= ^ ni*~

■ZJf /Оч*Пг." fli-i^-»-'^", где £ ■=

-I, минимум КЗ

иС"с*>-г+- л«'™ *

Используя метод отобракення сопряженных ребер графа, на данных схемах, ножно добиться сокращения^ расхода Kü до

«(3J\T S n¿ + Ztfz/(nrn2... ГЦ., +

_ t=i • - „

Ветвления возможно представлять в виде простои цепочки, ис-

¡льзуя неразделенные входы do множестве Б . ^Гогда дополняя схо-■ разовой коммутации схсмой с неразделенными полисами, можно

построить следувцэго типа неблокирующие многокаскадное сети.' Наименьшего числа каскадов среди этих сетей требуют сети с петлевыми соединениями. Поэтому объединяя параллельно по Я входам М/г4 оаэовых неблокирующих подсхем с петлевыми соединениями построим обобщенную КС с Я входами и Н выходами. Данный тип схе*

.1

требует КЗ -мин

при

S+í , ,/(5+<

М

ОПТ П. ~ с

т»-

Организуя простые цепочки одновременно на множестве незадей ствованных входов е' и неразделенных выходов Е" , синтезируется тип КС с комбинированным методом реализации неблокирующих соеди-

\Л/

мин конб

(з) = (6^ Соо^м -гя^+х

ноний, в которых число КЗ.

Слздуоний тип КС выбирается всегда с четным числом каскадов так как позволяет реализовать параллельный адресный поиск каналов. Для исключения блокировочных состояний^по правилу Бенеса объединяются параллельно по входам и выходам две подсхемы типа "ось", через которые реализуются два взаимно дополняющие друг друга группы перестановок, обеспечивавшие в общем случае Л"! перестановок. Расход числа КЭ в них находится как W|f ( 5) ■= Б2" • Л/" и при Ь°лТ - ^г^п. Я ■

Щ Сопоставление его с. затратами в .

классических схемах разовой коммутации указывает на то, что при ^Г^-113 выгоднее применять четырехкаскадные схемы по сравненнз < пятнкаскадными. Это подтверждается и для больного числа каскадо;

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

затрат w^! (г++о=/г(г^+<рг11+а1)+^ ^ +

пГпг ... п + , П1 = ^ = ,

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

Для КС в ЛВС требуется находить не глобальный оптьнуц для араметров , и £ разбиения..«ГГ н И из безусловной оп-имизации, а локальный с учетом дискретного характера выбираемых араметров. Поэтому задача сводится к нахождение вектора »г* ~ С^Т» ^-г,-.., П-Л") миннинзирувчого функция цели -асход КЗ ( V?') при выполнении ограничений ( М I = Г1| ЕВ=1Д ), где 1> - декретное множество

елых положительных чисел, кратных 2* (к с1,8), а - функции ида «АГ» З^ГТ П-1 ¿.О. Получены алгоритмы дискретной птимизации параметров синтезированных КС, среди алгоритмов наи-ольвей эффективность» отличаются алгоритмы на основе метода ектора спада, моделирование которых на ЭВМ позволило найти декретные оптимальные параметр». Программное обеспечение и таб-ицы параметров приведены в приложении, из которых следует, что 1асход оборудования сокращается в десятки ра'з, по сравнение с . атричнымп структурами, при- этом этот вышгрыи растет с увеляче-[ием Я . Для небольоих значений Л", не более 256, предпочтительнее труктуры первых двух типов, полностьв распараллеливаяцие процесс [астройки. С роотом ¿Г до 4096 предпочтительнее схемы третьего 'ипа,*а при ^О 4096 целесообразно применять схемы с петлевыми и ;омбнннрованнымн соединениями, с ограниченным числом ветвле-[иа в структурах и с четким числом каскадов при наращивании-

2.3. Развитие структур цифровых устройств неодинарной коммутации при временном уплотнении каналов

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

ется соотношениями: а) при анализе одного приращения, каждого

И данных соотношениях прираненкя форикрувтся при коммутации приращений и одноразрядных данных Хц^ , Ху-м получаемых при решении в ПйС системы уравнений Шеннона, на оснований которой в какдок столбце КС необходимо выполнять одновременно с коммутацией'н вычисление суммы приращений. Поэтому предлагается совместить эти два процесса в модулях структуры и в результате синтезировать на основе регистровых ячеек со сквозным суммированием коммутируемых данных новые параллельные вычислительные устройства: запоминавшее устройство неодинарной коммутации, электронный искатель-счетчик многоканальный, арифметико-логическое устройство для многооперандной обработки данных и цифре вую пространственно-врекеннув КС. Основной особенностью данных устройств является выигрыш в быстродействии при коммутации неод* ¡¡арных соединений в среднем 2*'» раза, возмонностьв одновременной н параллельной обработкой данных и их коммутации.

В пространственно-временных КС за счет сведения неодкнарно! коммутации к одинарной удалось использовать классические многокаскадные структуры с параметрами в каскадах, которые присущи обычным разовой и одинарной коммутации. Для этого в них используется метод перепрограммирования МКС, на основе которого предлагается соответствусщки алгоритм управления, обоспечквавккй пе рехс от реализации програ>;« произвольных неодинарких соедкнени к группе программ одинарных соединений для упорядоченных в прос ранстве входов процессоров, кехду которыми ветвления осуцествля втея простым замыканием близлежащих точек или КЭ. Показана его реализация з -перепрограккируемых ИБС, где 0^=2^ -I, а ^-число входов в каждый процессор. Данный подход предполагает мне гократнув передачу данных через промежуточные процессоры, пражд чу« за .¡иклов они достигнут требуемых процессоров.. Поэтому ^ссктйнное применение данного алгоритма на МКС в ИБС целеооой• раг-.;с тог;,а, е ;ли слова или пакеты передаваемых данных кестко

£ Уи

двух подключаемых каналов

где

1=1 ¿-1 1г

иксировгны и ограниченной длины.

2Л. Управление и контроль цифровыми устройствами

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

В разработке предлагаемых децентрализованных устройств уп-гвлепия (ДУУ) структурно-сложныни системами неодинарной коммута-ш (НК) исследуется динамический принцип прокладки параллельных гблокирувщих путей, выполнение которых при потоковой обработко эафов в ПВС должно вестись \рлько со стороны входов и выходов зоцессоров и в темпе выполнения вычислительных.процессов. Поэто-г коммутационные модули (КМ), из которых нараднвавт МКС должки »держать ДУУ, учитывавшие даннув специфику и сложность данных ¡тройств не должна зависеть от числа нарадйваекых каскадов. С 1етом этого разрабатывавтся алгоритмы"та устройства управления, в >торых различным образом формируется прадоревья соединительных 'тзП (ПСП), т.е. все возможные пути нз корневой верзины к сводным выходам. Синтезируется КМо..учетом одностороннего и двух- -?оро'ннего. поиска ПСП, причем 'арбитраж для альтернативных путей КМ ведется автоматически н в связи с этим в отличие от изаест-ix до настояавго времени КМ удается полностьв всклочить знегигч |равление по каскадам,,увеличить быстродействие в формирований !П и заданного пути в два раза.

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

Динамический принцип настройки удалось распространить и на |упповой параллельный поиск каналов, установление которых во-'тсл в свободном режиме искания,- как на матричных структурах, х а на каскадних. Данная ситуация складывается з ПВС при захза-освобо:*д&ищегося рссурса,'например прд создании коммутационных

распределителей ресурсов (КРР) менду группой свободных процессоров и освчбодивыейся группой Запоминавших устройств (ЗУ). Учитывая их функциональную информационную однородность, устанавливается последовательный приоритет между ними (например, сверху вниз или слева направо), который аналогичным образом переносится на матрицу КЗ. Таким образом, за счет распространения блокирующих сигналов по строкам и столбцам КЗ матрицы от корневых вершин, одновременно строятся все JV ПСП и JT независимых каналов. В таком волновом КРР, например при v/V обшее время фиксации групповых каналов не превышает четырех тактов при настройке как одного, так и сотен каналов одновременно.

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

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

ля программ в МКС моеот прн динамическом контроле обнаруживать азмененнв контрольных сумм одиночные и двойные сбои и восста-анвать их в нарушенных коммутаторах перед каждой передачей [>рчаиии по каналам.

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

Скорость и динамика параллельного отображения графов рэпаемой ачи на ЛВС зависит от принципов организации в них КС, в качест-которых при реиении задач искусственного интеллекта или пра реки задач оптимизации на графах могут быть регистровые КС (РКС), испьвтерные сети (1С) и однородные вычислительные) среды (ОВС) с мутацией элементов на плоскости. В них предлагаемые ДУУ реали-г алгоритмы параллельной прокладки неодинарных неблокирувщих цинений по автоматически формируемым неодинарным подстановкам роцессе трансляции программ. В многопроцессорной ТС (МТС) или содержится матрица регистровых КЗ (РКЭ), множество полисов В эрой соединены с М микропроцессорами (МП), участвувдими в парадной организации каналов в соответствии с реализуемым графом 1НТйческои сети (СС). При этом множество МП разбивается на два вые части с ЛГ=М/2, или Е^Б и Е1' и ^^ = |Б"| "Я. Всегда в Б1 есть подмножества х^ н Б-^ , EJ и Б2 , которые взаимно перпен-¡глярны друг другу, т.е. Каждый МП хранит

граммы отдельных ветвей, отображаемых параллельно в МТС. При к каждая ветвь представляет собой поток команд и операндов, дви-

и _ гт11 11 х- с- "

не которых з вершину е^ Е или е ^ <= г. приводит к <ированив новых операндов, записываемых в МП. Поэтому.ДУУ каж-о РКЭ для организации ветвлений сравнивает адреса в командах, между собой, так и проверяет их на совпадёние с адресом Х^ 1бца, в котором расположен данный элемент. Таким образом, на х сортируемых сетях У.Каутца реализуется нёблокирувцие неоди-иые подстановки. После этого сортирувдие КЗ (СКЭ), соДержадие ¡си ветвления по командам обработки настраивает обрабатывающие центы в среде на соответствувщие операции. Время настройки про-ционально (2<?Г-1)' ^од^- тактам.

При увеличении ^ в МТС на основе матричных неодинарных сорти-вих сотэй возрастает длины путай при настройке и увеличивается

¿k

аппаратные затраты по квадратичной зависимости. Поэтску исследуются различные варианту построения многокаскадных сортирующих и динамических структур для потоковой настройки к обработки GC. Синтезируется для них структура асинхронного транспьютера. В качестве первого варианта исследуется сеть наращивания СКЭ по принципу сортирующих сетей Батчера, в которой сокращается расход оборудования при сохранении организации неблокирующей автоматическо{ настройки на графи НК, уменьиается количество проходов при отображении графов слогных СС. Во втором варианте предлагается многокаскадная ТС, построенная в виде МКС первего типа и описанная в разделе 2, в которой только последний каскад строится из транспы торов в виде сетей Каутца или сетей Батчера. Тогда появляется возмоеность копирования данных и сокрацения расхода транспьютера] в последнем каскаде за счет увеличения сложности КС в предварительных каскадах. Следовательно, изменяя параметры в каскадах, можно находить минимум стоимости обоего оборудования при заданны: временных ограничениях на репение конкретного класса задач.

Показано, что для формирования и анализа СС в ПЗС при больших Я между МП, И модулями оперативной памяти (ОП) и К устройст вами ввода и вывода (УВВ) эффективно вводить динамические (£+1) каскадные дельта-сети (ДМКС), где , а С=2К, к=1,2,..

причем "С" размер КМ в ДМКС. В данной ПВО распараллеливание вычислительных процессов при обработке СС ведется одновременно в горизонтальном и вертикальном направлениях через ДМКС, в которой автоматически исключаются блокировочные состояния как через общи узлы фиксации и изменения конфликтов (УФИК), так и в КМ по море прокладки <Н" независимых путей. Для этого предлагаются программн аппаратное методы исовчэния блокировочных состояний;

а) путем программного изменения приоритетов для блокируемых каналов в ДМКС, наличие в КМ блоков приоритетного выбора;

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

в) путем многократного автоматического прохода или построе» путей через ДМКС с учетом временного прерывания или разрувзния предыдущих путей, которые блокировали последующие.

В последнем случав поочередно, чередуя процессы сборки u p¡ боркк лутей в специально разработанных КМ, мы всегда дсбъемся ti что ir каждой временном такте выполнится любая подстановка. При

том при "удачной подстановке"длина сеанса связи для каждого МП удет максимальной и равва всем подтактам во временном такте, ри "худших" подстановках минимальная длина связи на временном акте для МП будет равна одному подтакту.Поэтоиу в среднем при акой организации У$ИК и КМ можно дебитьсяповыивния производи-ельностк в 1,5 раза по сравнения с блокируемыми ДМКС.

'2.6. Создание высокопроизводительных вычислительных оистеи и комплексов управления на основе программируемых коммутационных структур

В разделе разрабатывайтся оптимальные программируемые КС я зтоды динамического управления ими при проектировании конкретных ¿числительных систем и комплексов для решения задач народного »зяйства, приводятся экспериментальные исследования.

Прежде всего показывается, что от организации построение ПКС матричных процессорах типа цифровых однородных сеток (ЦОС) эа-(спт их вычислительная мощность, точность решения задачи, аппа-1турные затрата. Для создания универсальных ДОС из \tz элементарных ЦОС.(5Ц0С), т.е. прямоугольной наращиваемой ЦОС размером ' т х m) , где /гг- - число узловых процессоров1 (УП), требует-t ß -каскадная МКС,, в которой потребуется расход КЗ .

Wa = $m(j: + i) У. Ограничивая число конфигураций из

10С, создается-линейные и пдоские ЦОС, разрабатывается.в иатрич->м процессоре БС-2703 модули КС, с помощь» которах иаращиваится пличные архитектуры, осуществляется процесс резервирования УЛ. шолнены экспериментальные исследования макетов КС для матрично->:процессора БС-2703 за'счет внедрения БИС КМ 1509 КП1, создано ¡тройство диагностирования системы коммутации, которое внедрено НИИ МВС при ТРТИ.

Наращиваемые архитектуры пространственных КС (ПКС) с динами-юкими и параллельными принципами управления анализируется для •здания бортовых МЭВМ.в которых между множеством МЛ и комплектов l4.it™ (КП) гсдстс,- иисгокрагиов дублирование яычислител5к0х про-iccob. Разработан модуль ПКС, который позволяет увеличивать как 1зрядность коммутируемых слов, так и число подключаемых МП и КП, [итывая при этом между ними.приоритет их подключения. Выполнена химизация количества его выводов при реализации в *иде БИС,

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

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

Исследованы возможности ПКС при создании систем параллельного управления технологическими процессами при нагревании слитков, повисавшие в них точность измерений; обеспечивавцив параллельный контроль и прогноз нагрева. Осуществлено внедрение ДКС в вычислительную сеть для автоматизации рабочих мест и р'обототи-зированный комплекс для диагностики печатных плат, т.е. РТК "КОДИАК" на НПО "Злектронмая", г.Киев. Экспериментальные исследования по создание новых микросхем для МКС послужили основой для создания на ПО "Электроника", г.Воронеж микросхемы волновой коммутатора, выполненной по п -МОП технологии в 46-выводном корпусе. Испытания данной микросхемы подтвердили возможность нара-циваиия КС с произвольным числом каскадов и полнув децентрализации устройств управления, реализувяие предложенные алгоритмы встречного поиска путей в МКС.

И. ОСНОВННВ РЕЗУЛЬТАТЫ РАБОТЫ

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

При решении основной проблема получены следуааио новые на-ные результаты.

I. Разработаны.исходные положения, которые легли в основу аоння задачи оптимизации: на основе механизмов вызова потоков ерандов и команд выбраны универсальные структуры параллельны* числительных систем со схемами неодинарной коммутации, оПти-льное построение которых определяет в них предельно допустимое ело -Я" процессоров, комплектов памяти, устройств ввода-вывода, епень ргепарал/елигания вычислительных процессов, их планирог икз и йиструс трансляции информации, предетавляемуп в виде проводках гра^-с;<еи (семантических сетей) или совокупности грату. неодинарной хониутпц:<и; доказана целесообразность разработки и п'сльежх -Я" в П!ЗС методов синтеза многокаскадных коммутацион-% суем, сетей, т,а. ИКС с полностье нсблокируеяыми ироцесса.ми строя км на неедина?ньго соединения и определены для них оснозн;ю ичерми олткиизацй*, сзззг.ккие не только с минимизацией сбзего ела аппаратуримя затрат, но и децентрализацией параллельних, рэдлельнб-гослэдозатгдьных и неблокирующих алгоритмов упряялз-я, сокращения осцого необходимого числа каскадов для отобраяа-я псеьозмо-дь«?. градом неодинарной коммутации, уменьшения чу.сла скадоа для образгванмя точек ветвления и вирокого внедрения БИС , СБИС для техническая реализации. ИКС. ■ 2.Впервые разрзботаны катоды структурного синтеза.малокаскад-

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

неблокирующего отображения произвольных графов при минимальном

числе каскадов для образования точек ветвления. При этом показан!

возможность распараллеливания в данных ИКС алгоритмов управления

установлением ветвящихся соединений в разовом режиме. -

, 3. .Найдены оценки расхода аппаратурных затрат, в сянтезиро-

ванних МКС и выполнена для них безусловная оптимизация параметре:

с цельв нахождения функций минимального расхода коммутационного

оборудования. На основе метода вектора спада для'данных МКС раз*. * -работай универсальный алгоритм оптимизации параметров, выбираемы

из заданного множества целых положительных чисел кратных 2х(кс1, значения которых определяется технической реализацией коммутаторов МКС в виде БИС я СБИС для параллельных вычислительных систем

4. 3 результате моделирования на ЭВМ различных типов синтезированных МКС выбрана инженерная методика для проектирования устройств неодинарной коммутации в.ПВС, в которых для больяих Ж27< <- 2*°) расход оборудования соизмерим с расходом элементов в классических МКС, но при этом на&ицдотся сокращение необходимого числа каскадов в 1,5*2 раза, что упрощает и ускоряет процессы управления во столько же раз.

3. Впервые'синтезированы программируемые устройства с временной и пространственно-временной коммутацией неодинарных соединений, в которых за/счет асинхронной передачи данных удаётся : среднем сжимать объем информации в 2-4 раза и тем самым во стол ко же раз увеличивать быстродействие. Причем данный принцип эффективно совмещать с выполнением арифметических операций в комм тируемых каналах, что позволяет распараллеливать обработку данн и создавать качественно новые вычислительные устройства!; в кото рых по сравнению с прототипами увеличивается по крайней мере в 1,5 раза быстродействие и помехоустойчивость.

6. Предложен метод и алгоритм многократного перепрограымщ •в*шяя •иеодинарыых связей, позволявший в многокаскадных простра! ственно-временных КС свести неодинарные программы коммутации к программам, содержащих только одинарные соединения между процо< сораии.

7. Разработаны алгоритмы и устройства децентрализованного управления в МКС при параллельном поиске и фиксации каналов, с тезированы логические коммутационные модуля, повывагдие бистро действие в 2*2,5 раза за счет встречного установления каналов.

дрены в КМ челночные алгоритму, обеспечивающие неблокируемость азовом режиме. Все предложенные КМ защищены авторскими'свиде-ьствами.

8. Предложена методика синтеза сортирующих коммутационных |уктур с произвольной параллельной настройкой групповых я вет-1ихсд связей, позволиввая во-первых, свнтеэвровать новые сости-щие коммутационные элементы (КЭ) для наращивания из них небло-•увщих сортирующих сетей; во-вторнх, обеспечить параллельную и ■оматическую трассировку в транспьютерных и вычислительных сре-:; в третьих, разработать в внедрить алгоритм динамического рас-»алл вливания задач, обеспечивая при этом автоматическое планиро-[ие и параллельную реалнзацвю сложных графов.

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

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

При реаении основной проблемы в диссертационной работе полу-ш результаты, имеющие следующую практическую ценность: :о'здание малой серии БИС волнового коммутатора и внедрение ав-зских свидетельств в организациях 'Р-6644,- А-Х141; ¡оздание и внедрение макетов адресного и волнового двухкасхадных «мутаторов с параллельным поиском групповых каналов при разра-гкэ новых вычислительных средств в организациях - Институт ки-рнетики АН УССР и МНЦТП, ' НПО "Красная Заря"; знедрение в изделиях организации Р-6644 нового типа цифровой зстранственно-временной КС в соответствии с а.с* 1378038; :оздание и макетирование варианта КС при разработке технического эекта матричного процессора ЕС-2703 и внедрение системы контроля в НИИ МВС при Таганрогском радиотехническом институте; зоздание встроенных автоматических трассировщиков для ячеек ОЗС использование их в разработках научно-технического центра по зи-копроизводительным вычислительным системам "Интеграл", г.Львов; разработка параллельных КС для автоматизации процессов контроля "итностмкн в робототнзнреванхеи "с"плс™сс РТК "КОДЙЛК" в НПО яектронмав" .г.Киев, в распределенных вычислительных сетях для АРМ ОКБ "Радуга" при НПО "Красная Заря", создание систем управления и контроле процессов нагрева в металлургической промкяленности, пользование в учебных процессах Днепропетровского унивеоситеть

3ü

и Лнапродзержйнакого индустриального института.

Основные результаты диссертации опубликованы в работах:

1. Зитиска Н.И., Макаревич О.Ь. Программируемые коммутационные структуры.-ibbob.-1992.-213с.: Ил.

2. Витиска Н.И. Синтез программируемых координатных матриц для проектируемых вычислительных структур// Вопросы радиоэлектроники. Серия ЭВТ. НИИ ЭИР.-1935.-Вып.I.-C.9-I8.

3. Витиска Н.И. К вопросу синтеза оптимальных неблокирусд::;: схем коммутации с четным числом каскадов//..Метода" и струг™;. сиг-тем телетрафика.-М.: Наука, 1979.-С.133-136.

4. Витиска Н.К. Метод реализации неодинарной разовой коммута^ ции в многокаскадных.схемах// Многопроцессорные вычислительные структуры. Сборник научных трудов. Вып.5(Х1/).-ТРТй.1983.-С.10-12

5. Витиска Н.И. Многокаскадные системы разовой к неодинарной коммутации с произвольным числом разделенных входов и выходов// Информационные сети и их анализ.-М.: Наука, 1970.-С.1Э5-1чй.

6. Витиска Н.И. Аппаратные методы и средства для параллельно реализации программ соединений в коммутационных сетях многспроцес сорных ЭВМ.-Препринт ИППММ АН УССР, JS7-90, львов, 1990.-С.19-20.

7. Витиска H.H. Об одном способе построения систем разовой

и древовидной коммутации// Электромеханика.-Ростов Н/Д, 1977, £10 -С.ПЗО-ПЗЗ.

8. Витиска Н.И. О методе реализации неблокируваих неодинариы соединений в системах разовой коммутации// 1У-е Всзсопзное сово«а ние по сетям и коммутации. Тез. докл.-М.: Наука, 1951.-С.69.

9. Витиска Н.И. Многокаскадные системы разовой и древовидной коммутации с наличие» петлевых соединений входов и выходов// Электромеханика.-Ростов Н/Д. 1978, Ю.-С.326-332.

10. Витиска Н.И.'Развитие структуры узлов автоматической кои мутации микропроцессоров// Многопроцессорные вычислительные струк туры. Сборник научных трудов. >ВыпЛ(Х).-ТРТИ. 1979.-С.82-сэ.

11 о Витиска Н.И. Методы и структуры для реализации автоматической коммутации информационных каналов в микропроцессорных скгт мах //Конференция "Эргатические системы, передача цифровой инфср* ции и микропроцессорная техника". Тез. докл.-Киев, I9b2.-C.86.

12. Витиска Н.И., Абрамович А.И. Однородная структурная реал зация алгоритма управления в схемах разовой коммутации// Многопрс цессорные вычислительные структуры. Сборник научных трудов. Вып.1/ (ХУ1-).-Таганрог. 1985.-С.23-26.

13. Абрамович А.И., Витиска Н.И., Гармаи В.А., Вор Л.А. Об ¡правлении сбоев в схемах разовой коммутации// Материалы между-1родной конференции. "Системы, допускапщие неисправностям диаг-эстика".-ПНР. Катовицн. Материалы 1'85.-1985.-СД60-165.

14. Абрамович А.И., Витиска H.H., Гармаи В.А. Автоматизированная система исправления сбоев в схемах разовой коммутации// эдели теории телетрафика в системах связи и вычислительной тех-ике.-Н.: Наука, 1985.-С.97-102;

15'. Витиска Н.И., Витиска Э.Н. Принципы параллельного уп-авления коммутационными структурами в вычислительных системах// ногопроцессорные вычислительные структуры. Сборник научных тру-ов. Вып.IO(XIX).-Таганрог. 1988.-С.34-38.

16. Витиска H.H., Кармазина В.В., ¿мэртина Т.Г. Метод и рограммы оптимизации сетей для неодинарной коммутации информации

ОВС и многопроцессорных системах// Вопросы построения коммута-нонных сетей.-Препринт ИППНМ АН УССР, »7-90, Львов, 1990.-.16-18.

17. Витиска Н.-Я., Витиска Э.Н. Структурный синтез, анализ и араллельное программирование 08С и транспьютерных систем// 1-я/, сесоазная конференция ОВС.-Тез.докл.-Львов, I99U.-С.125-128.

18. Витиска Н.И., Зайко В.Г. Синтез и анализ мультимикропро-ессорных систем с наращиваемой и программируемой структурой// ногопроцессорные вычислительные структуры. Сборник научных тру-ов. Вып.9(ХУШ).-Таганрог. I987.-C.IA-I6.

19. Бабенко Л.К., Витиска Н.И.. Николаев И.А. Вопросы комму-ации в цифровых однородных сетках// Многопроцессорные вычисли-■еЗгьные структуры. Сборник научных трудов. Бып.З(ХП).-Таганрог. 981.-С.35-37.

20. Витиска Н.И., Витиска Э.Н. Параллельное отображение и юализация семантических сетей в многопроцессорных транспьютерных шатенах// Многопроцессорные вычислительный структуры. Сборник тучных трудов. £ып.12(ХХ1).-Таганрог. 1990.-С.¿5-28.

21. A.C. 1580377, СССР НКИ Q 06Р 13/со. Матричный распреде-1итель// Витиска Н.И.(СССР) .-J2c.ИЛ.

гг. A.C. 14У936ч, Си; г МКи « U6P 15/16. Матричный коммутатор V Витиска Н.И., Витиска 3.JI. (СССР), бс.: ИЛ.

23. A.C. 1226643, СССР ГШ НОЗК J7/04. Соединитель многокаскадной коммутационной системы / Витиска Н.И.-, Макогон Н.И. (СССР). -14с.: ИЛ.

24. A.C. 1238258, СССР №Ш Н045 Э/00. Устройство дм временной коммутации, кашиов/ Витиска Н.И., Гончаранко^ .А. (СССР).-4с.: И/.." у' '•> ' . , ■ ' ' • -

25. A.C.* 1378038, СССР МКИ 3/00. Цифровая Пространственно-временная коммутационная система /.Витяска Н.И. £.др. .

(СССР).-5с. V JU.. • ' " '

' 26. A.C. I6I9289.CCCP ККИ ä Q6P 15/40, 15/16." Устройств* ' для формирования * анализа семантических сетей / Витяска Н.И., Галаган Н.И., БриовЕ.И., Ходаковский Н.И.; (СССР).-16с.: И.

27.A.C.96II4I, СССР ЫКИ НОЗК 17/04;-Электронный же кат ел ь-разъеджнитель / ВжТжска'Н.И.. Макаревич Д.Б.илр.<СССР).-8с.:1Ц

26. А. О. 1140242, СССР НКИ НОЗК Г7/04. Электронный'соединитель двоичной системы коммутации / Витиска Н.М., Абрамович А.М.

29. A.C. 1177949, СССР МНИ-Н04К 9/00. Двоичная система комму тацин / Ви*иска Н.И., Абрамович А.И. (СССР);-10с.-. И!. .

30. A.C. 955014, СССР НКИ С 06Р- 3/04: Устройство для обмена информацией / Зитиска H.fl. и др. (СССР).-Юс.: MI. ' . "

31. A.C. 1709311. СССР №Ш С 06f 15/16. Устройство коммутаца / витиска H.I., Витиска Э.Н.- БИ М4. ГМ2.

32. A.C. 769741, СССР ИШ HÖ3K 17/&4.'1<одуль многокаскадной ''коммутационной системы /ВитискаН.И. (СССР).-бе.: И1. .

33. А.С* 758517, „СССР МНИ НЗК -17/04.-Электрйюша искател-счетчик многоканальный / Витиска Н.И. (СССР).'- 5с.: HI.

34. A.C. 743230, СССР МНИ Н040 1/52. Устройотио для временной коммутации / Витиска Н.И. {СССР).- Ас.: II.

Наряду с данными публикациями, автором вылужены ж зарегистр« ровада-в. BHTl-зднтре-6 отчётов о НИР. .. *

1ИЧНШ ВК1АД АВТ0РА В СОБМЕСТНЫЕ РАБОТЫ

Из 46 печатных работ 21 (т.е. 4 5i ).опубликоваин лично авто: ром, а в совместных работах ему принадлежат основные научные жде» и положения.

ОП ТРТИ. Зак. 40J Тир .{00 . 199g г..