Однородная коммутирующая сеть

 

Изобретение относится к вычислительной технике, позволяет повысить вероятность безотказной работы однородной вычислительной структуры. Для этого однородная коммутирующая сеть содержит 2 К элементов И, 2 К элементов ИЛИ и матрицу коммутирующих ячеек размером К строк и М ctoлбцoв (М - максимально допустимое количество неисправных процессорных элементов; среди любых подряд пронумерованных А процессорных элементов, К - количество процессорных элементов, образующих вычислительную структуру). Коммутирующая сеть, отключая неисправные процессорные элементы, сохраняет между исправными регулярную структуру элек тронных связей, 1 з.п. 4)-лы. 5 ил. со о ;о о со 00

СОЮЗ СОВЕТСКИХ.

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

РЕСПУБЛИН

„„SU„, 130 (51)4 G 06 F 15 16

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3988228/24-24 (22) 06. 12.85 (46) 07,05.87. Бюл. У 17 (72) А.С.Ильин (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 661793, кл. Н 03 К 17/00, 1979.

Авторское свидетельство СССР

У .1164713, кл. G 06 F 11/20, 1982. (54) ОДНОРОДНАЯ КОММУТИРУЮЩАЯ СЕТЬ (57) Изобретение относится к вычислительной технике, позволяет повысить вероятность безотказной работы однородной вычислительной структуры. Для этого однородная коммутирующая сеть .содержит 2 К элементов И, 2 К элементов ИЛИ и матрицу коммутирующих ячеек размером К строк и М столбцов (М— максимально допустимое количество неисправных процессорных элементов среди любых подряд пронумерованных

А процессорных элементов, К вЂ” количество процессорных элементов, образующих вычислительную структуру).

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

130903

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

Целью изобретения является повьппение надежности.

1О

На фиг. 1 представлена структурная схема однородной коммутирующей сети для блочного варианта реализации; на фиг. 2 — функциональная схема однородной коммутирующей сети; на фиг. 3 — функциональная схема коммутирующей ячейки; на фиг, 4 и 5 — схемы информационных потоков между коммутируемыми процессорными элементами через коммутирующую сеть, если перечеркнутые процессорные элементы считать неисправными.

Коммутирующая сеть (фиг. 1) для однородной вычислительной структуры (среды) содержит Н коммутирующих блоков 1 (Н вЂ” количество периодов в требуемом наборе регулярных однонаправленных связей среди К пронумерованных коммутируемых процессорных элементов).

Коммутирующий блок 1 (фиг.2) со.держит первую группу из элементов И 2, первую группу из К элементов ИЛИ 3, вторую группу из К элементов ИЛИ 3, вторую группу из К элементов ИЛИ 5 и мат-. рицу коммутационных ячеек 6 размером

К строк и M столбцов (M — максимально допустимое количество неисправных процессорных элементов среди любых подряд пронумерованных А процессорных ! .:элементов) . Каждая ячейка 6 (фиг. 3) содержит элементы И 7-9, элементы

ИЛИ-НЕ 10-12, элемент ИЛИ 13 и элемент НЕ 14. Нумерация входов и выходов коммутирующей сети (коммутирующих блоков): 15 и 16 - входы для подключения соответственно первого и вто. рого управляющих входов процессорных элементов, 17 — входы для подключения информационных выходов процессорных элементов, 18 — выходы для подключения информационных входов процессорных элементов, 19 — выход состояния .коммутирующей сети, 20 — выход состояния коммутирующего блока, 21 — вход коммутирующего блока. 55

Дополнительный вариант предлагаемой коммутирующей сети отличается от основного тем, что каждый коммутирую3 2 щий блок путем дополнительных соединений преобразован к замкнутой кольцевой структуре, соответствующей данному коммутирующему блоку. На чертежах эти соединения не показаны, так как они строятся аналогично соединениям между Е-й и (Е+1)-й строками ячеек 6 и соответствующими им элементами И 2, ИЛИ 3 и И 4 °

Третьи входы элементов ИЛИ 13 коммутирующих ячеек 6 первого столбца в формуле изобретения не упоминаются, но их наличие возможно в практической реализации, когда коммутирующие ячейки делаются в виде унифицированных микросхем, Эти избыточные входы, как показано на фиг. 2, должны бы ь обнулены.

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

Для повышения канальности связей достаточно увеличить количество входных элементов И 2, выходных элементов ИЛИ 3 (фиг. 2), элементов И 7-9, ИЛИ 13 (фиг. 3), а также соответствующих этим элементам соединений между собой и с другими элементами.

Однородная вычислительная структура (среда) синтезируется с помощью предлагаемой коммутирующей сети следующим образом.

Если информационный выход Е-ro процессорного элемента подключить к (Е+Н)-му входу 17, а Е-й выход 18 подключить к информационному входу

Е-го процессорного элемента, установить уровень " 1" на каждом из управ- ляющих входов 15 и обнулить управляющие входы 16 коммутирующей сети, то .ячейки б, работая в режиме передачи информации в горизонтальном направлении (вентили И 8 открыты, вентили И 7, 9 закрыты), сформируют между процессорными элементами структуру электронных связей в виде регулярного ориентированного графа.

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

3 13090

В каждой ячейке 6 элемент ИЛИ 13 принимает информацию с любого из трех направлений: горизонтального, вертикального и леводиагонального. Эта информация передается дальше в одном из этих трех направлений через вентили И 7-9. Управление этими вентилями происходит с помощью элементов ИЛИ-НЕ

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

14 (и на первом выходе элемента ИЛИНЕ 117 установлен уровень "0", то информация передается вниз по вертикали через элемент И 7, а соседней сле-25 ва — снизу ячейке 6 передается с выхода элемента ИЛИ-НЕ 11 сигнал запрета передачи информации по отношению к ней направо; если на входе элемента НЕ 14 установлен уровень "1", то, 30 пройдя двойную инверсию через элемент НЕ 14 и элемент ИЛИ-НЕ 10, он откроет вентиль И 9, передающий информацию в направлении направо-вниз, и запретит соседним справа и снизу 35 ячейкам 6 передавать информацию по отношению к ним соответственно вниз и направо.

Если Е-й процессорный элемент вы40 шел из строя (или перешел в режим самоконтроля), то Е-й управляющий вход 15 обнуляется, а на (Е-Н)-м управляющем входе 16 устанавливается

"1". При. этом (Е-Н)-я ячейка 6 М-го

45 столбца получает запрет передачи информации направо неисправному Е-му процессорному элементу, перейдет в режим передачи информации вниз и передаст соседней слева-снизу ячейке 6 сигнал запрета передачи информации по отношению к ней направо. Эта ячейка аналогично перейдет в режим передачи информации вниз, и так далее по диагонали до (Е+Н-1)-й ячейки 6 первого столбца, которая, имея также от (Е+Н)-rn управляющего входа 15 запрет передачи информации вниз, перейдет в режим передачи направо-вниз

33 4 и передаст соседней снизу коммутирующей ячейке 6 сигнал запрета передачи информации по отношению к ней направо.

Эта ячейка 6 аналогично перейдет в режим передачи информации направовниз, и так далее по вертикали до

l (Е-1)-й ячейки 6 первого столбца, которая перейдет в режим передачи информации вниз, имея на то разрешение от Е-го управляющего входа 15 уровень

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

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

Таким образом, получены представленные на фиг. 4 и 5 в качестве примеров схемы информационных потоков между процессорными элементами 22 через однородную коммутирующую сеть при наличии неисправных (перечеркнутых) процессорных элементов. Эти схемы представлены для случая А=6, М=З..

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

Каждый случай выхода из строя коммутируемого процессорного элемента 22 приводит к изменению режимов передачи информации в А ячейках 6 по одной в каждой из А строк ячеек. Поэтому длина строки M ячеек 6 выбирается как максимально допустимое количество неисправных процессорных элементов среди любых подряд пронумерованных А процессорных элементов.

Когда количество неисправных процессорных элементов среди некоторых А подряд пронумерованных процессорных элементов достигает М, то некоторые ячейки 6 .М-ro столбца переходят .в

5 13090 режим передачи информации направовниз через вторые входы выходных элементов ИЛИ 3.

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

И 4 проверки и ИЛИ 5 проверки всех 15 коммутирующих блоков и сигнализируется на выходе 19 состояния коммутирующей сети уровнем "1", который означает, что коммутирующая сеть исчерпала свои возможности сохранять регуляр- 20 ную структуру электронных связей .между исправными процессорными элементами. формула изобретения

1. Однородная коммутирующая сеть, содержащая М столбцов, где М вЂ” максимально допустимое количество неисправных процессорных элементов. среди 30 любых А подряд пронумерованных процессорных элементов, из К коммутационных ячеек, причем каждая коммутационная ячейка содержит два элемента И, элемент ИЛИ и элемент НЕ, выход первого элемента И (Е, P)-й коммутационной ячейки (Е=1, ..., К-I P=1

M-1) подключен к первому входу элемента ИЛИ (Е+1, P)-й коммутационной ячейки, выход элемента ИЛИ каждой 40 коммутационной ячейки подключен кпервым входам. первого и второго элементов И той же коммутационной ячейки, выход первого элемента И (Е, М)-й коммутационной ячейки подключен к перво- 45 му входу элемента ИЛИ (E+1 M)-й ком,мутационной ячейки, выход второго элемента И (Е,Р)-й коммутационной ячейки подключен к.второму входу элемента ИЛИ (Е, Р+1)-й коммутационной 50 ячейки, отличающаяся тем, что, с целью повьппения надежности, в нее введены две группы элементов И, две группы элементов ИЛИ, а в каждую коммутационную ячейку введены три 55

I элемента ИЛИ-НЕ и третий элемент И, причем выход третьего элемента ИЛИ-HE калщой коммутационной ячейки подключен к второму входу второго элемента И, первому входу второго элемента

ИЛИ-НЕ и к первому входу первого элемента ИЛИ-НЕ той же ячейки, второй вход которого подключен к выходу эле- мента НЕ той же ячейки, выход элемента ИЛИ каждой ячейки подключен к первому входу третьего элемента И той же ячейки, выход второго элемента ИЛИ-НЕ каждой коммутационной ячейки подключен к второму входу первого элемента И той же коммутационной ячейки, выход первого элемента ИЛИ-НЕ каждой коммутационной ячейки подключен к второму входу третьего элемента И той же коммутационной ячейки, вход элемента НЕ каждой коммутационной ячейки подключен к второму входу второго элемента ИЛИ-НЕ той же коммутационной ячейки, первый вход (Е+Н)-го элемента И первой группы, где Н вЂ” количество параллельных информационных каналов однородной коммутирующей сети, подключен к входу элемента НЕ (Е+Н-1,1)-й коммутационной ячейки и является входом для подключения первого управляющего выхода Е-го процессорного элемента, второй вход (Е+Н)-го элемента И первой группы является входом для подключения информационного выхода Е-го процессорного элемента, выход Е-го элемента И первой группы подключен к второму входу элемента

ИЛИ (Е, 1)-й коммутационной ячейки, выход первого элемента ИЛИ-НЕ (Е,М)-й коммутационной ячейки подключен к второму входу третьего элемента ИЛИНЕ (Е+1,М)-й коммутационной ячейки и к первому входу (Е+1)-го элемента И второй группы, выход первого элемента ИЛИ-НЕ (Е,Р)-й коммутационной ячейки подключен к входу элемента НЕ (Е, Р+1)-1 коммутационной ячейки и второму входу третьего элемента ИЛИНЕ (Е+1,Р)-й коммутационной ячейки, выход третьего элемента И (Е,Р)-й коммутационной ячейки подключен к третьему входу элемента ИЛИ (Е+1, Р+1)-й коммутационной ячейки, выход второго элемента ИЛИ-НЕ (Е, Р+ 1)-й коммутационной ячейки подключен к первому входу третьего элемента ИЛИНЕ (Е+ 1, Р)-й коммутационной ячейки, первый вход третьего элемента ИЛИ-НЕ (E, М)-й коммутационной ячейки является входом для подключения второго управляющего выхода Е-го процессорно- го элемента и подключен к второму

"О"

° °

1б

Фиг.1

7 13090 входу Е-го элемента И второй группы, выход которого подключен к второму входу Е-ro элемента ИЛИ второй группы, выход которого подключен к первому входу (Е+1)-го элемента ИЛИ второй группы, выход К-ro элемента ИЛИ второй группы является выходом состояния системы, выход второго элемента И (Е, М) -й коммутационной ячейки . подключен к второму входу Е-го эле- 10 мента ИЛИ первой группы, выход которого является выходом для подключения информационного входа Е-го процессорного элемента, а первый вход Е-го элемента.ИЛИ первой группы соединен 15 с выходом третьего элемента И (Е-1, М)-й коммутационной ячейки.

2. Сеть по п. 1, о т л и ч а ющ а я с я тем, что вход элемента НЕ, выход первого элемента И, первого 20 элемента ИЛИ-НЕ и третьего элемента И (К, 1}-й коммутационной ячейки подключены к первому входу первого элемента И первой группы, к первому входу элемента ИЛИ, второму входу треть-25 его элемента ИЛИ-Н1 (1,1)-й коммутационной ячейки и к третьему входу элемента ИЛИ (1,2)-й коммутационной ячейки соответственно, выходы второ33 8 го и первого элементов ИЛИ-НЕ и первого и третьего элементов, И (К,P)-й коммутационной ячейки подключены к первому входу третьего элемента ИЛИНЕ (1, P-1)-й коммутационной ячейки, к первому входу элемента ИЛИ и второму входу элемента ИЛИ-НЕ (1, P)-й коммутационной ячейки и к третьему входу элемента ИЛИ (1, Р+1)-й коммутационной ячейки соответственно, выход второго и первого элементов HJIHHE, первого и третьего элементов И (К, М)-й коммутационной ячейки подключены к первому входу третьего элемента ИЛИ-НЕ (1, М-1)-й коммутационной ячейки, к первому входу элемента ИЛИ и второму входу третьего элемента ИЛИ-НЕ (1, М)-й коммутационной ячейки и к первому входу первого элемента ИЛИ первой группы соответственно, причем первый вход Т-го элемента И первой группы (Т=1,...,Н) являе гся входом для подключения первого управляющего выхода (К-Н+Т)-ro процессорного элемента, а второй вход

Т-го элемента И первой группы является входом для подключения информационного выхода (К-Н+Т)-го процессорного элемента.

1309033

1309033

Фиг.4

1309033

Составитель А.Мишин

Редактор А.Ворович Техред M.Ходанич Корректор C,Шекмар

Заказ 1800/42 : Тираж 673 Подписное

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

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

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