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

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

Наиболее близким по технической сущности к заявляемому устройству является устройство для обработки информации [2] в частности для перемножения матриц А_IxQ x B_QxT, содержащее 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, 67₁. 67L, 68₁,68L, три группы элементов ИЛИ 69, 70, и 71, элемент И 72 и элемент НЕ 73, причем в каждом вычислительном узле информационные входы 75 первой группы подключены к информационным входам первого регистра 55 и второго регистра 56, выходы которого подключены к информационным входам первой группы умножителя 59, выходы которого подключены соответственно к информационным входам первой группы сумматора 60, выходы первого регистра 55 подключены к выходам 83 первой группы вычислительного узла, информационные входы 79 второй группы которого подключены к информационному входу первого регистра первой группы 58 и к первым входам элементов И первой группы 66, выходы которых подключены к первым входам элементов ИЛИ первой группы 69, выходы которых подключены к информационному входу первого регистра 57₁ второй группы 57, выходы которого подключены к информационным входам второй группы умножителя 59, выходы р-го регистра второй группы 57 (где р 1, L) подключены к первым входам элементов И р-й группы 67р, выходы элементов И 67 с первой по L-ю группу подключены ко входам элементов ИЛИ второй группы 70, выходы которых подключены к первым входам элементов И 65 (L+2)-й группы, выходы которых подключены ко вторым входам элементов ИЛИ первой группы 69, выходы с третьего по (L+2)-й регистра первой группы 58 подключены соответственно к первым входам элементов И с первой по L-ю группу 68₁, 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:
C_ij⁽⁰⁾ 0; i 1.I; j 1.T;
C_ij^(k) C_ij^(k-1) + a_ik˙b_kj, k 1.Q.

Вычислительный узел 24 (25) обладает возможностью реализации функций:
a_выхⁱ⁺¹ aⁱ_вх; b_вых^i+D+2 bⁱ_вх;
Ci+2вых

Ciв_х +
τ_1выхⁱ⁺²=τ_1вхⁱ
τ_2выхⁱ⁺²=τ_2вхⁱ где
aⁱ_вх, bⁱ_вх, cⁱ_вх значения соответственно на информационных входах 75, 76 и 77 вычислительного узла на i-м такте;
τ_1вхⁱ, τ_2вхⁱ значения соответственно на управляющих входах 78 и 79 вычислительного узла на i-м такте;
aⁱ_вых, bⁱ_вых, сⁱ_вых, τ_1выхⁱ, τ_2выхⁱ- значения соответственно на выходах 83 87 вычислительного узла на i-м такте.

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

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

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

Организация входного потока значений элементов a_ij, b_ij и c_ij⁽⁰⁾управляющих сигналов τ₁, τ₂ и выходного потока значений элементов с_ijзадается следующими выражениями.

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

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

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

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

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

На выходе 22 устройства значение элементов с_ij формируется в моменты времени t= D_i + j + 2Q + 1 + t_o. Время вычисления последнего элемента С_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 в единичное состояние и он используется для фиксации признака исправности данного блока обработки 1_j. С выхода триггера 27 единица поступает на соответствующие входы элемента И 30 группы и информация с выходов регистров 54 и 55, триггеров 62 и 64 и регистра 58_L+2 соответственно через выходы 85, 83, 86, 87 и 84 вычислительного узла 24, через элементы И 30 группы и элементы ИЛИ 31 группы поступают соответственно на выходы 47-51 данного блока обработки 1_j. Единичный сигнал с выхода триггера 27 поступает также на инверсный вход элементов И 29 группы и блокирует обход данного блока обработки, в результате этого значения элементов с, а, b и сигналы τ₁, τ₂ поступают из предыдущего блока обработки 1_j-1 соответственно на входы 33-37 и через открытые элементы И 28 группы на соответствующие входы вычислительных узлов 24 и 25. Единичный сигнал с выхода триггера 27 через выход 46 признака отказа данного блока обработки поступает на соответствующий информационный вход сумматора 2_j и на выход 21_j признака отказа устройства.

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

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

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

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

Рассмотрим работу устройства для случая I T 2, Q 3, R 1. Если в процессе работы не обнаружено отказов блоков 1, то значение элементов a_ik, b_kj и c_ij^(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, первых разрядов 57₁ сдвигающих регистров 57, D-х разрядов 57 сдвигающих регистров 57, первых разрядов 58₁ сдвигающих регистров 58, (D+2)-х разрядов сдвигающих регистров 58, сумматора 60 и регистра 54 блоков обработки 1₁, 1₂ и 1₃ приведен в табл. 1.

Пусть на десятом такте работы устройства обнаружен отказ блока обработки 1₂. В этом случае состояния триггеров 61 и 63, регистров 53-56, 57₁, 58₁ и 58_i+2, сумматора 60, блоков обработки 1₁, 1₂, 1₃ и 1₄(где 14 резервный блок обработки) приведены в табл. 2, 2'.

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

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

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

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

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

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

Достоверность функционирования всего устройства определяется выражением
D_ф (2Р_уз(t) Р_уз²(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 минимальный номер среди номеров отказавших блоков обработки линейки устройства.

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

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)-й групп, тактовый вход и вход начальной установки вычислительного узла подключены соответственно к входам синхронизации и входам установка нулевого состояния всех регистров и триггеров.