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

 

Изобретение относится к вычислительной технике, может быть использовано в специализированных вычислительных машинах для умножения квадратных матриц одного порядка и позволяет повысить быстродействие устройства за счет совмещения операций ввода компонентов матриц с операцией их умножения. Устройство содержит информационные входы 1 первой группы, информационные входы 2 второй группы, входы 3 для задания кода нуля, тактовый вход 4, матрицу вычислительных блоков 5 и информационные выходы 6. В основу работы устройства положен алгоритм умножения матрицы А а -. на матрицу В Ь ,-j , определяющий матрицу С С ,- j (i 1,...n; j 1...П, где n - порядок - ., , квадратной матрицы): С .. 2-. а ., b , .. J J При этом определение любого элемента С требует п-кратн6го вьптолнения Ь ,. . fcоперации накопления С : С .j +а Ь . . На входы 1 и 2 устройства в порядке, определенном на фиг. 1, подаются по тактам элементы матриц А и В. При этом на информационных выходах 6 устройства формируются числовые компоненты матрицы С. 2 ил. Q (Л со О5 4 М

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

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

РЕСПУБЛИН (511 4 G 06 F 15/347

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

К А BTOPCKOMY СВИДЕТЕЛЬСТВУ 1э 6 1 :,—;,;. (21 ) 409 76 85 /24-24 (22) 25. 07. 86 (46) 30. 12. 87. Бюл. 1Ф 48 (72) В. IT. Якуш, С. Г. Седухин, В.Д. Козюминский и Л.Б. Авгуль (53) 681. 333 (088. 8) (56) Гун Суньюань. Систолические волновые матричные процессоры для высокопроизводительных вычислений. -ТИИЭР, т. 72, 1984, Р 7, с. 140.

Патент Великобритании 11р 2144245, кл ° G 06 F 7/52, опублик. 1985. (54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ

МАТРИЦ (57) Изобретение относится к вычислительной технике, может быть использовано в специализированных вычислительных машинах для умножения квадратных матриц одного порядка и позволяет повысить быстродействие устройства за счет совмещения операций ввода компонентов матриц с операцией

„„SU„„1363247 . A i их умножения. Устройство содержит информационные входы 1 первой группы, информационные входы 2 второй группы, входы 3 для задания кода нуля, тактовый вход 4, матрицу вычислительных блоков 5 и информационные выходы 6.

В основу работы устройства положен алгоритм умножения матрицы

А =(a;.1 на матрицу В = (b Ij), определяющий матрицу С = (С;11 (1-=

=1,...n; j = 1...n, где и — порядок и квадратной матрицы): С = .Е а 1 b <.

При этом определение любого элемента

С; требует и-кратнбго выполнения

- Ч Ф .k-1 Ю операции накопления С " =C .. +а h

ij fk ki

На входы 1 и 2 устройства в порядке, определенном на фиг. 1, подаются по тактам элемеатыматриа А и В. При этом на информационных выходах 6 устройства формируются числовые компоненты матрицы С. 2 ил.

> и

1363247

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

Пель изобретения — повышение быстродействия устройства.

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

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

HHAopMaIJHoHHbIB выходы 6.

В состав каждого вычислительного блока 5 входят три регистра 7, 8 и

9, блок 10 умножения, сумматор 11, триггер 12 и (Т+1) элементов И 13 где Т вЂ” разрядность кода представления числовых компонентов перемножаемых матриц.

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

В основу работы устройства положен алгоритм умножения матрицы A=t a;)

) на матрицу В=(b ), определяющий матрицу С=(с; ) (1=1,...п; j=l,...n, где п - порядок квадратной матрицы):

a;Äbl, l

Определение любого элемента С ) требует и-кратного выполнения операции накопления (2) +а, .Ь„.

С = С

Особенностями функционирования устройства являются сдвиг накапливаемых сумм С на очередном такте

1) работы из iP-го вычислительного блока 5 (i 1,...п; Р=1,...n-1) в i(P+1)-й блок 5 и неподвижность элементов Ь,.

1) матрицы В. .В исходном состоянии триггеры 12 и регистры 7-9 блоков 5 устанавлива- . ются в нулевое состояние. На информационные входы 1 подаются по тактам соответствующие Т-разрядные элементы (Ь,;, 1) матрицы В с доцолнитель0, . ным (Т+1)-м единичным разрядом, представленной на фиг. 1 в форме тре- ". угольника., где 1 — номер такта работы устройства. На первом такте элемент b, записывается в регистр 7

r блока 5, . Ha втором такте элементы

Ь, Ь, b 2 записываются в регист1l 24 ры 7 соответственно блоков 5 2, 51

21 и 522 . Ha третьем такте элементы Ь ь 3

1й

b 2, Ь9, b и Ь записываются в регистры 7 соответственно блоков 5 1, 5, 5 „, 5 и 5 ь. На четвертом

b, Ь 4 и Ь « записываются в регис4 тры 7 блоков 5 4,, 542, 54s 5,4, 524 и 5 4 соответственно. Таким образом, для записи всех элементов матрицы В

)к в соответствующие блоки 5 требуется и тактов работы устройства, где и размерность матрицы В.

Рассмотрим работу блока 5 „ при записи в регистр 7 элемента Ь „ . На первом такте Т-разрядный элемент Ь и (Т+1)-й единичный разряд поступают соответственно на Т-разрядный ин; формационный вход регистра 7 и установочный вход триггера 12. В исходном состоянии с инверсного выхода триггера 12 подается единичный сигнал на вход признака записи регистра 7 и

1 элемент b записывается в регистр 7.

11

На вход синхронизации триггера 12 поступает тактовый сигнал, по заднему фронту которого триггер 12 устанавливается в единичное состояние, запре- . щая запись в регистр 7 блока 5 „ .

При этом открываются элементы И 13.

На последующих тактах работы устройства запись элементов матрицы В в регистр 7 блока 5 „ запрещена, и соответствующие Т-разрядные элементы матрицы (Ь;, 1) с дополнительным

Р

4п единичным разрядом проходя через открытые элементы R.13 в соседний диагональный блок 522 .

На вторые информационные входы 2 .устройства подаются по тактам соот46 ветствующие Т-разрядные элементы а .. матрицы А, представленной на фиг. 1

1) в форме параллелограмма. На первом такте элемент а записывается в ре11 гистр 8 блока 5,„. На втором такте элемент а, „ записывается в регистр 8 блока 5 а элементы а" и а запи2t > 21 12 сываются в регистры 8 блоков 5 „ и

512 соответственно. Закономерность записи соответствующих элементов а..

1)

55 матрицы А сохраняется и на последующих тактах.

Рассмотрим работу устройства при формировании Т-разрядных элементов

С „ и С 2„ . На первом такте элементы з 136 а,1 и b записываются в регистры 8, 11 и 7 аоответственно блока 5,„ и подаются на входы блока 10 умножения. С выхода блока 10 умножения произведение а Ь поступает на вход суммаI

11 тора 11, на второй вход которого поступают нули, так как регистр 9 блока 5,„ постоянно находится в нулевом состоянии. В результате на первом такте на выходе сумматора 11 формируI ется накапливаемая сумма С = О +

I м + а „ „ b „, . На втором . такте накапливаемая сумма С записывается в pe4r гистр 9 блока 5, . В блоке 5, аналогично формируется накапливаемая сумма

С2, =0+a2, b, . Вблоке52 с регистров 8 и 7 йа входы блока 10

2 умножения подаются элементы а и

2 12

Ь, соответственно. На выходе сумма21 тора 11 формируется накапливаемая сумма С,„= С, + а,2 Ь, . Ha треть-,.

2 ем такте в блоке 5 „, аналогично формируется накапливаемая сумма С, э э

= 0+ а, Ь„, в блоке 5, — сумма сумма С,„= С,„+ а „ b На четЗ 2 З,Э вертом такте в блоке 5 „ аналогично формируется накапливаемая сумма

С,= О+ a4,Ь„, в блоке 5, 4 3 .сумма С = С., + а4 Ь4,, в блоке

5 „, †. сумма С „ = С „ + a 2,з,b . B блоке 5, — сумма С „, = С „+ а Ь

На четвертом такте накапливаемая сумма С „, является значением элемента С „„ матрицы произведения С и подается на выход 61. На последующих тактах работы устройства аналогично

Р формируются остальные элементы С, матрицы произведения С, представленной на фиг. 1 в форме параллелограмма.

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

Устройство для перемножения матриц, содержащее матрицу из Р Р вычис лительных блоков, где P — порядок матрицы, причем каждый вычислительный блок содержит три регистра, блок умножения и сумматор, о т л и ч а— ю щ е е с я тем, что, с целью повышения быстродействия устройства, в каждый вычислительный блок введены триггер и (Т+1) элементов И, где Т— разрядность кода представления числовых компонентов перемножаемых матриц, 3247 4 причем информационный вход первого регистра первого вычислительного блока первой строки матрицы является первым информационным входом первой группы устройства, информационный вход первого регистра К=го вычислительного блока (К = 2,..., P) первой

4 строки матрицы является К-м информа-. ционным входом первой группы устройства, информационный вход первого регистра М-го выччслительного блока (M=2, Р) первого столбца матрицы является (P-1+M)-м информационным входом первой группы устройства, выходы с первого по (Т+1)-й элементов

И (К-1)-ro вычислительного блока (М-1)-й строки матрицы подключены к информационному входу первого регистра К-ro вычислительного блока M-Й строки матрицы, информационный вход второго регистра Н-ro вычислительного блока первой строки матрицы (H=l Р) является Н-м информацион25 ным ВхОдОм ВтОрой Группы устрОЙстВа1 выход второго регистра Н-ro вычислительного блока (M-1)-й строки матрицы подключен к входу второго регистра

Н-ro вычислительного блока M-й строЗ0 ки матрицы, информационные входы третьих регистров всех вычислительных

1 блоков первого столбца матрицы явля-ются входами для задания кода нуля устройства, выход сумматора Н-ro вы35 числительного блока (К-1)-го столбца матрицы подключен к информационному входу третьего регистра Н-го вычислительного блока К-го столбца матрицы, выход сумматора Н-го вычислитель40 ного блока Р-го столбца матрицы является Н-м информационным выходом устройства, тактовый вход устройства .подключен к входам признаков записи вторых и третьих регистров и к Входам

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

50 с первыми ВхоДами с перВОГО по (T+1)-Й, элементов,И соответственно того же вычислительного блока матрицы, первый вход (Т+1)-ro - элемента И каждого вычислительного блока матрицы соеди- . нен с информационным входом триггера того же вычислительного блока матрицы, инверсный и прямой выходы триггера каждого вычислительного блока матрицы подключены к входу признака за13632

Составитель А. Мишин

Редактор А. Маковская Техред M.Äèäûê Корректор Л.Пилипенко

Тираж 671 Подписное

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

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

Заказ 6364/42

Производственно-полиграфическое предприятие, r,Óæãîðîä, ул.Проектная, 4 писи первого регистра и к вторым входам всех элементов И соответственно того же вычислительного блока матрицы, выходы первого и второго регистров каждого вычислительного блока подключены к входам первого и второго сомножителей соответственно блока

47

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