Матричное устройство для решения уравнений в частных производных
Устройство относится к вычислительной технике и может быть использовано в специализированных устройствах , предназначенных для решения уравнений Лапласа. Цель изобретенияповышения быстродействия. Устройство содержит матрицу из вычислительных ячеек. Каждая ячейка содержит блоки 2 дифференцирования, сумматоры 3 и регистр 1. Быстродействие повышается за счет использования избыточной четверичной системы кодирования, которая позволяет совмещать операции в блоках . 4 ил., 2 табл. 2/П5 Ш (Л со о:
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) (51)4 (06 F 7 64
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
2) ю
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3837949/24-24 (22) 03.01.85 (46) 07.04.87. Бюл. К - 13 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.Е, Золотовский и P.Â. Коробков
В (53) 681.32(088 ° 8) (56) Авторское свидетельство СССР
У 574733, кл. G 06 F 7/64, 1 %77.
Авторское свидетельство СССР
У 373735, кл. G 06 F 7/64, 1973. (54) МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ УРАВНЕНИЙ B ЧАСТНЫХ ПРОИЗВОДНЫХ (57) Устройство относится к вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения уравнений Лапласа ° Цель изобретения— повышения быстродействия. Устройство содержит матрицу из вычислительных ячеек. Каждая ячейка содержит блоки
2 дифференцирования, сумматоры 3 и регистр 1. Быстродействие повышается за счет использования избыточной четверичной системы кодирования, которая позволяет совмещать операции в блоках. 4 ил., 2 табл.
1302276
U/Ã= Яз
+...+vU(; 1)+vU„
U (<=1!>z }
U .. (!- 1
Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения уравнения Лапласа. 5
Целью изобретения является повьппение быстродействия.
На фиг. 1 приведена структурная схема вычислительной ячейки;- на фиг.2-10 то же,блока дифференцирования и сумматора; на фиг. 3 — то же, узла умножения; на фиг. 4 — соединение вычислительных ячеек в устройстве.
Устройство содержит М R вычисли- 15 тельных ячеек, образующих матричную структуру. Каждая вычислительная ячейка (фиг. 1) содержит регистр 1, m блоков дифференцирования 2, -2 входы блоков дифференцирования имеют 2О номера от 21 до 2, m сумматоров
3,-3 .
Блок дифференцирования (фиг. 2) содержит первый узел 4 памяти таблицы сложения, первый триггер 5, второй 25 узел 6 памяти таблицы сложения, первый умножитель 7, третий узел 8 памяти таблицы сложения, второй регистр 9, четвертый узел 10 памяти! ((-p) (! }! !1 11 (! Ф2) !
Величины VU .. (1=1, Р) зави- (!-р }} сят только от номера шага, а алго- ритм их отыскания не изменяется ° Поэтому, совмещая вычисление этих величин, можно значительно увеличить 45 скорость определения переменной U.
Это особенно важно при итерационных вычислениях. При использовании избыточной системы счисления, позволяющей выполнять арифметические опера- 50 ции,, начиная со старших разрядов, удается совместить определение приращений VU(, (j=l Р) во времени. (<-P+l }
Моделирование уравнения Лапласа 55 основывается на реализации разностного алгоритма. (1+! } (+ 11
U.к =U}к+VtЦ)к таблицы сложения, второй узел 11 умножения, пятый узел 12 памяти таблицы сложения, третий регистр 13, сумматор 3 (фиг. 2) содержит узел 14 памяти таблицы сложения, регистры
15 и 16.
Узел умножения (фиг. 3) содержит вход 17 первого коэффициента, входы
18 второго коэффициента, выходы 19, регистр 20 первого постоянного коэффициента, регистр 21 второго постоянного коэффициента, коммутатор 22, сумматор 23, регистр 24 результата.
В устройстве решается уравнение
Лапласа в случае прямоугольной граничной области — + — ;где à — граничная область (прямоугольник).
Работа схемы основана на свойстJ ве рекурсии — каждое новое значение зависит только от предыдущих значений.
U; =U;, +!}.U;
Выражение (11 можно представить в виде («1 ч
Vt U =(U +U; -211 — +
1.к (} .!}к (}-!}»
+(U ;(ÄÄ> +U. („,, -2U,„),, (г) где i=0 1,..., — номер итерации;
1=1,2,...,M-1 — число точек на переменной Х; К=1,2,...,R-1 — число точек на переменной У. Переменные
U0„ =(l « значения функции U на границе Х=О; U =(Р „ вЂ,значение функции
U на границе X=L;,U =.(} Π— значения на границе У=О; 0 „=(1 „ — значения на границе У=Н. Граничные значения заносятся в специальные регистры и не изменяются в процессе решения.
Все ячейки структуры выполняются и работают одинаково. Отличие граничных ячеек от центральных заклю1302276 чается только в том, что центральные связаны с соседними ячейками, а в граничных ячейках все входы подключаются к выходам блоков ячейки (2 ).
Для этого вместо подключения входов 2 < » 2„, 2>, 2, где j=1,2,... ...,m к выходам соседних ячеек они подключаются к входу 2, В этом слу1 чае величина Ж(1<<,1к +Ul -<) к 2П1 к превращается в величину (U +U
jx
-2U ), которая равна нулю. Следовательно, с выхода сумматора появляется граничное значение с требуемой задержкой. Общее число ячеек равно ЯК» где М вЂ” число дискретов по Х; R— число .дискретов по У.
Схема одной ячейки (фиг. 2) состоит из m блоков дифференцирования, вы- 0 (+<) полняющих операцию 9 О „ m сумматоров, реализующих первое равенство системы (2). Каждые блок 2 и сумматор 3 вычисляют соответствующие переменные для своего шага итерации.
Первый шаг начинается с занесения начальных и граничных значенйй в рео гистры 1 всех ячеек U x(j=1,2,..., ...,И; К=l,...,R). Ячейки с номерами 30
01к » Пмк» U < » UJR HBJIIIIOTCH гранич ными. В их регистры заносятся граничные значения. После занесения данных начинается вычисление. Специального разделения режимов занесения и вычисления не требуется, так как
1 операции при занесении ведутся над нулями и получаемые при этом нулевые значения не влияют на дальнейшие вычисления. В связи с этим управление занесением информации и вычислением производится одинаково — подачей синхронизирующей серии.
Старший первый разряд начального значения появляется на выходе регист45 ра 1 ячейки. С выхода регистра он поступает на вход блока 21, на остальные входы которого поступает информация с выходов регистра 1 соседних ячеек (фиг. 4). После выполнения операции 7
Аналогично через пять тактов формируется величина U на выходе суммаг
<к тора 3 и т.д. до последнего блока
2m и сумматора 3m, где формируется величина U „ . Если m итерации недостаточно» то полученное значение можно вновь запускать на первый блок 2 при и условии, что m —, в противном случае необходимо полученное на выходе значение U. задержать до прохождения всех и разрядов через блок 2< и сумматор 31. При достижении требуемого числа итерации вычисления заканчиваются.
На фиг. 2 приведена схема дифференцирующего устройства и сумматора, работающих в избыточной системе счисления.
Блок 2 работает следующим образом, Узлы памяти таблицы сложения записаны в табл. 1 чисел. В качестве системы счисления взята избыточная система счисления с основанием q=4.
Цифрам исходной системы О, 1, 2, 3 соответствуют цифры избыточной системы О, 1, 2, -1 (вспомогательное кодирование), О, 1, 2, 3, -2, -2 (основное кодирование). Вспомогательное кодирование позволяет избежать распространение переноса при сложении более чем на один разряд.
Таблица сложения цифр приведена в табл. 1, Таблица 1
+ О 1 2
3 -1 -2
0 00 01 02 ll 01 12
1 01 02 11 10 00 01
2 02 11 10 11 01 00
3 11 10 11 12 02 01
-1 01 00 01 02 12 11
-2 12 01 00 01 11 10
Первая цифра — перенос в старший разряд, черта сверху означает, что соответствующая цифра отрицательна.
5 302276
В узлах 4 и 8 записана таблица сложения трех цифр {табл. 2), сумма формируется в соответствии с выражением
Продолжение табл.2
Выходы ПЗУ
Вход
2 3 Разряд Разряд младший старший (3) 5 1
S-a, †„ +a где а,, а, а — цифры, поступающие соответственно на первый, второй и третий входы узлов
4и8.
Простым перебором нетрудно проверить, что максимальные значений суммы (3) — при сложении цифр {3+3-2 (-2))=
=22 и минимальное значение - при (-2-2-2 (х 3) ) =22. Таким образом, на первый и второй входы узла 6 могут поступать только сочетания цифр (0,1,2,-1,-2), Соответственно на выходе узла 6 формируются величины
+4, +3, +2, +1, О, -1, -2, -4. Каждой из перечисленных величин соответствует сигнал на одном из выходов узла 6 (+4, +3, +2, +1, -1, -2, -3, -4), нулю соответствует отсутствие сигналов на всех выходах. Сигналы с выходов узла 6 поступают на узел
7 умножения, где происходит умножеqt ние величины на одну из переях2 численных величин. Узел умножения представляет собой обычную схему параллельного умножения, состоящего из двух регистров, где хранятся множимое (, ) и (3 ) коммутатора, выбиgt 71
ЧХ 7 ха рающего требуемую величину, и параллельного накапливающего сумматора, работающего в избыточной системе.
000 000 . 010
100 000 111
100
000
010 110 000 000
110 110 000 100
000
000
111 100 000 100
011
000
100 000 000
010 000 000 о
010 000 100
100
010 010 000 010
110 010 000 111
000
111
010 000 111
011 010 000 011
110 011 000
Oll
Таблица 2
100 110 011 100
010 110 011 010
011
Выходы ПЗУ
Вход
011
Разряд старший
Разряд младший
1 2
110 110
111 110
011 111 111
011 000 Ol l
000 000 000 000
100 000 000 100.
010 000 000 010
110 000 000 111
111 000 000 111
011 000 000 010
011 110 011 Oll Oll
000
000
000
100
000 011 110 111
100 Oll 110 000
010 011 110 100
1О0
100
000
100
1302276
Продолжение табл. 2!
Выходы ПЗУ
Вход
Разряд Разряд младший старший
2 3
010
100
100
110 011 110 010
lll 011 110 011
011 011 110 100
111 011 011 100 000
011 011 011 000 000
Узлы 17 и 11 содержат по два регистра. В первый регистр заносится
Ч yt величина А, где А = либо †-г
ЧХ ЧУ
Регистр имеет шесть выходов. Первый выход регистра — выдача числа без сдвига; второй выход — выдача числа со сдвигом на 1 разряд; третий выход — выдача числа со сдвигом на 2 разряда в сторону старших разрядов; четвертый, пятый и шестой выходы аналогичны — только на выход выдается
35 инверсия числа.
Учитывая, что двоичный код легко преобразуется в четверичный избыточный код, величина А хранится в обычном двоичном коде, что снижает число триггеров для хранения информации.
Преобразование осуществляется на выходе коммутатора 22. К каждой паре разрядов, начиная от занятой, добавляется один разряд слева, на который подается константа нуль. К знаковому разряду добавляется слева два разряда, на которые поступает значение знакового разряда. Величина A масштабируется всегда таким образом, что ее учетверенное значение не превышает 1.
Погрешность в единицу младшего разряда двоичного числа возникает в связи с использованием инверсии при присвоении знака. Эта погрешность может быть ликвидирована, если на вход переноса младшего разряда сумматора подать знак числа. Однако при достаточно больших и этой погрешностью можно пренебречь.
Во второй регистр заносится веPt Ч
A 3 H HA= 3 у
ЧХ . а все остальное выполняется аналогично.
Таким образом, умножение осуществляется по тактам, в каждом такте происходит сложение числа, хранимого в регистре сумматора, и числа, поступающего с коммутатора. Сдвиг частичного произведения осуществляется автоматически при записи суммы в регистр сумматора за счет соответствующего подключения выходов сумматоров с входами разрядов регистра.
Образующийся старший разряд цифры сразу же выдается на выход схемы умножения.
Полученный старший разряд частичного произведения после выполнения операции умножения на текущий разряд может использоваться дальше. Для этого он поступает на узел 12, на второй вход поступает цифра из узла
ll умножения. Часть схемы, состоящая из узлов 8-11, работает аналогично описанной. За исключением того, что суммируются величины (U; („+,) +
-2П; „ ) и умножение npoucxogt дит на. величину
1 УЯ
Полученные разряды с выходов узлов умножения складываются на узел 12, представляющий собой одноразрядный сумматор, работающий в соответствии с таблицей сложений (табл. 1). Регистр 13 выполняет роль задержки. Две старшие цифры складываются. Образуется старшая (перенос) и младшая (сумма) цифры разрядов.. Перенос добавляется к цифре, поступающей из регистра 13, и после сложения результат появляется на второй группе выходов узла 12, а мпадшая цифра записывается в регистр 13. Затем складываются цифры более младшего разряда. Узел
14 в совокупности с регистром 15 также образует одноразрядный сумматор и предназначен для формирования величины
U(i +it =Ц45к +7+и(1 "15к
Вся описанная процедура может быть разбита по 5 тактам следующим образом: 1 — сложение первых разрядов
9 13 (начиная от старших разрядов) и формирование разряда умножения; 2 — сложение вторых разрядов и умножение на первый разряд сумм; 3 — сложение третьих разрядов, умножение на второй разряд сумм, формирование первого разряда произведения; 4 — сложение четвертого разряда, умножение на третий разряд суммы, формирование второго произведения, суммирование первых разрядов произведения;
5 — сложение пятых разрядов, умножение на четвертый разряд суммы, формирование третьего разряда произведения, суммирование вторых разрядов произведения, сложение первых разрядов приращения V
Формула изобретения
Матричное устройство для решения уравнений в.частных производных, содержащее М К вычислительных ячеек (где M — число дискретов по координате Х, à R — число дискретов по координате У, причем каждая вычислительная ячейка содержит регистр, установочные входы регистра (j, К)-ой вычислительной ячейки соединены (j, К)-ой группой входов начальных условий устройства (j=l, M; K 1, R), вход синхронизации регистра каждой вычислительной ячейки соединен с тактовым входом устройства, о т л и ч а ю— щ е е с я тем, что, с целью повьппения быстродействия, каждая вычислительная ячейка содержит m блоков дифференцирования и m сумматоров (где
m — разрядность операндов в четверичной избыточной системе), причем тактовые входы блоков дифференцирования и сумматоров всех ячеек подключены к тактовому входу устройства. С первого по четвертый информационные входы i-го (i=2,m) блока дифференцирования (j,Ê)-ой (j=2, M-1; K=2, К-1) вычислительной ячейки соединены . с выходами (i-1) сумматоров соответ02276 10 ственно (j+1, К)-й, (j-l, К)-й, (), К-1)-й и (j, К+1)-й вычислительных ячеек соответственно, с первого по пятый информационные входы первого блока дифференцирования (j, К)-й (j=2, M-1, К=2, R-1) вычислительной ячейки соединены с выходами регистров (j+1, К)-й, (j-l, К)-й, (j, К-1)-й, (j, К+1)-й вычислительной ячейки соответственно, пятый информационный вход i-го (i=2 m) блока дифференцирования (j К)-ой (1=2, М-1, К=2, R-1) вычислительной ячейки соединен с выходом (i-1)-ro сумматора той же вычислительной ячейки, выход i-го (i=1 m) блока дифференцирования подключен к входу первого слагаемого i-го сумматора той же вычислительной ячейки, выход которого
20 соединен с входом второго слагаемого. (i+1)-ro слагаемого той же вычислительной ячейки, выход m-го сумматора (1, К-ой вычислительной ячейки ()=1, M; K=l, R) соединен с информационным входом регистра той же вычислительной ячейки, первый и второй установочные входы i-ro блока дифференцирования (i=1 m) (j К)-ой вычисли.тельной ячейки (j=l, M; K=1, R) соединены с первым и вторым соответственно входами задания постоянных параметров устройства, информационные входы с первого по пятый i-го (i=2,m) блока дифференцирования (j,l), (1,К), (M, 35 К), (j,К) (j=l, М; К=l,R) вычислительных ячеек соединены с выходом (i-1)-го сумматора той же вычисли-. тельной ячейки, вход первого слагаемого которого соединен с выходом
40 (i-1)-ro блока дифференцирования той же вычислительной ячейки, а вход второго слагаемого i-го (i=2 ш) сумма-, тора (j,l), (1,К), (М,К), (j,R) вычислительных ячеек соединен с выходом
45 (i 1) (1 К) (М К) (). Ц 1
К=l, R) вычислительных ячеек соединен с информационными входами с первого по пятый первого блока дифференцирования тех же вычислительных ячеек, 50 выход которого соединен с входом первого слагаемого первого сумматора тех же вычислительных ячеек, вход второго слагаемого которого соединен с выходом регистра тех же вычислительных ячеек, 1302276
t 37
Фиг. 2
Вкпб записи
1302276
Составитель А. Чеканов
Редактор Л. Гратилло Техред Л.Олейник Корректор А. Ильин
Заказ 1217/48 Тираж 673 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-ÇS, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4