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

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

Иллюстрации

Показать все

Реферат

 

(72) Автор изобретения

Ю. Н. Максименко (71) Заявитель (54) ЯЧЕЙКА КАСКАДНОЙ КОММУТИРУЮЩЕЙ ГРЕДЫ

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

По основному авт. св. л"- 842788 известна ячейка, содержащая m входных блоков,. включающие три элемента И вЂ” НЕ и элемент И каждый, элементы И, НЕ, И вЂ” НЕ, ИЛИ, регистр и схему сравнения (1).

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

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

Поставленная цель достигается тем, что оно дополнительно содержит элемент И и элемент задержки, вторые элементы ИЛИ и НЕ, третий элемент И вЂ” НЕ и и выходных блоков, каждый из которых содержит четыре элемента

И вЂ” НЕ, два элемента НЕ и элемент задержки, причем i-ая шина ввода потенциала выделения (i 1, 2, ..., n) подключена к входу первого элемента НЕ i-го выходного блока, выход которого подключен к входу элемента задержки и к первым входам первого и второго элементов И вЂ” НЕ i-ro выходного блока, второй вход которого подключен к выходу элемента задержки i-го выходного блока, третий вход подключен к выходу первого элемента И вЂ” HE i-го выходного блока, а выход подключен к первому входу третьего элемента

И вЂ” НЕ i-го выходного блока, второй вход которого подключен к выходу четвертого элемента И вЂ” НЕ i-го выходного блока, первый вход которого подключен к выходу второго

94965 элемента НЕ i-го выходного блока, вход которого подключен к выходу первого элемента

И вЂ” НЕ i-го выходного блока, вторые входы четвертых элементов И--HE i-ых выходных блоков подключены к выходу второго элемента ИЛИ ячейки, j-ые входы первого элемента И вЂ” НЕ i-ro выходного блока (j = 2,3, n) подключены к выходам первых элементов И вЂ”,НЕ j-ых выходных блоков (j ф i) соответственно, m входов второго элемента

ИЛИ ячейки (m = 1,2, „m, m (п) подключены к m шинам ввода потенциала блокировки вьщеления соответственно, à (m +

+ 1)-ый вход подключен к выходу элемента

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

На чертеже показана функциональная схема ячейки.

Ячейка содержит входные блоки 1,— 1щ с шинами ввода потенциалов поиска 2 — 2m шинами 31 — Зm KQHTpoTIH и шинами 4 — 4п,, вывода потенциалов выделения, выходные бло30 ки 5> — 5> с шинами 6> — 6п вывода потенциалов блокировки выделения и шинами 7,— 7п, ввода потенциалов выделения, элемент ИЛИ 8 с шинами 9> — 9пт ввода потенциалов блокировки выделения, элемент И вЂ” НЕ 10 с шинами ll -lln вывода потенциалов поиска,. элемент И вЂ” НЕ 12, входами подключенный к шинам 7,— 7„ввода потенциалов выделения, а, выводом к входу элемента И 13, второй вход которого соединен через элемент НЕ 14 с выходом элемента И вЂ” НЕ 15, входы которо- 4О го подключены к шинам 4,— 4пт вывода потенциалов выделения, а третий вход элемента

И 13 соединен через элемент. 16 задержки с выходом элемента И вЂ” НЕ 12, Кроме того, ячейка содержит элемент ИЛИ

17, выход которого подключен к шинам 18>—

18л вывода кода ячейки и к первому входу схемы 19 сравнения, второй вход которой подключен к регистру 20, а выход соединен с (n + 1) -ым входом элемента И вЂ” НЕ 12 so ячейки, выход которого подключен ко входам элементов 16 и НЕ 21 задержки.

Каждый входной блок 1 содержит элемент

И вЂ” НЕ 22, первый вход которого подключен к шине 2 ввода потенциалов поиска, второй вход — к шине 3 контроля, а третий вход подключен к выходу элемента. НЕ 21, элемент И вЂ” HE 23, первый вход которого соеди;

0 4 нен с выходом элемента И--НЕ 22, а выход подключен к первому входу элемента И-HE

24, второй вход которого соединен с выходом элемента И-НЕ 12 ячейки, а выход подключен ко второму входу элемента И вЂ” HE

23 этого же входного блока к шине 4 вывода потенциала выделения.

Выход элемента И вЂ” НЕ 22 каждого входного блока подключен к соответствующему входу элемента И вЂ” НЕ 10 ячейки и другим входам элементов И вЂ” НЕ 22 остальных входных блоков.

Кроме того, каждый входной блок 25 содержит группу элементов И, управляющие входы которой подключены к выходу элемента И вЂ” НЕ 23, информационные входы подключены к шинам 26 ввода кода ячейки, а выходы подключены к соответствующим входам группы элементов ИЛИ 17.

Каждый выходной блок 5 содержит weмент И вЂ” НЕ 27, вход которого соединен через элемент НЕ 28 с шиной 7 ввода потенциала выделения 7, элемент И вЂ” НЕ 29, первый вход которого соединен с выходом элемента НЕ

28 и входом элемента 30 задержки, второй вход соединен с выходом элемента 30 задержки, третий вход соединен с выходом элемента И вЂ” НЕ 27, а выход подключен к первому входу элемента И вЂ” НЕ 31 формирования выходного потенциала блокировки выделения, второй вход которого соединен с выходом элемента И вЂ” НЕ 32, первый вход которого через элемент НЕ 33 соединен с выходом элемента И вЂ” НЕ 27, а второй вход подключен к выходу элемента ИЛИ. 8 ячейки.

Работа ячейки в режиме коммутации не отличается от работы ячейки прототипа. Отличие заключается в том, что в данной ячейке введен дополнительный режим работы — распределение заданий процессорам мультипроцессорной вычислительной системы. Этот режим задается путем установки регистров 20 ячеек системы в определенное фиксированное состояние, а именно в регистры 20 заносится код режима распределения. Конкретное значение кода не имеет значения, например, это может быть двоичный код с единицами во всех значащих разрядах.

Готовые к работе (исправные и незанятые в данный момент) процессоры и источники запросов на использование этих процессоров объединены множеством ячеек по графической схеме информационных связей системы.

Таким образом, в системе имеются ячейкиисточники запросов, ячейки-приемники запросов с готовыми к использованию процессорами и транзитные ячейки.

Процессоры ячеек-приемников записывают в регистры 20 код режима распределения, а

949650 источники запросов, подключенные к ячейкам-источникам, формируют соответственно на шинах 2, — 2п1 и 261 — 26п1 потенциалы поиска и код режима распределения. Транзитные ячейки осуществляют коммутацию потенциалов и кодов от ячеек-источников к ячейкам-приемникам.

Работа ячейки системы в режиме распреде. ления задания, как и в режиме коммутации, состоит из двух этапов: поиска и вьщеления. 10

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

20. Если произошло сравнение кодов, то данная ячейка является приемником запроса и

20 на выходе схемы 19 формируется нулевой потенциал выделения. Отличие в работе данной ячейки заключается в том, что на одну ячейку-источник может приходиться несколько ячеек-приемников. Такая ситуация возникает, 2$ если на один источник запросов приходится несколько готовых к загрузке процессоров.

В этом случае в системе формируется несколько потенциалов вьщеления, что отличаетданную ячейку от ячейки-прототипа.

На этапе выделения взаимодействие потенциалов выделения от разных ячеек-приемников осуществляется на уровне ячейки или на уровне системы ячеек.

Если в данный момент на ячейку поступа3$ ет несколько потенциалов вьщеления по шинам 7> — 7п, то с помощью элементов И вЂ” НЕ

27> — 27п выходных блоков с обратными связями, аналогичных элементам И вЂ” НЕ 22,— 22щ !, входных блоков, выбирается один потенциал

49 вьщеления, а остальные блокируются. Источнику заблокированного потенциала вьщеления по шине 6 выдается сообщение о том, что его потенциал вьщеления заблокирован и соот I ветствуннций процессор остается незагруженным.

4$

Нулевой потенциал блокировки вьщеления формируется элементом И вЂ” НЕ 29 выходного бло ка, инвертируется элементом И вЂ” НЕ 31 и по,ступает на шину блокировки потенциала выделения 6. Элемент 30 задержки исключает

$0 появление на шине 6 просечек (импульсных помех), вызванных переходными процессами в момент срабатывания многоустойчивого триггера, образуемого элементами И вЂ” НЕ 27> — 27п.

Величина задержки элемента 30 должна быть не менее ь3, где Y> — задержка на один »

$$ элемент.

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

7> — 7п ввода существуют потенциалы выделения,а на шинах 4,— 4,П вывода они отсутствуют. Это состояние блокировки потенциалов вьщеления ячейки фиксируется элементом И вЂ” 13.

Элемент 16 задержки устраняет импульсные помехи на выходе элемента И 13 на время переходного процесса. Величина задержки элемента 16 должна быть не менее 3 ii .

Собственный и транзитные сигналы блокировки потенциалов выделения объединяются элементом ИЛИ 8 и поступают на выходные блоки 5> — 5п, в которых с помощью элементов

И вЂ” НЕ 32 осуществляется их коммутация иа одно выходящее направление. Выходящее направление коммутации определяется тем выходным блоком, который в этот момент подключен к шине ввода потенциала выделения.

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

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

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

ВНИИПИ Заказ 5755/39 Тираж 731 Подписное

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

7 9496 с пониженными показателями качества (увеличивается длина канала связи, объединяющего источник запроса и ресурс).

Таким образом, данная ячейка с реализованными в ней новыми функциональными возможностями позволяет строить мультипроцессорные системы, устойчивые к отказам, Фдрмула изобретения

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

И вЂ” HF. i-ro выходного блока, вторые входы четвертых элементов И вЂ” НЕ i-ых выходных блоков подключены к выходу второго элемента ИЛИ ячейки, j-ые входы первого элемента И вЂ” НЕ i-ro выходного блока (j = 2,3, и) подключены к выходам первых элементов И вЂ” НЕ j-ых выходных блоков (j P i) соответственно, m входов второго элемента

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР К 842788, кл. 6 06 F 7/00, 1979 (прототип);