УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ ТРЕХ МАТРИЦ И ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Российский патент 1996 года по МПК G06F17/00 

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

Обычно для обеспечения достоверности получаемых при обработке информации результатов используется тестовый периодический контроль, проводимый с помощью внешних программно-аппаратных средств. При периодическом тестовом контроле вероятность пропуска отказа блока обработки пропорциональна времени между тестовыми проводками (период контроля), при этом объем ошибочной информации, выдача которой происходит между тестовыми проверками, также пропорционален периоду контроля. Временные затраты на тестовую проверку определяются объемом теста, поэтому пропускная способность линейки из блоков обработки известных устройств находится в обратно пропорциональной зависимости от временных затрат на тестовые проверки. Вероятность обнаружения отказа с помощью тестовых проверок определяется разрешающей способностью теста и объемом аппаратуры, охваченной контролем. Время восстановления вычислительного процесса после обнаружения отказа блока обработки (получение достоверного результата на выходе устройства) пропорционально числу P блоков обработки устройства (длине P линейки устройства).

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

Поставленная цель достигается тем, что в устройство, содержащее P блоков обработки 1₁,1_P, причем тактовый вход 15 устройства подключен к тактовым выходам блоков обработки с первого по P-й, информационные входы первой и второй групп 9 и 10, первый, второй и третий управляющие входы 11, 12 и 13 устройства подключены соответственно к информационным входам первой и второй групп, к первому, второму и третьему управляющим входам первого блока обработки, выходы первой группы, второй группы, первый, второй и третий выходы i-го блока обработки (i 1,P-1) подключены соответственно к информационным входам первой группы, второй группы, к первому, второму и третьему управляющим входам (i+1)-го блока обработки, введены с (P+1)-го по L-й блоки обработки 1 (L P+R, R число резервных блоков обработки), L комбинационных сумматоров 2, L-1 регистров 3, L узлов сравнения 4, L групп элементов ИЛИ 5, L групп элементов И 7 и элемент ИЛИ-НЕ 8, при этом тактовый вход 16 устройства подключен к тактовым входам блоков обработки 1 с (P+1)-го по L-й и к входам синхронизации регистров 3 с первого по (L-1)-й, выходы первой группы i-го блока обработки 1 подключен соответственно к первым входам элементов И 7 i-й группы, выходы первой группы j-го блока обработки 1 (j P+1,L) подключены соответственно к информационным входам первой группы (j+1)-го блока обработки и соответственно к первым входам элементов И 7 j-й группы, выходы первой группы L-го блока обработки 1 подключены соответственно к первым входам элементов И 7 L-й группы, выходы второй группы, первый, второй и третий выходы К-го блока обработки 1 (К 1, L-1) подключены соответственно к информационным входам второй группы, к первому, второму и третьему управляющим входам (К+1)-го блока обработки 1, четвертый выход Z-го блока обработки 1 (Z 1,L) подключен к информационному входу Z-го комбинационного сумматора 2 и к Z-му выходу группы 21 признака отказа устройства, выходы третьей и четвертой групп К-го блока обработки 1 подключены соответственно к информационным входам группы К-го комбинационного сумматора 2 и к первым входам элементов ИЛИ 5 К-й группы, выходы элементов И 7 групп с первой по L-ю подключены соответственно к входам элементов ИЛИ 6 L-й группы, выходы которых подключены соответственно к выходам 22 результата устройства, управляющие входы первой группы 14 которого подключены соответственно к управляющим входам первой группы первого блока обработки 1, выходы К-го комбинационного сумматора 2 подключены к информационным входам К-го регистра 3 и к входам первой группы К-го узла сравнения 4, выходы L-го комбинационного сумматора 2 подключены к входам первой группы L-го узла сравнения 4, выход Z-го узла сравнения подключен к вторым входам элементов И 7 Z-й группы и к Z-му входу элемента ИЛИ-НЕ 8, выход которого подключен к выходу 23 признака отказа устройства, управляющие входы второй группы 15 которого подключены к входам вторых групп всех узлов управления 4 и к управляющим входам вторых групп всех блоков обработки 1, информационные выходы К-го регистра 3 подключены соответственно к вторым входам элементов ИЛИ 5 К-й группы, выходы которых подключены соответственно к управляющим входам первой группы (К+1)-го блока обработки 1, Z-е входы установки первой, второй и третьей групп 17, 18 и 19 подключены соответственно к первому, второму и третьему входам установки Z-го блока обработки 1, вход блокировки 20 устройства. Каждый блок обработки 1 содержит первый и второй вычислительные узлы 24 и 25, узел сравнения 26, триггер 27, три узла элементов И 28-30, узел элементов ИЛИ 31 и элемент НЕ 32, причем информационные входы первой и второй групп 33 и 34, управляющие входы первой группы 38, первый, второй и третий управляющие входы 35-37 блока обработки 1 подключены соответственно к входам группы первого узла элементов И 28 и соответственно к входам группы второго узла элементов И 29, выходы группы первого узла элементов И 28 подключены соответственно к входам первой группы узла элементов ИЛИ 31, выходы которых подключены соответственно к выходам первой группы 48, второй группы 49, к первому 50, второму 51 и третьему 52 выходам блока обработки 1, выходы первой группы второго узла элементов И 29 подключены соответственно к информационным входам первой группы, второй группы, к первому, второму и третьему управляющим входам первого вычислительного узла 24 и соответственно к информационным входам первой группы, второй группы, к первому, второму и третьему управляющим входам второго вычислительного узла 25, выходы первой группы, второй группы, первый, второй и третий выходы первого вычислительного узла 24 подключены соответственно к входам группы третьего узла элементов И 30 и соответственно к входам первой группы узла сравнения 26, выходы первой группы, второй группы, первый, второй и третий выходы второго вычислительного узла 25 подключены соответственно к входам второй группы узла сравнения 26, выход которого подключен к информационному входу триггера 27, выход которого подключен к входам второго 29 и третьего 30 узлов элементов И, к инверсному входу первого узла элементов И и к четвертому 46 выходу блока обработки 1, выходы третьего узла элементов И 30 подключены соответственно к входам второй группы узла элементов ИЛИ 31, управляющие входы второй группы 42 блока обработки 1 подключены соответственно к управляющим входам группы первого вычислительного узла 24 и соответственно к управляющим входам группы второго вычислительного узла 25, первый вход установки 39 блока обработки 1 подключены к входам начальной установки первого 24 и второго 25 вычислительных узлов, второй и третий входы установки 43 и 44 блока обработки 1 подключены соответственно к входу установки в ноль и к входу установки в единицу триггера 27, вход 40 блокировки и тактовый вход 41 блока обработки 1 подключены соответственно к первому и второму (инверсному) входам элемента И 32, выход которого подключен к тактовым входам первого 24 и второго 25 вычислительных узлов и к входу синхронизации триггера 27, выход вторых групп первого и второго узлов элементов И 28 и 29 подключены соответственно к выходам третьей и четвертой групп 45 и 47 блока обработки 1.

Каждый вычислительный узел 24 (25) содержит комбинационный умножитель 53, комбинационный сумматор 54, с первого по четвертый регистры 55-58, группу регистров 59, с первого по шестой триггеры 60-65, с первой по (L+7)-ю группы элементов И 66-73, с первой по пятую группы элементов ИЛИ 74-78, с первого по третий элементы И 79-81, элемент НЕ 82 и дешифратор 83, при этом информационные входы первой группы 84 вычислительного узла подключены к информационным входам первого регистра 55, выходы которого подключены к первым входам элементов И 66 и 67 первой и второй групп, выходы элементов И первой группы 66 подключены к первым входам элементов ИЛИ 74 и 77 первой и второй групп, выходы элементов ИЛИ первой группы 74 подключены к информационным входам первой группы комбинационного умножителя 53, выходы которого подключены к информационным входам первой группы комбинационного сумматора 54 и первым входам элементов И 68 третьей группы, выходы которых подключены к первым входам элементов И 69 четвертой группы и первым входам элементов И 70 пятой группы, выходы которых подключены к вторым входам элементов ИЛИ 77 второй группы, выходы которых подключены к информационным входам второго регистра 58, выходы которого подключены к выходам первой группы 92 вычислительного узла, информационные входы второй группы 85 которого подключены к информационным входам третьего 56 и четвертого 57 регистров, выходы которых подключены соответственно к выходам второй группы 93 вычислительного узла и информационным входам второй группы комбинационного умножителя 53, выходы элементов И 67 второй группы подключены к первым входам элементов ИЛИ 75 третьей группы, выходы которых подключены к информационным входам второй группы комбинационного сумматора 65, выходы элементов И 68 третьей группы подключены к первым входам элементов ИЛИ 76 четвертой группы, выходы которых подключены к информационным входам первого регистра 59₁ группы, выходы S-го регистра 59 группы (S 1,L-1) подключены к информационным входам (S+1)-го регистра 59 группы и к первым входам S-го элемента И 73 группы, выходы L-го регистра 59 группы подключены к первым входам L-x элементов И 59 (L+5)-й группы, выходы элементов И 73 группы подключены к соответствующим входам элементов ИЛИ 78 четвертой группы, выходы которых подключены к первым входам элементов И 71 (L+6)-й группы и первым входам элементов И 72 (L+7)-й группы, выходы которых подключены к вторым входам элементов ИЛИ 75 третьей группы, выходы элементов И 69 четвертой группы подключены к вторым входам элементов ИЛИ 76 четвертой группы, выходы элементов И 71 (L+6)-й группы подключены соответственно к третьим входам элементов ИЛИ 76 четвертой группы и вторым входам элементов ИЛИ 74 первой группы, первый управляющий вход 86 вычислительного узла подключены к информационному входу первого триггера 60, выход которого подключен к вторым входам элементов И 66 первой группы, (L+7)-й группы 72, к первому входу первого элемента И 79, первому входу второго элемента И 81, информационному входу второго триггера 63 и входу элемента НЕ 82, выход которого подключен к вторым входам элементов И 67 второй группы, пятой группы 70 и (L+6)-й группы 71, второй управляющий вход 87 вычислительного узла подключен к информационному входу третьего триггера 61, прямой выход которого подключен к информационному входу четвертого триггера и второму входу первого элемента И 79, выход которого подключен к вторым входам элементов И 68 третьей группы, инверсный выход третьего триггера 61 подключен к второму входу второго элемента И 81, выход которого подключен к вторым входам элементов И четвертой группы 69, третий управляющий вход 88 вычислительного узла подключен к информационному входу пятого триггера 62 и к первому входу третьего элемента И 80, выход которого подключен к входу записи/считывания четвертого регистра 57, выходы второго 63, четвертого 64, пятого 65 триггеров подключены соответственно к первому 94, второму 95 выходам и к информационному входу шестого триггера 65, выход которого подключен к третьему выходу 96 вычислительного узла, управляющие входы 89 группы которого подключены к входам дешифратора 83, i-й выход которого (i 1,L) подключен к вторым входам элементов И 73 (S+5)-й группы, тактовый вход 90 вычислительного узла подключен к входам записи/считывания первого 55, второго 58 и третьего 56 регистров, регистров 59 группы, к входам синхронизации триггеров с первого по шестой и к второму входу третьего элемента И 80, вход начальной установки 91 вычислительного узла подключен к входам установки в ноль всех регистров и триггеров.

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

Конвейерное устройство для обработки информации содержит L блоков обработки 1, где L P+R, R число резервных блоков обработки, L комбинационных сумматоров 2, L-1 регистров 3, L узлов сравнения 4, L групп элементов ИЛИ 5 и 6, L групп элементов И 7, элемент ИЛИ-НЕ 8, информационные входы 9 и 10, управляющие входы 11-15, тактовый вход 16, входы установки 17-19, вход блокировки 20, группу выходов 21 признака отказа устройства, выходы результатов 22 и выход 23 признака отказа устройства. Каждый блок обработки 1 содержит вычислительные узлы 24 и 25, узел сравнения 26, триггер 27, узлы элементов И 28-30, узел элементов ИЛИ 31, элемент И 32, информационные входы 33 и 34, управляющие входы 35-39, вход блокировки 40, тактовый вход 41, входы установки 42-44, выходы 45-52. Каждый вычислительный узел 24 (25) содержит комбинационный умножитель 53, комбинационный сумматор 54, регистры 55-58, группу регистров 59, триггеры 60-65, группы элементов И 66-73, группы элементов ИЛИ 74-78, элементы И 79-81, элемент НЕ 82, дешифратор 83, информационные входы 84 и 85, управляющие входы 86-89, тактовый вход 90, вход начальной установки 91 и выходы 92-96.

В основу работы устройства для перемножения трех матриц положены следующие рекуррентные соотношения:


g(q)pj

= g(q-1)pj+c_pqd_qj,
g_pj= g(Q)pj;

h(o)ij= 0
h(p)ij= h(p-1)ij+f_ipg_pj,
h_ij= h(p)ij.
Вычислительный блок 24 (25) реализует следующие функции:
A^j+2= α^j,
B^j+2= β^j,
F^j+2= γ^j



F^j+1 f^j,
где g^j вспомогательная переменная (значение содержимого регистра 59₁ на j-м такте);
α^j,β^j,γ^j значения соответственно на первом, втором и третьем настроечных входах вычислительного модуля на j-м такте;
A^j, B^j, F^j значения соответственно на первом, втором и третьем настроечных выходах вычислительного модуля на j-м такте;
h^j, f^j значения соответственно на первом и втором информационных входах на j-м такте;
H^j, F^j значения соответственно на первом и втором информационных выходах на j-м такте.

В основу работы устройства для вычисления двумерного ДПФ положены рекуррентные соотношения перемножения трех матриц, где

C_P×Q= {C_pq} = {x_pq} ;

Вычислительный узел 24 (25) работает в шести режимах, которые задаются значениями управляющих сигналов a,β и γ, подаваемыми соответственно на входы 86, 87 и 88.

В первом режиме на входы 86, 87 и 88 подаются управляющие сигналы (α,β,γ) = (1,1,1).. При этом на входы 84 и 85 подаются соответственно элементы d и с, в регистр 55 записывается элемент d, в регистры 56 и 57 записывается элемент с (элемент И 80 открыт с помощью управляющего сигнала γ 1 и разрешена запись в регистр), элементы И 66, 68 и 79 открыты, на выходе умножителя 53 формируется значение с • d, которое через элементы И 68 и ИЛИ 76 на следующем такте записывается в регистр 59₁, элемент d с выхода регистра 55 через элементы И 66 и ИЛИ 77 подается на вход регистра 58 и далее на выход 92.

Второй режим задается управляющими сигналами (α,β,γ) = (1,1,0) на входах 86, 87 и 88. На входы 84 и 85 подаются соответственно элементы d и с'. Элементы И 66, 68 и 79 открываются, на выходе умножителя 53 формируется значение с • d (элемент с записан в регистре 57), на выход регистра 59₁ подается значение с • d через элементы И 68 и 76, на выход 92 выдается элемент d через элементы И 66 и ИЛИ 77, на выход 93 выдается элемент с'.

В третьем режиме на входы 86, 87 и 88 подаются управляющие сигналы (α,β,γ) = (1,0,1). На входы 84 и 85 подаются соответственно элементы d и с, открываются элементы И 66, 69, 72, 81 и 80, в регистры 56 и 57 записывается элемент с, в регистр 55 элемент d. На выходе умножителя 53 формируется значение с • d, на выходе сумматора 54 значение g c • d + c'd' (значение c' • d' подается на вход сумматора 54 с выхода регистра 59Λ), значение g с выхода сумматора 54 подается на вход регистра 59₁ через элементы И 69 и ИЛИ 76, элемент d подается через элементы И 66 и ИЛИ 77 на вход регистра 58.

В четвертом режиме на входы 86, 87 и 88 подаются управляющие сигналы (α,β,γ) = (1,0,0). На входы 84 и 85 подаются соответственно элементы d и с, элементы И 66, 69, 72 и 81 открываются, в регистр 55 записывается элемент d, в регистр 56 элемент с, в регистре 57 хранится элемент с". На входе умножителя 53 формируется значение c" • d, на выходе сумматора 54 значение g c" • d + c' • d' (значение с' • d' подается на вход сумматора 54 с выхода регистра 59Λ), значение g подается на вход регистра 59₁, элемент d подается через элементы И 66 и ИЛИ 77 на вход регистра 58.

Пятый режим работы задается управляющими сигналами (α,β,γ) = (0,0,1) на входах 86, 87 и 88. На входы 84 и 85 подаются соответственно элементы h и f. Элемент h записывается в регистр 55, а элемент f в регистры 56 и 57. Элементы И 67, 70, 71 открываются единичным сигналом с выхода элемента НЕ 82. На выходе умножителя 53 формируется значение f • g, где g содержимое регистра 59Λ, поступающее на второй вход умножителя 53 через элементы И 71 и ИЛИ 74, на выходе сумматора 54 значение h' h + f • g, которое подается через элементы И 70 и ИЛИ 77 на вход регистра 58.

В шестом режиме работы на входы 86, 87 и 88 подаются управляющие сигналы (α,β,γ) = (0,0,0). На входы 84 и 85 подаются соответственно элементы h и f, которые записываются соответственно в регистры 55 и 56. В регистре 57 хранится элемент f'.

Элементы И 67, 70 и 71 открываются. На входе умножителя 53 формируется значение f' • g, на выходе сумматора 54 значение h' h + f' • g, которое подается на вход регистра 58.

Во всех режимах работы управляющие сигналы α,β и γ задерживаются на два такта с помощью триггеров 59-64.

На входы 9 и 10 устройства подаются соответственно элементы d_ij (h_ij) и c_ij (f_ij) в моменты времени




где t_o= -(2+Λ),Λ = max{τ,p}..

На входы 11, 12 и 13 подаются соответственно управляющие сигналы α,β и γ в моменты времени






На выходе результата 22 устройства элементы h_ij формируются в моменты времени

Последний элемент h_Iτ формируется на (Λ(Q+I)+2p+τ-Λ)_м такте.

Период подачи элементов c_ij, d_ij, f_ij для перемножения матриц следующей задачи равен Λ•(Q+I) тактов.

Значение Λ порядка подается на вход 15 устройства, откуда оно через входы 42 блоков 1 и входы 89 вычислительных узлов поступает на дешифратор 83. В результате дешифрации значение L с выхода дешифратора 83 снимается единичный сигнал, который поступает на соответствующий вход элементов И 73_i. В результате этого с выходов регистров 59_i через элементы И 73_i и ИЛИ 78 информация поступает на соответствующие входы элементов И 71 и 72. Таким образом осуществляется настройка вычислительного узла на конкретное значение Λ≅L.

В каждом блоке обработки 1 производится дублирование выполняемых операций с помощью вычислительных узлов 24 и 25. Результаты выполнения операций, начинающиеся по заднему фронту синхросигнала, формируются на выходе 92 по завершении переходных процессов в комбинационных схемах 53 и 54. Далее информация с выходов 92-96 узлов 24 и 25 поступает соответственно на информационные входы узла сравнения 26. При совпадении информации, поступающей на информационные входы узла сравнения 26 из вычислительных узлов 24 и 25 блока 1_j, заданный блок обработки 1_j считается исправным и единица с выхода узла сравнения 26 записывается в триггер 27, который используется для фиксации признака исправности данного блока обработки 1_j. С выхода триггера 27 единица поступает на соответствующие входы узлов элементов И 29, 30. В результате этого значения α_ij(h(0)ij

), c_ij, α,β, и γ, поступающие из блока 1_j-1 через входы 33-37 блока 1_j, подаются соответственно на входы вычислительных узлов 24 и 25, значение m, поступающее из блока 1_j-1 на вход 38 блока 1_j, через узел элементов И 29 выдается на выход 45 блока 1_j. Единичный сигнал с выхода триггера 27 поступает также на инверсный вход узла элементов И 28 и блокирует обход данного блока обработки.

Единичный сигнал с выхода триггера 27 через выход 45 блока 1_j поступает также на выход 21_j признака отказа группы устройства. При несовпадении информации, поступающей на информационные входы узла сравнения 26 вычислительных узлов 24 и 25, данный блок обработки 1_j считается неисправным и первый сигнал с выхода узла сравнения записывается в триггер 27. С выхода триггера 27 нулевой сигнал информации с выходов 92-96 вычислительного узла 24 блокируется. Нулевой сигнал с выхода триггера 27 поступает также на соответствующий вход узла элементов И 29 и на инверсный вход узла элементов И 28. В результате этого поступление значений α_ij(h(0)ij

), c_ij (f_ij), α,β,γ в вычислительные узлы 24 и 25 через узел элементов И 29 блокируется и открывается путь обхода данного блока обработки 1_j. В этом случае значения α_ij(h(0)ij), c_ij (f_ij, α,β,γ, поступающие из предыдущего блока обработки 1_j-1 через узел элементов И 28 и узел элементов ИЛИ 31 выдаются соответственно на выходы 48-52 данного блока обработки. Значение m, поступающее из блока 1_j-1 на выход 39 блока 1_j, через узел элементов И 28 выдается на выход 47 блока 1_j. Нулевой сигнал с выхода триггера 27 через выход 46 блока 1_j выдается на выход 21_j признака отказа группы устройства.

Для того, чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 17 устройства. В этом случае внешними средствами управления на выходе 17_j устройства формируется сигнал, который через вход 43 блока обработки 1_j поступает на вход установки в ноль триггера 27.

Для того, чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 17_j устройства. В этом случае внешними средствами управления на входе 17_j устройства формируется сигнал, который через вход 43 блока обработки 1_j поступает на вход установки в ноль триггера 27. Для того, чтобы принудительно ввести блок обработки 1_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 18_j устройства. В этом случае внешними средствами управления на входе 18_j устройства формируется сигнал, который через вход 44 блока обработки 1_j поступает на вход установки в единицу триггера 27. При этом работа блока обработки 1_j может быть блокирована путем подачи на вход 20 устройства единичного сигнала. В этом случае единичный сигнал через вход 40 блока 1_j поступает на инверсный вход элемента И 32, который блокирует прохождение тактовых сигналов на тактовые входы вычислительных узлов 24 и 25, триггера 27.

Для установки регистров и триггеров вычислительных узлов 24 и 25 блока 1_j в исходное состояние при запусках и перезапусках устройства используется вход 19_j устройства. Для установки блока 1_j в исходное состояние на вход 19_j устройства подается единичный сигнал, который через вход 39 блока 1_j поступает на входы установки в исходное состояние вычислительных узлов 24 и 25. Вход установки в исходное состояние вычислительных узлов 24 и 25 подключен к входам установки в нулевое состояние всех регистров и триггеров узлов 24 и 25 (на фиг. 3 не показаны).

На вход 14 устройства подается нулевое значение величины m. При наличии исправных блоков 1₁,1_P с выходов 21₁, 21_P признака отказа устройства выдаются единичные сигналы, которые подаются на входы соответствующих комбинационных сумматоров 2₁,2_P. Значение m, поступающее на вход 38 блока 1_j, где j 1,n, в случае исправности блоков 1₁,1_j-1 равно j-1. В случае исправности блока 1_j данное значение m выдается на выход 45 блока 1_j и поступает на соответствующий вход комбинационного сумматора 2_j, с выхода которого снимается значение m=j,, которое записывается в регистр 3_j, и поступает на выход узла сравнения 4_j, на другой вход которого поступает значение P. Таким образом, на каждом такте в случае исправности блока 1_j с выхода комбинационного сумматора 2 выдается значение μ.

При совпадении значений m и P с выхода узла сравнения 4_j выдается единичный сигнал, который открывает элементы И 7_P (при этом все остальные элементы И 7 остаются закрытыми) и результат через элементы И 7_P и элементы ИЛИ 6 выдаются на выходы 22 устройства. В случае отказа блока 1_j происходит обход этого блока, как описано выше. При этом в случае исправности предыдущих блоков 1_I,1_j-1 на вход 38 блока 1_j поступает значение m=j-11, которое далее поступает на выход 47 блока 1_j, с выходов 45 и 46 блока 1_j снимаются нулевые значения и, таким образом, с выхода комбинационного сумматора 2_j снимается нулевое значение m. В результате этого с выхода узла сравнения 4_P снимается нулевое значение, которое закрывает элементы И 7_P. Если блок 1_P+1 исправен, то на вход 38 блока 1_P+1 поступает значение m=p-11, с выхода 46 блока 1_P+1 выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 2_P+1 снимается значение m=p. В результате этого с выхода узла сравнения 4_P+1 снимается единичный сигнал, который открывает элементы И 7_P+1 и результат через элементы И 7_P+1 и элементы ИЛИ 6 выдается на выходы результата устройства. Нулевое значение величины μ, формируемой на комбинационном сумматоре 2_j на последующих тактах, поступает на соответствующие входы элементов ИЛИ 5_j и в дальнейшем не влияет на величину mб поступающую на вход 38 блока 1_j+1.

Таким образом, блок обработки 1_j выводится из вычислительного процесса путем обхода, а первый из исправных резервных блоков, например I_P+1, вводится в процесс вычисления, при этом длина линейки исправно функционирующих блоков обработки 1 устройства сохраняется.

При обнаружении S отказов блоков 1 происходит обход отказавших блоков 1, как было описано выше. Пусть К номер последнего отказавшего блока 1 линейки, тогда с выхода 47 блока 1_K будет выдаваться значение m=p-s, которое поступит на вход 38 блока 1_K+1. Поскольку блок 1_K+1 считается исправным, то с выхода 46 блока 1_K+1 выдается единичный сигнал, с выхода комбинационного сумматора 2_K+1 будет выдано значение μ = p-s+1, которое поступит на выход 38 блока 1_K+2 и т. д. При попадании значения μ на выход 38 исправного блока 1_j, на выходе комбинационного сумматора 2_j формируется величина, равная m+1. При попадании значения μ на вход 38 неисправного блока 1_j, на выходе комбинационного сумматора 2_j формируется нулевое значение, а значение m с выхода 47 блока 1_j поступает на вход 38 следующего блока 1_j+1 линейки. С выхода комбинационного сумматора 2_P+S на вход узла сравнения 4_p+s подается значение m=p, с выхода узла сравнения 4_P+S подается единичный сигнал, который открывает элементы И 7_P+S, и результат с выхода 48 блока 1_P+S через элементы И 7_P+S и ИЛИ 6 поступает на выходы 22 результата. В данном случае на один из входов элемента ИЛИ-НЕ 8 поступает единичный сигнал, и соответственно на выходе 23 признака отказа устройства присутствует нулевой сигнал, который свидетельствует об исправности устройства. При R < S на выходах узлов 4₁,4_L будут нулевые значения, с выхода элемента ИЛИ-НЕ 8 на выход 23 признака отказа устройства будет выдано единичное значение, которое свидетельствует об исчерпании резерва и отказа устройства. Таким образом, при накоплении R отказов работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной. При обнаружении (R+1)-го отказа устройства с выхода элемента ИЛИ-НЕ 8 на выход 23 устройства выдается признак отказа устройства, который далее поступает на средства внешнего управления.

При работе устройства незаблокированные резервные блоки 1 автоматически функционируют в режиме контроля дублированием. В этом случае на входы первого блока обработки 1_r, где r ≥ P+1, находящегося в резерве, с выхода рабочей линейки устройства поступают вычислительные значения. В результате обработки этого значения в вычислительных узлах 24 и 25 и последующего сравнения результатов в узле 26 резервных блоков обработки 1_r происходит обновление значений триггеров 27 этих блоков. Дальнейшее использование этих резервов блоков обработки 1_r будет происходить с учетом их исправности.

Рассмотрим работу устройства для конкретного случая 1 P3, τ=Q=2 и R 1. Организация входного и выходного потоков данных, состояния регистров, триггеров, значения на выходах умножителя и сумматора вычислительных узлов блоков 1₁, 1₂ и 1₃ в случае их исправности приведены в табл. 1.

Рассмотрим формирование элемента h₁₁ в случае исправности блоков 1₁, 1₂ и 1₃. На первом такте в блоке 1₁ формируется значение c₁₁ • d₁₁, на втором такте значение c₁₂ • d₂₁, на четвертом такте значение g c₁₁ • d₁₁ + d₂₁ • c₁₂, на седьмом такте значение . В блоке 1₂ на девятом такте формируется значение . В блоке 1₃ на одиннадцатом такте формируется значение , которое выдается на выход 22 устройства на тринадцатом такте. Аналогичным образом формируются остальные элементы h_ij.

Устройство перемножает три (n x n) матрицы за 2 n (n + 1) тактов.

Пусть на одиннадцатом такте работы устройства обнаружен отказ блока обработки 1₂. В этом случае состояние регистров триггеров, значения на выходах комбинационных умножителей и сумматора вычислительных узлов блоков обработки 1₁, 1₂, 1₃ и 1₄ (1₄ резервный блок обработки) приведены в табл. 2. На такте t 11 обнаружен отказ блока 1₂, на такте t 12 производится обнуление блока 1₁, блокировка блока 1₂, на такте t 13 производится блокировка и обнуление блока 1₃, на такте t 14 производится перезапуск устройства, разблокирование блока 1₃. Появившийся отказ блока обработки 1₂ приводит к тому, что нулевое значение сигнала с выхода узла сравнения 26 записывается в триггер 27. С выхода триггера 27 нулевое значение сигнала поступает на входы узлов элементов И 29, 30 и на инверсные входы узлов элементов И 28. В результате этого происходит обход блока 1₂ и запрещение выдачи информации с выходов узла 24. Блокировка работы блока 1₂ осуществляется подачей единичного сигнала на вход 20₂ устройства. Обнуление блока 1₁ осуществляется с помощью подачи единичного сигнала на вход 19₁ устройства. Нулевой сигнал с выхода триггера 27 поступает на выход 21₂ устройства. Все временные диаграммы подачи значений элементов матриц и внешних управляющих сигналов формируются с помощью средств внешнего управления или аппаратурной среды. Алгоритм восстановления вычислительного процесса после обнаружения отказа блока 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+K: чтение информации с блока 1_j+K+1 в блок 1_j+K+2, блокировка и обнуление блока 1_j+K+1, разблокировка блока 1_j+K+1.

Если t_n время (число тактов), требуемое для подготовки к передопуску устройства со стороны средств внешнего управления, то время реинициализации линейки составит 2 (j+t_n) тактов.

В силу технологической структуры кристалл ИС состояния исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем большем, чем выше уровень технологии и степень интеграции ИС. Наличие не менее 16-разрядных комбинационных умножителей, сумматора и регистров обуславливает степень интеграции и уровень технологии, достаточные для проявления высокой степени корреляции отказов. При контроле дублированием вычислительных узлов необходимо, чтобы узлы и блоки обработки 1 были реализованы на разных кристаллах ИС. Аналогично, исходя из соображений корреляции отказов внутри кристалла ИС, необходимо, чтобы избыточные (резервные) блоки 1 не размещались на одних кристаллах ИС вместе с рабочими.

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

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

Для рассматриваемого систолического устройства
P_пр(t) = P2уз

(t);
P_oo (t) 2P_уз (t) (1 P_уз (t)),
где P_уз (t) вероятность безотказной работы вычислительного узла 24 (25).

Следовательно, достоверность функционирования всего устройства будет
D_ф= (2P_уз(t)-P2уз

(t))ⁿ.
При P_уз (t) 0,99, n 3 D_ф 0,996; при P_уз (t) 0,99, n 10 D_ф 0,9891; при P_уз (t) 0,999, n 3 D_ф 0,999997; при P_уз (t) 0,999, n 10 D_ф 0,999989; при P_уз (t) 0,9999 и выше D_ф практически равна 1.

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

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

1. Устройство для перемножения трех матриц и вычисления двумерного дискретного преобразования Фурье, содержащее P блоков обработки, каждый из которых включает первый вычислительный узел, причем тактовый вход устройства подключен к тактовым входам блоков обработки с первого по P-й, информационные входы первой и второй групп, первый, второй и третий управляющие входы устройства подключены соответственно к информационным входам первой и второй групп, к первому, второму и третьему управляющим входам первого блока обработки, выходы первой группы, второй группы, первый, второй и третий выходы i-го блока обработки (где i 1,P 1) подключены соответственно к информационным входам первой группы, второй группы, к первому, второму и третьему управляющим входам (i + 1)-го блока обработки, отличающееся тем, что в устройство введены с (P + 1)-го по L-й блоки обработки (где L P + R, R - число резервных блоков обработки), L комбинационных сумматоров, (L- 1)-й регистр, L узлов сравнения, L групп элементов ИЛИ, L групп элементов И и элемент ИЛИ НЕ, при этом тактовый вход устройства подключен к тактовым входам блоков обработки с (P + 1)-го по L-й и к входам синхронизации регистров с первого по (L 1)-й, выходы первой группы i-го блока обработки подключены соответственно к первым входам элементов И i-й группы, выходы первой группы j-го блока обработки (где j P + 1,L) подключены соответственно к информационным входам первой группы (j + 1)-го блока обработки и соответственно к первым входам элементов И j-й группы, выходы первой группы L-го блока обработки подключены соответственно к первым входам элементов И L-й группы, выходы второй группы, первый, второй и третий выходы k-го блока обработки (где k 1,L 1) подключены соответственно к информационным входам второй группы, к первому, второму и третьему управляющим входам (k + 1)-го блока обработки, четвертый выход Z-го блока обработки (где Z 1,L) подключен к информационному входу Z-го комбинированного сумматора и Z-му выходу группы признака отказа устройства, выходы третьей и четвертой групп k-го блока обработки подключены соответственно к информационным входам группы k-го комбинированного сумматора и первым входам элементов ИЛИ k-й группы, выходы элементов И групп с первой по L-ю подключены соответственно к входам элементов ИЛИ L-й группы, выходы которых подключены соответственно к выходам результата устройства, управляющие входы первой группы которого подключены соответственно к управляющим входам первой группы первого блока обработки, выходы k-го комбинированного сумматора подключены к информационным входам k-го регистра и к входам первой группы k-го узла сравнения, выходы L-го комбинированного сумматора подключены к входам первой группы L-го узла сравнения, выход Z-го узла сравнения подключен ко вторым входам элементов И Z-ой группы и к Z-му входу элемента ИЛИ НЕ, выход которого подключен к выходу признака отказа устройства, управляющие входы второй группы которого подключены к входам вторых групп всех узлов сравнения и к управляющим входам вторых групп всех блоков обработки, информационные выходы k-го регистра подключены соответственно ко вторым входам элементов ИЛИ k-й группы, выходы которых подключены соответственно к управляющим входам первой группы (k + 1)-го блока обработки, Z-е входы установки первой, второй и третьей групп подключены соответственно к первому, второму и третьему входам установки Z-го блока обработки, вход блокировки которого подключен к Z-му входу блокировки устройства, причем каждый блок обработки дополнительно содержит второй вычислительный узел, узел сравнения, триггер, три узла элементов И, узел элементов ИЛИ и элемент И, информационные входы первой и второй групп, управляющие входы первой группы, первый, второй и третий управляющие входы блока обработки подключены соответственно к входам группы первого узла элементов И и соответственно к входам группы второго узла элементов И, выходы группы первого узла элементов И подключены соответственно к входам первой группы узла элементов ИЛИ, выходы которых подключены соответственно к выходам первой группы, второй группы, к первому, второму и третьему выходам блока обработки, выходы первой группы второго узла элементов И подключены соответственно к информационным входам первой группы, второй группы, к первому, и третьему управляющим входам первого вычислительного узла и соответственно к информационным входам первой группы, второй группы, к первому, второму и третьему управляющим входам второго вычислительного узла, выходы первой группы, второй группы, первый, второй и третий выходы первого вычислительного узла подключены соответственно к входам группы третьего узла элементов И и соответственно к входам первой группы узла сравнения, выходы первой группы, второй группы, первый, второй и третий выходы второго вычислительного узла подключены соответственно к входам второй группы узла сравнения, выход которого подключен к информационному входу триггера, выход которого подключен к входам второго и третьего узлов элементов И, к инверсному входу первого узла элементов И и к четвертому выходу блока обработки, выходы третьего узла элементов И подключены соответственно к входам второй группы узла элементов ИЛИ, управляющие входы второй группы блока обработки подключены соответственно к управляющим входам группы первого вычислительного узла и соответственно к управляющим входам группы второго вычислительного узла, первый вход установки блока обработки подключен к входам начальной установки первого и второго вычислительных узлов, второй и третий входы установки блока обработки подключены соответственно к входу установки в нуль и к входу установки в единицу триггера, выход блокировки и тактовый вход блока обработки подключены соответственно к первому и второму (инверсному) входам элементов И, выход которого подключен к тактовым входам первого и второго вычислительных узлов и ко входу синхронизации триггера, выход вторых групп первого и второго узлов элементов И подключены соответственно к выходам третьей и четвертой групп блока обработки. 2. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит комбинационный умножитель, комбинационный сумматор, с первого по четвертый регистры, группу регистров, с первого по шестой триггеры, с первой по (L + 7)-ю группы элементов И, с первой по пятую группы элементов ИЛИ, с первого по третий элементы И, элемент НЕ и дешифратор, при этом информационные входы первой группы вычислительного узла подключены к информационным входам первого регистра, выходы которого подключены к первым входам элементов И первой и второй групп, выходы элементов И первой группы подключены к первым входам элементов ИЛИ первой и второй групп, выходы элементов ИЛИ первой группы подключены к информационным входам первой группы комбинационного умножителя, выходы которого подключены к информационным входам первой группы комбинационного сумматора и к первым входам элементов И третьей группы, выходы которых подключены к первым входам элементов И четвертой группы и элементов И пятой группы, выходы которых подключены к вторым входам элементов ИЛИ второй групп, выходы которых подключены к информационным входам второго регистра, выходы которого подключены к выходам первой группы вычислительного узла, информационные входы второй группы которого подключены к информационным входам третьего и четвертого регистров, выходы которых подключены соответственно к выходам второй группы вычислительного узла и к информационным входам второй группы комбинационного умножителя, выходы элементов И второй группы подключены к первым входам элементов ИЛИ третьей группы, выходы которых подключены к информационным входам второй группы комбинационного сумматора, выходы элементов И третьей группы подключены к первым входам элементов ИЛИ четвертой группы, выходы которых подключены к информационным входам первого регистра группы, выходы S-го регистра группы (где S 1,L 1) подключены к информационным входам (S + 1)-го регистра группы и первым входам элементов И (L + 5)-й группы, выходы L-го регистра группы подключены к первым входам элементов И (L + 5)-й группы, выходы элементов И (S + 5)-й группы подключены к соответствующим входам элементов ИЛИ четвертой группы, выходы которых подключены к первым входам элементов И (L + 6)-й группы и соответственно к первым входам элементов И (L + 7)-й группы, выходы которых подключены к вторым входам элементов ИЛИ третьей группы, выходы элементов И четвертой группы подключены к вторым входам элементов ИЛИ четвертой группы, выходы элементов И (L + 6)-й группы подключены соответственно к третьим входам элементов ИЛИ четвертой группы и вторым входам элементов ИЛИ первой группы, первый управляющий вход вычислительного узла подключен к информационному входу первого триггера, выход которого подключен к вторым входам элементов И первой группы, (L + 7)-й группы, к первому входу первого элемента И, к первому входу второго элемента И, информационному входу второго триггера и входу элементов НЕ, выход которого подключен к вторым входам элементов И второй группы, пятой группы и (L + 6)-й группы, второй управляющий вход вычислительного узла подключен к информационному входу третьего триггера, прямой выход которого подключен к информационному входу четвертого триггера и второму входу первого элемента И, выход которого подключен к вторым входам элементов И третьей группы, инверсный выход третьего триггера подключен к второму входу второго элемента И, выход которого подключен к вторым входам элементов И четвертой группы, третий управляющий вход вычислительного узла подключен к информационному входу пятого триггера и первому входу третьего элемента И, выход которого подключен к входу записи/считывания четвертого регистра, выходы второго, четвертого и пятого триггеров подключены соответственно к первому и второму выходам вычислительного узла и к информационному входу шестого триггера, выход которого подключен к третьему выходу вычислительного узла, управляющие входы группы которого подключены к входам дешифратора, i-й выход которого (где i 1,L) подключен к вторым входам элементов И (S + 5)-й группы, тактовый вход вычислительного узла подключен к входам записи/ считывания первого, второго и третьего регистров, регистров группы, к входам синхронизации триггеров с первого по шестой и к второму входу третьего элемента И, вход начальной установки вычислительного узла подключен к входам установки в нуль всех регистров и триггеров.