Ячейка каскадной коммутирующей среды Советский патент 1986 года по МПК G06F7/00 

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

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

На чертеже нредставлена функциональная схема ячейки каскадной коммутирующей среды.

Ячейка содержит входные блоки 1 , шины 2-2„ ввода потенциалов поиска, шипы 3-3„ ввода потенциалов выделения, шины 4-4„ контроля, шины 5- 5л ввода состояния, шины 6--6„ вывода состояния ячейки, шины 7 Уг ввода признака обмена, группы информационных шип 8|-8,,, выходные блоки 9i -9„, шины 10|-10„ вывода потенциалов выделения, шины lli--ll,i вывода потенциалов юиска, Н1ИНЫ 12i-- 12„ вывода признака режима, группы .нин 3i -13„ вывода информации, блок 14 управления, шину 5 ввода призпака источника сообщения, пшну 16 ввода собственного потенциала ноиска, iHHfiv 17 ввода собственного признака обмена, и.шну 18 вывода обобщенного сигнала квитирования обмена, 1нину 19 вывода обобпдениого сигнала квитирования маршрутизации, грунну шин 20 ввода собственной информации, Н1ипу 21 вывода состояния блокировки ячейки, шипу 22 ввода собственного запроса приемника, ьчину 23 разрешения установки собственного запроса приемн.ика.

Каждый входной блок 1,- содержит элементы ИЛИ 24,, И 25,, 26„ НЕ 27,. ИЛИ 28,-, И 29„ И-НЕ 30„ НЕ 31 „ И 32„ группу элементов И 33,, элементы ИЛИ-НЕ 34, и ИЛИ 35,. Каждый зыходной блок 9 содержит э.;1емент,1 И 36/, 37, и ИЛИ 38,-. Блок 14 управления содержит регистр 39, схему 40 сраБ1 епии. группу элемептов ИЛИ 41, триггер 42, элементы И 43. ИЛИ 44. НЕ 45, ИЛИ 46, И 47, НЕ 48, И 49, ИЛИ 50, И 51, ИЛИ 52, 53, И 54 -57. НЕ 58, И-НЕ 59, НЕ 60, И 61. НЕ 62, ИЛИ 63 и НЕ 64.

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

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

0

5

0

О

5

5

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

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

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

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

Рассмотрим работу ячейки на первом )тапе трансляционного обмена.

Каждой ячейке соответствует процессор, который имеет доступ в регистр 39 соответствующей ячейки. Ячейка-источник и все ячейки, которые входят в подмножество ячеек-приемников сообн1.епия, предварительно помечаются нулевым кодом, поступаю- щиг из соответствующих процессоров в регистры 39. Готовые к приему сообнления ячейки-нриемники из числа но.меченного подмножества ячеек устанавливают единичные потенциалы запроса на шинах 22. Нро- цессор, соответствуюп1ий ячейке-источнику сообщения, формирует едипичные потенциалы поиска и признака источника на соот- ветствуюп;их ншнах 1В к 15, выдает код мет

ки на группу шин 20 ввода информации, а на шине 17 ввода признака обмена устанавливает нулевой потенциал.

Единичный потенциал поиска с шины 16 поступает через элемент ИЛИ 52 на первые входы элементов И 36|-Збп выходных блоков. Код метки, формируемый процессором ячейки-источника на шинах 20, поступает через группу элементов ИЛИ 41 на первый вход схемы 40 сравнения. Если данная ячейка включена в состав подмножества ячеек, участвующих в трансляционном обмене (в регистре 39 установлен код метки), то на инверсном выходе схемы 40 сравнения формируется нулевой потенциал, который через элементы НЕ 62, И 61 и ИЛИ 63 устанавливает в нулевое состояние триггер 42. Единичный потенциал с нулевого плеча триггера 42 разрешает выдачу потенциалов поиска на входы элементов И 36i-36„ в смежные ячейки. При этом выдача потенциалов поиска по каждому направлению про- исходит лишь в том случае, если по данному входному направлению отсутствуют потенциалы поиска или контроля. Эта блокировка осуществляется с помощью элементов ИЛИ- НЕ 34, за счет чего осуществляется направленное формирование «дерева потенциалов- поиска.

Потенциалы поиска поступают в смежную ячейку по шинам 2i-2„ и через элементы ИЛИ 241-24л подаются на первые входы элементов И 26i-26л входных блоков.

Единичные потенциалы контроля, форми- руемые на шинах 4i-4„, блокируют через элементы НЕ 27i-27л подключение входного блока, отказавшего направления обмена к формируемому «дереву потенциалов поиска. Если направление обмена исправно (на соответствующей шине 4 установлен нулевой потенциал), то единичный потенциал поиска с выхода элемента И 26 поступает на первый вход элемента И-НЕ 30 и через элемент ИЛИ 52 - на вход элемента И 36 выходного блока.

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

На выходе элемента И-НЕ 30, подключенного к потенциалу поиска, формируется нулевой потенциал, который блокирует входы элементов И-НЕ 30 остальных входных блоков и через элемент НЕ 31 разрешает поступление кода ячейки с шин 8 через группу элементов ИЛИ 41 на вход схемы 40 сравнения. Если данная ячейка входит в подмножество ячеек-приемников сообщения, то на инверсном выходе схемы 40 сравнения формируется нулевой потенциал, который через элементы НЕ 62 и И 61 подтверждает нулевое состояние триггера 42, разрешая

5

0 5

0

5

5

5

0

выдачу потенциала поиска с выходов элементов И 36i-36л.

Если данная ячейка не входит в подмножество ячеек-приемников сообщения, то единичный потенциал с инверсного выхода схемы 40 сравнения через элемент И 43 устанавливает в единичное состояние триггер 42. Элемент 53 задержки блокирует элемент И 43 на время работы с.хемы 40 сравнения и величина задержки элемента 53 должна быть не менее времени срабатывания схемы 40 сравнения.

Единичное состояние триггера 42 транслируется по подключенным потенциалом поиска направлениям в смежные ячейки по шинам 6|-6л, при этом нулевой потенциал с нулевого плеча триггера 42 блокирует выдачу потенциалов поиска в граничной ячейке с выходов элементов И 36i-36„, ограничивая тем самым формирование «дерева потенциалов поиска в пределах граничных ячеек.

Первый этап завершается выявлением ячеек-приемников, наиболее удаленных от источника сообщения, в которых замыкаются потенциалы поиска. Эти ячейки являются источниками потенциалов выделения. Ячейка является источником потенциалов выделения, если она подключена по всем п входным направлениям, т. е. на всех входах ячейки имеются единичные потенциалы из числа потенциалов поиска, состояния смежной ячейки или контроля. Эти потенциалы объединяются элементами ИЛИ 28i-28„ входных блоков и поступают на п входов элемента И 49, который формирует потенциал выделения. Этот потенциал через элемент ИЛИ 50 поступает на входы элементов И 371-37„ выходных блоков и с выходов этих элементов по шинам lOi - Юл транслируются в смежные ячейки-приемники сообщения (или источник сообпдения) и в смежные граничные ячейки.

С этого момента начинается второй этан трансляционного обмена. Управление ком- .мутацией потенциалов выделения по выходам осуществляется элементами ИЛИ 38i - 38л выходных блоков, которые объединяют подключенные потенциалы поиска и состояния смежных ячеек. Потенциалы выделения выдаются из ячейки по направлению подключенного входного блока или но направлению поступления потенциала состояния смежной ячейки. Состояние блокировки ячейки (наличие единичных потенциалов контроля или состояния по всем п направлениям) фиксируется элементом И 47 и транслируется в соответствующий нроцессор по шине 21. Потенциал блокировки ячейки с выхода элемента И 47 через элемент НЕ 48 блокирует выдачу потенциала выделения в заблокированной (изолированной) ячейке. Потенциал выделения с выхода элемента ИЛИ 50 поступает также на первые входы элементов И 25|-25„ входных блоков, которые совместно с элементами ИЛИ образуют схемы защелки и фиксируют каналы обмена нотенциалом выделения. За счет этого осуществляется подключение «дерева каналов связи к источникам потенциалов выделения и путь обмена фиксируется со стороны наиболее удаленных ячеек-нрием НИКОВ сообщений (источников нотенциалов выделения).

Второй этан заверщается появлением единичных потенциалов выделения на шинах 3:-3„ ячейки-источника сообщения. Эти потенциалы объединяются элементом И 49 и на выходе элемента И 51 формируется единичный потенциал квитирования марпл- рутизации. Этот потенциал по тине 19 поступает в соответствующий процессор, информируя его о том, что все входящие в под- ножества приемники сообщения подключены к «дереву каналов связи и имеется по крайней мере один готовый к приему приемник.

Третий этап инициирует нроцессор-ис- точник сообщения, который, получив потенциал квитирования марпарутизации, обнуляет па щине 16 собственный потенциал поиска, формирует на щинах 20 информационное сообн;ение, а на щине 17 формирует единичный потенциал признака сообщения.

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

Информационное сообщ,ение с соответствующим признаком транслируется по «дереву каналов связи во все ячейки-приемники сообщения. Все ячейки-п1)иемники, получив сообщение, транслируют его по тинам 13 в соответствующие процессорь), которые по получении сообщения обнуляют потеп- циалы запросов приемников на пшнах 22.

Обнуление ншны 22 в ячейке-источнике потенциала выделения приводит к срабаты- шнию элемента И-НЕ 59, который блокирует выдачу нотенциалов В1з1делепия с выходов элементов И 37| -37„.

С этого момента начинается четвертый этап - квитирование обмена. Г1)оцесс обнуления потенциалов выделеьщя протекает по «дереву каналов связи в направлепии от источников потенциалов выделения до ячейки-источника сообщения (основания «дерева). Граничная ячейка по обнулению тотенциала поиска на iLinHax 2) --2„ устанавливает в пулевое состояние триггер единичным потенциалом с выхода элемепта НЕ 64.

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

0

5

0

5

0

0

5

0

5

бJП-lжe всего расположены к ячейкам ветвления.

В ячейках ветвления необходимо поддерживать выдачу потепциалов выделения до момента полного их обнуления по всем входам в данных ячейках. Этим обеспечивается поддержка наиболее длинных ветвей (каналов связи) «дерева на время их обмена. Такая П0;адержка осуществляется элементом И 54.

Если в ячейке на всех щинах 3i-3„ потенциалы выделения обнулились, то на выходе элемента И 54 устанавливается нулевой потенциал, что приводит к обнулению потенциалов выделения на тинах 10| -10„ и ячейка исключается из «дерева связи (выходы подключенных элементов И 26i-26 входных блоков обнуляются и путь обмена разрун1ается). Последним разрушается ствол «дерева, соединяющий источник и наиболее удаленный от него приемник сообщения.

Источники потенциалов выделения, а следовательно, и пути обмена поддерживаются единичными потенциалами с шин 22 и элементом И 55 и ИЛИ 50, образующих схему «заплелки. Эта схема поддерживает единичный потенциал выделения на выходе элемента ИЛИ 50 до момента обнуления тины 22 запроса приемника, которое, в свою очередь, осуществляется процессором при приеме сообщепия.

Общее обнуление потенциалов выделения на всех п н:инах З;-3 в ячейке-источнике фиксируется элементом И 56, на выходе которого формируется единичный потенциал квитирования об.мена. Этот потенциал по 18 поступает в соответствующий процессор, информируя его о том, что все при- емщ1ки приняли сообщение. Процессор по этому сигналу обнуляет потенциал признака обмена на mniie 17 и снимает с шин 20 информационное сообщение. Трансляционный обмен завершен. Обнуление потенциалов признака обмена на всех шинах ячейки освобождает ее и ячейка готова к еледующему циклу обмена. На выходе элемента НЕ 45 формируется единичный нотенциал, который но цшне 23 поступает в соответствующий процессор, разрепшя ему выставить на щи- lie 22 запрос приемника следующего цикла обмена.

Формула изобретения

Ячейка каскадной коммутирующей среды со, 1ержаш,ая входные блоки, каждый из которых включает элемент И-НЕ и группу эле- v .eirroB И, и блок управления, содержащий элементы И, ИЛИ, И-НЕ, НЕ, группу эле- MCiiTOB ИЛИ, регистр и схему сравпепия, причем выход элемента И-НЕ г -го (, п) входного блока соединен с /-м входом элемепта И-НЕ /-ГО (, п, ) входного блока, при (/ и (г-1)-м входом элемента

И-НЕ /-ГО входного блока, при , /-я группа информационных шин ячейки соединена с группой информационных входов группы элементов И i-ro входного блока, группа выходов которой соединена с г -й группой входов группы элементов ИЛИ, группа выходов которой соединена с группой шин вывода информации и первой группой входов схемы сравнения, вторая группа входов которой соединена с группой выходов регистра, выход схемы сравнения соединен с вход,ом первого элемента НЕ и первым входом первого элемента И блока управления, отличающаяся тем, что, с целью расширения функциональных возможностей в режиме трансляционного обмена путем реализации этапов квитирования маршрутизации, информационного обмена и квитирования информационного обмена, в нее введены выходные блоки, каждый из которых содержит элементы И, ИЛИ, в каждый входной блок введены элементы И, ИЛИ, ИЛИ-НЕ, НЕ, Б блок управления введены элементы И, ИЛИ, НЕ, задержки и триггер, причем г -я шина ввода потенциалов поиска ячейки соединена с первым входом первого элемента ИЛИ г -го входного блока, выход которого соединен с первыми входами первого и второго элементов И и элемента ИЛИ-НЕ i-ro входного блока, выход первого элемента И /-ГО входного блока соединен с вторым- входом первого элемента ИЛИ г -го входного блока, второй вход второго элемента И i-ro входного блока соединен с выходом первого элемента НЕ i-ro входного блока, вход которого соединен с первыми входами второго и третьего элементов ИЛИ, вторым входом элемента ИЛИ-НЕ i-ro входного блока и /-и шиной контроля ячейки, 1-я шина ввода состояния ячейки соединена с вторыми входами второго и третьего элементов ИЛИ /-го входного блока и первым входом элемента ИЛИ г -го выходного блока, г -я шина ввода потенциалов выделения ячейки соединена с третьим входом третьего элемента ИЛИ i-ro входного блока и г -м входом первого элемента ИЛИ блока управления, четвертый вход третьего элемента ИЛИ i-ro входного блока соединен с выходом второго элемента И, первым входом третьего элемента И, (п+1)-м входом элемента И-НЕ i-ro второго блока, вторым входом элемента ИЛИ i-ro выходного блока i-м входом второго элемента ИЛИ блока управления, выход элемента И-НЕ г -го входного блока соединен с входом второго элемента НЕ i-ro входного блока, выход которого соединен с управляюш,ими входами группы элементов И и управляющим входом четвертого элемента И i-ro входного блока, информационный вход которого соединен с i-й шиной ввода признака обмена ячейки, выход четвертого элемента И i-ro входного блока соединен с i-M входом третьего элемента ИЛИ блока управления, ()-й вход которого

0

5

0

5

0

5

0

5

5

соединен с шиной ввода собственного признака обмена ячейки, выход третьего элемента ИЛИ блока управления соединен с группой шин вывода признака режима ячейки, входом второго элемента НЕ и первыми входами второго и третьего элементов И блока управления, второй вход, третьего элемента И блока управления соединен с выходом третьего элемента НЕ блока управления, вход которого соединен с выходом первого элемента ИЛИ и вторым входом второго элемента И блока управления, выход которого соединен с первым входом четвертого элемента ИЛИ блока управления, второй вход которого соединен с первым входом четвертого элемента И и выходом пятого элемента И блока управления, i-й вход которого соединен с выходом третьего элемента ИЛИ i-ro входного блока, (п+1)-й вход пятого элемента И блока управления соединен с выходом четвертого элемента НЕ блока управления, вход которого соединен с пшной вывода состояния блокировки ячейки и выходом шестого элемента И блока управления, i-й вход которого соединен с выходом второго элемента ИЛИ i-ro входного блока, (л+2)-й вход пятого элемента И блока управления соединен с третьим входом второго элемента И блока управления, первыми входами первых элементов И выходных блоков и нулевым выходом триггера, единичный выход которого соединен с вторым входом третьего элемента И i-ro входного блока, выход которого соединен с i-й шиной вывода состояния ячейки, выход третьего элемента И блока управления соединен с первыми входами элемента И-НЕ и шестого элемента И блока управления, второй вход которого соединен с шиной ввода признака источника сообщения ячейки и вторым входом четвертого элемента И блока управления, выход которого соединен с шиной вывода o6o6ni,eii- ного сигнала квитирования маршрутизации ячейки, выход шестого элемента И б,-1ока управления соединен с шиной вывода обобщенного сигнала квитирования обмена ячо;1- ки, второй вход элемента И-НЕ блока yiipai;- ления соединен с выходом пятого элсмспга НЕ блока управления, вход которого соединен с шиной ввода собственного запроса приемника ячейки и первым входом седьмого элемента блока управления, выход которого соединен с третьим входом четвертого э, 1е- мента ИЛИ блока управления, выход которого соединен с вторым входом седьмого элемента И блока управления, вторыми входами первых элементов И входных блоков и первыми входами вторых элементов И выходных блоков, вторые входы KOTopi.ix соединены с выходом элемента И-НЕ б.мока управления, выход элемента ИЛИ i-ro выходного- блока соединен с третьим входом второго элемента И i-ro выходного б, 1ока, выход которого соединен с i-й in и ной вывода потенциала выделения ячейки, выход -хлсмента ИЛИ-НЕ i-ro входного б.пока соединен с вторым входом первого элемента И i-ro выходного блока, виход которого еоединен с i-й шиной вывода потенциала поиска ячейки, третьи входы первых элементов И выходных блоков объединены и соединены с входами элел1е1гга задержки и выходом второго элемента ИЛИ блока управления, (п-|-1)-й вход которого соединен с шиной ввода собственного нотенциала поиска ячей- еи, выход элемента задержки соединен с вто рым входом первого элемента и первым входом восьмого элемента И блока управле1 ия, выход которого соединен с выходом первого

элемента НЕ б.лгФ:а управления, выход восьмого элементу И соединен с первым входом пятого элемента Hj IM блока управления, второй вход которого соединен с выходом шестого элемента НЕ блока управления, выход пятого элемента ИЛИ блока управления соединен с нулевым входом триггера, единичный вход которого соединен-с выходом первого элемента И блока управления, третий вход которого соединен с выходом второго элемента НЕ, третьим входом восьмого элемента И блока управления и шиной раз- рен1ения установки собственного запроса приемника ячейки.

/f .23

fff

fOri

22

12i 12n

(л)с г;и-;итс, 11, Д. Фелоро:

Редактор Л. Воров1:Ч14 хро ; И. ik pecКорректор В. Бутяга

3;iКПЗ 4325; 19 i upamli/lПодпнсь-ое

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий

113035, Москва, Ж--Зо, Раушская наб., д. 4/5

Филиал ППП «Патент, i-, Ужгород, ул. Проектная, 4

Изобретение относится к автоматике и вычислительной технике и может быть ис- пользовьно при реализации технических средств параллельной обработки информации. Цель изобретения - расширение функциональных возможностей за счет реализации этапов квитирования маршрутизации, информационного обмена и квитирования информационного обмена. Цикл обмена информацией между источником и приемниками сообщения осуществляется за четыре этапа. На первом этапе ячейка - источник сообщения формирует «дерево кратчайших путей, связывающее источник с множеством приемников сообщения. Выявляются граничные ячейки, изолирующие «дерево от остальных ячеек, и наиболее удаленные от основания «дерева ячейки-приемники, формирующие потенциа.ты выделения. На втором этапе потенциалы выделения обратным ходом по «дереву кратчайших путей транслируются в ячейку - источник сообщения. При поступлении потенциалов выделения от всех наиболее удаленных от основания «дерева ячеек ячейка - источник формирует обобщенный сигнал квитирования маршрутизации, который поступает в процессор - источник. На третьем этапе осуществляется трансляция информационного сообщения от источника к множеству приемников по «дереву каналов связи. При получении сообщения наиболее удаленные от источника ячейки - приемники блокируют выдачу потенциалов выделения. На четвертом этапе ячейка - источник фиксирует момент обнуления всех потенциалов выделения и формирует сигнал квитирования обмена, поступающий в процессор источник. Одновременно с обнулением потенциалов выделения происходит разрушение «дерева каналов связи с освобождением всех занятых ячеек. 1 ил. «; (Л Ю 4 дэ ел о со