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

 

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

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

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

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

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

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

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

Поставленная цель достигается тем, что устройство для решения систем линейных алгебраических уравнений содержит M вычислительных модулей 16 первого типа, M вычислительных модулей 17 второго типа, M вычислительных модулей 18 третьего типа, M вычислительных модулей 19 четвертого типа, где M - размерность матриц, блок памяти 20, группу регистров 21, регистр 22 и три группы элементов ИЛИ 23, 24 и 25, причем первый 1 информационный вход устройства подключен к первым входам перовой 23 группы элементов ИЛИ, вторые входы которой подключены к первому информационному выходу первого 181 вычислительного модуля третьего типа, а выход - к информационному входу первого 161 вычислительного модуля первого типа, второй 2 информационный вход устройства подключен к первым входам второй 24 группы элементов ИЛИ, вторые входы которой подключены к выходу 21(M2-M+1)-гo регистра группы, а выход - к первому информационному входу первого 171 вычислительного модуля второго типа, третий 3 и четвертый 4 информационные входы устройства подключены соответственно к первому и второму информационным входам 18M-го вычислительного модуля третьего типа, пятый 5 информационный вход устройства подключен к первым входам третьей 25 группы элементов ИЛИ, вторые входы которой подключены к выходу регистра 22, а выход - к второму информационному входу 19M-го вычислительного модуля четвертого типа, первый 6 и второй 7 управляющие входы устройства подключены к первому и второму управляющим входам первого 161 вычислительного модуля первого типа, первый информационный выход, первой и второй управляющие выходы 16i-го вычислительного модуля первого типа подключены соответственно к информационному входу, первому и второму управляющим входам 16(i+1)-го вычислительного модуля первого типа, второй информационный выход 16i-го вычислительного модуля первого типа подключен к второму информационному входу 17i-го вычислительного модуля второго типа, третий 8 и четвертый 9 управляющие входы устройства подключены соответственно к первому и второму управляющим входам первого 171 вычислительного модуля второго типа, информационный выход, первый и второй управляющие выходы 17i-го вычислительного модуля второго типа подключены соответственно к информационному входу, первому и второму управляющим входам 17(i+1)-го вычислительного модуля второго типа, информационный выход 17M-го вычислительного модуля второго типа подключен к информационному входу блока памяти 20 и третьему информационному входу 18M-го вычислительного модуля третьего типа, пятый 10 и шестой 11 управляющие входы устройства подключены соответственно к первому и второму управляющим входам18M-го вычислительного модуля третьего типа, первый, второй и третий информационные входы, первый и второй управляющие входы 18i-го вычислительного модуля третьего типа подключены соответственно к первому, второму и третьему информационным выходам, первому и второму управляющим выходам 18 (i+1)-го вычислительного модуля третьего типа, первый информационный выход первого 181 вычислительного модуля третьего типа подключен к информационному входу первого 211 регистра группы, информационный выход 21i-го регистра группы подключен к информационному входу 21i+1-го регистра группы, седьмой 12 и восьмой 13 управляющие входы устройства подключены соответственно к входам записи и считывания блока памяти 20, i-й выход которого подключен к третьему информационному входу 19i-го вычислительного модуля четвертого типа, (M+1)-й выход блока памяти 20 подключен к первому информационному входу первого 191 вычислительного модуля четвертого типа, управляющий вход которого подключен к девятому 14 управляющему входу устройства, первый информационный выход, второй информационный вход и управляющий выход 19i-го вычислительного модуля четвертого типа подключены соответственно к первому информационному входу, второму информационному выходу и управляющему входу 19(i+1)-го вычислительного модуля четвертого типа, первый информационный выход 19М-го вычислительного модуля четвертого типа подключен к информационному входу регистра 22, выход которого подключен к выходу 26 устройства, синхровход 15 которого подключен к синхровходам всех вычислительных модулей, регистров и блока памяти 20, при этом вычислительный модуль первого 16 типа содержит сумматор 30, умножитель 31, узел вычисления обратной величины числа 32, первый 33 и второй 34 регистры, группу регистров 35i , первую 36i и вторую 37i группы триггеров, одиннадцать групп элементов И 38 - 48, пять элементов И 49 - 53, четыре группы элементов ИЛИ 54 - 57, два элемента ИЛИ 58 и 59, причем информационный вход 27 подключен к информационному входу первого 33 регистра, прямой выход которого подключен к первым входам первой 41 группы элементов И, первому входу сумматора 30 и входу узла вычисления обратной величины числа 32, выход которого подключен к первым входам второй 43 и третьей 47 групп элементов И, инверсный выход первого 33 регистра подключен к первым входам четвертой 48 и восьмой 40 группы элементов И, выход элементов И первой 41 группы подключен к первым входам элементов ИЛИ первой 54 группы, вторые входы которых подключены к выходу элементов И пятой 38 группы, а выход - к первому входу умножителя 31, второй вход которого подключен к выходу первого 351 регистра группы, а выход - к информационному входу второго 34 регистра и первым входам элементов И шестой 42 группы, выход которой подключен к второму входу сумматора 30, выход которого подключен к первым входам элементов И седьмой 44 группы, синхровход 64 вычислительного модуля подключен к первому входу первого 53 элемента И, выход которого подключен к синхровходу второго 34 регистра, выход которого подключен к первым входам элементов И пятой 38 и девятой 39 групп, выход которой подключен к первым входам элементов ИЛИ второй 55 группы, вторые входы которой подключены к выходу элементов И седьмой 44 группы, а выход - к первому 60 информационному выходу вычислительного модуля, выход элементов И восьмой 40 группы подключен к первым входам элементов ИЛИ третьей 56 группы, вторые входы которых подключены к выходу элементов И второй 43 группы, а выход - к информационному входу второго 352 регистра группы, выход 35i-го регистра группы подключен к информационному входу 35(i+1)-го регистра группы, выход 35M-го регистра группы подключен к информационному входу первого 351 регистра группы, выход которого подключен к первым входам элементов И десятой 46 и одиннадцатой 45 групп, вторые входы которой подключены к выходу первого 58 элемента ИЛИ, а выход - к третьим входам элементов ИЛИ третьей 56 группы, выход второго 59 элемента ИЛИ подключен к вторым входам элементов И десятой 46 группы, выходы элементов И десятой 46, третьей 47 и четвертой 48 групп подключены соответственно к первым, вторым и третьим входам элементов ИЛИ четвертой 57 группы, выход которой подключен к второму 61 информационному выходу вычислительного модуля, первый 28 и второй 29 управляющие входы которого подключены соответственно к информационным входам первых триггеров первой 361 и второй 371 групп, выходы i-го триггера первой 36 и второй 37 групп подключены к информационному входу (i+1)-го триггера соответственно первой 36 и второй 37 групп, выходы (M + 2)-го триггера первой 36 и второй 37 групп подключены соответственно к первому 62 и второму 63 управляющим выходам вычислительного модуля, прямой выход первого 361 триггера первой группы подключен к первым входам четвертого 51 и пятого 52 элементов И, а инверсный выход - к первым входам второго 49 и третьего 50 элементов И, прямой выход первого 371 триггера второй группы подключен к вторым входам триггера 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, группу регистров 75i , первую 76i и вторую 77i группы триггеров, девять групп элементов И 78 - 86, пять элементов И 87 - 91, четыре группы элементов ИЛИ 92 - 95 и девять элементов ИЛИ 96 - 104, причем первый 65 информационный вход вычислительного модуля подключен к информационному входу первого 72 регистра, выход которого подключен к первым входам элементов И первой 79 и второй 82, групп, второй 66 информационный вход вычислительного модуля подключен к информационному входу второго 74 регистра, выход которого подключен к первым входам элементов И третьей 78 и четвертой 83 групп, выход первого 751 регистра группы подключен к первым входам элементов И пятой 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 группы подключен к информационному входу второго 752 регистра группы, выход 75i-го регистра группы подключен к информационному входу 75(i+1)-го регистра группы, выход 75M-го регистра группы подключен к информационному входу первого 751 регистра группы, выход которого подключен к вторым входам элементов И девятой 84 группы, выходы восьмого 103 и девятого 104 элементов ИЛИ подключены к вторым входам соответственно элементов И седьмой 85 и восьмой 86 групп, выходы которых подключены соответственно к первым и вторым входам элементов ИЛИ четвертой 95 группы, выход которой подключен к информационному 105 выходу вычислительного модуля, первый 68 и второй 69 управляющие входы которого подключены к информационным входам первых триггеров соответственно первой 761 и второй 771 групп, выходы первых триггеров первой 761 и второй 771 групп подключены к информационным входам вторых триггеров соответственно первой 762 и второй 772 групп, выходы которых подключены соответственно к первому 106 и второму 107 управляющим выходам вычислительного модуля, прямой выход первого 761 триггера первой группы подключен к первым входам третьего 89 и четвертого 90 элементов И, а инверсный выход - к первым входам первого 87 и второго 88 элементов И, прямой выход первого 771 триггера второй группы подключен к вторым входам второго 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, две группы регистров 120i и 121j , два триггера 122 и 123, две группы элементов И 124 и 125, пять элементов И 126 - 130, группу элементов ИЛИ 131 и три элемента ИЛИ 132 - 134, причем первый 110 информационный вход вычислительного модуля подключен к информационному входу первого 119 регистра, выход которого подключен к первому входу сумматора 114, второй вход которого подключен к выходу умножителя 115, а выход - к первому 137 информационному выходу вычислительного модуля, второй 108 информационный вход которого подключен к первым входам элементов И первой 124 группы и информационному входу первого 1201 регистра первой группы выход 120i-го регистра первой группы подключен к информационному входу 120(i+1)-го регистра первой группы, выход 120(M+1)-го регистра первой группы подключен к второму 135 информационному выходу вычислительного модуля, выходы первого 132 и второго 133 элементов ИЛИ подключены к вторым входам элементов И соответственно первой 124 и второй 125 групп, выходы которых подключены соответственно к первым и вторым входам группы элементов ИЛИ 131, выход которой подключен к информационному входу первого 1211 регистра второй группы, выход 121i-го регистра второй группы подключен к информационному входу 121(i+1)-го регистра второй группы, выход 121M-го регистра второй группы подключен к первым входам элементов И второй 125 группы, выход первого 1211 регистра второй группы подключен к первому входу умножителя 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, первые 16i вторые 17i третьи 18i и 19i четвертые вычислительные модули, блок памяти 20, группу регистров 21i , регистр 22, первую 23, вторую 24 и третью 25 группы элементов ИЛИ и выход 26.

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

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

Вычислительный модуль третьего типа содержит первый 110, второй 108 и третий 109 информационные входы, первый 111 и второй 112 управляющие входы, синхровход 113, сумматор 114, умножитель 115, регистры 116 - 119, первую 120i и вторую 121i группы регистров, первый 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.

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

Пусть дана система линейных алгебраических уравнений где C1, . . . , CN - M х M плотные матрицы с диагональным преобладанием (диагональное преобладание на практике часто есть, например, когда уравнения вида (1) возникают при применении плавных разностных схем для решения параболических и гиперболических уравнений в частных производных; когда диагональное преобладание есть, тогда не надо делать выбор ведущего элемента, обычный метод Гаусса будет устойчивым), A2, ..., AN, B1, ..., BN-1 - M х M матрицы; Y1,..., YN, F1,..., FN-1 - M-мерные векторы.

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

Прямой ход - это приведение (1) к следующей блочно-двухдиагональной системе уравнений где I - единичная M х M матрица, Обратный ход - это решение системы (2):

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

В вычислительных модулях 16i и 17i осуществляется решение системы линейных алгебраических уравнений вида 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) - матрица, следующими рекуррентными соотношениями:

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

где * - все равно
Обратный ход алгоритма реализуется вычислительными модулями 19i , регистром 22 и группой элементов ИЛИ 25. Векторы YN = N,N-1,...,1 и Vq = -UN, - UN-1,..., U1 подаются в вычислительные модули из блока памяти 20. Вычислительные векторы Yq+1 используются для вычисления Yq.

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

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

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

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

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

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

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

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

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

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

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

где
Aj+1 и Bj+1 - значения соответственно на первом и втором управляющих выходах вычислительного модуля на (j + 1)-м такте;
j и - значения соответственно на первом и втором управляющих входах вычислительного модуля на j-м такте,
Pj+M+1= pj,
где
Pj+M+1 - значение на втором информационном выходе вычислительного модуля на (j+M+1)-м такте;
pj - значение на втором информационном входе вычислительного модуля на j-м такте,
Zj+2 = Zj,
где
Zj+2 - значение на третьем информационном выходе вычислительного модуля на (j+2)-м такте,
Zj - значение на третьем информационном входе вычислительного модуля на j-м такте,

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

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

где
Dj+1 и Yj+1 - значения соответственно на первом и втором информационных выходах вычислительного модуля на (j+1)-м такте;
dj, yj и xj - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на j-м такте.

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

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

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

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

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

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

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

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

После VM, M+1-го элемента на следующем такте подается элемент 3.
На выход 3 подаются элементы C(qij)и f(iq) в моменты времени

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

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

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

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

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

На (T+1)-м такте подается на вход считывания блока памяти 20 сигнал считывания "Сч", при этом с выходов блока памяти 20 осуществляется считывание элементов g(iq) и u(qij).
На вход 12 подаются сигналы = 01 в моменты времени

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

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

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

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

В табл. 1 - 8 для случая M = 2 и N = 3 приведены организация входного и выходного потоков данных, состояния регистров и значения на выходах умножителей, сумматоров и узлов вычисления обратной величины числа в соответствующих вычислительных модулях 161, 162, 171, 172, 181, 182, 191 и 192.


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

Устройство для решения систем линейных алгебраических уравнений, содержащее M вычислительных модулей первого типа, M вычислительных модулей второго типа, M вычислительных модулей третьего типа и M вычислительных модулей четвертого типа, где M - размерность матриц, причем каждый вычислительный модуль первого типа содержит сумматор, умножитель и узел вычисления обратной величины числа и каждый вычислительный модуль второго, третьего и четвертого типов содержит сумматор и умножитель, отличающееся тем, что в него введены блок памяти, группа регистров, регистр и две группы элементов ИЛИ, причем первый информационный вход устройства подключен к первым входам первой группы элементов ИЛИ, вторые входы которой подключены к первому информационному выходу первого вычислительного модуля третьего типа, а выход - к информационному входу первого вычислительного модуля первого типа, второй информационный вход устройства подключен к первым входам второй группы элементов ИЛИ, вторые входы которой подключены к выходу (M2 - 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-го регистра второй группы подключен к первым входам элементов И второй группы, выход первого регистра второй группы подключен к первому входу умножителя, второй вход которого подключен к выходу второго регистра, синхровход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ, а второй вход является синхровходом вычислительного модуля, третий информационный вход которого является информационным входом второго, третьего регистров, выход третьего регистра подключен к информационному входу четвертого регистра, выход которого является третьим информационным выходом вычислительного модуля, первый и второй управляющие входы вычислительного модуля являются соответственно информационными входами первого и второго триггеров, выходы которых подключены соответственно к первому и второму управляющим выходам вычислительного модуля, прямой выход первого триггера подключен к первым входам четвертого и пятого элементов И, а инверсный выход - к первым входам второго и третьего элементов И, прямой выход второго триггера подключен к вторым входам третьего и пятого элементов И, а инверсный выход - к вторым входам второго и четвертого элементов И, выход второго элемента И подключен к первым входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен к второму входу первого элемента ИЛИ, выход четвертого элемента И подключен к вторым входам второго и третьего элементов ИЛИ, выход пятого элемента И подключен к первому входу второго элемента И, синхровход вычислительного модуля подключен к синхровходам регистров первой и второй групп, первого, третьего и четвертого регистров, первого и второго триггеров, а также тем, что вычислительный модуль четвертого типа дополнительно содержит пять регистров, триггер, две группы элементов И и группу элементов ИЛИ, причем в нем информационный вход первого регистра является первым информационным входом вычислительного модуля, выход первого регистра подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, а выход является первым информационным выходом вычислительного модуля, информационный вход второго регистра является вторым информационным входом вычислительного модуля, выход второго регистра подключен к первым входам элементов И первой группы и является вторым информационным выходом вычислительного модуля, информационный вход третьего регистра является третьим информационным входом вычислительного модуля, выход третьего регистра подключен к первому входу умножителя, второй вход которого подключен к выходу четвертого регистра, выход элементов И первой группы подключен к первым входам группы элементов ИЛИ, вторые входы которой подключены к выходу элементов И второй группы, а выход - к информационному входу четвертого регистра, выход которого подключен к информационному входу пятого регистра, выход которого подключен к первым входам элементов И второй группы, вторые входы которой подключены к первому выходу триггера, инверсный выход которого подключен к вторым входам элементов И первой группы, информационный вход триггера является управляющим входом вычислительного модуля, выход триггера является управляющим выходом вычислительного модуля, синхровход триггера является синхровходом вычислительного модуля.

РИСУНКИ

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



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

Изобретение относится к контрольно-измерительной технике

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

Изобретение относится к способу и устройству для изменения размера шрифта сообщения в терминале мобильной связи

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

Изобретение относится к добыче нефти и газа с применением компьютерного моделирования. Техническим результатом является повышение эксплуатации месторождения. Предложен способ определения множества значений в промысловом объекте, реализуемый с использованием компьютера, и включает этапы, на которых осуществляют: получение компьютерной системой модели данных, представляющей коллектор и каждый скважинный ствол, причем модель содержит один или более узлов на указанном промысловом объекте, а узлы включают один или более наборов узлов, при этом каждый набор содержит единичный узел или множество соединенных друг с другом узлов, причем по меньшей мере один узел в каждом наборе находится в скважинном стволе; получение компьютерной системой системы линейных алгебраических уравнений, устанавливающих взаимосвязь между указанными значениями, представленными в уравнениях в качестве переменных, причем указанные значения включают давление для каждого узла в каждом наборе и включают значения расхода потока, определенные расходами потока в узлы или из узлов, в каждом наборе, и для каждого узла уравнения содержат набор из одного или более уравнений со значениями в узле, при этом для по меньшей мере одного узла в каждом наборе узлов набор из одного или более уравнений содержит по меньшей мере одно уравнение с давлением в узле и с одним или более значениями расхода потока в узле; выполнение компьютерной системой линейного преобразования системы уравнений, причем линейное преобразование включает линейное преобразование уравнений каждого набора уравнений для исключения по меньшей мере одного значения расхода потока из по меньшей мере одного уравнения в каждом наборе уравнений и при этом линейное преобразование обеспечивает преобразованную систему уравнений; и решение компьютерной системой преобразованной системы уравнений для указанных значений. 10 н. и 10 з.п. ф-лы, 19 ил.

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