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

 

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислителных машинах и устройствах обработки сигналов для умножения (n x п)-матрицы на вектор. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит m вычислительных модулей первого типа и вычислительный модуль второго типа, причем вычислительный модуль первого типа содержит пять регистров, умножитель, сумматор , триггер и элемент И, а вычислительный модуль второго типа содержит n + 1 регистров , сумматор, триггер и группу элементов И. Умножение (n x п)-матрицы на вектор осуществляется с помощью фиксированного числа m вычислительных модулей (т п). 4 ил., 1 табл. сл

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

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

РЕСПУБЛИК (я)5 G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

4 () Д о (лЭ и/m

yi=,, уи,,!=1, и;

k=0

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4819891/24 (22) 29,04.90 (46) 30.05.92. Бюл. ¹ 20 (72) В.П. Якуш, Н.А. Лиходел, B.Â. Косьянчук и А,А. Тиунчик (53) 681.325(088.8) (56) Kung Н.Т., Leiseison С.Е. Systolic Arrays (for И Sl), Sparse Matrix Proc. 1978, Society

for Inductrial and Applied Mathematics, 1979, р, 262, fig, 3 — 2.

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

¹ 1517039, кл, G 06 F 15/347, 1988. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР (57) Изобретение относится к области вычислительной техники и может быть испольИзобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов для умножения (п х n)-матрицы на вектор.

Цель изобретения — сокращение аппаратурных затрат.

На фиг. 1 представлена структурная схема устройства для умножения матрицы на вектор; на фиг, 2 — то хе, п = б, m = 3; на фиг, 3 — приемр схемы вычислительного модуля первого типа; на фиг. 4 — то же, второго типа.

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

2 информационные входы, группу информационных входов 3, первый 4 и второй 5 входы задания режима, синхровход 6, вычислительные модули 71 (i = 1, m), вычислительный модуль 7п1+1 и выход 8.

„„5Q„„1737463 А1 зовано в специализированных вычислителных машинах и устройствах обработки сигналов для умножения (n х n)-матрицы на вектор. Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит m вычислительных модулей первого типа и вычислительный модуль второго типа, причем вычислительный модуль первого типа содержит пять регистров, умножитель, сумматор, триггер и элемент И, а вычислительный модуль второго типа содержит n + 1 регистров, сумматор, триггер и группу элементов

И, Умножение (n х n)-матрицы на вектор осуществляется с помощью фиксированного числа m вычислительных модулей (rn < n), 4 ил., 1 табл.

Вычислительный модуль 7 (i = 1, m) (фиг, 3) содержит первый 9, второй 10 и третий 11 информационные входы, вход 12 задания режима, синхровход13, регистры 14 — 18, умножитель 19, сумматор 20, триггер 21, элемент И 22, первый 23, второй 24 и третий 25 выходы.

Вычислительный модуль 7m+> (фиг. 4) содержит информационный вход 26, вход 27 задания режима, синхровход 28, сумматор

29, регистры 30 (= 1, и + 1), триггер 31, группу элементов И 32 и выход 33.

Умножение (п х и)-матрицы А = (а ) на вектор Х задается выражениями:

1737463

i+2 i х вых= хвх

i+1 I а =ав

Ф

;!1

km+m уу= алх1,1=1,п:п=О,пТт — 1, j =I!.m+ l где m — целое число (m < n), которые определяются следующими рекуррентными соотношениями:! = 1, и, k = О. лТт — 1: у(" а=О у()а = yO )i + aijxj, J = km + 1, km + m, 4

i = 1, и: у(o)., у о

y1k1, = У ";+ Уп, k= 1, л7m 1, у (n/m-1) В приведенных соотношениях отношение п/m — целое число, в противном случае матрицу А и вектор X следует дополнить нулями до размерности и, при которой соотношение и /m будет целым числом.

Вычислительный модуль 7- (i = 1, m) обладает возможностью реализации функций:

i+1 ! I P у вых = у вх+ а вх х-р где х», у вх и а вх — значения соответственно

I i на первом, втором и третьем информационных входах вычислительного модуля на i-м такте; с Bx — значение на входе задания режима вычислительного модуля на i-M такте; х вы, — значение на первом выходе вычислительного модуля на (i + 2)-м такте; у вв!х — значение на втором выходе вычислительного модуля на (i + 1)-м такте; а ... — значение на третьем выходе

1+1 вычислительного модуля на (i + 1)-м такте;

P = О, n — 1 — параметр, определяемый алгоритмом.

Вычислительный модуль 7m+1 обладает возможностью реализации функции:

I+1 i i m ai

У BBIX = y BX+ y BX P BX ° где у вх — значение на информационном входе вычислительного модуля на i-м такте; фвх — значение на входе задания режима вычислительного модуля на i-м такте;

yI +, " — значение на выходе вычислительного модуля на (i+ 1)-м такте.

Вычислительный модуль 7 (i = 1, m) (фиг. 3) работает следующим образом. На входы 9, 10 и 11 подаются соответственно элементы х, у и а, которые записываются соответственно в регистры 14, 17 и 18. При

5 подаче на вход 12 единичного сигнала а= 1 элемент И 22 открывается, тактовый импульс подается на синхровход регистра 16 и обеспечивается запись элемента х в регистр

16. На выходе сумматора 20 формируется

10 значение у+ ах, которое подается на выход

24, Элемент х подается на выход 23 с задержкой на два такта. При подаче на вход 12 нулевого единичного сигнала а= О элемент

И 22 закрыт, в регистре 16 хранится ранее

15 записанный элемент х при а= 1, На входы

9, 10 и 11 подаются соответственно элементы х, у и а . На выходе сумматора 20 формируется значение у + а х, 1

ВЫЧИСЛИтЕЛЬНЫй МадуЛЬ 7m+1(фИГ, 4) ра20 ботает следующим образом. На вход

26 последовательно подаются элементы y i (i 1, 2, ...), которые записываются в регистр 301, При нахождении триггера 31 в нулевом состоянии группа элементов И 32

25 закрыта, на первый вход сумматора 29 подается элемент yi, а на второй вход — нулевое значение, на выходе сумматора 29 формируется значение элемента с, которое записывается в регистр 302. Таким образом, 30 при нахождении триггера 31 в нулевом состоянии происходит последовательная запись элементов yi в соответствующие регистры 30;. При установлении триггера 31 в единичное состояние группа элементов И

35 32 открывается, через которую на первый вход сумматора 29 подается содержимое у

I, рЕГИСтра 30в+1-ГО, На ВтОрОй ВХОД СуММатсра

29 подается содержимое yi регистра 301 и на выходе которого формируется значение у +

40+у, которое записывается в регистр 302 и подается на выход 33, Рассмотрим работу устройства для случая n = 6 и m = 3, Структура устройства и организация входного и выходного пото45 ков данных представлена на фиг, 2. На вход2 постоянно подается нулевое значение. На вход 4 в моменты времени 1=

= nk + m — 1 (k = О, n/m — 1) подается сигнал 1, в остальные моменты времени—

50 сигнал а= О, В таблице приведены состояния регистров, триггеров и значения на выходе сумматоров вычислительных модулей 71, 72, 73 и 74, а также значения на выходе 8 устрой55 ства.

Рассмотрим работу устройства при формировании элемента у1. В вычислительном модуле 71 на втором такте формируется зна- .

1737463 чение у()1о = у(о)1o+ а11х1, в вычислительном модуле 72 на третьем такте формируется значение у1о = у 10+ а12х2, в вычислитель(2) 1) ном модуле 7з на четвертом такте формируется значение у1о = у 1о = у2 1о + а1зхз, 3) (2) которое на пятом такте записывается в регистр 301 вычислительного модуля 74, а на одиннадцатом такте — в регистр 307. В вычислительном модуле 71 на восьмом такте формируется значение у» = у 11+ а14 х4, (4) в вычислительном модуле 72 на девятом-такTå формируется значение у()11 = у 11 + (5) (4)

+а15х5, в вычислительном модуле 7з н а десятом такте формируется значение у11 = у )11 = у .» + а15 х6, которое записывается на одиннадцатом такте в регистр

301 вычислительного модуля 74, в котором на выходе сумматора 29 на одинна)дцатом такте формируется значение у1 = у1 = у 1+ (1 (о +

+ у11, которое подается на выход 8 устройства. Аналогичным образом формируются остальные элементы выходного вектора (.

Последний элемент уп формируется на (2m + п /m — 2)-м такте. Период ввода элементов очередной задачи умножения матрицы на вектор равен (m + и + n /m — 1)

2 тактов, Формула изобретения

Устройство для умножения матрицы на вектор, содержащее m + 1 вычислительных матриц, где m — целое число, m < n, m < I, п — размер квадратной матрицы,! — ширина ленточной матрицы, причем первый и второй информационные входы устройства подключены соответственно к первому и второму информационным входам первого вычислительного модуля, первый и второй выходы i-го вычислительного модуля, где i =

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

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

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

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

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

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

35 второму входу элемента И и к входу синхронизации триггера, при этом (m + 1)-й вычислительный модуль содержит триггер, сумматор, регистр, сдвигающий регистр и блок элементов И, причем информацион40 ный вход (m+ 1)-го вычислительного модуля подключен к информационному входу регистра, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационному

45 входу сдвигающего регистра и к выходу (m+

t1)-го вычислительного модуля, вход синхронизации которого подключен к входу записисчитывания регистра, к входу синхронизации триггера и к входу сдвига сдвигающего реги50 стра, выход переноса которого подключен к первому входу блока элементов И, выход которого подключен к второму информационному входу сумматора, вход задания режима (m+ 1)-ro вычислительного модуля подключен

55 к информационному входу триггера, выход которого подключен к второму входу блока элементов И.

1737463

Ъ о ьГ 4 о(й

М .Р ь, о

41 ) !

° Ф ч В

О о а о о а оса

Я Я

1М Ф

s -о

«Я

Ъъ со «О

° м,4

4 p IP

g o о ъ.

«тз

a-Q Ь 4 ч о 0 Ч у o ас>ойдо

Qi, / сч < Я -" е

oIoIe а о,а < Qia

g o o oIo о о о о ) о

Hi Й H lH я!й о „о= 9 л

1

Щ

1ъ

Е м

Ъ,ц

< о

В ) г () (Ц

z о

=,3 с4

IQ 0

Kh - N .. о

: 1 Ъ-) -я

«ь

Ъ1

1 о<о З

Ъо

Ъ»

Ъ М ф

o o

1737463

y+ +pa-3+И аа pctJ

РЛ4Ф 3 ФЛК

С б б Я б (.(дна "& и а„„„., Ьл-("ак

Q2 Угу -Ра

> б-ПК -2,Лб". б (ббб бб -(i nr. -2 >k+

n>-, 2iru. а(/7)&/

n+Ze Р

e-/ ink а, а -г.nk

+ б lttL+

„0 с г и -n cm+n

Фиг. I

"<+ (гм ц х „.г-, (кббп-пн(Р(т-t С / (гефта.

8 7 6 2 (о -Ч 6 (2 б,р Ч 3 2

l3

Ос

Ose а ачба

Яу

a q

Ost

Ощ йу з

azi

Р,(М i5 о

ayl И сиБ О сс а

У М

М ау

8 у о а agq 0

44Z а б( ю с лг а зз о 2 аль 0

Ч з 0 а(д О (0

9 f6 Pl В (2

Ó6 5 к К3 Й

1737463 -2

:С

>> 3

Составитель B. Якуш

Редактор О. Спесивых Техред M,Моргентал Корректор Т, Малец

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

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

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

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