УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Российский патент 1998 года по МПК G06F17/12 

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

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

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

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

Недостатком этого устройства являются большие аппаратурные затраты.

Цель изобретения - сокращение аппаратурных затрат.

Поставленная цель достигается тем, что устройство для решения систем линейных алгебраических уравнений содержит M вычислительных модулей 16 первого типа, M вычислительных модулей 17 второго типа, M вычислительных модулей 18 третьего типа, M вычислительных модулей 19 четвертого типа, где M - размерность матриц, блок памяти 20, группу регистров 21, регистр 22 и три группы элементов ИЛИ 23, 24 и 25, причем первый 1 информационный вход устройства подключен к первым входам перовой 23 группы элементов ИЛИ, вторые входы которой подключены к первому информационному выходу первого 18₁ вычислительного модуля третьего типа, а выход - к информационному входу первого 16₁ вычислительного модуля первого типа, второй 2 информационный вход устройства подключен к первым входам второй 24 группы элементов ИЛИ, вторые входы которой подключены к выходу 21(M²-M+1)-гo регистра группы, а выход - к первому информационному входу первого 17₁ вычислительного модуля второго типа, третий 3 и четвертый 4 информационные входы устройства подключены соответственно к первому и второму информационным входам 18_M-го вычислительного модуля третьего типа, пятый 5 информационный вход устройства подключен к первым входам третьей 25 группы элементов ИЛИ, вторые входы которой подключены к выходу регистра 22, а выход - к второму информационному входу 19_M-го вычислительного модуля четвертого типа, первый 6 и второй 7 управляющие входы устройства подключены к первому и второму управляющим входам первого 16₁ вычислительного модуля первого типа, первый информационный выход, первой и второй управляющие выходы 16_i-го вычислительного модуля первого типа подключены соответственно к информационному входу, первому и второму управляющим входам 16_(i+1)-го вычислительного модуля первого типа, второй информационный выход 16_i-го вычислительного модуля первого типа подключен к второму информационному входу 17_i-го вычислительного модуля второго типа, третий 8 и четвертый 9 управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого 17₁ вычислительного модуля второго типа, информационный выход, первый и второй управляющие выходы 17_i-го вычислительного модуля второго типа подключены соответственно к информационному входу, первому и второму управляющим входам 17_(i+1)-го вычислительного модуля второго типа, информационный выход 17_M-го вычислительного модуля второго типа подключен к информационному входу блока памяти 20 и третьему информационному входу 18_M-го вычислительного модуля третьего типа, пятый 10 и шестой 11 управляющие входы устройства подключены соответственно к первому и второму управляющим входам18_M-го вычислительного модуля третьего типа, первый, второй и третий информационные входы, первый и второй управляющие входы 18_i-го вычислительного модуля третьего типа подключены соответственно к первому, второму и третьему информационным выходам, первому и второму управляющим выходам 18 (_i+1)-го вычислительного модуля третьего типа, первый информационный выход первого 18₁ вычислительного модуля третьего типа подключен к информационному входу первого 21₁ регистра группы, информационный выход 21_i-го регистра группы подключен к информационному входу 21_i+1-го регистра группы, седьмой 12 и восьмой 13 управляющие входы устройства подключены соответственно к входам записи и считывания блока памяти 20, i-й выход которого подключен к третьему информационному входу 19_i-го вычислительного модуля четвертого типа, (M+1)-й выход блока памяти 20 подключен к первому информационному входу первого 19₁ вычислительного модуля четвертого типа, управляющий вход которого подключен к девятому 14 управляющему входу устройства, первый информационный выход, второй информационный вход и управляющий выход 19_i-го вычислительного модуля четвертого типа подключены соответственно к первому информационному входу, второму информационному выходу и управляющему входу 19_(i+1)-го вычислительного модуля четвертого типа, первый информационный выход 19_М-го вычислительного модуля четвертого типа подключен к информационному входу регистра 22, выход которого подключен к выходу 26 устройства, синхровход 15 которого подключен к синхровходам всех вычислительных модулей, регистров и блока памяти 20, при этом вычислительный модуль первого 16 типа содержит сумматор 30, умножитель 31, узел вычисления обратной величины числа 32, первый 33 и второй 34 регистры, группу регистров 35_i , первую 36_i и вторую 37_i группы триггеров, одиннадцать групп элементов И 38 - 48, пять элементов И 49 - 53, четыре группы элементов ИЛИ 54 - 57, два элемента ИЛИ 58 и 59, причем информационный вход 27 подключен к информационному входу первого 33 регистра, прямой выход которого подключен к первым входам первой 41 группы элементов И, первому входу сумматора 30 и входу узла вычисления обратной величины числа 32, выход которого подключен к первым входам второй 43 и третьей 47 групп элементов И, инверсный выход первого 33 регистра подключен к первым входам четвертой 48 и восьмой 40 группы элементов И, выход элементов И первой 41 группы подключен к первым входам элементов ИЛИ первой 54 группы, вторые входы которых подключены к выходу элементов И пятой 38 группы, а выход - к первому входу умножителя 31, второй вход которого подключен к выходу первого 35₁ регистра группы, а выход - к информационному входу второго 34 регистра и первым входам элементов И шестой 42 группы, выход которой подключен к второму входу сумматора 30, выход которого подключен к первым входам элементов И седьмой 44 группы, синхровход 64 вычислительного модуля подключен к первому входу первого 53 элемента И, выход которого подключен к синхровходу второго 34 регистра, выход которого подключен к первым входам элементов И пятой 38 и девятой 39 групп, выход которой подключен к первым входам элементов ИЛИ второй 55 группы, вторые входы которой подключены к выходу элементов И седьмой 44 группы, а выход - к первому 60 информационному выходу вычислительного модуля, выход элементов И восьмой 40 группы подключен к первым входам элементов ИЛИ третьей 56 группы, вторые входы которых подключены к выходу элементов И второй 43 группы, а выход - к информационному входу второго 35₂ регистра группы, выход 35_i-го регистра группы подключен к информационному входу 35_(i+1)-го регистра группы, выход 35_M-го регистра группы подключен к информационному входу первого 35₁ регистра группы, выход которого подключен к первым входам элементов И десятой 46 и одиннадцатой 45 групп, вторые входы которой подключены к выходу первого 58 элемента ИЛИ, а выход - к третьим входам элементов ИЛИ третьей 56 группы, выход второго 59 элемента ИЛИ подключен к вторым входам элементов И десятой 46 группы, выходы элементов И десятой 46, третьей 47 и четвертой 48 групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ четвертой 57 группы, выход которой подключен к второму 61 информационному выходу вычислительного модуля, первый 28 и второй 29 управляющие входы которого подключены соответственно к информационным входам первых триггеров первой 36₁ и второй 37₁ групп, выходы i-го триггера первой 36 и второй 37 групп подключены к информационному входу (i+1)-го триггера соответственно первой 36 и второй 37 групп, выходы (M + 2)-го триггера первой 36 и второй 37 групп подключены соответственно к первому 62 и второму 63 управляющим выходам вычислительного модуля, прямой выход первого 36₁ триггера первой группы подключен к первым входам четвертого 51 и пятого 52 элементов И, а инверсный выход - к первым входам второго 49 и третьего 50 элементов И, прямой выход первого 37₁ триггера второй группы подключен к вторым входам триггера 50 и пятого 52 элементов И, а инверсный выход - ко вторым входам второго 49 и четвертого 51 элементов И, выход второго 49 элемента И подключен к вторым входам элементов И второй 43 и третьей 47 групп, выход третьего элемента И 50 подключен к вторым входам элементов И восьмой 40 и четвертой 48 групп, выход четвертого 51 элемента И подключен к вторым входам элементов И девятой 39 группы, первого 53 элемента И и первым входам первого 58 и второго 59 элементов ИЛИ, выход пятого 52 элемента И подключен к вторым входам элементов И пятой 38, шестой 42 и седьмой 44 групп и вторым входам первого 58 и второго 59 элементов ИЛИ, синхровод 64 вычислительного модуля подключен к синхровходам первого 33 регистра, регистров группы 35 и триггеров первой 36 и второй 37 группы, при этом вычислительный модуль второго 17 типа содержит сумматор 70, умножитель 71, три регистра 72 - 74, группу регистров 75_i, первую 76_i и вторую 77_i группы триггеров, девять групп элементов И 78 - 86, пять элементов И 87 - 91, четыре группы элементов ИЛИ 92 - 95 и девять элементов ИЛИ 96 - 104, причем первый 65 информационный вход вычислительного модуля подключен к информационному входу первого 72 регистра, выход которого подключен к первым входам элементов И первой 79 и второй 82, групп, второй 66 информационный вход вычислительного модуля подключен к информационному входу второго 74 регистра, выход которого подключен к первым входам элементов И третьей 78 и четвертой 83 групп, выход первого 75₁ регистра группы подключен к первым входам элементов И пятой 81 группы, выход третьего 73 регистра подключен к первым входам элементов И шестой 80 и седьмой 85 групп, выход сумматора 70 подключен к первым выходам элементов И восьмой 86 группы, выходы первого 97 и второго 98 элементов ИЛИ подключены к вторым входам соответственно элементов И первой 79 и шестой 80 групп, выходы которых подключены соответственно к первым входам элементов ИЛИ первой 92 группы, выход которой подключен к первому входу умножителя 71, выход которого подключен к первому входу сумматора 70 и информационному входу третьего 73 регистра, синхровход которого подключен к выходу пятого элемента И 91, выход третьего 101 элемента ИЛИ подключен к вторым входам элементов И второй 82 группы, выход которой подключен к второму входу сумматора 70, выход четвертого 96 и пятого 99 элементов ИЛИ подключены к вторым входам соответственно элементов И третьей 78 и пятой 81 групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ второй 93 группы, выход которой подключен к второму входу умножителя 71, выход шестого 102 элемента ИЛИ подключен к первым входам элементов И девятой 84 группы, выход которой подключен к первым входам элементов ИЛИ третьей 94 группы, вторые входы которой подключены к выходу элементов И четвертой 83 группы, вторые входы которых подключены к выходу седьмого 100 элементов ИЛИ, выход элементов ИЛИ третьей 94 группы подключен к информационному входу второго 75₂ регистра группы, выход 75_i-го регистра группы подключен к информационному входу 75_(i+1)-го регистра группы, выход 75_M-го регистра группы подключен к информационному входу первого 75₁ регистра группы, выход которого подключен к вторым входам элементов И девятой 84 группы, выходы восьмого 103 и девятого 104 элементов ИЛИ подключены к вторым входам соответственно элементов И седьмой 85 и восьмой 86 групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ четвертой 95 группы, выход которой подключен к информационному 105 выходу вычислительного модуля, первый 68 и второй 69 управляющие входы которого подключены к информационным входам первых триггеров соответственно первой 76₁ и второй 77₁ групп, выходы первых триггеров первой 76₁ и второй 77₁ групп подключены к информационным входам вторых триггеров соответственно первой 76₂ и второй 77₂ групп, выходы которых подключены соответственно к первому 106 и второму 107 управляющим выходам вычислительного модуля, прямой выход первого 76₁ триггера первой группы подключен к первым входам третьего 89 и четвертого 90 элементов И, а инверсный выход - к первым входам первого 87 и второго 88 элементов И, прямой выход первого 77₁ триггера второй группы подключен к вторым входам второго 88 и четвертого 90 элементов И, а инверсный выход - к вторым входам первого 87 и третьего 89 элементов И, выход первого 87 элемента И подключен к первым входам пятого элемента И 91, первого 97, четвертого 96, седьмого 100 и восьмого 103 элементов ИЛИ, выход второго 88 элемента И подключен к первым входам второго 98, третьего 101 и девятого 104 элементов ИЛИ и к вторым входам четвертого 96 и седьмого 100 элементов ИЛИ, выход третьего 89 элемента И подключен к первым входам пятого 99 и шестого 102 элементов ИЛИ и к вторым входам пятого 91 элемента И, первого 97 и восьмого 103 элементов ИЛИ, выход четвертого 90 элемента И подключен к вторым входам второго 98, третьего 101, пятого 99, шестого 102 и девятого 104 элементов ИЛИ, синхровход 67 вычислительного модуля подключен к синхровходам первого 72 и второго 74 регистров, регистров группы 75 и триггеров первой 76 и второй 77 групп, при этом вычислительный модуль третьего 18 типа содержит сумматор 114, умножитель 115, четыре регистра 116 - 119, две группы регистров 120_i и 121_j, два триггера 122 и 123, две группы элементов И 124 и 125, пять элементов И 126 - 130, группу элементов ИЛИ 131 и три элемента ИЛИ 132 - 134, причем первый 110 информационный вход вычислительного модуля подключен к информационному входу первого 119 регистра, выход которого подключен к первому входу сумматора 114, второй вход которого подключен к выходу умножителя 115, а выход - к первому 137 информационному выходу вычислительного модуля, второй 108 информационный вход которого подключен к первым входам элементов И первой 124 группы и информационному входу первого 120₁ регистра первой группы выход 120_i-го регистра первой группы подключен к информационному входу 120_(i+1)-го регистра первой группы, выход 120_(M+1)-го регистра первой группы подключен к второму 135 информационному выходу вычислительного модуля, выходы первого 132 и второго 133 элементов ИЛИ подключены к вторым входам элементов И соответственно первой 124 и второй 125 групп, выходы которых подключены соответственно к первым и вторым входам группы элементов ИЛИ 131, выход которой подключен к информационному входу первого 121₁ регистра второй группы, выход 121_i-го регистра второй группы подключен к информационному входу 121_(i+1)-го регистра второй группы, выход 121_M-го регистра второй группы подключен к первым входам элементов И второй 125 группы, выход первого 121₁ регистра второй группы подключен к первому входу умножителя 115, второй вход которого подключен к выходу второго 118 регистра, синхровход которого подключен к выходу первого 130 элемента И, первый вход которого подключен к выходу третьего 134 элемента ИЛИ, а второй вход - к синхровходу 113 вычислительного модуля, третий 109 информационный вход которого подключен к информационным входам второго 118 и третьего 116 регистров, выход третьего регистра 116 подключен к информационному входу четвертого 117 регистра, выход которого подключен к третьему 136 информационному выходу вычислительного модуля, первый 111 и второй 112 управляющие входы вычислительного модуля подключены к информационным входам соответственно первого 122 и второго 123 триггеров, выходы которых подключены соответственно к первому 138 и второму 139 управляющим выходам вычислительного модуля, прямой выход первого 122 триггера подключен к первым входам четвертого 128 и пятого 129 элементов И, а инверсный выход - к первым входам второго 126 и третьего 127 элементов И, прямой выход второго 123 триггера подключен к вторым входам третьего 127 и пятого129 элементов И, а инверсный выход - к вторым входам второго 126 и четвертого 128 элементов И, выход второго 126 элемента И подключен к первым входам первого 132 и третьего 134 элементов ИЛИ, выход третьего 127 элемента И подключен к второму входу первого 132 элемента ИЛИ, выход четвертого 128 элемента И подключен к вторым входам второго 133 и третьего 134 элементов ИЛИ, выход пятого 129 элемента И подключен к первому входу второго 133 элемента И, синхровход 113 вычислительного модуля подключен к синхровходам регистров первой 120 и второй 121 групп, первого 119, третьего 116 и четвертого 117 регистров, первого 122 и второго 123 триггеров, при этом вычислительный модуль четвертого 19 типа содержит сумматор 145, умножитель 146, пять регистров 147 - 151, триггер 152, две группы элементов И 153 и 154 и группу элементов ИЛИ 155, причем первый 140 информационный вход вычислительного модуля подключен к информационному входу первого 147 регистра, выход которого подключен к первому входу сумматора 145, второй вход которого подключен к выходу умножителя 146, а выход - к первому 156 информационному выходу вычислительного модуля, второй 141 информационный вход которого подключен к информационному входу второго 148 регистра, выход которого подключен к первым входам элементов И первой 154 группы и второму 157 информационному выходу вычислительного модуля, третий 142 информационный вход которого подключен к информационному входу третьего 149 регистра, выход которого подключен к первому входу умножителя 146, второй вход которого подключен к выходу четвертого 151 регистра, выход элементов И первой 154 группы подключен к первым входам группы элементов ИЛИ 155, вторые входы которой подключены к выходу элементов И второй 153 группы, а выход - к информационному входу четвертого 151 регистра, выход которого подключен к информационному входу пятого 150 регистра, выход которого подключен к первым входам элементов И второй 153 группы, вторые входы которой подключены к прямому выходу триггера 152, инверсный выход которого подключен к вторым входам элементов И первой 154 группы управляющий вход 143 вычислительного модуля подключен к информационному входу триггера 152, выход которого подключен к управляющему выходу 158 вычислительного модуля, синхровход 144 которого подключен к синхровходу триггера 152.

На фиг. 1 представлена структурная схема устройства для решения систем линейных алгебраических уравнений (СЛАУ); на фиг. 2 - структурная схема вычислительного модуля первого типа; на фиг. 3 - то же, второго типа; на фиг. 4 - то же, третьего типа; на фиг. 5 - то же, четвертого типа.

Устройство для решения СЛАУ содержит первый 1, второй 2, третий 3, четвертый 4 и пятый 5 информационные входы, первый 6, второй 7, третий 8, четвертый 9, пятый 10, шестой 11 и седьмой 12, восьмой 13 и девятый 14 управляющие входы, синхровход 15, первые 16_i вторые 17_i третьи 18_i и 19_i четвертые вычислительные модули, блок памяти 20, группу регистров 21_i , регистр 22, первую 23, вторую 24 и третью 25 группы элементов ИЛИ и выход 26.

Вычислительный модуль первого типа 16 содержит информационный вход 27, первый 28 и второй 29 управляющие входы, сумматор 30, умножитель 31, узел вычисления обратной величины числа 32, первый 33 и второй 34 регистры, группу регистров 35_i, первую 36_i и вторую 37_i группы триггеров , группы элементов И 38 - 48, элементы И 49 - 53, группы элементов ИЛИ 54 - 57, элементы ИЛИ 58 - 59, первый 60 и второй 61 информационные выходы, первый 62 и второй 63 управляющие выходы и снхровход 64.

Вычислительный модуль второго типа содержит первый 65 и второй 66 информационные входы, синхровход 67, первый 68 и второй 69 управляющие входы, сумматор 70, умножитель 71, первый 72, второй 73 и третий 74 регистры, группу регистров 75_i, первую 76_i и вторую 77_i группы триггеров, группы элементов И 78 - 86, элементы И 87 - 91, группы элементов ИЛИ 92 - 95, элементы ИЛИ 96 - 104, информационный выход 105, первый 106 и второй 107 управляющие выходы.

Вычислительный модуль третьего типа содержит первый 110, второй 108 и третий 109 информационные входы, первый 111 и второй 112 управляющие входы, синхровход 113, сумматор 114, умножитель 115, регистры 116 - 119, первую 120_i и вторую 121_i группы регистров, первый 122 и второй 123 триггеры, группы элементов И 124 и 125, элементы И 126 - 130, группу элементов ИЛИ 131, элементы ИЛИ 132 - 134, первый 137 и второй 139 управляющие выходы.

Вычислительный модуль четвертого типа содержит первый 140, второй 141 и третий 142 информационные входы, управляющий вход 143, синхровход 144, сумматор 145, умножитель 146, регистры 147 - 151, триггер 152, группы элементов И 153 и 154, группу элементов ИЛИ 155, первый 156 и второй 157 информационные выходы и управляющий выход 158.

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

Пусть дана система линейных алгебраических уравнений

где
C₁, . . . , C_N - M х M плотные матрицы с диагональным преобладанием (диагональное преобладание на практике часто есть, например, когда уравнения вида (1) возникают при применении плавных разностных схем для решения параболических и гиперболических уравнений в частных производных; когда диагональное преобладание есть, тогда не надо делать выбор ведущего элемента, обычный метод Гаусса будет устойчивым),
A₂, ..., A_N, B₁, ..., B_N-1 - M х M матрицы;
Y₁,..., Y_N, F₁,..., F_N-1 - M-мерные векторы.

Метод матричной прогонки (блочный метод Гаусса) для решения системы уравнений (1) состоит из прямого и обратного ходов.

Прямой ход - это приведение (1) к следующей блочно-двухдиагональной системе уравнений

где I - единичная M х M матрица,

Обратный ход - это решение системы (2):

Прямой ход реализуется с помощью вычислительных модулей 16_i, 17_i и 18_i и регистров 21_i.

В вычислительных модулях 16_i и 17_i осуществляется решение системы линейных алгебраических уравнений вида C • Z = W, где C - (M • M) - матрица; W - M • (M + 1) - матрица, т. е. выполняется матричная операция C^-1 • W на основе следующих рекуррентных соотношений:

Вычислительными модулями 18 и регистрами 21 реализуется матричная операция вида S = Q + P • Z, где S, Q и Z - M х (M + 1) - матрицы, P - (M х M) - матрица, следующими рекуррентными соотношениями:

Прямой ход нужен для того, чтобы найти U₁,..., U_N-1 и σ₁,...,σ_N. В соответствии с алгоритмом (3) эти матрицы находятся следующим образом:

где ^* - все равно
Обратный ход алгоритма реализуется вычислительными модулями 19_i, регистром 22 и группой элементов ИЛИ 25. Векторы Y_N = σ_N,σ_N-1,...,σ₁ и V_q = -U_N, - U_N-1,..., U₁ подаются в вычислительные модули из блока памяти 20. Вычислительные векторы Y_q+1 используются для вычисления Y_q.

Вычислительные модули 19 выполняют матричную операцию вида D = σ+XY, где X - (M х M) - матрица; D, σ и Y - векторы размера M, на основе следующих рекуррентных соотношений:

Рассмотрим работу вычислительных модулей и устройства.

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

где
A^j+M+2 и B^j+M+2 - значения соответственно на первом и втором управляющих выходах вычислительного модуля на (j + N + 2)-м такте;
α^j и β^j - значения соответственно на первом и втором управляющих входах вычислительного модуля на j - м такте,

где
F^j+1 - значения на первом информационном выходе вычислительного модуля на (j + 1)-м такте;
n = 0, 1, 2,..., - фиксированное число, определяемое алгоритмом,

где
f^j - значение на первом информационном входе вычислительного модуля на j - м такте,

где
C^j+1 - значение на втором информационном выходе вычислительного модуля на (j + 1)-м такте,

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

где A^j+2 и B^j+2 - значения соответственно на первом и втором управляющих входах вычислительного модуля на (j + 2)-м такте;
α^j и β^j - значения соответственно на первом и втором управляющих входах вычислительного модуля на j-м такте,

где
n = 0, 1, 2, ... , - фиксированное число, определяемое алгоритмом,
Pj1

= C^j-1,
где
C^j-1 - значение на втором информационном входе вычислительного модуля на (j - 1)-м такте,
Pj2 = f^j-1,
где
f^j-1 - значение на первом информационном входе вычислительного модуля на (j - 1)-м такте,

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

где
A^j+1 и B^j+1 - значения соответственно на первом и втором управляющих выходах вычислительного модуля на (j + 1)-м такте;
α^j и β - значения соответственно на первом и втором управляющих входах вычислительного модуля на j-м такте,
P^j+M+1= p^j,
где
P^j+M+1 - значение на втором информационном выходе вычислительного модуля на (j+M+1)-м такте;
p^j - значение на втором информационном входе вычислительного модуля на j-м такте,
Z^j+2 = Z^j,
где
Z^j+2 - значение на третьем информационном выходе вычислительного модуля на (j+2)-м такте,
Z^j - значение на третьем информационном входе вычислительного модуля на j-м такте,

где
Q^j+1 - значение на первом информационном выходе вычислительного модуля на (j+1)-м такте;
q^j - значение на первом информационном входе вычислительного модуля на j-м такте;
n = 0, 1, 2, ..., - параметр, определяемый алгоритмом,

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

где
D^j+1 и Y^j+1 - значения соответственно на первом и втором информационных выходах вычислительного модуля на (j+1)-м такте;
d^j, y^j и x^j - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на j-м такте.

Г^j+1 = γ^j,
где
Г^j+1 - значение на управляющем выходе вычислительного модуля на (j+1)-м такте,
γ^j - значение на управляющем входе вычислительного модуля на j-м такте.

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

На вход 1 подаются элементы C(1)ij

в моменты времени

На выходы 6 и 7 подаются управляющие сигналы α и β, значения которых определяются элементами V_ij (M х M) - матрицы в моменты времени

где
V_ij - элементы (M х M) - матрицы

На выход 2 подаются элементы b(q)ijи f(1)i в моменты времени

На выходы 8 и 9 подаются сигналы α и β, определяемые элементами V_ij (M х (M + 2) - матрицы

в моменты времени

После V_M,M+1-го элемента на следующем такте подается элемент α₃.
На выход 3 подаются элементы C(q)ijи f(q)i в моменты времени

На выход 4 подаются элементы -a(q)ik в моменты времени

На выходы 10 и 11 подаются сигналы α и β,, определяемые элементами V_ij (M х (M + 1) - матрицы

в момент времени

На информационный вход блока памяти 20 подаются элементы u(q)ij и g(q)i в моменты времени

В эти же моменты времени на вход 13 подается сигнал записи в память "Зп", по которому последовательно записываются в соответствующие ячейки памяти элементы u(q)ij и g(q)i.
Последний элемент q(N)i записывается на T = (M(MN+3N+M-1)-м такте.

На (T+1)-м такте подается на вход считывания блока памяти 20 сигнал считывания "Сч", при этом с выходов блока памяти 20 осуществляется считывание элементов g(q)i

и u(q)ij.
На вход 12 подаются сигналы γ = 0∨1 в моменты времени

На вход 5 подаются элементы Y(N)i = g(N)i в моменты времени

На информационный вход 140 вычислительного модуля 19₁ подаются элементы g(q)i с (M+1)-го выхода блока памяти 20 в моменты времени

С K-го выхода блока памяти 20 подаются элементы u(q)ik на вход 142 вычислительного модуля 19_K-го ( q = N-1, N-2,...,1) в моменты времени

На выходе 26 устройства формируются элементы q = N-1, N-2,...,1) в моменты времени

В табл. 1 - 8 для случая M = 2 и N = 3 приведены организация входного и выходного потоков данных, состояния регистров и значения на выходах умножителей, сумматоров и узлов вычисления обратной величины числа в соответствующих вычислительных модулях 16₁, 16₂, 17₁, 17₂, 18₁, 18₂, 19₁ и 19₂.

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов высокой производительности для решения систем линейных алгебраических уравнений с блочно-трехдиагональной матрицей методом матричной прогонки. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит M вычислительных модулей первого типа, М вычислительных модулей второго типа, М вычислительных модулей третьего типа, M вычислительных модулей четвертого типа, где M - размерность матриц, блок памяти, группу регистров, регистр и две группы элементов ИЛИ. В основу работу устройства положен систолический принцип обработки информации. 5 ил., 8 табл.

Устройство для решения систем линейных алгебраических уравнений, содержащее M вычислительных модулей первого типа, M вычислительных модулей второго типа, M вычислительных модулей третьего типа и M вычислительных модулей четвертого типа, где M - размерность матриц, причем каждый вычислительный модуль первого типа содержит сумматор, умножитель и узел вычисления обратной величины числа и каждый вычислительный модуль второго, третьего и четвертого типов содержит сумматор и умножитель, отличающееся тем, что в него введены блок памяти, группа регистров, регистр и две группы элементов ИЛИ, причем первый информационный вход устройства подключен к первым входам первой группы элементов ИЛИ, вторые входы которой подключены к первому информационному выходу первого вычислительного модуля третьего типа, а выход - к информационному входу первого вычислительного модуля первого типа, второй информационный вход устройства подключен к первым входам второй группы элементов ИЛИ, вторые входы которой подключены к выходу (M² - M + 1)-го регистра группы, а выход - к первому информационному входу первого вычислительного модуля второго типа, третий и четвертый информационные входы устройства подключены соответственно к первому и второму информационным входам M-го вычислительного модуля третьего типа, пятый информационный вход устройства подключен к первым входам третьей группы элементов ИЛИ, вторые входы которой подключены к выходу регистра, а выход - к второму информационному входу M-го вычислительного модуля четвертого типа, первый и второй управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого вычислительного модуля первого типа, первый информационный выход, первый и второй управляющие выходы i-го вычислительного модуля первого типа подключены соответственно к информационному входу, первому и второму управляющим входам (i + 1)-го вычислительного модуля первого типа, второй информационный выход i-го вычислительного модуля первого типа подключен к второму информационному входу i-го вычислительного модуля второго типа, третий и четвертый управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого вычислительного модуля второго типа, информационный выход, первый и второй управляющие выходы i-го вычислительного модуля второго типа подключены соответственно к информационному входу, первому и второму управляющим входам (i + 1)-го вычислительного модуля второго типа, информационный выход M-го вычислительного модуля второго типа подключен к информационному входу блока памяти и третьему информационному входу M-го вычислительного модуля третьего типа, пятый и шестой управляющие входы устройства подключены соответственно к первому и второму управляющим входам M-го вычислительного модуля третьего типа, первый, второй и третий информационные входы, первый и второй управляющие входы i-го вычислительного модуля третьего типа подключены соответственно к первому, второму и третьему информационным выходам, первому и второму управляющим выходам (i + 1)-го вычислительного модуля третьего типа, первый информационный выход первого вычислительного модуля третьего типа подключен к информационному входу первого регистра группы, информационный выход i-го регистра группы подключен к информационному входу (i + 1)-го регистра группы, седьмой и восьмой управляющие входы устройства подключены соответственно к входам записи и считывания блока памяти, i-й выход которого подключен к третьему информационному входу i-го вычислительного модуля четвертого типа, (M + 1)-й выход блока памяти подключен к первому информационному входу первого вычислительного модуля четвертого типа, управляющий вход которого подключен к девятому управляющему входу устройства, первый информационный выход, второй информационный вход и управляющий выход i-го вычислительного модуля четвертого типа подключены соответственно к первому информационному входу, второму информационному выходу и управляющему входу (i + 1)-го вычислительного модуля четвертого типа, первый информационный выход M-го вычислительного модуля четвертого типа подключен к информационному входу регистра, выход которого подключен к выходу устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, регистров и блока памяти, а также тем, что вычислительный модуль первого типа дополнительно содержит первый и второй регистры, группу регистров, первую и вторую группы триггеров, одиннадцать групп элементов И, пять элементов И, четыре группы элементов ИЛИ, два элемента ИЛИ, причем в нем информационный вход первого регистра является информационным входом вычислительного модуля, прямой выход первого регистра подключен к первым входам первой группы элементов И, первому входу сумматора и входу узла вычисления обратной величины числа, выход которого подключен к первым входам второй и третьей групп элементов И, инверсный выход первого регистра подключен к первым входам четвертой и восьмой групп элементов И, выход элементов И первой группы подключен к первым входам элементов ИЛИ первой группы, вторые входы которых подключены к выходу элементов И пятой группы, а выход - к первому входу умножителя, второй вход которого подключен к выходу первого регистра группы, а выход - к информационному входу второго регистра и первым входам элементов И шестой группы, выход которой подключен к второму входу сумматора, выход которого подключен к первым входам элементов И седьмой группы, синхровход вычислительного модуля является первым входом первого элемента И, выход которого подключен к синхровходу второго регистра, выход которого подключен к первым входам элементов И пятой и девятой групп, выход которой подключен к первым входам элементов ИЛИ второй группы, вторые входы которой подключены к выходу элементов И седьмой группы, а выход является первым информационным выходом вычислительного модуля, выход элементов И восьмой группы подключен к первым входам элементов ИЛИ третьей группы, вторые входы которых подключены к выходу элементов И второй группы, а выход - к информационному входу второго регистра группы, выход j-го регистра группы подключен к информационному входу (j + 1)-го регистра группы, M-го регистра группы подключен к информационному входу первого регистра группы, выход которого подключен к первым входам элементов И десятой и одиннадцатой групп, вторые входы которой подключены к выходу первого элемента ИЛИ, а выход - к третьим входам элементов ИЛИ третьей группы, выход второго элемента ИЛИ подключен к вторым входам элементов И десятой группы, выходы элементов И десятой, третьей и четвертой групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ четвертой группы, выход которой является вторым информационным выходом вычислительного модуля, первый и второй управляющие входы которого являются соответственно информационными входами первых триггеров первой и второй групп, выходы i-го триггера первой и второй групп подключены к информационному входу (i + 1)-го триггера соответственно первой и второй групп, выходы (M + 2)-го триггера первой и второй групп являются соответственно первым и вторым управляющими выходами вычислительного модуля, прямой выход первого триггера первой группы подключен к первым входам четвертого и пятого элементов И, а инверсный выход - к первым входам второго и третьего элементов И, прямой выход первого триггера второй группы подключен к вторым входам третьего и пятого элементов И, а инверсный выход - к вторым входам второго и четвертого элементов И, выход второго элемента И подключен к вторым входам элементов И второй и третьей групп, выход третьего элемента И подключен к вторым входам элементов И восьмой и четвертой групп, выход четвертого элемента И подключен к вторым входам элементов И девятой группы, первого элемента И и первым входам первого и второго элементов ИЛИ, выход пятого элемента И подключен к вторым входам элементов И пятой, шестой и седьмой групп и вторым входам первого и второго элементов ИЛИ, первый вход первого элемента И подключен к синхровходам первого регистра, регистров группы и триггеров первой и второй групп, а также тем, что вычислительный модуль второго типа дополнительно содержит три регистра, группу регистров, первую и вторую группы триггеров, девять групп элементов И, пять элементов И, четыре группы элементов ИЛИ и девять элементов ИЛИ, причем в нем первый информационный вход первого регистра является информационным входом вычислительного модуля, выход первого регистра подключен к первым входам элементов И первой и второй групп, второй информационный вход вычислительного модуля подключен к информационному входу второго регистра, выход которого подключен к первым входам элементов И третьей и четвертой групп, выход первого регистра группы подключен к первым входам элементов И пятой группы, выход третьего регистра подключен к первым входам элементов И шестой и седьмой групп, выход сумматора подключен к первым входам элементов И восьмой группы, выходы первого и второго элементов ИЛИ подключены к вторым входам соответственно элементов И первой и шестой групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ первой группы, выход которой подключен к первому входу умножителя, выход которого подключен к первому входу сумматора и информационному входу третьего регистра, синхровход которого подключен к выходу пятого элемента И, выход третьего элемента ИЛИ подключен к вторым входам элементов И второй группы, выход которой подключен к второму входу сумматора, выходы четвертого и пятого элементов ИЛИ подключены к вторым входам соответственно элементов И третьей и пятой групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ второй группы, выход которой подключен к второму входу умножителя, выход шестого элемента ИЛИ подключен к первым входам элементов И девятой группы, выход которой подключен к первым входам элементов ИЛИ третьей группы, вторые входы которой подключены к выходу элементов И четвертой группы, вторые входы которых подключены к выходу седьмого элемента ИЛИ, выход элементов ИЛИ третьей группы подключен к информационному входу второго регистра группы, выход j-го регистра группы подключен к информационному входу (j + 1)-го регистра группы, выход M-го регистра группы подключен к информационному входу первого регистра группы, выход которого подключен к вторым входам элементов И девятой группы, выходы восьмого и девятого элементов ИЛИ подключены к вторым входам соответственно элементов И седьмой и восьмой групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ четвертой группы, выход которой является информационным выходом вычислительного модуля, первый и второй управляющие входы которого являются информационными входами первых триггеров соответственно первой и второй групп, выходы первых триггеров первой и второй групп подключены соответственно к информационным входам вторых триггеров первой и второй групп, выходы которых являются соответственно первым и вторым управляющими выходами вычислительного модуля, прямой выход первого триггера первой группы подключен к первым входам третьего и четвертого элементов И, а инверсный выход - к первым входам первого и второго элементов И, прямой выход первого триггера второй группы подключен к вторым входам второго и четвертого элементов И, а инверсный выход - к вторым входам первого и третьего элементов И, выход первого элемента И подключен к первым входам пятого элемента И, первого, четвертого, седьмого и восьмого элементов ИЛИ, выход второго элемента И подключен к первым входам второго, третьего и девятого элементов ИЛИ и к вторым входам четвертого и седьмого элементов ИЛИ, выход третьего элемента И подключен к первым входам пятого и шестого элементов ИЛИ и к вторым входам пятого элемента И, первого и восьмого элементов ИЛИ, выход четвертого элемента И подключен к вторым входам второго, третьего, пятого, шестого и девятого элементов ИЛИ, синхровход вычислительного модуля является синхровходом первого регистра и подключен к синхровходам второго регистра, регистров группы и триггеров первой и второй групп, а также тем, что вычислительный модуль третьего типа дополнительно содержит четыре регистра, две группы регистров, два триггера, две группы элементов И, пять элементов И, группу элементов ИЛИ и три элемента ИЛИ, причем в нем информационный вход первого регистра является первым информационным входом вычислительного модуля, выход первого регистра подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, а выход - к первому информационному выходу вычислительного модуля, второй информационный вход которого подключен к первым входам элементов И первой группы и информационному входу первого регистра первой группы, выход i-го регистра первой группы подключен к информационному входу (i + 1)-го регистра первой группы, выход (M + 1)-го регистра первой группы является вторым информационным выходом вычислительного модуля, выходы первого и второго элементов ИЛИ подключены к вторым входам элементов И соответственно первой и второй групп, выходы которых подключены соответственно к первым и вторым входам группы элементов ИЛИ, выход которой подключен к информационному входу первого регистра второй группы, выход i-го регистра второй группы подключен к информационному входу (i + 1)-го регистра второй группы, выход M-го регистра второй группы подключен к первым входам элементов И второй группы, выход первого регистра второй группы подключен к первому входу умножителя, второй вход которого подключен к выходу второго регистра, синхровход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ, а второй вход является синхровходом вычислительного модуля, третий информационный вход которого является информационным входом второго, третьего регистров, выход третьего регистра подключен к информационному входу четвертого регистра, выход которого является третьим информационным выходом вычислительного модуля, первый и второй управляющие входы вычислительного модуля являются соответственно информационными входами первого и второго триггеров, выходы которых подключены соответственно к первому и второму управляющим выходам вычислительного модуля, прямой выход первого триггера подключен к первым входам четвертого и пятого элементов И, а инверсный выход - к первым входам второго и третьего элементов И, прямой выход второго триггера подключен к вторым входам третьего и пятого элементов И, а инверсный выход - к вторым входам второго и четвертого элементов И, выход второго элемента И подключен к первым входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен к второму входу первого элемента ИЛИ, выход четвертого элемента И подключен к вторым входам второго и третьего элементов ИЛИ, выход пятого элемента И подключен к первому входу второго элемента И, синхровход вычислительного модуля подключен к синхровходам регистров первой и второй групп, первого, третьего и четвертого регистров, первого и второго триггеров, а также тем, что вычислительный модуль четвертого типа дополнительно содержит пять регистров, триггер, две группы элементов И и группу элементов ИЛИ, причем в нем информационный вход первого регистра является первым информационным входом вычислительного модуля, выход первого регистра подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, а выход является первым информационным выходом вычислительного модуля, информационный вход второго регистра является вторым информационным входом вычислительного модуля, выход второго регистра подключен к первым входам элементов И первой группы и является вторым информационным выходом вычислительного модуля, информационный вход третьего регистра является третьим информационным входом вычислительного модуля, выход третьего регистра подключен к первому входу умножителя, второй вход которого подключен к выходу четвертого регистра, выход элементов И первой группы подключен к первым входам группы элементов ИЛИ, вторые входы которой подключены к выходу элементов И второй группы, а выход - к информационному входу четвертого регистра, выход которого подключен к информационному входу пятого регистра, выход которого подключен к первым входам элементов И второй группы, вторые входы которой подключены к первому выходу триггера, инверсный выход которого подключен к вторым входам элементов И первой группы, информационный вход триггера является управляющим входом вычислительного модуля, выход триггера является управляющим выходом вычислительного модуля, синхровход триггера является синхровходом вычислительного модуля.