Система децентрализованного обмена информацией Советский патент 1977 года по МПК G06F13/12 G06F15/16 

(54) СИСТЕМА ДЕЦЕНТРАЛИЗОВАННОГО ОБМЕНА ИНФОРМАЦИЕЙ

Изобретение относится к вычислительной технике и может быть использовано при построении систем обмена информацией в многомашинных вычиспитепьных коми лексах. Известна система обмена сетевого типа содержащая вычислительные машрны и коммутаторы, обьединекные в коммутадионнута сеть l. Задача управления сетью состо в том, чтобы гетя различных ситуаций на сети каждый раз из большого количества возможных путей между двумя машинами найти кратчайший по отношению к количес тву транзитов. В известной системе обме- на эта задача решается централизованно .на основе полной информации о состоянии всех элементов системы. Зта система обмена имеет недостатки: наличие единственного центрального органа (пульт управления, программа-диспетчер ) и необходимость наличия устройств отображения текущего состояния элементов сети, что уменьшает надежность всей системы обмена. Наиболее близкой по технической сушиости к предложенной системе является система децентрализованного объема информацией, содержащая вычиблительные машины, соединенные с блоками аппаратного контроля, по числу вычислительных машин в системе, коммутаторы и устройства управления обменом, причем смежные вычислительные машины соединены информационными магистралями через соответствующие коммутаторы 2. Недостатки известной системы децентрализованного обмена информацией состоят в том, что обмену данными между парой вычислительных маишн предшествует операция по определению кратчайшего пути в каждом устройстве управления, участвующем в обмене данными, что снижает скорость работы системы, кроме тог о отказ устройства управления обменом приводит к изоляции от системы соответствующей вычислител.™ ной машины, и соответствующий коммутатор исключается из коммутационной сети, образуемой всеми коммутаторами системы, а это снижает надежность системы. Целью изобретения является повышение быстроае{4ствия и надежности системы обмена информацией. Для этого каждое устройство управления обменом содержи блок формирьвання рельефа системы и ( .П - 1) блоков выбора направления обмена, причем входа каждого блока фоомйрования рельефа системы и первые входы (.71 1) блоков выбора направления обмена соединены с соответствутощими выходами блока аппаратного контроля данной вычислительной машины, а инверсный выхоЦ блока формирования рельефа системы соединен со вторыми входами блоков выбора направления обмена смежных устройств управления обменом, первые выходы каждого блока выбора направления обмена соединены управляющими шинами с соответ ствуюшими вторыми входами смежных блоков выбора направления обмена, а вторые выходы через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения. Кроме того, каждый блок выбора направления обмена содержит одновибратор, вход которого подключен к выходу элемента ИЛИ, входы которого соединены с выходами первых элементов И, первые входы крторых соединены через первые элементы НЕ с первыми входами блока выбора направления обмена, а вторые вхокы соединены со вторыми входами блока выбора йаправления обмена, выход одновибр тора подключен к первым входам первых элементов ИЛИ и к первым входам вторых элементов ИЛИ, выходы подклкие- ны ко входам вторых элементов НЕ , выходы которых подключены к первым входам вторых элементов И, а вторые входы вторых элементов И подключены к выходу эле мента ИЛИ, первые входы третьего элемента И подключены к выходам первых элемен тов И, а вторые входы к -выходам первых элементов ИЛИ, вторые входы которых подключены к выходам третьих элементов И, ко вторым входам вторых элементов ИЛИ и ко вторым выходам блока выбора направления обмена; каждый блок формирования рельефа системы содержит одновибраторы, вхо ды которых подключены ко входам блока формирования рельефа системы, а выходы огтновибраторов через элемент ИЛИ соединены с выходом блока формирования рельефа системы. На фиг. 1 представлена блок-схема пре ложенной системы децентрализованного обмена информацией четырех вычислительных машин; на фит 2 блок-схема устройства управлений Обменом на фиг. 3 - схема бло а выбора направления; на фиг. 4 - схема лока формирования рельефа. Система децентралнаованного обмена инормацией четырех вычислительных машин 1 содержит по числу вычислительных машин коммутаторы 2 и устройства управления обменом 3. Обмен информацией между вычислительными машинами осуществляется по информационным магистралям 4. Устройства управления обменом соединены управляющими магистралями 5, Устройства управления обменом подключены к коммутаторам 2 с помощью шин 6, по которым на коммутатор с устройства управления обменом выдаются сигналы-индикаторы крат-, чайших путей в системе. Каждое устройство управления обменом содержит независимо работающие блоки выбора направления 7 количество которых в каждом устройстве управления на единицу меньше числа устройств управления в системе, и блок формирования рельефа 8, Входы блока формирования рельефа и блоков выбора направления J- .о устройства управления обменом подключены к выходам соответствующего блока аппаратного контроля (на фиг. 2 не показанного). Появление сигнала ,5 ( f, р) на выходе бл«. ка аппаратного контроля узла оз-. качает отказ информационной магистрали 4, связывающей i -ый узел с Р -ым узлом. (Узел системы содержит вычислительную машину, коммутатор и устройство управления обменом). Каждый блок формирования рельефа через элемент НЕ 9 подключен через управлякнцие шины 10 ко входам блоков выбора направления обмена смежных узлов, а выходы всех блоков фррмирования рельефов объединены шиной перестроения 11. Шины 1Ои 11 образуют упраа, ляющую магистраль 5. Блок выбора направления содержит одновибратор 15, на вход которого через элементы ИЛИ 14 и элементы И 12 поступают входные сигналы OB С , 1), U (j.t, Д)с блоков выбора направления смежньтх узлов а выход одновибратора подключен на входы первых элементов ИЛИ 17. и вторых элементов ИЛИ 19. Здесь л - индекс уз- ла-источника или транзитного узла, j - индекс конечного узла. Кроме того, блок выбора направления содержит элементы И 16, НЕ 13, 20 и элементы И 18, выходы которых подключены ко входам соответству. щих блоков выбора направления смежных узлов.. Блок формирования рельефа содержит одновибраторы 21, на входы которых поступают сигналы S ( 1, р) с выходов блоков аппаратного контроля 23 соответствующих ин|)ормациоиных магистралей, и элемент ИЛИ 22, на выходе которого формируется сигнвл, осуществляющий формирование рель фов. Работа системы управления обменом ин формацией основана на волновом принципе поиска кратчайшего направления передачи информации (метод рельефов), Формирова- нне рельефа заключается в сопоставленйа каждому i -му узлу сети целого числа так, чтобы это число характеризовало крат чайдаее расстояние от данного i -го узла (источника информации или гранэигного узла) до конечного узла (потребителя ин. формации, или адресата). Конечный узел j получает число, равв О, узлы, смежные с конечным узлом, 1 и т.д. В сети сформирован 3 -рельеф, если узлам се- и приписаны тйкие числа, а сами числа. называются высотами з -рельефа и явлают ся указателями минимального количества узлов сети, через которые j -ьй узел свя зан с конечным узлом. В многополюсной сети для каждого конечного узла формируется свой рельеф; число рельефов равно количеству конечных узлов в сети. Если для пюбого .1 -го узла известны высоты сме ttbft узлов всех ГП рельефов, то данн:ую ин формацию можно представить в виде матрицы М (i, J)- Строки митрицы имеют индексы 3 it i ( i ls2,... n ), совпадающие с номерами конечных узлов; столбцы M(i,ij имектг индексы К (К 1,2,..., р ), соответствующие номерам ветвей, связывакняих i -4.1й узел со смежными узлами; элемент матрицытп -равен минимальному ко личеству транзитных узлов, участвующих в обмене iV-rd узла через смежный узел с -ым конечным узлом. Поиск кратчайшего пути по рельефу из .л -го узла в -ый сводится к тому, что в- j -О& строке матрицы М (i,j) выбирает ся минимальный элемент ТПц тп1п|т } (К н,2,... . Индекс РО Р указывает на направление смежно го узла, через который проходит кратчайший путь. Аналогичным образом в смежном узлеустанавливается связь по кратчайшему пути к следующему транзитному узлу и так далее, пока информация не достигнет конечного узла. Изменения в структуре сети, вызванные неисправностями информационных магистралей или узлов, сопровождаются .переформированием рельефа. При этом неисправные магистрали (узлы) исклюь чаются из процесса формирования рельефа, так что в результате переформирования рельефа поиск кратчайшего пути в сети происходит с учетом всех изменений, вызванных неисправнсютями информационных магистралей или узлов. В оста/хЬВ.ом одерац ш иере формирования рельефа иичек; не отличается . от оперании формирований рельафа, (Менсправность узла в системе эквивалента неисправностям всех его информационных ма«° гистраяей) В кресложенной сшл-л--ле нэцентролкзсванного обмена Hie.;;;-Jpi--ii-iCi-uii npe ijc:wcr-ipeB:o одновременное (параллельное) формирование рельефов для всех кедаечных узлов. Для это го каждое устройптйо управяения обменом разбивается на {-тееавйсамые (функдионаяьнр не связащ-хые между собой) блоки выбора направления обмена, число которых в жаждем узле на едийицу меньше количества yai-ios в системе. Каждый узел системы может являть ся как источником ннформадии( узел-источник), так и потребителем ш формации (конечным узлом), в каждом -ом ( j -i- i } блоке выбора направления обмена формируют-ся сигйалы-шдикаторы наяравлетш кратчай шего пути из данного т уаяа в j -bjft конечный узел. Из этих сигналов формнр5П отся управляющие сигналы (стрсбы) коммутатора. Блоки выбора направления обмена смеж- ных узлов постоянно обмениваются по лексным управляющим шинам информадкей о высотах рельефа, Объем информации о вы. сотах рельефа уменьшен до одного бита, это достигается за счет направленного двтгйекия фронта волны от центра конегког-о узйа и за счет выравниваикя скорост-ей дашкения фронта велйЫ при двгтжении фронта волны по различным управляющим шинам. (Под фронтом волны понимается дйожество узлов, имеющих в данный момент небольшую высс ту рельефа). На этапе формирования рельефа с течением времени фронт волвы, перемещаясь от центра, устанавливает в узлах соответствующие высоты рельефа. Ввиду неоднородностей параметров линий связи и электродных схем yartoB скорость движения фронта волны по различным управляющим шинам может быть неодинакова. В описываемой системе децентрайиаовакного обмена ш формацией скорости распространения фронта волны принудительо выравниваются путем цобавлелия к номи йальной задержке фронта волны фиксированного интервала времени Д . Задержка Д одинаова для всех узлов и величина ее выбираетя, исходя из условия: , , д(., ,)-t, де t - номинальное время распростраения фронта волны между узлаи;Д - максимальный разброс времеш ; N число узлов максимально возможоге контура. Направленное овткение фронта волны заключается в том, что на этапе формирования рельефа в системе существует только один центр волны - конечный узел и только одна волна, рожденная данным центром; в системе исключены условия возникновения отраженных волн. В системе децентрализованного обмена информацией обеспечено направленное движение фронта волны и выравнивание скоростей движения фронта волны по различным утфавляющим щинам, поэтому для формирования сигналов-индикаторов кратча ших пугай доб1:«гочно иметь информацию еледующего типа: находится ли данный узел в данный интервал времени Д в области дейст вия фронта волны или нет. Если в данный интервал времена i - 1йузелпо р о-ому направлению попал в область действия фронта волны, то Pfj -ое направление запоминается как направление кратчайшего пути, связы вающего i -ый узел с конечным. Работа устройства управления обменом 1 -го узла происходит следующим образом. В начальный момент сигналы S (i, р) С если все информационные магистрали узла исправны. При включении питания на выходах Всех элементов НЕ 9 появляются единичные уровни, которые поступают на первьге входы элементов И 12 блоков выбора направления обмена. На вторые входы элементов И 12 черев элемент НЕ 13 поступают с ггналы S ( 1, р) с выхода соответствующе- го блока -аппаратного контроля. Поскольку все. S { -1,р)0,то первый пришедший еди ничный уровень (например сигнал ( по первому входному направлению по одной изуправляющихшин 1О через элемент ИЛИ14 запускает одновибратор 15 и поступает на первый вход элемента И 16. На второй вход элемента И 16 поступает сигнал с хода одвовибратора 15 через элемент ИЛИ 17. Элементы И 16 и ИЛИ 17 служат для запомвпиания только тех сигналов UBX С J) 1, Р) которые поступают на входы блока выбора направления в течение времени & длительности работы одновибра тора 15. Сягн.аЛы f ()c выхода элементов И 16, являющиеся индикаторами направлений кратчайшего пути в системе, по щинам 6 поступают в коммутаторы 2. Сигналы tU, ( jj iip)c выходов блоков выбора направления формируются элементами И 18 и поступают через управляющие ши- ны 1О на соответствующие входы блоков выбора направлений смежных узлов. При этом сигналы L/gbix (1, 1, р) появляются на окончании времени д только на тех р -ых натфавлениях, которые не совпадают с направлениями кратчайшего пути. Такое направлензое движение фронта вопнь рельефа обеспечивается тем, что сигнал f( Лi,р) через элементы ИЛИ 19 и НЕ 20 поступает на первый вход элемента И 18, формирующего сигнал ,Оаь1х О , i. р) ни ---L«r ----.-Х) t rj второй ВХОД поступают сигналы вхО. ЛР через элементы И 12 и ИЛИ 14, Если в результате отказа информационной магистрали сработал блок аппаратного контроля и сформировал сигнал S {i, f ) 1 1, f ) на входах то появление сигнала S { блоков выбора направлений приводит к блокировке соответствующих элементов И 12 по вторым входам через элементы НЕ 13. Сигналы j.-i, iK j -f , n ) ,ране поступившие на входы блоков выбора направ Олений, блокируются сигналом S(i,t). Кромб того, сигнал S ( i, 1) поступает на соответствующие блоки формирования рельефа 8 и через одновибраторы 21 и элемент ИЛИ 22 шину перестроения 11 и элементы НЕ 9 ycfa- навливает нулевой уровень на управляющих шинах 1О. Происходит разруцгение рельефов, и по истечении времени работы одновибрато ра 21 устанавливается новый рельеф, отражающий измененное состояние системы. Дли тельность импульса одновибратора 21 долж- на быть достаточной для полного разрушений рельефа. Блок формирования рельефа 8 позволяет осуществить переформирование релье фов в системе при наличии множества сигналов S ( 1, р) в системе. При восстановлении отказавших информационных магистралей необходимо выключить соответствующие сигналы 5(V,p)со входов блоков выбора направлений и запустить coot ветствуюшие локи формирования рельефа. В остальном работа устройств управления обменом при восстановлении информационных магистралей ничем не отличается от работы в случае их отказа. Использование предложенной системы де централизованного обмена информацией позволяет значительно повысить быстродейст-- : вие многомашинных вычислительных комплексов за счет совмещения этапов формирований рельса и поиска кратчайшего пути, увеличить надежность работы комплекса за счет вьшолнения устройств управления обменом из функционально независимых блоков выбора направления обмена, а также эффективнее использовать вычислительные машины в ко плексе за счет того, что решение задачи ytt- равления сетью переносится с вычислител1 ных машин на устройства управления обменом. Формула изобре тени;}. 1. Система децентрализованного обмена информацией, содержащая /П вычислительных машин, соединенных с блоками аппаратного контроля, по чиспу вычислительных машин в системе, коммутаторы и устройства уп равления обменом причем смежные вычис лительйые машины соединены информационными магистрал5П и через соответствующие коммутаторы, отличающаяся тем, что, с целью повышения надежности и быстродействия системы, в ней каждое устройство управления обменом содержит блок формирования рельефа системы и ( TI- f ) блоков выбора направления обмена, причем входы каждого блока формирования рельефа системы и первые входы ( п - ) блоков выбора направления обмена соединены с соответствующими выходами блока аппаратного контроля данной вычислительной машины, а инверсньгй выход блока формирования рельефа системы соединен со вторыми входами блоков выбора направления обмена смежных устройств управления обменом, пер вые выходы каждого блока выбора направления обмена соединены управляющими шинами с соответствующими вторыми входами смежных блоков выбора направления обмена, а вторые выходы - через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения. 2, .Система по п. 1, о т л и ч а ю щ а с я тем, что каждый блок выбора направления обмена содержит одновибратор, вход кочторого подключен к выходу элемента ИЛИ, входы которого соединены с выходаТли первых элементов И, первые входы которых сое динены через первые элементы НЕ с первы ми входами блока выбора направления объле на, а вторые входы соединены со вторыми входами блока выбора направления обмена, выход одновибратора подключен к первым входам первых элементов ИЛИ и к первым входам вторых элементов ИЛИ, выходы которых подключены ко входам вторых элементов НЕ, выходы которых подключены к первым входам вторых элементов И, а вторые входы вторых элементов И подключены к выходу элемента ИЛИ, первые входы третьего элемента И подключены к выходам первых элементов И, а вторые входы - к выходам первых элементов ИЛИ, вторые входы которых подключены к выходам третьих элементов И, ко вторым входам вторых элементов ИЛИ и ко вторым выходам блока выбора направления обмена. 3. Система по п. 1, о т л и ч а ю щ а я с я тем, что каждый блок формирования рельефа системы содержит одновибратгуры, входы которых подключены ко входам блока формирований рельефа системы, а выходы одновибраторов через элемент ИЛИ соединены с выходами шокч фюрмирования рельефа системы. Источники информашге, пт инЕть;е во впкмание при экспертизе: -1. Алескеров С. А,, Григорович А, Ф., Попов А. А,, Радунский В. М, О нексп оых системах межмашинных связей , Сб, Электронная техника . Серия У1, Микролектроника, вып. 7 (15), 1968, с. 76-82, 2. Лаптев В. И. О децентрализованной истеме управления коммутируемой сетью вязи. Об, Дискретные автоматы и сети вязи . М., Наука, 1970, с.23-34.

М sM

f f

8

$(, S(3.2)

JLJL

в

S(3.)S{3,2) 7

Г)

r

7

ut

W Sij,2j

П Ir«i

ГГ

Фиг. 2

w

f/Ar/ X

fr/гг 1

/

„ l/2h

.3

3