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

 

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

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

РЕСПУБЛИК (19) /и) Ц1)g G 06 F. 15/347 ц 0

Нд БАЙИ! 1

Б! ГИБЛИ

ОПИСАНИЕ HSOBPETEHHR

H A BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM

IlPH П1НТ СССР 1 (21) 4659142/24 (22) 06.02.89 (46) 07, 01 . 91 . Бюл. И- 1 (72) В.П.Якуш, В.В.КосЬянчук, П.И.Соболевский и Н.A..Лиходед (53) 681.333(088.8) (56) ТИИЭР, 1987э Н 9э с. 194, рис.6.

Ramakrishnan I.V.,Fussel В.S.,Silbershatz А. Systolic matrix multiplications on à linear array. — Proc.

20 th Аппп. Allerton Conf. Commun.

Contr. and Comput., Nonticello, 0ct. 6-8, 1982, 1, р,625-626. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ

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

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

На фиг. 1 представлена структурная схема устройства для умножения (n х n) матриц, на фиг. 2 — структурная схема устройства для умножения (2х2) матриц на фиг. 3 — функциональная схема вычислительного модуля устройства для умножения (n x n) матриц, на фиг. 4 — функциональная схема выцислительного модуля устройст2 (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных для перемножения (n x п) матриц. Цель изобретения — повьппзчие быстродействия и сокращение аппаратных затрат. Цель достигается тем, что устройство содержит (2п-1) линейно связанных вычислительных модуля, каждый из которых содержит три регистра, узел задержки на и тактов„ умножитель, сумматор, триггер и группу элементов И. Особенностью работы устройства является параллельно-поточная пр- ганизация вычислений. 1 з.п.h-лы, 5 ил. ва для умножения (2х2) матриц; на фиг. 5 — временные диаграммы работы устройства для случая n - =2.

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

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

Вычислительный модуль 5 (фиг.3) содержит первый 7,и второй 8 инфор- мационные вхбды, управляющий вход 9, синхровход 10, регистры 11-13, узел

14 задержки, регистры 15; (i =1,n) узла задержки, умножитель 16, сумматор 17, триггер 18, группу элементов И 19, первый 20, второй 21 и

3 1619305 4 тре гий 22 информационные выходы, у!!гавляющий выход 23.

В основу работы устройства положен алгоритм перемножения двух (и и)

"1атриц, основанный на рекуррентных соотношениях: (о2 с> =О, i j =.1п; .<К1 М !1

i, = c + a2,kb„1, i,j,k =1,п. О (n) с ° ° =с, ij=1,п.

I)

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

В исходном состоянии регистры 15

11 — 13, 15; и триггер 18 находятся в нулевом состоянии. На i-м такте на входы 7 и 8 подаются соответственно элементы а и Ь, на вход 9 — нулевой сигнал и на вход 10 — тактовый импульс. При этом по заднему фронту тактового импульса в регистры 11 и

12 записываются соответственно элементы а и Ь (регистры 11-13 и 15 построены на двухтактных триггерах), на выходе умножителя 16 формируетея значение а ° Ъ, которое подается на вход сумматора 17, на второй вход которого с выхода узла 14 задержки-подается нулевое значение (группа элементов И 19 закрыта нулевым сигналом с триггера. 18) и на выходе сумматора

17 формируется значение а Ь.

На (i+1) м такте на входы 7 и 8 подаются соответственно элементы а ! и Ь, на вход 9 — единичный сигнал. При этом в регистры 11-13 записыI ваются соответственно элементы а

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

l < а Ь, на выходе сумматора 17 — знау ( чение а ° Ь +с (на второй вход сумматора 17 через открытые элементы

И 19 подается значение с, записанное 45 в регистре 15n) .

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

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

На входы 1 и 2 подаются соответственно элементы а,2, и b „ в соответствующие моменты времейи:

i+k n n

gik

Э

-j+k n-n+2, 12

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

t,„= n +i+ j-2. г (2) С12

На фиг. 1 показана организация подачи входного потока элементов а °

1Ц и bk в моменты времени в соответJ ствии с выражениями (1) и организация выходного потока элементов с"

IJ в соответствии с выражением (2).

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

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

n(n-1) единичных разрядов.

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

На первом такте на входы 2 и 3. подаются соответственно элемент Ь |г и нулевой разряд. При этом в вычислительном модуле 5, в регистр 12 записывается элемент Ь< .

На втором такте на входы 1-3 подаются соответственно элементы а ф 9

Ь1, и нулевой разряд. В вычислительном модуле 5, формируется значение с,2 = с и + а,1 Ь2, (элемент c = О, (о) так как группа элементов И 1 9 з акрыта нулевым сигналом с выхода триггера 1 8 и на второй вход сумматора 1 7 подается нулевое значение) .

На третьем такте на входы 1 - 3 подаются соответственно элементы а

Ь и единичный разряд. При этом в вычислительном модуле 5„ на выходе сумматора 17 формируется значение а г1 Ь 22 (при вычислениях не используется), в вычислительном модуле 5г на выходе сумматора 17 — значение (I2 (о2 с, = с г + а„Ь,, !

На четвертом такте на входы 1-3 подаются соответственно элементы а,г, Ь и единичный разряд. В выЧ. числительном модуле 51 — значение с 1t = с,, а, Ь„в модуле 5g.

Р> (2 значение сг, = с „+ а, Ьп

На пятом такте на вход 1 подается элемент а . При этом в вычислительном модуле 5, формируется значение агг Ь,z (при вычислении не используется}, в вычислительном мо5 16193 пуле 5 — значение с ; = с," + а, Ь в вычислительном модуле 5) — знащ (o) чение с = с + а, b,z .

На шестом такте в вычислительном модуле 5(с выхода регистра 15 на выходе 6 устройства подается значение c« = с «, в вычислительном д) р) модуле 5> формируется значение с, =

И с, + а, Ъ2,, в вычислительном модуле 5 — значение а(. Ь«(при вычислениях не используется).

На седьмом такте в вычислительном модуле 5 с выхода регистра 15 на выход 6 устройства подается значе(1) ние с ц = с,, в вычислительном мо(2) дуле 5 формируется значение с (1) с + а2дЬ, На восьмом такте в вычислительном модуле 5> с выхода регистра 15 по- 2О дается значение c» = с, на выход 6z .

И)

На девятом такте в вычислительном модуле 5) на выход 69 подается зна(Н чение с = с .

Время перемножения двух (n > п) мат-2g риц равно (n +4п-3) тактов. ъ

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

1. Устройство для умножения.матриц, содержащее 2п-1 вычислительных модулей (и — размерность перемножаемых матриц), причем первый и второй информационные входы первого вычислительного модуля являются соответственно первым и вторым информационными входами устройства, первый и второй информационные входы -вычислительного модуля (i. = 2,2п-1) подключены соответственно к первому и второму информационным выходам (i-1)-ro вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей,о т л и ч а ющ е е с я тем, что, с целью повьппе05 6 ния быстродействия и сокращения аппаратных затрат, управляющий в::од первого вычислительного модуля является управляющим входом устройства, управляющий вход ).-rn вычислительного модуля подключен к управляющему выходу (i-1)-го вычислительного модуля, третий информационный выход k-го вычислительного модуля (k = 1,2n-1) является 1с-м выходом устройства.

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

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

)6)9305

1 1 1 1 0" О" 0 3 5 а ар, а«с»- а„а,in " о а и

Аи- 4ию-ю для дую- 6пнбм Ь - бимбя 4

4 с„

CPuz. f

14 is Og 0f а„а„а„а„ а Zf gg If 12

1Г.;1Ч 305

Фиг. 4

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

Техред M.Ìîðãåíòàë Корректор T,Èàëåö

Редактор N.Áëàíàp

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

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

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

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