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

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных процессорах для обработки больших массивов данных. Цель изобретения - снижение аппаратурных затрат. Устройство содержит вычислительные блоки, сгруппированные в вычислительные модули, блоки суммирования, информационные входы и выходы, входы управления. Каждый вычислительный модуль содержит информационные входы и выходы, мультиплексоры, элементы задержки, блоки памяти и входы управления. Блок суммирования содержит информационные входы и выходы, сумматоры. Вычислительный блок содержит информационные входы и выходы, регистры операндов, умножитель и регистр результата. В основу работы устройства положен рекуррентный алгоритм перемножения N . N матриц, разбитых на блоки размерностью P . P (N кратно P). 3 з.п. ф-лы, 5 ил.

СООЭ СОВЕТСКИХ соцИАлистичесних

РЕСГ1УБ ЛИК рцs С 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

° °

z), ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЬГГИЯМ

ПРИ ГКНТ СССР 1 (21) 4497393/24-24 (22) 21,10.88 (46) 15.08.90. Бюл. К 30 (72) А.В. Демидов, А.Н. Бондарь, В.Г. Гриневич и A.Н. Семашко (53) 681,38(088.8) (56) Заявка Великобритании 9 2144245, кл. G 06 P 7/52, 1985, Гун Суньюань. Систолические и волновые матричные процессоры для высокопроизводительных вычислений, ТИИЭР, т. 72, 1984, N - 7, с. 140, рис. 8. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных процессорах для обработки больших массивов данных.

„„ЯУ„„1585804 А 1

Цель изобретения — снижение аппаратурных затрат. Устройство содержит вы" числительные блоки, сгруппированные в вычислительные модули, блоки суммирования, информационные входы и выходы, входы управления. Каждый вычислительный модуль содержит информацион ные входы и выходы, мультиплексоры, элементы задержки, блоки памяти и вхо. ды управления. Блок суммирования содерлжт информационные входы и выходы, сумматоры. Вычислительный блок содержит информационные входы и выходы, регистры операндов, умножитель и регистр результата. В основу работы уст. ройства положен рекуррентный алгоритм перемножения п х и матриц, разбитых на ф блоки размерностью р х р (и кратно р).

3 э.п. ф-лы, 5 ил.

С: 1585804

h„h

Г 1! hЯ hb4

А 1!т!

Г!1! "о!

Ч q!! " fb Ч!а ч!! Ч Ч хъ Ч!

"зъ 1а

Ь!с Г!4ъ Г!,!

q3ñ q ЬЪ ЧЗа

ЧФ! q4t ЧФЬ Ч!

1! 12 1а 14

21 f 22 23 с24

Я1 .а2 35 f 34

L 41 с 42 с 4.3 сФ4 с!, сс с!а ...с, Eàt с 21 с из ° ° с RS

b5| big Ь!а ° ° Ьil...а !! с@1 B! а! " 6!

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

На фиг. 1 представлена структурная схема устройства для умножения мат1О риц А и В размерности и хп (пунктиром выделен фрагмент, вход управления не показан); на фиг. 2-4 — составные элементы устройства для умножения матриц А и В дпя случая и х и = 8 х 8 и р х р = 2 х 2, где р — размерность блоков, на которые разбиваются перемножаемые матрицы (на фиг. 2 — структурная схема вычислительного мс1дуля; на фиг. 3 — структурная схема блока

20 суммирования, на фиг. 4 — структурная схема вычислительного блока); на фиг. 5 — последовательность ввода данных и получения результатов.

Устройство (фиг. 1) содержит ие1формационные входы 1, вычислительные модули выходы 3 вычислительных модулей,. входы блоков 4 суммирования, блоки 5 суммирования, выходы 6 блоков суммирования, вхоцы 7 блока суммиро1 вания, блок 8 суммирования, выход 9 устройства.

Вычислительный модуль (фиг. 2) содержит первую 10, и 10 2 и вторую 103 и 104 группы информационных входов, мультиплексоры 11, элементы 12 задерж-35 ки, вычислительные блоки 13, блоки

14 памяти, первый 15 и второй 16 управляющие входы, группу выходов 17.

Блок суммирования (фиг. 3) содержит первую 18 и вторую 19 группы вхо- 40 дов, сумматоры 20, группу выходов 21.

Вычислительный блок (фиг. 4) содержит первый 22 и второй 23 входы, ре-, . гистры 24 и 25, умножитель 26, первый

27 .и второй 28 выходы, регистр 29 и третий выход 30.

Работу устройства можно пояснить на примере умножения квадратных 8 х 8 матриц A,è В: А В = C,.

1 50

ft t! а lb ...ач (Ьll Ъг Ьfi Ь

Ч а!1 ас! а !а ...а!; Ь|! b!t brb ...Ъ!! а, а ° а!! ...аа! ° Ъа Ьас Ьаа ° ° ° Ьа = с! с ьс с!! ° с!!!

1) 55

Каждый элемент с результирующей матрицей С определяется по рекуррентной формуле с. =О, 1ci j<8;

1< а - г t (2) с1 . =- с", + а. Ь,, К=1,8. к!

Сгруппируем элементы матриц A..è В (1) в блоки размерности р х р = 2 х 2

H обозначим блоки матрицы А ii;j(i=

1,1=1,4; j=1, 1 1,4), а блоки матрицы

В с,"(= 1, 1; 1= 1,1) .

Результирующая матрица С также будет разбита на блоки p x р = 2 х 2 (i=1 1=1,4; j=1 1=1,4).

Блоки f; матрицы С также будут вычисляться йо рекуррентной формуле (2)

О й! !сс 0,„1 i, j <1;

f к = f " "+h q, К f, 1=1,4.

i) !J >к к)

Следовательно, по рекуррентной формуле (3) сразу будут вычисляться р элементов результирующей матрицы

С одного блока Й; . Соотношение (3) положено в основу работы предлагаемого устройства для умножения матриц.

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

В статическом режиме на входы 15 и 16 управдения подается разрешающий сигнал логической "1". При этогл через мультиплексоры 11 разрешается прохождение данных с информационных входов устройства к вычислительным блокам, Все регистры и сумматоры обнулены.

На первом такте (фиг. 5) на информационные входы устройства 1;(i--1,4) поступают 4 элемента а!, соответственно блоков h, 1ч12, 1!лэ, гг 1ч и 4 элемента Ь „, блоков q, q

1! 21 3! 41, причем элементы à, поступают на. входы 10„, а элементы Ь; — на входы 10з вычислительных модулей 2. (i= i 1;

1-1,4). На входы 15 и 16 управления подается разрешающий сигнал логическая "1". Операнды а „ через мультиплексоры 11, поступают ча первые входы вычислительного блока 13„„ а операнды

Ь„, через мультиплексоры 11 д — на вторые входы вычислительного блока 13 1„

4, 6

На четвертом такте сигналы логического "0" задержанные на один такт в, элементах 12„ блоков 2; (i=1 4), поступают соответственно на третьи входы мультиплексоров 11 . Эти сигналы запрещают прием операндов по первым и одновременно разрешают прохождение операндов по вторым входам мультиплексоров 11 . Через эти мультиплексоры проходят операнды соответственно с первых выходов вычислительных блоков

13 . Кроме этого, операнды Ь, блоков 1 7.

q,,q,,Ч, q с вторых выходов

Z11 91 1 9 вычислительных блоков 13 записываются соответственно в первые регистры блоков 14 7 памяти всех вычислительных модулей °

Вычислительные операции выполняются аналогично описанным. Исключение составляют операции сложения в сумматорах последнего блока 8 суммирова1 ния, в котором в накапливающих сумматорах 20 к ранее вычисленным операндам производится прибавление операндов, поступающих на первые и вторые входы блока 8 суммирования. Обнуле1 ние этих сумматоров происходит на следующем такте после вычисления каждого элемента с результирующей матрицы С.

На чертертом такте на первые входы

18 блока 8 суммирования поступают операции с выходов 21 блока 5 суммирования, а на вторые входы 19 — с выходов

21 блока 5< суммирования.

В конце четвертого такта работы устройства на выходах блока 8, суммирования будут сформированы следующие операнды: на выходе 21, — с „=а „Ь;, +

+а19 Ь91+ а75Ь 9-1+ а17 Ь.,„+ а 7 Ь 1+

+ a«b«+ а, ЬС1+ 1ВЬЭ1, н» выходе

211 а,„Ь 17+ а 1 ьЬ97+ а 1 Ь .+ а 17Ь7,; на выходе 21 9 — а 1Ь „, + а г Ь Э1+ а p +

+ а, 7 b; на выходе 21 + — О.

Таким образом, в конце 4 такта на сумматоре 20, блока 8„ суммирования будет сформирован первый элемент с

11 результирующей матрицы С, а на сумматорах 21 и 21 начнется формирование соответственно элементов с и с 1.

Аналогично вычисляются остальные элементы матрицы-результата С.

5 158580 (фиг. 2). Операнды а„ записываются в первые 24, а операнды Ь „ — во вторые .

25 регистры операндов (фиг. 4). После этого умножители 26 вычислительных блоков 13„, выполняют ойерацию умноже- 5 ния а Ь и результаты записываются в регистры 29 результатов. На этом первый такт работы устройства заканчивается. Остальные вычислительные блоки

13 вычислительных модулей 2; и сумма1О торы 20 блоков 5 и 8 суммирования произ-водят операции с нулевыми операндами, так как перед началом работы они были обнулены.

Таким образом, после первого такта работы в регистрах 29 результата вычислительного блока 13 вычислитель11 ных модулей 2 будут следующие операнды: а„ Ь,„ — в вычислительном модуле

2 ; а Ъ „ — в вычислительном модуле

2; а1 Ь, — в вычислительном модуле 2, а17Ь „,— в вычислительном модуле 2„.

kfa втором такте на информационные входы устройства поступают элементы а„, а,, Ь17, Ь7, тех же блоков

h;(j=1,4) и q,(i=1 4), причем элементы а, поступают на входы 10, а эле11 менты а, — на входы 101, элементы

bz, — на входы 10 >, элементы Ь вЂ” на входы 109 всех вычислительных блоков

2 (i=1,4). Элементы а „ перепись1ваются из регистров 24 вычислительных блоков 13и в регистры 24 вычислительных блоков 13,,„ Элементы Ь, переписы11 ваются из регистров 25 вычислительных 35 блоков 13 в регистры 25 вычислитель11 ных блоков 13,. Операнды из регистров

29 результата вычислительных блоков

13 всех вычислительных модулей пои парно поступают,на сумматоры 20 бло- 40 ! ков 5 и 5 суммирования. Элементы а „, а, Ь 1, Ь g, записываются в пер17. вые 24 и вторые 25 регистры вычислительных блоков 13,„, 13 „ 13 1 . В результате выполнения операций умно- 45 жения в регистрах 29 результата вычислительных модулей 2,. в конце 2-го такта будут следующие операнды: а «bz» а17 Ь, а 1Ь и (= 1); на выходе 21 . блока 5, — а1 b «+ а1 b 1, 50 на выходе 21 блока 5 7. — а 1 Ь 9 7+

+ а Ь,. на выходе 21 блока 5z а 9Ь 1 + а Ь „; на выходе 21„блока

51- О.

В регистрах 29 результата вычислительных блоков 13 вычислительных мо-. дулей 2 будут сформированы произведения в соответствии с поступивпыми операндами (фиг. 2 и 5).

Формула из оOpereния

1. Устройство для умножения матриц. содержащее m = ри вычислительных ièîäóëåé (п — размерность обрабатываемых матриц, кратная р; р — размер7 I 585804 8 ности блоков обрабатываемых матриц)„

i e u j e информационные входы которых (i=1,р; j=p+1;2p) образуют соответственно первую и вторую груп5 пы информационных входов устройства, отличающееся тем, что, с целью снижения аппаратурных затрат, устройство содержит 1-1 блоков суммирования (1=п/р), причем входы первой и aòoðoé групп К-го (К=1,1/2) блока суммирования подключены к соответствующим выходам групп выходов соответственно (2К-1)-го и 2К-ro вычислительнЫх модулей, группа выходов (1-1.)=го блока сумматоров является группой выходов устройства, входы первой и второй групп S-го блока суммирования (Б= г+1 r+t; r l/2+1/4+ ° ..+1/2t;t=

191/2) подключены к соответствующим вы- 20 ходам групп выходов соответственно (S-2t)-го и (S+2t+1)-ro блоков суммирования, управляющие входы вычислительных модулей образуют группу управляющих входов устройства. 25

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что,каждый вычислительный модуль содержит 2р мультиплексоров, 2р-1 элементов задержки, р вычислительных блоков и р блс- 30 йов памяти, причем i-е входы первой и второй групп информационных входов вычислительного модуля соединены с первыми информационными входами соответственно 1-го и (+р)-го мультиплексоров, первый и второй управляющие входы вычислительного модуля, подключены соответственно к управляющим входам первого и (р+1)-го мультиплексоров, управляющие Выходы i-ГО и (i+p)

ro мультиплексоров подключены к вхо4О дам соответственно 1-го и (х+р)го элементов задержки, выходы которых подключены к управляющим входам cooтветственно (i+1) го и (i+p+1) го мультиплексоров, информационный выход

i-ro мультиплексора подключен к первому входу (i, 1)-ro вычислительного блока, первый выход (i ч)-го вычислительного блока (v--1,р-1) подключен к первому входу (i v+t)-ro вычислительного блока, а первый выход (i.,р)-го вычислительного блока подключен к второму информационному входу i-го мультиплексора, информационный выход (i+p)-ro мультиплексора подключен к второму входу (1,i)-го вычислительного блока, второй выход (v,i)-го вычислчтельного блока подключен к второму входу (v+1 i)-ro вычислительного блока, второй выход (р,i)-го вычислительного блока подключен к входу i-го блока памяти, вы-. ход которого подключен к второму информационному входу (i+p)-го мультиплексора, третий выход (i,j)-ro вычислительного блока подключен к ((i-1)p+j)-му выходу вычислительного модуля.

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

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

1585804

4 4 de >Е Ои d» d22 d22

dn dn n ds da de d22 8п

° "0 1 1 1 1 1 1 1 1

° ° 1 0 0 0 0 0 0 1 1 а„а„

15r

dg

1У»

1585804

° ° s э

2 " З

ФЧ ре ev г ч

Составитель К. Кухаренко

Техред Л.Сердюкова Корректор В. Гирняк

Редактор Е. Копча

Тираж 5á9

Заказ 2327

Подписное

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

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

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