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

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

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

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

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

Вычислительный модуль 6 (фиг. 2) содержит первый 8, второй 9 и третий 10 информационные входы, вход 11 задания режима, синхровход 12, умножитель 13, сумматор 14, регистр 15, 16 и 17, 18 и 19 задержки, регистры 20| (. Л-2) узла 18 задержки, регистры 21| (, Л -2) узла 19 задержки, триггеры 22| (, Л-1), элемент И 23, первый 24, второй 25, третий 26 и четвертый 27 информационные выходы.

В основу работы устройства положен алгоритм перемножения двух (пхп) ленточных матриц А и В с шириной лент соответственно 1а Ра+Ча-1 и Ib pb+qtr1, где Ра и рь - число ненулевых элементов в первой строке

1 VJ

J

CJ Јь 00

соответствен но матриц А и В;раипь-число ненулевых элементов в первом столбце соответственно матриц А и В, основанный на рекуррентных соотношениях

1 i, j п; 1-ра-рь i-j qa+qb-1;

сц(°Ч);

ci/k))-t-3ikbkj;k 1,

ctjj min{rt.l+pa-1; j-i-qb-1}-min{0,j-pb; l-qa};

.

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

1+Л-2 I Эвых- Эвх I

1+1I

Ьоых - Ьвх J

i+Л- i i i-z i

Свых Свх Эвх Ьвх i

I 1-11 Л

Z-f (Твх i Tax ,... , TBX )l

i +Л- 1 i

Твых TBX i

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

i-м такте; i

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

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

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

1+Л-1

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

Ра и рь - число ненулевых элементов в первой строке соответственно матриц А и В; Qa и qb - число ненулевых элементов в первом столбце соответственно матриц А и В, (О, если 1, если , ,

f(r0,nгл)

2, если r0 ,

Л,если г0 -т -... ,. Вычислительный модуль 6 работает следующим образом.

На I-м такте элементы a, b и с матриц подаются соответственно на входы 8, 9 и 10 и записываются соответственно в регистры

20i, 16 и 17. Кроме того, при подаче на вход 11 единичного сигнала т открывается элемент И 23. который разрешает запись элемента а в регистр 15. На выходе сумматора

14 формируется значение (ci-ab), которое выдается на выход 26 с задержкой на Л-2 такта. Элемент а выдается на выход 24 с задержкой на Л-2 такта, элемент b выдается на выход 25 с задержкой на один такт, а

0 управляющий сигнал выдается на выход 27 с задержкой на Л-1 такт.

Организация потоков входных элеменк(0)

тов aik, bkj и cij , управляющих сигналов и

5 выходных элементов cij следующая.

Элементы aik подаются на вход 1 в моменты времени

(to+k+l(A-1)-(A -2)(да-1)-И.М.да+дь-1. jk i+1-qa, i+pa-1;

0

(to+k+l Л-(Л -Ща-1)-дь+1. l-qa+дь.п, i+1-qa, i+pa-1,

в остальные моменты времени на вход 1 подаются нулевые значения (полагаем 5 в случае к 0 и ). Возьмем to Л (qa-2)-qa. Элементы bkj подаются на вход 2 в моменты

времени

tbkj Ak+j-pa+1-i-to, ,n, J k+1-qb, k+pb-1. в остальные моменты времени на вход 2

0

5

0

5

0 подаются нулевые значения.

Элементы ci/° подаются на вход 3 в мо- . менты времени

(о)

tC|j A.I+j-(A -1)(ga-1)+to..n. jH+2-qa-qb.

5 i+pa+pb-2.

На выходе 7 устройства формируются

(Аф

элементы в моменты времени

. l+j+pa(A-1 Ho-1:

,n, jH+2-qa-qb, ii-pa+pb-2.

На вход 4 управляющий сигнал подается в моменты времени

t to+A i+2-(A-1)(qa-2), , д3+дь-2:

(A+1)i+A(qb-M)+qa+1, , n-qa-qb, а в остальные моменты времени на вход 4 подается .

Рассмотрим работу устройства для случая , , pb-Qa 2 и А 9. Запись с оответ- ствуюших значений в триггеры и регистры, Формируемые значения на выходе сумматора в вычислительных модулях, осуществляется в соответствии с выполняемыми функциями вычислительными модулями и заданной организацией входного потока элементов aik, bkj, ci/° и управляющих сигналов г. Формируемые значения на выходе 26 вычислительного модуля 64 подаются на выход 7 устройства. Последний элемент Спп формируется в момент времени, определяемый выражением

(n+pa)(-n-pa4tO-1.

В данном случае последний элемент ess формируется на 72-м такте.

Время перемножения двух ленточных матриц предлагаемым устройством равно (A-1Xn-bpa+qa-2)+2(n-1).

Период подачи элементов для очередного перемножения матриц равен (Л+1Хп-1) тактов.

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

Устройство для перемножения ленточных матриц, содержащее (p- q-l) вычислительных модулей (р и q - соответственно число ненулевых элементов в первой строке и первом столбце матрицы), причем первый информационный вход устройства подключен к первому информационному входу первого вычислительного модуля, первый выход 1-го вычислительного модуля (где ,... .... p+q-2) подключен к первому информационному входу (i-M)-ro вычислительного модуля, второй информационный вход устройства подключен к второму информационному входу (p+q-1)-ro вычислительного модуля, второй информационный вход 1-го вычислительного модуля подключен к второму выходу (1+1)-го вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия, третий информационный вход устройства подключен к третьему информационному входу первого вычислительного модуля, третий выход 1-го вычислительного модуля подключен к третьему информационному входу (i+1)-ro вычислительного модуля, вход задания режима устройства подключен к входу задания режима первого вычислительного модуля, четвертый выход 1-го вычислительного модуля

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения двух ленточных матриц А и 8. Цель изобретения - повышение быстродействия устройства. Цель достигается тем, что устройство содержит pa+qa-1 вычислительных модулей, где ра и qa - соответственно число ненулевых элементов в первой строке и первом столбце ленточной матрицы А, причем каждый вычислительный модуль содержит три регистра, два узла задержки на Л-2 такта, где Л 2ра+2да+рь+дь-6/рь и дь число ненулевых элементов соответственно в первой строке и первом столбце ленточной матрицы В/, умножитель, сумматор, Л-1 триггеров и элемент И. В основу работы устройства положена параллельно-поточная организация вычислений. 2 ил. сл

а.

./

v

- J