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

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

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

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

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

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

Вычислительный модуль 7т+1 (фиг. 4) содержит информационный вход 26, вход 27 задания режима, синхровход 28. сумматор 29, регистры 30j (i 1, n + 1), триггер 31, группу элементов И 32 и выход 33.

Умножение (n x п)-матрицы А { aij } на вектор X задается выражениями:

V|

GO XI

О GO

У

n/m

Ј У. k 0

l 1,n;

km +m

Yik 2) aiJXj

j km + 1

1, n; k 0, n/m - 1,

где m - целое число (m n), которые определяются следующими рекуррентными соотношениями:

i I, n, k 0, n/m - 1:

yMik o, n

y0)jk yC-i),. + a|jx j km + 1, km + m,

$&v

y. yi(n/m-1)

Vik, k 1, n/m- 1,

В приведенных соотношениях отношение n/m - целое число, в противном случае матрицу А и вектор X следует дополнить нулями до размерности п1, при которой соотношение n /m будет целым числом

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

J+2

X ВЫХ

X вх.

™ i + 1 „

d вых - и вх

yi+1Bb,x yiBx + aiBx.xi-pi P

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

а вх - значение на входе задания режима вычислительного модуля на i-м такте;

i+2

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

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

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

Р 0, n - 1 - параметр, определяемый алгоритмом.

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

у вых У вх + у втс РВХ где у вх - значение на информационном входе вычислительного модуля на i-м такте;

уЗ вх, - значение на входе задания режима вычислительного модуля на i-м такте;

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

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

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

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

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

Вычислительный модуль 7т+1 (фиг. 4) работает следующим образом. На вход 26 последовательно подаются элементы у i (i 1, 2, ...), которые записываются в регистр 30i. При нахождении триггера 31 в нулевом состоянии группа элементов 1/1 32

закрыта, на первый вход сумматора 29 подается элемент yi, а на второй вход - нулевое значение, на выходе сумматора 29 формируется значение элемента ci, которое записывается в регистр ЗОг. Таким образом,

при нахождении триггера 31 в нулевом состоянии происходит последовательная запись элементов yi в соответствующие регистры 30j. При установлении триггера 31 в единичное состояние группа элементов И

32 открывается, через которую на первый вход сумматора 29 подается содержимое y i регистра ЗОп+1-го, на второй вход сумматора 29 подается содержимое yi регистра 30i и на выходе которого формируется значение yi +

y i, которое записывается в регистр 302 и подается на выход 33.

Рассмотрим работу устройства для случая n 6 и m 3. Структура устройства и организация входного и выходного потоков данных представлена на фиг. 2. На вход 2 постоянно подается нулевое значение. На вход 4 в моменты времени t nk + m-1 (k 0, n/m -1) подается сигнал се 1, в остальные моменты времени сигнал а 0.

В таблице приведены состояния регистров, триггеров и значения на выходе сумматоров вычислительных модулей 7i, 2, 7з и 74, а также значения на выходе 8 устройства.

Рассмотрим работу устройства при формировании элемента yi. В вычислительном модуле 7i на втором такте формируется значениеу 1 ю + anxi, в вычислительном модуле 72 на третьем такте формируется значение ую у w+ai2X2, в вычислительном модуле 7з на четвертом такте формируется значение ую у®ю у®ю + aiaxa, которое на пятом такте записывается в регистр 30ч вычислительного модуля 74, а на одиннадцатом такте - в регистр 30. В вычислительном модуле 7i на восьмом такте формируется значение + ai4 X4, в вычислительном модуле 72 на девятом-так- /ге формируется значение у 5 ц у™ ц + +315X5, в вычислительном модуле 7з на десятом такте формируется значение уп у 11 + ai6 хб, которое записывается на одиннадцатом такте в регистр 30i вычислительного модуля 74, в котором на выходе сумматора 29 на одиннадцатом такте формируется значение yi уг + уц, которое подается на выход 8устройства. Аналогичным обра,зом формируются остальные элементы выходного вектора YПоследний элемент уп формируется на (2т + п2/т - 2)-м такте. Период ввода элементов очередной задачи умножения матрицы на вектор равен (m + n + п2/т - 1) тактов,

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

-1 m-1, подключены соответственно к

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

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

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

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

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

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

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

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

Н о.

о т f-i

YX

«

, H oV -

ta N -Л -Ч0-Јо Ј

Ь Р 1А

(м

ко a d о Q с а л хэ Q .о

5 5

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

ЗИЕ

ЗИЕ

--I I

г

-S)

-t;

Г

У

l

OS

«Л

Ј

IX

Ь

СС

fu

ооооооолоо

OQQDOoOOOuCiQ

U Vfci ft «i«ia& в

4 W -J

СП

со

О О о -

о

IV

i

Фиг.з