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

 

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

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

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

РЕСПУБЛИК (s>>s G 06 F 15/

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

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

К ПАТЕНТ.У 3

О

О

00 ()ь, 1Ы (21) 4880893/24 (22) 05,11.90 (46) 23,01,93, Бюл, ¹ 3 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêoâñêèé, Ю.С,Каневский, М.К.Клименко и С,Г.Овраменко (73) Киевский политехнический институт (56) Авторское свидетельство СССР

¹ 1363247, кл, G 06 F 15/347, 1986.

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

¹ 1552200, кл. G 06 F 15/347, 1988, (54) УСТРОЙСТВО Дл : УМНОЖЕНИЯ МАТРИЦ. Ж„„1790786 А3 (57) Устройство для умножения матриц относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами. Целью изобретения является повышение быстродействия. Новым в устройстве для умножения матриц, содержащем пхп вычислительных модулей первого 1 типа и блок 3 управления, является введение вычислительных модулей 2 второго типа и два коммутатора 4, 5, которое позволяет организовать непрерывную обработку трех матриц. за счет чего быстродействие повышается в 2 раза 2 з и ф-лы, 4 ил.

1790786

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

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

2 второго типа, блок 3 управления, коммутаторы первой 4 и второй 5 групп.

Вычислительный модуль первого типа (фиг. 2) содержит первый регистры 6, 7, умножитель 8, сумматор 9, регистр 10, триггер 11.

Вычислительный модуль второго типа (фиг, 3) содержит первый регистр 12, сумматор 13, умножитель 14, регистры 15, 16.

Блок 3 управления (фиг,4) содержит элемент ИЛИ 17, счетчик 1,8, дешифратор 19, элемент НЕ 20, регистры 21.

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

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

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

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

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

19 дешифрирует состояние нуля. На первые входы вычислительных модулей первого типа первого столбца поступают элементы а матрицы А по строкам, на вторые входы—

5 элементы bkj матрицы B по столбцам, Элементы 018 матрицы С поступают на первые входы вычислительных модулей 2,1,1 — 2.п,1 по строкам

Ь «Ь12Ь13

Ь21Ь22Ь23

Ьз1 ЬзгЬзз

d «d12d13

d21d22d23

d31d32d33 а11а1га1з

821822823 аз1азгазз 1Ф2 13 т21тггтгз

f31f32f33

d «d12d 13

d21d22d23

d31d32d33

С«С12С13

С21022С23

С31С32СЗЗ

Результирующая матрица получена сле20 дующим образом:

f« = d «0«+ о21021+ d31031 т21 = d22021 + d32031 + d120«;

f31 = о33031 + d13c«+ d23021, f12 = d «012 + о21022 + d31032, f22 = О22022 + О32032 + О12012, f32 = оззсзг + d13ñ12 + d23022:

f13 = d«013+ d21023+ о31033: тгз = d22c23 + d32033 + d12013: тзз = d33033 + d13Ñ13 + d23023, 25

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

7,1,1, На первый и второй входы вычислительного модуля 1.2.1 соответственно поступают Ь12 и 821 и записываются соответственно в регистры 6,2,1 и 7.2.1. На первый и второй входы вычислительного модуля 1,3,1 соответственно поступают Ь1з и аз1 и записываются соответственно в регистры 6.3.1 и 7,3,1.

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

45 6.1.1 и 7.1.1 элементы Ь«и 8«поступают на первый и второй выходы вычислительного модуля 1.1.1 и на первый и второй входы . умножителя 8,1.1, с выхода которого произведение Ь«а«поступает в сумматор 9.1.1, где складывается с нулем и записывается в регистр 10.1.1. На входы вычислительного модуля 1,1,1 поступают следующие элементы b21и 812 и записываются в регистры 6,1,1 и 7.1.1. На входы вычислительного модуля

1.1.2 поступают элементы b12 и 821 и записываются в регистры 6.1.2 и 7.1.2. На первый вход сумматора 9,2,1 вычислительного модуля 1.2,1 поступает произведение а2. Ь12, где складывается с нулем и записывается в

1790786 регистр 10.2.1. В регистры 6,2.1 и 7,2,1 соответственно записываются b22 и а22. В регистры 6.2.2 и 7.2.2 вычислительного модуля

1.2.2 соответственно записываются элементы b13 и а11. На первый вход сумматора 9,3.1 вычислительного модуля 1.3.1 поступает произведение a31b13 и складывается с нулем, результат записывается в регистр

10.3.1. В регистры 6.3,2 и 7.3.2 вычислительного модуля 1,3,2 соответственно записываются элементы Ь12 и а31.

Во втором такте с выхода регистра

10,1,1 вычислительного модуля 1.1.1 на второй вход сумматора 9.1,1 поступает произведение а»Ь», на первый вход которого с выхода умножителя 8.1,1 поступает 812Ь21 и результат 8»b»+812b21 снова записывается в регистр 10.1,1. В регистры 6,1.1 и 7.1.1 соответственно записываются элементы Ь31 и а13. на выходе сумматора 9.1.2 вычислительного модуля 1.1,2 будет сумма а21Ь11+О, которая записывается в регистр 1Р.1,2, В регистры 6.1.2 и 7.1,2 записываются

Ь21 и 822. В регистры 6,1.3 и 7,1,3 вычислительного модуля 1.1.3 записываются Ь1з и а21.

На входы сумматора 9.2.1 вычислительного модуля 1.2,1 поступают произведения a21b12. и 822Ь22 и с его выхода сумма а21Ьг2+а22Ь22 записывается в регистр 10.2.1. В регистры

6,2.1 и 7.2,1 записываются а23 и b32. На выходе сумматора 9.2,2 вычислительного модуля

1,2,2 появляется сумма a»b13+0 и записывается в регистр 10.2.2. В регистры 7,2,2 и

6.2.2 ЗапиСываЮтСя а12 и Ь23. В рЕгиСтры

7.2.3 и 6.2.3 вычислительного модуля 1.2,3 записываются а31 и Ь11. На входы сумматора

9.3.1 вычислительного модуля 1.3,1 поступают произведения а31Ь13 и 832b23 и результат а31Ь13+а32Ь2з записывается в регистр 10,3.1.

В регистры 7.3.1 и 6.3.1 записываются азз и Ь33. С выхсда СумматОра 9.3.2 а31Ь12+О вычислительного модуля 1.3,2 записывается в регистр 10,3,2, В регистры 7.3.2 и 6,3.2 записываются а32 и b22. В регистры 7,3,3 и

6,3,3 вычислительного модуля 1,3,3 записываются элементы а11 и Ь12 соответственно.

В третьем такте в сумматорах 9.1,1—

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

1.1,1 на третий выход поступает

a»b»+a12b21+a13b31 = d» и записывается в регистр 12,1,1 вычислительного модуля

12.1,1. На входы регистров 7,1,1 и 6.1.1 поступают элементы а» и Ь» новых матриц

1 I

А и В, В регистр 15,1,1 со второго входа вычислительного модуля 2.1.1 записывается элемент с» матрицы С. С выхода сумматора 9.1.2 вычислительного модуля 1,1,2 в

55 регистр 10.1,2 записывается а21Ь»+а22Ь21.

В регистры 7.1,2 и 6,1,2 соответственно записываются 823 и Ь31. С выхода сумматора

9,1.3 вычислительного модуля 1.1,3 в регистр 10,1,3, записывается a21b13+0, В регистры 7,1,3 и 6.1.3 записываются а22 и Ь23. В сумматоре 9.2,1 вычислительного модуля

1.2,1 получаем a21b12+a22b22+a23b32 = d22 и элемент d22 записывается в регистр 12,2,1 вычислительного модуля 2,2.1. На входы регистров 7.2.1 и 6.2,1 поступают элементы новых матриц. В регистр 15.2.1 записывается — c21. С выхода сумматора 9.2.2 вычислительного модуля 1,2.2 в регистр 10.2.2 записывается сумма 811Ь13+а12Ь23, В регистры 7.2.2 и 6.2.2 записываются элементы а13 и ьзз. С выхода сумматора 9,2.3 вычислительного модуля 1,2.3 в регистр 10.2.3 записывается а31Ь»+О. В регистры 7,2.3 и

6,2.3 записываются а32 и b21. В сумматоре

9.3.1 вычислительного модуля 1.3.1 получаем 831b13+832b23+833Ь33 = d33 и элемент бзз записывается в регистр 12.3.1 вычислительного модуля 2.3.1. В регистры 7.3.1 и 6.3.1 записываются элементы новых матриц.

В регистр 15,3.1 записывается сЗ1. С выхода сумматора 9.3.1 вычислительного модуля

1.3,2 в регистр 10.3,2 записывается

831Ь12+832Ь22, В регистры 7,3.2 и 6.3.2 записываются 833 и Ь32. С выхода сумматора

9.3.3 вычислительного модуля 1.3.3 в регистр 10.3.3 записывается а»Ь12+О. В регистры 7.3,3. и 6.3.3 записываются а12 и b22.

В четвертом такте в сумматоре 9,1,2 вычислительного модуля 1.1.2 получаем сумму а21Ь»+а22Ь21+а2зЬ31 = d21 и элемент d21 записывается в регистр 12.1.2 вычислительного модуля 2.1,2, В регистр 15.1.2 записывается с21. С выхода сумматора 9.1,3 вычислительного модуля 1.1.3 поступает а21Ь13+822Ь23 и записывается B регистр

10.1.3. В регистры 7,1.3 и 6.1.3 записываются а23 и Ь33. На входы умножителя 14,1,1 вычислительного модуля 2.1.1 поступают элементы d» и с», где происходит умножение d»c» и произведение поступает в сумматор 13.1,1, где складывается с нулем и б11c»+0 записывается в регистр 16,1,1, В регистр 12,1,1 записывается элемент d», а элемент с» передается B вычислигельный модуль 2.2.2 и записывается в регистр

15,2.2, 6 сумматоре 9,2.2 вычислительного модуля 1.2.2 получаем а11Ь13+а 12Ь23+813Ь33=

= d13 и элемент d13 записывается в регистр 12.2.2. С выхода сумматора 9.2.3 вычислительного модуля 1.2.3 получаем

831b»+832b22 и эта сумма записывается в регистр 10.2.3. В регистры 6.2,3 и 7.2.3 записываются b31 и азз. В сумматоре 9.2.1 вычислительного модуля 2.2.1 получаем сумму

1790786

dzzcz1+0, которая записывается в регистр

10.2.1, В регистр 12.2.1 записывается d22.

В сумматоре 9,2.1. B регистр 12.2.1 записывается dzz. В сумматоре 9.3,2 вычислительного модуля 1.3.2 получается а31Ь12+а32Ь22+аззЬ32 = б32 и записывается в регистр 12.3.1 вычислительного модуля

2.3.2. B регистр 15.3.2 записывается с31.

С выхода сумматора 9.3,3 вычислительного модуля 1,3.3 поступает allblz+a12bzz записывается в регистр 10,3,3. В регистры 7.3.3 и 6,3.3 записывается 813 и Ь32. С выхода сумматора 13.3.1 вычислительного модуля

2,3,1 поступает бззс31+О и записывается в регистр 16.3.1. B регистр 12.3.1 записываетCH б33.

B пятом такте в сумматоре 9.1.3 вычислительного модуля 1.1,3 получаем

821b13+822b23+823b33 = б23 и элемент б23 записывается в регистр 12.1.3 вычислительного модуля 2 1 3. В регистр 15 1, 3 записывается czl. С выхода сумматора

13.1,2 вычислительного модуля 2.1.2 поступает б11с11+б21с21 и записывается в регистр

16.1.2 вычислительного модуля 2.1.2. В регистр 12,1.2 записывается элемент dz1.

С выхода сумматора 13.1,1 вычислительного модуля 2.1.1 выдается б11с12+О и записывается в регистр 16.1,1, B регистр 12.1.1 записывается d11, В сумматоре 9,2.3 вычислительного модуля 1,2,3 получаем а31Ь11+a3zbzz+a33b31 =- б31 и элемент б31 записывается в регистр 10,2,3 вычислительного модуля 2.2.3, В регистр 15.2,3 записывается с31, С выхода сумматора

13.2.2 вычислительного модуля 2.2.2 выдается d33c31+d13c11 и записывается в регистр

16 2.2, В регистр 12.2.2 записывается б13, С выхода сумматора 13.2.1 вычислительного модуля 2,2.1 поступает d22c22+0 и записывается в регистр 16,2.1, В регистр 15.2.1 записывается cz3. В сумматоре 9,3,3 вычисл ител ьн ого модуля 1.3.3 получаем а11Ь12+а12Ь22+а13Ь32 = dlz и элемент б12 записывается в регистр 12,3.3 вычислительного модуля 2.3,3. В регистр 15.3.3 записывается с11, С.выхода сумматора

13,3,2 вычислительного модуля 2,3.2 поступает d22032+0 и записывается в регистр

16.3,2. В регистр 12.3,2 записывается d3z, С выхода сумматора 13.3.1 вычислительного модуля 2,3,1 поступает d33c32+0 и записывается в регистр 16,3.1, В регистр 15.3.1 записывается сзз.

В шестом такте в сумматоре 13,1.3 вычислительного модуля 2,1,3 получаем первый окончательный результат

d33c31+d13011+d23021 = f31, который записывается в регистр 14.1.3, В регистр 12.1.3 записывается б23, С выхода сумматора

13,1,2 вычислительного модуля 2,1,2 поступает d11с12+б21с22 и записыВается a регистр 16.1,2. В регистр 12.1.2 записывается dzl, С выхода сумматора 13.1,1 вычислительного модуля 2,1.1 поступает б11с13 и записывается в регистр 16.1.1. В сумматоре 13.2.3 вычислительного модуля 2.2,3 получаем

d11011+d21021+cI31c31 = f11 и результат f11 записывается в регистр 16,2.3. В регистр

15,2,3 записывается с32, С выхода сумматора 13.2.2 вычислительного модуля 2.2,2 поступает б33032+б13012 и записывается в регистр 16.2,2, B регистр 15.2.2 записывается с13. С выхода сумматора 13.2.1 вычислительного модуля 2.2.1 поступает dzzcz3+0 и записывается в регистр 16.2,1. В сумматоре

13.3.3 вычислительного модуля 2.3.3 получаем б22с21+бзгс31+б12с11 = fzl, а результат записывается в регистр 16.3.3, В регистр

12,3.3 записывается d12. С выхода сумматора 13,3.2 вычислительного модуля 2.3.2 поступает б22022+бзгсзз и записывается в регистр 16,3.2. В регистр 12.3.2 записывается d32. С выхода сумматора 13.3.1 вычислительного модуля 2,3,1 поступает бззс33+О и записывается в регистр 16,3.1, В седьмом такте в сумматоре 13,1.3 вычислительного модуля 2,1,3 получаем

d33c32+d13012+d23022 = f33 и результат f33 записывается в регистр 16.1.3, а с его выхода на выход устройства выдается f31, С выхода сумматора 13.1.2 вычислительного модуля

2.1.2 поступает б11с13+б21с23 и записыВается в регистр 16.1.2, B сумматоре 13.2,3 вычислительного модуля 2.2.3 получаем б11с12+б21с22+б31с32 = flz и результат записывается в регистр 16,2.3, с выхода которого на выход устройства выдается f11. В регистр

12.2,3 записывается б31. С выхода сумматора 13,2.2 вычислительного модуля 2.2.2 поступает бззс33+б13с13 и за и ис ы Ва ется В регистр 16,2.2, В сумматоре 13,3.3 вычислительного модуля 2.3,3 получаем

d22c22+d32c32+d12c12 = f22 и результат записывается в регистр 16.3,3, с выхода которого выдается fz1. B регистр 12,3,3 записывается

d1z. С выхода сумматора 13.3.2 вычислительного модуля 2,3.3 поступает cI22023+d32033 и записывается в регистр 16.3.2.

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

ci33c33+cI13c13+d23c23 = f33 и результат f33 записывается в регистр 16.1.3, с выхода которого выдается f32. В сумматоре 13,2.3 вычислительного модуля 2.2,3 получаем

d11c13+d21023+d21033 = f13 и результат записывается в регистр 16.2,3, с выхода которого выдается flz. В сумматоре 13,3.3 вычислительного модуля 2.3.3 получаем

1790786

622023+032033+312013 = 23 и результат записывается в регистр 14.3,3, с выхода которого выдается fate.

В девятом такте с выходов вычислительных модулей 2.1.3, 2,2,3 и 2.3.3 соответственно выдаются окончательные результаты т33, 23 т13.

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

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

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

55 го и второго типов соединены соответственно с вторыми информационными входами (i+1,s)x вычислительных модулей первого и второго типов (где в = j-1 при (i+j) — четном или s = j+1 при (i+j) — нечетном, причем s = j при j = 1, j = и), третий информационный выход (Ц)-го вычислительного модуля первого типа соединен с третьим информационным входом (i,j)-го вычислительного модуля второго типа.

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

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

1790786

:1 ) j з

1 (3.. (19 I

Э.

+ 21

)3

1 (1

) с 3

Составитель Е.Мурзина

Техред М.Моргентал Корректор Т.Вашкович

Редактор

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

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

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

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