Блок обработки матричной вычислительной системы

таит в расможностей обнаго сори возникотказаоших отипе приГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(54) БЛОК ОБРАБОТКИ ИНФОРМАЦИИ МАТРИЧНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ(57) Изобретение относится к вычислительной технике, в частности к архитектурам перестраиваемых матричных процессорных СБИС, использующих структурную перестройку, т.е. замену отказавших блоков обработки информации на резервные. Целью изобретения является расширение функциональных возможностей блока обработки информации (БОИ) путем обеспечения работоспособности состояния матрицы БОИ в условиях фатальных отказов за счет управИзобретение относится к вычислительной технике, в частности к архитектурам перастраиваемых матричных процессорных СБИС, использующих структурную перестройку, т.е, замену отказавших блоков обработки информации на резервныеЫ 1827675 А 1 ляемой деградации вычислительной размерности матрицы. Блок обработки информации матричной вычислительной системы содержит вычислительный узел 1, имеющий первый 1.1 и второй 1,2 информационные входы, первый 1.3 и второй 1,4 информационный выходы, выход .5 отказа, первый 2 и второй 3 узлы постоянной памяти, первый 4 и второй 5 входные, первый 6 и второй 7 выходные, коммутаторы, триггер 8, первый - четвертый 9 - 12 элементы ИЛИ, первый - третий 13 - 15 элементы И, вход 16 синхронизации, первый вход - выход 17 состояния, первый 18, второй 19 информационные выходы блока, выход 20 первого признака захвата блока, выход 21 признака невосстанавливаемого отказа блока, шестой вход 22 состояния блока, второй вход- выход 23 состояния блока, выход 24 отказа блока, первый - пятый 25, 27-30 входы состояния блока, вход 31 признака невосстанавливаемого отказа блока, вход 32 первого признака захвата блока, первый-четвертый 33 - 37 информационные входы блока, пятый -девятый 38 - 41 информацион н ы й входы блока. выход 42 второго признака захвата блока, вход 43 отказа верхнего блока и их связи . Новым в БОИ является введение триггера, третьего элемента И, четвертого элемента ИЛИ и обусловленных ими связей.4 ил Сущность изобретения сос ширении функциональных воз путем обеспечения работоспос стояния матрицы БОИ в целом новении такого распределения БОИ, которые в устройстве-про1827675 водят к ФО, но при меньшей вычислительной размерности матрицы переводят в режим транзита БОИ крайних строк и столбцов, т.е; их последовательного "вычеркивания",Например, после первого вычеркивания первые строки и столбец и М-е - строка и столбец как бы перестают существовать, а (й)-я строка и столбец становятся резервными. Таким образом, если отказавшие БОИ, находятся в "вычеркнутых" строках, то после изменения в,них режима эти строки исключены из рассмотрения, а матрица в целом сохраняет работоспособность, но при меньшей размерности - (М)-х (Й) и т,дПредлагаемое устройство обеспечивает расширение области применения для построения матричных процессорных СБИС с деградирующей размерностью (производительностью), а также СБИС с управляемой размерностью вычислительной структуры,На фиг. 1 представлена функциональная схема блока обработки информации матричной вычислительной системы; на фиг.2 и 3 представлены таблицы соответствия для первого и второго узлов постоянной памяти; на фиг.4 представлены триггеры реконфигурации.Блок обработки информации матричной вычислительной системы содержит вычислительный узел 1, имеющий первый 1,1 и второй 1,2 информационные входы, первый 1.3 и второй 1.4 информационные выходы, выход 1,5 отказа; первый 2 и второй 3 узлы постоянной памяти; первый 4 и второй 5 входные, первый 6 и второй 7 выходные коммутаторы, триггер 8: первый-четвертый 9 - 12 элементы ИЛИ; первый-третий 13-15 элементы И; вход 16 синхронизации; первый вход-выход 17 состояния; первый 18, второй 19 информационные выходы блока, выход 20 первого признака захвата блока; выход 21 признака невосстанавливаемого отказа блока; шестой вход 22 состояния блока; второй вход - ,выход 23 состояния блока; выход 24 отказа блока; первый-пятый 25, 27-30 входы состояния блока; вход 31 признака невосстанавливаемого отказа блока; вход 32 первого признака захвата блока; первый - четвертый ЗЗ - 37 информационные входы блока; пяты - девятый 38 - 41 информационные входы блока; выход 42 второго признака захвата блока; вход 43 отказа верхнего блока,Вычислительный узел (ВУ) 1 предназначен непосредственно для проведения выВходные первый 4 и второй 5 коммутаторы предназначены для коммутации на информационные входы 1.1 и 1.2 ВУ одного иэ возможных логических соседей БОИ.Выходные первый 6 и второй 7 коммута 50 торы предназначены для перевода БОИ в режим транзит, при этом информация с выходов входных коммутаторов 5, 4 поступает, минуя ВУ, на выходы 19 и 18 БОИ.Триггер 8 предназначен для управления переводом в режим транзита в случае воз 55 никновения ФО, Выход этого триггера выполняется по схеме с "открытым коллектором" числений, Он представляет собой одноразрядный самотестируемый вычисли- Первый 9 - третий 11 эле:;ванты ИЛИ, тель. Если необходимо выполнять динами- первый 13, второй 14 ялга".1 ь 1 И г,редназ 5 182767545 50 55 начены для формирования сигналов вертикального еу (1,и горизонтального ех (захватов и сигнала ФО(1,(первый и второйпризнак захвата).Четвертый элемент ИЛИ 12 предназначен для управления выходными коммутаторами 6 и 7.Третий элемент И 15 предназначен дляблокирования сигнала отказа ВУ(1. в БОИ"замкнутых" строк и столбцов матрицы.Устройство работает следующим образом.Рассмотрим работу БОИ на примере егоиспользования при построении прямоугольной матрицы размерностью 1 х М(8+1). т.е. матрицы с одним столбцом резервных БОИ. Таким образом, вьчислительный размер матриц М х М. Во всех БОИ (.матрицы (где= 1, К, ) = 1. И+) триггеры 8находятся в единичном состоянии, следовательно, на первых и вторых вь ходах-входахсостояния строк С23 и столбцов Т О) 17всех ПЯ находятся единичные потенциалы,так как выходы триггеров 8 всех БОИ каждого столбца обьединяются по схеме "монтажное И",При возникновении отказавших БУ алгоритм работц аналогичен алгоритму прототипа, а именно вся матрица"просматривается" сверху-вниз, слева-направо, Первый же БОИ (1. , в котором отказал ВУ, т.е. е(1, =1, вцрабатывае- сигналгоризонтального захвата ех (1, ), которыйпоступает на его выход 20, передаваясьвсем БОИ строки 1, находящимся справа отБОИ (1,. Все остальные БОИ строки 1., которые имеют отказавшие ВУ, (далее будемпросто называть отказавшие БОИ), вырабатывают сигнал вертикального захвата еу(1, )из строки (1-1). Далее захваченные блоки(блок, на вход 26 захвата еу (+1,которогопришел единичный согнал) строки (1-1) воспринимаются как отказавшие, т,е. самый левый иэ них(если левее нет отказавшего БОИ(1-1,воспринимается как самый левый отказ и вырабатываетсигнал горизонтальногозахвата, остальные же вновь вырабатываютсигнал вертикального захвата. Рассмотримпример фиг.4,а.В матрице 5 х 6 отказали БОИ с адресами (3.1),1,3.4), (3.5) и (5.2), В пятой строкесамым левым отказом считается БОИ (5.2),следовательно, он вырабатывает сигнал горизонтального захвата и относительно негапроисходит перестройка в строке 5, Так какдругих отказавших БОИ нет, то сигналь". вертикального захвата в строке 5 не вырабатываются и блоки из строки 4 незахватываются, В строке три БОИ (3,1) вырабатывает сигнал горизонтального захвата и относительно него происходит горизонтальная перестройка в строке. БОИ (3,4), (3.5) вырабатывают сигналы вертикального захвата еу (3.4) и еу (3,5), которые поступают на входы 26 БОИ (3.4), (2.5). Блок (2.4) является крайним левым отказом в строке 2 и относительно него происходит горизонтальная перестройка в строке 2. БОИ (2,5) вновь вырабатывает сигнал вертикального захвата, захватывая БОИ (1.5), Так как в первой строке других захваченных или отказавших БОИ нет, то перестройка горизонтальная производится относительно БОИ (1.5), на этом реконфигурация матрицы заканчивается, Рассмотрим как вырабатываются эти сигналы: ех и еу подробнее.Допустим, что БОИ (1. ) (фиг,1) является крайним левым отказавшим БОИ строки 1. Тогда единица с выхода отказа 1.5 ВУ через открытый элемент И 15 поступает на вход элемента ИЛИ 11, с выхода которого эта единица поступает на входы элементов И 13 и ИЛИ 9. Но элемент И 13 закрыт, так как со входа 32 горизонтального захвата поступает нулеьой потенциал - ведь слева от БОИ(1, Д нет отказавших или захваченных БОИ, - он является самцы левым отказавшим элементом, Таким образом, единица, проходя через элемент ИЛИ Я, появляется на выходе 20 горизонтального отказа ех (1, Д БОИ: т,е. ех(1, Д =-1. Кроме того, единица с выхода 1,5 отказа через элемент ИЛИ 12 поступает на управляюдие входы выходных коммутаторов 6 и 7, коммутируя на вертикальный 19 и 35, горизонтальный 8 выходы БОИ не соответствующие выходы 1,3, 1.4 ВУ 1, а выходы входных коммутаторов 4 и 5, - блок переходит в режим транзита.Следовательно, в крайнем левом отказавшем БОИ(1, формируется только сигнал горизонтального захвата ех (1. , поступающий на выход 20. поступает единица на выход 24 отказа е (1, Я БОИ; БОИ переходит в режим транзита, В случае, если крайним слева оказался БОИ захваченный блок, то единица на вход ИЛИ 11 поступает не с выхода И 15, а со входа 26 вертикального захвата е(+1, БОИ, т.е, е, (+1, = 1, В этом случае БОИ (1. ) вырабатывает только сигнал ех(1,3=1.В случае, если БОИ(1,отказал (е (1, ) = 1) иди был захвачен снизу еу(+1, ) = 1 и при этом не является самым левым отказом в строке. единица появляется не только на выходе 20 ех (1, Д, но и на выходе 42 вертикальнога захвата еу (1, ) БОИ, Происходит зто следующим образом, Так как БОИ (1, ) - не самый девиц отказ, то следовательно один из БОИ (1, К), где К ) уже вьработа. сигнал горизонтального захвата е (1, Ц - 1.10 15 20 25 30 35 40 50 Эта единица поступает на вход 32 горизонтального отказа ех (, )-1) БОИ, и, проходя через элемент ИЛИ 9, поступает на выход 20, т,е. ех (, ) = 1. Эта же единица со входа 32 поступает на вход элемента И 13, на другой вход которого поступает единица с выхода элемента ИЛИ 11, ведь БОИ (,является отказавшим или захваченным. Т,о., на выходе И 13 формируется единичный потенциал, который поступает на выход 42 вертикального захвата ех (1, 1) БОИ. Следовательно, БОИ (, сформировала сигналы ех (=1 иуу(=1.Аналогичные действия происходят во всех БОИ матрицы, и каждый БОИ, анализируя сигналы ех и еу соседних БОИ решает, выход какого БОИ скоммутирован на вход своего ВУ, Анализ этот выполняется с помощью двух первого 2 и второго 3 узлов постоянной памяти, Таблицы входов-выходов приведены на фиг.2 и 3, на этих же таблицах приведено какие сигналы (ех или еу 1 и с выходов каких БОИ(относительно . 4 ОИ (.коммутируются на их входы, а также информационные выходы каких БОИ при том или ином сочетании сигналов выбираются с помощью выходных коммутаторов.Рассмотрим пример выполнения коммутации выходов БОИ на примере БОИ (2,4) фиг.4,а БОИ (2.4) является захваченным, так как под ним расположен отказавший БОИ (3,4), не являющийся самым левым отказавшим БОИ строки 3. Следовательно, еу (+1,у= 1. Но БОИ (2.4) является самым левым захваченным БОИ строки 2, следовательно на его вход 32 поступает нуль, т.е. ехф (1, 1-1) = 1. Обращаясь к фиг.2, видим, что такому состоянию соответствует первая строка таблицы, - на вертикальный Вход 1,1 ВУБОИ (, Д коммутируется информационный вертикальный выход 19 БОИ(,)-1) что и показано на фиг.4 ба. Обращаясь к фиг.З и зная, что еу (+1, ) = 1, видим, что нас будет интересовать первая и пятая строки таблицы, а в этих строках сигналы, поступающие на входы О 4 и О 1. Т.е, нас интересуют сигналы еу (+1, )-1) и еу (+2, )-1) или еу (3,3) и еу(4.3), ведь=- 2, а) = 4, Итак, обратившись к БОИ (3.3), видим, что он является исправным и незахваченным, следовательно, сигнал вертикального захвата он вырабатывать не может еу (3,3) = О. Рассмотрев БОИ (4,3), видим, что в строке 4 нет даже сигнала горизонтального захвата ни в одном из БОИ, так как строка 4 не содержит отказавших . или захваченных БОИ, следовательно еу (4,3) = О, Т,амы идентифицировали требуемую нам строку таблицы (фиг,З) - это строка один, Следовательно, на горизонтальный информационный вход 1.2 ВУ БОИ (2,4) будет коммутироваться через выходной коммутатор 7 БОИ (3.3) и входной коммутатор 5 БОИ (2.4) выход 1.4 ВУ 1 БОИ (3.3), что и показано на фиг.4,а,Из всего вышесказанного следует следующее:- на входы 32 БОИ (, 1), где= 1, Ы, должны подаваться нулевые потенциалы- на входы 2 б БОИ (й где ) = 1, И+1 или) =1, ч(в случае столбца и строки резервных БОИ), должны также подаваться нулевые потенциалы;- данный алгоритм не сможет произвести реконфигурацию в случае, когда будет захватываться отказавший БОИ (. ), т,е. е(, =1 и еу(+1, = 1,Рассмотрим последний случай подробнее. Для выявления случаев, когда над отказавшимм или захваченным БОИ (. ), не являющимся крайним левым в строке , находится отказавший БОИ (-1, , вводится элемент И 14, на один из выходов которого щ)ступает сигнал е (-1, ). Таким образом, если формируется сигнал вертикального захвата еу (, , то единица с выхода И 13 поступает и на вход И 14, на выходе которого появится единичный потенциал, который, пройдя через элемент ИЛИ 10, появится на выходе 21 ФО (, ); Контролируя выход 21 БОИ (, И), можно определить в какой строке возник ФО, После возникновения сигнала ФО дальнейшая эксплуатация матрицы невозможна так как реконфигурация не может быть выполнена. Так было в устройстве-прототипе, но в предлагаемых БОИ этот алгоритм дополнен следующим образом.Известно, что в СБИС отказы концентрируются в силу особенностей технологии к краю кристалла. Следовательно, логично предположить, что сигнал ФО наиболее вероятно вызван отказами в крайних строках и столбцах БОИ. Поэтому предлагается при возникновении сигнала ФО переводить в режим транзита с блокировкой сигнала е (, . Крайние строки и столбцы, как бы "снимая" внешние БОИ, в надежде, что, исключив из рассмотрения отказавшие БОИ или их часть, удастся избежать ФО, пусть и ценой сокращения вычислительной размерности матрицы. Рассмотрим этот процесс подробнее,На входы 43 отказа верхнего БОИ блоков верхней строки, т,е, БОИ (1, , подаются единичные сигналы, ведь сверху блоков, а тем более исправных, нет вообще. Т,о., при распределении отказавших БОИ таком, как показано на фиг,4,б, возникает сигнал ФО в БОИ(1,6). Следовательно, на прямой К-вход .триггера 8 БОИ (1 Я) поступает единичныйпотенциал, на инверсный К-вход поступает сигнал логического нуля, так как справа больше столбцов БОИ нет (т,е, на входы 22 всех БОИ (, й или ч+1) поступают сигналы логического нуля. Па очередному тактовому импульсу, поступающему со входа 16 синхронизации, триггер 8 перейдет в нулевое состояние, а так как все триггеры 8 БОИ столбца 6 и 1 строки 5 и 1 обаединены с помощью перемычек (пунктир на фиг.1) по схеме "монтажное И", то на всех входах-выходах состояния строки С23 и столбца Т О) 24 будут равны нулю, Следовательно, эти нули, поступая на один из входов элемента ИЛИ 12, переведут БОИ этих строк и столбцов в режйм транзит. После этого мы получим матрицу БОИ вычислительной размерностью 3 х 3 с одним столбцом резервных БОИ, сигнал ФО в БОИ (1,6) исчезнет, так как в вычеркнутые строки попали БОИ, вызывавшие его формироваг: е. На фиг,3 в показан окончательный вид получаемой матрицы.Перемычка, изображенная нэ фиг,1 пунктиром, выполняется не во всех БОИ матрицы, а лишь в БОИ (,с одним столбцом резервных БОИ при=) ий/2), при) = =й+1 (Н/2+1) и при 1 = 1+ 1 (й/2+1), в матрицах са строкой и столбцом резервных БОИ (котарый является самым верхним) перемычки выполняются в БОИ (,при .= ) и ) .= Ю+1,В случае если сигнал ФО сформировался на в крайнем БОИ, кэк рассмотрено выше, та переключение триггера в атом БОИ(,не происходит, так как следующий столбец +1) еще не переведен в режим транзита, т.е, Т 0+1) = 1, и на вход 22 поступает единичный потенциал, - изменение состояния триггера 8 запрещается.И еще, на входы 31 ФО БОИ(1, должны подаваться нулевые потенциалы,Т.о., при возникновении таких множеств отказавших БОИ, которые в устройстве-прототипе приводили к ФО, в матрице, построенной из предлагаемых БОИ, будет приводить к "сжатию" матрицы к центру: квадратная матрица сжимается в "точку", а прямоугольная - в линию. Контролировать, - какой размер вычислительной матрицы обеспечивается в данный момент, можно па сигналам с выходов состояния 17 или 23 крайних БОИ какой-либо строки (первай или последней) или столбца (первого или последнега). Кроме того, такая матрица допускает внешнее управление размерностью матрицы, Так, подавая на входы-выходы 17. или 23 БОИ крайних строк или столбцов сигналов логического нуля с вцхадэ какого 5 пользующей данные БОИ. Все БОИ матрицы работают под управлением одного тактового генератора 20 выходом блока, первый выход вычислитель 35 ного узла соединен с вторым информацион 40 50 10 15 либо элемента, выход которого выполнен па схеме с "открытцм коллектором, можно принудительно переводить в режим транзита любые строки и столбцы матрицы, исФ ар мула и за бр ете н ия Блок обработки информации матричной вычислительной системы, содержащий вычислительный узел, первый входной и первый выходной коммутаторы, второй входной и второй выходной коммутаторы, первый и второй узлы постоянной памяти, первый и второй элементы И, первый, второй и третий элементы ИЛИ, причем с первого по четвертый информационные входы блока соединены соответственно с информационными входами первого входного коммутатора, выход которого соединен с первым информационным входом вычислительного узла и с первым информационным входом второго выходного коммутатора, выход которого является первым информационным выходом блока, с пятого по девятый информационныевходы блока соединены соответственно с информационными входами второго входного коммутатора, выход которого соединен с вторым информационным входом вычислительнога узла и с первым информационным входом второго выходного коммутатора, выход которога является вторым информационным ным входом первого выходного коммутатора, второй выход вычислительного узла соединен с вторым информационным входом второго выходного коммутатора, первый вход признака захвата блока соединен с первыми адресными входами первого и второго узлов постоянной памяти, с первым входом первого элемента И и первым входом первого элемента ИЛИ, выход которого является первым выходом признака захвата блока и соединен с вторым адресным входом первого узла постоянной памяти, первый и второй выходы которого соединены с первым и вторым управляющими входами первого входного коммутатора, вход признака невосстэнавливаемого отказа блока соединен с первым.входам второго элемента ИЛИ, выход которого является выходом признака невосстанавливэемого отказа блока, второй вход признака захвата блока соединен с вторым адресным входам второго узла постоянной памяти и третьим адресным входом первого узла постоянной памяти, с пероыгл вхо дам третьего элемента ИЛИ, выход котарогасоединен с вторым входом первого элемента ИЛИ и вторым входом первого элемента И, выход которого является вторым выходом признака захвата блока и соединен с первым входом второго элемента И и третьим адресным входоМ второго узла постоянной памяти, первый, второй и третий выходы которого соединены соответствен- .но с управляющими входами второго входного коммутатора, вход признака 1 фатального отказа блока соединен с вторым входом второго элемента И, выход которого является выходом фатального отказа блока И, соединен с вторым входом второго элемента ИЛИ, первый вход состояния блока 1 соединен с четвертым адресным входом первого узла памяти, второй вход состояния соединен с четвертым адресным входом второго узла постоянной памяти, третий вход состояния соединен с пятым адресным 2 входом второго узла постоянной памяти, четвертый вход состояния блока соединен с пятым адресным входом первого узла постоянной памяти, пятый вход состояния блока соединен с шестым адресным входом 2 второго узла постоянной памяти, о т л и ч а ющ и й с я тем, что, с целью расширения функциональных воэможностей за счет обеспечения режимов реконфигурации, в блок обработки информации введены треАр// бйф 4 ф.,у тий элемент И, четвертый элемент ИЛИ и триггер, причем выход отказа вычислительного узла является выходом отказа блока и соединен с прямым входом четвертого эле мента ИЛИ и с первым входом третьего эле-.мента И, выход которого соединен с вторым входом третьего элемента ИЛИ, выход вто рого элемента ИЛИ соединен с прямым Квходом триггера, выход которого является О первым входом-выходом состояния блока исоединен с первым инверсным входом четвертого элемента ИЛИ и вторым входом третьего элемента И, шестой вход состояния блока соединен с инверсным К-входом 5 триггера, второй вход-выход состояния блока соединен с третьим входом элемента И и вторым инверсным входом четвертого элемента ИЛИ, выход которого соединен с управляющими входами первого и второго О выходных коммутаторов, вход кода операции блока подключен к входу кода опера-.ции вычислительного узла, вход синхронизации блока подключен к входам синхронизации триггера, вычислительно го узла, первого и второго узлов постоянной памяти, кроме того, . первый вход-выход состояния блока соединен с вторым входом-выходом состояния блока при использовании блока в матрицах Н х О Н или Н х(Н+1).1827675 оставитель В.Литви ехоед М.Моргентал Подписноеобретениям и открытиямаушская наб., 4/5 КНТ ССС оиэдодственно-издательский комбинат "Патент", г, Ужгород. ул,Гагарина, 10 аказ 2359 ВНИИПИ Госуд Тиражтвенного комитета по 113035, Москва, Жо Корректор Н.Кешел