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

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

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

ЯЧЕЙКА КАСКАДНОЙ КОМИУТИРУКЙЦЕЙ СРЕДЫ, содержащая элементы И, ИЛИ, НЕ, И-НЕ и П входных блоков, каждый из которых содержит элементы И, И-НЕ, причем i :ья

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

Цель изобретения - повьш1ение быстродействия .

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

Ячейка содержит входные блоки 1,-1„ с шинами 2,-2п ввода потен,циалов поиска, шинами контроля и шинами 4,-4„ вывода потенциалов вьщеления, выходные блоки 5,-5 с шинами 6,-6 вывода потенциалов поиска, группами информационных выходных шин 7, -1л. и шинами 8, -8п, ввода потенциалов вьщеления.Кроме того, ячейка включает в себя группы информационных входных шин 9 ,-9nfi шину 10 ввода собственного потенциала поиска, шину 11 вывода потенциала квитирования маршрутизации, шину 12 вьтода потенциала квитирования обмена, шину 13 вывода потенциала разрешения выдачи собственного потенциала выделения шину 14 ввода собственного потенциала выделения и группу собственных информационных выходных шин 15.

1

Каждый входной блок 1 содержит элемент И-НЕ 16, один из входов которого соединен с шиной 2 ввода потенциала поисков, другой вход через элемент НЕ 17 с шиной 3 контроля, элемент ИЛИ-НЕ 18, один из

входов которого соединен с шиной 2 ввода потенциала поиска, другой вход - с шиной 3 контроля, элемент И 19, первый вход которого через

элемент НЕ 20 подключен к выходу элемента И-НЕ 16, а выход - к шине 4 вывода потенциала вьщеления. Выход элемента И-НЕ 16 каждого входного блока подключен к входам элементов И-НЕ 16 других входных блоков.

Каждьш выходной блок 5 содержит элемент И 21, первьй вход которого соединен с выходом элемента ИЛИ-НЕ

18 соответствующего входного блока, а выход - с шиной 6 вывода потенциала поиска, и группу элементов И 22, первые входы которой подключены к шине 8 ввода потенциала выделения, а выходы - к группе инфор.мационных выходных шин 7.

Кроме того, ячейка содержит группы элементов ИЛИ 23, группы входов которых подключены к соответствующим группам информационных входных шин 9j-9r ti , а группа выходов к группам информационных входов -. группы элементов И 22f-22(, выходных блоков, элемент И-НЕ 24, h входов

которого подключены к выходам элементов И-НЕ , входных блоков, а (п+1)й вход - к третьим входам элементов И-НЕ 1б|-1б, входных блоков и через первый элемент НЕ 25

к шине 10 ввода собственного потенциала поиска, первый элемент И26, первый вход которого подключен к выходу элемента И-НЕ 24 и вторым входам элементов И 21,-21ц выходных блоков, а выход -. к вторым входам элементов И входных блоков, элемент ИЛИ 27, h входов которого подключены к шинам 8,-8 ввода потенциалов выделения, а выход - к второму входу первого элемента И 26 и (h+3)M входам элементов И-НЕ 16, -16 f, входных блоков, второй элемент И 28, элемент ИЛИ-НЕ 29,входы которого подключены к шинам 8 -8 , ввода потенциалов выделения, а выход - к первому входу второго элемента И 28 и шине 13 разрешения выдачи собственного потенциала выделения, группу элем.ентов И 30, информационные входы которой подключены к выходам группы элементов ИЛИ 23, управляющие входы - к шине 14 ввода собственного потенциала выделения и второму входу элемента И 28, а выходы - к собственным информационным выходным шинам 15, третий элемент И 31 и четвертый элемент И 32, первые входы которых подключены к шине 10 ввода собственного потенциала поиска, вторые входы - соответственно напрямую и через второй элемент НЕ 33 к йыходу элемента ИЛИ 27, а выходы - соответственно к шине 11 квитирования Маршрутизации ишине 12 квитирования обмена.

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

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

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

Процессор, соответствующий ячейке-источнику сообщения, формирует единичный потенциал на шине 10 своей ячейки. Этот потенциал является

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

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

соединяющий источник и приемники сообщений.

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

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

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

Этап муршрутизации начинается с момента формирования процессором-источником сообщения на шине 10 единичного потенциала поиска. Проинвертированный элементом НЕ 25 потенциал поиска поступает на вход элемента И-НЕ 24 и в виде единичного потенциала поступает на входы эле- . ментов И 21,-21 выходных блоков. Если направление ( i 1, 2,...h) исправно (по шине контроля поступает нулевой потенциал) и не занято (по соответствующей шине 2, поступает нулевой потенциал) , то на выходе элемента ИЛИ-НЕ 18 формируется единичный потенциал, который разрешает выдачу потенциала поиска на выходное i е нйправление. Элементы И-НЕ 1б,-16„ входных блоков ячейки-источника блокируются нулевым потенциалом с выхода элемента НЕ 25, вьщеляя основание формируемого дерева кр чайших путей. Потенциал поиска поступает на- смежную ячейку по одной из шин 2,-2п на вход элемента И-НЕ 16 входного блока Ь. Элементы И-НЕ 16,-16р с обратными связями образуют многоустойчи вый триггер. Одновременное появлен потенциалов поиска по нескольким, шинам 2 -2„ приведет к тому, что только один элемент И-НЕ 16 подклю чится к потенциалу поиска, заблокировав все остальные. Потенциал поиска с выхода подключенного элемента И-НЕ 16 поступ ет на вход элемента И-НЕ 24, с выхода которого в форме единичного потенциала - на входы элементов И и выходных блоков. Дальней шее продвижение потенциала поиска по каждому направлению (связи) зависит от его состояния. Если i re направление исправно и по нему не поступает пбтенциал поиска, то на выходе элемента И -21 формируется потенциал поиска, который трансли.руется по шине 6; в следующую смежную ячейку. Таким образом осуществляется направленное формирова ние ерева с несливающимисяветвями источником сообщенияв основании. Процессор ячейки-приемника соо щецкя устанавливает собственный единичньй потенциал выделения на шине 14, который сообщает системе о готовности данного процесссора приему сообщения. Этот потенциал поступает на вход элемента И 28 и при соответствии транзитных пот циалов выделения со. стороны сменных ячеек (единичный ,потенциал на выходе элемента ИЛИ-НЕ 29) собственный потенциал вьщеления с вы;хода элемента И 28 через элемент ИЛИ 27 поступает на входы элементов И-НЕ 16,-16р входных блоков. Этим обеспечивается формирование дерева лишь на множестве ячеек-п емников готовых к приему сообщения. Ячейки, не участвующие в трансляционном обмене, «е включают ся в каналы обмена и могут быть ис пользованы для решения других зада Потенциал вьщеления с выхода элемента ИЖ 27 поступает на пер 66 вход элемента И 26, второй вход которого управляется потенциалом поиска с выхода элемента И-НЕ 24. При наличии обоих потенциалов на .выходе элемента И 26 формируется единич- , ный потенциал выделения, который с выходов элементов И транслируется в смежные ячейки. Направление смежной ячейки, по которому транслируется потенциал вьщеления, указывается подключенным входным блоком 1|, на выходе элемента НЕ 20 которого установлен единичный потенциал. Таким образом, по мере формирования дерева потенциалов поиска одновременно с -помощью потенциалов выделения фиксируются стволы дерева (каналы), по которым будет осуществляться информационный обмен. Каналы информационного обмена фиксируются потенциалами выделения, поступающими по шинам стороны смежных ячеек, или собственным потенциалом выделения, поступающим по шине 14. Эти потенциалы управляют соответственно выдачей информационного сообщения в и смежных ячеек или приемом информационного сообщения в собственный процессорприемник , Ячейки-приемники, смежные с ячейкой-источником, первыми подключаются к формируемому дереву и о.братным ходом с помощью своих потенциалов выделения фиксируют каналы обмена. Процесс закрепления каналов связи, соединяющих ячейку-источник с ближайшими с ней ячейками-приемниками, совмещается по времени с последукицим этапом формирования дерева потенциалов поиска в направлении от данных ячеек-приемников к другим ячейкам, смежньм с данными . Поступление единичного потенциала выделения в ячейку-источник сообщения информирует соответствующий процессор о том, что канал обмена с ближайшими .к нему приемниками зафиксирован со стороны этих приемников. Этот сигнал квитирования маршрутизации формируется на выходе элемента И 31 и транспортируется в свой процессор по шине 11. Процессор по сигналу на шине 11 формирует информационное сообщение, которое по шинам 9кц1 поступае.т на вход