Устройство для вычисления собственных значений (n o n) матрицы

 

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления собственных значений матрицы (n · n). Цель изобретения - повышение надежности за счет организации контроля и резервирования, расширение функциональных возможностей за счет решения задач различных размерностей. Поставленная цель достигается тем, что устройство содержит L блоков обработки 1 (где L = p + R, здесь R - число резервных блоков обработки); блок 2 ввода - вывода; L комбинационных сумматоров 3; (L - 1) регистр 4; L узлов сравнения 5; L групп элементов ИЛИ 6; L групп элементов И 7; элемент ИЛИ - НЕ 8 и элемент ИЛИ 9. 2 з.п.ф-лы, 2 табл., 5 ил.

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления всех собственных значений (n · n)-матрицы.

Известно устройство для вычисления всех собственных значений симметрической (n · n)-матрицы, содержащее n вычислительных блоков первого типа, (3n²-n)/2 вычислительных блоков второго типа и блок анализа [1].

Наиболее близким по технической сущности является устройство для вычисления всех собственных значений (n · n)-матрицы, содержащее вычислительный блок первого типа, (2n-1) блоков обработки [2].

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

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

Поставленная цель достигается тем, что устройство, содержащее (2n-1) блоков обработки 1, причем тактовый вход 21 устройства подключен к тактовым входам всех блоков обработки 1, информационные входы первой группы 12 устройства подключены к информационным входам первых групп всех блоков обработки, первый управляющий вход 17 устройства подключен к первым управляющим входам всех блоков обработки, выходы первой группы i-го блока обработки 1 (где i = 1, ..., (2n-2)) подключены соответственно к информационным входам второй группы (i+1)-го блока обработки, введены с 2n-го по L-й блоки обработки 1 (где L = 2n - 1 + R, R - число резервных блоков обработки 1), блок ввода-вывода 2, L - комбинационных сумматоров 3, (L-1) регистр 4, L узлов сравнения 5, (L-1) группа элементов ИЛИ 6, L групп элементов И 7, элемент ИЛИ-НЕ 8 и элемент ИЛИ 9, причем тактовый вход 21 устройства подключен к тактовым входам блоков обработки с 2n-го по L-й, блока ввода-вывода 2 и входам записи/считывания всех регистров 4, первый и второй выходы i-го блока обработки подключены соответственно ко второму и третьему управляющим входам (i+1)-го блока обработки, выходы первой группы, первый и второй выходы j-го блока обработки 1 (где j = 2n-1, ..., L-1) подключены соответственно к информационным входам второй группы, второму и третьему управляющим входам (j+1)-го блока обработки, информационные входы второй группы 10, второй 13 и третий 14 управляющие входы устройства подключены соответственно к информационным входам первой группы, первому и второму управляющим входам блока ввода-вывода 2, выходы первой группы, первый и второй выходы которого подключены соответственно к информационным входам второй группы, второму и третьему управляющим входам первого блока обработки, выходы второй группы которого подключены к информационным входам второй группы блока ввода-вывода 2, информационные входы третьей группы k-го блока обработки 1 (где k = 1, ..., L) подключены соответственно к выходам элементов И 7 k-й группы, первые входы элементов И 7 l-й группы (где l = 1, ..., L-1) подключены соответственно к выходам второй группы (l + 1)-го блока обработки, первые входы элементов И 7 L-й группы подключены соответственно к информационным входам третьей группы 11 устройства, управляющие входы первой группы 18 которого подключены соответственно к управляющим входам первой группы первого блока обработки, выходы третьей группы k-го блока обработки подключены ко входам группы k-го комбинационного сумматора 3, выходы l-го комбинационного сумматора 3 подключены к информационным входам l-го регистра 4 и входам первой группы l-го узла сравнения 5, выходы L-го комбинационного сумматора 3 подключены ко входам первой группы L-го узла сравнения 5, инверсный и прямой выходы k-го узла сравнения 5 подключены соответственно ко вторым входам элементов И 7 k-й группы и k-му входу элемента ИЛИ-НЕ 8, выход которого подключен к первому входу элемента ИЛИ 9, выход которого подключен к выходу 30 признака отказа устройства, выходы l-го регистра 4 подключены соответственно к первым входам элемента ИЛИ 6 l-й группы, выходы которых подключены соответственно к управляющим входам первой группы (l+1)-го блока обработки 1, выходы четвертой группы l-го блока обработки 1 подключены соответственно ко вторым входам элементов ИЛИ 6 l-й группы, управляющие входы второй группы 19 устройства подключены к управляющим входам группы блока ввода-вывода 2 и управляющим входам вторых групп всех блоков обработки 1, управляющие входы третьей группы 20 устройства подключены ко входам вторых групп всех узлов сравнения 5, вход установки в исходное состояние 15, входы точности 16 и вход 28 признака окончания решения задачи подключены соответственно ко входу установки в исходное состояние, информационным входам третьей группы и третьему выходу блока ввода-вывода 2, четвертый выход которого подключен ко второму входу элемента ИЛИ 9, k-й вход установки первой группы 23 устройства подключен к первому входу установки k-го блока обработки 1, k-й вход установки второй группы 24 устройства подключен ко второму входу установки k-го блока обработки 1, k-й вход установки третьей группы 25 устройства подключен к третьему входу установки k-го блока обработки 1, k-й вход блокировки 22 устройства подключен ко входу блокировки k-го блока обработки 1, выходы групп со второй по (L + 1)-ю и выходы (L + 2)-й группы блока ввода-вывода подключены соответственно к выходам результата 26 и выходам признака результата 27 устройства.

Блок 2 ввода-вывода содержит первый и второй узлы 31 и 32 ввода-вывода, узел сравнения 33, триггер 34 и группу элементов И 35, причем информационные входы первой группы 36, второй группы 37, третьей группы 40, первый управляющий вход 38, второй управляющий вход 39, управляющие входы 41 группы и вход 43 установки в исходное состояние блока подключены соответственно к информационным входам первой, второй, третьей групп, первому, второму, третьему управляющим входам, управляющим входам группы и входу установки в исходное состояние первого и второго узлов ввода-вывода, тактовый вход 44 блока подключен к тактовым входам первого и второго узлов ввода-вывода и входу синхронизации триггера 34, выходы первой группы, выходы групп со второй по (L + 1)-ю и выходы (L + 2)-й группы, первый, второй и третий выходы первого узла ввода-вывода 31 подключены соответственно ко входам первой группы узла сравнения 33 и первым входам элементов И 35 группы, выходы которых подключены соответственно к выходам 45₁ первой группы, выходам 45₂ групп со второй по (L + 1)-ю, выходам 45₃ (L + 2)-й группы, первому 40, второму 47 и третьему 48 выходам блока, выходы первой, второй и третьей группы, первый, второй и третий выходы второго узла ввода-вывода 32 подключены ко входам второй группы узла сравнения 33, выход которого подключен к информационному входу триггера 34, прямой и инверсный выходы которого подключены соответственно ко вторым входам элементов И 35 группы и четвертому выходу 49 блока.

Каждый блок обработки 1 содержит первый и второй вычислительные узлы 50 и 51, узел сравнения 52, триггер 53, первый, второй и третий узлы элементов И 54, 55 и 56, узел элементов ИЛИ 57 и элемент И 58, причем информационные входы первой группы 59, третьей группы 60, управляющие входы первой группы 65, второй управляющий вход 62 и третий управляющий вход 63 подключены соответственно ко входам групп первого и второго узлов элементов И 54 и 55, выходы первой группы первого узла элементов И 54 подключены ко входам первой группы узла элементов ИЛИ 57, выходы которого подключены соответственно к выходам первой группы 74, второй группы 75, первому 76 и второму 77 выходам блока, выходы первой группы второго узла элементов И 55 подключены соответственно к информационным входам первых групп, вторых групп, первым управляющим и вторым управляющим входам первого и второго вычислительных узлов 50 и 51, выходы первой группы, второй группы, первый и второй выходы первого вычислительного узла 50 подключены ко входам первой группы узла сравнения 52 и входам группы третьего узла элементов И 56, выходы которого подключены ко входам второй группы узла элементов ИЛИ 57, выходы первой группы, второй группы, первый и второй выходы второго вычислительного узла 51 подключены ко входам второй группы узла сравнения 52, выход которого подключен к информационному входу триггера 53, выход которого подключен ко входу третьего узла элементов И 56, входу второго узла элементов И 55, инверсному входу первого узла элементов И 54 и третьему выходу 78 блока, выходы вторых групп первого и второго вычислительных узлов 54 и 55 подключены соответственно к выходам четвертой группы 73 и третьей группы 72 блока, информационные входы второй группы 61, первый управляющий вход 64, управляющие входы второй группы 66 и первый вход установки 67 которого подключены соответственно к информационным входам третьих групп, третьим управляющим входам, управляющим входам групп и входам установки в исходное состояние первого 50 и второго 51 вычислительных узлов, второй и третий входы установки блока подключены соответственно ко входам установки в нуль и единицу триггера 53, вход блокировки 70 и тактовый вход 71 блока подключены соответственно к первому (инверсному) и второму входам элемента И 58, выход которого подключен к тактовым входам первого и второго вычислительных узлов и входу синхронизации триггера 53.

Каждый узел ввода-вывода 31 (32) содержит L комбинационных вычитателей 79, узел вычисления обратной величины числа 80, два делителя 81 и 82, L узлов сравнения 83, два регистра 84 и 85, две группы регистров 86, три триггера - 87 - 89, (5L + 4) группы элементов И 90 - 97, шесть элементов И 98 - 103, три группы элементов ИЛИ 104 - 106, два элемента ИЛИ 107 и 108 и дешифратор 109, причем информационные входы первой группы 109 узла ввода-вывода подключены к информационным входам первого регистра 84, выходы которого подключены к первым входам элементов И 96 первой группы, выходы которых подключены к первым входам элементов ИЛИ 104 первой группы, выходы которых подключены к выходам первой группы 117 узла ввода-вывода, информационные входы второй группы 110 которого подключены к информационным входам второго регистра 85, прямые выходы которого подключены к информационным входам первого регистра первой группы 86₁, информационным входам узла вычисления обратной величины 80 и первым входам элементов И 97 второй группы, выходы которых подключены ко вторым входам элементов ИЛИ 104 первой группы, выходы узла вычисления обратной величины 80 и инверсные выходы второго регистра 85 подключены соответственно к первым входам элементов И третьей группы 95 и первым входам элементов И четвертой группы 94, выходы которых подключены соответственно к третьим и четвертым входам элементов ИЛИ 104 первой группы, выходы i-го регистра первой группы 86 (где i = 1, ..., L) подключены к первым входам элементов И 90 (4 + i)-й группы, первым входам элементов И 91 (4 + 2L + i)-й группы и выходам (2 + i)-й группы 118 узла ввода-вывода, выходы элементов И 91 (4 + 2L + i)-й группы подключены соответственно ко входам элементов ИЛИ 106 второй группы, выходы которых подключены к информационным входам первого регистра 86L + 1 второй группы, выходы элементов И 90 (4 + i)-й группы подключены ко входам первой группы i-го комбинационного вычитателя 79, выходы которого подключены соответственно к информационным входам первой группы i-го узла сравнения 83, выход которого подключен к первому входу элемента И 92 (4 + 3L + i)-й группы, выход i-го элемента И 92 (4 + 3L + i)-й группы подключен к i-м входам элементов И 93 (4 + 4L + i)-й группы, выход которого подключен к i-му входу второго элемента ИЛИ 108, выход которого подключен к третьему выходу 120 узла ввода-вывода, информационные входы 111 третьей группы которого подключены к информационным входам второй группы всех узлов сравнения 83, выходы j-го регистра второй группы 86 (где j = 1, ..., L - 1) подключены к информационным входам (j + 1)-го регистра 86 второй группы и первым входам элементов И 90 (4 + L + j)-й группы, выходы L-го регистра 86_2L второй группы подключены к первым входам элементов И 90_2L (4 + 2L)-й группы, выходы элементов И 90 (4 + L + i)-й группы подключены ко входам второй группы i-го вычитателя 79, первый 112 и второй 113 управляющие входы узла ввода-вывода подключены соответственно к информационным входам первого 87 и второго 88 триггеров, прямой выход первого триггера 87 подключен к первым входам первого элемента И 100, четвертого элемента И 103 и первому выходу 121 узла ввода-вывода, инверсный выход первого триггера 87 подключен к первым входам второго 101 и третьего 102 элементов И, прямой выход второго триггера 88 подключен ко вторым входам первого элемента И 100, третьего элемента 102 и второму выходу 122 узла ввода-вывода, инверсный выход второго триггера 88 подключен ко вторым входам второго 101 и четвертого 103 элементов И, управляющие входы группы 114 узла ввода-вывода подключены ко входам дешифратора 109, тактовый вход 114 узла ввода-вывода подключен к счетным входам первого 81 и второго 82 делителя, первым входам пятого 98 и шестого 99 элементов И, входам синхронизации триггеров с первого по третий 87 - 89 и входам записи/считывания первого 84 и второго 85 регистров, выход пятого элемента И 98 подключен ко входам записи/считывания регистров 86 первой и второй групп, выход шестого элемента И 99 подключен к первому входу первого элемента ИЛИ 107, выход которого подключен ко второму входу пятого элемента И 98, выходы первого 81 и второго 82 делителя подключены соответственно ко второму входу первого элемента ИЛИ 107 и управляющему входу третьего триггера 89, выход которого подключен ко второму входу шестого элемента И 99 и входу установки в нулевое состояние первого делителя 81, j-й выход дешифратора 109 подключен ко вторым входам элементов И 91 (4 + 2L + j)-й группы (j = ), j-му входу элементов ИЛИ 105 с j-го по первый (j = ) и (j + 1)-му входу элемента И 93 (4 + 4L + j)-й группы, выход j-го элемента ИЛИ 105 подключен ко вторым входам j-х элементов И (4 + j)-й группы 90, (4 + L + j)-й группы 90 и (4 + 3L + j)-й группы 92, L-й выход дешифратора подключен ко вторым входам L-х элементов И (4 + L)-й группы 90_L, (4 + 2L)-й группы 90_2L и (4 + 4L)-й группы 92_L, вход установки в исходное состояние 115 узла ввода-вывода подключен ко входам установки в нуль всех триггеров, регистров и делителей узла ввода-вывода, выход i-го элемента ИЛИ 105 второй группы подключен к i-м выходам (3 + L)-й группы 119 узла ввода-вывода, L-й выход которой подключен к L-му выходу дешифратора 109.

Каждый вычислительный узел 50 (51) содержит комбинационный сумматор 123, комбинационный умножитель 124, четыре регистра 125, 126, 127 и 129, группу регистров 128, три триггера 130 - 132, (L + 7) групп элементов И 133 - 140, три группы элементов ИЛИ 141 - 143, два элемента ИЛИ 144 и 145, шесть элементов И 146 - 151 и дешифратор 152, причем информационные входы первой группы 153 вычислительного узла подключены к информационным входам первого регистра 125, выходы которого подключены к информационным входам первой группы комбинационного умножителя 124 и первым входам элементов И 136 первой группы, выходы которых подключены к выходам первой группы 163 вычислительного узла, информационные входы второй 154 группы которого подключены к информационным входам второго регистра 127, выходы которого подключены к информационным входам второй группы комбинационного сумматора 123 и первым входам элементов И 138 второй группы, выходы которых подключены к первым входам элементов ИЛИ первой 143 группы, выходы которых подключены к информационным входам второй группы комбинационного умножителя 124, выходы которого подключены к информационным входам второй группы комбинационного сумматора 123, информационным входам третьего регистра 129 и первым входам элементов И 133 третьей группы, выходы которых подключены к первым входам элементов ИЛИ 142 второй группы, выходы которых подключены к информационным входам первого регистра 128 группы, информационные входы третьей группы 155 вычислительного узла подключены к первым входам элементов И 134 четвертой группы и информационным входам четвертого регистра 126, выходы которого подключены к первым входам элементов И 139 пятой группы, выходы которых подключены ко вторым входам элементов ИЛИ 143 первой группы, выходы комбинационного сумматора 123 подключены к первым входам элементов И шестой группы 135, выходы которых подключены ко вторым входам элементов ИЛИ 142 второй группы, входы третьей группы которого подключены к выходам элементов И 134 четвертой группы, выходы третьего 129 регистра подключены к первым входам элементов И 137 седьмой группы, выходы которых подключены к третьим входам элементов ИЛИ 143 первой группы, выходы i-го регистра 128 группы (где i = 1,...,L - 1) подключены к первым входам элементов И 140 (7 + i)-й группы и информационным входам (i + 1)-го регистра 128 группы, выходы L-го регистра группы 128 подключены к первым входам элементов И 140 (7 +L)-й группы, выходы элементов И 140 групп с восьмой по (7 + L)-ю подключены соответственно ко входам элементов ИЛИ 141 третьей группы, выходы которых подключены к выходам второй группы 162 вычислительного узла, первый управляющий вход 156 которого подключен к информационному входу первого триггера 130 и первому (инверсному) входу первого элемента И 151, второй управляющий вход 157 вычислительного узла подключен к информационному входу второго триггера 131 и второму входу первого элемента И 151, третий управляющий вход 158 вычислительного узла подключен к информационному входу третьего триггера 132 и третьему входу первого элемента И 151, прямой выход первого 130 триггера подключен к первым входам второго 148 и третьего 150 элементов И и первому выходу 164 вычислительного узла, инверсный выход первого триггера подключен в первым входам четвертого 147 и пятого 149 элементов И, прямой выход второго триггера 131 подключен ко вторым входам третьего 150 и четвертого 147 элементов И и второму выходу 165 вычислительного узла, инверсный выход второго триггера 131 подключен ко вторым входам второго 148 и пятого 149 элементов И, инверсный выход третьего триггера 132 подключен к третьим входам второго 148 и четвертого 147 элементов И, тактовый вход 160 вычислительного узла подключен ко входам записи/считывания регистров группы 128, первого 125, второго 127, четвертого 126 регистров, первому входу шестого элемента И 146 и входам синхронизации триггеров с первого по третий 130 - 132, вход установки 161 в исходное состояние вычислительного узла подключен ко входам установки в нулевое состояние всех регистров и триггеров, управляющие входы группы 159 вычислительного узла подключены ко входам дешифратора 152, k-й выход которого (где k = 1,..., L) подключен ко вторым входам элементов И 140 (7 + k)-й группы, выход первого 151 элемента И подключен ко вторым входам элементов И 134 четвертой группы, выход второго 148 элемента И подключен к вторым входам элементов И шестой 135 и седьмой 137 групп и первому входу первого элемента ИЛИ 144, выход которого подключен к вторым входам элементов И 136 первой группы, выход третьего 150 элемента И подключен к третьим входам элементов И 135 шестой группы, второму входу первого 144 элемента ИЛИ и первому входу второго элемента ИЛИ 145, выход которого подключен ко вторым входам элементов И 139 пятой группы, выход четвертого элемента И 147 подключен к вторым входам элементов И второй 138 и третьей 133 групп, третьему входу первого элемента ИЛИ 144 и второму входу шестого элемента И 146, выход которого подключен к входу записи/считывания третьего 129 регистра, выход пятого элемента И 149 подключен к четвертым входам элементов И 135 шестой группы, четвертому входу первого элемента ИЛИ 144 и второму входу второго элемента ИЛИ 145.

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

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

Блок 2 ввода-вывода (фиг. 2) содержит узлы ввода-вывода 31 и 32, узел сравнения 33, триггер 34, блок элементов И 35, информационные входы 36 и 37, управляющие входы 38 - 41, вход установки в исходное состояние 43, тактовый вход 44, выходы 45 - 49.

Блок обработки 1 (фиг. 3) содержит вычислительные узлы 50 и 51, узел сравнения 52, триггер 53, узлы элементов И 54 - 56, узел элементов ИЛИ 57, элемент И 58, информационные входы 59 - 61, управляющие входы 62 - 66, входы установки 67 - 69, вход блокировки 70, тактовый вход 71, выходы 72 - 78.

Узел ввода-вывода 31 (32) (фиг. 4) содержит комбинационные вычитатели 79, узел 80 вычисления обратной величины, делители 81 и 82, узлы сравнения 83, регистры 84 - 86, триггеры 87 - 89, группы элементов И 90 - 97, элементы И 98 - 103, группы элементов ИЛИ 104 - 106, элементы ИЛИ 107 и 108, дешифратор 109, информационные входы 109 - 111, управляющие входы 112 и 113, вход установки в исходное состояние 115, тактовый вход 116, выходы 117 - 122.

Вычислительный узел 50 (51) (фиг. 5) содержит комбинационный сумматор 123, комбинационный умножитель 124, регистры 125 - 129, триггеры 130 - 132, группы элементов И 133 - 140, группы элементов ИЛИ 141 - 143, элементы ИЛИ 144 и 145, элементы И 146 - 151, дешифратор 152, информационные входы 153 - 155, управляющие входы 156 - 159, тактовый вход 160, вход установки в исходное состояние 161, выходы 162 - 165.

В основу работы устройства положен итерационный треугольный степенной метод вычисления собственных значений λ_i (1≅ i ≅ n) матрицы A = {aij}, 1 ≅ i, j ≅ n, где имеет место распределение В основе вычислительной схемы треугольного степенного метода лежит последовательное вычисление матриц m = 1,2,... по правилу A·C_m-1=B_m, Bm= C_m·R_m, где C_о= , 1≅i, j≅n - некоторая нижняя треугольная матрица с единицами по главной диагонали.

При этом τ^(m_ii⁾ _→ λ_i при m _→ ∞ , 1≅i≅n, следовательно, при достаточно больших m можно положить λ_i≈ τ^(m_ii⁾ , 1≅i≅n.

Если итерационный процесс прерван на шаге с номером m, то приближенное вычисление собственных векторов x_i матрицы A может быть выполнено по правилу R_mU⁽_i^m)= τ^(m_ii⁾U⁽_i^m) (т. е. сначала находится решение U⁽_i^m) треугольной системы линейных алгебраических уравнений) x⁽_i^m)= C_mU⁽_i^m), x ≈ x⁽_i^m). Эти соотношения показывают, что если для вычисления собственных значений матрицы A достаточной диагональных элементов τ^(m_ii⁾, то для нахождения собственных векторов требуются еще и внедиагональные элементы матриц R_m и C_m.

На каждом итерационном шаге m перемножение матриц A·C_m-1 и LU - разложение матрицы B_m на матрицы C_m и R_m представляются следующими рекуррентными соотношениями:

Сформируем следующие матрицы, элементы которых будут подаваться на соответствующие входы устройства:

где знак * обозначает любое значение 0 или 1.

Элементы d_ij представляют l-разрядные числа a_ij и одноразрядное число γ, принимающее значение 0 или 1.

4. Матрицу {h^ij}, 1 ≅ i, j ≅ n:

Узел ввода-вывода 31 (32) обладает возможностью реализации следующих функций:

где α^j и - значения соответственно на входах 111 и 112 узла ввода-вывода на j-м такте;
Vⁱ⁺¹ и W^j+1 - значения соответственно на выходах 121 и 122 узла ввода-вывода на (j + 1)-м такте,
A^j+1 - значение на выходе 117 на (j + 1)-м такте, где

где a^j и b^j - значения соответственно на входах 109 и 110 узла ввода-вывода на j-м такте,

Кроме того, узел ввода-вывода 31 (32) производит выдачу собственных значений λ_i и формирование сигнала δ признака окончания вычислений собственных значений.

Приближения к собственным значениям матрицы с выхода регистра 85 подаются на вход регистра 86₁ в моменты времени

где m - номер итерации, m = 1, 2, 3, ... .

Запись приближений к собственным значениям λ⁽_i^m) в регистры 86_j (j = ) осуществляется тактовыми импульсами, которые подаются с выхода элемента И 98 в моменты времени . В табл. 1 приведены состояния делителя 81 по модулю счета (n + 1), делителя 82 по модулю счета n², триггера 89 и регистров 86_j (j = ) для n = 3. На (n² - 1)-м такте на выходе делителя 82₂ формируется единичный сигнал, который на n²-м такте устанавливает делитель 81 в нулевое состояние, а триггер 89 - в единичное состояние, который открывает элемент И 99. На (n² + 1)-м такте через элементы И 99, ИЛИ 107 и И 98 тактовый импульс подается на синхровходы регистров 86, в которые осуществляется запись собственных чисел. Триггер 89 устанавливается в нулевое состояние. На ((i - 1)n + i + mn² - 1)-м тактах (i ≠ 1) на выходе делителя 81 формируется единичный сигнал, который на ((i - 1)n + i + mn²)-м тактах (i ≠ 1) открывает элемент И 98 и разрешает запись в регистры 86. На (n²(m + 1) - 1)-м тактах на выходе делителя 82 формируется единичный сигнал, который на (n²(m + 1)-м такте устанавливает триггер 89 в единичное состояние и разрешается запись в регистры 86. На (n²(m + 1)-м такте выполняется проверка точности вычислений . Если данное соотношение выполняется, то на выходе 120 признака окончания вычислений формируется единичный сигнал δ = 1. При этом с выходов 118_i (i = ) снимаются значения λ_i. Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений λ_i продолжается. Проверка соотношения выполняется вычитателями 80, узлами сравнения 84 (i = ) и элементом И 104.

Выходы 119 узла 31 (32) ввода-вывода используются для указания (средствам внешнего интерфейса устройства) выходов 118, с которых снимаются значения λ_i для конкретного значения n ≅ L. На выходы 119₁, ..., 119_n, где n ≅ L, с выходов элементов ИЛИ 106₁, ..., 106_n выдаются единичные значения признаков p, а на выходы 119_n+1, ..., 119_L - нулевые значения признака p.

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

где α^j и - значения соответственно на входах 156 и 157 вычислительного узла на j-м такте;
V^j+1 и W^j+1 - значения соответственно на выходах 164 и 165 вычислительного узла на (j + 1)-м такте,

где b^j, a^j и c^j - значения соответственно на входах 155, 153 и 154 вычислительного узла на j-м такте;
k - параметр, определяемый алгоритмом;
A^j+1 - значение на выходе 163 вычислительного узла на (j + 1)-м такте;
C^j+n-1 - значение на выходе 162 вычислительного узла на (j + n - 1)-м такте,

γ^j - значение на входе 158 вычислительного узла на j-м такте.

По управляющему сигналу запись в регистр осуществляется на (j + 1)-м такте, а по управляющему сигналу μ^j₅ на j-м такте.

Вычислительный модуль первого типа 8 работает в четырех режимах, которые задаются управляющими сигналами α и β , подаваемыми соответственно на входы 15 и 16.

В зависимости от значений α и β , подаваемых соответственно на входы 111 и 112, узел 31 (32) ввода-вывода может работать в четырех режимах.

В первом режиме (α,β) = (1, 1). При этом на выходе элемента И 100 формируется единичный сигнал (μ₁ = 1), который открывает элементы И 96. На выход 109 подается число a, которое записывается в регистр 84 и через элементы И 96 и ИЛИ 104 выдается на выход 117. Число b^j подается на вход 110, записывается в регистр 85 и поступает на вход регистра 86₁.

Во втором режиме (α,β) = (0, 0). При этом на выходе элемента И 101 формируется сигнал μ₂ = 1, который открывает элементы И 97. Число b записывается в регистр 85, выдается на выход 117 и поступает на вход регистра 86₁.

В третьем режиме (α,β) = (0, 1). На выходе элемента И 102 формируется сигнал μ₃ = 1, который открывает элементы И 95. На выход 110 подается число b^j, которое записывается в регистр 85 и поступает на вход регистра 86₁. На выход 117 через узел вычисления обратной величины числа 80, элементы И 95 и ИЛИ 104 выдается значение 1/b.

В четвертом режиме (α^j,β^j) = (1, 0). На выходе элемента И 103 формируется сигнал μ^j₄ = 1. Открываются элементы И 94. В регистр 86 записывается число b^j, которое поступает на вход регистр 86₁. С инверсного выхода регистра 85 на выход 117 выдается число (-b^j) через элементы И 94 и ИЛИ 104.

Сравнение значений λ⁽_i^m+1) и λ⁽_i^m) выполняется в узле ввода-вывода независимо от режима работы, задаваемого значениями α и β .

Вычислительный узел 50 (51) работает в пяти режимах, которые задаются управляющими сигналами α,β и γ , которые подаются соответственно на входы 153, 157 и 158.

Во всех режимах осуществляется запись чисел из регистра 128_i (i = 1, L - 1) в регистр 128_i+1. На выход 162 выдается число, записанное в регистр 128 L-й. Управляющие сигналы α и β записываются соответственно в триггеры 130 и 131 и выдаются соответственно на выходы 164 и 165.

В первом режиме ( α^j,β^j,γ^j ) = (0, 1, 0), на выходе элемента И 147 формируется сигнал μ^j₁ = 1, который открывает элементы И 135, 136, 138 и 146. В регистр 125 записывается число a^j, в регистр 127 - число c^j. На выходе умножителя 124 формируется произведение a^j · c^j, которое на (j + 1)-м такте записывается в регистры 123 и 128. Число a^j через элементы И 136 выдается на выход 163.

Во втором режиме (α^j,β^j,γ^j) = (1, 0, 0), на выходе элемента И 148 формируется сигнал μ^j_2/ = 1, открываются элементы И 135, 136 и 137. Число a^j записывается в регистр 125 и через элементы И 136 выдается на выход 163. На выходе умножителя 124 формируется произведение a^j · < содержимое регистра 129>, на выходе сумматора 123 - сумма ((c^j + a^j · <содержимое регистра 129>), которая на (j + 1)-м такте записывается в регистр 128.

В третьем режиме (α^j,β^j) = (0, 0), на выходе элемента И 149 формируется сигнал μ^j₃ = 1. Открываются элементы И 139, 135 и 136. В регистр 125 записывается число a^j, которое выдается на выход 163. На выходе умножителя 124 формируется произведение a^j · b^j (число b^j записывается в регистр 126), на выходе сумматора 48 - сумма (c^j + a^j · b^j) (в регистр 127 записывается число c^j), которая записывается на (j + 1)-м такте в регистр 128₁.

В четвертом режиме (α^j,β^j) = (1, 1). На выходе элемента И 150 формируется сигнал μ^j₄ = 1. Вычислительный узел работает аналогично, как и в третьем режиме.

В пятом режиме (α^j,β^j,γ^j) = (0, 1, 1). На выходе элемента И 151 формируется сигнал μ^j₅ = 1, который открывает элементы И 134. Число b^j через элементы И 134 и ИЛИ 142 подается на вход регистра 128₁, которое на j-м такте по заднему фронту тактового импульса записывается в регистр 128₁.

Входные и выходные потоки данных формируются согласно следующих выражений.

На выходы 12_i и 17_i () подаются элементы входной матрицы {d_ij} = { a_ij, γ} в моменты времени

На выход 10 подаются элементы C^(o_qj⁾, 1 ≅ j < q в момент времени = (q - 1)n + j - 1.

На выходы 13 и 14 подаются соответственно управляющие сигналы α и β матриц {τ_ij} и в моменты времени

Собственные значения λ⁽_i^m) формируются на выходах 26_i (i = ) при значении δ = 1 на выходе 28 в моменты времени

Элементы матрицы {h^(m_ij⁾} формируются на выходе регистра 85 узла 31 (32) блока ввода-вывода в моменты времени

В табл. 1 приведены состояния триггеров, регистров и значения на выходах узлов ввода-вывода и вычислительных узлов для n = 3 при отсутствии отказа. На десятом такте в блоке 2 формируется значение λ⁽₁¹⁾ , на четырнадцатом такте -λ⁽₂¹⁾ , на восемнадцатом такте -λ⁽₃¹⁾ , на девятнадцатом -λ⁽₁²⁾ , на двадцать третьем такте -λ⁽²⁾_2/ , на двадцать седьмом такте -λ⁽₃²⁾ . На двадцать седьмом такте выполняется проверка соотношения
В каждом блоке обработки 1 производится дублирование вычислительных операций с помощью вычислительных узлов 50 и 51. Результаты выполнения операций формируются по завершении переходных процессов в комбинационных схемах 123 и 124 и выдаются на выходы 162 и 163 вычислительных узлов, откуда эти результаты поступают соответственно на информационные входы узла сравнения 52. При совпадении информации, поступающей на информационные входы узла сравнения 52 из вычислительных узлов 50 и 51, данный блок обработки 1_j считается исправным и единица с выхода узла сравнения 52 записывается в триггер 53, который используется для фиксации признака исправности данного блока обработки 1_j. С выхода триггера 53 единица поступает на соответствующие входы элементов И 56 и информация с выходов вычислительного узла 50 через элементы И 56 и ИЛИ 57 поступает на выходы 74 - 77 блока обработки 1_j. Единичный сигнал с выхода триггера 53 поступает также на инверсные входы элементов И 54 и блокирует обход данного блока обработки 1_j. В результате этого значение g, поступающее на вход 65 блока 1_j, выдается на выход 72 блока 1_j. Единичное значение выдается также на выход 78 блока 1_j и соответственно на выход 29_j признака отказа устройства. Единичный сигнал на выходе 29_j устройства указывает средствам внешнего управления об исправности блока 1_j. При несовпадении информации, поступающей на информационные входы узла сравнения 52 из вычислительных узлов 50 и 51, данный блок обработки 1_j считается неисправным и нулевой сигнал с выхода узла сравнения 52 записывается в триггер 53. С выхода триггера 53 нулевой сигнал поступает на соответствующие входы элементов И 56 и выдача информации с выходов 162 - 165 вычислительного узла 50 блокируется. С выхода триггера 53 нулевой сигнал поступает на соответствующие входы элементов И 55 и на инверсные входы элементов И 54. В результате поступление информации в вычислительные узлы 50 и 51 через элементы И 55 блокируется и открывается путь обхода данного блока обработки 1_j. В этом случае информация, поступающая из предыдущего блока обработки 1_j-1, через элементы И 54 и ИЛИ 57 выдается соответственно на выходы 74 - 77 данного блока обработки 1_j. Значение g, поступающее на вход 65 блока 1_j, выдается на выход 73 блока 1_j. Нулевое значение выдается также на выход 78 блока 1_j и соответственно на выход 29_j признака отказа устройства. Нулевой сигнал на выходе 29_j устройства указывает средствам внешнего управления об обнаружении отказа блока 1_j.

Для того чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 24_j устройства. В этом случае средствами внешнего управления на выходе 24_j устройства формируется единичный сигнал, который через вход 68 блока обработки 1_j поступает на вход установки в нуль триггера 55. Для того чтобы принудительно ввести блок обработки 1_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 25_j устройства. В этом случае средствами внешнего управления на входе 25_j устройства формируется единичный сигнал, который через вход 69 блока обработки 1_j поступает на вход установки в единицу триггера 53.

При этом работа блока обработки 1_j может быть блокирована путем подачи на вход 22 устройства единичного сигнала. В этом случае единичный сигнал через вход 70 блока 1_j поступает на инверсный вход элемента И 58, который блокирует прохождение тактовых импульсов на тактовых входы вычислительных узлов 50 и 51 и триггера 53.

Для установки регистров и триггеров вычислительных узлов 50 и 51 блока 1_j в исходное состояние при запусках и перезапусках устройства используется вход 23_j устройства. Для установки блока 1_j в исходное состояние на вход 23_j устройства подается единичный сигнал, который через вход 67 блока 1_j поступает на входы установки в исходное состояние вычислительных узлов 50 и 51. Вход установки в исходное состояние вычислительных узлов 50 и 51 подключен ко входам установки в нулевое состояние всех регистров и триггеров узлов 50 и 51 (на фиг. 5 не показаны).

На вход 18 устройства подается нулевое значение величины g. При наличии исправных блоков 1₁, ...., 1_2n-1 с выходов 29_I, ..., 29_2n-1 признака отказа устройства выдаются единичные сигналы, которые поступают на входы соответствующих комбинационных сумматоров 3_I, ..., 3_2n-1. Значение g, поступающее на вход 65 блока 1_i, где i = 1, ..., 2_n-1, в случае исправности блоков 1₁, ..., 1_i-1, равно i - 1. В случае исправности блока 1_i данное значение g выдается на выход 72 блока 1_i и поступает на соответствующий вход комбинационного сумматора 3_i, с выхода которого снимается значение g = i, которое записывается в регистр 4_i и поступает на одни входы узла сравнения 5_i, на другие входы которого поступает значение 2_n-1. Таким образом, на каждом также в случае исправности блока 1_i, с выхода комбинационного сумматора 3_i выдается значение g = i.

При совпадении значений g и 2n-1 с инверсного выхода узла сравнения 5_i выдается нулевой сигнал, который закрывает элементы И 7_2n-1 (при этом все остальные элементы И 7 остаются открытыми). В результате этого на вход 60 блока 1_2n-1 и далее на входы 154 соответствующих вычислительных узлов 50 - 51 поступает нулевое значение. Таким образом определяется рабочая линейка блоков 1 обработки. В случае отказа блока 1_i происходит обход этого блока, как описано выше. При этом в случае исправности предыдущих блоков 1_I, ..., 1_j-1 на вход 65 блока 1_j поступает значение g = j - 1, которое далее поступает на выход 73 блока 1_j, с выходов 72 и 78 блока 1_j снимаются нулевые значения и, таким образом, с выхода комбинационного сумматора 3_j снимается нулевое значение g. В результате с инверсного выхода узла сравнения 5_2n-1 снимается единичное значение, которое открывает элементы И 7_2n-1. Если блок 1_2n исправен, то на вход 65 блока 1_2n поступает значение g = 2n, с выхода 78 блока 1_2n выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 3_2n снимается значение g = 2n-1. В результате с инверсного выхода узла сравнения 5_2n снимается нулевой сигнал, который закрывает элементы И 7_2n. В результате на вход 60 блока 1_2n и далее на входы 154 соответствующих вычислительных узлов 50 и 51 поступают нулевые значения. Таким образом определяется рабочая линейка блоков 1 обработки. Нулевое значение величины g, формируемой на комбинационном сумматоре 3_i на последующих тактах, поступает на соответствующие входы элементов ИЛИ 6_i и в дальнейшем не влияет на величину g, поступающую на вход 65 блока 1_j+1.

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

При обнаружении S отказов блоков 1 происходит обход отказавших блоков 1 как было описано выше. Пусть k - номер последнего отказавшего блока 1 линейки, тогда с выхода 73 блока 1_k будет выдаваться значение g = 2n - 1- S, которое поступит на вход 65 блока 1_k+1. Поскольку блок 1_k+1 считается исправным, то свыхода 72 блока 1_k+1 выдается единичный сигнал, с выхода комбинационного сумматора 3_k+1 будет выдано значение g = 2n - 3, которое поступит на вход 65 блока 1_k+1 и т.д. При попадании значения g на вход 65 исправного блока 1_j, на выходе комбинационного сумматора 3_i формируется величины, равная g + 1. При попадании значения g на вход 65 неисправного блока 1_i, на выходе комбинационного сумматора 3_i формируется нулевое значение, а значение g с выхода 73 блока 1_i поступает на вход 65 следующего блока 1_i+1 линейки. С выхода комбинационного сумматора 3_2n-1+S на выход узла сравнения 5_2n-1+S подается значение g = 2n-1, с инверсного выхода узла сравнения 5_2n-1+S выдается нулевой сигнал, который закрывает элементы И 7_2n-1+S. В результате на выход 60 блока 1_2n-1+S и далее на выходы 154 соответствующих вычислительных узлов 50 и 51 поступают нулевые значения. Таким образом определяется рабочая линейка блоков 1 обработки. В данном случае на один из входов элемента ИЛИ-НЕ 8 поступает единичный сигнал и соответственно при наличии нулевого сигнала на выходе 49 блока 2 ввода-вывода с выхода 30 признака отказа устройства снимается нулевой сигнал, который свидетельствует об исправности устройства. При R < S на выходах узлов сравнения 5_I, ..., 5_L будут нулевые значения, с выхода элемента ИЛИ-НЕ 8 через элемент ИЛИ 9 на выход 30 признака отказа устройства будет выдано единичное значение, которое свидетельствует об исчерпании резерва и отказе устройства.

Таким образом, при накоплении R отказов работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной.

Узлы 31 и 32 ввода-вывода блока ввода-вывода 2 также работают в режиме дублирования. При совпадении информации, поступающей с выходов узлов 31 и 32 ввода-вывода на соответствующие входы узла сравнения 33, с выхода узла сравнения 33 на информационный вход триггера 34 поступает единичный сигнал, который записывается в триггер 34. При несовпадении информации, поступающей с соответствующих выходов узлов 31 и 32 ввода-вывода, с выхода узла сравнения 33 на информационный вход триггера 34 поступает нулевой сигнал, который записывается в триггер 34. Единичный сигнал с инверсного выхода триггера 34 через элемент ИЛИ 9 проходит на выход 30 признака отказа устройства, а нулевой сигнал с прямого выхода триггера 34 блокирует выдачу информации из блока 2. Установка триггера 34 в нулевое состояние производится с помощью подачи сигнала установки в исходное состояние всего устройства (соответствующие цепи и, в частности цепь установки в нуль триггера 34 (на фиг. 1 - 6 не показаны)).

Таким образом, при обнаружении (R + 1)-го отказа устройства либо при обнаружении отказа блока ввода-вывода, с выхода 30 устройства выдается единичный признак отказа, который далее поступает на средства внешнего управления. При работе устройства незаблокированные резервные блоки 1 автоматически функционируют в режиме контроля дублированием. В этом случае на входы первого резервного блока обработки 1_p, где p ≅ 2n информация поступает с выходов рабочей линейки устройства и с выходов блока 1_p+1. В результате обработки этой информации в вычислительных узлах 50 и 51 и последующего сравнения результатов в узле 52 резервных блоков обработки происходит обновление значений триггеров 53 этих блоков. Дальнейшее использование этих резервных блоков обработки будет происходить с учетом их исправности.

Значения n и (2n-1) подаются соответственно на входы 19 и 20 устройства. Значение n поступает через вход 41 блока ввода-вывода и вход 114 узла ввода-вывода 31 (32) на вход дешифратора 109. Кроме того, значение n подается на входы начальной установки счета делителей 81 и 82 (не показано). При этом на выходе делителя 81 периодически выдается единичный сигнал после подсчета (n + 1) тактовых импульсов, а на выходе делителя 82 - после подсчета n² тактовых импульсов (коэффициент пересчета делителя 81 равен (n + 1), а делителя 82 - n²).

После дешифрации значения n с соответствующего входа дешифратора 109 значение x_i(i= ) открывает элементы И 91_i и И 93_i. При этом с выхода элементов И 91_i приближенные значения λ_i подаются на информационный вход регистра 86_L+1 через элементы ИЛИ 106, а также открывается элемент И 93_i, формирующий сигнал δ = 1, который выдается через элемент ИЛИ 108 на выход 120 узла ввода-вывода. Значения х₁, х₂₃..., х_L с выходов дешифратора поступают на соответствующие входы элементов ИЛИ 105. Единичные значения P₁, P₂₁..., P_L с выходов элементов ИЛИ 105 открывают соответствующие элементы И 90 и И 92. При этом используется в формировании собственных значений λ_i и признака окончания вычислений δ число элементов И 90, 91, 92 и 93, регистров 86, узлов сравнения 83 и вычитателей 79, задаваемое значением n (n= ).

Значения n также поступают через вход 159 на вход дешифратора 152 вычислительных узлов 50 (51) блока обработки 1. После дешифрации значения n, с соответствующего выхода дешифратора 152 единичное значение х_i открывает элементы И 140_i (i = ) и информация с выходов регистра 128_i через элементы И 140_i и ИЛИ 141 выдается на выход 162 вычислительного узла.

Таким образом, путем задания конкретного значения n в устройстве реализуются возможности вычисления собственных значений матриц (n · n) для различных n ≅ L.

Рассмотрим работу устройства для конкретного случая n = 3 и R = 1. Пусть на пятнадцатом такте работы устройства обнаружен отказ блока обработки 1₃. В этом случае организация входного и выходного потоков данных, содержимое триггеров, регистров и формируемые значения на выходах блоков обработки 1₁, 1₂, 1₃, 1₄, 1₅ и 1₆ (где 1₆ - резервный блок обработки), приведены в табл. 2.

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

Один из возможных алгоритмов восстановления вычислительного процесса после обнаружения отказа блока 1_j предусматривает следующую последовательность действий:
Такт i: фиксирование блока 1_j с обнаруженным отказом;
такт i+1: блокировка блока 1_j, считывание с блока 1_j-1, обнуление и блокировка блоков 1_j-1, 1_j+1, 1_j+2, ..., 1_2n-1;
такт i+2: считывание с блока 1_j-2, обнуление и блокировка блока 1_j-2;
такт i+3: считывание с блока 1_j-3, обнуление и блокировка блока 1_j-3;
.................................................. ..................

такт i+k: считывание с блока 1_j-k, обнуление и блокировка блока 1_j-k;
такт i + j: обнуление блока 2 ввода-вывода;
такт i + j + 1: перезапуск устройства, разблокировка блоков 1₁, 1₂, ..., 1_j-1, 1_j+1, ..., 1_2n-1.

При обнаружении отказа блока 2 ввода-вывода на i-м такте происходит немедленная блокировка устройства на (i + 1)-м такте.

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

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

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

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

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

Следовательно, достоверность функционирования устройства может быть оценена как
D_ф= (2P_уз(t)-P²_уз(t)²ⁿ.
При P_уз(t)=0,999, n = 5, D_ф = 0,999989, а при P_уз(t) = 0,9999 и выше D_ф практически равна 1.

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

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

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

2. Устройство по п. 1, отличающееся тем, что каждый узел ввода-вывода содержит L комбинационных вычитателей, узел определения обратной величины числа, два делителя, L узлов сравнения, два регистра, две группы регистров, три триггера, (5L + 4) группы элементов И, три группы элементов ИЛИ, шесть элементов И, два элемента ИЛИ и дешифратор, причем информационные входы первой группы узла ввода-вывода подключены к информационным входам первого регистра, выходы которого подключены к первым входам элементов И первой группы, выходы которых подключены к первым входам элементов ИЛИ первой группы, выходы которых подключены к выходам первой группы узла ввода-вывода, информационные входы второй группы которого подключены к информационным входам второго регистра, прямые выходы которого подключены к информационным входам первого регистра первой группы, информационным входам узла вычисления обратной величины и первым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ первой группы, выходы узла вычисления обратной величины и инверсные выходы второго регистра подключены соответственно к первым входам элементов И третьей группы и первым входам элементов И четвертой группы, выходы которых подключены соответственно к третьим и четвертым входам элементов ИЛИ первой группы, выходы b-го регистра первой группы (где b = 1,..., L) подключены к первым входам элементов И (4 + b)-й группы, первым входам элементов И (4 + 2L + b)-й группы и выходам (2 + b)-й группы узла ввода-вывода, выходы элементов И (4 + 2L + b)-й группы подключены соответственно к входам элементов ИЛИ второй группы, выход которых подключен к информационным входам первого регистра второй группы, выходы элементов И (4 + b)-й группы подключены к входам первой группы b-го комбинационного вычитателя, выходы которого подключены соответственно к информационным входам первой группы b-го узла сравнения, выход которого подключен к первому входу элемента И (4 + 3L + b)-й группы, выход b-го элемента И (4 + 3L + b)-й группы подключен к b-м входам элементов И (4 + 4L + b)-й группы, выход которого подключен к b-му входу второго элемента ИЛИ, выход которого подключен к третьему выходу узла ввода-вывода, информационные входы третьей группы которого подключены к информационным входам второй группы всех узлов сравнения, выходы l-го регистра второй группы (где l = 1, ..., L-1) подключены к информационным входам (j + l)-го регистра второй группы и первым входам элементов И (4 + L + l)-й группы, выходы L-го регистра второй группы подключены к первым входам элементов И (4 + 2L)-й группы, выходы элементов И (4 + L + b)-й группы подключены к входам второй группы b-го вычитателя, первый и второй управляющие входы узла ввода-вывода подключены соответственно к информационным входам первого и второго триггеров, прямой выход первого триггера подключен к первым входам первого элемента И, четвертого элемента И и первому выходу узла ввода-вывода, инверсный выход первого триггера подключен к первым входам второго и третьего элементов И, прямой выход второго триггера подключен к вторым входам первого элемента И, третьего элемента и второму выходу узла ввода-вывода, инверсный выход второго триггера подключен к вторым входам второго и четвертого элементов И, управляющие входы группы узла ввода-вывода подключены к входам дешифратора, тактовый вход узла ввода-вывода подключен к счетным входам первого и второго делителей, первым входам пятого и шестого элементов И, входам синхронизации триггеров с первого по третий и входам записи/считывания первого и второго регистров, выход пятого элемента И подключен к входам записи/считывания регистров первой и второй групп, выход шестого элемента И подключен к первому входу первого элемента ИЛИ, выход которого подключен к второму входу пятого элемента И, выходы первого и второго делителей подключены соответственно к второму входу первого элемента ИЛИ и управляющему входу третьего триггера, выход которого подключен к второму входу шестого элемента И и входу установки в нулевое состояние первого делителя, g-й выход дешифратора подключен к вторым входам элементов И (4 + L + g)-й группы g-му входу элементов ИЛИ с g-го по первый и (j + 1)-му входу элемента И (4 + 4L + g)-й группы, выход g-го элемента ИЛИ подключен к вторым входам g-х элементов И (4 + g)-й группы, (4 + L + g)-й группы и (4 + 3L + g)-й группы, L-й выход дешифратора подключен к вторым входам L-х элементов И (4 + L)-й группы, (4 + 2L)-й группы и (4 + 4L)-й группы, вход установки в исходное состояние узла ввода-вывода подключен к входам установки в нуль всех триггеров, регистров и делителей узла ввода-вывода, выход b-го элемента ИЛИ второй группы подключен к b-м выходам (3 + L)-й группы узла ввода-вывода, L-й выход которой подключен к L-му выходу дешифратора.

3. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит комбинационный сумматор, комбинационный умножитель, четыре регистра, группу регистров, три триггера, L + 7 групп элементов И, три группы элементов ИЛИ, два элемента ИЛИ, шесть элементов И и дешифратор, причем информационные входы первой группы вычислительного узла подключены к информационным входам первого регистра, выходы которого подключены к информационным входам первой группы комбинационного умножителя и первым входам элементов И первой группы, выходы которых подключены к выходам первой группы вычислительного узла, информационные входы второй группы которого подключены к информационным входам второго регистра, выходы которого подключены к информационным входам второй группы комбинационного сумматора и первым входам элементов И второй группы, выходы которых подключены к первым входам элементов ИЛИ первой группы, выходы которых подключены к информационным входам второй группы комбинационного умножителя, выходы которого подключены к информационным входам второй группы комбинационного сумматора, информационным входам третьего регистра и первым входам элементов И третьей группы, выходы которых подключены к первым входам элементов ИЛИ второй группы, выходы которых подключены к информационным входам первого регистра группы, информационные входы третьей группы вычислительного узла подключены к первым входам элементов И четвертой группы и информационным входам четвертого регистра, выходы которого подключены к первым входам элементов И пятой группы, выходы которых подключены к вторым входам элементов ИЛИ первой группы, выходы комбинационного сумматора подключены к первым входам элементов И шестой группы, выходы которых подключены к вторым входам элементов ИЛИ второй группы, входы третьей группы которого подключены к выходам элементов И четвертой группы, выходы третьего регистра подключены к первым входам элементов И седьмой группы, выходы которых подключены к третьим входам элементов ИЛИ первой группы, выходы l-го регистра группы (где l = 1,..., L - 1) подключены к первым входам элементов И (7 + l)-й группы и информационным входам (l + 1)-го регистра группы, выходы L-го регистра группы подключены к первым входам элементов И (7 + L)-й группы, выходы элементов И групп с восьмой по (7 + L)-ю подключены соответственно к входам элементов ИЛИ третьей группы, выходы которых подключены к выходам второй группы вычислительного узла, первый управляющий вход которого подключен к информационному входу первого триггера и первому (инверсному) входу первого элемента И, второй управляющий вход вычислительного узла подключен к информационному входу второго триггера и второму входу первого элемента И, третий управляющий вход вычислительного узла подключен к информационному входу третьего триггера и третьему входу первого элемента И, прямой выход первого триггера подключен к первым входам второго и третьего элементов И и первому выходу вычислительного узла, инверсный выход первого триггера подключен к первым входам четвертого и пятого элементов И, прямой выход второго триггера подключен к вторым входам третьего и четвертого элементов И и второму выходу вычислительного узла, инверсный вход второго триггера подключен к вторым входам второго и пятого элементов И, инверсный вход третьего триггера подключен к третьим входам второго и четвертого элементов И, тактовый вход вычислительного узла подключен к входам записи/считывания регистров группы, первого, второго, четвертого регистров, первому входу шестого элемента И и входам синхронизации триггеров с первого по третий, вход установки в исходное состояние вычислительного узла подключен к входам установки в нулевое состояние всех регистров и триггеров, управляющие входы группы вычислительного узла подключены к входам дешифратора, g-й выход которого (где g = 1, ..., L) подключен к вторым входам элементов И (7 + g)-й группы, выход первого элемента И подключен к вторым входам элементов И четвертой группы, выход второго элемента И подключен к вторым входам элементов И шестой и седьмой групп и первому входу первого элемента ИЛИ, выход которого подключен к вторым входам элементов И первой группы, выход третьего элемента И подключен к третьим входам элементов И шестой группы, второму входу первого элемента ИЛИ и первому входу второго элемента ИЛИ, выход которого подключен к вторым входам элементов И пятой группы, выход четвертого элемента И подключен к вторым выходам элементов И второй и третьей групп, третьему входу первого элемента ИЛИ и второму входу шестого элемента И, выход которого подключен к входу записи/считывания третьего регистра, выход пятого элемента И подключен к четвертым входам элементов И шестой группы, четвертому входу первого элемента ИЛИ и второму входу второго элемента ИЛИ.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16, Рисунок 17, Рисунок 18, Рисунок 19, Рисунок 20