Параллельное вычислительное устройство для решения разностных уравнений задач теории поля Советский патент 1980 года по МПК G06F17/12 

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

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

Недостатком этих устройств является низкое быстродействие. .

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

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

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

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

Эта цель достигаемся тем, что в

10 предлагаемом устройстве N арифметических блоков соединены в матрицу, первый, второй, третий, четвертый информационные входы (i,j)-ro арифметического блока соединены соответ15ственно с информационными выходами (1-1,J)-го, (i,j-l)-ro,(i+l,j)-ro (i,j+l)-ro арифметических блоков; пятый, шестой, седьмой и восьмой информсщионные входы - с информа20ционными выходами (i-2,j)-ro, (i,j-2)-ro, (i+2,j)-ro и (i,j+2)-ro арифметических блоков; девятый, десятый, одиннадцатый и двенадцатый информационные входы - с информа25ционными выходами (1-1, j-l)-ro (1+1, j-l)-ro, (1+1, j+l)-ro и (i-l,j+l)-ro арифметических блоков, причем в каждый арифметический блок введены дополнительно второй,тре30

тйй и четвертый регистры сдвига и дополнительный сумматор} первый, второй, третий, четвертый, пятый и шестой входы сумматора соединены соответственно с выходами первого, второго, третьего, четвертого, пятого и шестого элементов ИЛИ; первый, второй и третий входы первого элемента ИЛИ подключены соответственно через первый, пятый и девятый элементы И к первому, пятому и девятому входам арифметического блока первЫй, второй и третий входы второго элемента ИЛИ - через второй, шестой и десятый элементы И - ко второму, шесто и десятому информационным входам арифметического блока, первый, второй и третий входы третьего элемента ИЛИ - через третий, седьмой и одиннадцатый элементы И - к третьему, седьмому и одиннадцатому информационным входам арифметического блока, первый, второй и третий входы четвертого элемента ИЛИ - через четвертый, восьмой и двенадцатый элементы И - к четвертому, восьмому и двенадцатому информационным входам арифметического блока; выходы первого, второго, третьего, четвертого и пятого разрядов первого регистра сдвига подключены соответственно через тринадцатый, четырнадцатый, пятнадцатый, шестнадцатый и семнадцатый элементы И к четвертым входам первого, второго, третьего, четвертого элементов ИЛИ и к третьему входу пятого элемента ИЛИ, кроме того, второй и первый входы пятого элемента ИЛИ соединены через восемнадцатый и девятнадцатый элементы И соответственно с инверсными выходами второго и четвертого регистров сдвига, а первый и второй входы шестого элемента ИЛИ соединены через двадцать первый и двадцатый элементы И соответственно с прямым выходом второго регистра сдвига и с инверсным выходом третьего регистра сдвига; первый вход дополнительного сумматора соединен через двадцать второй элемент И с выходом сумматора, а второй вход дополнительного сумматора через двадцать третий элемент И - с инверсным выходом второго регистра сдвига, выход дополнительного сумматора - с управляющим выходом арифметического блока, а выход сумматора подключен через двадцать Четвертый элемент И ко входу первого регистра сдвига и через двадцать восьмой элемент И - к первому входу Седьмого элемента ИЛИ,прямой выход второго регистра сдвига подключен Через двадцать шестой элемент И ко входу четвертого регистра сдвига И через двадцать седьмой элемент И ко второму входу седьмого элемента ИЛИ, а третий вход седьмого элемента ИЛИ соединен через двадцать

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

с соответствующими управляющими входами арифметического блока.

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

Каждый арифметический блок

(фиг.2) содержит регистры сдвига 6-9, дополнительный сумматор 10, .сумматор 11, элементы 12-18 ИЛИ и элементы 19-47 И.

Работа устройства заключается в

аппаратной реализации решения разностных уравнений Пуансона:

-i,.i,..f

35 --,,.--,n,-,i,..,i

(1)

i,i -evuHj 4,о - ,о} Ц-.,W-H

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

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

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

О. - АУ в узлах с четными значения i+j.

И. - АУ в узлах с нечетными значениями i+j.

ft - АУ в узлах с четными i , j ,

1+четно.

для которых

IV,

ftj АУ в узлах с четными i,j.

i±i

нечетно.

для которых

2,

ь. J J Множество SI -51.,«Q.,, о

ет | УСтую сетку, множество «if-ч.-Vsi вспомогательную редкую сетку.

Перед началом вычислений в регистры сдвига 7 всех арифметических блоков засылаются значения правых частей разностных уравнений, а в регистры сдвига 6 граничных узлов значения граничных функций. Решение задачи делится на следую щие этапы: . А. Решение разностных уравнений на редкой сетке с помощью итерацион ного процесса: ,H-n.Uj, п и и h. 4 , i4i2,,j+2 ..).v{;., (2) j для upesi. t/ T i i ::;vc/ s:. ),i (з для (i,j). Б. Вычисление начальных приближе ний для узлов густой сетки с помощь интерполяции: .,,i,,.jH-2f,-.i) для (i,j) /л «f .,r.-,.i), ,5 ДЛЯ (i,j)6Sl. В. Решение разностных уравнений на густой сетке с помощью интерацио ного процесса: 1«.Х;-К,ХкЧгЧ Ж ) для (.i,j)esi,. .yj/- v, v,M . -4W .-f V i,j 4 V1-,ГЧ,, .j i.jj для (i,j)en. Г. Комбинация разностных решений узлов редкой сетки: .С. в. для (i,j) д. Вычисление точных значений для остальных узлов густой сетки с помощью интерполяции по формулам (4) и (5)„ Указанные вычисления выполняютс в параллельном вычислительном устройстве 2 следующим образом. А. В каждый из арифметических блоков 4 множества узлов Л подаются из блока управления 3 разрешаю щие сигналы на элементы 23-26 И. Этим обеспечиваются соединения, не обходимые для того, чтобы на первые четыре входа сумматора 11 поступали p...2,..j:.... i Ча Одновременно в эти арифмети ческие блоки подаются разрешающие сигналы на элементы 36 и 39 И, которые обеспечивают соответственно поступление учетверенных (например,предварительным сдвигом влево на два разряда) значений - с инверсного выхода регистра сдвига 6 и - с инверсного выхода регистра сдвига 7 на пятый и шестой входы сумматора 11. Кроме того, на элемент 40 И подается сигНал, разрешающий запись результата с выхода сумматора 11 на регистр сдвига 9. На элементы 42 И всех арифметических блоков множества узлов S1 подается сигнал, разрешающий регенерацию содержимого регистров сдвига 6. После этих подготовительных действий из блока управления 3 подается серия из Р импульсов сдвига (Р - разрядность переменных) на ре-гистры сдвига б всех арифметических блоков множества узлов ft и на регистры сдвига 6,7 и 9 всех арифметических .блоков множества узлов Si . В результате в каждом арифме-т тическом блоке множества узлов И. вычисляется и записывается в регистр сдвига 9 выражение, заключенное в скобки в формуле (2). Данное вычисление является первой фазой итерации. Затем начинается вторая фаза итерации. При этом блок управления 3 в каждом арифметическом блоке множества О. , снимает разрешающие сигналы со всех элементов И, работающих во время выполнения первой фазы,подает разрешающие сигнгшы на элементы 38 и 41 И и, кроме того, подает на элементы 31-35 И, сигналы, соответствующие значениям разрядов множителя -х ( U)- параметр релаксации). После этих подготовительных действий подается серия изР импульсов сдвига на регистры сдвига б и 9 всех арифметических блоков множества С. При этом на первые пять входов сумматора 11 подается (со сдвигом соответственно на один, два, три, четыре и пять разрядов) вычисленное в первой фазеВыражение (в скобке), причем поступление этих величин управляется значениями разрядов множителя -j- (О или i) . В результате на выходе- сумматора 11 образуется произведение скобки на множитель . Так как на шестой вход сумматора 11 через элемент 38 И поступает значение . с прямого вьлхода регистра сдвига бр то одновременно с вычислением указанного произведения происходит сложение этого произведения с переменной УД « Результат - новое значение переменной - (формула (2) через элементы 41 И, 18 ИЛИ поступает в регистр сдвига 6, замещая .его прежнее содержимое -

Вычисления по формуле (3) производятся аналогично, но при этом,, арифметические блоки множеств ft и

меняются ролями,

Проверка условия окончания итерационного процесса

9.

производится с помощью дополнительного сумматора 10. Если во время выполнения второй фазы итерации подать разрешающие сигналы на элементы 46 и 47 И, то на первый вход сумматора 10 будут поступать последовательнЬ (начиная с младшего) разряды Ц , а на второй - также последовательно, но в обратном коде, разряды 13 . Значит, на выходу сумматора 10 оёразуется разность -Uy.,-. При 2 - 2 условие окончания итерационного процесса (9) выполнится тода, когда старшие Р-г разрядов это разности равны нулю. Для проверки условия (9) подаются на элементы 46 и 47 И всех арифметических блоков данного множества разрешающие сигналы с задержкой на г тактов относительно начала второй фазы. Если сигналы на выходах 62 всех арифметических блоков данного множества нулевые, итерационный процесс окончен.

Полученные значения переменных и записываются в регистры сдвига 8, для этого в каждый арифметический блок множества i из блока управления 3 подается разрешающий сигнал на элемент +3 И и Р импульсов сдвига на регистры сдвига 6 и 8

Б. В каждый из арифметических блоков 4 множества ,/fl- подаются из блока управления 3 разрешающие сигналы на элементы 27-30 И. Одновременно в эти арифметические блоки подаются разрешающие сигналы на элементы 39 И и +1 И. Потом из блока управления 3 подаются Р имг пульсов сдвига на регистры сдвига

6всех арифметических блоков множества О. и на регистры сдвига 6 и

7множества , ( 51. , таким образом в каждом арифметическом блоке множества Sitj / О. вычисляется и записывается в регистры сдвига 6 выражение, заключенное в скобки в формуле (4).Затем выполняется деление

на 4 (например, путем сдвига вправо на два разряда) . В результате в „. регистрах сдвига 6 множества S1 /51 образуются начальные приближения

°,J-Далее начинается интерполяция

в узлах множества Л по формуле (5). Для этого в каждый арифметический блок данного множества подаются разрешающие сигналы на элементы 19-22 И, чтобы на первые четыре входа сумматора 11 поступали

переменные , и U,.,,U°,,,,, U ,,,. Одновременно в эти арифметические блоки подаются разрешающие сигналы на элемент 39 И, через который поступает с инверсного выхода регистра сдвига 7 на шестой вход сумматора 11. Сложение выполняется с помощью серии импульсов сдвига, подаваемых на регистры сдвига 6 множества 51 и регистры 6 и 7 мноQ жества Sl. После деления на 4 в регистрах 6 множества О. образуются начальные приближения и° : В. В каждый из арифметических блоков множества узлов подаются разрешающие сигналы на элементы 19-22 И для поступления переменных ,i.W.i-i.,j и ,,,, . Одновременно в эти арифметические блоки подаются разрешающие сигналы. на элементы И 36 и 39 (для подачи

0 переменных - 4vA и ,j ) и на элемент 40 И (для записи промежуточного результата на регистр 9) .,

Далее выполняются первая и вторая фазы итерации (этап А).

5 Результат - новое значение переменной (см. формулу (6)) - оказывается в регистре б.

Вычисления по формуле (7) производятся аналогично, но при этом

0 арифметические блоки множеств 5.;J и 51 меняются ролями.

На этом заканчивается выполнение одной итерации на густой сетке. Проверка условий окончания итерационного процесса производится так же, как описано выше (этап А). Если процесс не окончен, вычисления по формулам (6) и (7) повторяются (в противном случае устройство управп ления 3 переходит к выполнению этапа Г) .

Г. в каждый арифметический блок множества узлов О. подаются разрешающие сигналы на элементы 38, 37 и

- 40 И для поступления соответственно учетверенного (например, предварительным сдвигом влево на два разряда) значения с прямого выхода )егистра б на шестой вход сумматора 11, значения иЯ- - с инверсного

0 выхода регистра 8 на пятый вход сумматора 11 и записи результата с выхода сумматора 11 в регистр 9.

Затем подается серия из Р импульсов сдвига для вычисления и записи

5 в регистр 9 разности, заключенной в скобки в формуле (8). После этого блок управления 3 снижает разрешающие сигналы с элементов 38, 37 и 40 И, подает разрешающие сигнгшы на элемент 41 И и, кроме того, подает

на элементы 31-35 И сигналы, соответствующие значениям разрядов множителя 4,- Затем выполняется умножение так, как описано аыше (этап А).

5 В результате в регистре 6 АУ множества образуется комбинация разностных решений ,: в соответствии с формулой (8).

Д Вычисления выполняются так же, как было описано выше для этапа Б.

По окончании этапа Д в регистрах 6 всех арифметических блоков вычислительного устройства 2 находятся результирующие значения переменных UYJ , которые и составляют решение задачи.

Использование регистров сдвига с последовательным доступом и последовательных сумматоров существенно уменьшает стоимость арифметического блока 4. Кроме того, облегчается реализация параллельного вычислительного устройства 2, так как обмен информацией между арифметическими блоками производится последовательным кодом, что позволяет значительно уменьшить количество соединительных каналов. Это обстоятельство особенно важно при реализации арифметических блоков 4 в виде микропроцессоров на БИС, имеющих жесткие ограничения по числу вводов.

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

Параллельное вычислительное устройство для решения разностных уравнений задач теории поля/ содержащее блок управления и N арифметических блоков, каждый из которых содержит сумматор, регистр сдвига и элементы И, ИЛИ, причем управляющие входы каждого арифметического блока соединены с соответствующими выходами блока управления, о т л ичающееся тем, что, с целью повышения быстродействия, N арифметических блоков соединены в матрицу первый, второй, третий , четвертый информационные входы (i,j)-ro арифметического блока соединены соответственно с информационными выходами (i-l,j)-ro, (i,j-l)-ro, (i+1,j)-ro (i,j+l)-ro Арифметических блоков; пятый, шестой, седьмой и восьмой информационные входы с информационными выходами (i-2,j)го, (i,j-2)-ro, (i+2,j)-ro и (i,j+2)-ro арифметических блоков; девятый, десятый, одиннадцатый и двенадцатый информационные входы - с информационными выходами (i-l,j- го, (i+l,j-l)-ro, (i+l,j+I)-ro и (l-l,j+l)-ro арифметических блоков, причем в каждый арифметический блок введены дополнительно второй, третий и четвертый регистры сдвига и дополнительный сумматор; первый, второй, третий, четвертый, пятый и шестой входы сумматора соединены соответственно с выходами первого, второго, третьего, четвертого.

пятого и шестого элементов ИЛИ; первый, второй и третий входы первого элемента ИЛИ подключены соответственно через первый, пятый и девятый элементы И к первому, пятому и 5 девятому входам арифметического блока ; первый, второй и третий входы второго элемента ИЛИ - через второй, шестой и десятый элементы И - ко второму, шестому и десятому информаQ ционным входс1м арифметического блока, первый, второй и третий входы третьего элемента ИЛИ - через третий, седьмой и одиннадцатый элементы И - к третьему, седьмому и одиннадцатому

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

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

0 того, второй и первый входы пятого элемента ИЛИ соединены через восемнадцатый и девятнадцатый элементы И соответственно с инверсньвш выходами второго и четвертого регистров

5 сдвига, а первый и второй входы

шестого элемента ИЛИ соединены через двадцать первый и двадцатый элементы И соответственно с npHfCJM выходом второго регистра сдвига и с инд версным выходом третьего регистра сдвига; первый вход дополнительного сумматора соединен через двадцать второй элемент И с выходом сумматора, а второй вход дополнительного сумматора через двадцать третий элемент

5 И - с инверсным выходом второго регистра сдвига, выход дополнительного сумматора - с управляющим выходом арифметического блока, а выход сумматора подключен через двадцать чет0 элемент И ко входу первого регистра сдвига, и через двадцать восьмой элемент И - к первому входу седьмого элемента ИЛИ, прямой выход второго регистра сдвига под-

5 ключен через двадцать шестой элемент И ко входу четвертого регистра сдвига и через двадцать седьмой элемент И ко второму входу седьмого элемента ИЛИ, а третий вход седьмого

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

Источники информации, принятые во внимание при экспертизе

1.WLrsching t З.Е. Nova: а list .orientea computer, - Datamation

1966 r, 12.

2.Авторское свидетельство СССР 412605, кл. G 06 F 15/16, 1975 (прототип).