Ячейка однородной среды Советский патент 1992 года по МПК G06F15/16 

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

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

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

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

ИЛИ и первый-шестой элементы И, причем вход горизонтального отказа устройства соединен с первым входом первого и второго элемент а ИЛИ, первым инверсным входом первого элемента И, а также инверсным входом второго элемента И, выход которого соединен со вторым входом первого эле мента ИЛИ, выход которого соединен с первым входом третьего элемента И вход-выход обобщенного горизонтального отказа соединен со вторым инверсным входом первого элемента И, выход которого соединен со вторым инверсным входом первого элемента И, выход которого соединен с первым входом третьего элемента ИЛ1/1, а также вход-выход обобщенного горизонтального отказа соединен с прямым входом второго элемента И, вход отказа ПЯ устройства соединен с первым входом четвертого элемента ИЛИ, выход которого соединен со вторым входом третьего элемента И, выход которого является выходом вертиg

00

10

:оо

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

Недостатком известного устройства является то, что просмотр неисправных ПЯ и их перестройка производится только снизу-вверх Таким образом отказ всего двух ПЯ, на расположенных в верхней строке, приводит к фатальному отказу, отказу всей матрицы. Фатальный отказ возникает и тогда, когда находится строка I, в которой более одной неисправной или захваченной ячейки (i, j), где j - номер столбца, в котором находится ПЯ, которой соответствует ячейка (1-1), т.е. отказ всего четырех ПЯ приводит к фатальному отказу даже при наличии достаточного количества резервных ПЯ.

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

На фиг,1 представлена функциональная схема ячейки однородной среды; на фиг.2 и 3 - варианты структурной перестройки матричной процессорной СБИС по алгоритму двунаправленого свободного захвата.

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

В режиме Снизу-вверх ячейка реализует алгоритм свободного захвата, работа ее полностью аналогична работе известной. Просмотр ПЯ начинает снизу-вверх и слеванаправо. При обнаружении в строке не более одной отказавшей или охваченной снизу ячейки относительно нее происходит горизонтальная перестройка, т.е. логические номера ПЯ строки, стоящих за отказавшей

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

На фиг.За изображен вариант обхода

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

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

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

отказавшая ПЯ (i-1, j) из строки (Ы), то производится горизонтальная перестройка относительно этой ячейки независимо есть слева от нее отказавшие ПЯ или нет. Относительно остальных отказавших (захваченных) ПЯ производится захват исправных ПЯ из строки (i-1), т.е. вертикальная перестройка. Если же в строке i более чем двум отказавшим (захваченным) ПЯ соответствуют неисправные ПЯ из строки (i-1), то ячейка

однородной среды второй слева такой ПЯ вырабатывает сигнал фатального отказа, который распространяется через все ячейки данной строки и поступает на выход матрицы. Этот сигнал на выходе хотя бы одной

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

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

Причем, происходит переключение не всей матрицы, а только той строки I, в одной из ячеек (l,j), в которой возникли описанные условия.

Ячейка продолжает работать по старо- му алгоритму, но вместо сигнала об отказе верхней ПЯ теперь исследуется сигнал рб отказе нижней ПЯ, т.е. при перестройке Сверху-вниз необходимо избежать захвата неисправной ячейки, находящейся в ниж- ней строке (1+1). Кроме того, выход вертикального захвата блокируется, так как никакого захвата верхней ПЯ теперь нет. Зато теперь ячейка однородной массы вырабатывает новый сигнал - захват нижней ячейки lz(i, j). При получении сигнала lz(U) ячейка (И,) и вся строка (1-1), также переходят в режим Сверху-вниз (этот режим принимают как второй, а соответственно режим Снизу-вверх первый). В случае, ее- ли в одну из ячеек строки i , находящуюся во втором режиме, поступает сигнал ly(MJ), захвата верхней ячейки, то он (сигнал) преобразуется в сигнал lz(i,j) и поступает на вход захвата нижней ПЯ IZ(H, j) ячейки (i+1). переводя данную ячейку (i+1 ,j) и всю строку (i+1) во второй режим.

Таким образом очевидно, что теперь процессорная матрица может подвергаться перестройке как снизу-вверх, так и сверху- вниз, кроме того различные ее части могут находиться в различных режимах работы. Разберем алгоритм двунаправленного захвата на конкретных примерах (матрица имеет только столбец резервных ПЯ).

На фиг.2а изображен случай, когда в верхней строке произошло два отказа. В известной ячейке это привело бы к фатальному отказу, но в предлагаемой такого не происходит. Схема второй отказавшей ячейки (заштрихована в двух направлениях) переводит строку 1 во второй режим. Теперь эта ячейка вырабатывает сигнал lz(1.4), что проводит к захвату ячейки из второй строки (индексация ячеек и сигналов сохра- няется согласно требований, предъявляемых к известной ячейке). Фатального отказа не происходит, но теперь и вторая строка находится во втором режиме, в который ее перевел сигнал lz(1,4), поступивший на вход ячейки с фактическим номером (2,4).

Разберем второй случай (фиг.2б), когда над двумя неисправными ПЯ строки i находятся неисправные ПЯ строки (1+1). В известной ячейке это привело бы к фатальному отказу. Теперь же устройство (ячейка Заштрихована в двух направлениях) переводится во второй режим, благодаря чему происходит захват исправной ячейки из

строки, расположенной ниже, которая (строка) также переходит во второй режим.

В случае, изображенном на фиг.2в, произошел отказ в трех ячейках второй строки. При работе ячейки однородной среды в первом режиме неизбежно возникает фатальный отказ, т.е. запрос 1у (1,5) на вертикальный захват несуществующей ячейки. Для того, чтобы избежать этого, в схемах первой строки сигнал на входе горизонтального отказа 1x0-1,J) устанавливается равным единице. В результате в ячейке однородной среды с фактическим адресом (1,5) возникает сигнал, который переводит эту строку во второй режим. Это приводит к тому, что сигналы вертикального захвата 1у (2,3) и |у (2,5) преобразуются в сигналы 12(1 3) и lz(1,5), которые переводят и вторую строку в режим Сверху-вниз. Далее структурная перестройка проходит, как показано на фиг 2,II

Из описанного очевидно, что предлагаемые алгоритмы двунаправленного свободного захвата значительно гибче алгоритма свободного захвата.

Фатальный отказ (FF) возникает только в двух случаях: когда при работе ячейки однородной среды во втором режиме более чем одной неисправной ПЯ строки i соответствуют неисправные ячейки строки 0+1) и (1+2) (фиг.2г), а также в случае, изображенном на фиг.2д, а также при возникновении сигнала lz в одной из схем самой нижней строки матрицы. Например, на фиг.2г изображен случай, когда благодаря сигналам, выработанным в ячейках (4.4) и (5,4). произошло переключение строк 4,5 матрицы во второй режим перестройки. Но при этом неисправным ячейкам (4,2) и (4,4) четвертой строки соответствуют также неисправные ячейки (5,2) и (5,4), что приводит к невозможности структурной перестройки и, как следствие, к появлению сигнала FF на выходе ячейки (4,4).

В случае, изображенном на фиг.2д, аналогичный результат получается в два этапа. В первом происходит одновременный переход во второй режим третьей и пятой строк по сигналам, выработанным соответственно в ячейках (3,6) и (5,5). Во втором происходит перевод по сигналу lz(3,6) четвертой строки ПЯ во второй режим, и как следствие, вырабатывается ячейкой (4,5) сигнал фатального отказа, так как двум неисправным ячейкам (4,2) и (4.5) соответствуют также неисправные ячейки пятой строки (5,2) и (5,5). Структурная перестройка невозможна, даже если бы и хватало резервных ПЯ.

На входы (вертикальный и горизонтальный) каждой процессорной ячейки сигналы

от логических соседей могут поступать с выходов различных ПЯ в зависимости от физической конфигурации матрицы на данный момент времени.

Перестройка в горизонтальном и вертикальном направлениях производится неодинаково. Для исправной ячейки (i,j) возможными логическими соседями будут (фиг.За и б)

по вертикали:

a (I,J-1), в. (И,j), д. (l,jИ)

б. (1-1,J-1), г. (i-1, j+1), e. (I-2, J+1), ж. (1-2,

J+1)

по горизонтали:

a.(i1,j-1),B.(i,j-2)

б. (I, J-1). г. (14-1, j-1).

Введение седьмого элемента ИЛИ и связей, им обусловленных, обеспечивают объединение сигналов о изменении режима работы схемы, поступающих как от ячейки (1-1, j) по входу захвата нижней ПЯ Iz(l-1, j), так и с входа шестого элемента И.

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

Введение коммутатора и связей, им обусловленных, позволяет выбирать для работы ячейки, в зависимости от режима работы, сигналы отказа верхней 1(1-1,j), либо нижней 1(1+1,j)ПЯ.

i.

Введение вбсьмого и десятого элементов И, восьмого элемента ИЛИ и связей, ими обусловленными, позволяет либо блокировать выход захвата нижней ПЯ Iz(i,j) ячейки однородной среды в режиме Снизу-вверх либо в режиме Сверху-вниз подавать на этот выход сигналы с входа вертикального захвата ly(i+1, j) ячейки или третьего элемента И которые во втором режиме воспринимаются как сигналы запроса на захват ячейки из строчки (И 1).

Введение одиннадцатого элемента ИЛИ и связей, им обусловленных позволяет не допустить сигнал вертикального захвата 1уО+1.)) мэ вход четвертого элемента ИЛИ во втором режиме работы ячейки.

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

Введение девятого элемента И и связей, им обусловленных, обеспечивает блокировку выхода ly(i,j) во втором режиме, в

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

(1+1) и должен поступать на выход захвата нижней ПЯ Iz(l-J) ячейки однородной среды. Ячейка однородной среды содержит триггер 1 состояния, коммутатор 2, четвертый 3, седьмой 4, первый 5, пятый 6, шестой

0 7, второй 8, третий 9 и восьмой 10 элементы ИЛИ, седьмой 11, второй 12, девятый 13, четвертый 14, первый 15, пятый 16 десятый 17, одиннадцатый 18, третий 19, восьмой 20 и шестой 21 элементы И, третий 22 и шестой

5 23 информационные входы ячейки, четвертый 24 и второй 25 информационные выходы ячейки, настроечный вход-выход 26 ячейки, третий 27 и первый 28 информационные выходы ячейки, информационный

0 вход-выход 29 ячейки, десятый информационный вход 30 ячейки, пятый информационный выход 31 ячейки, второй 32, седьмой 33, первый 34 и четвертый 35 информационные входы ячейки, микровход 36 ячейки и пятый

5 информационный вход 37 ячейки.

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

5 Допустим в исходном состоянии все ПЭ матрицы исправны, следовательно на вход 32 l(l,j) соответствующей ячейки поступает нулевой потенциал, т.е. l(i,j) 0. Кроме того, нули поступают и на информационные вхо0 ды 30 и 37 нижней и верхней ячеек. На все входы и выходы данной ячейки при отсутствии отказавших ПЭ в матрице поступают одни нули, так как единице неоткуда взяться. Исключение составляют лишь ячейки,

5 обслуживающие самую верхнюю строку ПЭ. Так как над ними уже нет ПЯ, то попытка захвата верхней ячейки ячейкой с номером (1J) невозможно. Поэтому на входы 27 (i-1,J) ячеек, обслуживающих эти ПЭ, подаются

0 сигналы логической единицы, что эквивалентно расположенной сверху строки ПЯ, у которой все ПЭ отказали.

В случае отказа ПЭ (i, J) на вход 32 l(i,j) ПЯ ((,J) поступает единичный потенциал (все

5 ПЭ являются самотестируемыми). Кроме того, этот единичный потенциал поступает на вход 37 1(1-1,J) ячейки, обслуживающей ниже расположенный ПЭ (i+1, j), где I - номер строки матрицы ПЯ. a J - номер столбца. Эта же единица поступает на вход 30 1(1+1,J)

ячейки, обслуживающей выше расположенный ПЭ(Н, J).

Индексация входов и выходов ячеек проведена в соответствии с индексами ячеек, от которых поступают данные сигналы. Например, информационный вход 23 ячейки lz(l-1,j). Индексы говорят о том. что этот сигнал поступает с выхода 21. lz(l.j) ячейки, верхней (1+1,j) по отношению к данной (I.J) ячейке.

Итак, при отказе ПЭ (i,j), причем I 1, на вход 32 i(i,j) ячейки поступает единичный потенциал, который, пройдя через элемент ИЛИ 3 и открытый элемент И 16, поступает на вход элемента ИЛИ 8 С выхода ИЛИ 9 эта единица идет на выход 28 l(i,J) ячейки (ij), поступая на вход 34 lx(i,j-1) ячейки (i, J+1) Элемент И 16 открыт, так как на оба инверсных входа элемента И 15 поступают нули со входа 29 Eo(i) и 34 lx(i, j-1) ячейки. Единица с выхода элемента И 15 проходит через элемент ИЛИ 9, обрывая тем самым элемент И 16.

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

В случае, если произошел отказ ПЭ (i.j), а на вход 34 lx(i,j-1) соответствующей ячейки уже поступил единичный потенциал (т.е. отказали два ПЭ одной строки), то горизонтальная перестройка должна производиться относительно крайнего левого ПЭ. Данная же ПЯ (i,j) должна произвести вертикальную перестройку. Единица с входа 34 x(i,j-1) блокирует элемент И 15, и, как следствие, элемент И 16, однако, единица на выходе 28 x(i J) не исчезает, так как на второй вход элемента ИЛ И 8 поступает единичный потенциал с входа 34 lx(i, j-1).

Эта же единица, пройдя через элемент ИЛИ 5, открывает элемент И 19, на второй вход которого поступает единица, с выхода элемента ИЛИ 3 (ведь на входе 32 l(i,j) единица ПЭ (IJ) отказала).

Единица с выхода И 19 поступает на второй вход элемента И 13, на первый вход которого поступает единица с настроечного входа-выхода 26 ячейки (все строки матрицы пока находятся в первом режиме). Единица с выхода элемента И 13 поступает на

выход 24 iy(i,j) ячейки, сообщая ячейке (1-1,j) о ее захвате снизу, поступая на ее вход 33 y(+1,j).

Такой алгоритм работы реализуется

лишь в том случае, когда над обоими отказавшими ПЭ данной строки i находятся ис- правньге ПЭ строки (1-1). Если же над одним из этих ПЭ находится отказавший ПЭ, то горизонтальная перестройка производится

0 относительно последнего,1 независимо от места его расположения в строке, Относительно остальных ПЭ должна быть произведена вертикальная перестройка, т.е. соответствующие ячейки должны вырабо5 тать сигнал ly(i,J). Ячейка однородной среды в этом режиме работает следующим образом

К моменту появления единицы на входе 32 S(i.J) ячейки на входах 37 (1-1 .J) и 34 lx(l. J-1)

0 будут единицы, верхний (i-1, j) относительно данного (i,j) ПЭ отказал и в данной строке i левее ПЭ (1 j) есть отказчв- ший ПЭ, относительно которого произведена описанная горизонтальная перестройка

5 Единица, появившаяся на входе 32 l(i.j) соответствующей ячейки и свидетельствующая об отказе ПЭ (i,j), через элемент ИЛИ 3 поступает на входы элементов И 14 и 19, на вторые входы которых также поступают еди0 ницы На вход элемента И 14 с выхода коммутатора 2, один из элементов И которого открыт, на настроечном входе-выходе 26 всех ячеек строки - единица, на входе 37 I (1-1, j) так же. На вход элемента И 16 единица

5 поступает с выхода коммутатора 2 через элемент ИЛИ 9. На входе элемента А 19 - с входа 34 i(i,j-1)4epe3 элемент ИЛИ 5. Единица с выхода элемента И 19 через открытым элемент И 13, на второй вход которого по0 ступает единица С входа-выхода 26 ячейки, поступает на выход 24 ly(i,j) ячейки.

Сигнал на информационном входе 32 l(i.J) может появиться лишь по заднему фронту одного из импульсов, поступающих MS

5 синхровход 36 ячейки. Реализовать это требование несложно, так как все ПЭ и все ячейки выполняются на одной пластине полупроводника и работают от общего задающего генератора.

0 Единица с выхода элемента Л 16 поступает на второй вход элемента ИЛИ 8 как бы подтверждая сигнал x(l,j). Единица с выхода элемента И 14 поступает на входы элементов ИЛИ 6 и И 21, на другие входы которых

5 поступают нули с входа 22 E(i,j-1) ячейки. Этот нуль говорит о том, что в строке слева от данной ячейки нет ни одного отказавшего ПЭ, над которым расположен отказавший ПЭ в строке (1-1). Итак, сигнал на выходе элемента И 21 не изменяется, на выходе же

ИЛИ 6 появляется единица, поступающая на выход 25 E(l,j) ячейки. Эта единица поступает на вход 22 E(l,j-1) соседней справа ячейки (i,j+1) и через элемент ИЛИ 16 этой ячейки проходит на его выход 25 E(i,j) и т.д. Таким образом, эта единица проходит через все справа расположенные ячейки строки I, поступая на вход 22 E(i, j-1) и пыходя с выхода 25 E(i,j). В последних ячейках всех строк выход 25 Е (i,j) соединяется с входом 29 Е0() (фиг. пунктир). Единица на входе 29 Ео(0 сообщает всем ячейкам строки i о том, что в строке есть отказавший ЛЭ, над которым расположен отказавший ПЭ в строке (1-1).

Теперь в ячейке, расположенной слева от рассматриваемой, исчез сигнал на выходе 29 x(i,j) вследствие того, что элемент И 15 закрывается (на его инверсный вход поступает единица с входа 29), а это приводит к тому, что исчезает единица на одном из входов И 16, поступившая через элемент ИЛИ 19с выхода элемента И 15. Однако, в этой же ячейке вырабатывается сигнал ly(i,j) вертикального захвата. Происходит это следующим образом. На прямой вход элемента И 12 поступает единица с входа 29, а на инверсный - нуль, так как слева от этой ячейки нет отказавших ПЭ и захваченных ПЯ. Таким образом, на выходе элемента И 12 появляется единица, которая, пройдя через элемент ИЛИ 5, поступает на второй вход элемента И 19, на первом входе которого уже была единица, поступающая с входа 32 l(i,j) через элемент ИЛИ 3. Единица с выхода И 19 через открытый элемент И 13 поступает на выход 24 ly(IJ). Сигнал вертикальной перестройки сформирован. В ячейке же, которая обслуживает отказавший ПЭ, над которым расположен неисправный ПЭ, на входе 34 x(i, j-1) исчезает единица, но это не приводит к изменениям выходных сигналов, так как на выходе элемента ИЛИ 5 единица сохраняется.

На другой вход этого элемента теперь поступает единица с выхода элемента И 12, на прямой вход которого поступает единица, а на инверсный - нуль с входов 29 Ео() и 34 lx(i,j-1) соответственно. На этом формирование сигналов при таком типе отказа прекращается.

Работа устройства при захвате данного ПЭ снизу аналогична описанной с той лишь разницей что единица на вход элемента ИЛИ 3 поступает не с входа 32l(l,j), а с эходз 32 ty(I+1,j) через открытый элемент И 18, на другой вход которого поступает единица настроечного входа-выхода ячейки.

На входы 22 Е (, j-1) и 34 х(, j-1) крайних справа ячеек с индексами (1,1), должны для

нормальной работы ячеек постоянно подаваться нули. На вход 23 I (И, J) ячеек верхней строки, т.е. ПЭ с индексами (i.j). должны быть также поданы нули, а на вход

37 1(1-1, j) - единица. На вход 33 ly(i+1 J) устройств нижней строки, - это ПЯ с индексами (imax, j), должен быть подан нуль, а на вход 30 I(H-IJ) - единица.

Переход во второй режим и работа ячей0 ки в этом режиме осуществляются следующим образом.

Переход ячейки во второй режим происходит в случае: когда более чем над одним отказавшим или захваченным снизу ПЭ

5 строки i расположен отказавший ПЭ строки (i+1); когда в первой строке отказало либо захвачено более одною ПЭ, что эквивалентно предыдущему случаю, считая нулевую строку, состоящей из отказавших ПЭ; когда

0 строкой i производится попытка захвата ПЭ из строки (i-1), которая уже находится во втором режиме; когда в строке один из ПЭ захвачен сверху, т.е. строка, работающая во втором режиме, захватывает ПЭ из строки,

5 работавшей в первом.

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

0 1 состояния строки (каждой строки отдельно) объединены по схеме Электрическое ИЛИ (Монтажное ИЛИ)(фиг.1, резистор и пунктирная связь). Следовательно, инверсные выходы всех триггеров должны быть

5 выполнены по схеме с открытым коллектором (применительно к ТТЛ).

Рассмотрим первый случай, когда в строке i находится более чем один отказавший или захваченный снизу ПЭ, над кото0 рым в строке (i-) находятся отказавшие ПЭ. Допустим таких ПЭ два. Тогда в соответствующей ячейке левой из них будут сформированы сигналы lx(i,j) и E(i,j). как было описано. В соответствующей же правой

5 ячейке единицы будут на входах 22 Е (i,j-1), настроечном входе-выходе 26 ячейки, информационном входе-выходе Eo(i), входе 34 lx(l, j-1), входе 37 1(1-1 J) и входе 32 l(i,j). Следовательно, на выходе элемента И 21 поя0 зится единица, так как на обоих его входах также единицы. Один из них поступает с входа 22 Е (i,j-1), эту единицу сформировала ячейка, обслуживающая отказавший левый ПЭ. Вторая поступает с выхода элемента И

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

единичное состояние. В результате на настроечных входах-выходах 26 всех ячеек данной строки I появляется нуль. Ячейка переходит во второй режим.

Во втором режиме ячейка работает также, как и в первом с той лишь разницей, что теперь она вырабатывает сигнал не вертикального захвата ly{i,j) верхней ячейки, а сигнал захвата Iz(i.j) нижней ячейки. Для осуществления такой операции необходимо знать состояние нижней ячейки. С этой целью коммутатор 2 управляемый сигналом с настроечного входа-выхода 26, коммутирует на свой выход сигнал с входа 30 1(1+1,j), а не с входа 27 1(1-1, j), как это было в первом режиме. Кроме того, теперь по алгоритму работы захват снизу данной ячейки невозможен, перестройка идет сверху-вниз, поэтому нуль с настроечного входа-выхода 26 ячейки блокирует элемент И 18, чтобы исключить формирование ложного сигнала захвата ПЭ. Этот же сигнал блокирует элемент И 13, исключая формирование сигнала захвата ПЭ. Этот же сигнал блокирует элемент И 13, исключая формирование сигнала захвата верхней ячейки ly(i,j). Этот же сигнал деблокирует элементы И 11, 17 и 20.

Сигнал на выходе 31 lz(i,J) захвата нижней ячейки вырабатывается аналогично сигналу y(i,j) с той лишь разницей, что теперь единица с выхода элемента И 19 проходит не через элемент И 13 на выход 24 ly(i.j). a через элемент И 20 и элемент ИЛИ 10 на выход 31 lz(i,j) ячейки.

Рассмотрим второй случай перехода ячейки во второй режим, когда производится попытка захвата снизу ячейки, уже находящейся во втором режиме, т.е. на входе 33 1у(1+1. j появляется единица, которая, пройдя через открытый элемент И 17, поступает на второй вход элемента ИЛИ 10. попадая на выход 31 Iz(ij). Таким образом, сигнал вертикального захвата ly(i,j) ячейки (i,j) в ячейке (i-1,j) преобразуется в сигнал захвата нижней ячейки, который с выхода 31 Jy(i- 1 J) ячейки (И ,j) поступает на вход 23 z(l-1 ,j) ячейки (i,j). Эта единица через элемент ИЛИ 4 поступает на 1-вход триггера 1, который по очередному тактовому импульсу переходят в единичное состояние. После этого сигнал на выходе 24 ly(i.j) пропадет: элемент И 13 закрыт, следовательно пропадет и сиги ал на входе 23 Iz(M.j) но ячейка уже перешла на второй режим. Теперь элемент И 20 открыт, и единица с выхода И 19 через элементы И 20 и ИЛИ 10 поступает на выход 31 Iz(i.j) захвата нижней ячейки, т.е. после неудавшегося захвата верхнего ПЭ ячейка пытается захватить нижний ПЭ.

Единица с этого выхода поступает на вход 23 lz(i-1 J) ниже расположенной ячейки, где, пройдя через элемент ИЛИ 4, переводит триггер 1 в единичное состояние. Это и

есть третий вариант перехода ячейки во второй режим. Кроме того, эта же единица поступает на вход элемента ИЛИ 3, формируя сигнал захвата данной ячейки. Далее ячейка работает аналогично описанному режиму.

Рассмотрим условия возникновения фатального отказа, т.е. когда матрица в целом теряет работоспособность. Это происходит в том случае, когда двум и более отказавшим или захваченным ПЭ (l.j) строки I, которая

находится во втором режиме, соответствуют неисправные ПЭ (1+1. j) строки (1+1) Например, случай, изображенный на фиг.2 (все остальные случаи так или иначе сводятся к этому, фиг.2д).

Работа ячейки в этом случае аналогична работе ячейки при выработке сигнала E(i,j) в первом режиме. Разница заключается в следующем. Если эта строка уже находилась во втором режиме (например, на фиг.2.2 ячейка 5.4 отказала позже других, т.е. во втором режиме находились к моменту ее отказа строки 4,5, 6), то единица с выхода элемента И 21 через открытый элемент И 11 и элемент ИЛИ 7 поступает на информационный выход 27. Эта единица проходит через все справа стоящие ячейки, поступая на вход 35, выходя с выхода 27 ячеек; т.е., контролируя сигналы на выходах 27 крайних справа ячеек с индексами (I.Jrnax), можно четко зафиксировать момент фатального отказа. Наличие этого сигнала говорит о том, что в матрице возможна такая совокупность отказавших ПЭ. влияние которой не может быть устранено с помощью реконфигурации.

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

Ячейка однородной среды, содержащая шесть элементов ИЛИ и шесть элементов И,

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

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

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

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

2 J 4 5 6 7

п п а а а а пппппа

Ш П Ш П П П Ш П Й-П Q П Ш П Ш П П П П П П П П П

а п а п а п п

ПППШПШО

nnniintin

П Ш П Р Ш-П П ПШППШПО

п п а п п п п

D Р П

D D DID Щi D D

I

Фиг.З