Система децентрализованного обмена информацией

557358 Союз Советских Социалистических Республик(45) Дата опубликования опис М, Кл. 6 06 У 3/От Ь 96 7 15/1 сударственныи комет авета Мкниотраа ССС ео делам иэооретенийи открытий ДК 681.5:6250 (088,8) А Ф ович, 0,о и А. А. Поп кси 72) Авторы изобретения 7) Заявит 54) СИСТЕМА ДЕЦЕНТРАЛИЗОВАННОЮ ОБМЕНА ИНФОРМАЦИЕЙ а ебх на имеет недостатки: о центрального органа рограмма-диспетчер ) ичия устройств отобраяния элементов сети, ность всей системы Эта система обме наличие единственног (пульт управления, и и необходимость нал жения текущего сост что уменьшает надеж Изобретение относится к вычислительной технике и может быть использованопрн построении систем обмена информацией в многомашинных вычислительных комелексах. 5Известна система обмена сетевого тина,содержащая вычислительные машины и коммутаторы, объединенные в коммутапионнуюсеть 11. Задача управления сетью состоитв том, чтобы для различных ситуапий на тОсети каждый раз из большого количествавозможных путей между двумя машинаминайти кратчайший по отношению к количеству транзитов. В известной системе обмена эта задача решается централизованно .носнове полной информапии о состоянии всеэлементов системы,Наиболее близкой по технической сущности к предложенной системе являетсясистема децентрализованного объема информанией, содержащая вычислительные машины, соединенные с блоками аппаратногоконтроля, по числу вычислительных машинв системе, коммутаторы и устройства управления обменом, причем смежные вычислительные машины соединены информационными магистралями через соответствующиекоммутаторы 21,Недостатки известной системы децентрализованното обмена информацией состоят втом, что обмену данными между парой вычислительных машин предшествует операцияпо определению кратчайшего пути в каждомустройстве управления, участвующем в обмене данными, что снижает скорость работы системы, кроме того отказ устройства управления обменом приводит к изоляцииот системы соответствующей вычислител 1 ной машины; и соответствующий коммутатор исключается иэ коммутационной сети,образуемой всеми коммутаторами системы,а это снижает надежность системы.557358 Белью изобретения является повышение быстродействия и надежности системы обмена информацией.Дпя. этого каждое. устройство управления обменом содержич блок формирования рельефа системы и (,п - 1 ) блоков выбора направления обмена, причем входы каждого блока фоомйрования рельефа системы и пер. вые входь (,т -1) блоков выбора направления обмена соединены с соответствующими выходами блока аппаратного контроля данкой вычислительной машины, а инверсный выход блока формирования рельефа системы соединен со вторыми входами блоков выбора направления обмена смежных уст и ройств управления обменом, первые выходы каждого блока выбора направления обмена соединены управляющими шинами с соответствующими вторыми входами смежных блоков выбора направления обмена, а вторые выходы - 20 через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения. Кроме того, каждый блок выбора направления обмена содержит 26 одновибратор, вход которого подключен к выходу элемента ИЛИ, входы которого соединены с выходами первых элементов И; первые входы которых соединены через первые элементы НЕ с первыми входами бло- М ка выбора направления обмена, а вторые вхосоединены со вторыми входами блока выбора направления обмена, выход одновибратора подключен к первым входам первых элементов ИЛИ и к первым входам вторых Вб элементов ИЛИ, выходы которых подключены ко входам вторых элементов НЕ., вы.ходы которых подключены к первым входамвторых элементов И, а вторые входы вторых элементов И подключены к выходу элер 40мента ИЛИ, первые входы третьего элемента И подключены к выходам первых элементов И, а вторые входы - к выходам первыхэлементов ИЛИ, вторые входы которых подключены к выходам третьих элементов И, 45ко вторым входам вторых элементов ИЛИ ико вторым выходам блока выбора направления обмена; каждый блок формирования рельефа системы содержит одновибраторы, входы которых подкдючены ко входам блока 50формирования рельефа системы, а выходыогновибраторов через элемент ИЛИ соединены с выходом блока формирования рельь. фа системы. ИНа ф.п, 1 представлена блок" схема предложенной системы децечтрализованного обмена информацией четырех вычислительных машин; на фит, 2 - блок-схема устройства управления обменом, на фиг. 3 - схема бло4ка выбора направления, на фиг. 4 - схема блока формирования рельефа.Система децентрализованного обмена информацией четырех вычислительных машин 1 содержит по числу вычислительных машин коммутаторы 2 и устройства управления обменом 3. Обмен информацией между вычислительными машинами осуществляется по информационным магистралям 4, Устрой" ства управления обменом соединены управляющими магистралями 5. Устройства управления обменом подключены к коммутаторам 2 с помощью шин 6, по которым на коммутатор с устройства управления обменом выдаются сигналы-индикаторы кратчайших путей в системе.Каждое устройство управления обменом содержит независимо работающие блоки выбора направления 7, количество которых в каждом устройстве управления на единицу меньше числа устройств управления в системе, и блок формирования рельефа 8, Входы блока формирования рельефа и блоков выбора направления; -а о устройства управления обменом подключены к выходам соответствующего блока аппаратного контроля (на фиг. 2 не показанного). Появление сигнала Я ( 1,) на выходе бло ка аппаратного контроля 1 -го узла оз-. начает отказ информационной магистрали 4, связывающей 1 -ый узел с Р -ым узлом. (Узел системы содержит вычислительную машину, коммутатор и устройство управления обменом). Каждый блок формирования рельефа через элемент фНЕф 9 под ключен через управляющие шины 10 ко входам блоков выбора направления обмена смежных узлов, а выходы всех блоков фор мирования рельефов обьединены шиной перестроения 11. Шины 10 и 11 образуют упранляющую магистраль 5.Блок выбора направления содержит одновибратор 15, на вход которого через элементы ИЛИ 14 и элементы И 12 поступают входные сигналы (в А ( 3,1, 1 ), Ов, ( , , 2) с блоков выбора направления смежных узлов, а выход одновибратора подключен на входы первых элементов ИЛИ 17 и вторыхэлементов ИЛИ 19. Здесь 1 - индекс узла-источника или транзитного узла, 1 - ин-. декс конечного узла. Кроме того блок выбора направления содержит элементы И 16 НЕ 13, 20 и элементы И 18, выходы которых подключены ко входам соответствующих блоков выбора направления смежных узлов.Блок формированич рельефа содержит одновибраторы 21, на входы которых поступают сигналы 8 ( 1, р) с выходов блоков аппаратного контроля 23 соответствующих557358б бинформационных магистралей, и элементлей или узлов. В остаА -ьом операнди снеИЛИ 22, на выходе которого формируется. формирования рельефа кичем не отличаетсясигнал, осуществляющий формирование репье- от операции формирования рельефа 1-асс:.фов. правность узла в системе эквпвален.-а яе Работа системы управления обменом ин-исправностям всех его информационных маформацией основана на волновом принципе гистралей),поиска кратчайшего направления передачи В г-,.е дложенной са -.з .е,;ецентрал: эоинформации (метод рельефов), формирова- ванногг .бмена 1 я: :.р .:е цредус,хреноние рельефа заключается в сопоставлении одновременное (параллельное) формированиекаждому з -му узлу сети целого числа й рельефов для всех конечных узлов, Для это-.так, чтобы это число характеризовало крат- го каждое устройство управления обменомчайшее расстояние от данного-го узла разбивается на независимы;функциональна(источника информации или транзитного не связанные между собой) блоки выбораузла) до конечного узла (потребителя ин- направления обмена, число которых в каждомформации.или адресата). Конечный узел .1 1 Ь узле на единицу меньше количества узлов вполучает число, равд О, узлы, смежные с системе. Каждый узел системы может являть"конечным узлом, получает 1 и т.д, В сети ся как источником информации(узел-источсформирован 1 -рельеф, если ужам се- н ик), так и потребителем информации (коти приписаны такие числа, а сами числа, печным узлом), В каждом 1 -ом (+ 1 )называются высотами-рельефа и являют: 2 О блоке выбора направления обмена Формируют-ся указателями минимального количества ся сигйалы-индикаторы направления кратчай-узлов сети, через которые 3 -ый узел свя- щего пути иэ данпого 1 =го узла в-ыйзан с конечным узлом. В многополюсной конечный узел. Из этих сигналов формиротсети для каждого конечного узла формиру- ся управляющие сигналы (стробы) крммутатоется свой рельеф; число рельефов равйо ко ра, Блоки выбора направления обмена смежличеству конечных узлов в сети. Если для ных узлов постоянно обмениваются по дупЮабого 1 -го узла известны высоты смеж лексным управляющим шинам информациейных узлов всех д рельефов, то данную ин- о высотах рельефа, Обьем информации о выформацию можно представить в виде матри- сотах рельефа уменьшен до одного бита, этоцы Ф (1,ф) Строки матрицы имеют индексы ЗО достигается за счет направленного движе 3 Ф 1 ( 3 =1,2, и ), совпадающие с ння фронта волны от центра - конечного узланомерами конечных узлов; столбцы М(1,Ди за счет выравнивания скоростей движенияимеют индексы К (К = 1,2, р ), соот- фронта вбайы при движении фронта волны поветствующие номерам ветвей, связывающих различным управляющим шинам. (Под фрон 1 ый узел со смежными узлами; зле-том волны понимается множество узлов,мент матрицьппф равен минимальному ко- имевших в данный момент небольшую выссф 2личеству транзитных узлов, участвующих в ту рельефа 1.обмене , -гд узла через смежный К ыйузел с 1 -ым конечным узлом, На этаке формирования рельефа с течениемПоиск кратчайшего пути по рельефу из фе времени Фронт волны, перемешаясь от пен 1 -го узла в 1 -ый сводится к тому, что тра, устанавливает в узлах соответствующиев--ой строке матрицы М (1,) выбиает высоты рельефа. Ввиду неоднородностей пася минимальный элемент п= тпгп 1 ) раметроа линий связи и электро;:ных схемК = ,2 Р); Р= (Р . Индекс узйов скорость движения фронта волны поРо Ф Р указывает на направление смежно- Различным управляющим шинам может бытьго узла, через который проходит кратчай- неодинакова. В описываемой системе децеитра-.ший путь. Аналогичным образом в смежном йизаванного обмена информацией скоростиузле устанавливается связь по кратчайше Распространения фронта волны коинудительму пути к следующему транзитному узлу иб выравниваются путем добавления к номии так далее, пока информация не достигнет яальной задержке фронта волныфиксированногоконечного узда. Изменения в структуре се- интервала времени Ь , Задержка й одинати, вызванные неисправностями .нформа- кова для всех узлов и величина ее выбчраетционных магистралей или узлов, сопровож ся, исходя иэ условия:даются переформированием рельефа. ПриЬЬэтом неисправные магистрали (узлы) исклк= где 6 - номинальное время распрострачактся иэ процесса формирования рельефа, нения фронта волны между смежными узлатак что в результате переформирования Ре- ми;льефа поиск кратчайшего пути в сети проис- Ь - максимальный разброс времени;ходит с учетом всех изменений вызванных36 ОМ - число узлов максимально воз.,1 зжнеисправностями информационных магистра- ноге контура.Направленное движение фронта водны эа: ключается в том, что на этапе формирования рельефа в системе существует только один центр волны - конечный узел и только одна волна, рожденная данным центром; в системе исключены условия возникновения отраженных волн, В системе децентрализо ванного обмена информацией обеспечено направленное движение фронта волны и выравнивание скоростей движения фронта волны поредличным управляющим шинам, поэтому для формирования сигналов-индикаторов кратчай-ших путей досгаточно иметь информацию сле-. дующего типа: находится ли данный узел в данный интервал времени Ьв области дейст вия фронта волны или нет. Если в данный интервал времени 1 -ый узел по Р -ому направлению попал в область действия фронта волны, то Ро -ое направчение запоминается как напрамение кратчайшего пути, связы-фо веющего 1 -ый узел с конечным.Работа устройства управления обменом1 -то узла происходит следующим образом.В начальный момент сигналы 5 ( 1, р) =О, если все информационные магистрали узла ф исправны. При включении питания нв выходах всех элементов НЕ 9 появляются единичные уровни, которые поступают на первые входы элементов И 12 блоков выбора на првмения обмена. Йа вторые входы элементов И 12 через элемент НЕ 13 поступают пнвлы 6 ( 1, р) с выхода соответствующе" го блока аппаратного контроля, Посколькувсе 5 ( , с)=Я,то первый пришедший единичный уровень (например сигнал Ов(1 1,1по первому входному нвпрвмению по одной изупрввляющихшин 10) через элемент ИЛИ 14запускает одновибратор 15 и поступает напервый вход элемента И 16, Нв второй вход элемента И 16 поступает сигнал с вь 1-40 хода одновибрвтора 15 через элементИЛИ 17. Элементы И 16 и ИЛИ 17 служат для запоминания только тех сигналовО( 1, 1 р), которые поступают на входы блока вьбора направления в течение 45времени . Ь длительности работы одновибрвтара 15; Сигнв:ты (,1 р)с выхода элементов И 16, являющиеся индикатораминвпрамений кратчайшего пути в системе,по щинам 6 поступают в коммутаторы 2. Сигналы Рц (,1,1,р)с выходов блоков вы.бора нвлрввления формируютсч элементамиИ 18 и поступают через управляющие шины 10 на соответствующие входы блоковвыбора направлений смежных узлов. Приэтом сигНалы Он , ( 1 Р) поЯвлжотсЯнв окончании времени л только на тех1 -ых направлениях, которые не совпадаютс напрамениямискратчвйшего пуги. Такоенвпраменное движение фронта волны оелье 60 88фа обеспечивается тем, что сигнал 1(у, 1,р)через элементы ИЛИ 19 и НЕ 20 поступает нв первый вход элемента И 18, формирующето сигнал 4 ц(1, 1, р), а нввторой вход поступают сигналы О (1 1 рчерез элементы И 12 и ИЛИ 14,Если в результате отказа информацйонной магистрали сработал блок аппаратногоконтроля и сформировал сйгнал ь (1, 1 )= 1,то появление сигнала б( 1 1 ) на входахблоков выбора направлений приводит к блокировке соответствующих элементов И 12по вторым входам через элементы НЕ 13.Сигналы 0 (,1,1)( 1, 2, и),ранефпоступившие на входы блоков выбора направлений, блокируются ситналом 5(1,1). Крометого, сигнал 5( , 1) поступает на соответствующие блоки формирования рельефа 8 ичерез одновибраторы 21 и элемент ИЛИ 22,шину перестроения 11 и элементы НЕ 9 устанавливвет нулевой уровень нв упрамяющих шинах 10. Происходит разрушение рельефов, и по истечении времени работы одновибрвто рв 21 устанавливается новый рельеф, отражающий измененное состояние системы. Длцтельность импульса одновибратора 21 долж на быть достаточной для полного разрушений рельефа, Блок формирования рельефа 8 позволяет осуществить переформирование рельефов в системе при наличии множества сиг налов б ( 1, р) в системе.При восстаномении отказавших информационных магистралей необходимо выключить,соответствующие сигналы 5(,р)со входовблоков выбора напрамений и запустить соочветствующие лаки формирования рельефа.В остальном работа устройств упраменияобменом при восстановлении информационныхмагистралей ничем не отличается от работыв случае их отказа,Использование предложенной системы децентрвлизованнот о обмена информацией позволяет значительно повысить быстродействие . многомашинных вычислительных комплексов аа счет совмещения этапов формированийрельефа и поиска кратчайшего пути, увеличить надежность работы комплекса за счетвыполнения устройств упрамения обменомиз функционально независимых блоков выбора нвпрамения обмена, а также эффективнееиспользовать вычислительные машины в коМплексе ав счет того, что решение задачи уйю-рамения сетью переносится с вычислительных машин на устройства упрамения обменом.формула изобре тенин.1. Система децентрвлиаоввнного обменаинформацией, содержащач /И вычислительныхмашин, соединенных с блоками аппаратного контроля, по числу вычислительных машин в системе, коммутаторы и устройства уп; равления обменом, причем смежные вычислительные машины соединены информацион ными магистралями через соответствующие коммутаторы, о т л и ч а ю щ а я с я тем, что, с целью повышения надежности и быстродействия системы, в ней каждое уст ройство управления обменом содержит блок 10 формирования рельефа системы и ( и-) блоков выбора направления обмена, причем входы каждого блока формирования рельефа системы и первые входы ( ъ - 4 ) блоков выбора направления обмена соединены с соответствующими выходами блока аппаратного контроля данной вычислительной машины, а инверсный выход блока формирования рельефа системы соединен со вторыми входами олоков выбора направления обмена смежнйх устройств управления обменом, первые выходы каждого блока выбора направления обмена соединены управляюшими шинами с соответствующими вторыми входами смежных блоков выбора направления обмена, а вторые выходы - через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения.2. Система по п. 1, о т л и ч а ю ш а и-; ЗО с я тем, что каждый блок выбора направления обмена содержит одновибратор, вход ко торого подключен к выходу элемента ИЛИ, входы которого соединены с выходаМи первых элементов И, первые входы которых сое 35 динены через первые элементы НЕ с первы. ми входами блока выбора направления обмеь. на, а вторые входы соединены со вторыми входами блока выбора направления обмена, выход одновибратора подключен к первым входам первых элементов ИЛИ и к первым входам вторых элементов ИЛИ, выходы которых подключены ко входам вторых элементов НЕ, выходы которых подключены к первым входам вторых элементов И, а вторые входы вторых элементов И подключены к выходу элемента ИЛИ, первые входы третьего элемента И подключены к выходам первых элементов И, а вторые входы - к выходам первых элементов ИЛИ, вторые входы которых подклю- чены к выходам третьих элементов И, ко вторым входам вторых элементов ИЛИ и ко вторым выходам блока выбора направления обмена.3. Система по и, 1, о т л и ч а юш а я с я тем, что каждый блок формирования рельефа :истемы содержит одновибраторы, входы которых подключены ко входам блока формирования рельефа системы, а выходы одновибраторов через элемент ИЛИ соединены с выхода ли блоки формирования рельефа системы. Источники информации, щ ииятые во внимание при экспертизе:1. Алескеров С. А Григорович А, Ф., Попов А, А Радунский Б. М. " О некоторых системах межмашинны:, связей , Сб, Электронная техникаф. Серия У 1, Микроэлектроника, вып, 7 (15), 1968, с, 76-82.2. Лаптев В, И, О децентрализованной системе управления коммутируемой сетью связи", Сб, ",Пискретные автоматы и сети связи. М., Наука", 1970, с.23-34.Заказ 848/59 Тираж 818 ЦНИИПИ Государственного комитета Совета по делам изобретений и открытий 113035, Москва, Ж 35, Раушская наб