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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифровой обработки сигналов. Цель изобретения - расширение функциональных возможностей устройства за счет перемножения трех (N <SP POS="POST">.</SP> N) - матриц. Цель достигается тем, что в устройстве, содержащем N<SP POS="POST">2</SP> однотипных вычислительных модулей, имеющих пять регистров, два триггера, умножитель и сумматор, в каждый вычислительный модуль введены три группы элементов И и две группы элементов ИЛИ. Особенностью функционирования устройства является параллельно-поточная организация вычислений. 3 ил.

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„Я0„„ (g))g G 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BT0PCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4484350/24 — 24 (22) 29.07.88 (46) 23.03.90., Вюл. И 11 (72) В.П. Якуш, С.Г. Седухин, П.И. Соболевский и Н.А. Лиходед (53) 68 1.3(088.8) (56) Авторское свидетельство СССР

И 1345211, кл. G 06 F 15/347, 1986.

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

Ф 1388897, кл. С 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ПЕРЕГйОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть испольИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифровой обработки сигналов для перемножения трех матриц.

Цель изобретения — расширение функциональных возможностей устройства за счет перемножения трех матриц. На фиг. 1 представлена структурная схема устройства для перемнбжения трех (n ° n) ìàòðèö с размерностью матриц А, В и С, n=2, на фиг. 2 — функциональная схема вычислительного модуля, на фиг. 3 и 4 — временные диаграммы рабаты устройства.

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

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

2 < и 2 третьей группы, информационные входы 34 и 3 второй группы, синхровод 4, вычислительные модули 5, 5,, 5, и 5 и группу выходов 6, и 6 устройства.

Вычислительный модуль (фиг. 2) содержит первый 7, третий 8 и второй о

9 информационные входы, синхровход

10, регистры 11-15, умножитель 16, сумматор 17, триггеры- 18 и 19, первую группу 20 элементов И, вторую группу 21 элементов И, третью 22 группу элементов И, первую группу 23 элементов ИЛИ, вторую группу 24 элементов

ИЛИ, а также первый 25, третий 26 и второй 27 выходы.

В основу работы устройства положен алгоритм перемножения трех (п. n) -ма т— риц А, В и С, который определяет ре1552200 зуль(1ирующую матрицу О, элементы ко,торой вычисляются по формуле (11 (1 а, 1= 2 . а, Ь „.с „. и

Обозначим К;,„", а, (Ъ

РЧ тогда d j =:Е 1 а q, „ (1 1 (Алгоритм вычисления значений <4 определяется рекуррентными соотноше ниями

Е О, (р) (р-()

1(+ 1Р P$ 1

1 (i c и, 1 р б и, 1 = (1 и

Алгоритм вычисления 1" определя11 тся рекуррентными соотношениями

dÄÄ =0, (%1 (q 1

11 (1

;(1 (Ц У

1а1ап, 1 i(п, q (g.

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

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

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

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

На К-м такте на вход 7 подается к элемент а, на вход 8 — нулевое значение, на вход 9„- элемент Ъ, на к в)соды 92 и 9 - нулевой разряд. При этом элемент а записывается в ре-. ,к б гистр 11, элемент Ъ вЂ” в регистр 13, нЭ выходе умножителя 16 формируется значение à b, на выходе сумматора (17 - значение а Ь, так как регистры

12

2 и 14 находятся в нулевом состоянпи и через элементы ИЛИ второй группы 24 на первый вход сумматора

1(подается нулевое значение, элемен1-( ты И третьей группы 22 закрыты, так как триггер 18 находится в нулевом состоянии..

На (К+1) -м,такте на вход 7 подаетК+1 ся, элемент (а ), на вход 8 — нулег.вое значение, на вход 9 — элемент k+(f (Ь ), на вход 9 — нулевой разряд, на вход 9 — единичный разряд . При этом в регистр 11 записывается элемент а, в регистр 13 — элемент Ь, в регистр 14 — - значение a(b, так как элементы И второй группы 21 открыты (с инверсного выхода триггера 18 подается единичный сигнал на первые входы элементов И группы 21), на выходе умножителя 1б формируется зна(,( чение а " Ь, которое подается на второй вход сумматора 17, на первый вход которого через- элементы ИЛИ второй группы 24 подается значение а Ь, на выходе сумматора 17 формируется значение а Ь + а Ь

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

Э мент d, на вход 9 — элемент С"

Э на вход 9 — единичный разряд, на вход 9> — нулевой разряд. При этом триггер 18 устанавливается в единичное состояйие, триггер 19 — в нулевое состояние, элементы И первой группы 20 и элементы И второй группы

21 открываются, в регистр 11 записывается нулевое значение, в регистр

30 t2 — элемент d, в регистр 13 - элемент с, регистр 14 устанавливается в нулевое состояние, так как на его вход установки в нулевое состояние подавался единичный сигнал с выхода триггера 19 Ä 15 записывает35 ся значение а Ъ + а . Ъ, так как на вход разрешения записи регистра 15 с выхода триггера 19 подавался единичный сигнал, на выходе умножителя

1б формируется значение (а.Ь + а Ь ).с

40 {на первый вход умножителя 16 с выхода регистра 15 через открытые элементы И первой группы 20 и элементы

ИЛИ первой группы 23 подается значеI 1 ние а ° Ь + а: Ь, а на второй вход

45 элемент с); на выходе сумматора 17 формируется значение d + (aib +

+а(Ь),с.

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

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

2, и 2 постоянно подаются нулевые

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

О д элемент a «H e eH b с двумя дон

00 6

5 15522 полнительными (в+1) -м и (m+2) — м нулевыми разрядами. При этом в вычислительном модуле 5и формируется значение f „= Е „ + а „b«(фиг. 1, 3) .

На первом такте на входы 1<, 1, 3, и 3 устройства подаются соответственно элементы а<, а,, (Ь, 0,1) ! f

1 и (b«, О, О) . При этом в вычислительном модуле 5ц формируется значение

+а, Ъ, в вычислительном моИ (о)

И Н « » - — (al дуле 5,, — значение f „= f z, +а, Ь, в вычислительном модуле 5,< — значеС» (o) ние f, = f«+ a«b«.

На втором такте на входы 14, 1

3 и 3 подаются соответственно ну1 левое значение, элементы а, (с„.

1,0) и (Ь, 0,1) . При этом в вычис лительном модуле 5 „ формируется значение й„, = с1,, +f« «) в вычислительном модуле 5д, — значение f ц = f « + (В (»

+а b,, в вычислительном модуле 5,<значение f, =г., +a«b, в вычислительном модуле 5 — значение л) (о1

+ а,Ь«. 25

На третьем такте на входы 1» и 1 подаются нулевые значения, на входы

3 и 3 подаются соответственно элементы (с, 1,0) и (с,, 1,0) . При этом в вычислительном модуле 5ц форф (о) мируется значекие d = d„ +I«c«, в .вычислительном модуле 5д — значение и = d <, + Е, с «, в вычислитель(» (0) ном модуле 5 « - BH eHHe d, = d<

=d(+f с, которое подается на выq 35 ход 6, в вычислительном модуле 5 — (М ° О) значение f <> f 22 + а22 Ь z

На четвертом такте на вход 3 подается элемент (с,1,0). При этом в вычислительном модуле 5, формиру() (a> ао ется значение Й ez. =d z +f g, m в вычислит ельном модуле 5 4 — значение

d =Й„ =Й, +Е„ с, которое пода(Ф) ется на вход 6,1, в вычислительном мо(i) дуле 5ы значение d„= del =dD +

+f с, которое подается на выход

6„..

На пятом такте в вычислительном модуле 5 формируется значение и = d =d +f z c«, которое по(м (a) дается на выход 6

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

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

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

j, i — го вычислительного модуля соеди«нен с вторым информационным входом (j+1, i) -ro вычислительного модуля, причем первый информационный вход вычислительного модуля соединен с информационным входом первого регистра, информационные входы пятого регистра и первого триггера соединены соответственно с (1,ш)-ми и (ш+1)-м и (m— разрядность элемента матрицы) разрядами второго информационного входа вычислительного модуля, выход пятого э регистра соединен с первым входом умножителя и с (1,m) ìè разрядами второго выхода вычислительного модуля, (m+1)-й разряд второго выхода вычислительного модуля соединен с прямым выходом первого триггера, выход умножителя соединен с первым входом сумматора, входы разрешения записи первого, второго и пятого регистров, первого и второго триггеров соединены с синхровходом вычислительного модуля, о т л и ч а ю щ е е с я тем, что, с целью расширенйя функциональ ных возможностей за счет перемножения трех матриц, в каждый вычислительный модуль введены три группы элементов

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

Фиг.2

, ходом (i,n) -го вычислительного моду,,ля, при этом в кажцом вычислитель-! ном модуле выход первого регистра соединен с первым выходом вычислитель5, ного модуля и с первыми входами элементов ИЛИ первои группы, выходы и вторые входы которых соединены соот,ветственно с вторым входом умнохмтеля и выходами элементов И первой группы, первые и вторые входы кото,рых соединены соответственно с прямым

:выходом первого триггера и выходом четвертого регистра, информационный вход которого соединен с. первыми входами элементов И третьей группы, вто рые входы которых соединены с прямым выходом первого триггера, инверсный выход которого соединен с первыми входами элементов И второй группы, 20 торые входы которых соединены с выодом сумматора и с первыми входами лементов И третьей группы, выходы которых соединены с третьим выходом вычислительного модуля, третий информационный вход которого соединен с информационным входом второго регистра, выход которого соединен с первыми входами элементов И второй группы, выходы и вторые входы которых соединены соответственно с вторым входом сумматора и выходом третьего регистра, информационный вход и вход установки в нулевое состояние которого соединены соответственно с выходами элементов И второй группы и с входом разрешения записи четвертого регистра, (m+2) ì разрядом второго выхода вычислительного модуля, выходом второго триггера, информационный вход которого соединен с (m+2) -м разрядом второго информационного входа вычислительного модуля, синхровход которогс соединен с входом разрешения записи третьего регистра.

1552200

1552200

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

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

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

Закаэ 332

Тираж 565

Подписное

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

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

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