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

 

Изобретение относится к области вычислительной техники и может быть применено автономно или в качестве спецпроцессора в мультипроцессорных вычислительных системах для оперативного решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия. Устройство содержит п блоков вычисления разрядов, П(т-1) вычислительных блоков. Блок вычисления разряда содержит два сумматора-вьгчитателй, сумматор, два элемента НЕ, элемент И, элемент сложения по модулю два и группу ключей. Вычислительный блок содержит блок вычисления разряда и блок восстановления остатка, содержащий (п-1) сумматоров-воичитателей U) и группу ключей. За счет совмещения во времени вычислительных операций с времеием переходного процесса достигается цель изобретения. 4 ял.

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

РЕСПУБЛИН

Ч.В. ЛЫЗ

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

ПО ДЕЛАЮ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

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

ЪФФ " 6 (21) 3594639/24-24 (22) 24.05.83 (46) 23.10.86. Бюл. У 39 (71) Киевский ордена Трудового Красного Знамени институт инженеров граж4 данской авиации (72) Г.Е. Пухов, А.И. Стасюк и Ф.Е. Лисник (53) 681 . 32 (088.8) (56) Авторское свидетельство СССР

Р 805336, кл. С 06 F 15/324, 1978.

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

В 836396, кл. С 06 F 15/324, 1979.

Пухов Г.Е. и др. Разрядно-аналоговые вычислительные система. М.:

Советское радио, 1978, с. 254. (54) УСТРОЙСТВО ДЛЯ РИПЕНИЯ СИСТЕИ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к области вычислительной техники и может быть

„.$0„„ДЯ79Д А 1 применено автономно или в качестве спецпроцессора в мультипроцессорных вычислительных системах для оперативного решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия.

Устройство содержит и блоков вычисления разрядов, n ° (m-1) вычислительных блоков. Блок вычисления разряда содержит два сумматора-вычитателя, сумматор, два элемента НЕ, элемент И, элемент сложения по модулю два и группу ключей. Вычислительный блок содержит блок вычисления разряда и блок восстановления остатка, содер- ф жащий (n-1) сумматоров-вычитателей и группу ключей. За счет совмещения во времени вычислительных операций с временем переходного процесса достигается цель изобретения. 4 ил. д

12657

% !

v а" =

Y х

3 (2) А. ° . А, -1 <

2 А,Х

-з

А Х +

2 АХ +2 АХ

УП ф... +2A,Х

i р ч

=-2 а Хг (4) -Ъ

+ 2

-Ъ - vvl - р р

АХ +.;, +2АХ вЂ” йр=-2аX з я 3

-г

+2 АХ

-г г

+2 AX

2 .АХ

+2 АХ+

2A.Õ

П) . + 2 А„Х

v р ч л =-2 а„Х„, й

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

На фиг. 1 представлена схема устройства для решения систем линейных алгебраических уравнений для случая, когда n ™ 3 и ш = 4; на фиг. 2 схема блока вычисления разряда; на фиг. 3 — схема вычислительного блока; !5 на фиг. 4 — схема блока восстановления остатка, Устройство для решения систем линейных алгебраических уравнений (фиг. 1) содержит и блоков 1 вычисления разрядов, п ° (m-1) вычислительных блоков 2, i,j-e входные шины 3;, (i 1, n, j = l,m), (i,n+1)-е вход ные шины 41, выходные шины результата 1-го (1 = 1,М) разряда i-ro неV K известного 5;, 6;, 7; . Блок вычисления разряда 1 (фиг. 2) содержит два где е,е (0,11, х;E (O,ll, f;6(0,1%, m — разрядность представления информации, а i = j = 1,2,...,n.

На основании компонентов разрядных векторов Х сформируем следующие векторы бинарных элементов

X (х,,х,...,х ); X = (х,х

М (х,,х ...%„) (3), благодаря которым вектор Х исходной

+2 АХ +2 АХ +

93 2 сумматора-вычитателя 8, сумматор 9, два элемента НЕ 10, элемент И ll элемент сложения по модулю два )2 и группу ключей 13.

Вычислительный блок 2 (фиг. 3). содержит блок 1 вычисления разряда, блок 14 восстановления остатка и

k-управляющих шин 15,, lб,, 17; (k=

l,...,n-l). Блок 14 восстановления остатка (фиг. 4) содержит (n — 1) сумматоров-вычитателей 18 и (и-1) группу ключей 19.

Работу матричной вычислительной структуры для решения систем линейе ных алгебраических уравнений АХ=Г порядка и для случая, когда норма матрицы А удовлетворяет условию )I D Аt)4

2

6 — поясним на конкретном примере (где А — матрица коэффициентов; Х векторы неизвестных и правых частей;

D — диагональная матрица, элементами которой являются диагональные элементы матрицы А). Запишем значения коэффициентов а;;матрицы А и компонент х и f; векторов Х и Г в разрядной форме (Э), t Е

Сформируем следуннцие матрицы бинарных элементов системы уравнений может быть записан как

Х =22 Х.

-к "

k 1

Тогда систему алгебраических уравнений АХ = Г в развернутой форме на основании (1)-(3) запишем следунщим образом:

-tn щ v i v

+2 АХ вЂ” f, =-2а„Х, 3 л торов а, которая

= 3 имеет вид

) )26579 где а;, — разрядная матрипа (З1, составленная иэ разрядных век(5) а" =

Для иллюстрации запишем первую строку уравнений в выражении (4) при шеа Зип= 2. (6) -- "Разом в соответствии с (6) (»!

j» каждая строка выражения (4) может исходной системь уравнений удовлетбыть представлена в виде ш раэрнд- воряет условию )(DALAI g3 то ка»(щый ных уравнений, по которым организу1

11 tt ем вычисление компонентов хк следую компонент х» бУдет не более 2, т.е.

-» щим образом. (х (a 2 (фактически для х. можно

Из первых разрядных уравнений записать х а (О,З 1; ь 2} . Далее аы1 выражения,(4), записанных в виде численные значения компонентов х ф (22

Š— 2а;» х» = й», .» = !,и, (7) т.е. вектор Х = (x,,х,...,х„) предопределим х . При этом считается, ставляется в выражение (4) и на осчто остаток f в выражении (4) может новании втоРых РазРЯднь»х УРавнений (»

» принимать значения соответственно вида () (») (t) - 2 () (() (2 АХ-Г - f -2а « } (, 1 < 1 (I) (Il (t) - Z 2 (» ((<» -2 (2 АХ- f f ° f --2а,х =Й, Lf (2 Iàj)

Определим значения вторых разрядов Аналогичным образом каждый } -й, к% C Ф 2 зс К К

У х, т.е. вектор Х (х,,х,...,х„) . тор Х (x,,õ,..., х„) вычисляетг.ÿ тслк .

-(r-2) к-t (.-I) (к1) (к 2) -к (r) к -к

2 АХ f f Е(— 2 ая Е< а (Е1/с 2 1а, ;

Лк- 21 к I (< I) (к-I) (к-I) к („) (к) „(9)

2 АХ вЂ” i = f f -2а f jf 1<2 (а"!

Э »»» В» 11

Алгоритм вычисления каждого компо- к-1)

К нента х из выражения (9) (т.е. ре» (к.t) и а(имеют разные знаки что мож» Ф щения разрядных уравнений вида

» (к)

М

-2 а = f:) осуществляется следующим

- .»».- а к

Знх =Зн f(" ЭЗна" (!0) к » образом. Знак х будет положителен, где Знх» — знак х. принимает эначеесли . и а" имеют одинаковые зна- ние 0, если х > 0 и — когда (tt-2) !1 tt

ft 1t

3 »1

В (» -(» ки, и отрицательным, когда значенря x < 0; Знд ы а;» знак . и

} 3

1265793!

< — 2)а; ! к

wf

2 (" (к) м (с)

F О (г)

F >0

) + гi;i (с)

3 Р 0 ((()

f а.,la

1 Знх, = Знй! g Зна„= ОЭО = О;

3 их = Знй ®Зна, =0@0 =О.

2 (а„) = 0,5664062 — 2 0,625 = 0,2539062 = F,;

-I «I (à — 2 la, J = 0,6914062 — 2 "0,8125 = 0,2851562 = F ()

Fz)0 — х, = 1, Fz)0 3 = I

2 (!) -()! (Р< ) — 2 а„ = 0,2539062 — 2 0,625 = -0,585938 = Р, (F(, )l — 2 а1 = 0,2851562 — 2 0,8125=< -0,1210938 = Р (1

F((0 - х, = О;

<) I < 2

Р, <О õ =О (!) (<2 а (г)

l Р (+ 2 )а(, = 0,0585938

+ 2 (агг! = О, 1210938 х, = х< + !

Х2 Хг +

k = 2 (,)

-((!)

f; = 2 а „ х, = 0,2539062 — 2 0,3125 = 0,0976568 = f

f,(", )= 2 а„ х, = 0,2851562 — 2 0,375 = 0,0976562 = f

1f, l — 2 jа„ = 0,0976562 — 2 0,625 = 0,0585938 = F," (f(, )I — 2 агг = 0,0976562 — 2 0,8125 = 0,1054788 = F()

2 i

2 °

F, + 2 !а„ = 0,0976562 = Г

Fz" + 2 la„j = 0,0976562

Знх,=0;х< =0+0=О.

Знхг = 0; хг = О + О = О.

k=3

Лг) 2 2 й, — 2 а„х, = 0,0976562

S а;, принимает значение "0", е(.ли

1аким образом, значение lx";) может врыть вычислено в результате реализации одной иэ строк таблицы а век

Э личина х представляется в виде к к к, суммы двух значений х<1 = x + х

) j t благодаря чему при реал эации первой

<< строки )х; = 2, Вектор „ при этом с может быть записан как Х = (x, +

<г с! сг к< 2

x< + хк + хг + < ° ° + х + х<()< а;; <О. Модуль х"; определяется в соответствии с таблицей.

Рассмотрим изложенное на конкретном примере.

0,625Xl + 0,3125X2 = 0,5664062

0,375X1 + 0,8125Х2 0,6914062

Решение х<,х2 равно соответственно

20 Xl = 0,625, X2 = 0 ° 5625. Определим, удовлетворяет ли матрица системы уравнений условию

1(8 All = 1,4615384.

+ 2 0,625 = 0,2539062 = f

+ 2 . 0,8125 = 0,2851562 = Е"; х, =1+0=1 ! g

x2 = 1+0= 1!

265793

l- 2 la„l = 0,976562 — 2 Ор625 = 0,0195312 = Г, ()У г р) У(," - 2 !а„ = 0,0976562 — 2 0,8!25 = -0,093063 = Г();

F, 0 — — х, = 1; . (М

I Π— -х = О хг = 0; ,(М ()1 -) (ъ) Р— 2 (ац,(= 0,0195312 — 2 0,625 = 0,0585938 = Г, I F О; х = О; (М

Ьт 1 + 2 а (=-0,0585938 + 2 0,625 = 0,0195312 = й, ()

+ 2 !а„! = 0,0093063 — 2 0,8125 = 0,0976562 = fz

3 нх< = 0; х, = 1 + 0 = 1 ) =

3 нх = 0; х = 0 + 0 = О, ю

k=4 ()) -Ъ з

f, -2агхг

2 !а,)

М

-0,0195312 =„f

= 0,0976562 — 2 0,375 = 0,0507812 fz

= 0,0195313 — 2 0,625 = 0,0195313 = Р");

= 0 0507812 — 2 0,8125 = 0 = F (1) 4 ) г

F (О,— х(= О,— х, = О;

F =0 x = I õ =О;

i г г

f() = 0,0195313; — О+ 0 = 0

1+0=1.

4 4

Знх = 1, х, Решение

Х = (1010) - 0,625

Х = (1001) -0,5625.

Работа устройства происходит следующим образом. ЗО

На входные шины 4<,...,4n подаются соответственно значения компонентов f,,...,f„ вектора правых частей

F решаемой сйстемы уравнений AX = F.

На входные шины 3;;(i = 1,2,...,n) 35 подаются значения диагональных элементов а;; матрицы А и на входные шины 3, (1ф1) подаются значения побочных элементов а матрицы А. Пбсле этого в схеме протекает переходной про- 40 цесс, по окончанию которого в каждом (i;-1)-м блоке вычисления разряда 1 моделируется соответственно i-я строка выражения 7, благодаря чему на выходе элемента сложения по модул два 45

12 и элементов НЕ 10(i,l)-ro блока вычисления разряда 1 и соответственно на входной шине первого разряда неизвестного по 5;, 6,, 7; таблице образуются соответственно значения г

Знх;, х;; х; первого разряда i-го неизвестного х;. На выходе сумматора 9 (i„l) блока вычисления .разряда I образуется в соответствии с (7) значе()) ние f -, поступающее на второй,инфор- 55 мационный вход сумматора-вычитателя 8 блока восстановления остатка 1 4 (i, 2 ) -го вычислительного блока 2 ° в котором моделируется i-я строка выражения (8). При этом в блоке восстановления остатка 14 вычисляется эна() - 1 (() чение f; = 2 А Х вЂ” f, а в блоке вычисления разряда 1 — соответственно (!)ю -г г (г)

f; — 2 а. х; = f; Благодаря этому на выходе элемента сложения по модулю два 12 и элементов (i,2) блока вычисления разряда I и на вьмодных шинах г второго разряда 5;, 6,, 7; образуются соответственно знак Знх., и х;, х( г 11 второго разряда i-го неизвестного Х.

А на выходе сумматора 9 на блоке вы" (а) числения разряда 1 образуется f, поступающее на второй ннформационйый вход сумматора-вычитателя (i,3)-ro блока восстановления остатка 14. Аналогичным образом в каждом i j-м блохе восстановления остатка 14 моделирчет-(к-zl -> (- ) ся выражение (9), т.е. 2 А 1 -f (к-i) э ° ° f, а в соответствующем блоке вы1 ,r-с) числения разряда 1 выражение и (1 ! — 2 а -f сумматора 9 i, j-го блока вычисления разряда 1. Образуется (к1 значение f), a на выходных шинах к к к °

g-го разряда 5., 6,, 7; i, j-го блока вычисления разряда I в соответстрнн стаблицей образуются соответственно эначейия Знх, х;, х; j-го, r х кг разряда i-го неизвестного Х.

Таким образом, за время переходного процесса в,схеме на выходных шинах 5,, 6;, ?; ).,j блоков вычис) - °

1265793 ления разряда 1 образуются i-e компоненты Х вектора АХ = F неизвестI ных Х системы уравнений АХ = F, кото. рые можно записать как

Х -=Г 2 (х + х,)

Кл1

1 1

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

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

t5 тем, что, с целью увеличения быстродействия, в него введено и (m-1) блоков вычисления разряда и и .(m -1) блоков восстановления остатка (m— разрядность представления информации) причем блок вычисления разряда дополнительно содержит два сумматора-вычитателя, элемент И, группу ключей, два элемента НЕ и элемент сложения по модулю два, причем в каждом i,j ì (i= l и; j = l,m) блоке вычисления разряда информационные выходы первого сумматора-вычитателя j i-ro блока вычисления разряда соединены с первой группой информационных входов второго

30 сумматора-вычитателя i, j-ro блока вычисления разряда, информационные выходы которого соединены с входами первого слагаемого сумматора i,j-ro блока вычисления разряда, входы второго слагаемого которого соединены с выхо-35 дами ключей группы i,j-ro блока вычисления разряда, управляющие входы которых подключены к выходу элемента И i,j ãî блока вычисления разряда, выходы знака первого и второго сумматоров-вычитателей i,j-ro блока вычисления разряда соединены соответственно через первый и второй элементы НЕ i,j-ro блока вычисления разря— да соответственно к первому и второ45 му входам элемента 11 i j-го блока вы числения разряда, i j-й блок восстановления остатка (1 = l„n; j = 2,m) содержит (n-1) сумматор-вычитатель и (n-1) группу ключей, причем в каждом i,j-м (i = l,n; j = 2,m) блоке восстановления остатка выходы ключей

k-й (k =1, и-1) группы i,j-ro блока восстановления остатка соединены с первой группой входов k-го сумматора-55 вычитателя i,j-го блока восстановления остатка, информационные выходы которого соединен,и с второй группой ходов (k +1)-го сумматора-вычитатеяя 1 j-го бпока восстановления остатка, входы i.-х (i = l,n) диагональных коэффициентов уравнений устройства соединены с первыми группами входов первого и второго сумматора-вычитателя и информационными входами ключей группы i j — х (j = l m) блоков вычисления разряда, i-я (i = l,n) группа входов коэффициентов правых частей уравнений устройства соединена с второй группой входов первого сумматоравычитателя (i,l)-го блока вычисления разряда, первый и второй входы элемента сложения по модулю два (i,!)-ro блока вычисления разряда подключены к входам знака соответственно i-й группы входов коэффициентов правых частей уравнений устройства и входам

i-x диагональных элементов уравнений устройства i=l,ï выходы сумматора т I — ãо (I = I è, I= I т-1) блока вычисления разряда соединены с второй группой входов первого сумматора-вычитателя (i,j+1)-ro блока восстановления остатка, выходы (n-I)-го сумматора-вычитателя i,j--го (i = I,п, = 2,m) блока восстановления остатка соединены с второй группой входов первого сумматора-вычитателя i,j-ro блока вычисления разряда, выход знакового разряда (n-1) -го сумматоравычитателя i,j-ro блока восстановления остатка подключен к первому входу элемента сложения по модулю два

1,j-го блока вычисления разряда, второй вход которого подключен к входу знака х-го диагонального элемента устройства, входы i 1 (i = l,п, 1

l,п; i ф 1) элементов устройства соединены с информационными входами ключей 1-й группы i,j-ro (j = 2m) блока восстановления остатка, выходы элемента сложения по модулю два, первого и второго элементов НЕ i,j-го (i= 1 n; j = 1 m) блока вычисления разряда соединены с i j-ми выходами соответственно знака и первой и второй компонентами вектора неизвестных системы уравнений устройства, первый и второй управляющие входы ключей

k-й группы (k = I,n) (i, j)-го (i I,ï;

j = 2,m) блока восстановления остатка соединены с выходами соответственно первого и второго элементов НЕ (k,j-1)-ro (k P i) блока вычисления разряда, управляющий вход k-ro сумматора-вычитателя i,j-ro (i = l,п;

Il 1265793

2,m) блока восстановления остатка соединен с выходом элемента сло1

5 g tt г

fbi /б !7 ЖУЙ

3 жения по модулю цва (k, j — ) )-го (k Ф

i) блока вычисления разряда.

1265793

151 Ю 7

Фиг, Ф

Составитель А. Чеканов

Редактор А. Ворович Техред А.Кравчук Корректор А. Зимокосов

Заказ 5667/48 Тираж 671 Подписное

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

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

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