Устройство для операции над матрицами

Устройство для операции над матрицами

Иллюстрации

Показать все

Реферат

 

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

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

COLjHAËÈÑÒÈ×ЕСКИХ

РЕСПУБЛИК

1505G06 F 15 347

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

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

2, синхровход 3, операционные блоки

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

7 ил.

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ С,. :СР

I (21) 4289562/24-24 (22) 27.07.87

-(46) 07.01.90. Вюл. У 1 (72) В.П. Якуш, В.А. Мищенко, А.A. Ленев и А.Н. Курбацкий (53) 681.32(088.8) (56) Авторское свидетельство. СССР

В 140)478, кл, G 06 F 15/347, 1 986.

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

У 1464171, кл. С 06 F 15/347,,17.07.87. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД МАТ"

РИЦАИИ

ÄÄSUÄÄ 3534 О . А1

1534470

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

5 обработки сигналов для треугольного разложения и вычисления определителя плотной (nyn) матрицы.

Цель изобретения — расширение функциональных возможностей за счет вы- 1О числения определителей плотных (nxn)матриц в поточном режиме.

Иа фиг. 1 представлена структурная схема устройства для; случая и = 3, на фиг. 2 — функциональная схема (i,j)-го операционного блока (1,j = 2,п, i =j)„ на фиг. 3 — функциональная схема (,j) -го операционного блока (i= 2,n„ j=l,п-l, i ):j), HB фиг. 4 — функциональнЯЯ схема (1,1) — го операционного. блока на фиг. 5 — функциональная схема элемента задержки, ня фиг, 6 и / †. временные диаграммы работы устройства.

Устройство содержит первую группу информационных входов 1 (j=l,n), второй информационный вход 2, синхровход 3, операционные блоки 4 (i,j= 1,и,. Ъ j).. элементы 5; задержки 1 (=1.,Π†!..„ группу и!Нформационных выходов =., (j=-l,n), гр!еп. -.-;- информяц" ;.

Онны. BI" _#_ .>,!!ÎÂ > (.!.=1 ., n -1 и ь!нфор" ма ционный выход 8 .

Операционный блок !ерпсй гру ппы

r ъ формационные B_#_0Gbt 9 и 1 О, 35

11, регистр!я 2 и ". 3, умнс.жи ель делитель 15 > тригг,:.p 6,::,ле ленты

17 и О„группу элемен ов И . 9„элемент ИК 20, выходы 21-23.

Е((1

Операционный блок второй группь> (I =. n;: 1=-1,п-1; I >j) содержит (фиг 3) информационнь!е входы 24 и

25, сичхровход 26, регистры 27-29, умножитель 3О, ьычитатель 31, триггеры 32 и 33, элементы И 34 и 35, первую группу элементов И 36, вторую групгу элементов И 37, группу элементов ИЛИ 38,, элемент ИЕ 39, выхсдь.

4О и 41„

Операционный блок(1,1) содержит (фиг.4) информационнь. е входы 42 и

43, синхровход 44, регистр 45, умножитель 46, выходы 47 и 48.

Элемент задержки (фиг. 5) содержит вход 49, синхровход 50, регистры 51 и 52, выход 53.

Б ОcHoву работы устройства пОлОжен ялГОритм разложения плОтнОЙ (п п) мят рицы А на нижнюю треугольную (n-.n)матрицу В и верхнюю треугольную (nx

in)ìàòðèöó С с единичной диагональю, т.е. А = ВС. Элементы Ь" и с" onpe

Ь(, =а;,, с1, =а„/Ь„, -!

Ь; = а;; — Ь,„с„

М!

n=i«j «

1 с; — (à; —, Ь;„,с „„.), 1i !=

1 .1а и

При этом определитель de? (А) =- b (а!

b

) ! » и, то,алгоритм треугольного разпожения (l) ня .к-м шаге вычисЕ I,. лений (л — - !,n) мо:! .= бь:т ь задан в виде следующей системы,;!!=.куррентных соотношений:. (ttI, (к-!1 а к к !! ) а. = а" - а" а !

) !К !.!

k i j „ !, О; — а :. ри i.=-1, с-.; =а., прп 1

При Описании рабОты устрокствЯ В обозна"- енин а(в скобках указывает(!! ся номер х-го рекуррентного шага, а в обозначении а — номер 1. указывает такт работы устройства.

Потоки данных на входах и выходах устройства показаны на фиг. (, временные работы устройства — ня фиг,б и 7.

Элементы а и дополнитепьный раз ряд О или 1 подаются одновременно соответственно íà m разрядов и (ш +1)-й разряд входов первой группы в последовательности, указанной при описании работы устройства.

Устройство (при п = 3) работает следующим образом.

В исходном состоянии регистры 12, 13, 27, 28, 29, 51 и 52 и триггеры

16, 32 и 33 устройства устанавливаются в нулевое состояние (фиг.б и 7).

Работу устройства рассмотрим для треугольного разложения и вычисления определителя одной матрицы (1=1).

На нулевом такте на вход 1з подаето ся элемент а», О. При этом в блоке

5 15344

4 в регистр 12 записывается значение а „= b «, которое подается на выход 6 устройства, на выходе умножителя 14 формируется значение b»», ТаК как на первый его вход подается значение b»», а на второй вход — постоянно единица.

»

На первом такте элементы а,, О

1 и а,, подаются соответственно на входы 1 и lэ. При этом в блоке 4ээ (1) формируется значение а, = с, = а(/

/а л,, которое подается на вход 25 блока 4 2, в блоке 4 3Q в регистр 27 за-, (о) писывается элемент а, 121, который подается на вход 9»блока 422, а на вход 9 2 блока 4 — дополнительный разряд О, значение b, с вьгхода 23 блока 433 подается на элемент 5 задержки. 20

На втором такте элементы аэ,, О, а, 1 и а,э, 1 подаются соответст2 венно на входы 1„1 и 1. При этом в блоке 4 формируется значение а,) = с,э = а,"!/а(„), которое пддается на вход 25 блока 4э2, в блоке 432 (Л) (О) (1) (л), формируется значение а 2 = а 2- а 21а»2 которое подается на вход 9» блока 422; а на вход 92блока 4 2 — дополнительный разряд О, в блоке 422 в регистр

12 записывается значение Ъ2», которое подается на выход 61, в блоке 4» в регистр 27 записывается значение а()

31 Э» 3 35

На третьем такте элементы а, 1 .и а, 1 подаются соответственйо на э входы 1 и 1< а на вход l 3 — нулевое значение и дополнительный разряд О. При этом в блоке 4зз в Регистр 40

12 записывается нулевое значение, в (i) (0) блок 4 3Z формирУетсЯ а э = ааЗ-а, а,, которое подается на вход 9» (1) (1) блока 4<2, а на вход 92 блока 4 дополнительный разряд 1 в блоке 4» формируется значение а(= а — а(1, а(, = .

=.b, которое подается на вход 24, блока .4,, а на вход 24» блока 42»в дополнительный разряд О, на выход 6 ) подается значение С »2 в блоке 4 22 в регистр 12 записывается значение

Ь, которое подается на вход умножителя 14, с выхода элемента 5д задержки значение Ь»» подается на втоРой вход умножителя 14, на выходе умножителя 14 формируется произведение b„ Ь 2, на выход 6 подается значение Ь 2, в блоке 4«в регистр

27 записывается значение Ь э»

7О 6

На четвертом такте на вход 1» по4 дается элемент а э, 1,1, на вход 1< нулевое значение и дополнительный разряд О. При этом в блоке 4, форми(л) (O) () (1) руется sHa »eHHe a 33 а33 а э которое подается на вход 24, блока 4 „ а на вход 24 блока 42» — дополнительный разряд О, на выход 6 . подается значение С,э в блоке 422 формируется значение а2 = а23/а, которое

1 (2) (Л) / (л)1 подается на вход 25 блока 42(, в блоке 4» в регистр 27 записывается значение b которое подается на вход

42 блока 4»» ) в блоке 4„в регистр

45 записывается значение Ъ,, которое подается на выход 6»

На пятом такте на вход 1» подаются нулевое значение и дополнительный разряд О, в блоке 4 1 формируется (2) (л) (Z ) (2) азз аэ а32а2 Ьзз, которое подается на вход 42 блока 4« значение с подается на выход 7», в блоке 4», в регистр 45 записывается значение Ь, которое подается иа выход 6» .

На шестом такте в блоке 4„» в регистр 45 записывается значение Ь з, которое подается на выход 6;, на выходе умножителя 46 формируется 3Начение опРеДелителЯ det(A) Ь»л Ьд2 "

< Ьзз, которое подается на выход 8, Аналогичным образом устройство работает в поточном режиме. Состоянне триггеров и регистров устройства в потачком режиме показаны на временных диаграммах работы устройства (фиг.6 и 7).

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

Ус тр ой с тв о для операций над матрицами, содержащее первую группу (i i)-х операционных блоков, (1,1) операционный блок, (i=1,n,n-размерность матрицы), вторую группу (i,))-х операционных блоков (i) j l,n, i> 1) причем синхровход устройства подключен к синхровходам всех операционных блоков, первый информационный вход (j,, j)-га операционного блока подклюЪ чен к первому выходу (2+),j) -ro операционного блока, i (1, j=1, n-l, i o>j, и-размерность матрицы), второй информационный вход (i,j)-го операционного блока подключен к второму выходу i +1)-го операционного блока, (i®2,n,j=),ï-l,i > j) j-й инфор1534470 мационный вход первой группы устройства подключен к первому информационному входу (n, j ) -го операционного блока (j l,n), второй информационный вход устройства подключен к второму информационному входу (п,n)ro операционного блока, первый выход (i,i)-операционного блока подключен к i-му выходу первой группы устройства у (1 1 уп) у BTopoA BbIxop, (1 р

1)-ro операционного блока подключен к (i-1)-му выходу второй группы устройства, (i 2,п), третий выход (1,1)— го операционного блока подключен к третьему выходу устройства, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия при обработке массива матриц, в него введены (и-1) элементов задержки, причем (1,1)-й 2О операционный блок содержит регистр и умножитель, второй информационный вход (i,i)-ro операционного блока подключен к выходу i-го элемента задержки, вход которого подключен к третьему выходу (i+1, i+1)-ro операционного блока, (1=1,п-1), синхровходы всех элементов задержки подключены к синхровходу устройства, причем синхровход (1,1) операционного блока подключен к синхровходу регистра, первый информационный вход блока подключен к информационному входу регистра, выход которого подключен к первому выходу блока и к первому входу умножителя, второй вход и выход Ко торого подключены, соответственно, к второму информационному входу блока и к второму выходу блока, 1534470

1534470

1534470

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

Техред И.Ходанич

Корректор И.Муска

Редактор Н. Тупица

Заказ 43 Тираж 556 Подписное

ВНИИПИ Государственного комитета по изобретениям и открь:тням при ГКНТ СССР

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

Производственно-Hçäàòåëüñêèé комбинат "Патент", г. Ужгород, ул. Гагарина, 101