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

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

Известны устройства для решения уравнений в частных производных, состоящие из центрального устройства управления и сеткооднородных и одинаково соединенных модулей, каждый из которых имеет арифметическое устройство, выполняющее последовательно разряд за разрядом арифметические и логические операции, и двух блоков памяти емкостью по 2048 двоичных единиц каждый (Евреинов Э.В. Косарев Ю.Г. Однородные вычислительные системы высокой производительности. Новосибирск: Наука, 1966, с. 38-41, рис. 7).

Однако это устройство имеет большой объем оборудования, поскольку представляет собой вычислительную систему, состоящую из отдельных вычислительных машин со своим арифметическим устройством и блоками памяти.

Известно также устройство для решения задач математической физики, представляющее собой цифровую сетку, содержащую в узлах n-разрядные комбинационные сумматоры на 7n внешних входов [1]
Недостатком этого устройства является неустойчивость решения задач математической физики из-за наличия положительных обратных связей, так как каждый n-разрядный сумматор, находящийся в узлах сеточной области, соединен своими входными и выходными полюсами непосредственно с шестью соседними сумматорами.

Наиболее близким к изобретению по технической сущности является устройство для решения трехмерных задач математической физики, содержащее блоки суммирования, блок ввода исходной информации, блок вывода, регистра адреса, блок вычисления коэффициента, блок сравнения и блок управления [2]
Прототип имеет большое количество блоков суммирования в качестве узловых элементов цифровой сетки, так как в нем реализуется простой алгоритм, который аппроксимирует исходный дифференциальный оператор Лапласа с погрешностью до h², где h шаг дискретизации.

Для получения решения в области единичного куба с точностью δ порядка h² необходимо иметь сетку, содержащую N m x m x m 1/h³узловых элементов, при этом количество итераций для получения решения методом простой итерации пропорционально величине 1/h³ и при h << 1 будет большим. Таким образом, недостатками прототипа являются большие аппаратурные затраты и низкое быстродействие.

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

На фиг. 1 представлена блок-схема предлагаемого устройства; на фиг.2 приведено расположение соседних блоков суммирования 1 в объемной матрице, для узлов которой введены следующие обозначения: Ц центральный; Д диагональный, У угловой, для того, чтобы различать типы связей блока суммирования, расположенного в центре куба объемной матрицы; на фиг.3 схема блока суммирования.

Устройство содержит объемную матрицу блоков 1 суммирования, блок 2 ввода информации, блок 3 вывода информации, регистры 4-6 адреса, блок 7 сравнения и блок 8 управления.

Блок 1 суммирования содержит многовходовый сумматор 9, регистр 10, элемент И 11, группу 12 элементов И, четыре группы элементов 13-16 задержки, информационные входы 17-20, управляющие входы 21-23, параллельные выходы 24 и последовательный выход 25 (фиг.3).

Объемная матрица блоков 1 суммирования состоит из I слоев по J x K блоков 1 суммирования. Выходы кодов правых частей граничных условий блока 2 ввода информации соединены с первой группой информационных входов всех блоков 1 суммирования и второй группой информационных входов периферийных блоков 1 суммирования объемной матрицы соответственно. Параллельные выходы блоков 1 суммирования соединены с информационными входами блока 3 вывода информации и блока 7 сравнения. Вторая группа информационных входов внутренних (1< i< I, 1< j <I, 1<k <K) блоков 1 суммирования объемной матрицы соединена с последовательными выходами четырех соседних (i, j ± 1, k; i, j, k ±1) в данном i-ом слое и двух центральных в соседних слоях (i ±1, j, k) объемной матрицы блоков 1 суммирования (эти узлы объемной матрицы на фиг.2 обозначены как Ц центральные).

Третья группа информационных входов внутренних (i, j, k) блоков 1 суммирования i-го слоя соединена с последовательными выходами двенадцати ближайших по диагоналям (i, j ±1, k ±1; i 1, j, k ±1; i + 1, j ±1, k) в i-ом и двух соседних (i±1) слоях блоков 1 суммирования (на фиг.2 Д диагональные узлы).

Четвертая группа информационных входов внутренних (i, j, k) блоков 1 суммирования соединена с последовательными выходами восьми ближайших угловых (i ±1, j±1, k ±1) в двух соседних (i± 1) слоях блоков 1 суммирования (на фиг. 2 У угловые узлы). Первый, второй и третий выходы блока 8 управления соединены соответственно с управляющими входами блоков 2, 3 и 7 ввода информации, вывода информации и сравнения соответственно. Информационный вход блока 3 вывода информации соединен с объединенными параллельными выходами всех блоков 1 суммирования и информационным входом блока 7 сравнения. Выход блока 7 сравнения с входом блока 8 управления, четвертый, пятый и шестой выходы которого соединены соответственно с входами трех регистров 4, 5 и 6 адреса, выходы которых соединены с первым, вторым и третьим управляющими входами блоков 1 суммирования, четвертый и пятый управляющие входы которых соединены соответственно с седьмым и восьмым выходами блока 8 управления.

Выход многовходового сумматора 9 соединен с информационным входом регистра 10, параллельный выход которого соединен с первыми входами элементов И группы 12, выходы которых соединены с параллельными выходами 24 блока 1 суммирования. Последовательный выход регистра 10 соединен с первым входом элемента И 11, выход которого соединен с последовательным выходом 25 блока 1 суммирования. Управляющие входы 21-23 блока 1 суммирования соединены соответственно с вторыми, третьими и четвертым входами элементов И группы 12, управляющим входом регистра 10 и вторым входом элемента И 11. Первая группа информационных входов 17 блока 1 суммирования соединена с первой группой входов многовходового сумматора 9, вторая группа информационных входов 18 блока 1 суммирования соединена через элементы 13 задержки первой группы с второй группой входов многовходового сумматора 9 и входами элементов 14 задержки второй группы, выходы которой соединены с третьей группой входов многовходового сумматора 9 и входами элементов 15 задержки третьей группы, выходы которых соединены с четвертой группой входов многовходового сумматора 9, пятая группа входов которого соединена с третьей группой информационных входов 19 блока 1 суммирования и входами элементов 16 задержки четвертой группы, выходы которых соединены с шестой группой входов многовходового сумматора 9, седьмая группа входов которого соединена с четвертой группой информационных входов 20 блока 1 суммирования.

Блок 7 управления имеет типовую структуру на базе генератора импульсов элементов И и элементов задержки. Он обеспечивает выдачу последовательности управляющих сигналов на:
входы блока 2 ввода для обеспечения ввода в блоки 1 суммирования кодов правых частей в течение n тактов;
вторые и третьи управляющие входы блоков 1 суммирования в течение соответственно (n+7) и n тактов;
на входы регистров 4, 5 и 6 адреса для выбора блоков 1 суммирования и считывания из них результатов для выдачи в блок анализа или блок 3 вывода;
на вход блока 7 сравнения для сравнения результатов вычислений на двух последовательных итерациях,
на управляющий вход блока 3 вывода для выдачи результата решения.

Устройство работает следующим образом.

Под воздействием сигналов с выхода блока 8 управления, блок 2 ввода выдает в последовательном коде, начиная с младшего разряда, значения кодовых граничных условий на вторую группу информационных входов 18 внешних в объемной матрице (периферийных) блоков 1 суммирования и кодов правых частей в виде 60h²Fijk (для уравнения Пуассона) на первую группу информационных входов 17 блоков 1 суммирования, на вторую группу информационных входов 18 внутренних блоков 1 суммирования поступает последовательный код выходов 25 четырех соседних в данном слое i и двух центральных в соседних слоях (i ±1) блоков 1 суммирования. На третью группу информационных входов 19 блоков 1 суммирования поступают последовательные коды с выходов 25 двенадцати ближайших по диагонали в i-ом и двух соседних слоях (i±1) блоков 1 суммирования. На четвертую группу 20 информационных входов блоков 1 суммирования поступают последовательные коды чисел с выходов 25 восьми ближайших угловых в двух соседних слоях блоков 1 суммирования. Таким образом, в обозначениях узловых блоков 1 суммирования объемной матрицы, представленных на фиг.2, на вторую группу информационных входов 18 блока 1 суммирования поступают числа с выходов 25 шести блоков суммирования Ц- центральных, на третью группу информационных входов 19 с выходов двенадцати блоков суммирования Д диагональных и на четвертую группу входов 20 с выходов восьми блоков суммирования, обозначенных У угловых. На элементах 13-16 задержки коды чисел задерживаются на один разряд (один такт), так что числа, поступающие на входы 18, умножаются на коэффициент 14, а по входам 19 на коэффициент 3 (коды, поступающие на входы 19, передаются на пятую группу информационных входов многовходового сумматора 9 непосредственно и с задержкой на один такт на элемент 16, т.е. умноженные на 2 поступают на шестую группу информационных входов многовходового сумматора 9, а суммарный коэффициент равен 3). Многовходовый сумматор 9 блока 1 суммирования осуществляет суммирование каждого разряда всех чисел, поступающих на его входы, с запоминанием переносов в следующие разряды, и выдает результат на вход регистра 10, на котором производится сдвиг его содержимого на один разряд под управлением сигналов, поступающих на вход 22, выдача последовательного кода значения решения на предыдущей итерации (на первой итерации в регистре 10 содержится нулевой код) и запоминание результата вычислений на последующей итерации. По истечении n тактов выдача кода из регистра 10 через элемент И 11, управляемый сигналом по входу 23, прекращается (n-разрядный код из регистра 10 считан полностью) и в течение еще 7 тактов происходит обработка старших разрядов чисел, задержанных на элементах 13-16, и переносов в старшие разряды в многовходовом сумматоре 9, запись результата вычислений происходит как и прежде на регистре 10, который сдвигается в течение еще 7 тактов на 7 разрядов, т.е. результат вычислений на многовходовом сумматоре 9 записывается в регистр 10 с коэффициентом 1/128.

Таким образом, на (r+1)-ой итерации в регистре 10 внутреннего (i, j, k) блока 1 суммирования объемной матрицы фиксируется следующий результат вычислений:
U(r+1)i,j,k

= [-60h²Fijk+14(U(r)i,j_+1,k+U(r)i,j_-1,k+U⁽r)i,_j,k+1+U(r)i,j_,k-1+
+U(r)i+1_,j,k+U(r)i-1_,j,k +3(U(r)i,j_+1,k+1+U(r)i,j_-1,k+1+U(r)i,j_+1,k-1+U(r)i6j_-1,k-1+
+U(r)i+1_,j,k+1+U(r)i+1_,j-1,k+U(r)i+1_,j,k-1+U(r)i+1_,j+1,k+U(r)i-1_,j,k+1+
+U(r)i-1_,j-1,k+U(r)i-1_,j,k-1+U(r)i-1_,j+1,k)+U(r)i+1_,j+1,k+1+U(r)i+1_,j+1,k-1+
+U(r)i+1_,j-1,k+1+U(r)i+1_,j-1,k+1+U(r)i-1_,j+1,k+1+U(r)i-1_,j+1,k-1+U(r)i-1_,j-1,k+1+
+U(r)i-1_,j-1,k-1)] + +
+ h²Fijk
Эта формула аппроксимирует дифференциальный оператор исходного уравнения Лапласа с погрешностью 0(h⁸), что проверяется путем разложения дифференциального оператора в узлах объемной матрицы в ряд Тейлора и суммирование их с коэффициентами по вышеприведенной формуле.

Блок 8 управления устанавливает адреса переменных в регистры адреса 4, 5 и 6, которые выбирают соответствующие блоки 1 суммирования и считывают с регистров 10 информацию в блок 7 сравнения, в котором осуществляется сравнение значений решения на двух соседних по времени итерациях.

Последующие итерации осуществляются аналогично вышеописанному и, когда решения из двух следующих одна за другой итерациях отличаются на заданную малую величину, блок 7 сравнения выдает сигнал на блок 8 управления об окончании решения. С блока 8 управления через регистры 4-6 адреса поступает сигнал на первые управляющие входы блока 1 суммирования, при этом открываются элементы И группы 12, через которые результат решения выдается из регистра 10 на параллельные выходы 24 блока 1 суммирования и далее на вход блока 3 вывода.

По сравнению с прототипом в предлагаемом устройстве обеспечивается более высокая точность решения, поскольку погрешность аппроксимации трехмерного дифференциального оператора Лапласа в нем определяется восьмым порядком степени шага дискретизации (h⁸), а в прототипе вторым порядком (h²). Поскольку при реализации объемной цифровой сетки для решения трехмерного уравнения Лапласа необходимое количество узлов равно 1/h³, то данное предложение позволяет сократить аппаратурные затраты сетки за счет существенного уменьшения количества узловых блоков суммирования, поскольку шаг дискретизации для заданной точности может быть значительно увеличен по сравнению с вариантом использования в сетке узловых элементов прототипа. Так, например, для заданной точности δ 10^-8 шаг h для предлагаемого устройства равен 0,1, а для прототипа 10^-4, т.е. сетка при использовании прототипа содержит 10¹² узловых элементов, а для предлагаемого устройства 10³. Поскольку число итераций пропорционально квадрату числа узлов, то существенно повышается и быстродействие.

В качестве базового варианта можно рассмотреть решение задачи на любой универсальный ЭВМ. При этом базовое устройство значительно уступает предлагаемому по стоимости, аппаратурным затратам, быстродействию и другим параметрам.

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

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРЕХМЕРНЫХ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ, содержащее объемную матрицу блоков суммирования, состоящую из I слоев по I · K блоков суммирования в каждом слое, три регистра адреса, блок ввода информации, блок вывода информации, блок сравнения и блок управления, первый выход которого соединен с управляющим входом блока ввода информации, выходы кодов правых частей граничных условий которого соединены с первой группой информационных входов всех блоков суммирования и второй группой информационных входов периферийных блоков суммирования объемной матрицы соответственно, второй выход блока управления соединен с управляющим входом блока вывода информации, информационный вход которого соединен с объединенными параллельными выходами всех блоков суммирования, третий выход блока управления соединен с управляющим входом блока сравнения, информационный вход которого соединен с информационным входом блока вывода информации, выход которого подключен к входу блока управления, четвертый, пятый и шестой выходы которого соединены соответственно с входами трех регистров адреса, выходы которых соединены с первыми, вторыми и третьими управляющими входами блоков суммирования, четвертый и пятый управляющие входы которых соединены соответственно с седьмым и восьмым выходами блока управления, вторая группа информационных входов внутренних блоков суммирования объемной матрицы соединена с последовательными выходами четырех соседних в данном слое и двух центральных в соседних слоях объемной матрицы блоков суммирования, отличающееся тем, что третья группа информационных входов внутренних блоков суммирования i-го слоя соединена с последовательными выходами двенадцати ближайших по диагонали в i-м и двух соседних слоях блоков суммирования, а четвертая группа информационных входов внутренних блоков суммирования соединена с последовательными выходами восьми ближайших угловых в двух соседних слоях блоков суммирования, кроме того, блок суммирования содержит многовходовый сумматор, регистр, группу элементов И, элемент И и четыре группы элементов задержки, причем выход многовходового сумматора соединен с информационным входом регистра, параллельный выход которого соединен с первыми входами элементов И группы, выходы которых соединены с параллельными выходами блока суммирования, последовательный выход регистра соединен с первым входом элемента И, выход которого соединен с последовательным выходом блока суммирования, первый, второй, третий, чертвертый и пятый управляющие входы блока суммирования соединены соответственно с вторыми входами элементов И группы, управляющим входом регистра и вторым входом элемента И, первая группа информационных входов блока суммирования соединена с первой группой входов многовходового сумматора, вторая группа информационных входов блока суммирования соединена через элементы задержки первой группы с второй группой входом многовходового сумматора и входами элементов задержки второй группы, выходы которых соединены с третьей группой входов многовходового сумматора и входами элементов задержки третьей группы, выходы которых соединены с четвертой группой входов многовходового сумматора, пятая группа входов которого соединена с третьей группой информационных входов блока суммирования и входами элементов задержки чертвертой группы, выходы которых соединены с шестой группой входов многовходового сумматора, седьмая группа входов которого соединена с четвертой группой информационных входов блока суммирования.