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

 

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

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

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ

К ПАТЕНТУ 4

О

С> 4

00 (Л (21) 4880892/24 (22) 05.11.90 (46) 23.01.93. Бюл, ¹ 3 (71) Киевский политехнический институт им,50-летия Великой Октябрьской социалистической революции (72) Р.Выжиковский, Ю.С.Каневский, М.К.Клименко и С.Г.Овраменко (73) Киевский политехнический институт (56) Авторское свидетельство СССР

N 1363247, кл. G 06 В 15/347, 1986.

Авторское свидетельство СССР

¹ 1552200, кл. G 06 F 15/347, 1988. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ

„,. Ж» 1790785 А3 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе систолических устройств, предназначенных для выполнения операций над матрицами, Целью изобретения является повышение быстродействия, Новым вустройстве для умножения матриц, содержащем пхп вычислительных модулей 1 первого типа и блок 3 управления, является введение пхп вычислительных модулей 2 второго типа, что дает возможность организовать непрерывную обработку потока трех матриц, а это, в свою о4Ьредь, обеспечивает повышение производительности устройства в 2 раза. 2 з,п. ф-лы, 4 ил.

1790785

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

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

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

2 второго типа и блок 3 управления.

Вычислительный модуль первого типа (фиг, 2) содержит регистры 4, 5, умножитель

6, сумматор 7, регистр 8 и триггер 9.

Вычислительный модуль второго типа (фиг. 3) содержит регистр 10, умножитель 11, регистр 12, сумматор 13 и регистр 14, Блок 3 управления (фиг, 4) содержит элемент ИЛИ 15, счетчик 16, дешифратор 17, регистр 18.

Устройство предназначено для умножения матриц АхВхС = F, где А, В и С вЂ” матрицы размерности NxN, и может быть реализовано при следующих формулах;

dij = > Bikbkj

k=1 где a;k, Ь 1 и С1 — элементы матриц А, В и С;

4; — элементы промежуточной матрицы;

tis — элемент конечной матрицы F.

Кратко рассмотрим работу устройства, Для простоты описания и без потери общности положим N = 3. Условимся, что прием информации во все регистры осуществляется по переднему фронту синхроимпульса, то есть в начале такта. Считаем, что перед началом вычислений все регистры установлены в нулевое состояние. Имйульс пуска поступает на первый вход блока управления

3 (вход запуска) через элемент ИЛИ 15 поступает на второй вход счетчика 16 (вход разрешения записи s счетчик 16). Счетчик 16 работает в режиме вычитания. Дешифратор

17 дешифрирует состояние нуля. На первые входы вычислительных модулей 1 первого типа первого столбца поступают элементы, а матрицы А по строкам. На вторые входы— элементы матрицы B по столбцам. Элементы с1> матрицы С поступают на первые входы вычислительных модулей 2 второго типа первого столбца по строкам, а11а12а13 b» b12b13 d» d 12d13 а21а22а23 Ь21Ь22Ь23 = о21о22о23 а31а32а33 b31b32b33, d31d32d33 с111д12о13 с»с12с13 f11f12f13

О21о22О23 С21С22С23 = f21f22f23

d31d32d33 С31С32С33 f31f32f33

Результирующая матрица получена следующим образом; т» = d11c» + о13С13+ d12c12: т12 = d22C12 + о21С» + d23C13

f13 = С133С13 + d32C22 + d31C»

f21 = О11С21 + О13С13 + О12С22;

f22 = о22С22 + о21С21 + О23С23; т23 = оЗЗс23 + о32с22 + d31c21:

f31 = о»с31 + о13с33 + d12c32;

f32 = О22С32 + о21С31 + о2ЗСЗЗ:

f33 = ОЗЗСЗЗ+ о32С32 + о31С31.

25

Нулевой такт, На первый и второй входы вычислительного модуля 1.1,1 соответственно поступают элементы а» и Ь» и записываются соответственно в регистры 4.1.1 и

5,1.1. На первый и второй входы вычислительного модуля 1.2.1 соответственно поступают а21 и b12 и записываются соответственно в регистры 4,2,1 и 5,2.1. На первый и второй входы вычислительного модуля 1.3.1 соответственно поступают а31 и

b13 и записываются соответственно в реги40 стры 4.3.1 и 5.3.1.

В первом такте с вь1ходов регистров

4.1.1 и 5,1.1 элементы а11 и Ь» поступают на первый и второй выходы вычислительного модуля 1.1.1 и на первый и второй входы

45 умножителя 6.1.1, с выхода которого произведение а»Ь» поступает в сумматор 7,1,1, где складывается с нулем а11Ь11+0 и записывается в регистр 8.1.1. На входы вычислительного модуля 1,1.1 поступают следующие элементы а12 и b21 и записываются в регист ры 4.1.1 и 5.1,1. На входы вычислительного модуля 1,1.2 поступают элементы а11 и b13 и записываются в регистры 4,1,2 и 5.1,2. На первый вход сумматора

7,2,1 вычислительного модуля 1.2.1 поступает произведение а21Ь12, где складывается с нулем и а21Ь12+О записывается в регистр

8.2.1. В регистры 4,2.1 и 5.2.1 соответственно записываются а22 и Ь22 В регистры 4,2.2

1790785

10

50

55 и 5.2.2 вычислительного модуля 1.2.2 соответственно записываются элементы а21 и

Ь11, На первый вход сумматора 7.3.1 вычислительного модуля 1.3.1 поступает произведение a31b13 и складывается с нулем, результат a31b13+0 записывается в регистр

8.3.1. В регистры 4.3.2 и 5.3,2 вычислительного модуля 1.3,2 соответственно записываются элементы а31 и Ь12.

Во втором такте с выхода регистра 8 1.1 вычислительного модуля 1,1.1 на второй вход сумматора 7.1,1 поступает произведение а»Ь», на первый вход которого с выхода умножителя 6,1.1 поступает a12b21 и результат а»Ь»+а21Ь21 снова записывается в регистр 8,1,1, В регистры 4.1.1 и 5.1.1 соответственно записываются элементы а13 и b31. На выходе сумматора 7.1,2 вычислительного модуля 1.1.2 будет сумма а11Ь13+О, которая записывается в регистр 8.1.2. В регистры 4,1,2 и 5,1.2 записываются а12 и Ь23.

В регистры 4.1,3 и 5;1.3 вычислительного модуля 1,1,3 записываются а» и Ь12. На входы сумматора 7.2.1 вычислительного модуля 1,2.1 поступают произведения а21Ь12 и а22Ь22 и с его выхода сумма а21Ь12+а22Ь22 записываются в регистр 8,2.1. В регистры

4,2,1 и 5.2.1 записываются а23 и b32, На выходе сумматора 7,2.2 вычислительного модуля 1,2,2 появляется сумма а21Ь»+О и записывается в регистр 8.2.2, В регистры

4.2.2 и 5.2.2 записываются а22 и Ь21 В регистры 4.2.3 и 5.2.3 вычислительного модуля

1.2.3 записываются а21 и b13. на входы сумматора 7 вычислительного модуля 1.3.1 поступают произведения a31b13 и а32Ь23 и результат a31b13+a32b23 записывается в регистр 8.3,1. В регистры 4.3.1 и 5.3.1 записываются а33 и ь33. С выхода сумматора 7.3.2 вычислительного модуля 1.3.2 a31b1z+0 записывается в регистр 8.3.2. В регистры 4.3,2 и 5,3,2 записываются a3z u bzz. В регистры

4.3.3 и 5.3.3 вычислительного модуля 1.3.3 записываются а31 и b», В третьем такте в сумматорах 7.1.1—

7,7.п вычислительных модулей 1.1,1 — 1,1,п получаем первые элементы dij промежуточной матрицы D, Таким образом, с выхода сумматора 7.1.1 вычислительного модуля

1.1.1 на третий выход поступает

a«b»+a1zbz1+a13b31= d» и d» записывается в регистр 10 вычислительного модуля 2.1.1, На входы регистров 4.1,1 и 5.1,1 поступают элементы а» и b» новых матриц А и В. В регистр 12,2,1 с первого входа вычислительного модуля 2.1.1 записывается элемент с» матрицы С, С выхода сумматора 7.1.2 вычислительного модуля 1,1.2 в регистр 8.1,2 записывается а»Ь13+а12Ь23. В регистры 4.1,2 и 5.1.2 соответственно записываются а13 и

Ь33. С выхода сумматора 7.1.3 вычислительного модуля 1.1.3 в регистр 8,1,3 записывается а»Ь12+О. В регистры 4.1.3 и 5.1,3 записываются а12 и Ь22. В сумматоре 7.2.1 вычислительного модуля 1.2.1 получаем д21Ь12+а22Ь22+а23Ь32 = б22 и элемент б22 записывается в регистр 10.2.1 вычислительного модуля 2,2,1, На входы регистров 4,2,1 и

5.2,1 поступают элементы новых матриц, В регистр 12.2.1 записывается с12, С выхода сумматора 7.2.2 вычислительного модуля

1.2,2 в регистр 8.2.2 записывается сумма

az1b»+az2bz1, В регистры 4,2.2 и 5.2.2 записываются элементы а23 и b31. С выхода сумматора 7,2.3 вычислительного модуля 1.2.3 в регистр 8,2.3 записывается а21Ь13+О. В регистры 4.2.3 и 5,2,3 записываются azz u bz3.

В сумматоре 7,3.1 вычислительного модуля

1,3.1 получаем a31b13+a32b23+a33b33 = б33 и элемент б33 записывается в регистр 10.3.1 вычислительного модуля 2,3.1. В регистры

4.3.1 и 5,3.1 записываются элементы новых матриц. В регистр 12,3.1 записывается с13.

С выхода сумматора 7.3,2 вычислительного модуля 1.3.2 в регистр 8.3,2 записывается а31Ь12+а32Ь22. В регистры 4,3,2 и 5.3.2 записываются а33 и Ь32. С выхода сумматора

7,3.3 вычислительного модуля 1.3.3 в регистр 8.3.3 записывается а31Ь11+О. В регистры 4,3,3 и 5.3.3 записываются а32 и b21.

В четвертом такте в сумматоре 7.1.2 вычислительного модуля 1.1.2 получаем сумму

a»b13+a12bz3+a13b33 = б13 и элемент d13 записывается в регистр 10,1,2 вычислительного модуля 2.1.1. В регистр 12,1.2 записывается с13. С вь1хода сумматора 7.1,3 вычислительного модуля 1.1.3 поступает

a11Ь12+э11Ь22 и записывается в регистр

8,1.3. В регистры 4,1,3 и 5,1.3 записываются а13 и Ь23. На входы умножителя 11.1.1 вычислительного модуля 2,1.1 поступают элементы d» и с», где происходит умножение

d»c» и произведение поступает в сумматор

13.1.1, где складывается с нулем и записывается в регистр 14.1,1, В регистр 12.1.1 записывается элемент С22, а элемент с» передается в вычислительный модуль 2.2,2 и записывается в регистр 12,2,2. В сумматоре

7.2,2 вычислительного модуля 1.2,2 получаоМ а21Ь»+а22Ь21+э23Ь31 = б21 и элемент б21 записывается в регистр 10.2.2, С выхода сумматора 7.2.3 вычислительного модуля

1,2.3 получаем a21b13+a22b23 и эта сумма записывается в регистр 8.2,3, В регистры 4.2,3 и 5.2.3. Записываются az3 и Ь33. В сумматоре 13.2.1 вычислительного модуля 2.2.1 получаем сумму б22с21+О, которая записывается в регистр 14.2.1. В регистр 2.2,1 записывается czz. В сумматоре 7.3.2 вы1790785

55 т31, тзг и f33, числительного модуля 1.3,2 получается а31Ь12+азгЬ22+аззЬ32 = бзг и записывается в регистр 10,3.2 вычислительного модуля

2,3.2, В регистр 12.3.2 записывается 012.

С выхода сумматора 7.3.3 вычислительного модуля 1.3.3 поступает а31Ь»+азгЬг1 записывается в регистр 8.3.3. B регистры 4,3,3 и

5.3 3 записываются а33 и Ь31. С выхода сумматора 13.3.1 вычислительного модуля 2.3.1 поступает бззс13+О записывается в регистр

14,3.1. В регистр 12,3.1 записывается с23.

В пятом такте в сумматоре 7.1.3 вычислител ьного модуля 1.1.3 получаем а»Ь12+а12Ь22+а13Ь32 = б12 и элемент б12 за писывается в регистр 10.1,3 вычислительного модуля 2,1.3, В регистр 12.1,3 записывается с,г. С выхода сумматора

13.1.2 вычислительного модуля 2,1.2 поступает б11с11 б13с13 и записывается в регистр 14,1.2 вычислительного модуля

2.1.2. В регистр 12.1.2 записывается элемент с23. С выхода сумматора 13.1.1 вычислительного модуля 2,1.1 выдается d»c21+0 и записывается в регистр 14,1,1, В регистр

12.1.1 записывается с31. В сумматоре 7.2.3 получаем аг1Ь13+аггЬ23+аггЬ33 = бгз и элемент d23 записывается в регистр 10,2.3 вычислительного модуля 2,2.3. В регистр

12,2.3 записывается с13. С выхода сумматора 13.2.2 вычислительного модуля

2.2,2 выдается бггс12+бг1с11 vi записывается в регистр 14.2.2. B регистр

12.2,2 записывается сзг, B сумматоре

7.3.3 вычислительного модуля 1.3.3 получаем а31Ь»+азгЬ21+а33Ь31 = б31 и элемент

d31 записывается в регистр 10,3.3 вычислительного модуля 2.3.3, B регистр 12.3,3 вычислительного модуля 2.3.3 записывается с11.

С выхода сумматора 13.2.2 вычислительного модуля 2,3,2 поступает d33013+d32c12 и записывается в регистр 14.2.3. В регистр 12.3.2 записывается сгг, С выхода сумматора

13.3.1 вычислительного модуля 2,3,1 поступает бззс23+О и записывается в регистр

14.3.1. В регистр 12,3.1 записывается — с33.

В шестом такте в сумматоре 13.1.3 вычислительного модуля 2.1.3 получаем первый окончательный результат

d»c»+d13c13+d12c12 = f», который записывается в регистр 14,1,3. В регистр 12,1.3 за пис ы вает ся — c22. С выхода сумматора

13,1,2 вычислительного модуля 2.1.2 поступает d»c21+d13023 и записывается в регистр

14,1,2, В регистр 12.1,2 записывается — сзз.

С выхода сумматора 13.1.1 вычислительного модуля 2.1,1 поступает б»с31+О и записывается в регистр 14,1,1, В сумматоре 13.2.3 вычислительного модуля 2,2,3 получаем б22с12+б21с»+б23с13 = f12 и результат f12 за20

50 писывается в регистр 14.2,3, В регистр

14,2,3 записывается — сгз. С выхода сумматора 13.2,2 вычислительного модуля 2.2.2 поступает d22022+d21021 и записывается в регистр 14.2.2, В регистр 12,2.2 записывается с31. С выхода сумматора 13,2.1 вычислительного модуля 2.2.1 поступает бггсзг+О и записывается в регистр в регистр 14.2,1, В сумматоре 13,3,3 вычислительного модуля

2.3.3 получаем бззб13+б32012+б31011 = 113 и результат записывается в регистр 14.3.3. B регистр 12,3,3 записывается с21, С выхода сумматора 13,3.2 вычислительного модуля

2.3.2 поступает d33023+d32022 и записывается в регистр 14,3.2, В регистр 12,3,2 записывается 032. С выхода сумматора 13,3,1 вычислительного модуля 2.3,1 поступает бззс33+О и записывается в регистр 14.3.1.

В седьмом такте в сумматоре 13.1.3 вычислительного модуля 2.1.3 получаем

d»c21+d13c23+d12022 = f21 и результат записывается в регистр 14,1.3, а с его выхода на выход устройства выдается f11, В регистр

12.1.3 записывается с32. С выхода сумматора 13,1,2 вычислительного модуля 2.1,2 поступает б11с31+б13с33 и записывается в регистр 14,1.2, В сумматоре 14.2,3 вычислительного модуля 2,2,3 получаем

d22022+d21021+d23023 = Ы и результат записывается в регистр 14.2.3, с выхода которого на выход устройства выдается f12. В регистр

12.2.3 записывается сзз, С выхода сумматора 13.2.2 вычислительного модуля 2.2,2 поступает бггсзг+бг1с31 и записывается в регистр

14.2,2, В сумматоре 13.3,3 вычислительного модуля 2.3,3 получаем бззсгз+бзгсгг+б31021 =

123 и результат записывается в регистр 14.3.3, с выхода которого выдается f13. В регистр

12,3,3 записывается с31. С выхода сумматора 13.3.2 вычислительного модуля 2.3.2 поступаетт бззс33+бзгсзг и за и ис ы ва ется в регистр 14,3.2.

В восьмом такте в сумматоре 13.1.3 вычислительного модуля 2.1.3 получаем б11с31+б13сзз+б12с32 = f31 и результат за пи сывается в регистр 14,1,3, с выхода которого выдается f21, В сумматоре 13,2,3 вычислительного модуля 2.2.3 получаем бггсзг+бг1с31+б23033 = 32 и результат записывается в регистр 14,2,3, с выхода которого выдается f22, В сумматоре 13,3,3 вычислительного модуля 2.3.3 получаем бззсзз+бг1сзг+б31с31 = 133 и результат записывается в регистр 14.3.3, с выхода которого выдается f33, В девятом такте с выхода вычислительных модулей 2.1,3, 2,2.3 и 2.3.3 соответственно выдаются окончательные результаты

1790785

-55

На этом работа устройства по вычислению матрицы F = АхВхС заканчивается.

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

1. Устройство для умножения матриц, содержащее пхп вычислительных модулей первого типа и блок управления (где и— размерность матриц), причем первый информационный выход (Ц)-го вычислительного модуля первого типа (i = 1, ..., и; J = 1, „„и-1) соединен с первым информационным входом (Ц+1)-го вычислительного модуля первого типа, входы запуска, сброса, записи и счетный вход устройства соединены с соответствующими входами блока управления, выход которого соединен с входом разрешения записи (i,1)-го вычислительного модуля первого типа, первый и второй информационные входы которого соединены соответственно с первым и вторым информационными входами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены пхп вычислительных модулей второго типа, причем первый информационный вход (i,1)-го вычислительного модуля второго типа соединен с третьим информационным входом устройства, вход логического нуля которого соединен с вторым информационным входом (i,1)-ro вычислительного модуля второго типа, второй информационный выход (К))-го вычислительного модуля первого типа (k=1, ..., и-1) соединен с вторым информационным входом (k+1, j+1)-ro вычислительного модуля первого типа, второй информационный выход (п,))-го вычислительного модуля первого типа соединен с вторым информационным входом (1, j+1)-го вычислительного модуля первого типа, третий информационный выход (i,i)-го вычислительного модуля первого типа (l=1, ..., и) соединен с третьим информационным входом (i,l)-го вычислительного модуля второго типа, первый информационный выход (КДго вычислительного модуля второго типа соединен с первым информационным входом (k+1, j+1)-го вычислительного модуля второго типа, первый информационный выход (n,j)-го вычислительного модуля второго типа соединен с первым информационным входом (1, J+1)-го вычислительного модуля второго типа, второй информационный выход (I j)-го вычислительного модуля второго типа соединен с вторым информационным

50 входом (i, j+1)-ro вычислительного модуля второго типа, вторые выходы (i, n)-ных вычислительных модулей второго типа соединен с выходами устройства, выход разрешения записи (i,l)-го вычислительного модуля первого типа соединен с входами разрешения записи (i, I+1)-го вычислительного модуля первого типа и (i, 1)-го вычислительного модуля второго типа.

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

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

1790785!

Составитель Ю.Каневский

Техред М.Моргентал Корректор 3.Салко

Редактор

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

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

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

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