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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных , в том числе и систолических устройств, предназначенных для выполнения операций нэд матрицами. Целью изобретения является упрощение устройства за счет уменьшения числа информационных входов. Устройство для умножения матриц содержит матрицу из N х N вычислительных модулей и блок управления. Вычислительный модуль 1 ,l.j(i, j 1, N) содержит умножитель 3. регистры 4,5,6,7,10 и 11, сумматор 8, мультиплексор 9 и триггеры 12 и 13. 3 йл.

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

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

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

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

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) СПИСАНИЕ ИЗОБ ЕТЕНИЯ, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4930806/24 (22) 23.04.91 (46) 23.08.93. Бюл. М 31 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) Р. Выжиковски, Ю.С. Каневский, И.А. Кириченко, М.К. Клименко и С.Г. Овраменко (56) Патент Великобритании М 2144245, . кл. G 06 F 7/52, опублик. 1985.

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

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

„„5U„„1835548 А1 (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение. относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами. Целью изобретения является упрощение устройства за счет уменьшения числа информационных входов. Устройство для умножения матриц содержит матрицу из N х М вычислительных модулей и блок управления. Вычислительный модуль 1.Ц(1, l = 1, N) содержит умножитель 3, регистры 4,5,6,7;10 и 11, сумматор 8, мультиплексор 9 и триггеры 12 и 13. 3 ил.

1835548

25

Clj = ". alkbkf

k =1

55

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

Цель изобретения — упрощение устройства за счет уменьшения числа информационных входов.

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

Устройство для умножения матриц (фиг.1) содержит матрицу из N x N вычислительных модулей 1 (где N — порядок матрицы (N = 2г+ 1, г= 1,2,3,...) и блок управления 2.

Вычислительный модуль 1.1.) (1, J = 1, N) (фиг.2) содержит умно>китель 3, регистры 4—

7, сумматор 8, мультиплексор 9, регистры 10 и 11 и триггеры 12 и 13, Блок управления 2 (фиг,3) содержит генератор тактовых импульсов 14, счетчик 15 и дешифратор 16.

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

В основу работы устройства положен алгоритм умножения матрицы А = (а ) на матрицу В = (bi ), определяющий матрицу С

= (си) (i = 1...n, ) = 1...n, где n — порядок квадратной матрицы):

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

С) = С» + a;kbk .

k-1 (2)

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

В начале первого такта на входе запуска устройства присутствует единичный сигнал пуска, по которому в первом такте триггер

12 устанавливается в единицу, Кроме того, на первый информационный вход вычислительного модуля 1.1,1 поступает элемент

all, на второй информационный вход которого поступает элемент Ь|, эти элементы поступают соответственно в регистры 4.1.1 и 7,1,1 соответственно на первый и второй входы умножителя 3.1.1., с выхода которого произведение а Ь поступает на первый вход сумматора 8,1,1, на второй вход которого с третьего информационного входа поступает нуль. С выхода сумматора 8.1.1 сумма а11Ь11+ 0 поступает в регистр 10.1.1.

B вычислительном модуле 1.2,1 на информационные входы соответственно поступают элементы аг1 и Ьи. Злемент as< записывается в регистр 4.2.1, а элемент biz записывается в регистр 7,2.1 и соответственно в умножитель 3,2,1, с выхода которого произведение a21b12 поступает в сумматор 8,2,1, с выхода которого сумма аг Ь 2 + 0 поступает в регистр 10.2.1. В вычислительном модуле

1.3,1 в регистр 4,3.1. поступает элемент аз, а в регистр 7.3.1 — элемент Ь з. эти элементы соответственно поступают в умножитель

3.3.1, с выхода которого произведение аз Ь з через сумматор 8.3.1 поступает в регистр 10.3.1.

Во втором такте в вычислительном модуле 1.1,1 элемента а с выхода регистра

4.1.1 переписывается в регистр 5.1.1, а элемент Ь с выхода регистра 7,1.1 переписывается в регистр 6.",1, В регистры 4,1.1 и

7,1,1 соответственно записываются элементы азг и b22. С выхода умножителя 3.1.1

Выдается произведение a32b22, которое, пройдя через сумматор 8.1.1, записывается в регистр 11.1.1. В вычислительном модуле

1.2.1 элементы ац и b

4,2,1 и 7.2.1 соответственно переписываются в регистры 5,2.1 и 6,2,1, à в регистры 4,2.1 и 7.2,1 записываются соответственно a>z и

Ь з. С выхода умножителя 3.2.1 получаем произведение а гЬгз, которое, пройдя сумматор 8.2.1, поступает на первый вход мультиплексора 9,2.1, с выхода которого поступает в регистр 11.2.1. В вычислительном модуле 1;3.1 элементы аз и biz ñ выхода регистров 4,3,1 и 7.3.1 переписываются соответственно в регистры 5.3.1 и 6.3.1. С выхода умножителя 3,3.1 получаем произведение, которое, пройдя сумматор

8,3.1 и мультиплексор 9,3.1, поступает в регvtcTp 11,3,1.

B третьем такте в вычислительном модуле 1.1.1 элемент азг с выхода регистра 4.1.1 переписывается в регистр 5.1.1, а элемент

bz2 с выхода регистра 7.1.1 переписывается.в регистр 6.1.1, В регистры 4.1.1 и 7.1.1 соответственно записываются элементы а з и

Ьзз. С выхода умножителя 3.1,1 выдается произведение а зЬзз, которое, пройдя через сумматор 8.1.1, записывается в регистр

1835548 записываются соответственно а23 и b31, С 5 выхода умножителя 3.2.1 получаем произве10

15 элементы поступают соответственно в реги- 20 стры 4.1.2 и 7.1.2 и соответственно на пер25

35

11.1.1. В вычислительном модуле 1.2.1 элементы а12 и Ь23 с выхода регистров 4.2.1 и

7.2,1 соответственно переписываются в регистры 5,2.1 и 6.2.1, а в регистры 4.2.1 и 7.2.1 дение а33Ьз1, которое, пройдя сумматор

8.2,1, поступает на первый вход мультиплексора 9 .2.1, с выхода которого поступает в регистр 11.2.1. В вычислительном модуле

1.3.1 элементы а22 и b21 с выхода регистров

4.3.1 и 7.3.1 переписываются соответственно в регистры 5.3,1 и 6.3,1, С выхода умножителя 3.3.1 получаем произведение. которое, пройдя сумматор 8.3,1 и мультиплексор 9.3.1, поступает а регистр 11.3,1, В вычислительный модуль 1.1.2 поступает элемент а31, на второй информационный вход которого поступает элемент Ь12, эти вый и второй входы умножителя 3.1.2, с выхода которого произведение а31Ь12 поступает на первый вход сумматора 8.1,2, на второй вход которого с третьего информационного входа поступает a3zbzz и сумма

à31b12 + а32Ь22 с выхода сумматора 8;1.2 поступает в регистр 10.1.2, В вычислительном модуле 1.2.2 на информационные входы соответственно поступают элементы а11 и b 13. Элемент а11 записывается в регистр в умножитель 3.2.2, с выхода которого произведение a11b13 поступает в сумматор 8,2.2, с выхода которого сумма а11Ь13+ а12Ь2з поступает в регистр 10.2.2, В вычислительном модуле 1.3.2 в регистр 4.3,2 поступает элемент az1, а в регистр 7.3.2 — элемент b», эти элементы cooTBBTGTBBHHo поступают в умножитель 3.3.2, с выхода которого произведение az1b11 поступает а сумматор 8.3,2, с выхода которого сумма а21Ь11+ а22Ь21 поступает в регистр 10.3.2.

В четвертом такте в вычислительном модуле 1.1.1 элемент а23 с выхода регистра

4.1.1 переписывается а регистр 5.1,1, а элемент b33 с выхода регистра 7.1,1 переписывается в регистр 6.1,1. В регистры 4,1,1 и

7.1.1 соответственно записываются элементы новых матриц А и В а11 и Ь11 . С выхода

1 1 умножителя 3.1,1 выдается произведение а11 Ь11, которое, пройдя через сумматор

8.1.1, записывается в регистр 10.1.1, В вычислительном модуле 1.2.1 элементы азз и . Ь31 с выхода регистров 4.2.1 и 7.2.1 соответственно переписываются в регистры 5.2,1 и

6.2.1, а а регистры 4,2.1 и 7.2.1 записываются соответственно элементы az1 и Ь12 . В

1 1 вычислительном модуле 1.3.1 элементы а13 и Ьз2 с выхода регистров 4.3.1 и 7.3;1 переписываются соответственно а регистры

5,3.1 и 6,3.1. В вычислительном модуле 1.1.2 элементы а31 и Ь12 с выхода регистров 4.1.2 и 7.1.2 соответственно переписыва;отся в регистры 5.1.2 и 6.1.2, а в регистры 4.1,2 и

7.1.2 поступают элементы а22 и Ь23, которые также поступают на входы умножителя

3.1.2, с выхода которого произведение

a22b23 поступает в сумматор 8.1.2, с выхода которого выдается сумма аггЬ2з+ а23Ь33, которая поступает а регистр 11,1.2, В вычислительном модуле 1,2.2 с выходов регистров

4.?.2 и 7.2.2 элементы а11и Ь13 соответственно переписываются в регистры 5.2.2 и 6,2.2, а в регистры 4.2.2 и 7,2,2 соответственно поступают элементы а32 и b21, которые также поступают в умножитель 3.2.2, с выхода которого произведение a3zb21 поступает а сумматор 8.2.2, с выхода которого сумма

a32b21+ а33Ь31 поступает в регистр 11.2.2. В вычислительном модуле 1.3.2 с выходов регистров 4.3.2 и 7.3.2 элементы az1 и b11 соответственно переписываются B регистры

5,3.2 и 6.3.2, а в регистры 4.3.2 и 7.3,2 записываются элементы а12 и Ь22. эти элементы поступают в умножитель 3.3.2, с выхода которого произведение а12Ь22 поступает в сумматор 8.3.2, с выхода которого сумма а12Ь22+ a13b32 поступает в регистр 11.3.2.

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

1.1.2 элементы а22 и b12 с выхода регистров

4,1,2» 7.1,2 соответственно переписываются в регистры 5;1.2 и 6.1,2, а а регистры 4.1.2 и 7.1.2 поступают элементы а13 и Ьз1, которые также поступают на входы умножителя

3, 1,2, с выхода которого произведение

a13b31 поступает в сумматор 8.1.2, с выхода которого выдается сумма a11b11+ a13b31, которая поступает в регистр 11.1.2. В вычислительном модуле 1.2.2 с выходов регистров

4.2.2 и 7.2.2 элементы а32 и b21 соответственно переписываются в регистры 5.2.2 и 6.2.2, а в регистры 4.2.2 и 7.2,2 соответственно поступают элементы а23 и b32, которые также поступают в умножитель 3.2.2, с выхода которого произведение a23b32 поступает в сумматор 8.2.2, с выхода которого сумк1а

a21b1z + а23Ь32 поступает а регистр 11.2.2. В вычислительном модуле 1,3.2 с выходов регистров 4.3.2 и 7,3.2 элементы а 2 и bzz соответственно переписываются в регистры

5.3,2 и 6,3.2, а в регистры 4.3.2 и 7.3.2 записываются элементы а33 и b33, эти элементы поступают а умножитель 3.3,2, с выхода которого произведение a33b33 поступает а сумматор 8.3,2, с выхода которого сумма а31Ь13+ аззЬ33 поступает в регистр 11,3.2, В вычислительном модуле 1.1.3 на первый информационный вход поступает элемент а21, который поступает в регистр 4.1.3, а на второй информационный вход аычислительно1835548 го модуля поступает элемент Ь1з, который поступает в регистр 7,1.3, эти элементы соответственно поступают на первый и второй входы умножителя 3,1.3, с выхода которого произведение a21b13 поступает на первый вход сумматора 8,1.3, на второй вход которого с третьего информационного входа поступает аггЬгз + а23Ь33 и сумма аг1Ь1з + а22Ь2з + агзЬзз = Сгз с выхода сумматора

8.1,3 поступает в регистр 10.1.3.

В вычислительном модуле 1.2.3 на информационные входы соответственно поступают элементы а31 и Ь11. Элемент аз1 записывается в регистр 4.2 3, а элемент Ь11 записывается в регистр 7.2.3 и соответственно в умножитель 3.2,3, с выхода которого произведение аз1Ь11 поступает в сумматор

8,2.3, с выхода которого сумма a31b11 + а32Ь21+ a33b31 = C31 поступает в регистр

10,2,3. В вычислительном модуле 1.3,3 в регистр 4,3.3 поступает элемент а11, а в регистр 7,3,3 — элемент Ь12, эти элементы соответственно поступают в умножитель

3.3.3, с выхода которого произведение

a11b12 поступает в сумматор 8.3.3, с выхода которого сумма э11Ь12+ а12Ь22+ а1зЬз2 = С12 поступает в регистр 10.3.3.

В шестом такте в вычислительном модуле 1,1,2 элементы э13 и Ь31 с выхода регистров 4.1.2 и 7.1,2 соответственно переписываются в регистры 5.1.2 и 6.1.2, В . вычислительном модуле 1.2.2 с выходов регистров 4.2,2 и 7.2,2 элементы а1з и b31 соответственно переписываются в регистры 5,2,2 и 6 2.2 В вычислительном модуле

1.3.2 с выходов регистров 4.3,2 и 7.3.2 элементы а33 и Ьзз соответственно переписываются в регистры 5 3 2 и 6 3 2. В вычислительном модуле 1.1.3 элементы а21 и Ь1з с выхода регистров 4.1,3 и 7.1.3 соответственно переписываются в регистры

5,1,3 и 6. I.З, а в регистры 4,1.3 и 7.1.3 соответственно поступают элементы а12 и b21, эти элементы соответственно поступают на первый и второй входы умножителя 3,1.3, с выхода которого произведение à12b21 поступает на первый вход сумматора 8.1.3, на второй вход которого с третьего информационного входа поступают а11Ь11+ а1зЬз1 и сумма a11b11+ 313b31+ а12Ь21- С11 с выхода сумматора 8.1.3 поступает в регистр 11,1,3, В вычислительном модуле 1.2.3 с выхода регистров 4,2,3 и 7,2,3 соответственно элементы а31 и Ь11 переписываются в регистры

5.2.3 и 6.2.3, э элементы агг и b11 соответственно записываются в регистры 4,2.3 и 7.2.3 и в умножитель 3.2.3, с выхода которого произведение а22Ь32 поступает в сумматор

8.2.3, с выхода которого сумма аг1Ь1г + переписываются s регистры 5,1,3 и 6,1.3. С выхода регистра 11.1,3 С32 выдается на вы50.ход устройства. В вычислительном модуле

1.2.3 с выхода регистров 4.2,3 и 7,2,3 соответственно элементы а22 и b32 переписываются в регистры 5,2.3 и 6.2.3, С выхода регистра 11.2.3 С13 выдается на выход уст55 ройства. В вычислительном модуле 1.3.3 с выходов регистров 4.3,3 и 7,3,3 соответственно элементы а32 и Ь23 переписываются s регистры 5,3,3 и 6.3.3, С выхода регистра

11,3.3 С21 поступает на выход устройства.

45 а2зЬзг + аггЬ32 = C22 поступает в регистр

11.2.3.

В вычислительном модуле 1.3.3 с выходов регистров 4.3.3 и 7,3.3 соответственно элементы а11 и b12 переписываются в регистры 5,3,3 и 7.3.3, эти элементы поступают в умножитель 3,3.3, с выхода которого произведение азгЬ23 поступает в сумматор 8.3.3, с выхода которого сумма аз1Ь1з + аззЬзз +

+азгЬгз = Сзз поступает в регистр 11,3.3.

В седьмом такте в вычислительном модуле 1.1.3 элементы а1г и Ь21 с выхода регистров 4.1.3 и 7,1,3 соответственна переписываются в регистры 5,1,3 и 6,1.3, а в регистры 4 1 3 и 7.1.3 соответственно поступают элементы а33 и b32, эти элементь: соответственно поступают на первый и второй входы умножителя 3.1.3, с выхода которого произведение аззЬз2 поступает на первый вход сумматора 8,1,3, с выхода которого сумма а31Ь12 + азгЬ22 + аззЬзг = Сзг поступает в регистр 11.1.3, с выхода которого С11 выдается на выход устройства. В вычислительном модуле 1.2,3 с выхода регистров 4.2.3 и 7.2.3 соответственно элементы а22 и b32 переписываются в регистры

5,2.3 и 6,2,3, а элементы а13 и Ьзз соответственно записываются в регистры 4.2,3 и 7.2,3 и в умножитель 3,2.3, с выхода которого произведение a22b32 поступает в сумматор

8.2.3. с выхода которого сумма а11Ь1з + а12Ьгз + а1зЬзз = C13 поступает в регистр

11.2.3, с выхода которого С22 выдается на выход устройства. В вычислительном модуле 1.3,3 с вь1ходов регистров 4.3.3 и 7.3.3 соответственно элементы азг и Ьгз переписываются в регистры 5.3.3 и 7.3.3, а в регистры 4,3.3 и 7,3.3 поступают элементы а23 и

b31, эти элементы поступают в умножитель

3.3.3, с выхода которого произведение агзЬз1 поступает в сумматор 8.3.3, с выхода которого сумма а21Ь11+ а22Ь21+ агзЬз1 = C21 поступает в регистр 11.3.3, с выхода которого С33 поступает на выход устройства.

В восьмом такте s вычислительном модуле 1.1.3 элементы азз и Ьзг с выхода регистров 4.1.3 и 7,1.3 соответственно

1835548

1О

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

11.1.3 на выход устройства выдается Сгз, С выхода регистра 11.2.3 на выход устройства выдается Сз . С выхода регистра 11,3.3 на выход устройства выдается Ciz, На этом вычисление матрицы С = А х В заканчивается, Формула изобретения

Устройство для умножения матриц, содержащее блок управления и матрицу из N х N вычислительных модулей (где И вЂ” порядок матрицы, N = 2r+ 1, г = 1,2...), каждыЙ из которых содержит первый, второй и третий регистрь1, умножитель. сумматор и первый триггер, причем первый информационный выход (Ц)-ro вычислительного модуля матрицы (i = 1„,N - 1, j = 1,..., N - 1) соединен с первым информационным входом (i + 1, j +

1)-ro вычислительного модуля матрицы, второй информационный выход (k, j)-ro вычислительного модуля матрицы (k;.N) соединен с вторым информационным входом (k, J+ 1)-го вычислительного модуля матрицы, третий информационный выход (k, N)-ro, вычислительного модуля матрицы соединен с k-м выходом устройства, первый и второй информационные входы (К, lj-го вычислительного модуля матрицы соединены соответственно с К-ми информационными входами первой и второй групп устройства, К-й информационный вход задания кода нуля которого соединен с третьим информационным входом (К, !)-го вычислительного модуля матрицы, управляющий вход которого соединен с выходом блока управления, при атом в каждом вычислительном модуле информационные входы первого и второго регистров соединены соответственно с первым и вторым информационными входами модуля, управляющий вход которого соединен с входом первого триггера и управляющим входом третьего регистра, выход умножителя соединен с входом первого слагаемого сумматора, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства за счет уменьшения числа информационных входов, в каждый вычислительный модуль введены четвертый, пятый и шестой регистры, мультиплексор и второй триггер, причем первый информационный выход (N, ))-го вычислительного модуля матрицы соединен с перВым информационным ВХОДОМ (1, j + 1)-го вычислительного модуля матрицы, третий информационный выход (l, j)-го вычисли5

10 тельного модуля матрицы (I = 2...N) соединен с третьим информационным входом (!1, j+ 1)-го вычислительного модуля матрицы, третий информационный выход (1, j)-го Bblчислительного модуля матрицы соединен с третьим информационным входом (N, j)-го

Вычислительного модуля матрицы, управляющий выход (K, j)-го вычислительного модуля матрицы соединен с управляющим

ВхОДОм (К, ) + 1)-го вычислительного модуля матрицы, при этом в каждом вычислитель-, ном модуле матрицы первый и второй информационные входы модуля соединены соответственно с первым и вторым входами

20 регистров, выходы которых соединены соответственно с первым и вторым информациОнными выходами модуля, третий информационный вход которого соединен с входом второго слагаемого сумматора, выход которого соединен с первым информационным входом мультиплексора и информационным входом третьего регистра, выход которого соединен с вторым ин30

35 формационным входом мультиплексора, выход которого соединен с информационным входом шестого регистра, выход которого соединен с третьим информационным выходом модуля, управляющий выход которого соединен с выходом второго триггера, вход которого соединен с выходом первого

40 триггера, Вход которого соединен с управляющим входом мул ьти пле ксора.

25 умножителя, Выходы первого и второго регистров соединены соответственно с информационными входами четвертого и пятого

1835548

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

Техред M.Моргентал Корректор А.Козориэ

Редактор

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

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

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

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