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

 

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

COI03 СОВЕТСКИХ

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

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

ГОСУДАРСТВЕ! 1Н6!Й КОМИТЕТ

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4819893/24 (22) 28.04.90 .„.(46) 07.11.92. Бюл. N 41 ° (72) В,П.Якуш, В.В.Косьянчук, Н.А,Лиходед и П,И,Соболевский (56) Н.T.Kung, С.Е Lelserson. Slstollc Arrays (for VLSI), Sparse Matrix Proc. 1978, Society

for Industr. and Applied Math. 1979, р. 266, fig. 2-4, Авторское свидетельство СССР

N. 1677709, кл. G 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ

ЛЕНТОЧНЫХ МАТРИЦ (57) Изобретение относится к вычислительной технико и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройИзобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения двух ленточных матриц.

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

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

Устройство для перемножения ленточных матриц (фиг. 1) содержит группу 1 информационных входов, первый 2 и второй 3 информационные входы, вход 4 задания реЫ2 1774348 А1 ствах обработки сигналов для перемножения двух ленточных матриц А и 8. Цель изобретен ия — повышен ие быстродействия устройства. Цель достигается тем, что устройство содержит pa+qa-1 вычислительных модулей, где ра и qa — соответственно число ненулевых элементов в первой строке и первом столбце ленточной матрицы А, причем каждый вычислительный модуль содержит три регистра. два узла задержки на A-2 такта, где Л=2ра+2ца+рь+ць-6/рь и оь †число ненулевых элементов соответственно в первой строке и первом столбце ленточной матрицы В/, умножитель, сумматор, Л-1 триггеров и элемент И. В основу работы устройства положена параллельно-поточная организация вычислений. 2 ил. жима, синхровход 5, вычислительные модулй 6i (i=1, paiq 1) и Выход 7 Ды

Вычислительный модуль 6 (фиг; 2) со- (1 держит первый 8, второй 9 и третий 10 ин- р формационные входы, вход 11 задания режима, синхровход 12, умножитель 13, сумматор 14, регистр 15, 16 и 17, злы 18 и

19 задержки, регистры 20i (1=1, Л-2) узла 18 задержки, регистры 21i (1=1, Л -2) узла 19 задержки, триггеры 22l (l=1, Л-1), элемент

И 23, первый 24, второй 25. третий 26 и четвертый 27 информационные выходы.

В основу работы устройства положен алгоритм перемножения двух (nxn) ленточных матриц А и В с шириной лент соответственно Ia=pa+qa-1 и !ь=pb+qь-1, где ра и рь— число ненулевых элементов в первой строке C

1774348

СООтВЕтСтВЕННО МатрИц А И В; qa И qb — ЧИСЛО ненулевых элементов в первом столбце соответственно матриц А и В, основанный HQ рекуррентных соотношениях

1

cij(o)=0; с) ) )=сг()<" +a;kbkj; k=1, а)1;

ajj=min(n,i+Pa-1: j+qb-1)-min(0,j-Рь; I-qa);

)Я

c)j=c)j

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

1+Л вЂ” Z

aBIJIX aBX ° (+1 l.

Ьаых = Ьах

) +P„— 1 i свих = свх + авх Ьех

i — 1 l — л =1 (Tax ех " тех ) (+Л вЂ” 1 теых — tax где а ax, b ах и с ех — значения соответствен1 i I

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

i-м такте;

zIÄx — значение на настроечном входе вычислительного модуля на I-м такте;

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

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

1+Л-)

ТЕЕ(Х вЂ” ЗНаЧЕНИЕ На НаетРОЕь)НОМ ВЫходе вычислительного модуля на (i+ A-1)-м такте; ра и рь — число ненулевых элементов в первой строке соответственно. матриц А и В;

qa u qb — ЧИСЛО НЕНУЛЕВЫХ ЭЛЕМЕНТОВ В ПЕРвом столбце соответственно матриц А и В, (О, если то=1

1, если То=О, 2 1=1, f(УО 71 " ZA)

2,если г2=. F1=0,тг=1

Л,если то =т1 =... =т -1 =0,,— — 1.

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

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

201, 16 и 17, Кроме того, при подаче на вход

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

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

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

Организация потоков входных элеглен(о) тов aii<, bkj и сц, управля)ощих сигналов и выходных элементов с() следующая.

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

to+k+1(A-1)-(A -2)(ц,-t)+I I=1äÿ "ць-t, (<=1+1-ца, I+pa-1;

20 taik=

to+It+I аЬ-(A -t)(q t)-цьаt, I=ci+o,o, k=i+1-qa, i+pa-1, в остальные моменты времени на вход 1 подаются нулевые значения (полагаем a)k=0

25 в слУчае k О и k>n), Возьмем t0= A(qa-2)-qa.

Элементы Ь)<1 подаются на вход 2 в моменты времени

tbkj = Ak+j-pa+1. t0, !<=1,п, j=k+1-qb, k+pb-1, в остальные моменты времени на вход 2

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

Элементы cij подаются iia вход 3 в мо. менты времени (о) ьц) =A.Ic)(A-I)(q,-1)+to,I=I,o,)=аа2qаЦь, 35 (+ра+рь-2, На выходе 7 устройства формируются яij) элементы c)j-с) в моменты времени

1с)) = Л.l+j+pa(Л-1)+10-1;

i=1,п, j=i+2-qa-qi), i+Pa+Pb-2.

На вход 4 управляющий сигнал г=1 подается в моменты времени .t=t0+ Л 1+2-(Л-1)(qa 2), I=O, qa+qb-2

t=tO+(A+t)I+ Л(ЦЬ.а1)+ЦаЬ1, 1.=6; O-Ца-аЬ, 45 а в остальные моменты времени на вход 4 подается x=0, Рассмотрим работу устройства для случая п=5, ра=<1ь=3, pb=qa=2 и A=9, Запись соответствуюших значений в триггеры и регистры, формируемые значения на выходе сумматора в вычислительных модулях, осуществляется в соответствии с выполняемыми функциями вычислительными модулями и заданной организацией входного потока элементов а))<, bkj, сц и управляющих сигналов т. Формируемые

IttI )11 значения с))=с)) " на выходе 26 вычислительного модуля 64 подаются на выход 7 устройства, Последний элемент спп формируется в момент времени, определяемый выражением.1774348

4иг.1

Т= Л(п+ра)+и ра" (0-1.

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

Время перемножения двух ленточных матриц предлагаемым устройством равно 5 (Л -1)(п+ра+цд-2)+2(п-1}, Период подачи элементов для очередного перемножения матриц равен (Л4-1)(п-1) тактов.

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

Устройство для перемножения ленточных матриц, содержащее (p+q 1) вычислительных модулей (р и q — соответственно число ненулевых элементов в первой строке и первом столбце матрицы), причем первый 15 информационный вход устройства подключен к первому информационному входу первого вычислительного модуля, первый выход

i-ro вычислительного модуля (где i=1,... ..., p+q-2) подключен к первому информаци- 20 онному входу (i+1)-го вычислительного модуля, второй информационный вход устройства подключен к второму информационному входу (p+q-1)-го вычислительного модуля, второй информационный вход I-ro 25 вычислительного модуля подключен к второму выходу (i+1)-ro вычислительного модуля. синхровход устройства подключен к синхровходам всех вычислительных модулей, о т л и ч а ю щ е е с я тем, что, с целью 30 повышения быстродействия, третий информационный вход устройства подключен к третьему информационному входу первого вычислительного модуля, третий выход i-го вычислительного модуля подключен к треть- 35 ему информационному входу (i+1)-ro вычислительного модуля, вход задания режима устройства подключен к входу задания режима первого вычислительного модуля, четвертый выход I-го вычислительного модуля 40 подключен к входу задания режима (i+1)-го вычислительного модуля, причем каждый вычислительный модуль содержит три регистра, умножитель, сумматор, элемент И и три сдвигающих регистра, причем в каждом вычислительном модуле первый информационн ы и вход вы числ ител ь ного модуля подключен к информационным входам первого регистра и первого сдвигающего регистра. выход переноса которого подключен к первому выходу вычислительного модуля, второй информационный вход которого подключен к информационному входу второго регистра, выход которого подключен к первому информационному входу умножителя и к второму выходу вычислительного модуля, третий информационный вход которого подключен к информационному входу третьего регистра, выход которого подключен к первому информационному входу сумматора, второй информационный вход и выход которого подключены соответственно к выходу умножителя и K информационному входу второго сдвигающего регистра, выход переноса которого подключен к третьему выходу вычислительного модуля, вход задания режима которого подключен к информационному входу третьего сдвигающего регистра и к первому входу элемента И, выход которого подключен к входу записи/считывания первого регистра, выход которого подключен к второму информационному входу умножителя, выход переноса третьего сдвигающего регистра подключен к четвертому выходу вычислительного модуля, синхровход которого подключен к входам сдвига всех сдвигающих регистров, к входам записи/считывания второго и третьего регистров и к второму входу элемента И.

1774348.ти

i а с+Л-4 6

Г, з

ТР

è,,Г2() Ж л) giA-7

Фиг.2

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

Техред М,Моргентал

Редактор

Корректор И. Шмакова

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

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

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

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