ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ Российский патент 1998 года по МПК G06F7/00 

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

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

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

Целью изобретения является расширение области применения за счет более полного использования резервных ПЯ, что позволяет достичь большей вероятности схранения работоспосбности процессрной матрицы (ПМ) СБИС при одинаковом числе отказавших ПЯ по сравнению с известными.

На фиг. 1 представлена функциональная схема ячейки однородной среды; на фиг. 2 - схема распределения отказов и результат реконфигурации ПМ при четырехкратном сбое: на фиг. 3 - схема распределении отказов и результат реконфигурации ПМ при шестикратном сбое; на фиг. 4 - схема распределение отказов и результат реконфигурации ПМ при восьмикратном сбое; на фиг. 5 - схема распределения отказов при восьмикратном сбое (при этом возникает фатальный отказ ПМ); на фиг. 6 - линии связи ПЯ (i,j) с непосредственными физическими сседями.

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

Первый вход первого элемента ИЛИ сединен с выходом восьмого элемента И, второй вход первого элемента ИЛИ сединен с выходом десятого элемента ИЛИ, третий вход первого элемента ИЛИ сединен с первым входом ячейки, первый выход которой сединен с выходом первого элемента ИЛИ. Второй вход ячейки сединен с первым входом пятнадцатого элемента И и с первым входом второго элемента ИЛИ, второй вход которого сединен с выходом четырнадцатого элемента И и о шестнадцатым входом ячейки, второй выход которой сединен с выходом второго элемента ИЛИ. Первый вход третьего элемента ИЛИ сединен с выходом седьмого элемента ИЛИ. Второй вход третьего элемента ИЛИ сединен с входом 3 ячейки, с прямым входом третьего элемента И и с первым входом первого элемента И. Выход третьего элемента ИЛИ сединен с инверсным входом четвертого элемента И и с первым входом третьего элемента И. выход которого сединен с первым входом двенадцатого элемента и, с первым прямым входом одиннадцатого элемента и, с прямым входом десятого элемента И и с первым прямым входом девятого элемента И, выход которого сединен с девятым выходом ячейки и с первым входом восьмого элемента ИЛИ, выход которого сединен с первым входом седьмого элемента ИЛИ. Шестнадцатый вход ячейки сединен с вторым входом двенадцатого элемента И и с инверсным входом девятого элемента И. Пятнадцатый вход ячейки сединен с третьим входом двенадцатого элемента И, с вторым прямым входом одиннадцатого элемента И, с вторым прямым входом девятого элемента И и с инверсным входом десятого элемента И, выход которого сединен с вторым входом восьмого элемента Или и с восьмым выходом ячейки, четырнадцатый вход которой сединен с четвертым входом двенадцатого элемента И, с третьим прямым входом девятого элемента И и с инверсным входом одиннадцатого элемента И, выход которого сединен с третьим входом восьмого элемента ИЛИ и с седьмым выходом ячейки, четвертый вход которой сединен с инверсным входом второго элемента И, и с первым входом девятого элемента ИЛИ, выход которого соединен с первым входом четвертого элемента ИЛИ, вход которого соединен с третьим выходом ячейки, пятый вход, которой соединен со вторым выходом девятого элемента ИЛИ, с первым входом двадцатого элемента И, с первым входом двадцать первого элемента И, выход которого соединен с первым входом десятого элемента ИЛИ, выход которого соединен с инверсным входом четырнадцатого элемента И. Шестой вход ячейки соединен со вторым входом двадцать первого элемента И, с третьим входом девятого элемента ИЛИ и первым входом девятнадцатого элемента И, выход которого соединен со вторым входом десятого элемента ИЛИ. Седьмой вход ячейки соединен с четвертым входом девятого элемента ИЛИ, с вторым входом девятнадцатого элемента И и вторым входом двадцатого элемента И, выход которого соединен с входом десятого элемента ИЛИ. Восьмой вход ячейки соединен с пятым входом девятого элемента ИЛИ, с первым входом шестнадцатого элемента И с первым входом семнадцатого элемента И, выход которого соединен с четвертым входом десятого элемента ИЛИ. Девятый вход ячейки соединен с шестым входом девятого элемента ИЛИ, первым входом восемнадцатого элемента И и вторым входом шестнадцатого элемента И, выход которого соединен с пятым входом десятого элемента ИЛИ. Десятый вход ячейки соединен с седьмым входом девятого элемента ИЛИ, с вторым входом семнадцатого элемента И и с вторым входом восемнадцатого элемента И, выход которого соединен с шестым входом десятого элемента ИЛИ. Выход девятого элемента ИЛИ соединен о прямым входом четырнадцатого элемента И, выход которого соединен с вторым входом пятнадцатого элемента И, выход которого соединен с прямым входом четвертого элемента И, с вторым входом третьего элемента И и с первым входом тринадцатого элемента И, выход которого соединен с первым входом пятого элемента ИЛИ, выход которого соединен с первым прямым входом пятого элемента И, с первым входом восьмого элемента И, с первым прямым входом седьмого элемента И и с прямым входом шестого элемента И, выход которого соединен с первым входом шестого элемента ИЛИ и с пятым выходом ячейки, одиннадцатый вход которой соединен с вторым входом восьмого элемента И и с инверсным входом пятого элемента И, выход которого соединен с вторым входом шестого элемента ИЛИ и с шестым выходом ячейки, двенадцатый вход которой соединен с вторым прямым входом пятого элемента И, с инверсным входом шестого элемента И, с вторым прямым входом седьмого элемента И и с третьим входом восьмого элемента И. Тринадцатый вход ячейки соединен с третьим входом пятого элемента И, с четвертым входом восьмого элемента И и с инверсным входом седьмого элемента И, выход которого соединен с третьим входом шестого элемента ИЛИ и с четвертым выходом ячейки. Выход шестого элемента ИЛИ с вторым входом седьмого элемента ИЛИ. Выход четвертого элемента И соединен с вторым входом пятого элемента ИЛИ. Выход двенадцатого элемента И соединен с вторым входом тринадцатого элемента И. Выход первого элемента ИЛИ соединен с вторым входом четвертого элемента ИЛИ.

Процессорная матрица СБИС состоит ив определенного количества ПЯ связанных между сбой в регулярную структуру, в которой каждая ПЯ непосредственно связана с четырьмя соседними ПЯ. Если все ПЯ исправны, то ПМ разбита на два подмножества, а именно:
резервный столбец (крайний справа столбец ПМ);
логическую матрицу (ЛМ) (все остальные ПЯ).

Цель повышения отказоустойчивости заключается в поддержании в исправном (нормально функционирующем) состоянии ЛМ при выходе из строя любых ПЯ, входящих в ПМ, за счет использования резервных ПЯ. Восстановление работоспособности ЛМ при возникновении сбоев в ПМ осуществляется за счет переключения коммутаторов, расположенных между ПЯ в ПМ. При этом некоторые коммутаторы могут находиться в таком положении, что ПЯ физически расположенные далеко друг от друга (не смежно) являются логическими соседями. Таким образом ЛМ сохраняет свою структуру. Каждая ПЯ состоит из двух блоков: собственно процессорного элемента (ПЭ), который непосредственно выполняет вычисления и схемы управления реконфигурацией (СУР), которая опрашивает состояние работоспособности рядом расположенных ПЭ и вырабатывает управляющие сигналы для переключения коммутаторов с целью обхода отказавших ПЯ. Перестройка в горизонтальном и вертикальном направлении производится неодинаково. Для исправной ПЯ(i j) возможными логическими соседями будут
по вертикали:
1 - ПЯ(i-1, j+1)
2 - ПЯ(i-1, j)
3 - ПЯ(i-1, j-1)
4 - ПЯ(i, j+1)
5 - ПЯ(i-2, j-1)
6 - ПЯ(i-1, j+3)
7 - ПЯ(i, j+2)
8 - ПЯ(i-2, j)
9 - ПЯ(i-2, j-2)
10 - ПЯ(i-2, j+1)
11 - ПЯ(i-1, j+2)
12 - ПЯ(i, j-1)
13 - ПЯ(i-3, j)
14 - ПЯ(i-2, j+2)
15 - ПЯ(i-1, j-2)
16 - ПЯ(i+1, j-1)
17 - ПЯ(i+1, j)
18 - ПЯ(i-3, j-1)
19 - ПЯ(i-3, j+1)
20 - ПЯ(i-1, j-3)
21 - ПЯ(i+1, j+1)
22 - ПЯ(i, j-2)
23 - ПЯ(i-3, j+2)
по горизонтали
1 - ПЯ(i, j-1)
2 - ПЯ(i, j-2)
3 - ПЯ(i+1, j-1)
4 - ПЯ(i-1, j-1)
5 - ПЯ(i-1, j-2)
6 - ПЯ(i+1, j-2)
7 - ПЯ(i+1, j)
8 - ПЯ(i-1, j)
9 - ПЯ(i-1, j-3)
10 - ПЯ(i+2, j-1)
11 - ПЯ(i+2, j-3)
12 - ПЯ(i+2, j)
13 - ПЯ(i+2, j-2)
14 - ПЯ(i, j-3)
15 - ПЯ(i+2, j+1)
16 - ПЯ(i-1, j+1)
17 - ПЯ(i-2, j-2)
18 - ПЯ(i-2, j-1)
19 - ПЯ(i+2, j-3)
Следовательно, для обеспечения реконфигурации коммутаторы должны иметь возможность создания каналов между ПЯ(i,j) и 19 близ расположенными ПЯ в горизонтальном направлении и 23 ПЯ в вертикальном направлении. Созданные таким образом каналы предназначены для обмена вычислительной информацией необходимой для каждого ПЭ. Кроме этого для нормального функционирования СУР каждой ПЯ необходимо, чтобы все ПЯ являлись самодиагностируемыми, т.е. сами вырабатывали сигнал J(i, j) отказа ПЯ и не должны иметь внутреннюю память. Реконфигурация ПМ должна производиться за время, меньшее одного такта работы СБИС, сохраняя корректность вычислений. Для обеспечения нормального функционирования ПМ необходимо, чтобы сигнал J(i,j) отказа ПЯ(i,j) подавался на вход 4 J(i,j) данной ПЯ(i,j) (фиг. 1) и этот же сигнал должен быть подан на вход 15 I(i+1, j) ПЯ(i-1, j), на вход 14 I(i+1, j+1) ПЯ(i-1, j-1), на вход 16 I(i+1, j-1) ПЯ(i-1, j+1), на вход 12 I(i-1, j) ПЯ(i+1, j), на вход 13 I(i-1, j+1) ПЯ(i+1, j-1), на вход 11 I(i-1, j-1) ПЯ(i+1, j+1). Аналогичным образом должны быть скоммутированы и сигналы отказа от других ПЯ. Если ПЯ находится в самой нижней строке ПМ, то на входы 15, 16, 14 должны быть постоянно поданы единичные потенциалы, что соответствует отказу всех ПЯ расположенных ниже данной строки. Если ПЯ находится в самой верхней строке ПМ, то единичный потенциал подается соответственно на входы 11, 12, 13. Вход 9 ПЯ(i j) соединяется с выходом 8 ПЯ(i-1, j), вход 10 ПЯ(i,j) соединяется с выходом 9 ПЯ(i-1, j+1); вход 8 ПЯ(i,j) соединяется с выходом 7 ПЯ(i-1, j+1); вход 6 ПЯ(i, j) соединяется с выходом 5 ПЯ(i+1, j); вход 5 ПЯ(i,j) соединяется с выходом 6 ПЯ(i+1, j+1); вход 7 ПЯ(i,j) соединяется с выходом 4 ПЯ(i+1, j-1), вход 1 ПЯ(i,j) соединяется с выходом 1 ПЯ(i, j-1); вход 2 ПЯ(i,j) соединяется с выходом 2 ПЯ(i, j-1); вход 3 ПЯ(i,j) соединяется с выходом 3 ПЯ(i,j+1); выход 1 ПЯ(i,j) соединяется с входом 1 ПЯ(i, j+1); выход 2 ПЯ(i,j) соединяется с входом 2 ПЯ(i, j+1); выход 3 ПЯ(i,j) соединяется с входом 3 ПЯ(i, j-1). Для ПЯ составляющих крайний левый столбец ПМ на входы 1,2 и подаются нулевые потенциалы, что соответствует тому, что левее данной ПЯ нет отказавшей ПЯ, захватившей эту строку ПМ. Кроме того для этих же ПЯ на входы 16 и 11 подаются единичные потенциалы, которые указывают на отсутствие ПЯ левее данной в соответствующей строке. Для ПЯ, составляющих самый правый столбец ПМ (крайние правые в каждой отроке ) на выходы 14 и 13 подаются единичные потенциалы. Выходы 1 каждой ПЯ крайнего правого столбца ПМ объединены через элемент ИЛИ и составляют выход матрицы, присутствие единицы на котором означает фатальный отказ матрицы. Этот сигнал на выходе хотя бы одной строки свидетельствует о том, что матричная процессорная СБИС неработоспособна, т. е. реконфигурация при данном распределении отказов невозможна. Каждая строка ПМ дополняется еще одним элементом ИЛИ с прямым входом и одним инверсным входом. На прямой вход этого элемента ИЛИ подается с выхода элемента ИЛИ соответствующего нижней строке (для самой нижней строки на этот вход подается нулевой потенциал) и этот же сигнал подается на вход 3 ПЯ, составляющей крайний правый столбец ПМ. На второй вход элемента ИЛИ (инверсный) подается сигнал с выхода 2 ПЯ, находящейся в самом правом столбце ПМ. Выход элемента ИЛИ соединяется с прямым входом элемента или, соответствующего строке, находящейся над данной.

В статическом режиме, когда все процессорные элементы матрицы находятся в работоспособном состоянии, на всех входах процессорной ячейки присутствуют нулевые потенциалы. Таким образом на входах девятого злемента ИЛИ и на прямом входе четырнадцатого элемента И ноль. На входах семнадцатого, восемнадцатого, девятнадцатого, двадцатого и двадцать первого элементов И также нули, на их выходах нули, которые через десятый элемент ИЛИ поступают на инверсный вход четырнадцатого злемента И. На выходе четырнадцатого элемента И находится нулевой потенциал, который поступает на вход второго элемента ИЛИ, на второй вход которого также поступает ноль со второго входа ячейки. Таким образом на выходе 2 ячейки присутствует нулевой потенциал, который говорит всем ячейкам строки, расположенным справа от данной ячейки, что все ячейки, расположенные слева от данной, включая и данную, безотказны. Если все ячейки строки работоспособны, то с выхода 2 процессорной ячейки, расположенной последней справа в строке, нулевой потенциал поступает на инверсный вход элемента ИЛИ. С выхода этого злемента единичный потенциал поступает на вход 3 процессорной ячейки верхней строки. Этот единичный потенциал пройдя через второй элемент И, на инверсном входе которого присутствует нулевой потенциал от системы самотестирования ПЯ, и через четвертый элемент ИЛИ поступает на выход 3 ПЯ. Таким образом всем ПЯ, расположенным в строках сверху относительно данной ПЯ, будет сообщено о том, что при необходимости захвата соседних ПЯ, можно будет его осуществить в направлении вниз.

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

При отказе в строке двух ПЯ, левая из них будет реконфигурирована описанным выше образом, для другой же ПЯ на ее вход 2 будет поступать единица, которая пройдет через пятнадцатый элемент И, поскольку данная ПЯ также отказала. С выхода пятнадцатого элемента И единица поступает на третий элемент И, четвертый элемент И и тринадцатый элемент И. Если обе отказавшие ПЯ находятся не в самой нижней строке, то на входе 3 данной ПЯ установлен единичный потенциал. Таким образом на выходе третьего элемента И будет единица, которая пройдет через десятый элемент И поскольку на его инверсном входе будет установлен нуль, т.к. нижние ПЯ работоспособны. Таким образом на выходе 8 ПЯ будет установлена единица, которая сообщает о захвате ПЯ, расположенной снизу относительно данной ПЯ. Кроме того единица с выхода десятого элемента И через восьмой элемент ИЛИ и седьмой элемент ИЛИ поступает вход первого элемента И пропуская единичный потенциал со входа 3 ПЯ через первый элемент И и четвертый элемент ИЛИ на вход 3 ПЯ, если он присутствует. Если обе отказавшие ПЯ находятся в самой нижней строке матрицы, то на входы 14, 15, 16 ячейки будут поданы единицы, а также будет отсутствовать единица, на входе 3 ПЯ. Единица с выхода пятнадцатого элемента И пройдет через четвертый элемент И (поскольку на инверсный вход его подан нулевой потенциал) и пятый элемент ИЛИ. Если в соседней сверху строке все ПЯ работоспособны, то на входы 11, 12, 13 ПЯ поданы нули. Таким образом единица с выхода пятого элемента ИЛИ пройдет через шестой элемент И, выход 5 ПЯ, что говорит о захвате ПЯ в верхней строке. Если ПЯ(i-1, j) отказала или захвачена, то произойдет захват ПЯ(i-1, j+1), так как единица с выхода пятого элемента ИЛИ пройдет через седьмой элемент И и попадет на 4 выход ПЯ. Кроме того эта единица пройдя через шестой элемент ИЛИ и седьмой элемент ИЛИ пропустит единичный потенциал со входа 3 ПЯ на выход 3 ПЯ, если он там присутствует.

Рассмотрим работу СУР в динамике. Просмотр ПЯ начинается снизу-вверх и слева-направо. При обнаружении в строке не более одной отказавшей или захваченной ячейки относительно нее происходит горизонтальная перестройка, т.е. логические номера ПЯ строки, стоящие правее отказавшей (захваченной) ПЯ, сдвигаются на один вправо, используя при этом для последней логической ПЯ строки резервную ПЯ этой строки. В случае появления в строке нескольких отказавших или захваченных ПЯ, также, как и в алгоритме ограниченного захвата первой слева отказавшей (захваченной) ПЯ присваивается статус горизонтальной перестройки, а остальным - вертикальной. Причем если ниже анализируемой строки осталось n резервных ПЯ, то с целью более полного использования резерва первым n ПЯ присваивается статус перестройки вертикально-вниз, а остальным вертикально-вверх. Если на пути перестройки в вертикальном направлении оказывается отказавшая ПЯ, то статус перестройки вертикально-вверх изменяется на вертикально-вверх-вправо, если это возможно, и вертикально-вверх-влево - в противном случае. Аналогичные изменения статуса реконфигурации происходит и при направлении вертикально вниз на вертикально-вниз-влево.

Фатальный отказ матричной структуры (фиг. 5) возможен в одном случае, а именно, если в строке 1 произошло не менее двух отказов и для второго из них невозможна перестройка ни в одном из шести направлений (вертикально-вниз, вертикально-вниз-вправо, вертикально-вниз-влево, вертикально-вверх, вертикально-вверх-вправо, вертикально-вверх-влево).

На фиг. 2 изображен случай четырехкратного отказа ПЯ, который привел бы известную ячейку однородной среды с алгоритмом двунаправленного свободного захвата к фатальному отказу, но в предлагаемой такого не происходит. Схема второй отказавшей ячейки пятой строки вырабатывает сигнал Iy(5.4), что приводит к захвату ячейки из четвертой строки, находящейся справа по отношению к столбцу с отказавшей ячейкой. Таким образом данное распределение отказов успешно парировано, а ЛМ осталась работоспособной.

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

В известной матрице фатальный отказ возникает и в случае появления восьмикратного отказа, (в матрице отказали сразу восемь ПЯ) распределение отказов которого приведено на фиг. 4, В этом случае 6 строка матрицы схемы управления ПЯ (5.5) будет переведена во второй режим работы (направление вниз) и в то же время схемой управления ПЯ (6,4) будет переведена в первый режим работы (направление вверх). Таким образом возникает конфликт, заключающийся в одновременном требовании перестройки для шестой строки как вверх, так и вниз, что означает исчерпание резерва для данной строки и фатальный отказ матрицы. Предлагаемая же ячейка позволяет реконфигурировать указанное распределение отказов, где производится реконфигурация, достаточно гибко за счет большого охвата, имеющихся в наличии резервных ячеек. Фатальный отказ (FF) в предлагаемой матрице возникает только при наличии восьмикратного сбоя, распределение отказов которого приведено на фиг. 5.

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

Если все элементы матрицы находятся в исправном состоянии (фиг. 1), то на вход 4 соответствующей ячейки поступает сигнал I(i,j) от схемы самодиагностики процессорного элемента данной ячейки. Исправному состоянию ПЭ соответствует логический ноль. Этот же сигнал, кроме того, поступает на вход 12 I(i-1, j) ПЯ, находящейся внизу в том же столбце, что и данная ПЯ, а также на вход 13 I(i-1, j+1) ПЯ, находящейся внизу в столбце справа по отношению к данной, на вход 11 I(i-1, j-1) ПЯ, находящейся внизу в столбце слева по отношению к данной, на вход 15 I(i+1, j) ПЯ, находящейся сверху в том же столбце, что и данная, на вход 14 I(i+1, j+1) ПЯ, находящейся сверху в столбце справа, на вход 16 I(i+1, j-1) ПЯ, находящейся сверху в столбце слева. Кроме того, выход 8 Iz(i+1, j) данной ПЯ соединен непосредственно с входом 9 Iz(i-1, j) ПЯ, находящейся внизу в том же столбце, что и данная, выход 7 Iz(i+1, j+1) данной ПЯ соединен с входом 8 Iz(i-1, j-1) ПЯ, находящейся внизу в столбце справа, выход 9 Iz(i+1, j-1) соединен с входом Iz(i-1, j+1) ПЯ, находящейся внизу в столбце слева, вход 9 Iz(i-1, j) данной ПЯ, соединен с выходом 8 Iz(i+1, j) ПЯ, находящейся сверху в том же столбце, что и данная, вход 10 Iz(i-1, j+1) данной ПЯ соединен с выходом 9 Iz(i+1, j-1) ПЯ, находящейся сверху в столбце справа, вход 8 I(i-1, j-1) ПЯ соединен с выходом 7 Iz(i+1, j-1) ПЯ, находящейся сверху в столбце слева, входы 1 FF(i, j-1), 2 Ix(i, j-1), 3 А(i, j+1) данной ПЯ соединены соответственно с выходами 1 FF(i, j), 2 Ix(i, j), 3 А(i, j) ПЯ, находящейся слева от данной ПЯ в той же строке, выходы 1 FF(i,j), 2 Ix(i,j), 3 А(i, j) соединены соответственно с входами 1 FF(i,j-1), 2 Ix(i, j-1), 3 А(i, j+1) ПЯ, находящейся справа от данной ПЯ в той же строке.

На входы 11 I(i-1, j-1), 12 I(i-1, j), 13 I(i-1, j+1) всех ПЯ самой верхней строки матрицы подаются логические единицы, которые информируют о невозможности реконфигурации вверх, на входы 16 I(i+1, j+1), 15 I(i+1, j). 14 I(i+1, j+1) всех ПЯ самой нижней строки матрицы также подаются логические единицы, на входы 1 FF(i, j-1) и 2 Ix(i, j-1) самого левого столбца матрицы подаются логические нули. Выходы 1 FF(i,j) самого правого столбца матрицы заведены на схему ИЛИ и в результате появляется сигнал фатального отказа матрицы. Каждая строка матрицы имеет по одному дополнительному двухвходовому элементу ИЛИ с одним инверсным входом. Инверсный вход соответствующего элемента каждой строки соединен с выходом 2 Ix(i,j) самого правого столбца матрицы, а второй вход соответствующего элемента ИЛИ соединен с выходом аналогичного элемента нижней строки. На второй вход элемента ИЛИ соответствующего самой нижней строке подается логический нуль.

Рассмотрим подробно работу схемы управления ПЯ (фиг. 1) при возникновении отказов. В случае одного отказа ПЭ (i,j) на вход 4 I(i,j) ПЯ (i,j) поступает единичный потенциал (все ПЭ являются самотестируемыми). Кроме того этот единичный потенциал поступает на соответствующие входы трех ПЯ, обслуживающих вышерасположенные ПЭ и входы трех ПЯ, обслуживающих нижерасположенные ПЭ.

Единичный потенциал с входа 4 I(i,j), проходя девятый элемент ИЛИ и четырнадцатый элемент И поступает на вход второго элемента ИЛИ. (Если среди окружающих ПЯ нет ни одной отказавшей, кроме ПЯ(i,j), то на выходе десятого элемента ИЛИ будет сформирован нулевой потенциал, который, попадая на инверсный вход четырнадцатого элемента И, открывает его.) Поскольку левее ПЯ(i, j) отказов нет, то на вход 2 ПЯ(i,j) поступает нулевой потенциал, который закрывает пятнадцатый элемент И, следовательно изменений сигналов на остальных выходах не происходит, а формируется лишь единичный сигнал на информационном выходе 2 Ix(i,j) ячейки. Этот сигнал, проходя через все ячейки, справа стоящие от данной, информируют их о том, что в одной из ячеек, стоящих слева, горизонтальная перестройка произведена, т.е. резервная ПЯ (точнее ПЭ) данной строки i уже использована, и второй уже такой быть не может.

В случае, если произошел отказ ПЭ (i,j), а на вход 2 Ix(i,j-1) соответствующей ячейки уже поступил единичный потенциал (отказали два ПЯ одной строки), то горизонтальная перестройка должна производиться относительно крайнего левого ПЯ. Данная же ПЯ (i,j) должна произвести вертикальную перестройку. Если ниже данной строки 1 есть еще хотя бы одна строка, то в ней на выходе 2 Ix(i,j) присутствует нулевой потенциал, сообщающий, что отказавших ПЯ в этой строке нет, который, пройдя через инверсный вход элемента ИЛИ, передает на вход 3 крайней справа ячейки строки 1 единичный потенциал. Если процессорные ячейки, расположенные правее ПЯ (i,j), работоспособны, то они пропустят единичный потенциал со своего входа 3 на выход 3 следующим образом: на вход 4 I(i,j) поступает нулевой потенциал от схемы самотестирования, который проходит на инверсный вход второго элемента И, пропуская единичный потенциал со входа 3 через четвертый элемент ИЛИ на выход 3. Таким образом на входе 3 ПЯ (i,j) присутствует единичный потенциал, который, пройдя третий элемент ИЛИ поступает на вход третьего элемента И. С другой стороны единичный потенциал от схемы самотестирования ПЯ (i,j), через вход 4, проходя через девятый элемент ИЛИ, четырнадцатый элемент И, пятнадцатый элемент И (так как на второй вход этого пятнадцатого элемента И поступает единичный потенциал с входа 2 ПЯ) и третий элемент И поступает на вход девятого элемента И, десятого элемента И, одиннадцатого элемента И и двенадцатого элемента И. В зависимости от состояния ПЯ в строке i+1 единичный потенциал поступает на выход 8, либо на выход 7, либо на выход 9. Если ПЯ(i+1, j) работоспособна, то на выходе 8 появляется единица, сообщая ПЯ(i+1, j) о ее захвате сверху, поступая на ее вход 9 Iz(i-1,j). Если же ПЯ(i+1, j) неработоспособная то на входе 15 ПЯ(i, j) присутствует единичный потенциал, который запирает десятый элемент И, в то же время открывает одиннадцатый элемент И и на выходе 7 появляется единица, сообщая ПЯ(i+1, j-1) о ее захвате сверху слева, поступая на ее вход 8 Iz(i-1, j-1). В случае, если неработоспособны две ячейки ПЯ(i+1, j) и ПЯ(i+1, j+1), то единицы с входов 15, 14 ПЯ(i,j) запирают десятый элемент И и одиннадцатый элемент И, пропуская единицу через девятый элемент И на вход 9 I(i+1, j-1), сообщая ПЯ(i+1, j-1) о ее захвате сверху справа, поступая на ее вход 10 I(i-1, j+1).

Если три ПЯ, расположенные непосредственно под ПЯ(i, j) неработоспособны или в строках, расположенных ниже строки i полностью использованы все резервные ПЯ, то единица с выхода пятнадцатого злемента И через четвертый элемент И или тринадцатый элемент И, проходя через пятый элемент ИЛИ, поступает на вход пятого элемента И, шестого элемента И, седьмого элемента И, восьмого элемента И. В зависимости от работоспособности ПЯ, расположенных над ПЯ(i, j), единица появляется на одном из выходов 5, 6 или 4. Если ПЯ(i-1, j) работоспособна, то на вход 12 ПЯ(i, j) поступает нулевой потенциал, который, попадая на инверсный вход шестого элемента И, пропускает единицу на выход 5 Iy(i-1, j) ячейки (i, j), сообщая ПЯ(i-1, j) о ее захвате снизу, поступая на ее вход 6 Iy(i+1, j). Если ПЯ(i-1, j) неработоспособна, то на вход 12 поступает единица, которая запирает шестой элемент И, пропуская на вход седьмого элемента И единицу. Единица с выхода седьмого злемента И поступает на выход 4 Iy(i-1, j+1) ячейки (i, j), сообщая ПЯ(i-1, j+1) о ее захвате снизу, поступая на ее вход 7 I(i+1, j-1). Если обе ПЯ(i-1, j) и ПЯ(i-1, j+1) неработоспособны, то соответствующие единицы поступают на входы 12 и 13 ПЯ(i, j), которые запирают шестой элемент И и седьмой элемент И и открывают пятый элемент И, с выхода которого единица поступает на выход 6 Iy(i-1, j-1) ПЯ(i, j), сообщая ПЯ(i-1, j-1) о ее захвате снизу, поступая на ее вход 5 I(i+1, j+1).

Cигнал фатального отказа FF(i,j) появляется на выходе первого элемента И в случае появления единичного потенциала на выходе пятого элемента ИЛИ, что соответствует требованию вертикальной перестройки вверх и одновременного появления единиц на входах 11, 12, 13 ПЯ(i,j), что соответствует невозможности реконфигурации вверх. Полученная единица с выхода восьмого элемента И попадает через первый элемент ИЛИ на выход 1 ПЭ(i,j). Появление единицы на выходе 1 информирует о фатальном отказе при реконфигурации матрицы. Единица фатального отказа может быть сформирована также десятым элементом ИЛИ в случае попытки одновременного захвата ПЯ(i,j) сверху или снизу, если на входы 8, 9, 10 ПЯ(i, j) или на входы 5, 6, 7 ПЯ(i,j) придут одновременно два единичных потенциала.

Изобретение относится к вычислительной технике и, в частности, к архитектурам перестраиваемых матричных процессорных СБИС, использующих структурную перестройку (реконфигурацию), т.е. замену отказавших процессорных ячеек (ПЯ) на резервные. Изобретение состоит из 10 элементов ИЛИ и 21 элемента И. Сущность изобретения заключается во введении дополнительных функций в схему управления реконфигурацией, позволяющих увеличивать число направлений перестройки (обхода) и за счет этого расширить область успешно реконфигурируемых вариантов появления большого числа отказов. Новизна изобретения заключается в возможности переназначения логических адресов процессорных ячеек не только в горизонтальном направлении и в направлениях вертикально вверх и вертикально вниз, но и в диагональных направлениях (вниз-вправо, вниз-влево, вверх-вправо, вверх-влево). 6 ил.

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