Устройство для перемножения матриц Советский патент 1987 года по МПК G06F17/16 

11363247

Изобретение относится к вычислим

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

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

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

Устройство содержит информационные входы 1 первой группы, информационные входы 2 второй группы, входы 3 для задания кода нуля, тактовьш вход 4, матрицу вычислительных блоков 5 и f информационные выходы 6.

В состав каждого вычислительного блока 5 входят три регистра 7, 8 и 9, блок 10 умножения, сумматор 11, триггер 12 и (Т+1) элементов И 13, где Т - разрядность кода представления числовых компонентов перемножаемых матриц.

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

В основу работы устройства поломент b J блока 5

записывается в регистр 7 На втором такте элементы

« 2г записываются в регистры 7 соответственно блоков 5 , , 5, и 5л, . На третьем такте элементы h ,

22

U k

bji. Ьз,

31

и b J записываются в

регистры 7 соответственно блоков 5,,

10

я и 73 3V Wa четвертом такте элементы Ь , b , b , Ь, Ь/(, , b J,j к записываются в регис- 7 блоков 5 ,

5 42 5 43 Н - Zf

г тры

и 5j соответственно. Таким образом,

дпя записи всех элементов матрицы В IF, в соответствующие блоки 5 требуется

п тактов работы устройства, где п размерность матрицы В.

Рассмотрим работу блока 5„ при

записи в регистр 7 элемента b . На 20 первом такте Т-разрядный элемент bj

и (Т+1)-й единичный разряд поступа- ют соответственно на Т-разрядный ин- ;формационньй вход регистра 7 и установочный вход триггера 12. В исходном состоянии с инверсного выхода триггера 12 подается единичный сигнал на вход признака записи регистра 7 и элемент b записывается в регистр 7. На вход синхронизации триггера 12 по25

жен алгоритм умножения матрицы А а--

на матрицу jj , определяющий мат- 30 ступает тактовый сигнал, по заднему

фронту которого триггер 12 устанавли t J J v- ili c l.cji/in u nn

,...n; ,...n, где n - порядок квадратной матрицы):

рицу jj

вается в единичное состояние, запре-. щая запись в регистр 7 блока 5,, . При этом открываются элементы И 13.

(1)

Определение любого элемента С ( требует п-кратного выполнения операции накопления

fi

+ а. - b. . ik .

(2)

Особенностями функционирования устройства являются сдвиг накаплива40 единичным разрядом проходя через открытые элементы И.13 в соседний диагональный блок 522

На вторые информационные входы . устройства подаются по тактам соотемых сумм С , на очередном такте 45 ветствующие Т-разрядные элементы а ..

- г . t I

работы из iP-ro вычислительного блока 5 (1 1 ,. . . ,. . .п-1) в i (Р+1)-й блок 5 и неподвижность элементов Ь.. матрицы В.

В исходном состоянии триггеры 12 и регистры 7-9 блоков 5 устанавлива- ; ются в нулевое состояние. На информационные входы 1 подаются по тактам соответствующие Т-разрядные элемен50

матрицы А, представленной на фиг. I в форме параллелограмма. На первом такте элемент

гистр 8 блока 5 /

fi

записывается в ре- На втором такте

элемент а J записывается в регистр 8 блока 5j, , а элементы а и а записываются в регистры 8 блоков 5 и 5.

соответственно. Закономерность записи соответствующих элементов а .

11

ты (Ь,j , l) матрицы В с доцолнитель- gg матрицы А сохраняется и на последум- ным ( единичным разрядом, пред- щих тактах.

ставленной на фиг. 1 в форме тре- ;; Рассмотрим работу устройства при угольника, где 1 - номер такта рабо- формировании Т-разрядных элементов ты устройства. На первом такте эле- С и Cj,,. На первом такте элеме2ггы

мент b J блока 5

записывается в регистр 7 На втором такте элементы

« 2г записываются в регистры 7 соответственно блоков 5 , , 5, и 5л, . На третьем такте элементы h ,

22

U k

bji. Ьз,

31

и b J записываются в

регистры 7 соответственно блоков 5,,

я и 73 3V Wa четвертом такте элементы Ь , b , b , Ь, Ь/(, , b J,j к записываются в регис- 7 блоков 5 ,

5 42 5 43 Н - Zf

г тры

и 5j соответственно. Таким образом,

дпя записи всех элементов матрицы В F, в соответствующие блоки 5 требуется

п тактов работы устройства, где п размерность матрицы В.

Рассмотрим работу блока 5„ при

записи в регистр 7 элемента b . На 0 первом такте Т-разрядный элемент bj

и (Т+1)-й единичный разряд поступа- ют соответственно на Т-разрядный ин- ;формационньй вход регистра 7 и установочный вход триггера 12. В исходном состоянии с инверсного выхода триггера 12 подается единичный сигнал на вход признака записи регистра 7 и элемент b записывается в регистр 7. На вход синхронизации триггера 12 по5

0 ступает тактовый сигнал, по заднему

вается в единичное состояние, запре-. щая запись в регистр 7 блока 5,, . При этом открываются элементы И 13.

На последующих тактах работы устройства запись элементов матрицы В в регистр 7 блока 5 запрещена, и соответствующие Т-разрядные элементы матрицы (Ь ,-j, l) с дополнительным

единичным разрядом проходя через открытые элементы И.13 в соседний диагональный блок 522

На вторые информационные входы . устройства подаются по тактам соответствующие Т-разрядные элементы а ..

. t I

0

матрицы А, представленной на фиг. I в форме параллелограмма. На первом такте элемент

гистр 8 блока 5 /

fi

записывается в ре- На втором такте

элемент а J записывается в регистр 8 блока 5j, , а элементы а и а записываются в регистры 8 блоков 5 и 5.

соответственно. Закономерность записи соответствующих элементов а .

11

g матрицы А сохраняется и на последум- щих тактах.

а

11

записываются в регистры 8;

причем информационный вход первого регистра первого вычислительного блока первой строки матрицы является первым информационным входом первой группы устройства, информационный вход первого регистра К-го вьиисли- тельного блока (К 2,..., Р) первой строки матрицы является К-м информа-. ном состоянии. В результате на первом IQ ционным входом первой группы устройства, информационньй вход первого реи 7 с оответственно блока 5, и подаются на входы блока 10 умножения. С выхода блока 10 умножения произведение а b поступает на вход сумматора 11, на второй вход которого поступают нули, так как регистр 9 блока 5 , постоянно находится в нулетакте на выходе сумматора 1I формируcL О +

На втором , такте накапли- записьгоается в реется накапливаемая сумма + а

ь:

гистра М-го вычислительного блока (,..,,Р) первого столбца матрицы является (Р-1+М)-м информационным гистр 9 блока 5. . В блоке 5 анало- 15 входом первой группы устройства, вы-

11

11

ваемая сумма С

гично формируется накапливаемая сумма

О + а,, b . В блоке 5 , с регистров 8 и 7 на входы блока О умножения подаются элементы а и Ь„ соответственно. На выходе сумма- тора 11 формируется накапливаемая

2

20

сумма

с с

.

На треть:-;

ем такте в блоке 5 аналогично фор- мируется накапливаемая сумма С j,

О + а

I

С

.1 -.. ъ

г ii

С 2

в блоке 5

71 сумма С

+ а

П

Ь

- сумма блоке 5

с;, .а,Ь-; -. вертом такте в блоке 5

формируется

г

+1

сумма С С ,,

13

На чет- 1 аналогично накапливаемая сумма Ь , , в блоке

Ь

5 1, - сумма С блоке

f

i

+ а С

+ а

5|, - в блоке

. ,

в

5 - сумма С

а:, Ь,

О + а и , ,

- . .

зг

э

I С,, . а; На четвертом такте накапливаемая сумма С является значением элемента матрицы произведения С и подается на выход 6 . На последующих тактах работы устройства аналогично формируются остальные элементы С -j матрицы произведения С, представленной на фиг. 1 в форме параллелограмма.

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

Устройство для перемножения матриц, содержащее матрицу из вычислительных блоков, где Р - порядок матрицы, причем каждый вычислитель- ньй блок содержит три регистра, блок умножения и сумматор, отличающееся тем, что, с целью повышения быстродействия устройства, в каждый вычислительный блок введены триггер и (Т+l) элементов И, где Т - разрядность кода представления числовых компонентов перемножаемых матриц.

ходы с первого по (Т+1)-й элементов И (к-О-го вычислительного блока (М-1)-й строки матрицы подключены к информационному входу первого регистра К-го вычислительного блока М-й строки матрицы, информационный вход второго регистра Н-го вычислительно - го блока первой строки матрицы (,...,Р) является Н-м информацион25 ным входом второй группы устройства, выход второго регистра Н-го вычислительного бло&а (М-1)-й строки матрицы подключен к входу второго регистра Н-го вычислительного блока М-й стро-

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

25 числительного блока (К-1)-го столбца матрицы подключен к информационному входу третьего регистра Н-го вычислительного блока К-го столбца матрицы, выход сумматора Н-го вычислитель40 ного блока Р-го столбца матрицы является Н-м информационным выходом устройства, тактовый вход устройства .подключен к входам признаков записи вторых и третьих регистров и к входам

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

50

55

гистра М-го вычислительного блока (,..,,Р) первого столбца матрицы является (Р-1+М)-м информационным - 15 входом первой группы устройства, вы-

а

20

-;

.

ходы с первого по (Т+1)-й элементов И (к-О-го вычислительного блока (М-1)-й строки матрицы подключены к информационному входу первого регистра К-го вычислительного блока М-й строки матрицы, информационный вход второго регистра Н-го вычислительно - го блока первой строки матрицы (,...,Р) является Н-м информацион25 ным входом второй группы устройства, выход второго регистра Н-го вычислительного бло&а (М-1)-й строки матрицы подключен к входу второго регистра Н-го вычислительного блока М-й стро-

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

25 числительного блока (К-1)-го столбца матрицы подключен к информационному входу третьего регистра Н-го вычислительного блока К-го столбца матрицы, выход сумматора Н-го вычислитель40 ного блока Р-го столбца матрицы является Н-м информационным выходом устройства, тактовый вход устройства .подключен к входам признаков записи вторых и третьих регистров и к входам

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

50

55

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

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

Изобретение относится к вычислительной технике, может быть использовано в специализированных вычислительных машинах для умножения квадратных матриц одного порядка и позволяет повысить быстродействие устройства за счет совмещения операций ввода компонентов матриц с операцией их умножения. Устройство содержит информационные входы 1 первой группы, информационные входы 2 второй группы, входы 3 для задания кода нуля, тактовый вход 4, матрицу вычислительных блоков 5 и информационные выходы 6. В основу работы устройства положен алгоритм умножения матрицы А а -. на матрицу В Ь ,-j , определяющий матрицу С С ,- j (i 1,...n; j 1...П, где n - порядок - ., , квадратной матрицы): С .. 2-. а ., b , .. J J При этом определение любого элемента С требует п-кратн6го вьптолнения Ь ,. . fcоперации накопления С : С .j +а Ь . . На входы 1 и 2 устройства в порядке, определенном на фиг. 1, подаются по тактам элементы матриц А и В. При этом на информационных выходах 6 устройства формируются числовые компоненты матрицы С. 2 ил. Q (Л со О5 4 М

. Z

Составитель А, Мишин Редактор А. Маковская Техред М.Дидык Корректор Л.Пилипенко

Заказ 6364/42

Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытии 113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4