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

(21)3868947/24-24

(22)19.03.85

(46) 23.12.88. Бюл. № 47 (72) Ю.Н.Максименко и А.С.Максименко (53) 681.3(088.8) (56) Авторское свидетельство СССР 983702, кл. G 06 F 7/00, 1981. Авторское свидетельство СССР К 1249503, кл. G 06 F 7/00, 1985. (54)(57) ЯЧЕЙКА КАСКАДНОЙ КОММУТИРУЮЩЕЙ СРЕДЫ, содержащая элементы И, ИЛИ, НЕ, И-НЕ, группу элементов ИЛИ, -триггер входные блоки, каждый из которых содержит элементы И, ИЛИ, НЕ к и выходшае блоки, каждый из которых содержит элемент И, причем шина контроля ячейки соединена с первыми входами элемента ШШ-НЕ и первого элемента ИЛИ и входом первого элемента НЕ i-ro (,п) входного блока, выход которого соединен с первым входом первого элемента И i-ro входного блока, выход которого соединен с i-м входом первого элемента ИЛИ ячейки, выход которого соединен с первыми входами элементов И выходных блоков, вторсЛ вход элемента И i-ro выходного блока соединен с выходом элемента ШШ-НЕ i-ro входного блока, выход элемента И i-ro выходного блока соединен с i-й шиной вывода потенциала поиска ячейки, выход первого элемента ИЛИ i-ro входного блока соединен с i-м входом первого элемента И ячейки, выход которого соединен с первым входом второго элемента И ячейки, второй вход которого соединен с первым входом третьего элемента И ячейки, первый вход четвертого элемента И ячейки соединен с выходом второго элемента ИЛИ и входом первого элемента НЕ ячейки, выход которого соединен с первым входом пятого элемента И ячейки, второй вход которого соединен с вторы входом четвертого элемента И и входом второго элемента НЕ ячейки,о тлич ающая ся тем, что, с целью расширения области применения за счет обеспечения возмояг- ности работы, ячейки в качестве транзитной, в нее введены группа элементов И и элемент ИЛИ-НЕ, а каждый выходной блок содержит группу элементов И, причем i-я шина ввода потенциала поиска ячейки соединена с вторыми входами элемента Ш1И-НЕ и первого элемента И i-ro входного блока, выход которого соединен с пepвы tи входами второго элемента И и второго элемента ШШ к вторым входом первого элемента ШШ i-rd входного блока третий вход которого соединен с i-й шиной ввода потенциала квитирования маршрутизации ячейки, вторые входы вторых элементов И входных блоков объединены и соединены с выходом первого элемента И ячейки, выход второго элемента И i-ro входного блока соединен с i-й шиной вывода потенциала квитирования маршрутиза- 1Ц1И ячейки j-й (,п-О вход третьего элемента И i-ro входного блока соединен с выходом второго элемента НЕ k-ro () входного блока, п-й вход третьего элемента И 1-го входного блока соединен с выходом второго элемента ИЛИ i-ro входного блока, второй вход которого соединеЯ с i-й шиной вывода потенциала выде- Ленин ячейки входом второго элемента НЕ и выходом третьего элемента И

«у

й 1

Од

i-го входного блока, (п+1)-й вход которого соединен с выходом третьего элемента ИЛИ ячейки, i- ft вход Которого соединен с i-й шиной ввода потенциала выделения, управляющими входами элементов И группы элементов И i-ro выходного блока и i-м входом элемента ИЛИ-НЕ ячейки выход которого соединен с шиной разрешения выдачи собственного потенциала выделения ячейки, группа информационных входов группы элементов И выходного блока соединена с группой выходов группы элементов ИЛИ ячейки, tn-H( ,п+1} группа входов которой соединена с ш-й группой информационных входных шин ячейки, группа выходов группы элементов И i-ro выходного блока соединена с i-й группой информационных выходных шин яяейки5 Группа информационных входов группы элементов И ячейки соединена с группой выходов группы элементов ИЛИ ячейки, управляющие входы группы элементов И ячейки объединены и соединены с шиной ввода собственного потенциала выделения и (п+1)м входом третьего элемента ИЛИ ячейки, (п+1)вход первого элемента ИЛИ ячейки соединен с выходом-пятого элемента И ячейки, шина ввода собственного по. 446613

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

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

Цель изобретения - расширение области применения за счет,обеспечения возможности работы ячейки в качестве транзитной.

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

Ячейка содержит входные блоки 1,-1, шины ввода потенциалов поиска, шины 3 ,-3 контроля, шины , вывода потенциалов выделения;, шины 5-,-5 вода потенциалов квитирования маршрутизации, шины 6,-6 вывода потенциалов квитирования маршру

тизации, выходные блоки 7,-7,, шины , вывода потенциалов поиска, группы информационных выходных шин ,, шины ввода потенциалов вьщеления, шину 11 ввода потенциала квитирования обмена, шину 12 вывода потенциала квитирования маршрутизации, шину 13 ввода собственного потенциала поиска, шину 14 ввода собственного потенциала выделе.чия, шину 15 разрешения выдачи собственного потенциала выделения.

Каждый входной блок 1i ячейки содержит элементы И 16i, элементы НЕ 171, элемент ИЛИ-НЕ 18i, элемент ИЛИ 19i, элемент И 20i,элемент ИЛИ 21i, элемент И 22i и элемент НЕ 23i. Каждый выходной блок 7i ячейки

содержит элемент И 24i и группу эЛементов И 251.

Кроме того, ячейка содержит группу элементов И 25, элемент И 26, элемент И-НЕ 27, элемент ИЛИ 28 и 29, элемент ИЛИ-НЕ 30, элемент И 31 триггер 32, элемент НЕ 33, элемент И 34, элемент НЕ 35, элементы И 36- 38, элемент ИЛИ 39, элемент И 40, элемент ИЛИ 41, элемент НЕ 42, груп пу элементов ИЛИ 43 и группу информационных входных шин 44,.

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

Трансляционный обмен относится к числу групповых обменов и характеризуется наличием одной ячейки-источника сообщения и множества ячеек- приемников сообщений. В однородной вычислительной системе, например, каждой ячейке соответствует процессор, связанный с данной ячейкой управляющими и информационными шинами. Множество ячеек-приемников сообщений и ячейка-источник сообщения с помощью информационных и управляющих шин объединяются в вычислительну систему. Каждая ячейка имеет п ветвей, с помоп ью которых она связана со .смежными ячейками. Процессоры ячеек-приемников сообщений включают собственные единичные потен1Д1алы выделения (готовности приемников) на шинах 14 соответствующих ячеек. Процессор, соответствующий ячейке- источнику сообщения, формирует собст венньй едииичньй потенциал поиска на шине 13 своей ячейки. Этот потенциал является основанием дерева потенциалов поиска, которое формируется на всем множестве ячеек и ука- зывает кратчайший путь в ячейку-источник сообщения.

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

Информационный обмен на чинаатся с момента появления в ячейке-источнике сигналов квитирования маршрутизации (квитирование поиска) и выделения.

0

5

0

5

0

0

5

0

5

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

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

Работу ячейки в режиме трансляционного обмена составляют следующие этапы:

Этапы 2 и 3 совмещены по времени, поэтому эти этапы можно условно объединить в один этап квитирования маршрутизации.

Рассмотрим подробнее работу ячейки на каждом из указанных этапов.

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

Далее потенциал поиска поступает на (п+1)-й вход элеме нта ИЛИ 23 и с его выхода - на первые входы элементов И 24(-24 выходных блоков. Вторые входы этих элементов управляются элементами ШШ-НЕ 18,-18 соответствующих входных блоков. Появление потенциала поиска или потенциала контроля по какому-либо входному направлению блокирует выдачу потейциала поиска по этому направлению. Этим обеспечивается направленное формирование дерева потенциалов поиска на множество исправных ячеек. Отказ

5

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

Этап маршрутизации заканчивается когда дерево потенциалов поиска охватит все множество ячеек. Рост дерева потенциалов поиска ограничивается физическими размерами системы.

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

Рассмотрим работу ячейки на этапе квитирования- маршрутизации.

В граничной ячейке по всем исправ- 25 блокируя поступление собственного

30

ным входам поступают единичные потенциалы поиска, которые через элементы ИЛИ 19 т-19), поступают на входы элемента И 26. Единичный потенциал с выхода элемента И 26 поступает на первые входы элементов И входных блоков.

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

40

потенциала поиска на вход элемента ИЛИ 28. К этому моменту времени пу обмена зафиксированы потенциалами вьщеления. Этапы выделения и квити рования маршрутизации совмещены по времени, причем этап выделения заканчивается раньше этапа квитирова ния маршрутизации.

Рассмотрим работу ячейки на эта выделения.

Готовые к приему сообщения ячей ки-приемники сообщений формируют единичные потенциалы выделения на шинах 14, которые поступают на вхо ды элементов ИЛИ 29.

Единичный потенциал вьщеления с выхода элемента ИЛИ 29 поступает на первые входы элементов И 22,-22 входных блоков. Вторые, входы этих элементов управляются через элементы ИЛИ 21 .,-21 с выходов элемен тов И 16,-16f, входных блоков. Этим обеспечивается выделение стаола д рева потенциалов поиска, связываю щего источник и приемник сообщения 50 Элементы И 22 .,-22,, с помощью элеме тов НЕ 23-1-23f, охвачены обратными связями таким образом, что они обр . зуют многоустойчивый триггер, подключающий на шины 4 .,-4 вывода по- 55 тенциала выделения лишь один едини ный потенциал и запрещающий выдачу этих потенциалов по другим выходны шинам.

маршрутизации, либо потенциал контроля, которые объединяются элементом ИЛИ 19 и поступают на вход элемента И 26. На выходе элемента И 26 формируется единичный потенциал, если данная ячейка охвачена потенциалами поиска, квитирования маршрутизации или контроля по всем п направлениям. При этом потенциалы квитирования маршрутизации дополняют потенциалы поиска и контроля так, чтобы общее количество их равнялось п. В ячейке-источнике сообщения на входах , исправных направлений появляются потен

циалы квитирования маршрутизации. Отказавшие направления маскируются потенциалами контроля, поступающими по шинам 3 соответствующих направлений таким образом, что на выходах всех п элементов ИЛИ 19,-19 формируются единичные потенциалы, которые включают элемент И 26. Если ячейка изолирована (по всем п направлениям поступают сигналы контроля), то она блокируется по входу нулевым потенциалом с выхода элемента И-НЕ 27. Единичный потенциал с выхода элемента И 26 поступает на первый вход элемента И 37, второй вход которого включен единичным потенциалом с шины 13.-

На выходе элемента И 37 ячейки- источника формируется обобщенный единичньй потенциал квитирования маршрутизации, которьй поступает на первый вход элемента И 31 и через элемент ИЛИ 41 - в элемент НЕ 42,

0

0

потенциала поиска на вход элемента ИЛИ 28. К этому моменту времени пути обмена зафиксированы потенциалами вьщеления. Этапы выделения и квитирования маршрутизации совмещены по времени, причем этап выделения за канчивается раньше этапа квитирования маршрутизации.

Рассмотрим работу ячейки на этапе выделения.

Готовые к приему сообщения ячейки-приемники сообщений формируют единичные потенциалы выделения на шинах 14, которые поступают на входы элементов ИЛИ 29.

Единичный потенциал вьщеления с выхода элемента ИЛИ 29 поступает на первые входы элементов И 22,-22 входных блоков. Вторые, входы этих элементов управляются через элементы ИЛИ 21 .,-21 с выходов элементов И 16,-16f, входных блоков. Этим обеспечивается выделение стаола де- рева потенциалов поиска, связывающего источник и приемник сообщения. 0 Элементы И 22 .,-22,, с помощью элементов НЕ 23-1-23f, охвачены обратными связями таким образом, что они обра- . зуют многоустойчивый триггер, подключающий на шины 4 .,-4 вывода по- 5 тенциала выделения лишь один единичный потенциал и запрещающий выдачу. этих потенциалов по другим выходным шинам.

5

Благодаря этому обеспечивается выделение ствола дерева с несливающимися ветвями, т.е. выбирается оди кратчайший путь, соединяющий источник и приемник.

Элементы ИЛИ 21 и И 22 входных блоков образуют схемы защелки, с помощью которых потенциалы выделения фиксируют состояние одного из подключенных входных блоков.

Если i-й (,2,... ,п) входной блок подключен к потенциалу поиска 21 и на блокирующих входах элемента И 221 установлены единичные потенциалы (потенциал вьщеления транслируется по шине 41), то единичный потенциал с выхода элемента И 221 и через элемент ИЛИ 211 поступает на вход элемента И 221 и с этого момента состояние шины 41 определяется состоянием элемента ИЛИ 29 (наличием потенциалов вьщеления на входах ячейки) . Этап квитирования маршрутизации заканчивается блокировкой вьщачи собственного потенциала поиска из ячейки-источника. К этому моменту времени каналы, связывающие ячейку- источник с ячейками-приемниками, зафиксированы потенциалами выделения. Поэтому обнуление дерева потенциалов поиска не разрушает зафиксированные каналы связи, а освобождает лишь те ячейки, которые не участвуют в трансляционном обмене.

Этап информационного обмена начи- наетсй по единичному потенциалу по шине 12 квитирования маршрутизации. Этот потенциал формируется в ячейке- источнике на выходе элемента И 31 при наличии на ее входах хотя бы одного потенциала выделения (в системе имеется хотя бы одна готовая к .прие- i-iy ячейка-приемник) и при наличии обобщенного потенциала квитирования маршрутизации по шине 12 поступает в соответствующий процессор, информируя его о том, что система готова к приему сообщения. По этому сигналу процессор формирует сообщение, которое по шинам поступает на соответствующую ячейку и по отмеченному входным потенциалом выделения

0

5

0

5

0

5

0

5

0

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

в процессор-приемник.

Единичный потенциал с выхода элемента И 31 устанавливает триггер 32 ячейки-источника в единичное состояние, подготавливая ячейку-источник к формированию потенциала квитирования обмена.

Процессор ячейки-приемника, приняв сообщение по шинам 9,,,,, обнуляет шину 14 ввода собственного потенциала выделения, разрушая канал обмена ячейки-источника с данной ячейкой. Общее обнуление всех потенциалов выделения в системе является сигналом квитирования трансляционного обмена, который формируется на выходе элемента И 34.

Единичный потенциал с выхода элемента И 34 по шине 11 поступает в процессор ячейки-источника сообщения , информируя его о завершении цикла трансляционного обмена. По этому сигналу процессор обнуляет группу информационных входных шин 4,, и шину 13 ввода собственного потенциала поиска.

Элементы И 38, ИЛИ 39, И 40 и ИЛИ 41 образуют схемы защепки, которые устраняют импульсные помехи на выходе элемента И 36, возникающие во время обнуления шины 13 по сигналу с выхода элемента И 34.

Обнуление шины 13 устанавливает через элемент НЕ 33 триггер 32 в исходное нулевое состояние.

Элемент Ш1И-НЕ 30 служит для фор мирования разрешения выдачи собственного потенциала выделения процессору-приемнику в следующем . По единичному потенциалу с выхода элемента ИЛИ-НЕ 30, который транслируется в соответствующий процессор по шине 15, процессору разрешается формировать новый единичный потенциал выделения на шине 14.