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

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных маши нах и устройствах обработки сигналов . Цель изобретения расширение функциональных возможностей устройства за счет перемножения N(nXn)- матриц (). Для этого в устройство введены 3 п2-п вычислительных модулей , каждый из которых содержит умножитель , сумматор, три регистра, триггер, восемь групп элементов И и четыре группы элементов ИЛИ. В основу работы устройства положена параллельно-поточная организация вычислений . 7-ил.

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

fl0 ИЗОБРЕТЕНИЯМ И ОЧИРЫТИЯМ

APH ГКНТ 00ОР

1 (21-) 4675483/24 (22) 11, 04.89 (46) 23,05,92, Бюл. Р 19 (72) .В.Ï,ßêóø, Н,А.Лиходед, В,B.Косьянчук и П,И,Соболевский {53} 681,3 (088.8) (56) Авторское свидетельство СССР

У 1413644, кл. G 06 P 15/347, 1988, Авторское свидетельство СССР

Р 1552200, кл, G 06 F 15/347, 1988, (54) УстРойстВО ПЛЯ ПГГИНожи(ИЯ

МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть исполь"

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

Целью изобретения является расши рение функциональных возможностей устройства за счет перемножения N матриц (N > 3), На фиг.1 представлена структурная схема устроиства для; перемножения

N матриц, на фиг,2 - организация входыаго потока элементов матриц

В<®Ъ, В®...,, В ") для 0 - четного, на фиг.3 структурная схема устройства для перемножения N матриц . для 0 4 и и 2, на фиг,4 - то же, для N. 5 и n 2, на фиг. 5 - функциональная схема вычислительного модуля, на фиг.б и 7 ;временные диа-. ,„SU„„3 735867. (g))g С,06 F 15/347

2 зовано в высокопроизводительных специализированных вычислительных маши нах и устройствах обработки сигналов, Цель изобретения - расширение функциональных возможностей устройства за счет перемножения N(nkn)-" матриц {N>3), Для этого в устройство введены 3 n -n вычислительных моду". лей, каждый из которых содержит ум" ножитель, сумматор, три регистра, триггер, aoceMb групп элементов И и четыре группы элементов ИЛИ, В основу работы устройства положена параллельно-поточная организация вычис"

- лений. 7.ил. граммы работы устройства для И =- 4 и n = 2.

Устройство для перемножения Ы мат-, риц (Фиг. 1) содержит информационные входы первой группы 1; (i = 1, n), информационные входы второй группы

2,, информационные вхо ы третьей

Ж группы 31 (3 = 1, Зп-1, синхро- QO вход 4, вычислительные модули 5;, © информационные выходы первой груп- . пы 6, и информационные выходы второй группы 7;.

Вычислительный модуль 5,) (фиг.5) содержит информационные входы 8-10, синхровход 11 умножитель 12, сумма" тор 13, регистрй 1Ф"-." Tb, триггер 17, группы элементов И 18-25, группы элементов ИЛИ 26-29, информационные выходы 30"32.

В основу работы устройства поло" жен,алгоритм,перемножения N матриц

3 . 173

С М * С") В{г) В) ) ... ° В(" который задается следующими рекуррентными со. отношениями: (Р)(ь)

О, i j 1п, р 20, 1) (Р)(К) (Р)({ - ) (P-1) (Р) с, с" +c ° Ь,„.

1) 1) 1К ){) д-ьЗ «){ " 1 эпв Р .- 2е) )1

c „ c, i, j. 1 и, p 2 N, (Р) (h)

Ч, ) (Р)(К)

В обозначении с индекс в

1) скобках р указывает номер матрицы, а индекс в скобах k - номер рекуррентного шага.

В обозначении с. индекс в (р);

11 скобках.р указывает номер матрицы, а индекс без скобок и - номер такта работы устройства.

Вычислительный модуль 5 работает в двух режимах, которые задаются зна" чением управляющего сигнала "1" или

"О", подаваемого на. вход 10ц.

В первом режиме работы управляющих единичный сигнал подается на вход 10г, При этом триггер 17 устанавливается в единичное состояние и открываются группы элементов И 18, 20 и 23. На входы 8, 9 и 10{ подают- . ся соответственно элементы с „, с „ и Ьц1,, которые записываются по зап" нему Фронту тактового импульса соответственно в регистры 14 - 16. На выходе умножителя 12 формируется зна"

1 чение Ь 1{ c „, а на выходе сумма"

1 тора 13 " значение с ык= сз{{+Ь к сз„, которое через открытую группу элементов И 24 и группу элементов ИЛИ 29 подается на выход 31. С выхода регистра 14 через открытую группу эле" ментов.И 23 и группу элементов ИЛИ 28 элемент с „ подается на выход 30. С выходов регистра 16 и триггера 17 соответственна элемент b „ и единичный сигнал подаются соответственно . на выходы 32 { и 32 вычислительного модуля.

Во втором режиме работы вычислителЬного модуля на вход 10 подается нулевой сигнал, устанавливая триггер

17 в нулевое состояние. При этом от-. крываются группы элементов И 19, 21, 22 и 25. На входы 8, 9 и 10 подают" ся соответственно элементы сь„, св{{ и Ь )1, которые записываютея соответственно в регистры 14 - 16, На выхо5867 4 де умножителя 12 формируется значение Ь „cBx а на выходе сумматора .

13 - значение с ык с + Ь щ, ° с ь ех вк

1 которое через открытую группу элементов И 22 и группу элементов ИЛИ

28 подается на выход 30, С выхода регистра 15 элемент с щ через открытую группу элементов И 25 и группу эле-

1() ментов ИЛИ 29 подается на выход 31.

С выходов регистра 16 и триггера 17 соответственно элемент b „ и нулевой сигнал подаются соответственно на выходы 32{ и 32 . Кроме того, вычислительный модуль 5 выполняет функцию передачи элементов с и c 6„ соответ зх ственно на выходы 31 и 30 вь{числи" тельного модуля с задержкой их на один такт при подаче нулевого элемен29 та b „ = 0 на вход 10 { независимо от значения управляющего сигнала на вхо, де 10< вычислительного модуля, т.е.

c g{,{)(= с и с8ык = c ), Это исполь зуется при доставке элементов с 1{ и

2 с в соответствующий .вычислительный модуль 51, устройства.

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

В исходном состоянии регистры 14З0 16 и триггер 17 вычислительного модуля 5;) устройства находятся в ну" левом состоянии. Организация подачи элементов матриц С("), В(г), В() и

B() показана на фиг. 3. На входы второй .группы 2, (i = i,n). постояннно

З5 подаются нулевые значения, На входы первой группы 1, (i = 1,n) после по- дачи элементов матрицы также постоянно подаются нулевые значения.

C нулевого по второй такты работы 0 устройства осуществляется доставка элементов c(и c (" соответственно

1{ {2 в вычислительные модули 5< и .5 путем подачи на входы третьей группы

3 устройства нулевых значений Ь,"

" = 0 (фиг,3, 6), С первого по чет!

J вертый такты работы .устройства аналогичным образом обеспечивается дос" тавка элементов с«) и c«) соответг{ га ственно в вычислительные модули 5{,{

56и 5

Йа третьем такте в вычислительном молуле 5г< Формируется значение с()({) = c(z)() . + с/{ ° Ь (.), С {{ С{{ С{{ {1 °

На четвертом такте в вычислитель Ы ном модуле 5 Формируется значение ,(г)(г),,(г)(1) +,(1), Ь(г)

{1 {{ {г z{ лительном модуле 5г - значение формула изобретения

Устройство для перемножения мат45 риц, содержащее матрицу n x и вычис" лительных модулей (и - Размерность перемножаемых матриц), причем i-й икформациокный вход (i =1,и) первой группы входов устройства подключен к

50 первому информационному входу (х, 1)"

ro вычислительного модуля, первый информационный выход (i,j)-го вычислительного модуля подключен к первому информационному входу (i,ъ+1)-го вы" числительного модуля (j = 1,и-1}, . синхровход устройства подключен к синхровходам всех вычислительных модулей, о т л и ч а ю щ е е с я тем, что, с целью расширения функ5 173586 фаъпь п«(оъ ««ъ Ь (2ъ с «2 —,2 + с и «2 У лительном модуле 5«4 - значение (2)(«1 .= (2)(o) (I) b(z)

21 С zl «i °

На пятом такте в вычислительном модуле 5 2 формируется значение

+ ®, b® в вычисС « ю С «« + С И ii Ф ли тел ь ном модуле 5 2 - значение ()" = с")" +,(«) Ь() в в.. - 1О

С 12 «2 «2 2гj лительном модуле 5 « - значение (21() + с(» ° b (2» в вычисС2 = С 2«+ Сzz 2«ю лительном модуле 5« - значение (М («) (2И ) («) (2)

t5

С22 С22 + С.2««2

На шестом такте в вычислительном модуле 52< ««ъормируется значение

+ с() b() в выч слис 12 — 12 + ii "i2 вычисли тельном модуле 52 - значение 2О

+ с(). Ь в вычисС «С 1«+ С «2 zi «В ВЫЧИС лительном МОдуле 5 - значение (S)() + с(z) Ь() в вычислиС 2«С2 + С 2 Ь - В ВЫЧИСЛИ тельном vnpype 5,4 - значение .С(2"2) = с()(«) + с(l b(2)

z2 2г гг 22 °

На седьмом такте в .вычислительном модуле 5 формируется значение ()(г) = ()() + с(2) ° b() в вь«чис30 лительном модуле 5 24 — значение (4) (i) (4) (о) (З) Ь (4) с1 с«+ сii Ь ««в Вычис лительном модуле 5,« - значение () («) (6) (« {2) Ь (3)

22 Z« 12 ° лительном модуле 5 - значение З5 (3)(2) (Ъ)(«) + (z) b($)

С2« = с2«+ сzz Ьг«

HB восьмом такте в вычислительном модуле 52 формируется значение ц с «+ с «2 21 лительном модуле 5 2 - значекие (4)(«) (4)() + Р) ° Ь (4» в гч с«2 = с «2 + с«« ° «2 е В вычис лйтельном модуле 54 - значение (ъ) (z) (ъ) («» + (2) Ь (3)

С 22 =. С 22 + CZZ ° 22 t В ВЫчис» лительном модуле 5«4 - значение (4) («) (4) (б) (Ъ) Ь (4)

= Z> + С2« « °

На девятом такте в вычислительном модуле 5,г4 А«.р««ируется значение,(4)() = с(4)() + с Ю, b() в вычислительном модуле 5<> - значение (4)(2) (4)(«) + () b(4) в вычисС2(= С2« + Czz. zi ф BbWHC лительном модуле 5 - значение с 22 = с 2 + с2, (41 () (4)() (ъ) b Ф 15 вычислительного модуля 5уг за)ьи(4) (4) (z) сывается значение с 4« = с i, 7 б

На десятом такте в вычислитеЛьном модуле 5«4 формируется значение (q) (zl (4 ъ (il (2) (4) сгг = с ) + с 2г bzz, e Регистр

22

15 вычислительного модуля 5«2 запи(4) (4)(2) сывается значение с 21 = с 2«, в регистр 15 вычислительного модуля (4) (4) (2)

5 - значение с 42 с«2 в ре» гистр 15 вычислительного модуля 52 значение с(4), которое подается на

И ) выход второй группы 7> устройства.

На одиннадцатом такте значение с записывается в регистр 15 вы(4)

29 числительного модуля 51>, значение с() - в регистр 15 вычислительного

Ю (4) модулЯ 5  значение с z« " B Регистр

15 вычислйтельного модуля 5<<, которое подается на выход второй группы 7 устройства, (4)

На двенадцатом такте значение с записывается в регистр 15 вычисли(4) телького модуля 5«2, значение с ъ в регистр 15 вычислительного модуля

5,, которое подается на выход второй группы 7 устройства. и)

На тринадцатом такте значение с записывается в регистр 15 вычислительного модуля 5 и подается на выход второй группы 7< устройства.

Таким образом, с десятого по тринадцатый такты осуществляется доставка соответствующих элементов с(4)

«) (i,j = 1, 2) к соответствующим выходам второй группы « (i = 1, 2} устройства.

При перемножении «« матриц (И - не«» четное) элементы с " формируются на соответствующих выходах первой группы 6; (i = 1,и) устройства (фиг.4), 7 17 циональных возможностей за счет перемножения 0 матриц (0 p3) в устройство введены 2 n -n вычислительных модулей, причем первый информаЧионныд еыход (ь,к)-го еычиспитепьноге модупя (k n, 3n-2) подключен к первому информационному входу (i, k+1)-го вычислительного модуля, первый информационный выход (i, 3n-1)-го вычислительного модуля подключен кi-му выходу первой груп((ы выходов устройства, -й информационный вход второй группы входов устройства подключен к второму информационному входу. {i, 3n-1)-го . вычислительного мо" дуля, второй информационный выход (ь 1 -го еычиспитепьного модуяя (1 е 2,3п-1) подключен к второму информационному входу (i 1"1}-ro вычислительного модуля, вторые инФормационные выходы (i,1)-х вычис" лительных модулей образуют вторую .группу выходов устройства, третья группа информационных входов которого образована третьими информаци3 867 8 онными входами (n,m)-x вычислительных модулей (ш -".1, 3п-1), третий информационный выход (р,ш)-го вычислительного модуля (р,Г,n) подключен, к третьему информационному входу (р-1,m)-ro вычислительного модуля,, причем каждый вычислительный модуль выполняет функцию, описываемую сле-"

О дующими выражениями:, К с в

Д сю если р 1; !

d =*.а+Ъс е=Ь если в - О, где а, Ь и с — значения соответственно на первом, втором и третьем щ информационных входах вычислитель" ного модуля на Ь-м такте, й,е u f— . значения соответственно на первом, втором и третьем информационных выходах вычислительного модуля на д (В+1)-м такте, g - значение (m+1)-ro разряда се

1735867

1735867

1735867

1735867

1735867 Фиг.1 в

Составитель И,Голиков

Техред М.дидык . Корректор С.Шекмар

Редактор О.Юрковецкая

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

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

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

W OHOOSW

Проиэводственно-иэдательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101