Параллельное вычислительное устройство для решения разностных уравнений задач теории поля

 

(«i742945

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ИТЕЛЬСТВУ

Союз Советскик

Социалистических

Республик (61) Дополнительное к авт. сеид-ву (22) Заявлено 291 275 (21 ) 230 600 О/18-24 (51)М. Кл.

G 06 F 15/32 с присоединением заявки Ио

Государственный комитет

СССР яо делам изобретений я открытий (23) Приоритет

Опубликовано 2506.80. Бюллетень Ио 23

Дата опубликования описания 2506.80 (53) УДК 681 ° 14 (088.8) (72) Авторы изобретения

В.П. Ильин и Я.И. Фет

Вычислительный центр Сибирского отделения AH СССР и Институт математики Сибирского отделения АН СССР (7! ) Заявители (54) ПАРАЛЛЕЛЬНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

ДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ УРАВНЕНИЙ ЗАДАЧ

ТЕОРИИ ПОЛЯ

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

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

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

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

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

Цель изобретения — повыаение быстродействия цифрового вычислительного устройства при решении раэностных уравнений задач теории поля. (() Эта цель достигается тем, что в предлагаемом устройстве N арифметических блоков соединены в матрицу, первый, второй, третий, четвертый информационные входы (i,j) -го ариф-!

5 метического блока со д"иены соответственно с информационными выходами (i-l,j)-ro, (1,j-l) -го,(1+l,j)-го (1,j+l) -го арифметических блокову пятый, шестой, седьмой и восьмой информационные входы — с информационными выходами (1-2,j) -го, (i,j-2) -го, (1+2,j) -го и (1, +2) -ro арифметических блокову девятый, десятый, одиннадцатый и двенадцатый информационные входы — с информационными выходами (1-1, j-1)-го (1+1 j-1) -го, (1+1, )+1) -го и (i-l,j+1) -ro арифметических блоков, ууричем в каждый арифметический блок

Введены дополнительно второй,тре742945

f0

35

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

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

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

На фиг. 1 приведена блок-схема устройства; на фиг. 2 — схема арифметических блоков.

Устройство содержит универсальную вычислительную машину 1, параллельное вычислительное устройство

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

Каждый арифметический блок (фиг.2) содержит регистры сдвига

6-9, дополнительный сумматор 10, сумматор 11, элементы 12 — 18 ИЛИ и элементы 19-47 И.

Работа устройства заключается в аппаратной реализации решения раз— ностных уравнений Пуансона: где f. u g — заданные значе1 т 3 1) ния правой части и граничных функций.

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

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

Q. — АУ н узлах с четными зна1 чениям i+j.

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

Q. — АУ н узлах с четными i,), 1. +Д для которых — 1 четно.

Q — АУ в узлах с четными i,j„

2

1+1 для которых нечетно, % 1

Множество =Ю„+Я- образует густую сетку, множество а"=g-1"Я2 вспомогательную редкую сетку.

Перед началом вычислений н регистры сднига 7 всех арифметических блоков засылаются значения правых частей разностных уравнений, а н

742945 регистры сдвига б граничных узлов " значения граничных функций.

Решение задачи делится на следую- щие этапы:

A. Решение разностных уравнений на редкой сетке с помощью итерацион- 5 ного процесса:

И+1 (Ю Yl И l1 . рl1

Ч.. = — (а % . %. д и

4V„".>-4.f, )+ 1., (2) 10

ЦвЯ (1,j)E Q, -4.Х ++% ., (3) ДЛЯ (- 3 ) Е 1 г 20

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

1j 4 1-1;)-1 i× -1 1+1,1+1 1-1 1+1 131 длЯ (1,3)Еа", /а ". для (i, j)ea"

В. Решение разностных уравнений на густой сетке с помощью интерационного процесса:

30 для (1, j ) Ca.

Д. Вычисление точных значений для остальных узлов густой сетки с помощью интерполяции по формулам (4) и (5) .

Укаэанные вычисления выполняются в параллельном вычислительном устройстве 2 следующим образом.

A. В каждый из арифметических блоков 4.множества узлов Q. пода21 ются из блока управления 3 разрешающие сигналы на элементы 23-26 И. 60

Этим обеспечиваются соединения, необходимые для того, чтобы на первые четыре входа сумматора 11 поступали одновременйо в этй арифмети- 65

1 (6) для (i j) EQ . й. = — Ч. +М, 1Ч. 14 4% Х . 1-%

Ц 4 (1-1,), J-1 i 1Ä,)Мдля (3 )Е ", (7)

Г. Комбинация раэностных решений узлов редкой сеткиг 45

1/ h 2é

"1,)= Ъ 4" К"(, l, (8) ческие блоки подаются разрешающие сигналы на элементы 36 и 39 И, которые обеспечивают соответственно поступление учетверенных (например, предварительным сдвигом алево на два рази ряда) значений Ч1 > — с инверсного выхода регистра сцвига б и f — c

1,5 инверсного выхода регистра сдвига 7 на пятый и шестой входы сумматора 11. Кроме того, на элемент 40 И подается сигнал, разрешающий запись результата с выхода сумматора 11 на регистр сдвига 9. На элементы 42 И всех арифметических блоков множества узлов Я. подается сигнал, разреги шающий регенерацию содержимого регистров сдвига б.

После этих подготовительных действий из блока управления 3 подается серия из P импульсов сдвига (P — разрядность переменных) на ре- гйстры сдвига 6 всех арифметических блоков множества узлов Q. и на г регистры сдвига 6,7 и 9 всех арифметических блоков множества узлов

Q.„, В результате в каждом арифмегн тическом блоке множества узлов Я.1 вычисляется и записывается в регистр сдвига 9 выражение, заключенное в скобки в формуле (2) . Данное вычисление является первой фазой итерации.

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

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

После этих подготовительных действий подается серия из Р импульсов сдвига на регистры сдвига б и 9 всех арифметических блоков множества Q .

При этом на первые пять входов сумматора 11 подается (со сдвигом соответственно на один, два, три, четыре и пять разрядов) вычисленное в первой фазе выражение (в скобке), причем поступление этих величин управляется значениями разрядов множителя (0 или 1). В резульЖ тате на выходе. сумматора 11 образуется произведение скобки на множитель

-- . Так как на шестой вход сумматора

11 через элемент 38 И поступает значение V с прямого выхода регистра и сдвига б, то одновременно с вычислением укаэанного произведения происходит сложение этого произведения с переменной Ч - . Результат — новое

1у9 значение переменной — Ч," (формула (2) через элементы 4 И, 18 ИЛИ поступает в регистр сдвига б, замещая .его прежнее содержимое — Ч;1 .

742945

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

Q.2 меняются ролями.

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

Ug — 0„"- с производится с помощью дополнительного сумматора 10. Если во время выполнения второй фазы итерации подать разрешающие сигналы на элементы

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

U, а на второй — также последова- !5 и+ тельно, но в обратном коде, разряды

U 1- . Значит, на выходе сумматора 10 и и, образуется разность U„ -×; .. При

1"17 115

2 < 6 - условие окончанй я итерационного процесса (9 ) выполнитс я тог- 0 да, когда старшие Р— г разрядов этой разности равны нулю . Для проверки условия (9 ) подаются на элементы 46 и 4 7 И всех арифметических блоков данного множества разрешающие си гна- 25 лы с задержкой на r тактов относительно начала второй фазы . Если си гналы на выходах 6 2 всех арифметических блоков данного множества нулевые, итерационный процесс окончен . 30

Полученные значения переменных записываются н регистры сдви2b

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

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

7 множества Я-"„ (Q., таким образом н каждом арифметическом блоке множества Я „ Я. вычисляется и запиh 2h сывается в регистры сднига 6 выражение, заключенное в скобки в формуле (4) .Затем выполняется деление на 4 (например, путем сдвига вправо на два разряда). B результате в 55 регистрах сднига б множества Й.„IQ™ образуются начальные приближения

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

Одновременно в эти арифметические блоки подаются разрешающие сигналы на элемент 39 И, через который f-.

j„2 поступает с инверсного выхода регистра сдвига 7 на шестой вход сумматора 11. Сложение выполняется с помощью серии импульсов сдвига, поданаемых на регистры сдвига 6 множества Q.„ и регистры 6 и 7 мноh жестна Я" . После деления на 4 в регистрах 6 множества Q q обраЪ зуются начальные приближения

1 1

В. В каждый из арифметических блоков множества узлов Я.„ подаются разрешающие сигналы на элементы 19-22 И для поступления пеУ1 ременных 4„. 1,), й1), й1+ ) и 1, 1

Одновременно в эти арифметические блоки подаются разрешающие сигналы. на элементы И 36 и 39 (для подачи переменных — 4Ч;"- и й; . ) и на

111

1 элемент 40 И (для записй промежуточного результата на регистр 9) „

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

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

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

Я" мен яют ся ролями .

На этом заканчивается выполнение одной итерации на густой сетке.

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

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

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

11, значения U.2." - c инверсного

jij выхода регистра 8 н а пятый вход сумматора 1 1 и записи результата с выхода сумматора 1 1 н ре гис тр 9 „

Затем подается серия и з P импул ьсов сдвига для вычи сл ени я и з апи си в регистр 9 разности, заключенной в скобки н формуле (8 ) . После этого блок управления 3 снижает разрешающие сигналы с элементов 3 8, 3 7 и 4 0 И, подает разрешающие сигналы на элемент 4 1 И и, кроме того, подает н а элементы 3 1- 3 5 И сигналы, соот в е т - ст вующие значениям разрядов множител я ; Затем выполняется умножеМ ние та, как описано выше (этап А) .

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

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

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

U., которые и составляют решение задачи. !О

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

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

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

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

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

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

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

12 т-- --

IT1, I 1

Г Г !

Г

1 ! ! !

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

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

1. Wi.rsching I J.Е . Nova! à fist— .orientea computer. — "Datamation"

1966 r М 12.

2. Авторское свидетельство СССР

М 412605, кл. G 06 F 15/16, 1975 (прототип) 742945

Составитель Н. Палеева

ТехРед M.Петко Корректор Н. Стец

Редактор Т. Киселева

Тираж 751 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 3619/15

Филиал ППП Патент, г. Жкгород, ул. Проектная,4