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

 

Устройство для перемножения матриц относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времени. Известное устройство для перемножения матриц имеет большое количество вычислительных модулей. Заявляемое устройство обладает на 2N - 2 меньшим количеством вычислительных модулей за счет их соединения в последовательную цепочку. Устройство для перемножения матриц содержит N вычислительных модулей , N - 1 блоков регистров и блок синхронизации . Вычислительный модуль содержит умножитель , четыре регистра, два мультиплексора, четыре триггера, сумматор и блок регистров. Блок синхронизации содержит два счетчика и два дешифратора . На информационные входы устройства поступают элементы матриц А и В, причем элементы матрицы А поступают по столбцам, а элементы матрицы В - по строкам. Во входные регистры умножителя поступают входные данные. С выхода умножителя произведения поступают в сумматор. Промежуточные результаты суммирования поступают в блок регистров , а окончательные результаты через мультиплексор поступают на выход устройства. Через регистры информация передается в следующие вычислительные модули. 3 ил.

(19) SU (1Ц 1839262 А1 (51} 5 066015 347 сотоз совктских

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК госудАРствкннок ПАткнтнок вкдомство сссР госllATEHT cccp}

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4763007/24 (22) 27.1139 (46) 30.12.93 Бюл. Na 48-47 (71) Киевский политехнический институт (72) Выжиковски Роман(РЦ Каневский Ю.С.; Клименко МК; Овраменко С.Г. (54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ

МАТРИЦ (57) Устройство дпя перемножения матриц относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времени. Известное устройство дпя перемножения матриц имеет большое количество вычислительных модулей Заявляемое устройство обладает íà 2N — 2 меньшим количеством вычислительных модулей за счет их соединения в последовательную цепочку. Устройство для перемножения матриц содержит N вычислительных модулей, N — 1 блоков регистров и блок синхрониза— ции. Вычислительный модуль содержит умножитель, четыре регистра, два мультиплексора, четыре триггера, сумматор и блок регистров. Блок синхронизации содержит два счетчика и два дешифратора. На информационные входы устройства поступают элементы матриц А и В, причем элементы матрицы А поступают по столбцам, а элементы матрицы

 — по строкам. Во входные регистры умножителя поступают входные данные. С выхода умножителя произведения поступают в сумматор. Промежуточные результаты суммирования поступают в блок регистров, а окончательные результаты через мультиплексор поступают на выход устройства. Через регистры информация передается в следующие вычислительные модули 3 ил.

1839262

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

Известно устройство для умножения матрицы на вектор (авт,св, СССР N.

1226484, кл, G 06 F 15/31, опублик. 23.04.86), содержащее N вычислительных модулей (ВМ) и блок управления, Алгоритм умножения матриц на этом устройстве осуществляется последовательно подачей на его первый информационный вход столбцов матрицы операнда, Недостатком этого устройства является большое количество информационных входов, Наиболее близким к изобретению является устройство для перемножения матриц (авт.св. СССР N 1705836, кл. 6 06 F 15/347, 17,10.89), содержащее N BM, где N=1, ..., N — размерность перемножаемых матриц, N-1 блоков регистров и блок синхронизации, Оно выбрано s качестве прототипа. Недостатком прототипа являются большие аппаратурные затраты.

Целью изобретения является сокращение аппаратных затрат.

На фиг, 1 изображена структурная схема устройства, на фиг. 2 — функциональная схема ВМ; на фиг. 3 — диаграмма работы устройства, Устройство для перемножения матриц (фиг. 1) содержит BM 1.I (i=1, N), блоки регистров 4л (i.=1, N — 1) и блок 6 синхронизации, причем первый 2 и второй 3 информационные входы BM 1,1 являются соответственно первым и вторым информационными входами устройства, входы синхронизации ввода и вывода элементов матриц которого подключены соответственно к одноименным входам блока б синхронизации, первый и второй выходы которого подключены соответственно к первому и второму управляющим входам ВМ 1.1. Первый и второй информационные выходы i-ro ВМ 1,i (i=1, N-1) подключены соответственно к первому и второму информационным входам

BM 1.i+1, первый и второй управляющие входы которого подключены соответственно к первому и второму управляющим выходам i-ro ВМ 1л. Третий информационный выход 5 BM 1.1 является выходом устройства, третий информационный вход i-ro BM подключен к третьему информационному выходу BM 1,i+1 через i-й блок регистров 4л.

BM 1.i (фиг. 2) содержит умножитель 7, первый 9 и третий 10 регистры, первый мультиплексор 14, четвертый регистр 15, первый 17 и второй 20 триггеры, сумматор

21, блок 22 регистров, второй мультиплек5

55 сор 23, третий 26 и четвертый 29 триггеры.

Первый информационный вход 8 подключен к информационному входу первого регистра

9 и первому входу умножителя 7, второй вход которого подключен к второму информационному входу 13 ВМ, информационному входу второго регистра 12 и первому информационному входу первого мультиплексора 14, Второй информационный вход и управляющий вход последнего подключены соответственно к выходу второго регистра 12 и первому управляющему входу 18 ВМ, объединенному с информационным входом первого триггера 17, выход которого подключен к информационному входу второго триггера 20, выход которого является первым управляющим выходом 19 ВМ. Первый

11 и второй 16 информационные выходы BM подключены соответственно к выходам третьего 10 и четвертого 15 регистров, информационные входы которых подключены соответственно к выходам первых регистра

9 и мультиплексора 14. Выход умножителя 7 подключен к первому входу сумматора 21, второй вход и выход которого подключены соответственно к выходу и информационному входу блока 22 регистров. Информационный вход блока 22 регистров подключен к первому информационному входу второго мультиплексора 23, второй информационный вход которого является третьим информационным входом 24 BM. Третий информационный выход 25 BM подключен к выходу второго мультиплексора 23, управляющий вход которого подключен к выходу четвертого триггера 29 и второму управляющему выходу 28 ВМ, Второй управляющий вход 27 ВМ подключен к информационному входу третьего триггера 26, выход которого подключен к информационному входу четвертого триггера 29, Блок синхронизации содержит счетчики

30 и 31, входы 32 и 33, дешифраторы 34 и 35.

При реализации процедуры умножения матрицы на матрицу устройство должно вычислять выражение вида

C=A В=(ая) (bj.Hñ ), (1) к где cia= >.à J bjn, А — матрица А порядка М х

J =1 хК; a;J — элемент матрицы А;  — матрица В порядка К х М; Ь п — элемент матрицы В; С— матрица С порядка M х К, полученная в результате произведения; i=1, 2..... М; j=l, 2. ..., К; п=1,2,...,M.

Рассмотрим работу устройства при К=3

ВМ (для простоты рассмотрим случай квадратных матриц K=M). Предполагается, что на вход 2 устройства подаются элементы матрицы А, на вход 3 — матрицы В. Количе1839262

20 ство регистров в блоке регистров 4 К-2. В данном устройстве в блоке 22 регистров будут три регистра, а в блоке регистров 4— один. Все регистры внутри блоков регистров соединены последовательно и информация передается с входного регистра в последующие, Условимся, что информация в регистры принимается по переднему перепаду синхроимпульса. Элементы aij матрицы А поступают на первый информационный вход 2 устройства по столбцам, а элементы bjn матрицы  — на второй информационный вход 3 по строкам.

Умножение матрицы А на B заключается в вычислении элементов матрицы С по формуле (1).

С11 С22 С33

С12 сгз С31

С13 С21 С32

На выходе первого дешифратора 34 формируется сигнал (условимся логический

"0"), который выдается при поступлении на вход устройства первого элемента строки

bj1. При подаче на первый управляющий вход BM активного управляющего сигнала происходит разрешение записи информации в регистр 12, а мультиплексор 14 производит передачу информации с второго входа на его выход. Активный сигнал поступает через каждые три такта.

Первый такт. В BM 1.1. Во входные регистры умножителя 7,1 поступают данные а» и b», в регистр 9.1 записываются а». а в регистр 12,1 — Ь11. Управляющий сигнал с входа 18.1 записывается в триггер 17.1.

Второй такт, B ВМ 1.1. В умножителе7.1 происходит умножение a»b» и произведение записывается в его выходной регистр, а во входные регистры записываются новые исходные данные az1 и b12. В регистр 10.1 записывается а» в регистр 9.1 — az1, а в регистр 15.1 — Ь1г, Управляющий сигнал с выхода триггера 17.1 записывается в триггер 20.1.

Третий такт. В ВМ 1.1. Произведение

311Ь11 с выхода умножителя 7.1 в сумматоре

21.1 складывается с нулем и результат записывается во входной регистр бока 22.1 регистров, В умножителе 7.1 происходит умножение 321b12 и произведение записывается в его выходной регистр. На входы умножителя 7.1 поступают 331 и b13. В регистр 10.1 записывается 321, в регистр 9,1— а31, в регистр 15.1 - Ь 13. В В М 1.2. ka входы умножителя 7,2 поступают соответственно

311 и Ь12. В регистр 9.2 записывается 3» а в регистр 12.2 — b1z. Управляющий сигнал с выхода триггера 20.1 через выход 19.1 ВМ

1,1 поступает на управляющий вход 18,2 и фиксируется в триггере 17.2.

Четвертый такт. В BM 1,1, Произведение a21b12 в сумматоре 21.1 складывается с нулем и результат записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение 331Ь13 и произведение записывается в его выходной регистр, а во входные регистры умножителя 7,1 записываются входные данные a12 и bz1. В регистр 10.1 записывается а31, в регистр 9.1 — 312, а в регистр 12.1 — bz1. В BM 1.2, В умножителе

7.2 происходит умножение а11Ь12 и произведение записывается в его выходной регистр. В регистр 10.2 переписывается а11 с регистра 9.2. а в него записывается az1. В регистр 15.2 записывается Ь13.

Пятый такт. В BM 1.1. Произведение

331Ь13, пройдя через сумматор 21.1, записывается в блок 22.1 регистров. В умножителе

7.1 происходит умножение a11b 12 и произведение.записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают новые входные данные 322 и Ь22.

В регистр 10.1 переписывается данное а1г с регистра 9.1. В регистр 9.1 записывается а22, а в регистр 15.1 — bzz. В BM 1.2. Произведение a»b12 с выхода умножителя 7.2 переписывается в блок 22.2 регистров, В умножителе 7,2 происходит умножение

321b13 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают входные данные а31 и Ь», В регистр 10.2 записывается а21, в регистр 9.2 — 331, в регистр 15.2 — Ь», B BM

1.3. Во входные регистры умножителя 7.3 поступают а» и b13. В регистр 9.3 поступает а», а в регистр 12.3 — Ь13, Шестой такт. В BM 1.1. В сумматор 21.1 на второй вход с блока 22.1 регистров поступает произведение а»Ь», оно суммируется с поступившим на первый вход произведение а1гЬг1. Результат 311Ь»+312Ь21 записывается в блок 22,1 регистров, В умножителе

7.1 происходит умножение а2гЬг2 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7,1 поступают входные данные азг и Ь23. В регистр 10.1 поступает а12, в регистр 9.1 — азг, в регистр 15.1 — bz3. В BM 1.2. В блок 22,1 регистров записывается произведение а21Ь13. В умножителе 7,2 происходит умножение аз1Ь11 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают а12 и bzz. В регистр 10,2 поступает а31, в регистр 9.2—

312, в регистр 12,2 — bzz. В ВМ 1.3. В умножителе 7.3 происходит умножение а»Ь13 и произведение записывается в его выходной регистр. Во входные регистры умножителя

7.3 записываются 321 и Ь11. В регистр 10.3

1839262 записывается 811, в регистр 9.3 — 821, в реги Стр 15.3 — b11.

Седьмой такт. В BM 1.1 В сумматоре

21.1 происходит суммирование произведений а21Ь12+а22Ь22 и сумма записывается в блок 22.1 регистров, В умножителе 7,1 происходит умножение а32 и bz3 и произведение записывается в его выходной регистр.

Во входные регистры умножителя 7.1 поступают а13 и b31. В регистр 10.1 записывается а22, в регистр 9.1 — а13, а в регистр 12.1 — Ь31, В ВМ 1,2, В блок 22.2 регистров записывается произведение а31Ь11. В умножителе 7.2 происходит умножение а12Ь22 и произведение записывается в его выходной регистр, BQ входные регистры умножителя 7,2 записываются а22 и Ь23. В регистр 10,2 записывается а12, в регистр 9.2 — 822, в регистр 15,2 — bz3. В BM 1.3. B блок 22.3 регистров записывается произведение a11b13, В умножителе 7.3 происходит умножение а21Ь11 и произведение записывается в его выходной регистр. Во входные регистры поступают а31 и b1z. В регистр 10,3 записывается а21, в регистр 9.3 — а31, в регистр 15.3 — Ь12.

Восьмой такт, В BM 1,1, В сумматоре

21.1 происходит суммирование а31Ь13+а32Ь23 и результат записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение a13b31 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают az3 и b32. В регистр 10,1 записывается

813, в регистр 9,1 — 823. в регистр 15.1 — Ьз2.

В BM 1.2. В сумматоре 21.2 происходит суммирование а11Ь12+а12Ь22 и результат записывается в блок 22.2 регистров. В умножителе 7.2 происходит умножение а22Ь23 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают 832 и Ь21. В регистр

10.2 записывается а22, в регистр 9.2 — а32, в регистр 15.2 — b21. В BM 1.3. В блок 22,3 регистров записывается a21b11. В умножителе 7.3 происходит умножение a31b12 и результат записывается в его выходной регистр. Во входные регистры умножителя

7.3 записываются а12 и bz3, В регистр 10,3 записывается а31, в регистр 9,3 — а12, в регистр 12.3 — Ь23.

Девятый такт, В BM 1.1. В сумматоре

21.1 происходит суммирование а11Ь11+812Ь21+а13Ьз1=с11 и результат через первый вход мультиплексора 23.1 поступает на выход 5 устройства. В умножителе 7.1 происходит умножение а23Ь32 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.1 поступают а33 и Ь33. В регистр 10.1 записывается

az3, в регистр 9.1 — а33, в регистр 15,1 — Ь33, В BM 1.2. B сумматоре 21.2 происходит суммирование 821Ь13+а22Ь23 и результат записывается в блок 22.2 регистров, В умножителе 7,2 происходит умножение

832Ь21 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают а31 и Ь12. В регистр

10,2 записывается a3z, е регистр 9.2 — a13, в регистр 12.2 — Ь32. В BM 1,3. В блок 22,3 регистров поступает а31Ь12. В умножителе

7.3 происходит умножение a12b23 и результат записывается в его выходной регистр.

Во входные регистры умножителя 7.3 поступают а22 и b21. В регистр 10,3 поступает 812. в регистр 9.3 — а22, а в регистр 15.3 — bz1.

Десятый такт. В BM 1.1. В сумматоре

21.1 происходит суммирование

821b12+822bz2+az3b32=c22 и результат выдается на выход 5 устройства. В умножителе 7.1 происходит умножение аззЬ33 и произведение записывается е его выходной регистр.

В регистр 10.1 записывается азз. В ВМ 1.2.

В сумматоре 21.2 происходит суммирование а31Ь11+аз2Ь21 и результат записывается в блок 22,2 регистров, B умножителе 7.2 происходит умножение a13b3z и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.2 записываются а23 и Ьзз. В регистр 10.2 записывается а1з, в регистр 9.2 — агз, а в регистр

15.2 — Ьзз. В BM 1.3, B сумматоре 21.3 происходит суммирование 811b13+812b23 и результат записывается в блок 22.3 регистров.

В умножителе 7,3 происходит умножение

a2zb21 и результат записывается в его выходной регистр. Во входные регистры умножителя 7,3 записываются аз2 и bzz. В регистр

10,3 записывается azz, в регистр 9.3 — а32, а в регистр 15.3 — Ь22.

Одиннадцатый такт.- В ВМ 1.1. В сумматоре 21,1 происходит суммирование а31Ь13+а32Ь23+аззЬзз=сзз и результат поступает на выход 5 устройства. В BM 1.2, В сумматоре 21.2 происходит суммирование а11Ь12+812Ь22+813Ь32=с12 и результат через мультиплексор 23.2 записывается в блок регистров 4.1. В умножителе 7,2 происходит умножение а2зЬ33 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7,2 поступают 833 и

Ь31, В регистр 10.2 записывается 823, в регистр 9.2 — а33, а в регистр 15.2 — b31, В ВМ

1,3. В сумматоре 21,3 происходит суммирование 821b11+azzbz1 и результат записывается в блок 22,3 регистров, В умножителе 7.3 происходит умножение a32b22 и произведение записывается в его выходной регистр.

Во входные регистры умножителя 7.3 посту1839262

35 и второй информационные выходы i-ro вычислительного модуля (i=1, N — 1), подключены соответственно к первому и второму информационным входам (i + 1)-ro вычислительного модуля, первый и второй управляющие входы которого подключены соответственно к первому и второму управляющим выходам i-ro вычислительного модуля, третий информационный выход первого вычислительного модуля является

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

55 пают а13 и Ь33. В регистр 10.3 записывается а32, в регистр 9,3 — a13, а в регистр 12.3 — Ь33.

Двенадцатый такт. В BM 1.2. С выхода блока регистров 4.1 через второй вход мультиплексора 23.1 на выход 5 устройства выдается с12. В сумматоре 21.2 происходит суммирование 321Ь13+322Ь23+323Ьзз=с23 и результат записывается в блок регистров

4.1. В умножителе 7.2 происходит умножение 333b31 и результат записывается в его выходной регистр. B регистр 10.2 записывается а23. В ВМ 1,3. B сумматоре 21.3 происходит суммирование a31b12+a32b22 и сумма записывается в блок 22.3 регистров. B умножителе 7.3 происходит умножение а13Ь33 и произведение записывается в его выходной регистр, Во входные регистры умножителя

7.3 поступают а23 и Ь31. В регистр 10.3 записывается а13, в регистр 9.3 — а23. в регистр

15.3 — Ьз1.

Тринадцатый такт. В BM 1.2. С выхода блока регистров 4.1 на выход 5 устройства выдается с23. В сумматоре 21.2 происходит суммирование а31Ь11+а32Ь21+а33Ь31=с31 и результат записывается в блок регистров

4,1. B BM 1.3. В сумматоре 21,3 происходит суммирование 311Ь12+312Ь23+313Ь33=с13 и результат через мультиплексор 23.3 записывается в блок регистров 4.2. В умножителе

7.3 происходитумножение а23Ь31и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.3 записываются а33 и Ь32. B регистр 10.3 записывается а23, в регистр 9.3 — а33, в регистр

15,3 — Ь32.

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

УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ.

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

Четырнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается с31. С выхода блока регистров 4.2 в блок регистров 4.1 переписывается с13. В сумматоре 21.3 происходит суммирование а21Ь11+аг2Ь21+а23Ь31=с21 и результат записывается B блок регистров 4,2, В умножителе 7.3 происходит умножение a33b32 и результат записывается в его выходной регистр. В регистр 10.3 записывается а33.

Пятнадцатый такт. С выхода блока буферных регистров 4.1 на выход 5 устройства выдается с13, а в блок регистров 4.1 с выхода блока регистров 4.2 переписывается с21, В сумматоре 21.3 происходит суммирование

331Ь12+332Ь22+333Ь32=с32 и результат записывается в блок регистров 4.2.

Шестнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается с21, 3 в блок регистров 4,1 записывается с32, Семнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается последний результат матрицы с32.

Таким образом, предложенное устройство выгодно отличается от прототипа, так как содержит на 2 N — 2 ВМ меньше, чем прототип. Кроме того, время вычисления произведения матриц в прототипе составляет Зх

xN -1, а в заявляемом устройстве — 2N .

2 2 (56) Джахадиш Х.В, и др. Матричные структуры для реализации итерационных алгоритмов. ТИИЭР, т, 75, 1987, рис. 6.

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

N. 1705836, кл. G 06 F 15/347, 1989.

18392б2

12 к выходу второго регистра и первому управляющему входу вычислительного модуля, объединенному с управляющим входом второго регистра и с информационным входом первого триггера, выход которого подключен к информационному входу второго триггера, выход которого является первым управляющим выходом вычислительного модуля, отличающееся тем, что. с целью сокращения аппаратурных затрат, третий информационный вход I-ro вычислительного модуля подключен к третьему информационному выходу (i + 1)-го вычислительного модуля через i-ый блок регистров, в каждом вычислительном модуле первый и второй информационные выходы подключены соответственно к выходам третьего и четвертого регистров, информационные входы которых подключены соответственно к выходам первых регистра и мультиплексора, выход умножителя подключен к первому входу сумматора, второй вход и выход которого подключены соответственно к выходу и информационному входу блока регистров, информационный вход которого подключен к первому информационному входу второго мультиплексора, второй информационный вход которого является третьим информацион10 ным входом вычислительного модуля, третий информационный выход которого подключен к выходу второго мультиплексора, управляющий вход которого подключен к выходу четвертого триггера и второму управляющему выходу вычислительного модуля, второй управляющий вход которого подключен к информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера, 1839262

1с

1 Г 3 4 Х 8 7 В У Ю ff sz 13 Я

Ф2

27Г

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

Редактор Т. Юрчикова

Закаэ 3407

Составитель В, Червяцов

Техред М, Моргентал Корректор П. Герещи

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

НПО "Поиск" Роспатента

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