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

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

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

На фиг. 1 представлена структурная схема устройства для перемножения трех (п-п)-матриц с размерностью матриц А, В и С, , на фиг. 2 - функциональная схема вычислительного модуля, на фиг. 3 и 4 - временные диаграммы работы устройства.

Устройс1во для перемножения трех (п«п)-матриц (фиг. 1) для содержит информационные входы 1, и 14 первой группы, информационные входы

2( и 2г третьей группы, информационные входы 3 и 32 второй группы, син- хровод 4, вычислительные модули 5, , 521 и 52i и группу выходов 6, и 6Z устройства.

Вычислительный модуль (фиг. 2) содержит первый 7, третий 8 и второй 9 информационные входы, синхровход 10, регистры 11-15, умножитель 16, сумматор 17, триггеры 18 и 19, первую группу 20 элементов И, вторую группу 21 элементов И, третью 22 группу элементов И, первую группу 23 элементов ИЛИ, вторую группу 24 элементов ИЛИ, а также первый , третий 26 и второй 27 выходы.

В основу работы устройства положен алгоритм перемножения трех (гьп)-млт- риц А, В и С, который определяет реСП

ел ю го

эуль ирующую матрицу D, элементы которой вычисляются по формуле

и

d,,i 2П 21 ajpbpa.Co,: .

Jр« гт J

Г

Обозначим fja 21aJpbp( ,

7 тогда d «j 2L ,

Алгоритм вычисления значений Јц определяется рекуррентными соотношениями

Ч

О,

.(Р

г(р-«)

, 1ЈрЈп, 1 q n ,

Алгоритм вычисления d;: определя- Јтся рекуррентными соотношениями

о,

СИ

ij

ЈЧр(и

, , .

При описании работы устройства я обозначении в скобках индекс i указывает номер рекуррентного шага, а в обозначении а индекс i - номер т|акта работы устройства.

Вычислительный модуль работает следующим образом,

В начальный момент регистры 11-15 и триггеры 18 и 19 устанавливаются в нулевое состояние (не показано). Регистры 11-15 и триггеры 18 и 19 изменяют свое состояние по заднему фронту тактового импульса.

На такте на вход 7 подается к

элемент а ченяе, на

на вход 8 - нулевое зна- 9 4 - элемент Ь , на

вход

9л и 9« - нулевой разряд. При

к этом элемент а записывается в pejгйстр 11, элемент Ьк - в регистр 13, на выходе умножителя 16 формируется значение а-b, на выходе сумматора 17 - значение а -Ь1 , так как регистры 1Ј и 14 находятся в нулевом состоянии и через элементы ИЛИ второй группы 24 на первый вход сумматора Г/ подается нулевое значение, элементы И третьей группы 22 закрыты, так как триггер 18 находится в нулевом состоянии.

На (К+1)-м такте на вход 7 подается элемент (а1 ) , на вход 8 - нулевое значение, на вход 9 - элемент

(Ь )

к-н

на вход 9г - нулевой разряд,

0

5

0

5

30

35

40

ся нулевое значение.

jK+4Д

мент d , на вход 9 50

на вход 9 единичный разряд. При этом в регистр 11 записывается элемент а , в регистр 13 - элемент b , в регистр 14 - - значение , так как элементы И второй группы 21 открыты (с инверсного выхода триггера 18 подается единичный сигнал на первые входы элементов И группы 21), на выходе умножителя 16 формируется значение а Ь , которое подается на второй вход сумматора 17, на первый вход которого через элементы ИЛИ второй группы 24 подается значение а-Ь, на выходе сумматора 17 формируется значение + a -b1.

На (К+2)-м такте на вход 7 подаетна вход 8 - эле-Ki-a элемент С ,

на вход 9 - единичный разряд, на вход 9з нулевой разряд. При этом триггер 18 устанавливается в единичное состояние, триггер 19 - в нулевое состояние, элементы И первой группы 20 и элементы И второй группы 21 открываются, в регистр 11 записывается нулевое значение, в регистр 12 - элемент d, в регистр 13 - элемент с, регистр 14 устанавливается в нулевое состояние, так как на его вход установки в нулевое состояние подавался единичный сигнал с выхода триггера 19, в регистр 15 записывается значение а-Ь + a Ь1, так как на вход разрешения записи регистра 15 с выхода триггера 19 подавался единичный сигнал, на выходе умножителя 16 формируется значение (a-b + a1-b )-c (на первый вход умножителя 16 с выход регистра 15 через открытые элементы И первой группы 20 и элементы ИЛИ первой группы 23 подается значение а.Ь + а .« b , а на второй вход - 45 элемент с), на выходе сумматора 17 формируется значение d + ( + + а ,- Ь ),-с.

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

В начальный момент регистры 11-15 и триггеры 18 и 19 вычислительных модулей 5 и , 5 ,Ј , 54 и 5 7г устанавливаются в нулевое состояние. На входы 2 , и 2,, постоянно подаются нулевые

55

t

значения.

На нулевом такте на входы 1д и 3 устройства подаются соответственно элемент а.,, и элемент Ь.. с двумя до515522006

олнительными (т+1)-м и (т+2)-м ну- дулей (п - размерность матриц), кажлевыми разрядами. При этом в вычислительном модуле 5(1 формируется значение f f + а „

(фиг. 1, 3).

На первом такте на входы 1(, 1, 3, и 3 устройства подаются соответственно элементы , а, , (Ь , 0,1) и (Ь,г, О, 0). При-этом в вычислительном модуле 5( формируется значение IQ u i° +a(( B вычислительном могг J Р t

дуле 52 - значение г2, f,

в вычислительном модуле 54я ffO f(ol MJ

+a4t b 14 , - значение

«г

/:

11

+ а,

ta . На втором такте на входы 1, 1г, 3, и 3 подаются соответственно нулевое значение, элементы , (с, 1,0) и (, 0,1). При этом в вычислительном модуле 5 „ формируется значение d +f1(c,() в вычислительном модуле 52, - значение f f ( + +амЦ, , в вычислительном модуле - значение f i лительном модуле 5„„

й - 1+а«Ьл- ь

На третьем такте на входы 1 и 1j подаются нулевые значения, на входы 3 и Зт. подаются соответственно элементы (с , 1,0) и (с|, , 1,0). При этом в вычислительном модуле 5„ формируется значение d1 , c4i , в -вычислительном модуле 5 „( - значедый из которых содержит пять регистров, умножитель, сумматор и два триг- ера, причем первый информационный 5 вход (i,1)-ro вычислительного модуля (i Т7п) соединен с i-м входом первой группы информационных входов устройства, второй информационный вход (1,1)-го вычислительного модуля соединен с i-м входом второй группы информационных входов устройства, син- хровход которого соединен с синхро- входами всех вычислительных модулей, первый выход (i,j)-ro вычислительно20

+а,а Ьг2 ,

в вычис- - значение

iOl j(°

2

го модуля (, n-1) соединен с первым информационным входом (i, j + 1)-ro вычислительного модуля, второй выход j, вычислительного модуля-соединен с вторым информационным входом (j+1,i)-ro вычислительного модуля, причем первый информационный вход вычислительного модуля соединен с информационным входом первого регистра, 25 информационные входы пятого регистра и первого триггера соединены соответственно с (1,т)-ми и (т+1)-м и (т - разрядность элемента матрицы) разряда ми второго информационного входа вычислительного модуля, выход пятого регистра соединен с первым входом умножителя и с (1,т)-ми разрядами вто рого выхода вычислительного модуля, (т+1)-й разряд второго выхода вычислительного модуля соединен с прямым

30

ние d( + t2l cm в вычислительном модуле 5л - значение d d +f{/i с 21 , которое подается на выход 6, , в вычислительном модуле 5,- - 35 вькодом первого триггера, выход умно- (г)мLi

значение f

22.

f2V + a2.2-b2Z.

На четвертом такте на вход 3 подается элемент ( Э1,0). При этом в вычислительном модуле 5Л, формирул -л (01

d т -О.

40

12.

вычислительном модуле 5 4л - значение

dW хл

,1г d , которое подается на вход 6,, в вычислительном, коС JjC 3 Л(Л

дуле 5гг - значение д, d2l d u + которое подается на выход

ttНа пятом такте в вычислительном

модуле 5гг формируется значение гг. dzz +Јггс1-2. которое подается на выход 6г.

На фиг. 3 показано состояние регистров 11-15 и триггеров 18 и 19 вычислительных модулей устройства для перемножения трех матриц в потоковом режиме.

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

Устройство для перемножения матриц, содержащее п вычислительных можителя соединен с первым входом сумматора, входы разрешения записи первого, второго и пятого регистров, первого и второго триггеров соединены с синхровходом вычислительного модуля, отличающееся тем

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

45 модуль введены три группы элементор Й-, две группы элементов ИЛИ, причем третий информационный вход (i,1)-ro вычислительного модуля соединен с i-м входом третьей группы информаци50 окных входов устройства, третий выход (i,j)-ro вычислительного модуля соединен с третьим информационным входом (i,j-H)-ro вычислительного модуля, (т+2)-й разряд второго инфор55 мационного входа (1,1)-го вычислительного модуля соединен с (т+2)-м разрядом 1-го входа второй группы информационных входов устройства, 1-й выход которого соединен с третьим выQ

дый из которых содержит пять регистров, умножитель, сумматор и два триг- ера, причем первый информационный 5 вход (i,1)-ro вычислительного модуля (i Т7п) соединен с i-м входом первой группы информационных входов устройства, второй информационный вход (1,1)-го вычислительного модуля соединен с i-м входом второй группы информационных входов устройства, син- хровход которого соединен с синхро- входами всех вычислительных модулей, первый выход (i,j)-ro вычислительно0

С

го модуля (, n-1) соединен с первым информационным входом (i, j + 1)-ro вычислительного модуля, второй выход j, вычислительного модуля-соединен с вторым информационным входом (j+1,i)-ro вычислительного модуля, причем первый информационный вход вычислительного модуля соединен с информационным входом первого регистра, 5 информационные входы пятого регистра и первого триггера соединены соответственно с (1,т)-ми и (т+1)-м и (т - разрядность элемента матрицы) разрядами второго информационного входа вычислительного модуля, выход пятого регистра соединен с первым входом умножителя и с (1,т)-ми разрядами второго выхода вычислительного модуля, (т+1)-й разряд второго выхода вычислительного модуля соединен с прямым

0

5 вькодом первого триггера, выход умно-

вькодом первого триггера, выход умно-

жителя соединен с первым входом сумматора, входы разрешения записи первого, второго и пятого регистров, первого и второго триггеров соединены с синхровходом вычислительного модуля, отличающееся тем,

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

модуль введены три группы элементор Й-, две группы элементов ИЛИ, причем третий информационный вход (i,1)-ro вычислительного модуля соединен с i-м входом третьей группы информациокных входов устройства, третий выход (i,j)-ro вычислительного модуля соединен с третьим информационным входом (i,j-H)-ro вычислительного модуля, (т+2)-й разряд второго информационного входа (1,1)-го вычислительного модуля соединен с (т+2)-м разрядом 1-го входа второй группы информационных входов устройства, 1-й выход которого соединен с третьим выи t 0 I 7JJ/0

Мп ,пnйпп п п п n n j

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифровой обработки сигналов. Цель изобретения - расширение функциональных возможностей устройства за счет перемножения трех (N ^. N) - матриц. Цель достигается тем, что в устройстве, содержащем N² однотипных вычислительных модулей, имеющих пять регистров, два триггера, умножитель и сумматор, в каждый вычислительный модуль введены три группы элементов И и две группы элементов ИЛИ. Особенностью функционирования устройства является параллельно-поточная организация вычислений. 3 ил.

Редактор В.Петраш

Составитель К.Кухаренко

Техред Л.СердюковаКорректор В.Кабаций

Заказ 332

Тираж 565

ВМИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Подписное