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

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

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

На фиг. 1 представлена структурная схема устройства для умножения (n х п) матриц} на фиг. 2 - структурная схема устройства для умножения () матриц} кЛ фиг. 3 - функциональная схема вычислительного модуля устройства для умножения (n x п) матриц; на фиг. 4 - функциональная схема вьшислительного модуля устройства для умножения (2x2) матриц; на фиг. 5 - временные диаграммы работы устройства для случая п 2.

Устройство для умножения матриц (фиг.1) содержит первый 1 и второй 2 информационные входы, упрг-вляющий вход 3, синхровход 4, вычислительные модули 5j(i 1,2n-1, n - размерность матриц) и выходы 6, (i 1, 2п-1).

Вычислительный модуль 5 (фиг.З) содержит первый 7,и второй 8 информационные входы, управляющий вход 9, синхровход 10, регистры 11-13, узел 14 задержки/ регистры 15; (,п) узла задержки, умножитель 16, сумматор 17, триггер 18, группу элементов И 19, первый 20, второй 21 и

0

QD

СО

СЛ

J 1третий 22 информационные выходы, управляющий выход 23.

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

CU

liO

M

(rO

с

0, i,j .. 1 ,n ;

ct;V + alikbkj 1 n } ij , 1 ,nВычислительный модуль 5 работает следующим образом.

В исходном состоянии регистры 11-13, 15; и триггер 18 находятся в нулевом состоянии. На i-м такте на входы 7 и 8 подаются соответственно элементы а и Ь, на вход 9 - нулевой сигнал и на вход 10 - тактовый импульс. При этом по заднему -фронту тактового импульса в регистры 11 и 12 записываются соответственно элементы а и b (регистры 11-13 и 15 построены на двухтактных триггерах) , на выходе умножителя 16 формируется значение а-b, которое подается на вход сумматора 17, на второй вход которого с выхода узла 14 задержки-подается нулевое значение (группа элементов И 19 закрыта нулевым сигналом с триггера 18) и на выходе сумматора 17 формируется значение а«Ъ.

На (i-H)-M такте на входы 7 и 8 подаются соответственно элементы а и Ъ , на вход 9 - единичный сигнал. При этом в регистры 11-13 записываются соответственно элементы а , Ь( и Ь, триггер 18 устанавливается в единичное состояние, на выходе умножителя 16 формируется значение а b , на выходе сумматора 17 - значение а .Ъ +с (на второй вход сумматора 17 через открытые элементы И 19 подается значение с, записанное в регистре 15п).

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

В исходном состоянии регистры 11- 13 и 15, и триггер 18 вычислительных модулей 5 устройства устанавливаются в нулевое состояние.

На входы 1 и 2 подаются соответственно элементы a jk и b к в соответ jствующие моменты времени:

i+k.n-n; 4kp -j+k-n-n+2.

(1)

93054

На выходах 6, устройства выдаются элементы с j в моменты времени

tc., nz+i+j-2.

(2)

На фиг. 1 показана организация подачи входного потока элементов av и Ъ j в моменты времени в соответствии с выражениями (1) и организа- ция выходного потока элементов с : в соответствии с выражением (2).

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

На управляющий вход 3 устройства, начиная с первого такта, пода- ется последовательно п нулевых раз- рядов, а затем последовательно п(п-1) единичных разрядов.

Рассмотрим работу устройства для п 2 (фиг.2).

На первом такте на входы 2 и 3подаются соответственно элемент b j и нулевой разряд. При этом в вычислительном модуле 5( в регистр 12 записывается элемент Ъ. 0 На втором такте на входы 1-3 по2

даются соответственно элементы а,, , Ь1( и нулевой разряд. В вычислительном модуле 5, формируется значение c(j) с(°, + а((Ъ(, (элемент с - О,

5 так как группа элементов И 19 закрыта нулевым сигналом с выхода триггера 18 и на второй вход сумматора 17 подается нулевое значение). На третьем такте на входы 1-3 по0 даются соответственно элементы aL Ь г и единичный разряд. При этом в . вычислительном модуле 5,, на выходе сумматора 17 формируется значение а21Ь22.(при вычислениях не испол ь5 зуется), в вычислительном модуле 5Z

на выходе сумматора 17 - значение ,М „(°)

с 1г, - с

2.

+ а

it a г

На четвертом такте на входы 1-3 подаются соответственно элементы , Ь121 и единичный разряд. В вычислительном модуле 5, - значение с 7/ с({ + , . в модуле 5г - ( с V. +

значение

г

21

а21ЬН

На пятом такте на вход I подает- 55 ся элемент . При этом в вычисли- тельном модуле 5, формируется значение а2г b 12 (при вычислении не используется) , в вычислительном модуле 5г . 2) 12.

с « +

а«ьгг

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

чение с

и) 22

,«) -гг

аг, Ъ,г

На шестом такте в вычислительном модуле 5j с выхода регистра 152 на выходе 6 f устройства подается значение с( с „

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

(О

(О

модуле Ь2 формируется значение с2,

Cj,+ ,, в вычислительном модуле 5} - значение a(Z- b, (при вычислениях не используется).

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

выход 6, устройства подается значе«)

ние с ,2 с,2 , а вычислительном модуле 55 формируется значение cz2z

- . L

- c21-i10

15

а21Ь

21

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

а с выхода регистра

15,

по20

ля, третий информационный выход k-ro вычислительного модуля (k 1,2п-1) является k-м выходом устройства.

2. Устройство по п. 1S отличающее, ся тем, что каждый вычислительный модуль содержит три регистра, узел задержки, умножитель, сумматор, триггер, группу элементов И, причем первый и второй информационные входы вычислительного модуля подключены соответственно к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому и второму информационным выходам вычислительного подуля и к информационному входу

Время перемножения двух (п п) третьего регистра,выход которого яв- риц равно (п2+Ап-3) тактов.ляется вторым информационным выходом

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

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

На девятом такте в модуле 5} на выход 6

г чение с1 с

на выход Ь2, вычислительном подается зна22

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

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

35

подключены соответственно к выходам группы элементов И и умножителя,

4Q первый и второй входы которого подключены к выходам соответственно первого и второго регистров, синхровход вычислительного модуля подключен к синхровходам всех регистров, тригге.с ра и узла задержки.

6193056

иия быстродействия и сокращения аппаратных затрат, управляющий в:-.од первого вычислительного модуля является управляющим входом устройства, управляющий вход 1-го вычислительного модуля подключен к управляющему выходу (i-l)-ro вычислительного моду™

ля, третий информационный выход k-ro вычислительного модуля (k 1,2п-1) является k-м выходом устройства.

10

15

по20

30

35

подключены соответственно к выходам группы элементов И и умножителя,

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

f ... f f t ... f 10 ... O..., OM OM fl«r От- auotta/n-

tm tnH iffiii ttt- itin6ti eti dm-itui

P

1 f3 0 0

4 a« flji flf2/ fe f 5«

Я

№г.2