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

%г.-2

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

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

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

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

Вычислительный модуль 1.1.J (i, j 1, N) (фиг.2) содержит умножитель 3, регистры 4- 7, сумматор 8, мультиплексор 9, регистры 10 и 11 и триггеры 12 и 13.

Блок управления 2 (фиг.З) содержит генератор тактовых импульсов 14, счетчик 15 и дешифратор 16.

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

В основу работы устройства положен алгоритм умножения матрицы А aij на матрицу В bij, определяющий матрицу С fcij (i 1...n, j Т...п, где n - порядок квадратной матрицы):

И

У aikbkj. k 1

(1)

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

Cijk + aikbk|.

(2)

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

В начале первого такта на: входе запуска устройства присутствует единичный сигнал пуска, по которому в первом такте триггер 12 устанавливается в единицу. Кроме того, на первый информационный вход вычислительного модуля 1.1.1 поступает элемент

аи, на второй информационный вход которого поступает элемент bn, эти элементы поступают соответственно в регистры 4.1.1 и 7,1.1 соответственно на первый и второй входы умножителя 3.1.1., с выхода которого произведение anbn поступает на первый вход сумматора 8.1.1, на второй вход которого с третьего информационного входа поступает нуль. С выхода сумматора 8.1.1

сумма,anbn + 0 поступает в регистр 10.1.1. В вычислительном модуле 1.2.1 на информационные входы соответственно поступают элементы 321 и bia. Элемент 321 записывается в регистр 4.2.1, а элемент bi2 записыва5 е.тся в регистр 7.2.1 и соответственно в умножитель 3.2.1, с выхода которого произведение 321612 поступает в сумматор 8.2.1, с выхода которого сумма 32ibi2 + 0 поступает в регистр 10.2.1. В вычислительном м одуле

0 1.3.1 в регистр 4.3.1. поступает элем ент аз1, а в регистр 7.3.1 - элемент bia. эти элементы соответственно поступают в умножитель 3.3.1, с выхода которого произведение азтЬтз через сумматор 8.3.1 поступает в ре5 гистр 10.3.1.

Во втором такте в вычислительном модуле 1.1.1 элемента аи с выхода регистра 4.1.1 переписывается в регистр 5.1.1, а элемент bn с выхода регистра 7.1.1 переписы0 вается в регистр 6.1.1. В регистры 4.1.1 и 7.1.1 соответственно записываются элементы аз2 и Ь22. С выхода умножителя 3.1.1 выдается произведение аз2Ь22, которое, пройдя через сумматор 8.1.1, записывается

5 в регистр 11.1.1. В вычислительном модуле 1.2.1.элементы ai2 и bi2 с выхода регистров 4.2.1 и 7.2.Т соответственно переписываются в регистры 5.2.1 и 6.2.1, а в регистры 4.2.1 и 7.2.1 записываются соответственно 312 и

0 Ь23- С выхода умножителя 3.2.1 получаем произведение ai2b23, которое, пройдя сумматор 8.2.1, поступает на первый вход мультиплексора 9.2.1, с выхода которого поступает в регистр 11.2.1. В вычислитель5 ном модуле 1-.3.1 элементы аз1 и bisc выхода регистров 4.3.1 и 7.3.1 переписываются соответственно в регистры 5.3.1 и 6.3.1. С выхода умножителя 3.3.1 получаем произведение, которое, пройдя сумматор

0 8.3.1 и мультиплексор 9.3.1, поступает в регистр 11.3.1.

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

5 Ь22 с выхода регистра 7.1.1 переписывается в регистр 6.1.1. В регистры 4.1.1 и 7.1.1 соответственно записываются элементы 323 и Ьзз. С выхода умножителя 3.1.1 выдается произведение 32зЬзз, которое, пройдя через сумматор 8.1.1, записывается в регистр

11.1.1. В вычислительном модуле 1.2.1 элементы ai2 и Ьаз с выхода регистров 4.2.1 и 7.2.1 соответственно переписываются в регистры 5.2.1 и 6.2.1,3 в регистры 4.2,1 и 7.2.1 записываются соответственно а23 и Ьз1. С выхода умножителя 3.2.1 получаем произведение аззЬз1, которое, пройдя сумматор 8.2.1, поступает на первый вход мультиплексора .1, с выхода которого поступает в регистр 11.2.1. В вычислительном модуле 1.3.1 элементы а22 и D21 с выхода регистров 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 поступает элемент аз1, на второй информационный вход которого поступает элемент bi2, эти элементы поступают соответственно в реги- стры 4.1.2 и 7.1.2 и соответственно на первый и второй входы умножителя 3.1.2, с выхода которого произведение азгЬ12 поступает на первый вход сумматора 8.1.2, на второй вход которого с третьего информа- ционного входа поступает аз2Ь22 и сумма a3ihi2 + аз2Ь22 с выхода сумматора 8. 1.2 поступает в регистр 10.1.2. В вычислительном модуле 1.2.2 на информационные входы соответственно поступают элементы аи и Ь1з. Элемент аи записывается в регистр в умножитель 3.2.2, с выхода которого произведение anbi3 поступает в сумматор 8.2.2, с выхода которого сумма anbi3 + ai2b23 поступает в регистр 10.2.2. В вычислительном модуле 1.3.2 в регистр 4.3.2 поступает элемент 321, а в регистр 7.3.2 -элемент Ьп, эти элементы соответственно поступают в умножитель 3.3.2, с выхода которого произведение 32ibn поступает в сумматор 8.3.2, с выхода которого сумма a2ibu + 322b2i поступает в регистр 10.3.2.

В четвертом такте в вычислительном модуле 1.1.1 элемент Э23 с выхода регистра 4.1.1 переписывается в регистр 5.1.1, а элемент Ьзз с выхода регистра 7.1.1 переписы- вается в регистр 6.1.1. В регистры 4.1.1 и 7.1.1 соответственно записываются элементы новых матриц А иВ аи иЬп .Свыхода умножителя 3.1.1 выдается произведение aii1bn1, которое, пройдя через сумматор 8.1.1, записывается в регистр 10.1.1. В вычислительном модуле 1.2.1 элементы азз и Ьзт с выхода регистров 4.2.1 и 7.2.1 соответственно переписываются в регистры 5.2.1 и 6.2.1, а-в регистры 4.2.1 и 7.2.1 записывают- ся соответственно элементы 3211 и bi21. В вычислительном модуле 1.3.1 элементы атз и Ьз2 с выхода регистров 4.3.1 и 7.3.1 переписываются соответственно в регистры

5.3.1и 6.3.1. В вычислительном модуле 1.1.2 элементы аз1 и bi2 с выхода регистров 4.1.2 и 7.1.2 соответственно переписываются а регистры 5.1.2 и 6.1.2, а в регистры 4,1.2 и

7.1.2поступают элементы 322 и 023. которые также поступают на входы умножителя 3.1.2, с выхода которого произведение Э22023 поступает в сумматор 8.1.2, с выхода которого выдается сумма 322b23 + 32зЬзз, которая поступает в регистр 11,1.2. В вычислительном модуле 1.2.2 с выходов регистров 4.2. 7.2.2 элементы аи и bis соответственно переписываются в регистры 5.2.2 и 6.2.2, а в регистры 4.2.2 и 7,2.2 соответственно поступают элементы аз2 и Ь21, которые также поступают в умножитель 3.2.2, с выхода которого произведение аз2Ь21 поступает 0 сумматор 8.2.2, с выхода которого сумма зз2Ь21 + аззЬзт поступает в регистр 11.2.2. В вычислительном модуле 1.3.2 с выходов регистров 4.3.2 и 7.3.2 элементы 321 и Ьп соответственно переписываются в регистры 5.3.2 и 6.3.2, а в регистры 4.3.2 и 7.3.2 записываются элементы ai2 и Ь22, эти элементы поступают в умножитель 3.3.2, с выхода которого произведение ai2b22 поступает в сумматор 8.3.2, с выхода которого сумма ai2b22 + Э1зЬз2 поступает в регистр 11.3.2.

В пятом такте в вычислительном модуле 1.1.2 элементы 322 и b 12 с выхода регистров 4.1,2 и 7.1.2 .соответственно переписываются в регистры 5.1.2 и 6.1.2, а в регистры 4.1.2 и 7.1.2 поступают элементы Э1з и Ьз1. которые также поступают на входы умножителя 3.1.2, с выхода которого произведение 313D31 поступает в сумматор 8.1.2, с выхода которого выдается сумма anbn + а1зЬзь которая поступаете регистр 11.1.2. В вычислительном модуле 1.2.2 с выходов регистров 4.2.2 и 7.2.2 элементы аз2 и Ьг1 соответственно переписываются в регистры 5.2.2 и 6.2.2, а в регистры 4.2.2 и 7.2.2 соответственно поступают элементы 323 и Ьз2, которые также поступают в умножитель 3.2.2, с выхода которого произведение Э2зЬз2 поступает в сумматор 8.2.2, с выхода которого сумма 32ibi2 + Э2зЬз2 поступает в ре-гистр 11.2.2. В вычислительном модуле 1.3.2 с выходов регистров 4.3.2 и 7.3.2 элементы 312 и Ь22 соот- ветстЁенно переписываются в регистры 5.3.2 и 6.3.2, а в регистры 4.3.2 и 7.3.2 записываются элементы азз и Ьзз. эти элементы поступают в умножитель 3.3.2, с выхода которого произведение аззЬзз поступает в сумматор 8.3.2, с выхода которого сумма + аззЬзз поступает в регистр 11.3.2. В вычислительном модуле 1.1.3 на первый информационный вход поступает элемент 321, который поступает в регистр 4.1.3, а на второй информационный вход вычислительного модуля поступает элемент Ьчз, который поступает в регистр 7.1.3, эти элементы соответственно поступают на первый и второй входы умножителя 3,1.3, с выхода которого произведение 32ibi3 поступает на первый вход сумматора 8.1.3, на второй вход которого с третьего информационного входа поступает 322D23 + Э23РЗЗ И Сумма 321013 + 322b23 + 323D33 С23 С ВЫХОДЭ СуММЭТОра

8.1.3 поступает в регистр 10.1.3.

В вычислительном модуле 1.2.3 на информационные входы соответственно поступают элементы аз1 и Ьц. Элемент аз1 записывается в регистр 4.2,3, а элемент Ьц записывается в регистр 7.2.3 и соответст- венно в умножитель 3.2.3, с выхода которого произведение азтЬп поступает в сумматор 8.2.3, с выхода которого сумма азгЬп + 932b2t + аззЬз Сз1 поступает в регистр 10.2.3. В вычислительном модуле 1.3.3 в ре- гистр 4.3.3 поступает элемент аи, а в регистр 7,3.3 - элемент bi2. эти элементы соответственно поступают в умножитель 3.3.3, с выхода которого произведение anbi2 поступает в сумматор 8.3.3, с выхода которого сумма anbi2 + ai2b22 + Э1зЬз2 Ci2 поступает в регистр 10,3.3.

В шестом такте в вычислительном модуле 1.1.2 элементы а тз и Ьз1 с выхода регист- ров 4.1.2 и 7.1.2 соответственно переписываются в регистры 5.1.2 и 6.1.2. В вычислительном модуле 1.2.2 с выходов регистров 4.2.2 и 7.2,2 элементы ai3 и Ьз1 соответственно переписываются в регистры 5,2.2 и 6,2.2 В вычислительном модуле

1.3.2с выходов регистров 4.3.2 и 7.3.2 элементы азз и Ьзз соответственно переписываются в регистры 5.3.2 и 6.3.2. В вычислительном модуле 1.1.3 элементы.Э21

и bis с выхода регистров 4.1.3 и 7.1.3 соот- ветственно переписываются в регистры

5.1.3и 6.1.3, а в регистры 4,1.3 и 7.1.3 соответственно поступают элементы ai2 и Ь21, эти элементы соответственно поступают на первый и второй входы умножителя 3.1.3, с выхода которого произведение a i2bai поступает на первый вход сумматора 8.1.3, на второй вход которого с третьего информационного входа поступают anbn + Э1зЬз1 и сумма anbn +913031 + ai2b2i ° Си с выхода сумматора 8.1.3 поступает в регистр 11,1,3,

В вычислительном модуле 1.2.3 с выхода регистров 4.2,3 и 7.2,3 соответственно элементы аз1 и Ьц переписываются в регистры 5.2.3 и 6.2.3, а элементы 322 и Ьц соответст- венно записываются в регистры 4.2.3 и 7.2.3 и в умножитель 3.2.3. с выхода которого произведение Э22Ьз2 поступает в сумматор 8.2.3. с выхода которого сумма a2ibi2 +

Э2зЬз2 + 322b32 C22 поступает в регистр 11.2.3,

В вычислительном модуле 1.3.3 с выходов регистров 4.3.3 и 7.3.3 соответственно элементы аи и bi2 переписываются в регистры 5,3.3 и 7.3.3, эти элементы поступают в умножитель 3.3.3, с выхода которого произведение аз2Ь23 поступает в сумматор 8.3.3, с выхода которого сумма asibis + аззЬзз + +аз2Ь23 Сзз поступает в регистр 11.3.3.

В седьмом такте в вычислительном модуле 1.1.3 элементы ai2 и Ь21 с выхода регистров 4.1.3 и 7,1,3 соответственно переписываются в регистры 5.1.3 и 6.1.3, а в регистры 4.1.3 и 7.1.3 соответственно поступают элементы азз и Ьз2, эти элементы соответственно поступают на первый и второй входы умножителя 3.1.3, с выхода которого произведение аззЬз2 поступает на первый вход сумматора 8.1,3, с выхода которого Сумма 33lbl2 + 332b22 + ЭЗЗЬ32 С32

поступает в регистр 11.1.3, с выхода которого Си выдается на выход устройства. В вычислительном модуле 1.2,3 с выхода регистров 4,2.3 и 7.2.3 соответственно элементы 322 и Ьз2 переписываются в регистры 5,2.3 и 6.2.3, а элементы ai3 и Ьзз соответственно записываются в регистры 4.2.3 и 7,2.3 и в умножитель 3.2.3, с выхода которого произведение Э22Ьз2 поступает в сумматор 8.2.3, с выхода которого сумма ацЬ1з + ai2b23 + Э1зЬзз Ci3 поступает в регистр 11.2.3, с выхода которого С22 выдается на выход устройства. В вычислительном модуле 1.3,3 с выходов регистров 4.3.3 и 7.3.3 соответственно элементы аз2 и Ь23 переписываются в регистры 5.3.3 и 7.3.3, а в регистры 4.3.3 и 7.3.3 поступают элементы 323 и Ьз.1, эти элементы поступают в умножитель 3.3.3, с выхода которого произведение Э2зЬз1 поступает в сумматор 8.3.3, с выхода

КОТОРОГО Сумма Э21Ьц +322b21 + Э23Ь31 С21

поступает в регистр 11.3.3, с еыхода которого Сзз поступает на выход устройства.

В восьмом такте в вычислительном модуле 1.1.3 элементы азз и Ьз2 с выхода регистров 4.1.3 и 7,1.3 соответственно переписываются в регистры 5.1.3 и 6.1.3. С выхода регистра 11.1,3 Сз2 выдается на выход устройства. В вычислительном модуле 1.2.3 с выхода регистров 4.2.3 и 7.2.3 соответственно элементы Э22 и Ьз2 переписываются в регистры 5.2.3 и 6.2.3. С выхода регистра 11.2.3 Ci3 выдается на выход устройства. В вычислительном модуле 1.3.3 с выходов регистров 4.3,3 и 7.3.3 соответст-. венно элементы аз2 и Ь23 переписываются в регистры 5.3.3 и 6,3.3. С выхода регистра 11,3.3 C2i поступает на выход устройства.

В девятом такте с выхода регистра 11.1.3 на выход устройства выдается Сгз. С выхода регистра 11.2.3 на выход устройства выдается Сз1. С выхода регистра 11.3.3 на выход устройства выдается Ci2.

На этом вычисление матрицы С А х В заканчивается.

Формула изобретения Устройство для умножения матриц, содержащее блок управления и матрицу из N х N вычислительных модулей (где N - порядок матрицы, N 2r+ 1, г 1,2...), каждый из которых содержит первый, второй и третий регистры, умножитель, сумматор и первый триггер, причем первый информационный выход (l,j)-ro вычислительного модуля матрицы (I 1...N - 1. j 1,..., N - 1) соединен с первым информационным входом (I + 1, j + 1)-го вычислительного модуля матрицы, второй информационный выход (к, j)-ro вычислительного модуля матрицы (k 1...N) соединен с вторым информационным входом (k, j + 1)-го вычислительного модуля матрицы, третий информационный выход (k, N)-ro, вычислительного модуля матрицы соединен с k-м выходом устройства, первый и второй информационные входы (К, 1)-го вычислительного модуля матрицы соединены соответственно с К-ми информационными входами первой и второй групп устройства, К-й информационный вход задания кода нуля которого соединен с третьим информационным входом (К, 1)-го вычислительного модуля матрицы, управляющий вход которого соединен с выходом блока управления, при этом s каждом вычислительном модуле информационные входы первого и второго регистров соединены соответственно с первым и вторым информационными входами модуля, управляющий вход которого соединен с входом первого триггера и управляющим входом третьего регистра, выход умножителя соединен с входом первого слагаемого сумматора, отличающее с я

тем, что. с целью упрощения устройства за счет уменьшения числа информационных входов, в каждый вычислительный модуль введены четвертый, пятый и шестой регистры, мультиплексор и второй триггер, причем первый информационный выход (N, }-го вы- числительного модуля матрицы соединен с первым информационным входом (I, j + 1)-го вычислительного модуля матрицы, третий

информационный выход (I, j)-rp вычислительного модуля матрицы (I 2N) соединен с третьим информационным входом (I - 1, j + 1)-го вычислительного модуля матрицы, третий информационный выход (I, j)-ro вычислительного модуля матрицы соединен с третьим информационным входом (N, j)-ro вычислительного модуля матрицы, управляющий выход (К, )-го вычислительного модуля матрицы соединен с управляющим

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

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

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

Ф.иг.1

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

F

LL

л

«

ю

Д

Фиг.З