устройство для перемножения двух матриц

Классы МПК:G06F17/16 матричные или векторные вычисления
Автор(ы):,
Патентообладатель(и):Якуш Виктор Павлович,
Смирнов Виталий Александрович
Приоритеты:
подача заявки:
1993-04-28
публикация патента:

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

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

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

Описание изобретения к патенту

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

Наиболее близким по технической сущности к заявляемому устройству является устройство для обработки информации [2] в частности для перемножения матриц АIxQ x BQ x T, содержащее 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устройство для перемножения двух матриц, патент № 2049352bkj, k 1.Q.

Вычислительный узел 24 (25) обладает возможностью реализации функций:

aвыхi+1 aiвх; bвыхi+D+2 biвх;

Ci+2вых Ciвх + устройство для перемножения двух матриц, патент № 2049352 устройство для перемножения двух матриц, патент № 2049352

устройство для перемножения двух матриц, патент № 20493521выхi+2=устройство для перемножения двух матриц, патент № 20493521вхi

устройство для перемножения двух матриц, патент № 20493522выхi+2=устройство для перемножения двух матриц, патент № 20493522вхi где

aiвх, biвх, ciвх значения соответственно на информационных входах 75, 76 и 77 вычислительного узла на i-м такте;

устройство для перемножения двух матриц, патент № 20493521вхi, устройство для перемножения двух матриц, патент № 20493522вхi значения соответственно на управляющих входах 78 и 79 вычислительного узла на i-м такте;

aiвых, biвых, сiвых, устройство для перемножения двух матриц, патент № 20493521выхi, устройство для перемножения двух матриц, патент № 20493522выхi- значения соответственно на выходах 83 87 вычислительного узла на i-м такте.

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

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

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

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

Значения элементов аik подаются на вход 9 устройства в моменты времени

tустройство для перемножения двух матриц, патент № 2049352 Di + k + 2 + t0, где i 1.D, k 1.Q,

to (Q 2) D 2, D max (I, Q).

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

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

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

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

На выходе 22 устройства значение элементов сij формируется в моменты времени tустройство для перемножения двух матриц, патент № 2049352= 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 и сигналы устройство для перемножения двух матриц, патент № 20493521, устройство для перемножения двух матриц, патент № 20493522 поступают из предыдущего блока обработки 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 и сигналов устройство для перемножения двух матриц, патент № 20493521, устройство для перемножения двух матриц, патент № 20493522 в узлы 24 и 25 через элементы И 28 группы блокируется и открывается путь обхода данного блока обработки 1j. В этом случае значения элементов с, а, b и сигналы устройство для перемножения двух матриц, патент № 20493521, устройство для перемножения двух матриц, патент № 20493522 поступающие из предыдущего блока обработки 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), устройство для перемножения двух матриц, патент № 20493521 и устройство для перемножения двух матриц, патент № 20493522 на соответствующие входы блока 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 устройство для перемножения двух матриц, патент № 2049352 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 устройство для перемножения двух матриц, патент № 2049352 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устройство для перемножения двух матриц, патент № 2049352= 3i + k + 3; i, j 1, 2; k 1, 2, 3;

tустройство для перемножения двух матриц, патент № 2049352= j 3k + 9; j 1, 2;

tустройство для перемножения двух матриц, патент № 2049352 3i + j + 3;

Значения элементов результирующей матрицы Сij формируются в моменты времени

tустройство для перемножения двух матриц, патент № 2049352= 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отк устройство для перемножения двух матриц, патент № 2049352D минимальный номер среди номеров отказавших блоков обработки линейки устройства.

Класс G06F17/16 матричные или векторные вычисления

способ оптимизации алгоритма управления конкретным объектом и/или процессом -  патент 2479864 (20.04.2013)
устройство вращения вектора -  патент 2475830 (20.02.2013)
устройство нормировки вектора -  патент 2473961 (27.01.2013)
устройство для моделирования процесса принятия решения в условиях неопределенности -  патент 2468423 (27.11.2012)
ячейка однородной вычислительной среды и устройство для сжатия двоичных векторов на базе ячеек однородной вычислительной среды -  патент 2450327 (10.05.2012)
устройство нормировки вектора -  патент 2449354 (27.04.2012)
инструкция и логическая схема для выполнения операции скалярного произведения -  патент 2421796 (20.06.2011)
способ передачи-приема сигнала в многопользовательской системе радиосвязи с множеством передающих и множеством приемных антенн -  патент 2398359 (27.08.2010)
устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации -  патент 2398270 (27.08.2010)
устройство вычисления сумм произведений -  патент 2306595 (20.09.2007)
Наверх