Устройство для решения систем линейных алгебраических уравнений

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах для решения систем линейных алгебраических уравнений /СЛАУ/. Цель изобретения - повышение надежности за счет организации контроля и резервирования и расширение функциональных возможностей за счет решения задач различных размерностей. Поставленная цель достигается тем, что конвейерное устройство для обработки информации содержит L n + R блоков обработки, где n размерность СЛАУ, R число резервных блоков обработки, L комбинационных сумматоров, L 1 регистров 3, L узлов сравнения, L групп элементов ИЛИ и группу элементов ИЛИ, L групп элементов И и элемент ИЛИ НЕ. 1 з. п. ф-лы, 3 ил. 8 табл.

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

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

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

Поставленная цель достигается тем, что в устройство, содержащее n блоков обработки 1₁.1_n, где n размерность решаемой задачи, причем вход синхронизации устройства подключен к входам синхронизации блоков обработки с первого по n-й, первый и второй управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого блока обработки 1₁, первый и второй выходы i-го блока обработки подключены соответственно к первому и второму управляющим входам (i+1)-го блока обработки (где i 1.n), входы коэффициентов устройства подключены соответственно к информационным входам первого блока обработки 1₁, выходы первой группы i-го блока обработки 1_i подключены соответственно к информационным входам (i+1)-го блока обработки 1_i+1, введены с (n+1)-го по L-й блоки обработки, где L n + R, R число резервных блоков обработки, L комбинационных сумматоров 2, L-1 регистров 3, L узлов сравнения 4, L групп элементов ИЛИ 5 и группа элементов ИЛИ 6, L групп элементов И 7 и элемент ИЛИ-НЕ 8, причем выходы первой группы i-го блока обработки подключены соответственно к первым входам элементов И 7i-й группы, выходы первой группы j-го блока обработки (где j=1.L-1) подключены к первым входам элементов И 7-й группы и к информационным входам (J+1)-го блока обработки, выходы первой группы L-го блока обработки подключены к первым входам элементов И 7 L-й группы, первый и второй выходы j-го блока обработки подключены соответственно к первому и второму управляющим входам (J+1)-го блока обработки, третий выход k-го блока обработки (где K1.L) подключен к K-му выходу 19_k группы признака отказа устройства и к информационному входу k-го комбинационного сумматора 2k, выход g-го комбинационного сумматора (где g=1, L-1) подключен к информационному входу g-го регистра 3 и к первому входу g-го узла сравнения 4, выход L-го комбинационного сумматора 2 подключен к первому входу L-го узла сравнения 4, выход j-го узла сравнения подключен к k-му входу элемента ИЛИ-НЕ 8 и к вторым входам элементов И 7 k-й группы, выходы g-го регистра подключены к первым входам элементов ИЛИ 5 g-й группы, выходы которых подключены к управляющим входам группы (g+1)-го блока обработки, выходы второй группы g-го блока обработки подключены к вторым входам элементов ИЛИ g-й группы, управляющие входы 12 группы устройства подключены к управляющим входам группы первого блока обработки, выходы третьей группы k-го блока обработки подключены к информационным входам группы k-го комбинационного сумматора 2, вход 13 порядка решаемой задачи устройства подключен к вторым входам всех узлов сравнения 4 и к третьим управляющим входам всех блоков обработки, вход 18 тактовых импульсов устройства подключен к входам синхронизации блоков обработки 1 с n-го по L-й и входам записи/считывания всех регистров 3, выходы элементов И 7 групп с первой по L-ю подключены к соответствующим входам элементов ИЛИ 6 группы, выходы которых подключены к выходам 20 результата устройства, выход 21 признака отказа которого подключен к выходу элемента ИЛИ-НЕ 8, k-й вход установки первой группы 14, k-й вход установки второй группы 15, k-й вход установки третьей группы и k-й вход блокировки 17 устройства подключены соответственно к первому, второй, третьему входам установки и к воду блокировки k-го блока обработки 1.

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

Каждый вычислительный узел 22(23) содержит три регистра 48-49, группу регистров 50, два сдвигающих регистра 51 и 52, два триггера 53 и 54, дешифратор 55, умножитель 56, сумматор 57, узел 58 вычисления обратной величины числа, группы элементов И 59-70, группы элементов ИЛИ 71-75, элементы И 78-82 и два элемента ИЛИ 76 и 77, при этом в каждом вычислительном узле 22 (23) информационные входы 83 подключены к первым входам элементов И первой 60 и второй 61 групп, выходы которых подключены соответственно к первым входам элементов ИЛИ 71 первой группы и к информационным входам первого регистра 48, выходы которого подключены к первым входам элементов И 62 третьей группы и к информационным входам первой группы вычитателя 57, выходы которого подключены к первым входам элементов И 65 четвертой группы, выходы которых подключены к первым входам элементов ИЛИ 72 второй группы, выходы которых подключены к выходам группы 89 вычислительного узла, выходы элементов ИЛИ 71 первой группы подключены к информационным входам второго регистра 47, выходы которого подключены к информационным входам первого регистра 50 группы, к первым входам элементов И 66 пятой группы и к информационным входам узла 58 вычисления обратной величины числа, выходы которого подключены к первым входам элементов И 64 шестой группы, выходы которых подключены к первым входам элементов ИЛИ 74 группы, выходы которых подключены к информационным входам первой группы умножителя 56, выходы которого подключены к информационным входам второй группы вычитателя 57 и к информационным входам третьего регистра 49, выходы которого подключены к первым входам элементов И 64 седьмой группы и первым входам элементов И 67 восьмой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ 73 четвертой группы и вторым входам элементов ИЛИ 72 второй группы, выходы элементов И 62 третьей группы подключены к вторым входам элементов ИЛИ 73 четвертой группы, выходы которых подключены к информационным входам второй группы умножителя 56, первый управляющий вход 84 вычислительного узла подключен к информационному входу первого триггера 53, ко вторым (инверсным) входам элементов И 61 второй группы и к первому входу первого элемента И 78, выход которого подключен ко вторым входам элементов И 60 первой группы и к первым (инверсным) входам элементов И 59 девятой группы, выходы которых подключены к вторым входам элементов ИЛИ 71 первой группы, инверсный выход первого триггера 53 подключен к первым входам второго и третьего элементов И 80 и 82, выход второго элемента И 80 подключен к вторым входам элементов И 63 седьмой группы, элементов И 65 четвертой группы и элементов И 66 пятой группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 74 третьей группы, выход третьего элемента И 82 подключен к вторым входам элементов И 67 восьмой группы, прямой выход первого триггера 53 подключен к информационному входу первого сдвигающего регистра 51 и к первому входу четвертого элемента И 81, выход которого подключен ко вторым входам элементов И 62 и 64 третьей и шестой групп и к первому входу пятого элемента И 79, выход которого подключен ко входу записи-считывания третьего регистра 49, второй управляющий вход 85 вычислительного узла подключен к второму входу первого элемента И 78 и к информационному входу второго триггера 54, прямой выход которого подключен к второму входу третьего элемента И 82 и к информационному входу второго сдвигающего регистра 52, инверсный выход второго триггера 54 подключен к вторым входам второго и четвертого элементов И 80 и 81, выходы разрядов с первого по L-й первого сдвигающего регистра 51 подключены соответственно к первым входам элементов И 70₁.70_L, выходы которых подключены к входам первого элемента ИЛИ 77, выход которого подключен к первому выходу 91 вычислительного узла, выходы разрядов с первого по L-й второго сдвигающего регистра 52 подключены соответственно к первым входам элементов И 69₁.69_L, выходы которых подключены к входам второго элемента ИЛИ 76, выход которого подключен к второму выходу 90 вычислительного узла, выходы i-х регистров 50_i группы подключены соответственно к первым входам элементов И 68_i, выходы которых подключены соответственно к i-м входам элементов ИЛИ 75 пятой группы, выходы которых подключены к вторым входам элементов И 59 девятой группы, третий управляющий вход 86 подключен к входу дешифратора 55, i-й вход которого подключен к вторым входам i-го элемента И 69, i-го элемента И 70 и i-х элементов И 68 группы, вход начальной установки 88 вычислительного узла подключен к входам установки в "нуль" всех регистров и триггеров, тактовый вход 87 вычислительного узла подключен к входам записи/считывания первого 47 и второго 48 регистров, ко входам синхронизации первого 53 и второго 54 регистров, к входам синхронизации сдвигающего регистра 51 и к второму входу пятого элемента И 79.

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

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

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

Каждый вычислительный узел 22(23) содержит регистры 47-49, группу регистров 50, сдвигающие регистры 51 и 52, триггеры 53 и 54, дешифратор 55, умножитель 56, вычитатель 57, узел 58 вычисления обратной величины числа, группы элементов И 59-70, группы элементов ИЛИ 71-77, элементы И 78-82, информационные входы 83, управляющие входы 84-86, тактовый вход 87, вход 88 установки в исходное состояние, выходы 89-91.

В основу работы устройства для решения системы линейных алгебраических уравнений (СЛАУ) вида A₁X A₂, где A₁=a_ij} A₂=a_i,n+k} Xx_ik} ij , k n порядок системы, m число столбцов в правой части, положен метод Гаусса-Жордана, который представляется следующими рекуррентными соотношениями: a^(o_ij⁾= a_ij, i , j ; k а_кк^(к) а_кк^(к-1); a^(k_kj⁾= a^(k_kj^-1)/a_kk j ; a^(k_ik⁾= a^(k_ik^-1), i ; a^(k_ij⁾= a^(k_ij^-1)-a^(k_ij⁾·a^(k_kj⁾, i , j a^(k)_n+k,j= a^(k_kj⁾, j
x_ij= a⁽ⁿ⁾_n+i,n+j, i , j
При описании работы устройства в обозначении а индекс k в скобках указывает номер рекуррентного шага, а в обозначении а^t индекс t без скобок номер такта работы устройства.

Вычислительный узел 22(23) обладает возможностью реализации следующих функций:
Т₁ⁱ⁺ⁿ⁺³ τ₁ⁱ;
T₂ⁱ⁺ⁿ⁺³ τ₂ⁱ, где τ₁ⁱ и τ₂ⁱ значения соответственно на первом и втором управляющих входам вычислительного узла на i-м такте,
Т₁ⁱ и Т₂ⁱ значения соответственно на первом и втором управляющих выходах вычислительного узла на i-м такте,
Aⁱ⁺¹= где eⁱ xⁱ ˙ yⁱ
xⁱ=
yⁱ=
b^i-1=
cⁱ e^i-1, если τ₁^i-1 1 и τ₂^i-1 где аⁱ значение на информационном входе вычислительного узла на i-м такте, Аⁱ значение на информационном выходе вычислительного узла на i-м такте.

Логика работы вычислительного 22(23) приведена в табл.1. Вычислительный узел 22(23) работает в четырех режимах. В первом режиме на входы 84 и 85 подаются единичные сигналы (τ₁ 1, τ₂ 1), которые записываются соответственно в триггеры 53 и 54. Кроме того, эти сигналы подаются на входы элемента И 78, на выходе которого формируется единичный сигнал, который открывает элементы И 60. Значение элемента а_i, подаваемое на входы 83 вычислительного узла через элементы И 60 и элементы ИЛИ 71, записывается в регистр 47. Содержимое регистра 47 (значение элемента а_i-1) записывается в регистр 50₁, а содержимое регистров 50_i (i 1, L 1) переписывается в разряды 50_i+1.

Во втором режиме работы на входы 84 и 85 подаются соответственно единичный и нулевой сигналы (τ₁ 1, τ₂ 0), которые записываются соответственно в триггеры 53 и 54. На выходе элемента И 81 формируется единичный сигнал, на инверсные входы элементов И 59 и 61 поступают нулевые сигналы, в результате этого элементы И 61, 62, 59 и 64 и 79 открываются. При этом значение элемента в, поступающее на входы 83 вычислительного узла, записывается в регистр 48, в регистрах 50 происходит сдвиг (циклическая перезапись значений элементов a_i). На выходе умножителя 56 формируется значение с b, которое поступает на информационный вход регистра 49 и записывается в него на следующем такте.

В третьем режиме работы на входы 84 и 85 подаются нулевые сигналы (τ₁ 0, τ₂ 0), которые записываются соответственно в триггеры 53 и 54. На выходе элемента И 80 формируется единичный сигнал, на инверсные входы элементов И 59 и 61 поступают нулевые сигналы, в результате этого элементы И 59, 61, 63, 65 и 66 открываются. При этом в регистрах 50_iпроисходит сдвиг информации, в регистр 48 записывается значение элемента d, поступающее на вход 83 вычислительного узла, в регистре 49 хранится значение элемента С. На выходе умножителя 56 формируется значение е с (содержимое регистра 47), на выходе вычислителя 57 значение f b-e, которое через элементы И 65 и ИЛИ 72 поступает на выходе 89 вычислительного узла.

В четвертом режиме на входы 84 и 85 подаются соответственно нулевой и единичный сигналы (τ₁ 0, τ₂ 1),которые записываются соответственно в триггеры 53 и 54. На выходе элемента И 82 формируется единичный сигнал, на инверсный вход элементов И 59 группы поступает нулевой сигнал, в результате этого элементы И 59 и 67 открываются. При этом в регистрах 50 происходит сдвиг информации, содержимое регистра 49 через элементы И 67 и ИЛИ 72 выдается на выход 89 вычислительного угла. Управляющие сигналы, подаваемые соответственно на входы 84 и 85, задерживаются соответственно на триггере 53, сдвигающем регистре 51 и на триггере 54, сдвигающем регистре 52 на L + 3 такта и выдаются соответственно на выходы 91 и 90.

Организация входного потока значений элементов а_ij, управляющих сигналов τ₁,τ₂ и выходного потока значений х_ij задается следующими выражениями. Значения а_ij подаются на выход 9 в моменты времени t i + (n+1)j n-2, значения x_ij снимаются выхода 20 в моменты времени t i + (n+1)j+ n²+ 2n-2, управляющие сигналы τ₁ и τ₂подаются на входы 10 и 11 в моменты времени (1,1)^о, (1,1)¹, (1,1)ⁿ, (1,0)ⁿ⁺¹, (0,0)ⁿ⁺², (0,0)^2n, (0,1)2ⁿ⁺¹, (1,0)^{n+1 (n+m-1)}, (0,0)^{(n+1)(n+m-1)+1}, (0,0)^{(n+1)(n-m-1)+n-1}, (0,1)^{(n+1)(n+m-1)+n}.

В каждом боке обработки 1 производится дублирование вычислительных операций с помощью вычислительных узлов 26 и 27. Результаты выполнения операций, начинающихся по заднему фронту синхросигнала, формируются на выходе умножителя 56 и/или вычитателя 57, в зависимости от режима работы узла 26(27) по завершению переходных процессов в комбинационных схемах 58 и 56 или 58, 56 и 57 в зависимости от режима узла 26(27) и выдаются на выходы 89 вычислительных узлов 26(27), с которых эти результаты поступают соответственно на информационные входы узла сравнения 24. При совпадении информации, поступающей на информационные входы узла сравнения 24 из вычислительных узлов 26 и 27, данный блок обработки 1_j считается исправным и единица с выхода узла сравнения 24 записывается в триггер 26, который используется для фиксации признака исправности данного блока обработки 1_j. С прямого выхода триггера 25 единица поступает на соответствующие входы элементов И 27 и информация с выходов 89-91 вычислительного узла через элементы ИЛИ 28 поступает на выходы 44-46 блока обработки 1_j. Единичный сигнал с прямого выхода триггера 25 поступает также на инверсный вход элемента И 26 и блокирует обход данного блока обработки 1_j. В результате этого значение g, поступающее на вход 34 блока 1_j, выдается на выход 41 блока 1_j. Единичное значение выдается также на выход 42 блока 1_j и соответственно, на выход 19_jпризнака отказа устройства. Единичный сигнал на выходе 19_j устройства указывает средствам внешнего управления об исправности блока 1_j. При несовпадении информации, поступающей на информационные входы узла сравнения 24 из вычислительных узлов 26 и 27, данный блок обработки 1_j считается неисправным, и нулевой сигнал с выхода узла сравнения 24 записывается в триггер 25. С выхода триггера 25 нулевой сигнал поступает на соответствующие входы элементов И 27 и выдача информации с выходов 89-91 вычислительного узла 22 блокируется. Нулевой сигнал с выхода триггера 25 поступает также на соответствующие входы элементов И 28 и на инверсные входы элементов И 26. В результате этого поступающие значения итерации переменной и значения сигналов τ₁ и τ₂ в вычислительные модули 26 и 27 через элементы 27 блокируется и открывается путь обхода блока обработки 1_j-1. В этом случае значения итерации переменной и сигналов τ₁ и τ₂, поступающие из предыдущего блока обработки 1_j-1 через элементы И 26 и ИЛИ 29, выдаются соответственно на выходы 44-46 данного блока обработки 1_j. Значения g, поступающее на вход 34 блока 1_j, выдается на выход 43 блока 1_j. Нулевое значение выдается также на выход 42 блока 1_j и соответственно на выход 19_j признака отказа устройства. Нулевой сигнал на выходе 19_j устройства указывает средствам внешнего управления об обнаружении отказа блока 1_j.

Для того чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 15 устройства. В этом случае внешними средствами управления на входе 15 устройства формируется единичный сигнал, который через вход 37 блока обработки 1_j поступает на вход установки в "нуль" триггера 25. Для того чтобы принудительно ввести блок обработки 1_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 16_j устройства. В этом случае внешними средствами управления на входе 16_j устройства формируется сигнал, который через вход 38 блока обработки 1_j поступает на вход установки в "единицу" триггера 25. При этом работа блока обработки 1_j может быть блокирована путем подачи на вход 17_j устройства единичного сигнала. В этом случае единичный сигнал через вход 39 блока 1_j поступает на инверсный вход элемента И 30, который блокирует прохождение синхросигналов на входы синхронизации вычислительных узлов 22 и 23 и триггера 25.

Для установки регистров и триггеров вычислительных узлов 22 и 213 блока 1_j в исходное состояние при запусках и перезапусках устройства используется вход 13_j устройства. Для установки блока 1_j в исходное состояние на вход 13_j устройства подается единичный сигнал, который через вход 35 блока 1_j поступает на входы установки в исходное состояние вычислительных узлов 22 и 23. Вход установки в исходное состояние вычислительных узлов 22 и 23 подключен ко входам установки в нулевое состояние всех регистров и триггеров узлов 22 и 23 (на фиг.3 не показаны).

На вход 12 устройства подается нулевое значение величины g. При наличии исправных блоков 1₁.1_n с выходов 19₁.19_n признака отказа устройства выдаются единичные значения, которые поступают на входы соответствующих комбинационных сумматоров 2₁.2_n. Значение g, поступающее на вход 34 блока 1_i, где i 1. n, в случае исправности блоков 1₁.1_i-1, равно i-1. В случае исправности блока 1_i данное значение g выдается на вход 41 блока 1_i и поступает на соответствующий вход комбинационного сумматора 2_i, с выхода которого снимается значение g= 1, которое записывается в регистр 3_i и поступает на вход узла сравнения 4_i, на другой вход которого поступает значение n. Таким образом, на каждом такте в случае исправности блока 1_i, с выхода комбинационного сумматора 2_i выдается значение g=1. При совпадении значений g и n с выхода узла сравнения 4i выдается единичный сигнал, который открывает элементы И 7_n (при этом все остальные элементы И 7 в данном случае остаются закрытыми), и результат через элементы И 7_n и элементы ИЛИ 6 выдается на выход 20 результата устройства. В случае отказа блока 1_j происходит обход этого блока, как описано выше. При этом в случае исправности предыдущих блоков 1₁.1_j-1, на вход 34 блока 1_jпоступает значение g j-1, которое далее поступает на выход 43 блока 1_j, с выходов 41 и 42 блока 1 снимаются нулевые значения и, таким образом, с выхода комбинационного сумматора 2_j снимается нулевое значение g. В результате этого с выхода узла сравнения 4_n снимается нулевое значение, которое закрывает элементы И 7_n. Если блок 1_n+1исправен, то на вход 34 блока 1_n+1 поступает значение g n-1, с выхода 42 блока 1_n+1 выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 2_n+1 снимается значение g n. В результате этого с выхода узла сравнения 4_n+1 снимается единичный сигнал, который открывает элемент И 7_n+1 и результат через элементы И 7_n+1 и элементы ИЛИ 6 выдается на выходы результата 20 устройства. Нулевое значение величины g, формируемое на комбинационном сумматоре 2_i на последующих тактах, поступает на соответствующие входы элементов ИЛИ 5_j и в дальнейшем не влияет на формируемую величину g, поступающую на вход 34 блока 1_j+1. Таким образом, блок обработки 1_j выводится из вычислительного процесса путем обхода, а первый из исправных резервных блоков, например 1_n+1, вводится в процесс вычисления, при этом длина линейки исправно функционирующих блоков обработки 1 устройства сохраняется. При обнаружении S отказов блоков 1 происходит обход отказавших блоков 1, как было описано выше. Пусть k номер последнего отказавшего блока 1 линейки, тогда с выхода 43 блока 1_k будет выдаваться значение g n-s, которое поступит на вход 34 блока 1_k+1. Поскольку блок 1_k+1 считается исправным, то с выхода 42 блока 1_k+1 выдается единичный сигнал, с выхода комбинационного сумматора 2_k+1 будет выдано значение gn-S+1, которое поступит на вход 34 блока 1_k+2, и т.д. При попадании значения g на вход 34 исправного блока 1_i на выходе комбинационного сумматора 2_iформируется величина, равная g+1. При попадании значения g на вход 34 неисправного блока 1_i на выходе комбинационного сумматора 2_i формируется нулевое значение, а значение g с выхода 43 блока 1_i поступает на вход 34 следующего блока 1_i+1 линейки. С выхода комбинационного сумматора 2_n+sна вход узла сравнения 4_n+s подается значение g=n, с выхода узла сравнения 4_n+s выдается единичный сигнал, который открывает элементы И 7_n+s, и результат с выхода 44 блока 1_n+s через элементы И 7_n+s и ИЛИ 6 поступает на выходы 20 результата. В данном случае на один из входов элемента ИЛИ-НЕ 8 поступает единичный сигнал и, соответственно, на выходе 21 признака отказа устройства поступает нулевой сигнал, который свидетельствует об исправности устройства. При R < S на выходах узлов 4₁,4_L будут нулевые значения, с выхода элемента ИЛИ-НЕ 8 на выход 21 признака отказа устройства будет выдано единичное значение, которое свидетельствует об исчерпании резерва и отказе устройства. Таким образом, при накоплении отказов работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной. При обнаружении (R+1)-го отказа устройства с выхода 21 устройства выдается признак отказа устройства, который далее поступает на средства внешнего управления. При работе устройства незаблокированные резервные блоки 1 автоматически функционируют в режиме контроля дублирования. В этом случае на входы первого блока обработки 1_р, где p ≥ n + 1, находящегося в резерве, с выхода рабочей линейки устройства поступает вычислительное значение итерации.

В результате обработки этого значения в вычислительных узлах 22 и 23 и последующего сравнения результатов в узле 24 резервных блоков обработки 1_р происходит обновление значений триггеров 25 этих блоков. Дальнейшее использование этих резервных блоков обработки 1_р будет происходить с учетом их исправности.

Значение размерности СЛАУ, используемое для решения СЛАУ различной размерности на данном устройстве, подается на вход 13 устройства и далее через входы 35 блоков 1 и входы 86 узлов 22 и 23 на входы дешифраторов 55. С n-го выхода дешифратора 55 единичное значение поступает на соответствующие входы элементов И 68_n, 6₉n и 70_n, а информация с выхода регистра 50_n группы через элементы И 68_n и ИЛИ 75_nпоступает на входы элементов И 59, информация с выхода разряда 52_n+2 сдвигающего регистра 52 через элементы И 69n и ИЛИ 76 выдается на выход 90 (τ₁), узла, информация с выхода разряда 51_n+2 сдвигающего регистра 51 через элементы И 70_n и ИЛИ 77 выдается на выход 91 (τ₂) узла. Таким образом, в устройстве реализуются возможности решения СЛАУ различного порядка n ≅ L.

Рассмотрим работу устройства для конкретного случая: n3, m 2, R 1. Пусть в процессе работы не обнаружено отказов блоков обработки, тогда значения элементов а_ij подаются на вход 9 в моменты времени.

t_aij i + 4j 5.

Значения элементов а_ij, подаваемые с единичными управляющими сигналами τ₁ и τ₂ записываются в соответствующие разряды сдвигающих регистров 51 и 52 вычислительных узлов. При подаче значений элементов а_ij с управляющими сигналами (τ₁ 1, τ₂ 0), (τ₁ 0, τ₂ 0) и (τ₁ 1, τ₂ 1) в вычислительных узлах осуществляется вычислительный процесс в соответствии с приведенными выше рекуррентными соотношениями.

Организация входного и выходного потоков данных, управляющих сигналов, содержимое триггеров, регистров, формируемые значения на выходах умножителя, вычитателя и блоков обработки для n=3, m=2 приведены в табл.2-4. На выходе 20 устройства выдаются значения элементов a₄₄⁽³⁾ x₁₁, a₅₄⁽³⁾ x₂₁, a₆₄⁽³⁾ x₃₁, a₄₅⁽³⁾ a₁₂, a₅⁵⁽³⁾ x₂₂, a₆₅⁽³⁾ x₃₂ соответственно на 17-м, 18-м, 19-м, 21-м, 22-м и 23-м тактах. Время вычисления последнего значения х_nm равно n² + + nm + 3n + m 2 тактов.

Пусть на 14-м такте работы устройства обнаружен отказ блока обработки 12. В этом случае организация входного и выходного потоков данных, управляющих сигналов, содержимое триггеров, регистров, формируемые значения на выходах умножителя, вычитателя и блоков обработки 1₁, 1₂, 1₃, 1₄ (где 1₄ резервный блок обработки) приведены в табл.5-8.

На такте t 14 обнаружен отказ блока 1₂, на такте t 15 приведено обнуление блока 1₁, блокировка блока 1₂ (в дальнейшем информация, находящаяся в его узлах, не влияет на дальнейший процесс обработки), блокировка и обнуление блока 1₃. На такте t 16 произведен перезапуск устройства (на входы блока 1₁ начата подача соответствующих значений), произведена разблокировка 1₃, с такта t 15 производится обход блока 1₂ и включение в работу резервного блока 1₄ путем коммутации выходов блока 1₄ и выходов 20 устройства. Длина линейки устройства остается прежней.

Алгоритм восстановления вычислительного процесса после обнаружения отказа блока 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_о-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-I.

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

Пусть на такте t 14 появившийся отказ блока обработки 1 привел к тому, что нулевое значение сигнала с выхода узла сравнения 24 записалось в триггере 25. С выхода триггера 25 нулевое значение сигнала поступает на входы элементов И 27 и 28, на инверсные входы элементов И 26. В результате этого происходит обход блока 1₂. Блокировка 1₂ осуществляется подачей единичного сигнала на вход 17₂ устройства. Обнуление блока осуществляется с помощью подачи единичного сигнала на вход 15₁устройства. Все временные диаграммы подачи значений входных элементов матриц и управляющих сигналов формируются с помощью средств внешнего управления или аппаратурной среды. В силу технологической структуры кристалла ИС состояние исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем больше, чем выше уровень и степень интеграции.

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

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

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

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

Следовательно, достоверность функционирования всего устройства будет
D_ф (2Р_уз(t) Р_уз²(t))n.

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

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

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

1. УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее n блоков обработки, каждый из которых включает первый вычислительный узел, где n размерность решаемой задачи, причем вход синхронизации устройства подключен к входам синхронизации блоков обработки с первого по n-й, первый и второй управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого блока обработки, первый и второй выходы i-го блока обработки подключены соответственно к первому и второму управляющим входам (i + 1)-го блока обработки (где i 1, n), входы коэффициентов устройства подключены к информационным входам первого блока обработки, выходы первой группы i-го блока обработки подключены к информационным входам (i + 1)-го блока обработки, отличающееся тем, что в него введены с (n + 1)-го по L-й блоки обработки, где L n + R, R число резервных блоков обработки, L комбинационных сумматоров, L 1 регистров, L узлов сравнения, L групп элементов ИЛИ, L групп элементов И и элемент ИЛИ-НЕ, причем выходы первой группы i-го блока обработки подключены к первым входам элементов И i-й группы, выходы первой группы j-го блока обработки (где j n, L 1) подключены к первым входам элементов И j-й группы и информационным входам (j + 1)-го блока обработки, выходы первой группы L-го блока обработки подключены к первым входам элементов И L-й группы, первый и второй выходы j-го блока обработки подключены соответственно к первому и второму управляющим входам (j + 1)-го блока обработки, третий выход K-го блока обработки (где K 1, L) подключен к K-му выходу группы признака отказа устройства и информационному входу K-го комбинационного сумматора, выход g-го комбинационного сумматора (где g 1, L 1) подключен к информационному входу g-го регистра и первому входу g-го узла сравнения, выход L-го комбинационного сумматора подключен к первому входу L-го узла сравнения, выход K-го узла сравнения подключен к K-му входу элемента ИЛИ-НЕ и вторым входам элементов И K-й группы, выходы g-го регистра подключены к первым входам элементов ИЛИ g-й группы, выходы которых подключены к управляющим входам группы (g + 1)-го блока обработки, выходы второй группы g-го блока обработки подключены к вторым входам элементов ИЛИ g-й группы, управляющие входы группы устройства подключены к управляющим входам группы первого блока обработки, выходы третьей группы K-го блока обработки подключены соответственно к информационным входам группы K-го комбинационного сумматора, вход порядка решаемой задачи устройства подключен к вторым входам всех узлов сравнения и третьим управляющим входам всех блоков обработки, вход тактовых импульсов устройства подключен к входам синхронизации блоков обработки с n-го по L-й и входам записи-считывания всех регистров, выходы элементов И групп с первой по L-ю подключены к соответствующим входам элементов ИЛИ L-й группы, выходы которых подключены к выходам результата устройства, выход признака отказа которого подключен к выходу элемента ИЛИ-НЕ, K-й вход установки первой группы, K-й вход установки второй группы, K-й вход установки третьей группы и K-й вход блокировки устройства подключены соответственно к первому, второму, третьему входам установки и входу блокировки K-го блока обработки, причем каждый блок обработки содержит дополнительно второй вычислительный узел, узел сравнения, триггер, три узла элементов И, узел элементов ИЛИ и элемент И, причем в каждом блоке обработки информационные входы, управляющие входы группы, первый и второй управляющие входы блока обработки подключены к соответствующим входам группы первого узла элементов И и входам группы второго узла элементов И, выходы первой группы первого узла элементов И подключены к входам первой группы узла элементов ИЛИ, выходы которых подключены к выходам первой группы, первому и второму выходам блока обработки, первый вход установки которого подключен к входу начальной установки вычислительных узлов, второй и третий входы установки блока обработки подключены соответственно к входу установки в "0" и входу установки в "1" триггера, тактовый вход синхронизации и вход блокировки блока обработки подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к тактовым входам первого и второго вычислительных узлов и триггера, выход которого подключен к инверсному входу первого узла элементов И, входам второго и третьего узлов элементов И и третьему выходу блока обработки, выходы первой группы второго узла элементов И подключены соответственно к информационным входам, первому и второму управляющим входам первого вычислительного узла и соответственно к информационным входам, первому и второму управляющим входам второго вычислительного узла, выходы группы, первый и второй выходы первого вычислительного узла подключены соответственно к информационным входам первой группы узла сравнения и соответственно к входам группы третьего узла элементов И, выходы которого подключены к входам второй группы узла элементов ИЛИ, выходы группы, первый и второй выходы второго вычислительного узла подключены к информационным входам второй группы узла сравнения, выход которого подключен к информационному входу триггера, третий управляющий вход блока обработки подключен к третьим управляющим входам первого и второго вычислительных узлов, выходы вторых групп первого и второго узлов элементов И подключены соответственно к выходам второй и третьей групп блока.

2. Устройство по п. 1, отличающееся тем, что каждый вычислительный узел содержит дешифратор, три регистра, группу регистров, первый и второй сдвигающие регистры, первый и второй триггеры, узел вычисления обратной величины числа, умножитель, вычитатель, n+9 групп элементов И, 2n + 5 элементов И, пять групп элементов ИЛИ и два элемента ИЛИ, при этом в каждом вычислительном узле информационные входы вычислительного узла подключены к первым входам элементов И первой и второй групп, выходы которых подключены к первым входам элементов ИЛИ первой группы и информационным входам первого регистра, выходы которого подключены к первым входам элементов И третьей группы и входам первой группы вычитателя, выходы которого подключены к первым входам элементов И четвертой группы, выходы которых подключены к первым входам элементов ИЛИ второй группы, выходы которых подключены к выходам группы вычислительного узла, выходы элементов ИЛИ первой группы подключены к информационным входам второго регистра, выходы которых подключены к информационному входу первого регистра группы, первым входам элементов И пятой группы и информационным входам узла вычисления обратной величины числа, выходы которого подключены к первым входам элементов И шестой группы, выходы которых подключены к первым входам элементов ИЛИ третьей группы, выходы которых подключены к входам первой группы умножителя, выходы которого подключены к входам второй группы вычитателя и информационным входам третьего регистра, выходы которого подключены к первым входам элементов И седьмой и восьмой групп, выходы которых подключены соответственно к первым входам элементов ИЛИ четвертой группы и вторым входам элементов ИЛИ второй группы, выходы элементов И третьей группы подключены к вторым входам элементов ИЛИ четвертой группы, выходы которых подключены к входам второй группы умножителя, первый управляющий вход вычислительного узла подключен к информационному входу первого триггера, вторым (инверсным) входам элементов И второй группы и первому входу первого элемента И, выход которого подключен к вторым входам элементов И первой группы, и к первым (инверсным) входам элементов И девятой группы, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ первой группы, инверсный выход первого триггера подключен к первым входам второго и третьего элементов И, выход второго элемента И подключен к вторым входам элементов И седьмой группы, элементов И четвертой группы и элементов И пятой группы, выходы которых подключены к вторым входам элементов ИЛИ третьей группы, выход третьего элемента И подключен соответственно к вторым входам элементов И восьмой группы, прямой выход первого триггера подключен к информационному входу первого сдвигающего регистра и первому входу четвертого элемента И, выход которого подключен к вторым входам элементов И третьей и шестой групп и первому входу пятого элемента И, выход которого подключен к входу синхронизации третьего регистра, второй управляющий вход вычислительного узла подключен к второму входу первого элемента И и информационному входу второго триггера, прямой выход которого подключен к второму входу третьего элемента И и информационному входу второго сдвигающего регистра, инверсный выход второго триггера подключен к вторым входам второго и четвертого элементов И, выходы с первого по L-й первого сдвигающего регистра подключены соответственно к первым входам элементов И с шестого по (L + 5)-й, выходы которых подключены к входам первого элемента ИЛИ, выход которого подключен к первому выходу вычислительного узла, выходы с первого по L-й второго сдвигающего регистра подключены соответственно к первым входам элементов И с (L + 6)-го по (2L + 5)-й, выходы которых подключены к входам второго элемента ИЛИ, выход которого подключен к второму выходу вычислительного узла, выходы K-х регистров группы () подключены к первым входам элементов И (K + 9)-й группы, выходы которых подключены к K-м входам элементов ИЛИ пятой группы, выходы которых подключены к вторым входам элементов И девятой группы, третий управляющий вход вычислительного узла подключен к входу дешифратора, K-й выход которого подключен к вторым входам (K + 5)-го элемента И, (K + L + 5)-го элементов И и элементов И (K + 9)-й группы, вход начальной установки вычислительного узла подключен к входам установки в "0" всех регистров и триггеров, тактовый вход вычислительного узла подключен к входам синхронизации первого и второго регистров, первого и второго сдвигающих регистров, регистров группы и второму входу пятого элемента И.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13