Ячейка каскадной коммутирующей среды

Ячейка каскадной коммутирующей среды

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

ЕЕСПЮЛИН с;114. С 06 F 7/00 с ф

CO

С0

ЬФ

М

Cb (21) 3758444/24-24 (22) 28.06.84 (46) 23. 12. 85. Бюл. У 47 (72) 9.H. Максименко (53) 681.3(088.8) (56) Авторское свидетельство СССР

В. 752344, кл. G 06 F 7/00, 1978.

Авторское свидетельство СССР .В 983702, кл. С 06 F 7/00,,1981. (54)(57) ЯЧЕЙКА КАСКАДНОЙ КОММУТИРУЮЩЕЙ СРЕДЫ, содержащая элементы И, ИЛИ, НЕ,.И-HE и и входных блоков, каждый иэ которых содержит элементы

И, И-НЕ, причем 1 тя (1 1 tl ) шина ввода потенциала поиска соединена с первым входом элемента

И-НЕ < -го входного блока, выход которого соединен с 1 =м входом элемента И-НЕ, 1 =м входом элемента

И-НЕ ) =го (1 е и; 1 ф 1 ) входного блока при 1 и (1+1)=м

1 входом элемента И-НЕ 1 =го входного блока при ) i, (И+1)=й вход элемента

И-HE s =ro входного блока соединен с выходом первого элемента НЕ и (й+1)=м входом элемента И-НЕ, о тл и ч а ю щ а я с я тем, что, с целью повышения быстродействия, в нее введены элементы ИЛИ-НЕ, НЕ и л выходных блоков,.каждый из которых содержит элемент И и группу элементов И, причем =я шина контроля соединена с первым входом элемента ИЛИ-НЕ го входного блока и входом первого элемента

НЕ j =го входного бло у, выход которого соединен с (И+2)м входом

° элемента И-HE i =го входного блока, я шина ввода потенциала поиска соединена с вторым входом элемен„„SU„„1200276 А та ИЛИ-НЕ q =го входного блока, выход которого соединен с первым входом элемента И 1 -го выходного блока, второй вход которого соединен с выходом элемента И-НЕ, выход которого соединен с первым входом первого элемента И, выход которого соединен с первым входом элемента

И-НЕ го входного блока, второй вход которого соединен с выходом второго элемента НЕ 1 =го входного блока вход которого соединен с выФ

I ходом элемента И-НЕ 1 =го входного блока, выход элемента И i =го входного блока соединен с =й шиной вывода потенциала выделения, 1 Ыя (Е =- г ° л +1) . р информационных входных шин ячейки соединена с группой входов ь =й группы элементов ИЛИ, выходы (я+1)=й группы элементов ИЛИ соединены с первыми входами элементов И группы элементов И q =ro выходного блока, выходы которой соединены с 1 и группой информационных выходных шин ячейки, вторые входы элементов

И группы элементов И 1 =го выходного блока объединены и соединены с и шиной ввода потенциала выделения, i =м входом. элемента ИЛИ-НЕ и 1 =м входом элемента ИЛИ, выход элемента ИЛИ-НЕ соединен с шиной разрешения выдачи собственного потенциала вьщеления и первым входом второго элемента И, выход которого соединен с (в+1)=м входом элемента

ИЛИ, выход которого соединен с (П+3)=м входом элемента И-НЕ i =ro входного блока, вторым входом первого элемента И, входом второго эле1200276

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

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

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

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

Ячейка содержит входные блоки

1)-1„ с шинами 2)-2„ ввода потен,цйалов поиска, шинами 3, -3 „ контроля и шинами 4 -4 вывода потенциалов

tl выделения, выходные блоки 5, -5> с шинами 6 -6 вывода потенциалов и поиска, группами информационных вы ходных шин 7 -7 и шинами 8 -8 ввода потенциалов выделения. Кроме того, ячейка включает в себя группы информационных входных шин 9,-9„,,шину

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

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

И 1, =-ro выходного блока соединен с — И шиной вывода потенциала поиска.

2 входов которого соединен с шиной 2 ввода потенциала поиска, другой вход — с шиной 3 контроля, элемент

И 19, первый вход которого через элемент HE 20 подключен к выходу элемента И-НЕ 16, а выход — к шине

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

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

18 соответствующего входного блока, а выход - с шиной 6 вывода потенциала поиска, и группу элементов

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

Кроме того, ячейка содержит группы элементов ИЛИ 23, группы входов которых подключены к соответствующим группам информационных входных шин 9 -9 п,, а группа выходов— к группам информационных входов группы элементов И 22 -22 > выходных блоков, элемент И-HE 24, и входов которого подключены к выходам элементов И-НЕ 16 -16 входных блоков, а (й+1)=й вход — к третьим входам элементов И-НЕ 161-16 и входных блоков и через первый элемент HE 25 к шине 10 ввода собственного потен циала поиска, первый элемент И 20 первый вход которого подключен к вы1200276 ходу элемента И-НЕ 24 и вторым ., входам элементов И 21 -21 выход.tl ных блоков, а выход — к вторым входам элементов И 19<-19„ входных блоков, элемент ИЛЙ 27, И входов которого подключены к шинам 8 -8 и ввода потенциалов вьщеления, а выход — к второму входу первого элемента И 26 и (И+3) м входам элементов

И-HE 16 -16,„ входных блоков, второй элемент И 28, элемент ИЛИ-НЕ 29,. входы которого подключены к шинам

8 -8, ввода потенциалов выделения, а выход — к первому входу второго элемента И -28 и шине 13 разрешения выдачи собственного потенциала выделения, группу. элементов И 30, информационные входы которой подключены к .выходам группы элементов

ИЛИ 23, управляющие входы — к шине

14 ввода собственного потенциала выделения и второму входу элемента

И 28, а выходы — к собственным информационным выходным шинам 15, третий элемент И 3 1 и четвертый элемент И 32, первые входы которых подключены к шине 10 ввода собственного потенциала поиска, вторые входы — соответственно напрямую и.через второй элемент НЕ 33 к выходу эле,мента ИЛИ 27, а выходы — соответственно к шине t1 квитирования маршрутизации и шине 12 квитирования обмена.

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

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

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

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

У готовых к приему сообщения, и не

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

Этот потенциал информирует процессор-источник сообщения о том, что в системе установлен канал связи

У

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

Процессор-приемник сообщения, получив информационное сообщение

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

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

Рассмотрим работу ячейки на

40 каждом из указанных этапов.

Этап муршрутизации начинается с момента формирования процессором-источником сообщения на шине 10 единичного потенциала поиска. Проинвертированный элементом НЕ 25 по45 тенциал поиска поступает на вход элемента И-НЕ 24 и в виде единичного потенциала поступает на входы элементов И 21 -21l, выходных блоков.

Если < =е направление (l = 1, 502.) ,...h) исправно (по шине 3 конт-! роля поступает нулевой потенциал) и не занято (по соответствующей шине 2, поступает нулевой потенциал), то на выходе элемента

55.ИЛИ-HE 18 формируется единичный потенциал, который разрешает выдачу потенциала поиска на выходное =е направление. Элементы И-НЕ 16 -16 и

35

45

55

5 12002 входных блоков ячейки-источника

° блокируются нулевым потенциалом с выхода элемента HE 25, выделяя ,основание, формируемого "дерева" кратчайших путей. Потенциал поиска поступает на смежную ячейку по одной из шин 2 -2„ на вход элемента

И-НЕ 16 входного блока 1

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

Потенциал поиска с выхода подключенного элемента И-HE 16 поступает на вход элемента И-НЕ 24, с выхода которого в форме единичного потенциала — на входы элементов .

И 2 1 -21 выходных блоков. Дальнейшее продвижение потенциала поиска по каждому направлению (связи) зависит от его состояния. Если 1 =e 25 направление исправно и по нему не поступает пбтенциал поиска, то на выходе элемента И .21 ; формируется потенциал поиска, который трансли.руется по шине 6; в следующую 30 смежную ячейку. Таким образом осуществляется направленное формироваI/ ние церевас несливающимисяветвями с

:источником сообщенияв основании.

Процессор ячейки-приемника сообщения устанавливаей собственный единичный потенциал выделения на шине 14, который сообщает системе о готовности данного процесссора к приему сообщения. Этот потенциал поступает на вход элемента И 28 и при соответствии транзитных потенциалов вьщеления со стороны сменных ячеек (единичный, потенциал на выходе элемента ЙЛИ-НЕ 29) собственный потенциал выделения с выхода элемента И 28 через элемент

ИЛИ 27 поступает на входы элеменI тов И-HE 16 -16п входных блоков.

Этим обеспечивается формирование

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

Потенциал выделения с выхода элемента ИЛИ 27 поступает на первый

76 Ь вход элемента И 26, второй вход которого управляется потенциалом поиска с выхода элемента И-НЕ 24. При наличии обоих потенциалов на,выходе элемента И 26 формируется единичный потенциал выделения, который с выходов элементов И 19<-19„ транслируется в смежные ячейки. Направление смежной ячейки, по которому транслируется потенциал вьщеления, указывается подключенным входным блоком 1„, на выходе элемента НЕ 20 которого установлен единичный потенциал.

Таким образом, по мере формирования "дерева" потенциалов поиска одновременно с помощью потенциалов выделения фиксируются стволы дерева" (каналы), по которым будет осуществляться информационный обмен.

Каналы информационного обмена фиксируются потенциалами выделения, поступающими по шинам 8<-8 со стороны смежных ячеек, или собственным.потенциалом выделения, поступающим по шине 14. Эти потенциалы управляют соответственно выдачей информационного сообщения в П смежных ячеек или приемом информационного сообщения в собственный процессорприемник.

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

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

ПО Il!HIIBN 9г)11 IIACTупает на ВХОД

Составитель Л.Федоров

Редактор В.Петраш Техред M.Ïàðoöàé

Корректор И.Муска

Тираж 709 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Заказ 7868/54

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

7 12002 ячейки и по зафиксированному каналу передается в смежную ячейку-приемник.

Информационное сообщение поступает в ячейку-приемник по одной из

5 групп входных шин 9 -9д и с выхода группы элементов ИЛИ 23 через груп,пу элементов И 30 поступает на группу собственных информационных выходных шин 15 на вход процессора- 10 приемника, Процессор, получая сообщение, обнуляет собственный потенциал выделения на шине 14. Если в системе имеются ячейки-приемники, которые еще не завершили этап обме- 15 на, то каналы обмена будут поддерживаться за счет их собственных потенциалов выделения. Информационные каналы обмена поддерживаются наиболее удаленными от источника, ячейками-приемниками сообщений. 3авершение, этапа информационного обмена осуществляется после того, как информационное сообщение достигает этих ячеек и их процессоры примут 2s это -сообщение, По приему сообщения процессоры обнуляют собственные потенциалы и в системе начинается процесс последовательного разрушения каналов связи в направлении от наиболее удаленных ячеек-приемников к ячейке-источнику.

Обнуление всех потенциалов выделения в системе фиксируется эле%

76 8 ментом ИЛИ-НЕ 29 в каждой ячейке, единичный потенциал с выхода которого по шине 13 направляется в соответствующий процессор, разрешая ему формировать на шине 14 собственный единичный потенциал выделения следующего цикла обмена. Обнуление потенциалов выделения по всем входам в ячейке-источнике сопровождается появлением единичного потенциала на выходе элемента HE 33 и срабатыванием элемента И 32. На выходе элемента И 32 формируется единичный потенциал квитирования обцена, который по шине 12 поступает в процессор, информируя его о завершении цикла обмена. Следующий цикл обмена начинается с появления на выходе. элемента И 31 ячейки-источника потенциала квитирования маршрутизации.

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