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

fZjjonSK-Tt a&x. дювзикзгаежзияв

1

(21) 4658438/24 (22), 06.02.89 (46) 07.01 .91. Бюл. V 1 (72) В.П.Якуш, В.З.Косьянчук, П.И.Соболевский и Н „ А. Лих огтг ед

(53)681,333(088.8)

(56) ТИЮР № 9, 1987, с. 194, рис. 6, Ratnakrischnan I.V.. Fussell D.S, and Silbershatz A. Sy3tolic Matrix multiplication on a linear array,- Proc. 20-th AimuAllercJon Conf. Commune Gontr.and Cornput, Monticel loj Oct.6-8, 1982, 1, p.625-626.

(54)УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ

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

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

На фиг, 1 представлена структурная схема устройства для умножения (п хп) матриц; на фиг, 2 - структурная схема устройства для умножения двух () матриц; на фиг.З - функциональная схема вычислительного модуля устройства для умножения(пхп) матриц/ на фиг. 4 - функциональная схема вычислительного модуля устройства для умножения двух () матриц J на фиг, 5 и 6 - временные диаграммы работы устройств для п 2

Устройство для ум: охения авух (пЈп) матриц (фиг.1; содержит первый 1, второй 2 и третий 3 информа i 7) Кз пор чтение тгнс- чтся к вычислительной технчке н кс- ояано л С|ТС1Пгллизнр ванн1тх вы- чкслк ГОЛЫШУ мдгл нах л устройггвях срработ и данньг июленн-т ()- катриц Пепь ичогтптен::, - ояьгпе е быстролсл твич-ь 1;ель т;ости аеп.ч тем, что устройство сил JCTT i jn-24 линейно СБЯЗаННЫл О11О1.-11ИПНКХ|К СХПОКО ,

причем операционпьчЧ блок . лг четыре регистра, у ол эа./ Гпжки на

п- 1 ) Г 1КТОВ , УМЧОЖ1Г2ЛЬ Л Cy -fMrtTOr,

Особенностью рг. /o poi C ПР ТЕЛЯ- ггся параллг-л нп-г..л очганязгЦНЯ ВЫЧИСТ Ни Й. 1 ЗсП., 6 КЛ.

ционные входы, чнхгоЕхо/т 4, вычислительные моду iii Sj (i i.3n-2) и выход 8.

Вычислительный ксдуль 5 (фиг,

содержит первый

втспои

и третий

9 информационные вчодь 5 си хровход 10, регистры 11-14, умно деталь 15, сумматор 16, узел 17 задержки, регистры 18: (i t,n + 1)t лег вый 1°, шторок 2U и третий 21 инсЬор1чзш он ные выходы.

Узел задержки ;ожет быть вь;лол- нен, например, в виде группы последовательно соединенных регистров 18:

(i 1,п+1/.

i

В основу работы усг т с т за положен алгоритм умножения п-. nj ллгркц, основанный ь.а ре уррен-г чх состноп г- нлях,

.-СС) г Л: :.

J

«чА

Ј35

яг

tsisri

О

О

J

-

-ii r;i

ь«.

,tn

И - см i

Ч М

Вычислительный модуль работает следующим образом. На i-м такте элемента матриц а, Ъ и с подаются соответственно на входы 7-9 и записыва,, гея соответственно ч регистры 11-13. При этом на выходе умножителя 15 формируется значение , а на выходе сумматора 16 - значение (с + ), кото- рое подается на информационный вход регистра 14. Элемент а с выхода регистра 11 подается на i-м такте на выход 19, элемент b задерживается узлом 17 задержки на (п+1) тактов и подается на выход 19 на (1+п+1)-м такте, а значение (с + а-Ъ) подается на выход 21 на (1+1)-м такте.

Устройство работает следующим образом.

Б исходном состоянии регистры 11- 14 и 17) вычислительных модулей 5 устройства устанавливаются в нулевое состояние. На входы 7-9 подаются соответственно элементы а, , Ък . и

J мени:

KJ в соответствующие моменты вреta;K i(n+1)+k+2n -Zn-21,

4kj -(n+1)j-nk+2n2+n+1, (1)

tc;j ni-j+2nu-2n+1.

На выход 6 устройства выдаются элементы cjj результирующей матрицы с в моменты времени . 35

(2)

t с- ni-j+2n2+ 4n-3 .

На фиг.1 показана организация подачи входного потока элементов а|(, , b k; и с ; . в моменты времени в соот- ветствии с выражениями (1) и организация выходного потока элементов с; в соответствии с выражением (2).

Рассмотрим работу устройства для перемножения двух () матриц (фиг.2).

На первом такте на вход 2 устройства подается элемент Ь2г (фиг.2, верхний индекс .без скобок элементов а, b и с указывает момент пода- чи элементов матриц в устройство). При этом элемент Ь22 записывается в регистр 12 вычислительного модуля 5 (фиг,4 и 5) .

На втором такте элемент Ьгг посту- пает в узел 17 задержки вычислительного модуля 5,.

На третьем такте на вход . устрой- т ва попччтг.я элемент Ь(1, в регистр

0

5

12 вычислительного модуля 5 записи- вается элемент Ь4i, в регистр 18 узла 17 задержки вычислительного модуля $i - элемент Ь22.

На четвертом такте на вход 2 устройства подается элемент bz . При этом в вычислительном модуле 5 в регистр 12 записывается элемент Ь21 , в регистр 18 - элемент Ь1г ,в регистр 185 - элемент hj.z«

На пятом такте на вход 3 устройства подается элемент c °J (верхний индекс в скобках указывает номер рекуррентного шага). При выполнении операции перемножения матриц А-В элементы

0

5

Л«

3

cvy 0, i,j 1,п. Устройством может выполняться матричная операция С+А В, в этом случае элементы

сФ 0. В вычислительном модуле 5

(. элемент с,4 записывается в регистр

13, элемент Ьц - в регистр 18, элемент Ъ tj - в регистр 18. В вычислительном модуле 52 в регистр 12 запи- сывается элемент Ь2г.

На шестом такте на вход 1 устройства подается элемент а , на вход

2устройства - элемент Ь«, на вход

3устройства - элемент . При этом в вычислительном модуле 5f фор- мируется значение с °t + а((Ьи , которое подается на вход регистра 14.

На седьмом такте на вход 1 устройства подается элемент а, на вход 2

)

устройства - элемент с

(о) гг.

При этом

соответствующие элементы а, Ъ. и с j: записываются в соответствующи регистры вычислительных модулей 5 и 5г (фиг.5), в вычислительном модуле 5-i формируется значение - (о) ,1Л

С12 + ate Ь2«

На восьмом .такте на вход 3 устройства подается элемент . в вычислительном модуле 52 формируется значение с + а ,г Ь2, .

На девятом такте на вход 1 устройства подается элемент аг, , в вычислительном модуле 5 формируется

значение .Ј«

с

(О

+ а

г - г а 4 22 На десятом такте на вход 1 устройства подается элемент а22 , в вычислительном модуле 5, формируется значение

C2t с(21 + аы ЬН- На одиннадцатом такте в вычислительном модуле 5-) формируется значе- ние cjj c2z + яг,.

516

На двенадцатом такте в вычислительном модуле 5д формируется значе- +

ние с с Ј

а 22 Ь21.

На тринадцатом такте в вычислительном модуле 5. формируется значение с22 с Ј2 + Д22Ьг, , элемент с с выхода регистра 14 подается на выход 6 устройства.

На выход б устройства подаются

элементы с

сл

W

г

ft и

с2г - eg

и

соответственно на четырнацатом, пятнадцатом и шестнадцатом тактах.

Время перемножения двух (п а п) матриц предлагаемым устройством равно (Зп + 4п-4) тактов.

Форму л а и з о б р е т е i п

Т. Устройство для умножения матриц, - содержащее Зп-2 (п - размерность перемножаемых матриц) вычислительных модулей, причем первый и второй информационные входы первого вычислительного модуля являются со- ответственно первым и вторым информационными входами устройства, первый и второй информационные входы i-го вычислительного модуля (i 2,Зп-2) подключены соответственно к первому и второму выходам (i-l )-ro вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью повышения быстродействия, тревя Utt0n - Я« L

4до&.«,«.( w -

fin ftt ftaCtt ffw i

46

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

выходом устройства.

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

вычислительного модулеf выход первого регистра подключен к первому гыхопу вычислительного модуля и первому входу умножителя, второй вход которого подключен к выходу вте. регистра и информационному входу узла задержки, выход которого является вторым выходом вычислительного модуля, третий выход которого подключен к ЕЫХОДУ четвертого ре-

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

5,

E

5г

- - - - - А$3n-i

Cft -Cnn -Ctt-Cit Cn -Cm

$ut

8

. гТбЛВ-КрМ GZicz itcn.

Q гпф

WE6I91

« I

f 2 J 45-6 789 10 ti 12 13 14 15 16 П 18 19 ППППППППППППП ПППППП

Jgff I g« Qu g«L

JCfflCJFIFiSW L

Jfa |fyiticg|g

-ЧП1 fa I h

t

-Jtfff |g« IGzf ff

-ГЖ

JgHlg lC

я

if,

,

a,

,

%

«

J gff {an

JCfflCJFIFiSW L

Jffflgi l

Jfa |fyiticg|g;y -EV3

-ЧП1 fa I h

tn 6n i

J «T-UttlAi

-Jtfff |g« IGzf ffu

tffrtlffu

-ГЖП- a I fe/

JgHlg lC l i.

я гу/мг