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

1

(21)4497393/24-24

(22)21.10.88

(46) 15.08.90. Бюл. № 30

(72) А.В. Демидов, А.Н. Бондарь,

В.Г. Гриневич и А.Н. Семашко

(53)681.38(088.8)

(56)Заявка Великобритании № 2144245, кл. G 06 F 7/52, 1985.

Гун Суньюань. Систолические и волновые матричные процессоры для высокопроизводительных вычислений, ТИИЭР, т. 72, 1984, № 7, с. 140, рис. 8.

(54)УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ

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

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

(Л

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

СП

00

сд

00

( Sf

фиг i

10

15

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

Цель изобретения - снижение аппаратурных затрат.

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

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

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

Блок суммирования (фиг. 3) содер

о

ч

о, 1 i j 8 ;

.- г k

а.Ь,, ,8.

(2)

Сгруппируем элементы матриц Аи В (1) в блоки размерности рхр 2x2 и обозначим блоки матрицы А h,j(i 1 J ) а блоки матрицы

Результирующая матрица С также будет блоки р х р 2 х 2 f,- (, 1 1,4; j ),

Q

11

4i

3f

4f

rz 11

-«

2-2 23 (|

32

f33 34

- 1 t 4.3 14,

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

0. 1 f .

ij 1J IK

i, J

q

Ki

,,4.

(3)

30

Следовательно, no рекуррентной

формуле (3) сразу будут вычисляться

р элементов результирующей матриды

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

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

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

-. - v-v.-.x-K ciii-HciJi ли ичаикои I . ири этом через

жит первую 18 и вторую 19. группы вхо-40 мультиплексоры 11 разрешается прохождов, сумматоры 20, группу выходов 21, В ычислительный блок (фиг. 4) содержит первый 22 и второй 23 входы, per,, гистры 24 и 25, умножитель 26, первый 27 .и второй 28 выходы, регистр 29 и третий выход 30.

Работу устройства можно пояснить на примере умножения квадратных 8x8 матриц А .и В; А В С„

дение данных с информационных входов устройства к вычислительным блокам. Все регистры и сумматоры обнулены.

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

11 S

12

Чэ

И 4

элемента b ,, блоков q . , q ,,,, 4,,q, 50 причем элементы a,-j поступают на, вхо55

ды 10 , а элементы h,-j - на входы вычислительных модулей 2. ( ,4). На входы 15 и 16 управлени подается разрешающий сигнал логиче кая 1. Операнды а , через мультипл

Каждый элемент с результир-ующей матрицей С определяется: по рекуррентной формуле

, соры 11 поступают на первые входы

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

о

ч

о, 1 i j 8 ;

.- г k

а.Ь,, ,8.

(2)

Сгруппируем элементы матриц Аи В (1) в блоки размерности рхр 2x2 и обозначим блоки матрицы А h,j(i 1 J ) а блоки матрицы

15

Результирующая матрица С также будет блоки р х р 2 х 2 f,- (, 1 1,4; j ),

11

rz 11

-«

Q

4i

2-2 23 (|

3f

32

f33 34

4f

- 1 t 4.3 14,

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

0. 1 f .

ij 1J IK

i, J

q

Ki

,,4.

(3)

Следовательно, no рекуррентной

формуле (3) сразу будут вычисляться

р элементов результирующей матриды

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

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

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

ciii-HciJi ли ичаикои I . ири этом через

мультиплексоры 11 разрешается прохож40 мультиплексоры 11 разрешается прохож

дение данных с информационных входов устройства к вычислительным блокам. Все регистры и сумматоры обнулены.

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

11 S

12

Чэ

И 4

элемента b ,, блоков q . , q ,,,, 4,,q, 0 причем элементы a,-j поступают на, вхо10,

5

ды 10 , а элементы h,-j - на входы вычислительных модулей 2. ( ,4). На входы 15 и 16 управления подается разрешающий сигнал логическая 1. Операнды а , через мультиплексоры 11 поступают на первые входы

соры 11 поступают на первые входы

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

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

Таким образом, после первого такта работы в регистрах 29 результата вычислительного блока 13 вычислительных модулей 2 будут следующие операнды: a;,,b,- в вычислительном модуле 2.; a,b.j,- в вычислительном модуле a,j Ь ,j-,- в вычислительном модуле 2 ; а f-fb Tf- в вычислительном модуле 2.

На втором такте на информационные входы устройства поступают элементы

12

Зц

П

Ь, тех же блоков

25

h,-;(j 1 ,4) и qj,(,4), причем элементы аj поступают на входы 10, а элементы а а, - на входы 10, элементы Ь,,- на входы 10 J, элементы b ,- на входы всех вычислительных блоков 2 (,4), Элементы а , перепись вают- ся из регистров 24 вычислительных

30

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

На чертертом такте на первые входы 18 блока 8 суммирования поступают oneблоков 13„ в регистры 24 вычислитель- рации с выходов 21 блока 5 суммирования, а на вторые входы 19 - с выходов

ных блоков 1 3 jj. Элементы b переписываются из регистров 25 вычислительных 35 блоков 13, в регистры 25 вычислительных блоков 13,. Операнды из регистров 29 результата вычислительных блоков 13,j всех вычислительных модулей попарно поступают,на сумматоры 20 бло- 40 ков 5 и 5 суммирования. Элементы u ai II b г,записываются в первые 24 и вторые 25 регистры вычисли21 блока 5,j суммирования.

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

+а,, Ьэ1+ а,Ь 5-,+ г + а, Ь4,+ ,+

47

bа

fZ

+ а

1Ъ

211 - а ,1 b

на выходе 21j - , +

п Т2

23 3

.+ а.

а ,j bg, ; нл выходе J1+ а

+ на выходе 21 4 - 0.

тельных блоков 13, 13,

3 1. В

результате выполнения операций умножения в регистрах 29 результата вы- числительных модулей 2 . в конце 2-го такта будут следующие операнды: а fibi а, b,; (); на выходе 21, блока 5y. - a bji-b a jbjt;, на выходе 21гблока 5 а ,

5i на выходе 2 Ij, блока

n TI

на выходе 21.блока

+ а -рb-yi ; J, + а 5 2 - 0.

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

85804

кого О,

10

На четвертом такте сигналы логичес- задержанные на один такт в элементах 12 блоков 2, (,4), поступают соответственно на третьи входы мультиплексоров 11. Эти сигналы запрещают прием операндов по первым и одновременно разрешают прохождение операндов по вторым входам мультиплексоров 112. Через эти мультиплексоры проходят операнды соответственно с первых выходов вычислительных блоков 13 . Кроме этого, операнды Ь,блоков

q „, Чг, 1}, ,

q с вторых выходов.

15

20

25

-

30

вычислительных блоков 13 записываются соответственно в первые регистры блоков 142 памяти всех вычислительных модулей.

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

На чертертом такте на первые входы 18 блока 8 суммирования поступают one50

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

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

+а,, Ьэ1+ а,Ь 5-,+ г + а, Ь4,+ ,+

47

bа

fZ

+ а

1Ъ

211 - а ,1 b

на выходе 21j - , +

п Т2

23 3

.+ а.

5

0

а ,j bg, ; нл выходе J1+ а

+ на выходе 21 4 - 0.

Таким образом, в конце 4 такта на сумматоре 20, блока 8 суммирования будет сформирован первый элемент с, результирующей матрицы С, а на сумматорах 21 ,j и 21 - начнется формирование соответственно элементов с , и с.;,.

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

55

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

типлексоров,

щ, р вычислительных блоков

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

к|ов памяти, причем i-e входы первой и в1торой групп инфорк ационных входов ззычислительного модуля соединены с первыми информационны ш входами соот- Е1етственно i-ro и (i+p)-ro. мультиплексоров, рервый и втррой управляющие входы вычислительного модуля, подключены соответственно к управляющим входам первого и (р+1)-го мультиплексоров, управляющие выходы i-ro и (i+p)- го мультиплексоров подключены к входам соответственно i-ro и (i+p)- г6 элементов задержки, выходы которых подключены к управляюпщм )зходам соот- зетственно (i-H)-ro и (i-bp+1)-ro мультиплексоров , информационный выход

,5

0

0

5

Q

0

5

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

игЗ

ФигЛ