Узловой элемент цифровой сетки для решения краевых задач

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕаЪБЛИК (19) (111

А1 (ц y G 06 F 15/32

ОПИСАНИЕ ИЗОБРЕТЕНИЯ:

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3834636/24-24 (22) 29.12.84 (46) 23.07.86. Бюл. !(- 27 (71) Одесский ордена Трудового Красного Знамени политехнический институт (72) И.Д.Коноплев, В.Е.Прокофьев, А.М.Казачинский и Л.А.Волощук (53) 68!.333 (088.8) (56) Авторское свидетельство СССР

Р 739542, кл. (06 F 15/32, 1978.

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

N 811275, кл. G 06 F 15/324, 1978. (54) УЗЛОВОЙ ЭЛЕМЕНТ ЦИФРОВОЙ СЕТКИ

ДЛЯ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ (57) Изобретение относится к области цифровой вычислительной техники и может быть использовано при разработке специализированных вычислительных машин и процессоров для решения краевых задач. Целью изобретения являются повышение точности и быстродействия. Устройство содержит блок памяти, счетчик, группу элементов И, группу элементов ИЛИ, регистры, сумматоры, блок синхронизации, счетчик адреса, блок проверки окончания итерационного процесса °

Устройство позволяет за счет введенных блоков осуществить распараллеливание вычислительного процесса и тем самым повысить точность и быстродействие устройства. 3 ил.

Изобретение относится к цифровой вычислительной технике и может быть использовано при разработке специализированных вычислительных машин и процессоров для решения краевых задач, описываемых уравнением (1) и краевыми уравнениями (2)-(6) dx, "l dx„dx > Йх

d dT . dT

+ — (11- )+4(x х х L )=сР— —;

dx Mx з 3

1 2 3 1 1

246111 2 элемент.4 ИЛИ-НЕ 25, элемент 2И 26, элемент 2 ИЛИ-HE 27, элемент 2ИЛИ 28.

Блок 11 синхронизации содержит элемент 2 И-HE 29, триггер 30, эле5 мент 2 И 31, счетчик 32, блок 33 памяти и генератор 34 тактовых импуль— сов.

Для решения уравнения (1) — (6) преобразуются к системе уравнений вида

I YQKC

U .= ) 2 Ь. U. +F (71

ГК 1 1К,Г1,М 1,М

1 К

Т = f(S,i);

q(S,i) =Гp,,, )

dT . ((S,- ) =ГТ,(S,т )-T(S,1 )j =-(P„",1„(4)

T=f (х,,х,х ) при = (б)

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

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

Устройство содержит блок 1 памяти коэффициентов и свободного члена уравнений, счетчик 2 адреса, группу элементов И 3.1,... — 3.6, четвер. тый. элемент И 4, сумматор 5 единиц, регистр 6 суммы, третий элемент И 7, элемент 3 ИЛИ 8,. второй элемент И 9, одноразрядный сумматор 10, блок I1 синхронизации, регистр 12 произведения, блок 13 проверки окончания итерационного процесса, пятый элемент И 14, первый элемент И 15, элемент 2 ИЛИ 16, регистр 17 результата, элемент 2И"НЕ 18, группу информационных входов устройства 19.1...—

19,6, выход 20-14 сигнализации окончания итерационного процесса.

Блок 13 проверки окончания итера— ционного процесса содержит элемент

4И 21, двухразрядный регистр 22, элемент 23 сравнения, триггер 24, где i=1,2„3, k=1,2; n — момент времени, для которого производится расчет П „, индекс М указывает на масштабное представление индексированных переменных, которые всегда сводятся к следующим численным интервалам

0" П м 1

0 Ь,, < 1 и заведомо представлены в дополнительном коде.

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

ЗО известные значения коэффициентов

Ь; и свободного члена F а такtn, h, М же значения искомой функции U, получаемые в соседних узловых элементах.

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

Решение системы уравнений выполняется метоцом итераций. При этом узловой:элемент использует Hà J é ите4П рации значения U., определенные

l К, ll в (j-1)-м приблюкении. Таким образом уравнение (7) для вычисления

U „ в 1-м приближении. необходимо записать так

45 !мокс

+Р

, Г1,М

Условие окончания итерационного процесса, обеспечивающего вычисле50 ние (U „ „ ),, имеет вид !

/(U„, ), — (U „„),, (-, (9) где — заданная точность результата.

Последовательность действий, про55 изводимых в узловом элементе на одной итерации, можно условно разделить на два этапа. Первый — это собственно решение уравнения (8) и по3

t лучение значения (V ) на накап,n,м ливающем регистре 12 произведения и второй — поразрядная перезапись результата и регистра 12 произнедения н регистр 7 результата с однонремен ной проверкой условия окончания итерационного процесса в блоке 13 проверки окончания итерационного процесса.

ПеРвый этап состоит из m циклов, н каждом из которых п тактов, и еще одного такта, где m — это длина двоичного кода

Алгоритмически каждому циклу соответствует процесс получения суммы 15 частичных произведений одного разряда (коэффициента) Ъ|„ „ „ на двоичный код U,.

I <

Для получения конечного результата необходимо повторить столько циклов, сколько разрядов содержит код Ь к „ и столько тактов в цикле, к,ь сколько разрядов имеет код U к,,м, а также произвести суммирование Ч; b,„„со свободным членом 25

F „, которое производится за 1

1 1 такт работы.

Необходимо отметить также следующие особенности.

Так как О. (U ) 1,0 Ь 1, 30 то и их произнедение будет находиться в интервале

1246

20

Очевидно, что максимально возможное значение, получающееся в регистре 12 произведения при суммировании шести значений b; Б; „ м, может быть равно 6.

Следовательно, при использовании 40 двоичной системы исчисления для исключения ошибок переполнения регистр

12 произведения помимо m разрядов для дробной части числа должен быть дополнен тремя двоичными разрядами, а та .z

l Е U b. и Р одним знак K,,М н, ч 1ч, коным разрядом, 45 Управляющий сигнал 20-2 с блока

11 отключает выход регистра 6 суммы от входа одноразрядного сумматора

fÑ, когда все три разряда суммы просуммированы с разрядами регистра

50 произведения.

B результате первого такта в регистре 12 произведения записывается сумма частичных разрядных произведений и в младшем разряде устанавливается m — 1 разряд накопленного результата.

Второй такт отличается от первого толькЬ тем, что на группу информаСуммирование результата K X U. x

1к,л<м Ь;к, полученного за m циклов, с кодом Г „, производится по окончании последнего цикла в течение еще одного дополнительного такта работы.

Для представления одинаковым образом слагаемых код F„ „ дополнен тремя разрядами целой части, н которых эа111 4 писаны тоже коэффициенты, что и в знаковом разряде.

Первый цикл реализуется в узловом элементе следующим образом.

Управляющий импульс 20 — 10 с блока 11 поступает на счетный вход счетчика 2 адреса, на выходах которого устанавливается "Адр 1", соответствующий ячейкам памяти с младшими разрядами Ь;, На группе элементов И 3. 1-3.6 происходит поразрядное умножение

m-го разряда Ь, íà m-й разряд

i!,л, М

Результаты поразрядного умножения складынаются на сумматоре 5 единиц, сумма произведений, как указывалось не может превышать шести, поэтому по управляющему импульсу 20- 4 с бло ка 11 результат суммирования принимается на трехразрядный регистр 6 суммы. Далее производится поразрядное сложение содержимого регистра

6 суммы и регистра !2 произведения на одноразрядном сумматоре 10 и размещение результата на регистре 12 произведения путем повторения m+5 раэ управляющего сигнала 20-6 с блока 11 который обеспечивает сдвиг в сторону младших разрядов и одновременно с этим прием результата суммирования предыдущего разряда в старший разряд регистра 12 произведения и трехкратного повторения управляющего сигнала 20;5 (с блока 11) последона .ельного сдвига содержимого регистра 6 суммы. Управляющий сигнал 20-1 с блока 11 отключает выход регистра 12 произведения от входа одноразрядного сумматора 10. Это необходимо в первом такте первого цикла, когда происходит одновременная запись и очистка регистра 12 произведения.

5 1246 ционных нходов устройства !9.1 — 19.6 поступают m-1 разряды U „ „, что

IK, i,М достигается круговым сдвигом на региотре результата соседних с данным узловых элементов. Соответственно происходит круговой сдвиг (управляющий сигнал 20-8) значения (У,,„)„,, расположенного на регистре 17 результата рассматриваемого узлового элемента. 1О

В результате второго такта н регистре 12 произведения формируется серия результатов первого и второго тактов, а в младшем разряде устанавливается m-2 разряд накопленного 15 результата.

В последнем m" такте цикла управляющий сигнал 20-6 повторится не ш+

+5 раз, а только 5 раз, что обеспечивает -размещение m-1 разряда на- Ю копленной суммы в младшем разряде регистра 12 произведения.

Следует отметить, что в результате кругового движения накапливаемого результата в регистре 12 произведения в кажцом цикле,по сравнению с известным устройством экономится (m — 1) микротактов работы устройства. Это можно пояснить следующими расчетами: ЗО

В каждом из 1 по m-1 тактах работы предлагаемого узлового элемента производится (m + 5) сдвигов регистра произведения для получения

Ф очередного накаплинаемого результата, З5

Всего за m-1 тактов будет произведено (m-1) (m+5) . микротактов.

В m такте производится 5 сдвигов.

Всего на цикле будет затрачено (m-1) (m+5) + 5 микротактон работы. тр

В каждом из 1 по ш-1 тактах работы известного устройства, на накапливающем сумматоре такой же разрядности KBK H peFHctp 12 произведения последонательное распростране- 45 ние переноса из младших разрядов в старшие займет (ш+3) микротактов работы устройства и сдвиг нправо еще один микротакт. Всего (ш+4) микротакта. За (m-1) тактов будет произведе- 5О но (m 1) (ш+4) микротактов.

В ш такте работы известного устройства производится (ш+4)+(ш-1) микротактов °

Всего на цикл будет затрачено (m-1) (ш+4)+2 ш + 3 микротактов работыы.

11! Ь

Посчитаем разнииу: (m+1)(m+4)+

+2m+3-(m-1)(тп+5) -5=(m-1)(m+4-тп-5)+

+2m+3-5== — (m-1) +2m+2=m-1 .

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

3.1-3.6 поступают следующие разряды н последнем такте при 4-м сдвиге регистра 12 произведения закрывается вход одноразрядного сумматора 10 управляющим сигналом 20-11 с блока

11, что обеспечивает чистоту полу-. чения переноса в старший разряд регистра 12 произведения.

Результатом Ш циклов является

ЕЕ Б;„„ Ь!ки

Далее, н течение одного такта работы происходит суммирование с кодом F, Для чего производится ш+4 кратное повторение упранляющих импульсов 20-6 и 20-10, при открытом элементе И 4 упранляющим сигналом

20-3 и закрытых элементах И 7 и 2

И-HE 18 соответственно управляющими сигналами 20-2 и 20-9 °

Как видно за ш циклов будет сэкономлено m(m-i) микротактов работы устройства. На суммирование с F . „ будет затрачено (ш+4) микротакта.

Тогда экономия времени выполнения первого этапа составляет m(m-1)

-(m+4)=(m-1)(m-1)-5 микротактов.

На втором этапе определяется выполнение условия окончания итерационного процесса (9) и размещение результата текущей итерации на ре" гистре 17 результата.

Характерно, что искомое значение

0%„ „ 1. Поэтому, если íà j-й итерации значение (U, „) выйдет г,,м за указанный интернал, то заранее известно, что оно не является искомым. Поэтому проверка условия (9) выполняется н следующей последовательности.

1,. Если (Б „,„)> О, то условие (9) не выполнено и (U „,,„),, на регистре 17 результата присваивается значение О.

2,. Если (U„ „ )„. 1, то условие (9) также не выполнено и (U ) м,л,и на регистре 17 результата присваивается значение 1-р, где m — количество разрядов, выбранных для представления в двоичной системе счисления.

1246 полученного результата. Результат суммы при (U ) = (U, )., ра— вен 0 во всех разрядах. При (U „)„> (О „„),, на величину Г равен 0 во всех разрядах . При (U „),, ((U „„)„., на величину

F равен 1 во всех разрядах, задаваемых Я . Таким образом, условие (9) выполняется если при суммировании код суммы содержит во всех разрядах, 20

fS задаваемых, в том числе и знаковым либо все 0 либо все 1. Условие (9) не выполняется в противном случае.

Приведенная последовательность реализуется блоком 13 проверки окон- 25 чания итерационного процесса.

Управляющий сигнал режима работы узлового элемента 20-9 открывает элемент И 14 и тем самым соединяет выход блока проверки окончания итерацион- ЗО ного процесса с входом регистра 17 результата, а также элемент 2 И вЂ” НЕ 18.

На регистр 12 произведения поступает управляющий импульс 20-7 сдвига дробной части результата в сторону 35 младших разрядов. Сдвигаемая информация поступает в блок проверки окончания итерационного процесса и на второй вход одноразрядного сумматора 10 (элемент И 9 открыт). На ре- 40 гистр 17 результата подается управляющий импульс 20-8 последовательного сдвига и приема. Управляющие импульсы 20-7, 20-8 повторяются ш раз.

Таким образом, длительность второго этапа работы узлового элемента определяется m микротактами.

Блок 13 проверки окончания итерационного процесса параллельно выполняет следующую последовательность 50 действий.

Анализирует на элементе ИЛЦ-HE 25 четыре старших разряда. регистра произведения {один знаковый и три целой части (U „„)„, .

Наличие логического "0" на инверсном выходе элемента 4ИЛИ-НЕ.25 говорит о ситуациях, соответствующих пун7

3. Если (U „ )„< i, то на реI гистр 17 результата записывается значение (U )„è определяется выI полнение условия (9), которое предполагает, во-первых, получение результата (U„„„), — (П „„),, При этом (U,„ )„, представляется в до"3 полнительном коде как отрицательное число с помошью преобразователя элемента 2 И вЂ” НЕ 18. Во-вторых, анализ 10

111 8 ктам 1 и 2, вышеприведенной последовательности. Элементы 4И 2 1 и элемент

26 совпадения закрываются, а элементы 2 ИЛИ-НЕ 27, 2 ИЛИ 28 пропускают на выход блока "JIor. 0" или

"лог. 1". Наличие "лог.1" на инверсном .выходе элемента 4ИЛИ-НЕ 25 свидетельствует о ситуации пункта

3. Открытый элемент 26 совпадения соединяет выход регистра 12 произведения с входом регистра 17 результата. Элемент 4И 21 открывается тогда, и только тогда, когда поступает управляющий сигнал 20-11 задания точности результата и. пропускает импульсы сдвига/приема 20-6. Двухразрядный регистр 22 начинает последовательно записывать и сдвигать значение (U „ „)„ (U м )J в поступающее с выхода сумматора 10.

Элемент 23 сравнения осуществляв ет поразрядное сравнение поступакп е го кода. В случае несовпадения вырабатывается сигнал несовпадения "лог. который по приходу тактового синхроимпульса 20-12 запоминается на триггере 24 и происходит остановка процесса сравнения. На управляющем выходе 20-14 появляется сигнал не-выполнения условия (9). В регистр

17 результата заканчивается запись и узловой элемент готов к выполнению следующей итерации. В начале каждой итерации триггер 24 признака выполнения условия (9) у=танавливается в состояние 0 управляющим импульсом

20-13. В случае совпадения сравниразрядов (U „ )J условие (9) выполнено и процесс pev;eíèÿ завершен.

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

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

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

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

10 па выходов которого подключена к группе входов блока памяти., группа выходов значений коэффициентов уравнения которого соответственно сое-динена с первыми входами соответствующих элементов И группы, вторые входы которых являются группой информационных входов устройства, выходы элементов И группы подключены к соответствующим входам сумма- 10 тора, отличающийся тем, что, с целью повь.шения точности и быстродействия, в него введены блок проверки окончания итерационного процесса, состоящий из элемента 4И, 15 элемента 4 ИЛИ-НЕ,, элемента 2 И, элемента 2 ИЛИ-НЕ, элемента 2 ИЛИ, двухразрядного регистра, элемента сравнения и триггера, регистр суммы, пять элементов И, элемент 3 ИЛИ, 20 элемент 2 ИЛИ, элемент 2И-НЕ, оцноразрядный сумматор, регистр произведения и регистр результата, выход которого является выходом результата решения уравнения устройства.и под- ?5 ключен к прямому входу элемента И-НЕ выход которого соединен с первым входом первого элемента И и с первым входом лемента 3 ИЛИ, выход которого подключен к первому входу однораз- ЗО рядного сумматора, второй вход которого соединен с выходом второго элемента И, первый вход которсго подклю- . чен к первому выходу блока синхронизации, второй выход которого соединен с первым входом третьего элемента И, выход которого подключен к второму входу элемента 3 ИЛИ, третий вход которого соединен с выходом четвертого элемента И, первый вход кото- о рого подключен к третьему выходу блока синхронизации, четвертый выход которого соединен с входом записи регистра суммы, вход сдвига которого подключен к пятому выходу блока синхронизации, шестой выход ксторого соединен с первым входом элеменra

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

2И-HE и к девятому выходу блока синхронизации, десятый выход которого соединен со счетным входом счетчика адрес.а одиннадцатый выход блока синхронизации подключен к второму входу элемента 4 И, выход которого соединен с входом записи двухразряд— ного регистра, первый и второй выхо— ды которого соединены соответственно с первым и вторым входами элемента сравнения, выход которого подключен к информационному входу триггера, вход синхронизации которого соеди-, нен с двенадцатым выходом блока син— хронизации, тринадцатый выход которого подключен к входу установки

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

1246113

1246111

78

Составитель В.Рыбин

Редактор В.Иванова Техред О.Гортвай Корректор И.Муска

Заказ 4003/43 Тираж 67 1 . Подписное

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

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

Производственно-полиграфическое предприятие,, г. Ужгород, ул. Проектная, 4