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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУ БЛИН

46613 А1 (19) (11) (51) 4 С 06 Р 7/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

K ABTOPCKOIMIV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГКНТ СССР (21) 3868947/24-24 (22) 19 ° 03.85 (46) 23.12.88. Бюл. Ф 47 (72) Ю.Н.Максименко и А.С.Максименко (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

Н 983702, кл. 0 06 F 7/00, 1981.

Авторское свидетельство СССР з 1249503, кл. G 06 F 7/00, 1985. (54)(57) ЯЧЕЙКА КАСКАДНОЙ КОИМУТИРУИЩЕИ СРЕД)1, содержащая элементы И, ИЛИ, НЕ, -HE группу элементов ИЛИ, .-триггер, входные блоки, каждый из которьм содержит элементы И, ИЛИ, НЕ и ИЛИ-НЕ и вьмодные блоки, каждый из которых содержит элемент И, причем шина контроля ячейки соединена с первыми входами элемента ИЛИ-НЕ и первого элемента ИЛИ и входом первого элемента НЕ i-го (i=1,n) входного блока, выход которого соединен с первым входом первого элемента И

i-го входного блока, выход которого . соединен с i-м входом первого элемента ИЛИ ячейки, выход которого соединен с первыми входами элементов

И выходных блоков, второй вход элемента И i-го выходного блока соединен с выходом элемента ИЛИ-HE i-го входного блока, выход элемента И

i-ro выходного блока соединен с i-й шиной вывода потенциала поиска ячейки, выход первого элемента HJIH i-го входного блока соединен с i-м входом первого элемеьга И ячейки, выход которого соединен с первым входом второго элемента И ячейки, второй вход которого соединен с первым входом третьего элемента И ячейки, первый вход четвертого элемента И ячейки соединен с выходом второго злемента ИЛИ и входом первого элемента

НЕ ячейки, выход которого соединен с первым входом пятого элемента И ячейки, второй вход которого соединен с вторым входом четвертого элемента

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

ro элемента И i-ro входного блока, выход которого соединен с первыми входами второго элемента И и второго элемента ИЛИ и вторым входом первого элемента ИЛИ i-гб входного блока, третий вход которого соединен с i-й шиной ввода потенциала квитирования маршрутизации ячейки, вторые входы вторых элементов И входных блоков объединены и соединены с выходом первого элемента И ячейки, выход . C5 второго элемента И i-ro входного блока соединен с i-й шиной вывода Э® потенциала квитирования марщрутиза" фф ции ячейки, j-й (jt п-1) вход третьего элемента И i-го входного блока соединен с выходом второго элемента

HE k-го (к1,а,МО входного блока, и-й вход третьего элемента И i-ro входного блока соединен с выходом . мЗ второго элемента HJIH i-го входного блока, второй вход которого соединея с i-й шиной вывода потенциала выделения ячейки, входом второго элемента HE и выходом третьего элемента И

1446613

i-ro входного блока, (и+1)-й вход которого соединен с выходом третьего элемента ИЛИ ячейки, i-й вход

Которого соединен с i-й шиной ввода потенциала выделения, управляющими входами элементов И группы элементов

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

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

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

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

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

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

2 тизации, выходные блоки 7,-7„, шины

8,-8> вывода потенциалов поиска, группы информационных выходных шин

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

Каждый входной блок 1i ячейки содержит элементы И 16i, элементы НЕ

17i, элемент ИЛИ-НЕ 18х, элемент ИЛИ

19i элемент И 20i,элемент ИЛИ 21i, элемент И 22i и элемент НЕ 23i.

Каждый выходной блок 7i ячейки содержит элемент И 24i и группу элементов И 251.

Кроме того, ячейка содержит группу элементов И 25„,„, элемент И 26, элемент И-НЕ 27, элемент ИЛИ 28 и

29, элемент ИЛИ-НЕ 30, элемент И 31, триггер 32, элемент HE 33, элемент

И 34, элемент HE 35, элементы И 3638, элемент ИЛИ 39, элемент И 40, элемент ИЛИ 41, элемент HE 42, группу элементов ИЛИ 43 и группу информационных входных шин 44„- 44„,.

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

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

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

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

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

446613

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

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

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

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

1. Маршрутизация — поиск на всем множестве ячеек-приемников.

2. Квитирование маршрутизации—

25 подтверждение того факта, что поиском охвачено все множество ячеек.

3. Вьщеление хотя бы одной готовой к приему сообщения ячейки.

Информационный обмен.

5. Квитирование информационного обмена.

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

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

Этап маршрутизации начинается с момента формирования на шине 13 процессором-источником сообщения собственного единичного потенциала поиска.

Этот потенциал поступает на первый вход двухвходового элемента И 36, второй вход которого открыт с выхо45 да элемента НЕ 42.

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

55 поиска по этому направлению. Этим обеспечивается направленное, формирование "дерева" потенциалов поиска на множество исправных ячеек. Отказ

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

3 поступает на смежные ячейки.

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

"дерева" потенциалов поиска ограничивается физическими размерами системы.

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

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

В граничной ячейке по всем исправ- 25 ным входам 2„-2 „поступают единичные потенциалы поиска, которые через элементы ИЛИ 19„-19 поступают на входы элемента И 26. Единичный потенциал с выхода элемента И 26 поступает на первые входы элементов И

20„-20„ входных блоков.

На вторые входы этих элементов поступают единичные потенциалы с выхода подключенных элементов И 16, 16„.

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

ИЛИ 19 и поступают на вхбд элемента

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

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

Единичный потенциал с выхода элемента И 26 поступает на первый вход элемента И 37, второй вход которого включен единичным потенциалом с шины 13.

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

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

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

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

Единичный потенциал выделения с выхода элемента ИЛИ 29 поступает на первые входы элементов И 22,-22 „ входных блоков. Вторые. входы этих элементов управляются через элементы ИЛИ 21„-21„ с выходов элементов И 16,-16 „ входных блоков. Этим ,обеспечивается выделение ствола "де:рева" потенциалов поиска, связывающего источник и приемник сообщения.

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

446613

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

5 ник и приемник.

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

Если i-й (i=1,2,...,n) входной блок подключен к потенциалу поиска

2i и на блокирующих входах элемента

И 22i установлены единичные потенциалы (потенциал выделения транслируется по шине 4i) то единичный потенциал с выхода элемента И 22i и через элемент ИЛИ 21i поступает на вход элемента И 22 и с этого момен- 20 та состояние шины 4i определяется состоянием элемента ИЛИ 29 (наличием потенциалов выделения на входах ячейки). Этап квитирования маршрутизации заканчивается блокировкой выдачи 25 собственного потенциала поиска из ячейки-источника. К этому моменту времени каиалы, связывающие ячейкуисточник с ячейками-приемниками, зафиксированы потенциалами выделения.

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

Этап информационного обмена начи35 нается по единичному потенциалу по шине 12 квитирования маршрутизации.

Этот потенциал формируется вячейкеисточнике на выходе элемента И 31 при наличии на ее входах хотя бы одного потенциала выделения (в системе имеется хотя бы одна готовая к приему ячейка-приемник) и при наличии обобщенного потенциала квитирования 45 маршрутизации по шине 12 поступает в сбответствующий процессор, информируя его о том, что система готова к приему сообщения. По этому сигналу процессор формирует сообщение, которое по шинам 44 +, поступает на соответствующую ячейку и по отмеченному входным потенциалом выделения направлению транслируется в смежную ячейку. Информационное сообщение транслируется всем приемникам nG каналу связи, зафиксированным потенциалами выделения, и с выходов группы элементов И 25 „,„ по группе информационных выходных шнн 9 „„ поступает в процессор-приемник.

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

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

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

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

Элементы И 38, ИЛИ 39, И 40 и

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

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

Элемент ИЛИ-НЕ 30 служит для формирования разрешения выдачи собственного потенциала выделения процессору-приемнику в следующем цикле.

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

144б613

0((ФФа( ф!

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

Техред Л.Олийнык Корректор В.Гирняк

Редактор А.Ворович

Заказ 6748/53 тираж 704 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР !13035, Москва, K-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4