Матричное устройство для решения уравнений в частных производных Советский патент 1987 года по МПК G06F7/64 

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

Целью изобретения является цовьше- ние быстродействия.

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

Устройство содержит MxR вычисли- тельных ячеек, образующих матричную структуру. Каждая вычислительная ячейка (фиг. 1) содержит регистр 1, m блоков дифференцирования 2, -2, входы блоков дифференцирования имеют номера от 2. до 2 , m сумматоров 3-3

- - ГТ1«

Блок дифференцирования (фиг. 2) содержит первый узел 4 памяти таблицы сложения, первый триггер 5, второй узел 6 памяти таблицы сложения, первый умножитель 7, третий узел 8 памяти таблицы сложения, второй регистр 9, четвертый узел 10 памяти

) (;.p,, +7U (;-p, +... +

и,.

lUp+0

Ci-p-ri)

Величины Vи,. - (j l, P) зависят только от номера шага, а алгоритм их отыскания не изменяется. Поэтому, совмещая вычисление этих величин, можно значительно увеличить скорость определения переменной U. Это особенно важно при итерационных вычислениях. При использовании избыточной системы счисления, позв оля- ющей выполнять арифметические Опера- ции,. начиная со старших разрядов. Удается совместить определение приращений .Vи,.. (j l, P) во времени.

Моделирование уравнения Лапласа 55 основывается на реализации разностного алгоритма.

{(40 i (Ui)

UjK UiK+VtUjK

таблицы сложения, второй узел 11 умножения, пятый узел 12 памяти таблицы сложения, третий регистр 13, сумматор 3 (фиг. 2) содержит узел 14 памяти таблицы сложения, регистры 15 и 16.

Узел умножения (фиг. 3) содержит вход 17 первого коэффициента , входы 18 второго коэффициента, выходы 19, регистр 20 первох о постоянного коэффициента, регистр 21 второго постоянного коэффициента, коммутатор 22, сумматор 23, регистр 24 результата.

В устройстве решается уравнение Лапласа в случае прямоугольной гра- « 9U ничнои области - уг дуг

I и/Г tfJ

где Г - гра ничная область (прямоугольник) .

Работа схемы основана на свойстсве рекурсии - каждое новое значение

зависит только от предьщущих значений.

,., +AU;(1)

Выражение ( можно представить в виде

h+i

и., (u

(j.,yK (j-,)K

-2U

J

+u.

j(-0

-2UU)

vt

Чу2

(2)

где ,1,..., - номер итерации; ,2,...,М-1 - число точек на переменной X; ,2,...,R-1 - число то- чрк на переменной У. Переменные UOK. Ч ох значения функции U на границе U{,. . -.значение функции и на границе ,UJg tj)j - значения на границе U,, - значения на границе . Граничные значения заносятся в специальные регистры и не изменяются в процессе решения.

Все ячейки структуры выполняются и работают одинаково. Отличие граничных ячеек от центральных заклю313022764

чается только в том, что централь- сумматора равна двум тактам и, сле- ные связаны с соседними ячейками, а , довательно, через пять тактов стар- в граничных ячейках все входы подключаются к выходам блоков ячейки (2j, ) .

Для дов 2j,

.. .in.

этого вместо подключения вхо . J3 14 J -

к выходам соседних ячеек они

через

ший разряд U . поступает на блок 2j куда на другие входы поступают величины с сумматора 3, соседних ячеек. Аналогично через пять тактов формируется величина U на выходе суммаJK

тора 3 и т.д. до -последнего блока 2т и сумматора 3т, где формируется величина Uj . Если ш итерации недостаточно, то полученное значение можн вновь запускать на первый блок 2 п

Б этом cjjy4j i)K ,,K - 2UjV ,0 в величину

к входу (U

2j.,

--и

(jK JK-2U;j,), которая равна нулю. Следовательно, с выхода сумматора появляетс граничное значение с требуемой задержкой. Общее число ячеек равно Ml, где М - число дискретов по X; R - число .дискретов по У.

в

Схема одной ячейки (фиг. 2) состоит из m блоков дифференцирования, вы

(1-и)

, и m сумматоров, реализующих первое равенство системы (2). Каждые блок 2 и сумматор 3 вычисляют соответствующие переменные для своего шага итерации, Первый шаг начинается с занесения начальных и граничных значений в регистры 1 всех ячеек U;, (.j l ,2,..., ...,М; ,...,R). Ячейки с номерами

полняющих операцию V U

и

и.

U:

U;

являются гранич

k. Mfc 1 JR

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

Старший первый разряд начального значения появляется на выходе регистра 1 ячейки. С выхода регистра он поступает на вход блока 21, на остальные входы которого поступает информация с выходов регистра 1 соседних ячеек (фиг. 4). После выполнения операции и 1 поступает следующий синхроимпульс и второй разряд поступает На блок 21. Задержка блоков 2 равна трем . Следовательно, через три такта старший разряд величины появляется на входе сум матора 3, На сумматорах 3 формиру- „ -М , Задержка

JK.

сумматора равна двум тактам и, сле- довательно, через пять тактов стар-

через

ший разряд U . поступает на блок 2j , куда на другие входы поступают величины с сумматора 3, соседних ячеек. Аналогично через пять тактов формируется величина U на выходе суммаJK

тора 3 и т.д. до -последнего блока 2т и сумматора 3т, где формируется величина Uj . Если ш итерации недостаточно, то полученное значение можн вновь запускать на первый блок 2 п

условии, что т5. прив противном слу

чае необходимо полученное на выходе значение U: задержать до прохождения всех п разрядов через блок 2, и сумматор 3. При достижении требуемого числа итерации вычисления заканчиваются.

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

Блок 2 работает следующим образом. УЗЛЫ памяти таблицы сложения записаны в табл. 1 чисел. В качестве системы счисления взята избыточная система счисления с основанием .

Цифрам исходной системы О, 1, 2, 3 соответствуют цифры избыточной сие-

темы О, 1, 2, -1 (вспомогательное

кодирование). О, I, 2, 3, -2, -2 (основное кодирование). Вспомога- 35 тельное кодирование позволяет избежать распространение переноса при сложении более чем на один разряд. Таблица сложения цифр приведена в

табл. 1

40

,

45

,

55

Первая цифра - перенос в старший разряд, черта сверху означает, что соответствующая цифра отрицательна.

(W - и

) коммутатора, выби- 35

рающего требуемую величину, и параллельного накапливающего сумматора, работающего в избыточной системе.

Продолжение табл. 2

ПО 011 ПО

010

010

111 011 по

011

100

011

011 по

100

100

111 011 oil

100

000

on

on on

000

000

Узлы 17 и 11 содержат по два регистра, В первый регистр заносится

АА Vt « Vt

величина А, где А либо - ,

V Ау-У

Регистр имеет шесть выходов. Первый выход регистра - выдача числа без сдвига; второй выход - вьщача числа со сдвигом на 1 разряд; третий выход - выдача числа со сдвигом на 2 разряда в сторону старших разрядов; четвертый, пятый и шестой выходы аналогичны - только на выход вьщается инверсия числа.

Учитывая, что двоичньш код легко преобразуется в четверичный избыточный код, величина А хранится в обычном двоичном коде, что снижает число триггеров для хранения информации. Преобразование осуществляется на выходе коммутатора 22. К каждой паре разрядов, начиная от занятой, добавляется один разряд слева, на который подается константа нуль. К знаковому разряду добавляется слева два разряда, на которые поступает значение знакового разряда. Величина А

45 ется к цифре, поступающей из регистра 13, и после сложения результат появляется на второй группе выходов узла 12, а младшая цифра записывается в регистр 13. Затем складываются

масштабируется всегда таким образом, о цифры более младшего разряда. Узел что ее учетверенное значение не пре- . ,д совокупности с регистром 15 так- вьш1ает 1.

Погрешность в единицу младшего разряда двоичного числа возникает в

55

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

же образует одноразрядный сумматор и предназначен для формирования величины

U(i4,lJK U.V,U(v,l.,

Вся описанная процедура может быть разбита по 5 тактам следующим образом: 1 - сложение первых разрядов

достаточно больших п этой погрешностью можно пренебречь.

Во второй регистр заносится величина А 3

Vt

или А 3

Vt

5

0

5

fl - у2 ,

а все остальное вьтолняется аналогично.

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

Полученный старший разряд частичного произведения после выполнения операции умножения- на текущий разряд может использоваться дальше. Для этого он поступает на узел 12, на второй вход поступает цифра из узла 11 умножения. Часть схемы, состоящая из узлов 8-11, работает аналогично описанной. За, исключением того, что суммируются величины (и;;., +

М(It ll умножение происхоVtдит на величину .

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

0 с таблицей сложений (табл. 1). Регистр 13 выполняет роль задержки. Две старЩие цифры складываются. Образуется старшая (перенос)и младшая (сумма) цифры разрядов.. Перенос добавля5 ется к цифре, поступающей из регистра 13, и после сложения результат появляется на второй группе выходов узла 12, а младшая цифра записывается в регистр 13. Затем складываются

0

о цифры более младшего разряда. Узел . ,д совокупности с регистром 15 так-

цифры более младшего разряда. Узел ,д совокупности с регистром 15 так-

же образует одноразрядный сумматор и предназначен для формирования величины

U(i4,lJK U.V,U(v,l.,

Вся описанная процедура может быть разбита по 5 тактам следующим образом: 1 - сложение первых разрядов

(начиная от старших разрядов) и формирование разряда умножения; 2 - сложение вторых разрядов и умножение на первый разряд сумм; 3 - сложение третьих разрядов, умножение на второй разряд сумм, формирование первого разряда произведения; 4 - crto- жение четвертого разряда, умножение на третий разряд суммы, формирование второго произведения, суммирование первых разрядов произведения; 5 - сложение пятых разрядов, умножение на четвертый разряд суммы, Сформирование третьего разряда произведения, суммирование вторых разрядо произведения, сложение первых разрядов приращения tU/-,v. и U,-:, и

формирование первого разряда величины и,. , . , которая поступает в следую-

щую ячейку и т.д. Задержка между поступлением первого разряда переменной и формирование его нового значения в ячейке составляет пять тактов.

Формула из обре тени яМатричное устройство для решения уравнений в-частных производных, содержащее M-R вычислительных ячеек (где М - число дискретов по координате X, а R - число дискретов по координате У, причем каждая вычислительная ячейка содержит регистр, установочные входы регистра (j, К)-ой вычислительной ячейки соединены (j, К)-ой группой входов начальных условий устройства (, М; , R), вход синхронизации регистра каждой вычислительной ячейки соединен с тактовым входом устройства, отличающее с я тем, что, с целью повьше- ния быстродействия, каждая вычислительная ячейка содержит m блоков дифференцирования и П1 сумматоров (где m - разрядность операндов в четверичной избыточной системе), причем тактовые входы блоков дифференцирования и сумматоров всех ячеек подключены к тактовому входу устройства. С первого по четвертьй информационные входы i-го (,т) блока дифференцирования (л,К)-ой (, М-1; , R-1) вычислительной ячейки соединены с выходами (i-1) сумматоров соответ

0

5

5

0

ственно (J+1, К)-й, (j-l, К)-й, (j, К-1)-й и (j, К+1)-й вычислительных ячеек соответственно, с первого по пятый информационные входы первого блока дифференцирования (j, К)-й (, М-1; , R-1) вычислительной ячейки соединены с выходами регистров (J+1, К)-й, (J-1, К)-й, (j, К- -1)-й, (j, К+1)-й вычислительной ячейки соответственно, пятый информационный вход i-ro (, m) блока дифференцирования (j, К)-ой (, М-1, , R-1) вычислительной ячейки соединен с выходом (L-l)-ro сумматора той же вычислительной ячейки, выход i-ro (, m) блока дифференцирования подключен к входу первого слагаемого 1-го сумматора той же вычислительной ячейки, выход которого соединен с входом второго слагаемого- (1+1)-Го слагаемого той же вычислительной ячейки, выход т-го сумматора и °й вычислительной ячейки (, М; К, R) соединен с информационным входом регистра той же вычислительной ячейки, первый и второй установочные входы 1-го блока дифференцирования (,т), (j, К)-ой вычислительной:, ячейки (, М; , R) сое0

динены с первым и вторым соответственно входами задания постоянных параметров устройства, информационные входы с первого по пятый 1-го (,т) блока дифференцирования (j , 1) , (1,К), (М, 5 К), (j,R) (, М; ,R) вычислительных ячеек соединены с выходом (i-l)-ro сумматора той же вычислит тельной ячейки, вход первого слагаемого которого соединен с выходом (1-1)-го блока дифференцирования той же вычислительной ячейки, а вход второго слагаемого 1-го (,т) сумма-, тора (j,l), (1,К), (М,К), (j,R) вычислительных ячеек соединен с выходом (1-1), (1,К), (М,К), (j,R)-, (j l, М; К, R) вычислительных ячеек соединен с информационными входами с первого по пятый первого блока дифференциро- ванчя тех же вычислительных ячеек, выход которого соединен с входом первого слагаемого первого сумматора тех же вычислительных ячеек, вход второго слагаемого которого соединен с выходом регистра тех же вычислительных ячеек.

5

0

5

37i Фае. 2

записи

((

Sxoif записи

.f«)

2

)

Лж(3)

.

f ч г I i/3/jtf

izj

. П

±

2

//1

2kn

Г

1

Фиг. ч

Устройство относится к вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения уравнений Лапласа. Цель изобретения- повышения быстродействия. Устройство содержит матрицу из вычислительных ячеек. Каждая ячейка содержит блоки 2 дифференцирования, сумматоры 3 и регистр 1. Быстродействие повышается за счет использования избыточной четверичной системы кодирования, которая позволяет совмещать операции в блоках. 4 ил., 2 табл. 2/П5 Ш (Л со о: