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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2 t) 4705493/24 (22) 10,05.89 (46) 15.09.91. Бюл. М 34 (72) B.Ï.ßêóø, В.В.Косьянчук, П.И.Соболевский и Н.А.Лиходед (53) 681.3(088.8) (56) Ramakrlshman l.V., Fussel 0.S., Sllbershatz А. Systolls matrix multlpllcatlons

on à linear array, Proc 20-th Annu. Allerton

Conf. Commun, Contr. and Comput., Montlceito, Oct., 6-8. 1982, s. 1, р. 625-626.

ТИИЭР, N.9,,1987, с.194, рис.6, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализироИзобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (nxn)-матрицы на ленточную матрицу.

Целью изобретения является повыше-. ние быстродействия устройства, На фиг.1 представлена структурная схема устройства для умножения матриц; на фиг.2 — структурная схема устройства для

n=4, р=3, q=2, где и — размерность перемножаемых матриц, р и q соответственно число ненулевых элементов первой строки и первого столбца матрицы-множителя; на фиг.3 — органиэация входного потока элементов и x(p+q-1) матрицы В (В получена из исходной ленточной матрицы В путем до„„Ы2„„1677709 А1 ванных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (nxn)-матрицы на ленточную матрицу. Цель изобретения — повышение быстродействия. Поставленная цель достигается тем, что устройство содержит(р+ q

- 1) вычислительных модулей, где р и р соответственно количество элементов в первом столбце и в первой строке ленточной матрицы. Элементы матрицы-множимого поступают последовательно по столбцам на первый информационный вход устройства, элементы ленточной матрицы-множителя подаются параллельно на р+ q -1 информационных входов группы. В основу работы устройства положена параллельно-поточная органиэация вычислений. 4 ил., 1 табл. ) полнения ее нулями, описанным на фиг,3 способом. Аналитически 8 задается следующим образом; bIi = bI-i+ð,i при J=1,ð; l=1,n+Jр и при =р+1,p+q-1, i=-J-p+I,n, а в остальных случаях bii равно О); на фиг,4 — пример схемы вычислительного модуля.

Устройство для умножения матриц (фиг,1) содержит первый информационный вход 1, второй информационный вход 2, группу информационных входов 3, синхровход 4, вычислительные модули 5i i=1,p+q-1 и выход 6, Вычислительный модуль 5 (фиг.4) содержит первый информационный вход 7, второй информационный вход 8, третий информационный вход 9, синхровход 10, регистры 11-13, умножитель 14, сумматор 15, узел 16 задержки, регистры узла задержки

171 i=i,n-2, элемент И 18, первый информа1677709

45 ционный выход 19 и второй информационный выход 20.

В основу работы устройства положен алгоритм перемножения плотной (nxn)-матрицы А на ленточную матрицу В, основанный н уекуррентных соотношениях;

cj) = 0, а = макс(0, 1-q), Ц = 1,п; сц =j,:j) +Blkk)k)ik= а +,п, Ц=1,n, = с1()), р, = мин(п, ),р-1), 1 ) =1, Вычислигельный модуль работает следующим образом.

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

11, 13 и 12 (элемент В записывается в регистр 13 при подаче на вход 9 единичного разряда, который открывает элемент И 18 и разрешает запись в регистр 13). При этом на выходе умножителя 14 формируется значение n Ь, на выходе сумматора 15 — значение (с + а Ь), которое задерживается узлом 16 задержки на (n-2) тактов и выдается на выход 20. Элемент а задерживается на один такт регистром 11 и выдается на выход 19, Организация входного и выходного потоков элементов плотных (и x n)-матриц А и

С показана на фиг.1, а ленточной матрицы

В на фиг,3. Элементы Bjj„ (3k) и с )() подаются в моменты времени. та jk и ): + 1 - и - p +(и-1)(q=1) + 1, t(j = и k - (n-1)j + (p+q-2)(п-1), )

t "j) =1+ nj — n

На выходе 6 устройства формируются элементы cj) = cl) 1 в моменты времени

tc 11 = i + nj + (и-1)(p+q-2) - 1

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

l номер такта работы устройства.

Рассмотрим работу устройства для перемножения платной (n х n)-матрицы А на ленточную матрицу В (n=4, р=З, q=2) (фиг,2).

Состояние регистров 11 — 13 и 17 и формируемое значение на выходе сумматора 15 операционных блоков устройства приведены в таблице.

Загрузка элементов ац, в вычислительный модуль 5 осуществляется с второго по семнадцатый такты, загрузка элементов

n)()) — с первого по шестнадцатый такты. В соответствии с организацией подачи элементов матрицы В (фигЗ), каждый элемент

Ь1) или нулевое значение подаются на соответствующий вход Çi и вместе с дополнительным (m+1)-м единичным разрядом, записываются в регистр вычислительного модуля 5 и хранятся в нем п тактов. Элемент

l0

30 сц = cll() + ацЬц формируется в вычисли() (о) тельном модуле 5з на четвертом такте, элемент сц = сц(а г Ьгд — в вычислительн м (г) (Ь (г) модуле 5г на седьмом такте, элемент сц (=

=сц(+ а э Ьз1 — e вычислительном модуле 5t на десятом такте и выдается на выход 6 устройства на двенадцатом такте, Аналогичным образом формируются остальные элементы с ) результирующей матрицы С, которые выдаются на выход 6 устройства с двенадцатого по двадцать седьмой такты в соответствии с приведенной таблицей, Время перемножения платной (пхп)матрицы на ленточную матрицу равно

n(n+p+q-1)-р-q.

ПерИод ввода элементов матрицг очередной задачи перемножения равен тактов, Если на вход 2 в предлагаемом устройстве подавать элементы С) О, то устройство реализует матричную операцию С+ АВ.

Кроме того, предлагаемое устройство может выполнить перемножение ленточной матрицы А на плотнук (п х n)-матрицу В, где ленточная матрица А содержит в первом

/ столбце q элементов, а в первой строке — р элементов, При этом необходимо элементы транспонированной матрицы В аналоТ гичным образом подавать на вход ". а элементы транспонированной ленточной матрицы А — на входы Çj и на выходе 6 устройства формируются элементы транспонираванной результирующей матрицы С .

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

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

1677 7D9

OE 53

7Я (.тА

С)ч

4 5

Рг

33 гг

1Е

Рг СМ

12 35

z Pt 3 Я

Pz

СМ

О C((()

О С

2 Он

C (o) 0 C(o

3 аг/

C 0

Crr

0 С(Ч аъ/ аг( (о, /2 С(г

C3i

) (((C2 (—,ггву

-3(аз/

a(/ аг /

C 1(/ аз( (2 Сгг

Е а(2 ач(агl

И а»/ сзг () (г C 3ã (72г

С(С(/ аз(C/r 2 г(С(2 с (о) чг

Ь/2

Eg3 (C (,2 сгг() "щ

СЧ2

Сг(сг(8 зг

Сг с(22

C/r2

9 ач2

/3 с? ?

Сэ С31 с, с„, а/г азг (и

32

С/

Сэг (оэг

3 Се3 (Сг(Сгз с„ агг ачг

?2 с,(3

С 2

С33

Сгг (г.1 ((гз

23 СвЗ ззг

Сч2 сг(С(2 С/г

c„, (гчг

А33 ((гз Счз ()

Сь1 счч (2.

/2 233

С3

Сг3 (гч2

Сгг Сгг ((23 сз(с

Сз

Сзз

С(г) гз

Счг сзг С33 (Сзз

1 Ç (гчз

3 багз сч(с»(сг

Q(3

@33

33 зг с (2) 33

3(/ С2Ч

Cr2

Счг Счз

C(/× с уз

Сгг с/зз чг

С»3

CÀ

7 5 ((.гч 6 азу жчч зч

3(/ Сз

С(3

Сг

С зз СЗЗ (з) ) ч Счз

Сг3 а»

Сзг гь

Ci<

3У Счч

Сзз

Cr2

Сз2 сэу

Ch3I ()

-гч

C (3) (з сч, чч чу счч агч

Сгз сгч ч

C(3") VV

c„ (1 (ч с„ с«

С2 С,„

Сгч

С33 C3

C(» ч

Сзу(» С, с с(ч) Счч с/ц

Счз Сгз с ч

С«С33 сгч

Сг чз с

С3»

Сз (Ч с (» с(») 11"г("()1МИ "»1" (1(г((" " )и

1+1 двых авх

I+n1 i i свых = свх + Bex Ьвх d, I 1 где авх, свх и dex — значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на I-м такте;

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

С22 с»1 с(," C( (»)

Счг (гг

Сз Сзг

Сг 3 с»г а„„- аг((а1((ц г- агга(г а(- аг(а(1

t(Cf("((1 (г гг " Cr(t" ((((аг(((()(I+n-1 свых — значение на втором информационном выходе вычислительного модуля на (1-(-и-1)-м такте;

5 d — значение (m+1)-ro разряда bex .

I ), п — размерность перемножаемых матриц;

m — разрядность операндов.

1677709

1! lf 3! 41 П 11 31ь41 13 O 33 43 14 14 34 44 Ьг.4

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

Техред М.Моргентал Корректор Л. Бескид

Редактор С. Лисина

Заказ 3115 Тираж Ì6 Подписное

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

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

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

П 10 <14 г» Ф 00дг0р00 03@ 40303 а 0 0 Ь3033 3000414 ПИЛ 00И n 43 14 Ю 0 0 М Ю 31 11011 И,» 33 ж И

С11 С11 С31 С41 С11 СЦС31 СР 013 СР3 СЦ С43 С14 С14 034 044

В,", ВВ,0,1 В0„1 В3,1

0,1 В43,1

Id t3 0 0

0",1 О f В41 В3134,1

Фл. Z