Устройство обращения матриц

 

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

„„SU„„1429126

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

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

РЕСПУБЛИН (so 4 G 06 F 15/347

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ф а

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

Н А 8ТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 ) 4) 9202) /24-24, .(22) 05.02.87 (46) 07.10.88. Бюл. У 37 (72) В.II. Якуш, С.Г. Седухин, А.Н. Семашко, А.И. Белоус и В.В. Грицык (53) 681.32(088.8) (56) Седухин С.Г. Параллельная интерпретация прямых методов линейной алгебры. Программирование, 1984, 9 4; с. 57-68.

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

В 13870)3, кл. 0 06 F 15/347, 1986. (54) УСТРОЙСТВО ОБРАЩЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике н может быть использовано для обращения матриц.

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

1429126

Изобретение относится к вычислительной технике и может быть исполь зовано для обращения (цкп)-матриц.

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

«) «-14 < К2 } ак1 = ari /а„„, k <) <

a r} = 4".-, » ê"-л) (к} г, °

1 <1 <и 1

На фиг. 1 представлена функцио» нальная схема устройства для обраще- 15 ния (nwn)-матриц для случая n= 3, на фиг. 2 — функциональная схема (k,k,k)-ro операционного блока (k=

=l,n); на фиг. 3 — функциональная схема (k,kj, k,)-го операционного 20 блока (k, = k+1, .Е п k =1)," на фиг. 4 — функциональная схема (i, k k,)-ro операционного блока (i=

=1 рп, k) = к+1, 3+n, kTn, i ), на фиг. 5 — картина распространения 25 вычислительных фронтов.

Устройство для обращения (пхп)— матриц для случая n = 3 (фиг.l) содержит информационные входы 1, операционные блоки 2, регистры 3, эле- 30 менты 4 задержки, выходы 5.

Операционный блок 2, 1<В k, k (k=

=l,n) (фиг. 2) содержит информационный вход 6, синхровход 7, ре. гистр 8, узел 9 вычисления обратной величины числа и выход 10.

Операционный блок 2k, 1<1; Ы (К

= k+1 k+n, k=1 ï) (фиг. 3) содержит сиихровход 7, первый вход 11, второй вход 12, регистры 13 и 14, умно-. 40 житель 15, первый выход 16, второй выход 17, третий выход 18 и четвертый выход 19.

Операционный блок 2, К, lt (i =1,и, К4 = К41, К+о, К= l,п, к У К) 4б . содержит синхровход 7, первый вход

20, второй вход 21, третий вход 22, регистры 23-25, умножитель 26, вычислитель 27, первый выход 28, второй выход 29 и третий выход 30.

Элементы 4 задержки задерживают данные на два такта работы устройства.

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

В исходном состоянии регистры

3, 8, 13, 14, 23, 24 и 25 устройства (фиг. 1-4)устанавливаются в нулевое состояние (не показано).

В основу работы предлагаемого уст- ° ройства положен метод Гаусса-Жордана, при котором расширенная (nz2n)-матрица (А/El сводится к (и х2п)-матрице (Е/А "1 по рекуррентным соотно" (e/ шениям для а,, = а,, и i, $ = l,n, l,п.

n+k

i < n k с $ < n+k

<)сп

Очередность подачи элементов а„>

1 первой (m= 1 ) (пхп ) -матрицы, где — номер такта, показана на фиг. 1.

На нулевом такте элемент а „подается на вход 111 ПЭ 2441, на выходе которого формируется значение

1/а 1л !

На первом такте элементы а„и а24 подаются соответственно на входы 1 1 блока 2qz и 121В регистра Згц

В блоке 24т, фориирунтон ннаоенне а„= а„ /4и, в регистр 3у1 запи(1 (О) (М сывается элемент а .

Картина распространения вычислительных фронтов по тактам показана на фиг. 5.

На втором такте на входы 1И1 блока 2, lzzl блока 2 „и 12.11 ре° гистра 3,1 подаются соответственно элементы а, а и а 1 . В блоке 21 (42) (42) формируется значение а(= a„> /а14 в блоке 2 — а ) = а(2 - а()а () в

224 22 2Z Z1 12, j регистр 311 записывается элемент аз1 °

На третьем такте на входы 1 4 блока 2z>q, 1 „блока 2э 1 подаются

2 соответственно элементы а ь и а . В блоке 21,41 формируется значение b1 =

О)»

1/а ) так как на вход 11 постоянно подается единица (фиг. 3). В блоке 2 1 формируется значение а (1) .= а — а а„" . В блоке 2,. — значе2Ь (1) И Оба. (oj, (,) ние а = аВ, — à>1 là,, в блоке 2 - значение -1/а л)

На четвертом такте на вход 1 1 блока 22 подается элемент а . В

4 блоке 2 1„формируется значение b (1

= -а,, /а ), так как на вход 20 постоянно подается нулевое значение (фиг. 4). В блоке 2 4 формируется значение а = а -а а,>, в блоке (Л) (о) . (A (1

2 к — значение а() = a() /"., в ре(л) гистр 3„zz записывается значение а„

1 в регистр З z — значение а>"

Ж, На пятом такте в блоке 2 формируется значение Ъ = -a /a () () (. б2

1429126

45

3 так как на вход 20 постоянно подается нулевое значение (фиг. 4). В блоИ) ке 21» формируется значение аль (1) (1) (2) (2) а,ю a„«a«5, s блоке 2«4а -Ь«„= 5 (1) Z (1) («) "(,)

= Ъ« /а««в в блоке 2 > — а = а (1) (/) аМ а25 °

На шестом такте в блоке 244«фо— («) мируется значение b = b(„ ) - a(") Ь «)» в блоке 2252 — значение Ь = 1/а(л)2 1О (на вход ll постоянно подается единица в блоке 2зее — значение Ь и= (1) «)

b> -а Ь«л, в блоке 2555 — значение 1/а .

На седьмом такте в блоке 21 2 фор- !5

Мируется Значение Ьл« = — а 42 /a«2{ (На

«) () (1) вход 20 постоянно подается нулевое значение), в блоке 254 — значение

М) («) («)

Ь л = Ь,л /а 5у, в регистр 3«зь писывается значение а23 (О

На восьмом такте в регистр 345 записывается значение аль, в блоке (2)

224 формируется значение Ъ

Ы (г) (O. (б)

= b24 — а«ь Ь5!, в блоке 2 5ц — значение Ь,) = b )/a(5 ), в регистр З„ 25 записывается значение аф .

На девятом такте в блоке 2442. формируется значение Ь = Ълл — а» Ььл (о) (Ц (б) лл !») » ьл. в блоке 2255 — значение bz2 = b(E) («) . (ь)

2« а«ь Ь52, в блоке 2«еь — значение 30

Ь = 1/а (на вход ll постоянно по() . (2) дается единица)

На десятом такте в. блоке 242 форCQ (2) i ) (2)

МИруЕтСя ЗяаЧЕНИЕ ЪЛ« = Ъл« вЂ” a b» с5) -45 («) 2 в блоке 22е — значение Ъ«ь = -а

h)

«5

/а (на вход 20 постоянно подается нулевое значение).

На одиннадцатом такте в блоке 2леу формируется значение Ъл = -а„ /й (31 (2) й) (на вход 20 постоянно подается нулевое значение).

Сформированные значения элементов

Ь2! обратной матрицы А " на соответствующих тактах выдаются на выходы устройства 5 (фиг.l).

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

Устройство обращения матриц, содержащее и операционных блоков, z где пхп — размерность матрицы, причем синхровходы операционных блоков подключены к синхровходу устройства, о т л и ч а ю щ е е с я тем, что с целью повышения быстродейст.вия в него введены n +n-n onepa5 t.

2 ционных блоков, n --n регистров и п (п-1)/2 элементов задержки, причем информационный вход (l,l,l)-го операционного блока подключен к (1,1, l) — му информационному входу устройства, (i,l,l)-й информационный вход устройства (i=7,ï) подключен к информационному входу (i,1,!)-го регистра, (i,g,l)-й информационный вход устройства (i=1,n, ) =2,n) под" ключен к первому входу (i,1)-го операционного блока, выход (k,k,k)ro операционного блока (k=1,n) подключен к второму входу {k,k+1 k)-го операционного блока, выход (i,k,k)ro регистра (i, k=1,n, iPk) подключен к второму входу (i,k+I,k)-го операционного блока, второй выход (i, kI,kj-го операционного блока (i k=I, и; k> -k+I, g+k-1) подклю ен к второму входу (i,kI+l,k)-ro операционного блока, третий выход (i 1k !, k) -го операционного блока (i k,n- l,k — — k+1

Е!.и;Е=Г,п-f) подключен к третьему входу (i+1,kj,k)-го операционного блока, четвертый выход (i ?;;,k)-ro операционного блока (i=2,k, k =1+1, k+n,Е=,n) !одключен к третьему вхо ду (i-l, k,,k)-ro операционного блока, первый вьход (i i,k)-ro операционного блока (i=2 п,k--Гбп- ; =!с+1) подключен к первому входу (i,i,k+1)го операционного блока, первый выЪ

xone (i,k<,k)-го операционного блока (х =1,Г; k> =k+1, k=1,n-l) подключен к входу (i,k>,k)-ro элемента задержки, выход которого подключен к ин.формационному входу {i k> й+1)-ro регистра, первый выход (i,k;,?-.)-ro операционного блока (=1(+всрп, k> =5+1, k-=1,п-2) подключен к информационному входу (i k),k+I)-ro регистра, первый выход (з,kI,Ы)-го операционного блока (i=1,k, kq =k+2,k+n, k=1,n-l) подключен к входу (i Ö,k)-ro элемейта задержки, выход которого подключен к первому входу (k,kj 1+1)-го операционного блока, первый выход (i,k>,k)-го операционного блока (1=

=ИТрп,k> =k+2,k+n,k=1,n-l) подключен к первому входу (i,kj,k+1)-ro операционного блока, первый выход (i,J,n)-го операционного блока (i=

=I,ï, 1=йт(, 2n) подключен к соответствующему выходу устройства, синхровход устройства подключен к синхроводам операционных блоков и регистров.

2. Устройство по п. l о т л и ч а ю щ е е с я тем, что (k,k,k)-й операционный блок (k=Г,й) содержит

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

3. Устройство по п. 1, о т л и- 10 ч а ю щ е е с я тем, что (k,k;,k)-й операционнь и блок (kl =&Т,k+n,k=1,п)

; содержит два регистра и умножитель, причем первый и второй входы блока ! подключены соответственно к информа; ционным входам первого и второго ре(! гистров, выходы которых подключены соответственно к первому и второму входам умножителя, выход которого подключен к первому, третьему и чети. вертому выходам блока, выход второго регистра подключен к второму выходу блока, синхровход блока подключен к синхровходам первого H второго регистров.

4. Устройство по и. i., о т л ич а ю щ е е с я тем, что (i k,k)-й операционный блок (i=l,ri,kz=k++++n;

k=T,n,igk) содержит три регистра, умножитель и вычитатель, причем первый, второй и третий входы блока подключены соответственно к информационным входам регистров с первого по третий, синхровходы которых подключены к синхровходу блока, выходы второго и третьего регистров подключены соответственно к первому и второму входам умножителя, выход которого подключеи к первому входу вычитателя, второй вход и выход которого подключены соответственно к выходу первого регистра и к первому выходу блока, выходы второго и третьего регистров подключены соответственно к второму и третьему выходам блока.

1429 1 26

1429126 б 7.у

Фю5

Составитель M. Силин

Редактор В. Бугренкова Техред Л.Сердюкова Корректор В. Романенко

Заказ 5127/46

Тираж 704 Подписное

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

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

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