Устройство для перемножения матриц Советский патент 1992 года по МПК G06F15/347 

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

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

На фигj представлена структурная схема устройства для перемножения N матрицТ на фиг.2™- организация входного потока элементов матриц

В&, BwBW для N - четного j

на фиг.З структурная схема устройства для перемножения N матриц для 2, на фиг. - то же, для N 5 и п 2J на фиг. 5 - функциональная схема вычислительного модуля, на фиг.6 и 7 - ременные диа-j

граммы работы устройства для N А и п 2.

Устройство для перемножения N матриц (фиг. 1) содержит информационные входы первой группы 1j (i 1, п), информационные входы второй группы 2j, информационные входы третьей группы 3 (j 1, Зпт1), синхро- вход , вычислительные модули 5;: , информационные выходы первой труп- . пы 6; и информационные выходы второй группы 7;.

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

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

М

00

ел

00

о -Kj

С («I- CI( -B(. задается следующими отношениями:

(Р)(о) СЧ

of

„м

Ч

И

в ij скобках р указывает номер матрицы,

а индекс в скобах k - номер рекуррентного шага.

В обозначении с

(И Ч

индекс в

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

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

В первом режиме работы управляющих единичный сигнал подается на вход 10g. При этом триггер 17 устанавливается в единичное состояние и открываются группы элементов И 18, 20 и 23, На входы 8, 9 и 10, подаются соответственно элементы c uft свх и Ьвх, которые записываются по зад15 тельный модуль 5 выполняет функцию передачи элементов с. и с 6х соотве ственно на выходы 31 и 30 вычислительного модуля с задержкой их на один такт при подаче нулевого элеме

20 та b 6Х 0 на вход 10 независимо от

значения управляющего сигнала на вхо , де 102 вычислительного модуля, т.е. и cL., cL. Это испольс вык с вх

свых сех

зуется при доставке элементов сбх

25 сВу в соответствующий вычислительный модуль 5{| устройства.

Устройство при N - 4 и п « 2 (фиг. 3) работает следующим В исходном состоянии регистры 1 16 и триггер 17 вычислительного модуля 5 ij устройства находятся в нулевом состоянии. Организация подачи элементов матриц С, , В(3г и ) показана на фиг. 3. На входы второй группы 2; (i 1,п) постоян

30

uivy|« VXril| jriiilUI& | н- tl /I1WVI4SS11

нему фронту тактового импульса соот- 35 подаются нулевью значения. На входы

ветственно в регистры Ь - 16. На выходе умножителя 12 формируется значение Ьад с е,, а на выходе сумма

тора 13 значение с

вых

сйх+Ь

&х -вх

первой группы 1 } (i 1 ,п) после подачи элементов матрицы также постоянно подаются нулевые значения.

С нулевого по второй такты работы устройства осуществляется доставка

которое через открытую группу элементов И и группу элементов ИЛИ 29 подается на выход 31. С выхода регистра И через открытую группу эле- ментов И 23 и группу элементов ИЛИ 28 элемент подается на выход 30. С выходов регистра 16 и триггера 17 соответственно элемент ЪБх и единичный сигнал подаются соответственно на выходы 32) и 32. вычислительного модуля,

Во втором режиме работы вычислительного модуля на вход 10g подается нулевой сигнал, устанавливая триггер 17 в нулевое состояние. При этом открываются группы элементов И 19 21, 22 и 25, На входы 8, 9 и 10 подаются соответственно элементы сЈк, с вх и Ь&х которые записываются соответственно в регистры 1 - 16. На выхо1735667

де умножителя 12 формируется значение b

бх свх а на выходе сумматора

13 - значение с

вых

ьх

+ Ъ

вас

в

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

ментов ИЛИ 29 подается на выход 31. С выходов регистра 16 и триггера 1 соответственно элемент Ь&х и нулевой сигнал подаются соответственно на выходы 32 и 322. Кроме того, вычисли5 тельный модуль 5 выполняет функцию передачи элементов с. и с 6х соответ ственно на выходы 31 и 30 вычислительного модуля с задержкой их на один такт при подаче нулевого элемен0 та b 6Х 0 на вход 10 независимо от

значения управляющего сигнала на вхо- , де 102 вычислительного модуля, т.е. и cL., cL. Это испольс вык с вх

свых сех

зуется при доставке элементов сбх

и

сВу в соответствующий вычислительный модуль 5{| устройства.

Устройство при N - 4 и п « 2 (фиг. 3) работает следующим обр азом„ В исходном состоянии регистры 16 и триггер 17 вычислительного модуля 5 ij устройства находятся в нулевом состоянии. Организация подачи элементов матриц С, , В(3г и ) показана на фиг. 3. На входы второй группы 2; (i 1,п) постоянно

uivy|« VXril| jriiilUI& | н- tl /I1WVI4SS11

подаются нулевью значения. На входы

5 подаются нулевью значения. На входы

0

первой группы 1 } (i 1 ,п) после подачи элементов матрицы также постоянно подаются нулевые значения.

С нулевого по второй такты работы устройства осуществляется доставка

ДО

с « с л

соответственно

элементов cv и

в вычислительные модули и 5

г Згз путем подачи на входы третьей группы

3 устройства нулевых значений bj: 5 о (фиг,3, 6), С первого по четвертый такты работы .устройства аналогичным образом обеспечивается доставка элементов с и с соответственно в вычислительные модули 0 и .

Нэ третьем такте в вычислительном модуле 5«л формируется значение 3(о + сР,

С С ( . f С/,, D t .

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

с.Ь, в вычис- $25 значение

ссг)(г U)d с « с « лительном модуле

(o

c

+ с , в вычислительном модуле 5н знамение («НО в («Но) ч cW.bW .

С 2, С г - С Z(. D „ .

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

С«И ШС««Л + cWb(;}. в вымис- лительном модуле значение

СМ( )«) + CW h(J B вычис- с «. с -л см ьгг в вычис лительном модуле 5 & - значение

) + ГСО ,ь (г) в вычиг- с 4i с гг °г в вычис

(«И C2i лительном модуле 5,5 значение

ШО (Н«) (0 (г)

с ггс ггс 21 Dia

На шестом такте в вычислительном

модуле 5г Нормируется значение

c(S« - c(Ste) + c«;, Ь(5. в вычисл тельном модуле значение

с(ад ссз)0) +c(j.b«, В8ЫЧИСлительном модуле 5(2 значение „(з10)

г

) .bJ,.B вычислительном модуле 5 значение ,.СгНг)

гг

с(г)(0 + с(0, ь(«) с jz сгг D22

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

+ cU.bgfв вычислительном модуле 524 значение

С(4НО- fc c(ju-) + СЫ. btj)f8 вычис.

лительном модуле 5 -значение

c«W -c(W +с«, bff, в вычис- лительном модуле 5 is - значение

сй)() сйК«) + CW, b() с «i c «j + сгг Dai

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

(Н«) ()(0 (Я ,) с н с М + с ъг| в вычислительном модуле значение

c(j)(l) c(4)(rt +С).Ъ(4), ввычис.

лительном модуле 5 значение -WW СЫ(0 + Pfe) . ЬЙ) ВЫцИсС - С -t- С гг « D2 , В ВЫЧИС

лительном модуле 5(4 значение

.(4)0) (4) (в) + Ы. ь(4)

с-г1 сг« + с D«

На девятом такте в вычислительном модуле 5-24 Формируется значениес -с Й(0 + сМ.Ъ«1, в вы- числительном модуле значение C14)U) .C(jj0) cg. bW, в вычис- лительном модуле 5fj - значение СИ|0) . CWW + СЫ, bWf в регистр t5 вычислительного модуля . записывается значение с

(4) 11

(4)(г) с ц .

35867

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

(4(0 (Я it4)

см. e c A + cl,Ј. Ь„, в регистр 5 15 вычислительного модуля запи. (4Н«)

сывается значение с

10

25

35

40

45

50

г

с

«

регистр 15 вычислительного модуля (4) ()()

Ьг - значение с с,а

в ре55

гистр 15 вычислительного модуля 54( (41

значение су4 , которое подается на выход второй группы 7V Устройства.

(1) 2%

На одиннадцатом такте значение

записывается в регистр 15 вы15 числительного модуля 5. значение с ;1 - в регистр 15 вычислительного

/41

модуля значение с( в Регистр 15 вычислительного модуля 5 , которое подается на выход второй груп- 20 пы 7 устройства,.

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

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

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

При перемножении N матриц (N - нечетное) элементы с W формируются на соответствующих выходах перв.ой группы 6j (i - 1 ,п) устройства (фиг.). Формула изобретения

Устройство для перемножения матриц, содержащее матрицу nx n вычислительных модулей (п - размерность перемножаемых матриц), причем 1-й информационный вход (1 1,п) первой группы входов устройства подключен к первому информационному входу (itt)- го вычислительного модуля, первый информационный выход (i,j)-ro вычислительного модуля подключен к первому информационному входу (i.j+l)-ro вычислительного модуля (j 1,n-l), синхровход устройства подключён к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью расширения функциональных возможностей за счет перемножения N матриц () в устройство введены 2 па-п вычислительных модулей, причем перёый информационный выход (i,k)-говычислитель- ного модуля (k п, Зп-2) подключен к первому информационному входу (1, k+l)ro вычислительного модуля, первый информационный выход (Ј, Зп-1)-г вычислительного модуля подключен к i-му выходу первой группы выходов устройства, i-й информационный вход второй группы входов устройства подключен к второму информационному входу (i, Зп-1)-го вычислительного модуля, второй информационный выход (1Л1-го вычислительного модуля (1 2,Зп-1) подключен к второму информационному входу (1,1-1)-го вычислительного модуля, вторые информационны выходы (i,l)-x вычислительных модулей образуют вторую группу выходов устройства, третья группа информационных входов которого образована третьими информационными входами (,n,m)-x вычислительных модулей (т 1, Зп-l), третий информационный выход (р,т)-го вычислительного модуля (р 2,п) подключен, к третьему информационному входу (р-1,т)-го вычислительного модуля, причем каждый вычислительный модуль выполняет функцию, описываемую еле- дующими выражениями:.

f с;

d а е Ь+ас

d .а+Ъс е b

е

} }

если

если

и в 1;

о,

где a, b и с - значения соответственно на первом, втором и третьем

20 информационных входах вычислительного модуля на h-м такте, d,e и f - , значения соответственно на первом, втором и третьем информационных выходах вычислительного модуля на

25 (Ь+1)-м такте, g - значение (т+1)-го разряда с,

со un er

Г-.

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