Устройство для решения систем алгебраических уравнений Советский патент 1986 года по МПК G06J1/02 G06F15/32 

11

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

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

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

устройства при решении систем алгебраических уравнений; на фиг.З временная диаграмма работы устройства.

Устройство содержит первую группу накапливаюш,их сумматоров , , I и

-In

вторую группу накапливаюш,их

п-ю

П1

сумматоров 1, , I22 jl2n

группу накапливающих сумматоров 1 . 5 Ипп умножители 2 i-й группы (,.,.,п), первая группа сумматоров 3, вторая группа сумматоров 4э третья группа сумматоров 5, чет-- вертая группа сумматоров 6, пятая группа сумматоров 7, п-я группа умножителей 8,, (п+1)-я группа умножителей З, 2п-я группа умножителей Sfis ( 1)-я группа умножителей. .. 9 ,, (2п+2)-я группа умножителей 3ii-H группа умножителей 9п ()-я .группа умножителей 10,, (Зп -2)-я группа умножителей 10, 4п-я группа умножителей Ю, п накапливающие сумматоры 11 экстраполированны значений регистры 12 невязки, первая группа элементов И 13, вторая группа элементов И 14, регистровый блок 15 памяти, содержащий п регис ров 15i (,,,.,п), дешифраторы 16, счетчики 17, триггеры 18, схемы 19 сравнения.

Представленный вариант использования устройства предусматривает выполнение его в виде одинаковых .ячеек 20,блок-сз{ема которых представлена на фиг.1. С помощью ячейки 20} производится вычисление

неизвестного х

Математически работа устройства описывается следутощет С|1стемой урав-. нений и равенств.Если обозначить через х; - вектор неизвестных вы- .численных на j шаге, vxj - вектор приращений, то в накопителях 11 формируется величина.

-I..

9 9

r jДля первой ячейки можно записать

(inV

Текущее значение невязки определяется. .

5j,,5j-Avx,. ,.

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

п 5,: -На,.. Х

(}

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

Рассогласование Sj используется для формирования нового значения приращений V X

J + Vx

. о J + 1 -т

tSj),

где g. - функция выделения m дробных разрядов, начиная со знака. Таким образом.

П

5j-Avx.,, ,

Xj.,, i

J+

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

vF

v(p.

.; ,,,:

КЧ 1

Ро ЕЧЕ-А).

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

.. ки

vF --

-Г,

9

х-и

Ь1

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

С-;|;.,

-r.fi.,г

i

соответственно в п-й ячейке вычисляется элемент

f;; -S .-s« -- p

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

« .,.pi

м9

И1-1

п.S efv-j, .

PMVF

tf

Р 1, п , .6 moJn j -

Величина J связана с номером шага. Если j ё п-1, то j, а при j п из номера шага вычитается .й,где t - число натурального ряда

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

Время работы разбито на циклы.Каж дый цикл содержит m тактов.Начало цикла в виде сигнала поступает с синхровхода устройства на счетчик 17 и триггер 18.. В результате в счетчике формируется номер шага (в данном случае первый шаг), а триггер 18 перебрасывается в 1 состояние и на выходе элемента .И 13 формируется приращение длиной m разрядов. Приращение, начиная с младших разрядов, поступает на умножитель 8, на остальные умножители приращения поступают с выходов других элементов И 13. Второй множи- ель. наносится в умножители ,накап лийающих сумматоров с выходов 1,; . Так как произведение имеет 2 m разрядов, то m старших разрядов формируется во втором цикле. Начиная с первого разряда второго цикла величина с выхода сумматора 5 поступает на умножитель 2, на вхЪды остальных умножителей поступает информация с выходов остальных (п-1) сумматоров 5. Получаемые на выходах умножителей 2, произведения складываются на сумматоре 4. .

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

1

слястолму

ри ряда.

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

., складываются на сумматоре 6. Сформированная на выходе величина пос- тупае.т на умножитель 10, на остальные умножители 10 - Ю поступают величины с выходов соответствующих сумматоров 6. На выходе сумматора 7 в первом шаге формируется прира- ()И)

20

щение

VP

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

30

35

Во втором шаге все повторяется .- Однако в связи С тем, что ко второму шагу в первом столбце регистрового блока памяти информация меняется то происходит вычисление приращения

т (

V г , J которое по сигналу с выхода дешифратора 16 добавляется к содержимому накапливающего сумматора 1 ,2 и так далее до тех пор, пока небудут скорректированы все элементы

7 матрицы 9 . Этот факт фиксируется. в счетчике 17 наличием во всех разрядах единицы, После поступления сигнала четного цикла п-го шага счетчик 17 переполняется и на выхо 5 де переноса формируется сигнал, по которому содержимое накапливающих сумматоров 112 переписывается в регистры 8j, 9,- и 10; умножителей Далее процесс корректировки элемен50 тов матрицы продолжается по

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

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

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

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

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

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

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

Подачей синхроимпульса :на тактовый вход триггер 18 перебрасывается в 1 состояние и разрешает прохождение старших m разрядов реги ра 12 на выход устройства,.которые, представляют собой величины vx,, поступающие на входы умножителей 8| каждой ячейки.На выходах умножителей 8 формируются величины д ух , .Суммируя полученные значения, формируем приращение неизвестного на (J+1)-м шаге.

VK

eCjfO

/Я

,(e.i,,,,,,i,.

Полученное приращение складывает- ;ся с предыдущим значением неизвестной в накопителе 11

,(JH)

-X,j-t- VX

)

Одновременно происходит умножение

приращений v х

e()

на коэффициен-

ты и формирование новой невязки

Sj rHl eiV 4j -,)

г-

а а VX .,, .

et {j-n)

вычисляется в сумматоре 4, а сама невязка S в сумматоре 3. Т как произведение , формируемое на выходе умно- жителей 2, имеет 2 m разрядов, то регистр невязки имеет 2т разрядов. Это позволяет не отбрасьшать m

младших разрядов невязки и вычислять ее (невязку) с точностью.меньшей

чем

ш

10

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

. И ерационньп1 процесс протекает до тех пор пока все приращения

V Xg(E 1,...,п) не окажутся рав- ными 0. Равно нулю, это значит, что все разряды приращения равны нулю, т.е. V X , 0,0,...,0.

20

Так как

85;

--2:a,;vx,j.2

-(m+0

то равенство нулю всех старших m разрядов S j..;, достигается всегда. Параллельно с итерационным процессом вычисления неизвестных х про- текает итерационный процесс вычисления корректирующей матрицы . В начале формируется промежуточная форма V F на умножителях 9 и сумматоре 6

vF;f ..a,,.S;,UHn)

t1 , если i i e 0, если i j e.

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

- ;г | ре; ргч& -)

складыва,ется с последующими значениями 9 g

16 16 &

в накапливающих сумматорах 1, .

Дешифратором 16 вырабатывается следующая последовательность стробирующих сигналов (С), по которым происходит сложение полученных приращений в соответствующем накап- .ливающем сумматоре, 1 СI - для 1JP

Ьг

С 2 - ДЛЯ 1,

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

1ц

- для 1гг

Сг - для Ijj

С,., - для1

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

С, - для1„п

Сг - для 1П1

С, - дЛя 1.,

С„ - для 1„(„.)

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

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

.

Iа

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

; Устройство для решения систем ал гёбраических уравнений .содержащее с первой по п-ю группы умножителей (где п - число переменных в системе уравнений), п накапливающих сумматоров экстраполированных значений. п схем сравнения, п сумматоров первой группы, п сумматоров второй группы, п регистров невязки, причем Быхад i-ro регистра невязки (, 2,...,п) подключен к первому входу i-ro сумматора первой группы, выход которого подключен к входу i-ro регистра невязки, а второй вход - к выходу, i-ro сумматора второй группы, входы .которого подключены к выходам i-x умножителей группа с первого по п-й вход первого сомножителя которых подключена к информационным входам устройства, отличающееся тем, что, с целью повышения быстродействия в него введены с первой по п-ю группы из п накапливающих сумматоров , с ()-и по 4 п-ю группы из

2035528

п множигелей, третья, четвертая, пятая группы из п сумматоров, регистровый блок памяти, п Ервая и , вторая группы из п элементов И, 5 п триггеров, п счетчиков, п дешифраторов J при этом синхровход устройства подключен к счетным входам триггеров к К счетным входам счетчиков, выход перепол i-ro счетчи10 ка подключен к ст1,.бирующим входам умно.жителей с (п4-1)-й по 4 п-ю группу,выход i-ro триггера подключен к первому входу i-ro элемента И первой группы, второй вход котоfS рого подключен к выходу i-ro сумматора первой группы, а выход - к первому входу i-й схемы сравнения и к входу первого сомножителя умножителей j-группы (J () ,. . , ,2п) ,

20 при этом выходы накапливающих сумматоров i-й,группы подключены к входам второго сомножителя i-x умножителей с (п -1)-й по 4 п-й групп, вь;ходы i-x множителей групп с

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

30 i-ro накапливающего сумматора экстраполированных значений, при этом i- й выход регистрового блока памяти подключен к входам второго сомножи- теля i умножителей групп с (2п +1)-й по 3 п-ю,выходы которых подключены к информационным входам i-ro сумматора четвертой группы, выход которого подключен к входам второго сомножителя i-x умножить.« лей групп с (Зп-)-й по 4 п-ю, выходы которых подключены к входам i-ro сумматора пятой группы, выход которого подключен к информационным входам п накапливающих о мматоров

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

35

50

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

фиг. 2

Цирхунщия unpoffMrttua I регистров TIj и Sij

ЛТ

(I

t iцикл I fapMupodaMue njmisteSeHua

- J (J «MM .

ФорнироВание праизвеЗени

A . S.i

MO унн 2i

pq..xxxxxxxx|

, vywvvvwJ

J XXXXXXX CX),-....,...--,,opftufx Scfiue нЛко зивугния S |.

Lxsixxxxixxxxj JMrvf//tfff S I

foai eipupoitttHuii .entHoi I3

Ргрниробание но- .йога прчрашения , Чгемоа 13

8гпорой шаг

I 3m.

5m

(1 -

foai eipupoitttHuii .entHoi I3

-Н

Третий шаг