Узловой элемент цифровой сетки для решения краевых задач Советский патент 1986 года по МПК G06F17/13 

12А61

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

JJrrij-trrt

d

.v)-p§

т f(S,r);

qvS.t) Тш.,

dT.

iT.ot (s.t )T,(S.T: )-T(s,T) ,l,.()

jmriT

N-gir n :

(x, ,Xj,Xj),

T.,

45.

при

L I

мац.

(5)

(6)

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

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

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

Блок 13 проверки окончания итерационного процесса содержит элемент 4И 21, двухразрядный регистр 22, элемент 23 сравнения, триггер 24,

0

5

0

5

30

40

45

50

112

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

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

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

iMOKC

V.,. b к,н-и„,,,, +Р,,,,„, (7)

где ,2,,3; ,2 п - момент времени, для ко торого производится расчет Uf,h,M индекс М указывает на масштабное представление индексиро- ванн ых переменных, которые всегда сводятся к следующим численным интервалам

.,n,

«.- и.1

. 1 F, О 4b, 5 1

и заведомо представлены в дополнительном коде.

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

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

Решение системы уравнений выполняется методом итераций. При этом узловой элемент использует на j-й итерации значения U, , определенные в {j-1)-M приближении. Таким образом уравнение (7). для вычисления Up.,B j-M приближении .необходимо записать так

iV l..,MV,- (8) + г

ih.M

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

/(uJ.,M-i -. и.,.,м V, / . . (5)

где

заданная точность результата.

55

Последовательность действий, производимых в узловом элементе на одной итерации, можно условно разделить на два этапа. Первый - это собственно решение уравнения (8) и получение значения (и„ ) на нака iМI М

ливающем регистре 12 произведения и второй - поразрядная перезапись ре- зультат-а и регистра 12 произведения в регистр 7 результата с одновремен ной проверкой условия окончания итерционного процесса в блоке 13 проверки окончания итерационного процесса Первый этап состоит из m циклов в каждом из которых п тактов, и еще одного такта, где m - это. длина двоичного кода

U;,,, И Ь;,,

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

Для получения конечного результата необходимо повторить столько циклов, сколько разрядов содержит код Ь| и столько тактов в цикле, сколько разрядов имеет код U. а также произвести суммирование | к1 свободным членом

fn о м которое про.изводится за°1 такт работы.

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

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

и Ь.,, (и;,,,,„ V, 1.

Очевидно, что максимально возможное значение, получающееся в регистре 12 произведения при суммировании шести значений bj U, , может

быть равно 6.

Следовательно, при использовании двоичной системы исчисления для исключения ошибок переполнения регистр 12 произведения помимо m разрядов для дробной части числа должен быть дополнен тремя двоичными разрядами, а таг-же, учитывая использование дополнительного кода при суммировании Г ilU- b- и F одним знаi к «к ,п,ГА (K,h f.n.M

KOB6IM разрядом.

b.

Суммирование результата Г Г U- „.

I К j П( Г

Ь,- , полученного за m циклов, с кодом F |, производится по окончании последнего цикла в течение еще одного дополнительного такта работы. Для представления одинаковым образом слагаемых код F дополнен тремя разрядами целой части, в которых за46111

писаны тоже коэ4|фициенты, что и в знаковом разряде.

Первый цикл реализуется в узловом элементе следующим образом. 5 Управляющий импульс 20-10 с блока 11 поступает на счетный вход счетчика 2 адреса, на выходах которого устанавливается Адр 1, соответствующий ячейкам памяти с младшими 10 разрядами Ь- .

1 iM

На группе элементов И 3.1-3.6 происходит поразрядное умножение га-го разряда bj на т-и разряд

il,K,M

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

20 ка 11 результат суммирования принимается на трехразрядный регистр 6 суммы. Далее производится поразрядное сложение содержимого регистра 6 суммы и регистра 12 произведения

25 на одноразрядном сумматоре 10 и размещение результата на ре-гистре 12 произведения путем повторения т+5 раз управляющего сигнала 20-6 с блока 11, который обеспечивает сдвиг

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

Управляющий сигнал 20-2 с блока 11 отключает выход регистра 6 от входа одноразрядного сумматора 1C, когда все три разряда суммы просуммированы с разрядами регистра

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

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

Второй такт отличается от первого толькЬ тем, что на группу информа35

0

5

ционных входов устройства 19.1-19.6 поступают m-l разряды Uj , что достигается круговым сдвигом на регистре результата соседних с данным узловых элементов. Соответственно происходит круговой сдвиг (управляющий сигнал 20-8) значения ( ), расположенного на регистре 17 результата рассматриваемого узлового элемента.

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

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

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

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

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

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

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

«; 10

15

Ю

5 0

5 0

5 0

5

116

Посчитаем разнипу: (m+1)(m+4)+ -i-2m+3-(га-1) (m+5) -5 (m-1) (m+4-m-5) + f2m+3-5. -(m-1)+2m+2 m-r.

Второй цикл и.все последующие отличаются от первого цикла тем, что счетчик адреса увеличивает свой код на единицу и на входы элементов .И 3.1-3.6 поступают следующие разряды в последнем такте при 4-м сдвиге регистра 12 произведения закрывается вход одноразрядного сумматора 10 управляющим сигналом 20-11 с блока 1i, что обеспечивает чистоту получения переноса в старший разряд регистра 12 произведения.

Результатом ffi циклов является f U; Ь,к,„ . Далее, в течение одного такта работы происходит суммирование с кодом Р,, м . Для чего производится т+4 кратное повторение управляющих импульсов 20-6 и 20-10, при открытом элементе И 4 управляющим сигналом 20-3 и закрытых элементах И 7 и 2 И-НЕ 18 соответственно управляющими сигнгшами 20-2 и 20-9.

Как видно за m циклов будет сэкономлено m(m-1) микротактов работы устройства. На суммирование с F будет затрачен.о (т+4) микротакта. Тогда экономия времени выполнения первого этапа составляет m(m-1) - -(m+4)(m-1)(m-1)-5 микротактов.

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

Характерно, что искомое значение UiU с 1, Поэтому, если на j-й итерации значение ( выйдет за указанный интервал, то заранее известно, что оно не является искомым. Поэтому проверка условия (9) выполняется в следующей последовательности.

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

2 „ Если (Uj и и j ° условие (9) таюке не выполнено и (U ). .

m, h,M

на регистре 17 результата присваивается значение l-p где m - количество разрядов, выбранных для представления в двоичной системе счисления.

7

3. Если (U)j 1, то на регистр 17 результата записывается значение (,)j и определяется выполнение условия (9), которое предполагает, во-первых, получение ре- зультата (),. - (и„,),, . При этом (, )j, представляется в дополнительном коде как отрицательное число с помотгью преобразователя элемента 2 И-НЕ 18. Во-вторых, анализ полученного результата. Результат суммы при (и )j. ()j., равен О во всех разрядах. При

-Um,n,M)j (U,,, а величину равен О во всех разрядах. При

и.п,«,м)/ Ur,r,,M Vi на величину f равен 1 во всех разрядах, задаваемых f . Таким образом, условие (9) выполняется если при суммировании код суммы содержит во всех разрядах, задаваемых , в том числе и знаковым либо все О либо все 1. Условие (9) не выполняется в противном случа

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

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

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

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

Анализирует на элементе ИЛЦ-НЕ 25 четыре старщих разряда регистра произведения (один знаковый и три целой части ()/;.

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

ктам 1 и 2, вышеприведенной последовательности. Элементы 4И 21 и элеме 26 совпадения закрьшаются, а эле- менты 2 ИЛИ-НЕ 27, 2 ИЛИ 28 пропускают на выход блока лог. О или лог. 1. Наличие лог.1 на инверсном выходе элемента 4ИЛИ-НЕ 25 свидетельствует о ситуации пункта 3. Открытый элемент 26 совпадения соединяет выход регистра 12 произведения с входом регистра 17 результата. Элемент 4И 21 открывается тогда, и только тогда, когда поступает управляющий сигнал 20-11 задания точности результата и. пропускает импульсы сдвига/приема 20-6. Двухразрядный регистр 22 начинае т последовательно записьтать и сдвигать значение (U)j - ( ),, , поступающее с выхода сумматора 10.

Элемент 23 сравнения осуществляет поразрядное сравнение поступающе - го кода. В случае несовпадения ръфа- батьшается сигнал несовпадения лог. 1, которьй по приходу тактового синхроимпульса 20-12 запоминается на триггере 24 и происходит остановка процесса сравнения. На управляющем выходе 20-14 появляется сигнал не-- вьтолнения условия (9) . В ре.гистр Г/ результата заканчивается запись и узловой элемент готов к выппнению следующей итерации. В начале каждой итерации триггер 2 признака выполнения условия (9) устанавливается в состояние О управляющим импульсом 20-13. В случае совпадения сравниваемых разрядов (и). -(U)j., условие (9) выполнено и процесс решения завершен.

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

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

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

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

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

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

19J 9-Г

/9-3 79- 19-5 19-6

го-з

t f f

о-п

)

ZO-3

JzO-5

zo-f

20-S

2о-;з го-ц

J-f

3-2

3-5

3-6

ЫГ

3

n

2 IV

20-5

20-2

20-1

2(7-5

20-7

/3

Фмг./

го-6

2(7-1

21

-

23

20-/J -

3772:

ZO-7V

-

Фмг.г

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

2 ; /1-

Составитель В.Рыбнн Редактор В.Иванова Техред О.Гортвай Корректор И.Муска

Заказ 4003/43 Тираж 671 . Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и oткpыти 113035, Москва, Ж-35, Раушская наб .,, д. 4/5

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

Фиг. 3