Однородная коммутирующая сеть Советский патент 1987 года по МПК G06F15/163 

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

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

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

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

Коммутирующий блок 1 (фиг.2) со- держит первую группу из элементов И 2 первую группу из К элементов ИЛИ 3, вторую группу из К элементов ИЛИ 3, вторую группу из К элементов ИДИ 5 и матрицу коммутационных ячеек 6 размером К строк и М столбцов (М - максимально допустимое количество неисправных процессорных элементов среди любых подряд пронумерованных А процессорных |элементов) . Каждая ячейка 6 (фиг. 3) содержит элементы И 7-9, элементы ИЛИ-НЕ 10-12, элемент ИЛИ 13 и элемент НЕ 14. Нумерация входов и выходов коммутирующей сети (коммутирующих блоков): 15 и 16 - входы для подключения соответственно первого и вто- рого управляющих входов процессорных элементов, 17 - входы для подключения информационных выходов процессорных элементов, 18 - выходы для подключения информационных входов процессорных элементов, 19 - выход состояния коммутирующей сети, 20 - выход состояния коммутирующего блока 21 - вход коммутирующего блока.

Дополнительный вариант предлагаемой коммутирующей сети отличается от основного тем, что каждый коммутирую

5

0

5

0

5

0

5

0

5

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

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

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

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

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

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

3130

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

нимают, анализируют и передают сигна-tO от Е-го управляющего входа 15 уровень

О, на котором закрывает также Е-й

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

Воздействие другой пары управляющих сигналов 15 и 16, соответствующих вышедшему из строя процессорному элередается в одном из двух других на- 20 менту, приведет к изменению режимов правлений: если на входе элемента НЕ передачи информации в последователь- 14 (и на первом выходе элемента ИЛИ- ности ячеек 6, -отсчитываемых анало- НЕ 11 установлен уровень О, то информация передается вниз по вертикагичным образом с той лишь разницей, что если ячейки 6 первого столбца уж

ли через элемент И 7, а соседней сле- изменили режим передачи информации.

ва - снизу ячейке 6 передается с выхода элемента ШШ-НЕ 11 сигнал запрета передачи информации по отношению к ней направо; если на входе элемента НЕ 14 установлен уровень l, то, пройдя двойную инверсию через элемент НЕ 14 и элемент ИЛИ-НЕ .10, он откроет вентиль И 9, передающий информацию в направлении направо-вниз, и запретит соседним справа и снизу :Ячейкам 6 передавать информацию по отношению к ним соответственно вниз и направо.

30

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

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

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

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

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

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

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

гичным образом с той лишь разницей, что если ячейки 6 первого столбца уже

изменили режим передачи информации.

0

0

5

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

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

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

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

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

0

5

5130

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

Пример схемы информационных потоков для такой ситуации представлен на фиг. 5. При этом ра вторых входах некоторых элементов И 4 проверки по

является уровень 1 , означающий требование сохрйнения работоспособности

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

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

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

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

щей сети уровнем 1 , который означает, что коммутирующая сеть исчерпала

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

тами.

Формула изобретения

25

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

элемент ИЛИ и элемент НЕ, выход пер- 35 выход первого элемента ИЛИ-НЕ (Е,М)-й вого элемента И (Е, Р)-й коммутацион- коммутационной ячейки подключен к ной ячейки (, ..., К-1; ,..., М-1) подключен к первому входу элемента ИЛИ (E+l, Р)-й коммутационной ячейки, вькод элемента ИЛИ каждой 40 второй группы, выход первого элемен- в;оммутационной ячейки подключен к пер- та ИЛИ-НЕ (Е,Р)-й коммутационной вым входам перваго и второго элементов И той же коммутационной ячейки, выход первого элемента И (Е, М)-й коммутационной ячейки подключен к перво- 45 НЕ (Е+1,Р)-и коммутационной ячейки, му входу элемента ИЛИ (Е+1,М)-й ком- выход третьего элемента И (Е,Р)-й

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

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

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

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

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

каждой коммутационной ячейки подклю- чен к второму входу первого элемвн- та И той же коммутационной ячейки,

каждой коммутационной ячейки подклю- чен к второму входу первого элемвн- та И той же коммутационной ячейки,

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

мента НЕ каждой коммутационной ячейки подключен к второму входу второго элемента ИЛИ-НЕ той же коммутационной

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

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

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

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

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

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

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

входу Е-го элемента И второй группы, выход которого подключен к второму входу Е-го элемента ИЛИ второй группы, выход которого подключен к первому входу (Е+О-ГО элемента ИЛИ вто- рой группы, выход К-го элемента ИЛИ второй группы является выходом состояния системы, выход второго элемента И (Е, М)-й коммутационной ячейки подключен к второму входу Е-го эле- мента ИЛИ первой группы, выход которого является выходом для подключения информационного входа Е-го процессорного элемента, а первый вход Е-го элемента ИЛИ первой группы соединен с выходом третьего элемента И (E-l, М)-й коммутационной ячейки.

2. Сеть поп. 1,отличаю- щ а я с я тем, что вход элемента НЕ, выход первого элемента И, первого элемента ИЛИ-НЕ и третьего элемента И (К, 1)-и коммутационной ячейки подключены к первому входу первого элемента И первой группы., к первому входу элемента ИЛИ, второму входу третьего элемента ИЛИ-НЕ (1,1)-и коммутационной ячейки и к третьему входу элемента ИЛИ (1,2)-и коммутационной ячейки соответственно, вькоды второ 0

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

9иг.1

пп

2Г

W

фиг.З

U

L

Cl (-J1

L

XiR

L

Составитель А.Мишин Редактор А.Ворович Техред М.Ходанич Корректор С.Шекмар

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

ФиаУ

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