УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ ДВУХ МАТРИЦ Российский патент 1995 года по МПК G06F17/16 

Описание патента на изобретение RU2049352C1

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

Наиболее близким по технической сущности к заявляемому устройству является устройство для обработки информации [2] в частности для перемножения матриц АIxQ x BQxT, содержащее Q блоков обработки, причем каждый блок обработки содержит умножитель, сумматор, четыре регистра, группу из D регистров, где D max(I,Q), группу из D + 2 регистров, четыре триггера, три группы элементов И, группу элементов ИЛИ и элемент НЕ. В основу работы устройства положена параллельно-поточная организация вычислений. При использовании тестового периодического контроля для обеспечения достоверности получаемых при обработке информации результатов вероятность пропуска отказа блока обработки пропорциональна времени между тестовыми проверками (период контроля), при этом объем ошибочной информации, выдача которой происходит до тестовой проверки, также пропорционален периоду контроля. Временные затраты на тестовую проверку определяются объемом теста и, соответственно, пропускная способность линейки из блоков обработки обратно пропорциональна этим временным затратам, а вероятность обнаружения отказа с помощью тестовой проверки определяется разрешающей способностью теста и объемом аппаратуры, охваченной контролем. Время восстановления вычислительного процесса (получение достоверного результата на выходе устройства после обнаружения отказа) пропорционально числу блоков обработки устройства (длине Q линейки устройства).

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

Поставленная задача достигается тем, что в устройство, содержащее L блоков обработки 1, где L > D, D размер обрабатываемых матриц, причем тактовый вход 19 устройства подключен к тактовым входам блоков обработки с первого по L-й, информационные входы первой, второй и третьей групп 9-11, первый и второй управляющие входы 12 и 13 устройства подключены соответственно к информационным входам первой, второй и третьей групп, к первому и второму управляющим входам первого блока обработки, информационные входы первой, второй и третьей групп, первый и второй управляющие входы а-го блока обработки (где а 2,L) подключены соответственно к входам первой, второй и третьей групп, к первому и второму входам (а-1)-го блока обработки, введены L комбинационных сумматоров 2, L узлов сравнения 5, (L-1)-й регистр 3, L групп элементов И 6, L -1 групп элементов ИЛИ 4 и элемент ИЛИ-НЕ 8, причем управляющие входы 14 группы устройства подключены соответственно к управляющим входам группы первого блока обработки, выходы четвертой группы b-го блока обработки (где b 1, L-1) подключены соответственно к первым входам элементов ИЛИ 4 b-й группы, выходы которых подключены соответственно к управляющим входам группы (b+1)-го блока обработки, с-е входы установки в исходное состояние первой, второй и третьей групп 15, 16 и 17 устройства (где с 1, L) подключены соответственно к первому, второму и третьему входам установки в исходное состояние с-го блока обработки, с-й вход блокировки 18 устройства подключен ко входу блокировки с-го блока обработки, выходы третьей группы с-го блока обработки подключены соответственно к первым входам элементов И 6 с-й группы, выходы которых подключены соответственно ко входам с-й группы элементов ИЛИ 7 с-й группы, выходы которых подключены соответственно к выходам результата 22 устройства, третий выход 1 с-го блока обработки подключен к с-му выходу 21 признака отказа группы устройства и к информационному входу с-го комбинационного сумматора 2, выходы b-го комбинационного сумматора 2 подключены ко входам первой группы b-го узла сравнения 5 и 4 информационным входам b-го регистра 3, входы которого подключены соответственно к вторым входам элементов ИЛИ 4 b-й группы, выходы L-го комбинационного сумматора 2 подключены соответственно к входам первой группы L-го узла сравнения 5, вход с-го узла сравнения 5 подключен ко вторым входам элементов И 6 с-й группы и к с-му входу элемента ИЛИ-НЕ 8, выход которого подключен к выходу 23 признака отказа устройства, входы 20 задания размерности D обрабатываемых матриц которого подключены соответственно ко входам вторых групп узлов сравнения 5 с первого по L-й и к информационным входам четвертых групп блоков обработки 1 с первого по L-й, выходы пятой группы с-го блока обработки 1 подключены соответственно к информационным входам группы с-го комбинационного сумматора 2, тактовый вход 19 устройства подключен к тактовым входам регистров 3 с первого по (L-1)-й.

Каждый блок обработки 1 содержит два вычислительных узла 24 и 25, узел сравнения 26, триггер 27, три блока элементов И 28-30, блок элементов ИЛИ 31 и элемент И 32, причем в каждом блоке обработки информационные входы первой, второй, третьей групп 33, 34 и 35, управляющие входы группы 38, первый и второй управляющие входы 36 и 37 подключены соответственно ко входам групп первого и второго блоков элементов И 28 и 29, выходы первой группы которого подключены соответственно ко входам первой группы блока элементов ИЛИ 31, выходы которого подключены соответственно к выходам первой, второй, третьей групп 47-49, к первому и второму выходам 50 и 51 блока обработки, выходы первой группы первого блока элементов И 28 подключены соответственно к информационным входам групп с первой по третью, к первому и второму управляющим входам первого и второго вычислительных узлов 24 и 25, выходы групп с первой по третью, первый и второй выходы первого вычислительного узла 24 подключены соответственно к входам группы третьего блока элементов И 30 и соответственно ко входам первой группы узла сравнения 26, выходы третьего блока элементов И 30 подключены соответственно к входам второй группы блока элементов ИЛИ 31, выходы вторых групп первого и второго блоков элементов И 28 и 29 подключены соответственно к выходам пятой 45 и четвертой 52 групп блока обработки, информационные входы 42 четвертой группы которого подключены к информационным входам первого 24 и второго 25 вычислительных узлов, выходы групп с первой по третью, первый и второй выходы второго вычислительного узла 25 подключены соответственно ко входам второй группы узла сравнения 26, выход которого подключен к информационному входу триггера 27, выход которого подключен ко входам первого 28 и третьего 30 блоков элементов И, к инверсному входу второго блока элементов И 29 и к третьему 46 выходу блока обработки, тактовый вход 40 которого подключен к первому входу элемента И 32, выход которого подключен к тактовым входам первого 24 и второго 25 вычислительных блоков и триггера 27, вход 39 блокировки, первый, второй и третий входы установки 41, 43 и 44 в исходное состояние блока обработки подключены соответственно ко второму (инверсному) входу элемента И 32, ко входам установки в исходное состояние вычислительных узлов 24 и 25, ко входу установки в нулевое состояние триггера 27 и входу установки в единичное состояние триггера 27.

Каждый вычислительный узел 25 и 24 содержит четыре регистра 53-56, дешифратор 74, две группы регистров 57 и 58, умножитель 59, сумматор 60, четыре триггера 61-64, (2L+2) групп элементов И 65, 66, 671. 67L, 681,68L, три группы элементов ИЛИ 69, 70, и 71, элемент И 72 и элемент НЕ 73, причем в каждом вычислительном узле информационные входы 75 первой группы подключены к информационным входам первого регистра 55 и второго регистра 56, выходы которого подключены к информационным входам первой группы умножителя 59, выходы которого подключены соответственно к информационным входам первой группы сумматора 60, выходы первого регистра 55 подключены к выходам 83 первой группы вычислительного узла, информационные входы 79 второй группы которого подключены к информационному входу первого регистра первой группы 58 и к первым входам элементов И первой группы 66, выходы которых подключены к первым входам элементов ИЛИ первой группы 69, выходы которых подключены к информационному входу первого регистра 571 второй группы 57, выходы которого подключены к информационным входам второй группы умножителя 59, выходы р-го регистра второй группы 57 (где р 1, L) подключены к первым входам элементов И р-й группы 67р, выходы элементов И 67 с первой по L-ю группу подключены ко входам элементов ИЛИ второй группы 70, выходы которых подключены к первым входам элементов И 65 (L+2)-й группы, выходы которых подключены ко вторым входам элементов ИЛИ первой группы 69, выходы с третьего по (L+2)-й регистра первой группы 58 подключены соответственно к первым входам элементов И с первой по L-ю группу 681, 68L, выходы которых подключены ко входам элементов ИЛИ третьей группы 71, выходы которых подключены к выходам 84 второй группы вычислительного узла, информационные входы 77 третьей группы которого подключены к информационным входам третьего регистра 53, выходы которого подключены к информационным входам второй группы сумматора 60, выходы которого подключены к информационным входам четвертого регистра 54, выходы которого подключены к выходам 85 третьей группы вычислительного узла, первый управляющий вход 78 которого подключен к первому входу элемента И 72 и к информационному входу первого триггера 61, выходы которых подключены соответственно ко входу синхронизации второго регистра 56 и к информационному входу второго триггера 62, выход которого подключен к первому выходу 87 вычислительного узла, второй управляющий вход 79 которого подключен ко вторым входам элементов И первой группы 66, ко входу элемента НЕ 73 и к информационному входу третьего триггера 63, выходы элемента НЕ 73 и третьего триггера 63 подключены соответственно ко вторым входам элементов И 65 (L+2)-й группы и к информационному входу четвертого триггера 64, выход которого подключен ко второму выходу 87 вычислительного узла, информационные выходы 80 четвертой группы которого подключены ко входам дешифратора 74, q-й выход которого (где q 1,L) подключен к вторым входам q-х элементов И (q+1)-й и (L+q+2)-й групп 67 и 68, тактовый вход 82 и вход 81 начальной установки вычислительного узла подключены соответственно ко входам синхронизации и входам установки в нулевое состояние всех регистров и триггеров.

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

Устройство содержит L блоков обработки 1, где L D + R, D размерность перемножаемых матриц, R число избыточных (резервных) блоков обработки, L комбинационных сумматоров 2, L-1 регистров 3, L групп элементов ИЛИ 4, L узлов сравнения 5, L групп элементов И 6, группу элементов ИЛИ 7, элемент ИЛИ-НЕ 8, группы информационных входов 9, 10 и 11, управляющие входы 12, 13 и 14, группы входов установки 15, 16 и 17, входы блокировки 18, тактовый вход 19, вход 20 задания размерности матриц, группу выходов 21 признака отказа, выходы результата 22 и выход 23 признака отказа устройства.

Каждый блок обработки 1 содержит вычислительные узлы 24 и 25, узел сравнения 26, триггер 27, группы элементов И 28, 29, 30, группу элементов ИЛИ 31, элемент И 32, информационные входы 33-38, вход 39 блокировки, тактовый вход 40, вход 41 установки в исходное состояние, вход 42 задания размерности, управляющие входы 43 и 44, выходы 45-52.

Каждый вычислительный узел 24 и 25 содержит регистры 53-56, группы регистров 57 и 58, умножитель 59 и сумматор 60, триггеры 61-64, группы элементов И 65-68, группы элементов ИЛИ 69-71, элемент И 72, элемент НЕ 73, дешифратор 74, группы информационных входов 75-77, управляющие входы 78 и 79, вход 80 задания размерности матриц, вход 81 начальной установки, тактовый вход 82, выходы 83-87.

В основу работы устройства положены рекуррентные соотношения умножения матрицы АIхQ и ВQxT:
Cij(0) 0; i 1.I; j 1.T;
Cij(k) Cij(k-1) + aik˙bkj, k 1.Q.

Вычислительный узел 24 (25) обладает возможностью реализации функций:
aвыхi+1 aiвх; bвыхi+D+2 biвх;
Ci+2вых

Ciв
х +
τ1выхi+21вхi
τ2выхi+22вхi где
aiвх, biвх, ciвх значения соответственно на информационных входах 75, 76 и 77 вычислительного узла на i-м такте;
τ1вхi, τ2вхi значения соответственно на управляющих входах 78 и 79 вычислительного узла на i-м такте;
aiвых, biвых, сiвых, τ1выхi, τ2выхi- значения соответственно на выходах 83 87 вычислительного узла на i-м такте.

Каждый из вычислительных узлов 24(25) работает в четырех режимах, которые задаются значениями управляющих сигналов τ1 и τ2, подаваемых на входы 78 и 79 соответственно. На выходах 86 и 87 вычислительного узла управляющие сигналы τ1 и τ2 выдаются с задержкой на два такта.

В первом режиме работы вычислительного узла (τ1, τ2) (1, 1), на входы 77, 75 и 76 вычислительного узла подаются соответственно значения элементов с, а и b. При этом значение с по заднему фронту тактового импульса записывается в регистр 53, значение элемента а в регистры 55 и 56, так как при τ1 1, элементы И 72 группы открыты, значение элемента b записывается в первые разряды 571 и 581 групп регистров 57 и 58, так как при τ1 1 элементы И 66 группы открыты. При завершении переходных процессов на выходы комбинационного умножителя 59 формируется значение а˙b, а на выходе комбинационного сумматора 60 значение с + а˙b, которое записывается в регистр 54 по заднему фронту следующего тактового импульса. Таким образом, информация с выхода сумматора 60 выдается через регистр 54 на выход 85 вычислительного узла с задержкой на один такт, значение элемента b выдается на выход 84 вычислительного узла с задержкой на D+2 тактов. Во втором режиме работы (τ1, τ2) (0,1), на выходы 77, 75 и 76 вычислительного узла подаются значения элементов с, а и b. По заднему фронту тактового импульса значение элемента с записывается в регистр 53,значение элемента b в регистр 55, значение элемента а записывается в первые разряды 571 и 581 групп регистров 57 и 58. По завершении переходных процессов на выходе умножителя 59 формируется значение а1˙b, где значение элемента а1записано в регистр 56 ранее при τ11, на выходе сумматора 60 значение с + а1˙b, которое записывается в регистр 54 по заднему фронту следующего тактового импульса. Таким образом, информация с выхода сумматора 60 выдается через регистр 54 на выход 85 вычислительного узла с задержкой на один такт. Происходит также сдвиг в регистрах 57 и 58, в результате которого из j-х разрядов регистров 57 и 58 осуществляется перезапись значений элементов в (j+1)-е разряды этих регистров.

В третьем режиме работы (τ1, τ2) (1,0) на входы 77, 75 и 76 подаются значения элементов с, а и b. По заднему фронту тактового импульса значение элемента с записывается в регистр 53, значение элемента а в регистры 55 и 56, значение элемента b записывается в первые разряды 581 сдвигающих регистров 58. Значение элемента b1, записанное в D-х разрядах 57D сдвигающих регистров 57 на предыдущем такте, переписывается через открытые элементы И 65 и 67 и через элементы ИЛИ 69 и 70 групп в первые разряды 571 группы регистров 57. На выходе умножителя 59 формируется значение а˙b1, на выходе сумматора 60 значение с + a˙b1, которое записывается в регистр 54 на следующем тактовом импульсе. Таким образом, информация с выхода сумматора 60 выдается через регистр 54 на выход 85 вычислительного узла с задержкой на один такт. Происходит также сдвиг в регистрах 57 и 58, в результате которого из j-х разрядов регистров 57 и 58 осуществляется перезапись значений элементов в (j+1)-е разряды этих регистров. В четвертом режиме работы (τ1, τ2) (0, 0) на выходы 77, 75 и 76 подаются значения элементов с, а и b. По заднему фронту тактового импульса значение элемента с записывается в регистр 53, значение элемента а', записанное в регистре 56 при τ1 1 и значение элемента b', записанное в первых разрядах 571 группы регистров 57 при τ2 1, поступают на соответствующие информационные входы умножителя 59. На входы сумматора 60 поступает информация с выхода умножителя 59 и с выхода регистра 53. На выходе сумматора 60 формируется значение с + а' b', которое записывается в регистр 54 по заднему фронту следующего тактового импульса. Происходит также сдвиг в регистрах 57 и 58, в результате которого из j-х разрядов регистров 57 и 58 осуществляется перезапись значений элементов в (j+1)-е разряды этих регистров.

Организация входного потока значений элементов aij, bij и cij(0)управляющих сигналов τ1, τ2 и выходного потока значений элементов сijзадается следующими выражениями.

Значения элементов аik подаются на вход 9 устройства в моменты времени
t Di + k + 2 + t0, где i 1.D, k 1.Q,
to (Q 2) D 2, D max (I, Q).

Значения элементов bkj подаются на вход 10 устройства в моменты времени t j Dk + 2D + 2 + to, где j 1.I.

Значения элементов сij(o) подаются на вход 11 устройства в моменты времени t Di + j + 2 + to.

Управляющий сигнал τ1 1 подается на вход 12 устройства в моменты времени t Dr + 3 + to, в остальные моменты τ1 0, где r 2 Q, I.

Управляющий сигнал τ2 1 подается на вход 13 устройства в моменты времени t q + D + 2 + to, в остальные моменты τ2 0, где q 1, D.

На выходе 22 устройства значение элементов сij формируется в моменты времени t= Di + j + 2Q + 1 + to. Время вычисления последнего элемента СIT равно (I + Q 2) D + 2Q T 1 тактов. Период ввода элементов для умножения последующих матриц А и В равен (I + Q 1)D 1 тактов.

В каждом блоке обработки 1 проводится дублирование операций с помощью вычислительных узлов 24 и 25. Результаты выполнения операций формируются на выходе сумматора 60 по завершении переходных процессов в комбинационных схемах 59 и 60 и выдаются на выходы 80 вычислительных узлов 24 и 25. Эти результаты поступают соответственно на информационные входы узла сравнения 26. При совпадении информации, поступающей на информационные входы узла сравнения 26 из вычислительных узлов 24 и 25, данный блок обработки считается исправным и единица с выхода узла сравнения 26 устанавливается триггер 27 в единичное состояние и он используется для фиксации признака исправности данного блока обработки 1j. С выхода триггера 27 единица поступает на соответствующие входы элемента И 30 группы и информация с выходов регистров 54 и 55, триггеров 62 и 64 и регистра 58L+2 соответственно через выходы 85, 83, 86, 87 и 84 вычислительного узла 24, через элементы И 30 группы и элементы ИЛИ 31 группы поступают соответственно на выходы 47-51 данного блока обработки 1j. Единичный сигнал с выхода триггера 27 поступает также на инверсный вход элементов И 29 группы и блокирует обход данного блока обработки, в результате этого значения элементов с, а, b и сигналы τ1, τ2 поступают из предыдущего блока обработки 1j-1 соответственно на входы 33-37 и через открытые элементы И 28 группы на соответствующие входы вычислительных узлов 24 и 25. Единичный сигнал с выхода триггера 27 через выход 46 признака отказа данного блока обработки поступает на соответствующий информационный вход сумматора 2j и на выход 21j признака отказа устройства.

При несовпадении информации, поступающей на информационные входы узла сравнения 28 из вычислительных узлов 24 и 25, данный блок обработки 1j считается неисправным и нулевой сигнал с выхода узла сравнения 26 устанавливает триггер 27 в нулевое состояние. С выхода триггера 27 нулевой сигнал поступает на соответствующие входы элементов И 30 и выдача информации с выходов регистров 54, 55, триггеров 62, 64 и регистра 58L+2 соответственно через выходы 85, 83, 86, 87 и 84 блокируется. Нулевой сигнал выхода триггера 27 поступает также на соответствующие входы элементов И 28 группы на инверсные входы элементов И 29 группы. В результате поступление значений элементов с, а и b и сигналов τ1, τ2 в узлы 24 и 25 через элементы И 28 группы блокируется и открывается путь обхода данного блока обработки 1j. В этом случае значения элементов с, а, b и сигналы τ1, τ2 поступающие из предыдущего блока обработки 1j-1 через элементы И 29 группы и элементы ИЛИ 31 группы 31 группы, выдаются соответственно на выходы 47-51 данного блока обработки. Нулевой сигнал с выхода триггера 27 через выход 46 признака отказа данного блока обработки поступает на соответствующий информационный вход сумматора 2j и на выход 21j признака отказа устройства.

Для того, чтобы в определенных ситуациях принудительно вывести блок 1j из состава устройства, используется установочный вход 15j устройства. В этом случае внешними средствами управления на входе 15j устройства формируется сигнал, который через вход 43 блока обработки 1j поступает на вход установки в ноль триггера 27. Для того, чтобы принудительно ввести блок 1j обработки в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 16j устройства. В этом случае внешними средствами управления на входе 16j устройства формируется сигнал, который через вход 44 блока обработки 1j поступает на вход установки в единицу триггера 27. При этом работа блока 1j может быть блокирована путем подачи на вход 18j устройства единичного значения. В этом случае единичный сигнал через вход 39 блока 1j поступает на инверсный вход элемента И 32 и блокирует прохождение тактовых импульсов на тактовые входы узлов 24 и 25 и триггера 27. Для установки регистров и триггеров вычислительных узлов 24 и 25 в исходное состояние при запусках и перезапусках устройства используется вход 17j устройства. Для установки блока 1j в исходное состояние на вход 17j устройства поступает единичный сигнал, который через вход 41 блока 1j поступает на выходы установки в исходное состояние вычислительных узлов 24 и 25 и далее на входы установки в нулевое состояние всех регистров и триггеров узлов 24 и 25 (на фиг. 3 соответствующие цепи не показаны).

Значение D размерности перемножаемых матриц подается на вход 20 устройства. В процессе работы устройства одновременно с подачей значений aik, bkj, cij(o), τ1 и τ2 на соответствующие входы блока 11 на вход 14 устройства подается нулевое значение величины g. В случае исправности всех блоков обработки на выходах 21 устройства будут присутствовать единичные значения. Тогда на произвольном такте с выхода комбинационного сумматора 2i будет сниматься значение g= i, которое запишется в регистр 3i и поступит на соответствующий вход узла сравнения 5i. При совпадении значений g и D с выхода узла 5i будет выдан единичный сигнал, который откроет группу элементов И 6 и, таким образом, вычисленное значение элемента с(D) через группу элементов И 6D и группу элементов ИЛИ 7 поступит на выход 22 результата устройства. При этом с выходов остальных узлов сравнения 5 будут выдаваться нулевые сигналы, единичный сигнал с выхода узла 5D поступит на соответствующий вход элемента ИЛИ-НЕ 8, с выхода которого на выход 23 признака отказа устройства поступит нулевой сигнал. Оставшиеся в данном случае блоки 1D+1.1D+R, где L D + R, являются избыточными и используются в качестве резерва. Избыточные (резервные) блоки 1D+1, 1D+R, как и рабочие блоки 11, 1D, непрерывно проверяются, поскольку информация с выходов блока 1Dпоступает также на соответствующие входы блока 1D+1. В резервных блоках 1D+1, 1D+R, как и в основных, происходит обработка информации в узлах 24 и 25, сравнение результатов в узле 26 и запись результата сравнения в триггер 27.

При обнаружении отказа блока 1j осуществляется обход этого блока, при этом нулевой сигнал с выхода 46 блока 1j выдается на выход 21j и на соответствующий вход комбинационного сумматора 2j. В этом случае с выхода комбинационного сумматора 2j выдается значение g j -1, с выхода комбинационного сумматора 2j+1 выдается значение g j и т.д. с выхода комбинационного сумматора 2D выдается значение g D-1. При этом с выхода узла сравнения 5D будет выдан нулевой сигнал, который закроет группу элементов И 6D. Если первый резервный блок обработки 1D+1является исправным, т.е. с выхода 46 блока 1D+1 выдается единица, то с выхода комбинационного сумматора 2D+1 будет выдано значение D. В этом случае с выхода узла сравнения 5D+1 будет выдан единичный сигнал, который откроет группу элементов И 6D+1, и вычисленное значение С(D)через группу элементов И 6D+1 и группу элементов ИЛИ 7 выдается на выход 22 устройства. При обнаружении S1 отказов среди основных блоков 11, 1D и наличии S2 отказов среди резервных блоков 1D+1. 1D+R с выхода комбинационного сумматора 2D на текущем такте будет сниматься значение g D S1, которое на следующем такте поступает на соответствующий вход комбинационного сумматора 2D+1, в результате этого с выхода узла сравнения 5D будет выдан нулевой сигнал, который закроет группу элементов И 6D. С выхода комбинационного сумматора 2p, где p число задействованных блоков 1 линейки (в том числе и отказавших), D + S1 ≅ p < D + S1 + S2 будет выдано значение g D, в результате этого с выхода узла сравнения 5p будет выдан единичный сигнал, который откроет границу элементов И 6p. Если число отказавших блоков 1 превышает число резервных, т.е. при S1 + S2 > R, с выходов узлов сравнения 51, 5D+Rвыдаются нулевые значения, которые закрывают все группы элементов И 6 и поступают на входы элемента ИЛИ-НЕ 8, с выхода которого единичный сигнал поступает на выход 23 признака отказа устройства. Единичный сигнал на выходе 23 свидетельствует об окончательном отказе устройства. При обходе отказавшего блока 1j на такте t происходит также обход соответствующих сумматора 2j и регистра 3j следующим образом. Значение g, где g ≅ j, с выходов элементов И 4j-1, поступает на вход 38 блока 1j и через открытую группу элементов И 29 поступает с выхода 52 блока 1j на входы группы элементов ИЛИ 4j, с выхода которых значение g поступает на вход 38 блока 1j+1. На такте t+1 нулевое значение с выхода 45 блока 1j складывается на сумматоре 2 с нулевым значением, поступающем с выхода 46 блока 1j, нулевое значение результата сложения через регистр 3j поступает на соответствующие входы группы элементов ИЛИ 4j и в дальнейшем не влияет на формирование текущего значения величины g для следующих блоков 1h, где h > j. Таким образом, если на t-м такте работы устройства произошел отказ блока 1j, то начиная с (t+1)-го такта значение g на выходах комбинационных сумматоров 2h, соответствующих исправным блокам 1h, будет меняться, и неискаженная информация в течение следующих 2(D-j) тактов еще будет выдаваться с выхода результата устройства.

Рассмотрим работу устройства для случая I T 2, Q 3, R 1. Если в процессе работы не обнаружено отказов блоков 1, то значение элементов aik, bkj и cij(o) подаются на входы 9, 10 и 11 устройства в моменты времени:
t= 3i + k + 3; i, j 1, 2; k 1, 2, 3;
t= j 3k + 9; j 1, 2;
t 3i + j + 3;
Значения элементов результирующей матрицы Сij формируются в моменты времени
t= 3i + j + 8.

В этом случае состояние триггеров 61, 63, регистров 53, 55, 56, первых разрядов 571 сдвигающих регистров 57, D-х разрядов 57 сдвигающих регистров 57, первых разрядов 581 сдвигающих регистров 58, (D+2)-х разрядов сдвигающих регистров 58, сумматора 60 и регистра 54 блоков обработки 11, 12 и 13 приведен в табл. 1.

Пусть на десятом такте работы устройства обнаружен отказ блока обработки 12. В этом случае состояния триггеров 61 и 63, регистров 53-56, 571, 581 и 58i+2, сумматора 60, блоков обработки 11, 12, 13 и 14(где 14 резервный блок обработки) приведены в табл. 2, 2'.

На такте t 10 обнаружен отказ блока 12, на такте t 11 произведено обнуление блока 11 и произошла блокировка блока 12 (в дальнейшем информация, находящаяся в его узлах, не влияет на дальнейший процесс обработки), на такте t 12 произведен перезапуск устройства (на входы блока 11 начата подача соответствующих значений), произведено обнуление и блокировка блока 13, на такте t 13 произведена разблокировка блока 13. С такта t 12 производится обход блока 12 и включение в работу резервного блока 14. Длина линейки устройства остается прежней. Возможный алгоритм восстановления вычислительного процесса после обнаружения отказа блока 1j предусматривает следующую последовательность действий:
такт i: фиксирование блока 1j с обнаруженным отказом, блокировка блока 1j, чтение информации с блока 1j+1 в блок 1j+2, обнуление блока 1j+1 и блокировка блока 1j+1;
такт i+1: чтение информации с блока 1j+2 в блок 1j+3, блокировка и обнуление блока 1j+2, обнуление блоков 11. 1j-1.

такт i+2: чтение информации с блока 1j+3 в блок 1j+4, блокировка и обнуление блока 1j+3 разблокировка блока 1j+1, перезапуск;
такт i+3: чтение информации с блока 1j+4 в блок 1j+5, блокировка и обнуление блока 1j+4, разблокировка блока 1j+2;
такт i + R: чтение информации с блока 1j+k+1 в блок 1j+k+2, блокировка и обнуление блока 1j+k+1, разблокировка блока 1j+k-1;
При k D-j происходит подключение выхода используемого резервного блока 14 к выходу 22 устройства.

Если tn время (число тактов), требуемое для подготовки к перезапуску устройства со стороны средств внешнего управления, то время реинициализации линейки составит j+tn тактов, время восстановления работоспособности устройства составит два такта (т.е. через 2 такта после обнаружения отказа на входы 9-14 можно подавать соответствующие значения). Пусть на такте t 10 появившийся отказ блока обработки 12привел к обходу 12 и запрещение выдачи информации с вычислительного узла 24 на выходы 47-52 блока 12. Блокировка работы блока 12 осуществляется подачей единичных сигналов на вход 182 устройства. Обнуление блока 11осуществляется с помощью подачи единичного сигнала на вход 151установки. Отметим, что входы 15 установки подключены ко входам установки в нуль всех регистров, регистров и триггеров вычислительных узлов 24 и 25 и на фиг. 3 не показаны. В силу технологической структуры кристалла ИС состояния исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем больше, чем выше уровень технологии и степень интеграции ИС. Наличие не менее чем 16-разрядных умножителя 59 комбинационного типа, сумматора 60 комбинационного типа, групп регистров 57 и 58 (не менее чем 16 D-разрядных и (D+2)-разрядных) и регистров 53-56 обуславливают степень интеграции и уровень технологии, достаточные для проявления высокой степени корреляции отказов. При контроле дублированием вычислительных узлов необходимо, чтобы отказы этих узлов были независимы. Для этого нужно, чтобы узлы 24 и 25 блока обработки 1 были реализованы на разных кристаллах ИС. Аналогично, исходя из соображений корреляции отказов внутри кристалла ИС, необходимо, чтобы избыточные (резервные) блоки обработки 1 не размещались на одних кристаллах ИС вместе с рабочими.

Технико-экономический эффект предлагаемого устройства заключается в следующем.

В предлагаемом устройстве осуществляется непрерывный аппаратный контроль на протяжении всего времени работы и блокировка выдачи ошибочной информации при обнаружении отказавшего блока обработки. В устройстве реализован наиболее полный аппаратный контроль, ориентированный на обнаружение отказов всех видов, при этом время контроля сравнимо с тактовым периодом. Достоверность функционирования блока обработки систолического устройства будет определяться как
Dф(t) Pпр(t) + P0,0(t), где Рпр(t) вероятность правильной работы блока обработки 1;
Р0,0(t) вероятность правильной работы блока обработки 1 и выдачи с выхода 46 блока 1 сигнала отказа.

Для рассматриваемого систолического устройства
Рпр(t) Руз2(t),
Р0,0(t) 2Pуз(t)(1-Руз(t)), где Руз(t) вероятность безотказной работы вычислительного узла 24 (25).

Достоверность функционирования всего устройства определяется выражением
Dф (2Руз(t) Руз2(t))D.

При Руз 0,99, D 3, Dф 0,996,
Руз 0,99, D 10, Dф 0,9891,
Руз 0,999, D 3, Dф 0,000007,
Руз 0,999, D 10, Dф 0,999989,
Руз 0,999 и выше Dф практически равна 1.

Время восстановления вычислительного процесса (получение достоверного результата на выходе устройства) пропорционально значению nотк, где nотк ≅D минимальный номер среди номеров отказавших блоков обработки линейки устройства.

Похожие патенты RU2049352C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ ТРЕХ МАТРИЦ И ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2066878C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2049350C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СВЕРТКИ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2112274C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2066879C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (n n) МАТРИЦЫ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2117987C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2051412C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОЙ СВЕРТКИ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
  • Косьянчук Виктор Васильевич
RU2117986C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОЙ СВЕРТКИ 1993
  • Якуш Виктор Павлович[Ru]
  • Косьянчук Виктор Васильевич[By]
  • Смирнов Виталий Александрович[Ru]
RU2049353C1
УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ N X N МАТРИЦ 1990
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
RU2037199C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР 1991
  • Якуш В.П.
  • Тиунчик А.А.
  • Лиходед Н.А.
  • Соболевский П.И.
RU2011222C1

Иллюстрации к изобретению RU 2 049 352 C1

Реферат патента 1995 года УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ ДВУХ МАТРИЦ

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах, в частности, при цифровой обработке сигналов для перемножения двух матриц. Цель изобретения повышение надежности за счет организации контроля и резервирования и расширение функциональных возможностей за счет решение задач различных размерностей. Поставленная цель достигается тем, что устройство содержит L D + R блоков обработки, где D размерность матриц, R - число избыточных блоков обработки, L комбинационных сумматоров, L 1 регистров, с первой по (L 1)-ю группу элементов ИЛИ, L узлов сравнения, L групп элементов И, L-ю группу элементов ИЛИ и элемент ИЛИ. В основу работы устройства положена параллельно-последовательная организация вычислений с аппаратным контролем, обходом и замещением отказавших блоков обработки. 1 з. п. ф-лы, 3 ил. 2 табл.

Формула изобретения RU 2 049 352 C1

1. УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ ДВУХ МАТРИЦ, содержащее L блоков обработки, каждый из которых включает первый вычислительный узел, где L > D, D размер обрабатываемых матриц, причем тактовый вход устройства подключен к тактовым входам блоков обработки с первого по L-й, информационные входы первой, второй и третьей групп, первый и второй управляющие входы устройства подключены соответственно к информационным входам первой, второй и третьей групп, к первому и второму управляющим входам первого блока обработки, информационные входы первой второй и третьей групп, первый и второй управляющие входы а-го блока обработки (где а=2, L) подключены соответственно к выходам первой, второй и третьей групп, к первому и второму выходам (a 1)-го блока обработки, отличающееся тем, что устройство содержит L комбинационных сумматоров, L узлов сравнения, L 1 регистров, L групп элементов И, L групп элементов ИЛИ и элемент ИЛИ НЕ, причем управляющие входы групп устройства подключены соответственно к управляющим входам группы первого блока обработки, выходы четвертой группы b-го блока обработки (где b=1, L 1) подключены соответственно к первым входам элементов ИЛИ b-й группы, выходы которых подключены соответственно к управляющим входам группы (b + 1)-го блока обработки, C-е входы установки в исходное состояние первой, второй и третьей групп устройства (где C 1, L) подключены соответственно к первому, второму и третьему входам установки в исходное состояние C-го блока обработки, C-й вход блокировки устройства подключен к входу блокировки C-го блока обработки, выходы третьей группы C-го блока обработки подключены соответственно к первым входам элементов И C-й группы, выходы которых подключены соответственно к входам C-й группы элементов ИЛИ L-й группы, выходы которых подключены соответственно к выходам результата устройства, третий выход C-го блока обработки подключен к C-му выходу признака отказа группы устройства и информационному входу C-го комбинационного сумматора, выходы b-го комбинационного сумматора подключены к входам первой группы b-го узла сравнения и информационным входам b-го регистра, выходы которого подключены соответственно к вторым входам элементов ИЛИ b-й группы, выходы L-го комбинационного сумматора подключены соответственно к входам первой группы L-го узла сравнения, выход C-го узла сравнения подключен к вторым входам элементов И C-й группы и C-му входу элемента ИЛИ НЕ, выход которого подключен к выходу признака отказа устройства, входы задания размерности обрабатываемых матриц которого подключены соответственно к входам вторых групп узлов сравнения с первого по L -й и информационным входам четвертых групп блоков обработки с первого по L-й, выходы пятой группы C-го блока обработки подключены соответственно к информационным входам группы C-го комбинационного сумматора, тактовый вход устройства подключен к тактовым входам узлов задержки на два такта с первого по (L 1)-й, а каждый блок обработки дополнительно содержит второй вычислительный узел, узел сравнения, триггер, три блока элементов И, блок элементов ИЛИ и элемент И, причем в каждом блоке обработки информационные входы первой, второй, третьей групп, управляющие входы группы, первый и второй управляющие входы подключены соответственно к входам групп первого и второго блоков элементов И, выходы первой группы которого подключены соответственно к входам первой группы блока элементов ИЛИ, выходы которого подключены соответственно к выходам первой, второй, третьей групп, к первому и второму выходам блока обработки, выходы первой группы первого блока элементов И подключены соответственно к информационным входам групп с первой по третью, к первому и второму управляющим входам первого и второго вычислительных узлов, выходы групп с первой по третью, первый и второй выходы первого вычислительного узла подключены соответственно к входам группы третьего блока элементов И и соответственно к входам первой группы узла сравнения, выходы третьего блока элементов И подключены соответственно к входам второй группы блока элементов ИЛИ, выходы вторых групп первого и второго блоков элементов И подключены соответственно к выходам пятой и четвертой групп блока обработки, информационные входы четвертой группы которого подключены к информационным входам первого и второго вычислительных узлов, выходы групп с первой по третью, первый и второй выходы второго вычислительного узла подключены соответственно к входам второй группы узла сравнения, выход которого подключен к информационному входу триггера, выход которого подключен к входам первого и третьего блоков элементов И, инверсному входу второго блока элементов И и третьему выходу блока обработки, тактовый вход которого подключен к первому входу элемента И, выход которого подключен к тактовым входам первого и второго вычислительных блоков и триггера, вход блокировки, первый, второй и третий входы установки в исходное состояние блока обработки подключены соответственно к второму (инверсному) входу элемента И, входам установки в исходное состояние вычислительных узлов, к входу установки в нулевое состояние триггера и входу установки в единичное состояние триггера. 2. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит четыре регистра, дешифратор, две группы регистров, умножитель, сумматор, четыре триггера, 2L + 2 группы элементов И, три группы элементов ИЛИ, элемент И и элемент НЕ, причем в каждом вычислительном узле информационные входы первой группы вычислительного узла подключены соответственно к информационным входам первого регистра и соответственно к информационным входам второго регистра, выходы которого подключены к информационным входам первой группы умножителя, выходы которого подключены соответственно к информационным входам первой группы сумматора, выходы первого регистра подключены соответственно к выходам первой группы вычислительного узла, информационные входы второй группы которого подключены соответственно к информационному входу первого регистра первой группы и первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ первой группы, выходы которых подключены соответственно к информационному входу первого регистра второй группы, выходы которого подключены соответственно к информационным входам второй группы умножителя, выходы P-го регистра второй группы (где P=1, L) подключены соответственно к первым входам элементов И P-й группы, выходы элементов И с первой по L-ю групп подключены соответственно к входам элементов ИЛИ второй группы, выходы которых подключены соответственно к первым входам элементов И (L + 2)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ первой группы, выходы с третьего по (L + 2)-й регистров первой группы подключены соответственно к первым входам элементов И с первой по L-ю группу, выходы которых подключены соответственно к входам элементов ИЛИ третьей группы, выходы которых подключены соответственно к входам второй группы вычислительного узла, информационные входы третьей группы которого подключены соответственно к информационным входам третьего регистра, выходы которого подключены соответственно к информационным входам второй группы сумматора, выходы которого подключены соответственно к информационным входам чертвертого регистра, выходы которого подключены соответственно к выходам третьей группы вычислительного узла, первый управляющий вход которого подключен к первому входу элемента И и информационному входу первого триггера, выходы которых подключены соответственно к входу синхронизации второго регистра и информационному входу второго триггера, выходы которого подключены к первому выходу вычислительного узла, второй управляющий вход которого подключен к вторым входам элементов И первой группы, входу элемента НЕ и информационному входу третьего триггера, выходы элемента НЕ и третьего триггера подключены соответственно к вторым входам элементов И (L + 2)-й группы и информационному входу четвертого триггера, выход которого подключен к второму выходу вычислительного узла, информационные входы четвертой группы которого подключены к входам дешифратора, q-й выход которого (где q 1, L) подключен к вторым входам элементов И (q + 1)-й и (L + q + 2)-й групп, тактовый вход и вход начальной установки вычислительного узла подключены соответственно к входам синхронизации и входам установка нулевого состояния всех регистров и триггеров.

Документы, цитированные в отчете о поиске Патент 1995 года RU2049352C1

Аппарат для очищения воды при помощи химических реактивов 1917
  • Гордон И.Д.
SU2A1
Устройство для умножения матриц 1990
  • Якуш Виктор Павлович
  • Косьянчук Виктор Васильевич
  • Лиходед Николай Александрович
  • Соболевский Павел Иосифович
SU1793446A1
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

RU 2 049 352 C1

Авторы

Якуш Виктор Павлович

Смирнов Виталий Александрович

Даты

1995-11-27Публикация

1993-04-28Подача