Устройство для решения систем алгебраических уравнений

Авторы патента:

G06J1/02 - дифференциальные анализаторы

G06F15/32 - Цифровые компьютеры вообще (конструктивные элементы G06F 1/00-G06F 13/00); оборудование для обработки данных вообще (нейронные сети для обработки данных изображений G06T)

Изобретение относится к цифровой вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия устройства. ; Скорость сходимости итерационного решения системы уравнений в данном устройстве определяется нвличиj -2 2 -2 НОИ q f. , ,„ , что в 2 (J + On раз больше, чем скорость сходимости итерационного процесса у У стройствапрототипа. J + 2 1 - 2 (J 1)п где п - число переменных. Устройство содержит накапливающие сумматоры, умножители, блоки сумматоров, регистровый блок памяти , дешифраторы, счетчики, триггер, схемы сравнения, элементы И. 3 ил. Л

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

NIIMWN

РЕСПУБЛИК ге а»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTI

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

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

/ Й,, ц Ц, ф

1 /

2" -2 (j + 1)n (21) 3741955/24-24 (22) 16 ° 05.84 (46) 07.01.86 Бюл. 9 1 (7.1) Таганрогский радиотехнический институт им.В.Д.Калмыкова (72) В.Е.Золотовский и P.Â.Êîðîáêîâ (53) 681.325.(088.8) (56) Авторское свидетельство СССР

У 682902, кл. G 06 F 15/32, 1979.

Цифровые дифференциальные анализаторы.Сб.перев. с англ./Под ред.

Б.Я .Когана., Л.: l973.

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

9 710044, кл. С 06 F 15/32, 1980. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ .

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ. (57) Изобретение относится к цифровой вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения систем линейных алгебраических уравнений. (5» 4 G 06 1 1/02 G 06 F 15

Цель изобретения вЂ” повышение быстродействия устройства.

Скорость сходимости итерационного решения системы уравнений в данном устройстве определяется величиj+2

2 вЂ” 2 ной с (. ), Что в раз больше, чем скорость сходимости итерационного процесса у устройствапрототипа. где n вЂ” число переменных.

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

1203552

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

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

На фиг. 1,показана блок-схема устройства„ соответствующая реализации одного (первого) уравнения системы алгеораических уравнений; на фиг. 2 вЂ” блок-схема устройства при одном варианте использования устройства при решении систем алгебраических уравнений; на. фиг.3 временная диаграмма работы устройства.

Устройство содержит первую группу накапливающих сумматоров < „ вторую группу накапливающих сумматОроВ 1 1 1 gg ) ° ° р 1 1 и ю группу накапливающих сумматоров 1 „

1nz,,1... умножители 2; i-й группы (i=1,...,n), первая группа сумматоров 3, вторая группа сумматоров третья группа сумматоров э, четвертая группа сумматоров 6, пятая группа сумматоров 7, и-я группа умножителей 8,, (и+1)-я группа умножителей 8, 2п-я группа умножителей

8р, (2n + 1) -я группа умножителей

9,, (2п 2)-я группа умножителей 9>, Зп-я группа умножителей 9п (Зп+1)-я .группа умножителей 10, (Зп 2)-я группа умножителей 10, 4п-я группа умножителей 10„, и накапливающие сумматоры 11 экстраполированных значений регистры 12 невязки, перJ вая группа элементов И 13, вторая группа элементов И 14, регистровый

2 блок 15 памяти, содержащий и регистров 15 „„ (K=1,...,n), дешифраторы

16, счетчики 17, триггеры 18, схемы

19 сравнения.

Представленный вариант использования устройства предусматривает выполнение его в виде одинаковых .ячеек 20 вЂ” 20>,блок-схема которых представлена йа фиг.1. С помощью ячейки ?01 производится вычисление неизвестного х; °

«1атематически работа устройства описывается следующей системой урав-. нений и равенств. Если обозначить через х вЂ” вектор неизвестных вы) .численных на ) шаге, ух, вЂ” вектор приращений, то в накопителях 11 формируется величина.

Для первой ячейки можно записать э 3 ,(1, Текущее значение невязки определя1О ется

Ь „ э -Avx „ Ф!

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

5,(„=5, -7 д,;,(;„) . где ." вЂ” функция выделения ш дробных разрядов, начиная со знака.

Таким образом, э

Ь „=5--Ачх,, ) о

r x3„„= Р (6J 1;

3 чх „= Р„ х„.,; х .=х + x

)4j

Для формирования обратной матрицы используется следующий,интерационный. процесс

4О чР„,"-Р,А Е; ., " х "х+,, Р.=E (а-s j.

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

5Q ячейке элемент

9х 1 K yФ3

11 li i во второй ячейке вычисляется элемент

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

Рассогласование S> используется для формирования нового значения привЂ” ращений 7х

1203552

2((Zi «> 21 ° 1 23 соответственно в п-й ячейке вычисляется элемент

3а один шаг вычисляется один столбец приращения матрицы P, поэтому

К+3 И

Р,;а; ер . ес Зр л е вЂ” е3 F р ер 3, е

P = 1 <3 > .0 = ВОЛ „j 3- 3

Величина 2 связана с номером шага. Если j n-1, то I-=j а при

> n из номера шага вычитается .t„,где t вЂ” число натурального ряда.

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

Время работы разбито на циклы.Каждый цикл содержит m тактов,Начало цикла в виде сигнала поступает с синхровхода устройства на счетчик 17 и триггер 18.. В результа те в счетчике формируется номер шага (в данном случае первый шаг), а триггер 18 перебрасывается в

"1" состояние и на выходе элемента .И 33 формируется приращение длиной

m разрядов. Приращение, начиная с младших разрядов, поступает на умножитель 8, на остальные умножители приращения поступают с выходов других элементов И 13. Второй множи тель. наносится в умножители 8„,накапливающих сумматоров с выходов 1 «

Так как произведение имеет 2 ш разрядов, то ш старших разрядов формируется во втором цикле. Начиная с первого разряда второго цикла величина с выхода сумматора 5 поступает на умножитель 2, на входы остальных умножителей поступает информация с выходов остальных (n-1) сумматоров 5. Получаемые на выходах умножителей 2< произведения складываются на сумматоре 4.

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

4 имеет 2 m разрядов,,то регистр

12 имеет 2 ш разрядов, поэтому ш

4 младших разрядов рассогласования > получающихся во 2-м цикле не участ-! вуют в формировании приращения. Это достигается тем, что по сигналу "Начало второго цикла" триггер 18 перебрасывается в нуль и закрывает элемент И 13. Одновременно со схемами 8; умножения в первом цикле начинают работать схемы 9 умно1 жения.. Множимые поступают с выходов регистров 15, множители хранятся в регистрах 9; умножителей и заносятся туда из накапливающих сумматоров 1„ . Полученные произведения

11 складываются на сумматоре 6. Сформированная на выходе величина поступает на умножитель 10, на остальные умножители 10< вЂ” 10„ поступают величины с выходов соответствующих сумматоров 6. На выходе сумматора

7 в первом шаге формируется npupa(j «)

Щение Г3 - н которое по сигналу с выхода дешифратора 16 складывается с содержимым накапливающего сумматора 1<г, в первом цикле второго шага. Каждый шаг содержит два цикла вЂ” нечетный и четный циклы.

Во втором шаге все повторяется;

Однако в связи с тем, что ко второму шагу в первом столбце регистрового блока памяти информация меняется то происходит вычисление приращения й+1)

35 ч < 3, которое по сигналу с выхода дешифратора !6 добавляется к содержимому накапливающего сумматора

1, и так далее до тех пор, пока не будут скорректированы все элементы

40 матрицы Р . Этот факт фиксируется. в счетчике 17 наличием во всех разрядах единицы, После поступления сигнала четного цикла п-го шага счетчик 17 переполняется и на выхп45 де переноса формируется сигнал, по которому содержимое накапливающих сумматоров 1 > переписывается в регистры 8 „ 9; и 10; умножителей.

Далее процесс корректировки элеменаов матрицы Р продолжается по описанному выше алгоритму. Параллельно с процессом формирования обратной матрицы выполняется интерационный процесс вычисления неизвестных х.Отыскание неизвестных продолжается до тех пор пока приращения чх „не станут равными нулю. Этот факт фиксируется с помощью и схем сравнения

3 1203552 с нулем, Если приращение равно нулю, то на выходе схемы сравнения с нулем появляется единичный сигнал и работа устройства прекращается.

Искомые переменные формируются в накапливающих сумматорах 11 путем суммирования приращений, пос тупающих, на их входы.

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

Первоначально в блок 15 памяти и одновременно в умножители 2 всех ячеек заносятся коэффициенты а, матрицы А. Затем в накапливающие сумматоры 1 записываются коэффициенты Р, матрицы У = Е+(Е-а)..

В регистры 12 всех ячеек записываются свободные члены b„ .

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

Подачей синхроимпульса на тактовый вход триггер 18 перебрасывается в "1" состояние и разрешает прохождение старших m разрядов регистра 12 на выход устройства,.которые представляют собой величины v x,, поступающие на входы умножителей 8, каждой ячейки.На выходах умножитео лей 8 формируются величины 9 V x„ .

Суммируя полученные значения. формируем приращение неизвестного на (j+1)-м шаге. младших разрядов невязки и вычислять ее (невязку) с точностью меньшей чем 2 щ . Для того чтобы разрядная сетка не увеличивалась при вычисле ниях и в устройстве не возникал устойчивый колебательный процесс при котором приращения тх принимают значения + А,, где A вЂ” const, разрядность приращений ограничивается

10 величиной m, т.е. вычисления неизвестных ведутся с точностью 2

Ограничение разрядности приращения осуществляется с помощью И 13 и триггера 18. Как следует из диаграммы (фиг.?) элемент И 13 необходимо открывать только в нечетных циклах. Это осуществляется с помощью счетного триггера 18, который на каждый нечетный синхроимпульс перерабатывается в единичное состояние., И ерационньп процесс протекает до тех пор пока все приращения

7 х (Х =1,...,n) не окажутся рав2с ными О. Равно нулю, это значит, что все разряды приращения равны нулю, т.е. Ч х, = 0,0,...,0.

Так как 6 1 -а х „ 2 г1 <(„)вЂ” то равенство нулю всех старших m разрядов Sj+< достигается всегда.

Параллельно с итерационным процессом вычисления неизвестных х про35 !текает итерационный процесс вычисления корректирующей матрицы

В начале формируется промежуточная форма V F на умножителях 9 и сумматоре 6.1(a>) tj «()и) Одновременно происходит умножение

1: э приращений х z(„ i на коэффициен- .4 ты а ; и формирование новой невязки

1, если е

О, если i ф е.

Затем окончательная величина коррекции элементов матрицы Р а

50 вычисля в накапливающих сумматорах 1 (8

Дешифратором 16 вырабатывается следующая последовательность стрцПолученное приращение складывает,ся с предыдущим значением неизвестной в накопителе 1 1 ется в сумматоре 4, а сама невязка

S > < в сумматоре 3. ТЯк как произведение, формируемое на выходе умножителей 2, имеет 2 m разрядов, то регистр невязки имеет 2 ш разрядов. то позволяет не отбрасывать m складывается с последующими значениями Р;е

С0 p,JIH 110 для ячейки 2

С 1 вЂ” для 177

С2 для 1

2 2 .„+ 2 Я1 Д

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

Устройство для решения систем алгебраических уравнений содержащее с первой по и-ю группы умножителей (где n - -число переменных в системе уравнений), и накапливающих сумматорон экстраполированных значений и схем сравнения, и сумматоров первой группы, п сумматоров второй группы, и регистров невязки, причем выход i-ro регистра невязки (i--1, 2,...,n) подключен к первому входу i-го сумматора первой группы, выход которого подключен к входу

i-го регистра невязки, а второй вход вЂ” к выходу I,-ro сумматора.второй группы, входы :которого подключены к выходам i-x умножителей

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

У группы из и накапливающих сумматоров, с (n+ 1) -й по 4 и-ю группы из

7 бирующих сигналов (С), по которым происходит сложение полученных приращений в соответствующем накап;ливающем сумматоре 1

C1 вЂ” для 1<

С для 1 z

С, вЂ” для 17

С„- для 1 для ячейки и

С, вЂ” gJIH 1„„

С7 для 1 и

С1 вЂ” дйя 1„

Сh для 11(„1

После появления и сигналов счетчик 17 вырабатывает специальный сигнал, по которому содержимое накапливающих сумматоров 1 ; записываются в умножители Se> 9 е и 10e .

Полная асимитотическая скорость ,сходимости итерационного процесса в предлагаемом устройстве определяется величиной

1203552 8 п умножителей, третья, четвертая, пятая группы нз и сумматоров, регистровый блс". памяти, первая и вторая группы из п элементов И, и триггеров, п счетчиков, и дешифраторов при этом синхровход устройства подключен к счетным входам триггеров н к счетным входам счетчиков, выход перепол ния 1-го счетчи1о ка подключен к сто.. бирующим входам:.: умножителей с (п+1} вЂ” и по 4 п-ю группу,выход i-ro триггера подключен к первому входу i-го элемента

И первой группы, второй вход которого подключен к выходу 1-го сумматора первой группы, а выход вЂ” к первому входу -й схемы сравнения и к входу первого сомножителя умножителей j -грчппы (j = (и+1),. ° .92n), при этом выходы накапливающих сумма-с1ов i-й групйы подключены к входам второго сомножителя 1-х умнож. телей с (n +1)-й пс 4 и-й групп, выходы 1-х умножителей групп с

25 (и+1)-i по 2 и-ю подключены к входам i-го сумматора третьей группы

) выход которого подключен к входам второго сомножителя умножителей с первой по и-ю группы и к входу

i-ro накапливающего сумматора экстраполированных значений, при этом и выход регистрового блока памяти подключен к входам второго сомножителя i ë умножителей групп с. (2п +

+1)-й по 3 и-ю выходы которых под"

1 ключены к информационным нходам

i ro сумматора четвертой группы, выход которого подключен к входам второго сомножителя д-х умножителей групп с (3n i)-й по 4 п-ю, выходы которых подключены к входам

i-го сумматора пятой группы, выход которого подключен к информационным входам и накапливающих сумматоров

i-й группы,стробирующие входы которых подключены к выходам с первого по и-й i-ro дешифратора, входы которого подключены к выходам i-го счетчика, а (n + 1) -й ныход вЂ” к первому входу i-ro элемента И второй группы, второй вход которого подключен к входу управления коррекцией содержимого матрицы экстраполяции устройства, а выход вЂ” к стробирующему входу i- ro сумматора четвертой

55 группы, второй вход i-й схемы сравнения подключен к шине нулевого потенциала устройства.

1203552

1203552 фиреумщир мчроряаоции о региотри ф и 5Ч. лг Ъл Я/% Фнг &ф Ела

1у

И ции вЂ” 1 2-о циня И циая - 4 4 s ° ° ° е» дд г1иня «а»

Фарииробаное лроооЫенир Форноробоние яроиздеденм 1

1, Фцанирайык фяийИицо лг 1рж i

Яу не унн. g.i .о уингi

I l

I 1форнидрфоа,е npwa еФнж но уин2<

Форниро4рае мяЬго гна а ни» $

1Щ ущрфои е нуйа значения S