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

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

Известно устройство для умножения матрицы на вектор (авт.св. СССР № 1226484, кл. G 06 F 15/31, опублик. 23.04.86), содержащее N вычислительных модулей (ВМ) и блок управления. Алгоритм умножения матриц на этом устройстве осуществляется последовательно подачей на его первый информационный вход столбцов матрицы операнда. Недостатком этого устройства является большое количество информационных входов.

Наиболее близким к изобретению является устройство для перемножения матриц (авт.св. СССР Ns 1705836, кл. G 06 F 15/347. 17.10.89),- содержащее N ВМ, где , ..., N - размерность перемножаемых матриц, N-1 блоков регистров и блок синхронизации. Оно выбрано е качестве прототипа. Недостатком прототипа являются большие аппаратурные затраты.

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

На фиг, 1 изображена структурная схема устройства; на фиг. 2 - функциональная схема ВМ; на фиг. 3 - диаграмма работы устройства.

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

ВМ 1.i (фиг. 2) содержит умножитель 7, первый 9 и третий 10 регистры, первый мультиплексор 14, четвертый регистр 15, первый 17 и второй 20 триггеры, сумматор 21, блок 22 регистров, второй мультиплексор 23, третий 26 и четвертый 29 триггеры. Первый информационный вход 8 подключен к информационному входу первого регистра 9 и первому входу умножителя 7, второй

вход которого подключен к второму информационному входу 13 ВМ, информационному входу второго регистра 12 и первому информационному входу первого мультиплексора 14. Второй информационный вход

0 и управляющий вход последнего подключены соответственно к выходу второго регистра 12 и первому управляющему входу 18 ВМ, объединенному с информационным входом первого триггера 17, выход которого под5 ключей к информационному входу второго триггера 20, выход которого является первым управляющим выходом 19 ВМ. Первый 11 и второй 16 информационные выходы ВМ подключены соответственно к выходам

0 третьего 10 и четвертого 15 регистров, информационные входы которых подключены соответственно к выходам первых регистра 9 и мультиплексора 14. Выход умножителя 7 подключен к первому входу сумматора 21,

5 второй вход и выход которого подключены соответственно к выходу и информационному входу блока 22 регистров. Информационный вход блока 22 регистров подключен к первому информационному входу второго

0 мультиплексора 23, второй информационный вход которого является третьим информационным входом 24 ВМ. Третий информационный выход 25 ВМ подключен к выходу второго мультиплексора 23, управ5 ляющий вход которого подключен к выходу четвертого триггера 29 и второму управляющему выходу 28 ВМ. Второй управляющий вход 27 ВМ подключен к информационному входу третьего триггера 26, выход которого

0 подключен к информационному входу четвертого триггера 29.

Блок синхронизации содержит счетчики

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

При реализации процедуры умножения

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

-B( bjnHcm,(1)

к где ст 2 a i bjn; А матрица А порядка М х

0J 1

хК; aij - элемент матрицы А; В - матрица В

порядка К х М; bjn - элемент матрицы В; С - матрица С порядка М х К, полученная в результате произведения; . 2. .... М; , 2. 5 ..., К; .2, ..., М.

Рассмотрим работу устройства при ВМ (для простоты рассмотрим случай квадратных матриц ). Предполагается, что на вход 2 устройства подаются элементы матрицы А, на вход 3 - матрицы В. Количество регистров в блоке регистров 4 К-2. В данном устройстве в блоке 22 регистров будут три регистра, а в блоке регистров 4 - один. Все регистры внутри блоков регистров соединены последовательно и информация передается с входного регистра в последующие. Условимся, что информация в регистры принимается по переднему перепаду синхроимпульса. Элементы aij матрицы А поступают на первый информационный вход 2 устройства по столбцам, а элементы bjn матрицы В - на второй информационный вход 3 по строкам. Умножение матрицы А на В заключается в вычислении элементов матрицы С по формуле (1).

С11С22СЗЗ

С12С23С31

С13С21С32

На выходе первого дешифратора 34 формируется сигнал (условимся логический О), который выдается при поступлении на вход устройства первого элемента строки bji. При подаче на первый управляющий вход ВМ активного управляющего сигнала происходит разрешение записи информации в регистр 12, а мультиплексор 14 производит передачу информации с второго входа на его выход. Активный сигнал поступает через каждые три такта.

Первый такт. В ВМ 1.1. Во входные регистры умножителя 7.1 поступают данные an и он, в регистр 9.1 записываются an. a в регистр 12.1 - он. Управляющий сигнал с входа 18.1 записывается в триггер 17.1.

Второй такт. В ВМ 1.1. В умножителе 7.1 происходит умножение anbn и произведение записывается в его выходной регистр, а во входные регистры записываются новые исходные данные а21 и bi2- В регистр 10.1 записывается an, в регистр 9.1 - 321, а в регистр 15.1 - bi2. Управляющий сигнал с выхода триггера 17.1 записывается в триггер 20.1.

Третий такт. В ВМ 1.1. Произведение апЬц с выхода умножителя 7.1 в сумматоре 21.1 складывается с нулем и результат записывается во входной регистр бока 22.1 регистров. В умножителе 7.1 происходит умножение 32ibi2 и произведение записывается в его выходной регистр. На входы умножителя 7.1 поступают аз1 и bia. В регистр 10.1 записывается Э21, в регистр 9.1 - аз1, в регистр 15.1 - b 13. В ВМ 1.2. На входы умножителя 7.2 поступают соответственно an и bi2. В регистр 9.2 записывается an, a в регистр 12.2 - bi2. Управляющий сигнал с выхода триггера 20.1 через выход 19.1 ВМ 1.1 поступает на управляющий вход 18.2 и фиксируется в триггере 17.2.

Четвертый такт. В ВМ 1.1. Произведение 32ibi2 в сумматоре 21.1 складывается с нулем и результат записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение азтЬчз и произведение записывается в его выходной регистр, а во входные регистры умножителя 7,1 записываются входные данные ai2 и bai. В регистр 10.1 записывается аз1, в регистр 9.1 - ai2, а в

регистр 12.1 - D21. В ВМ 1.2. В умножителе 7.2 происходит умножение a nbi2 и произведение записывается в его выходной регистр. В регистр 10.2 переписывается an с регистра 9.2, а в него записывается 321. В

регистр 15.2 записывается bia.

Пятый такт. В ВМ 1.1. Произведение 33ibi3, пройдя через сумматор 21.1, записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение ai ib 12 и произведение .записывается а его выходной регистр. Во входные регистры умножителя 7.1 поступают новые входные данные 322 и Ь22. В регистр 10.1 переписывается данное ai2 с регистра 9.1. В регистр 9.1 записывается

322, а в регистр 15.1 - Ь22. В ВМ 1.2. Произведение a nbi2 с выхода умножителя 7.2 переписывается в блок 22.2 регистров. В умножителе 7.2 происходит умножение 32ibi3 и произведение записывается в его

выходной регистр. Во входные регистры умножителя 7.2 поступают входные данные аз1 и Ьц В регистр 10.2 записывается 821, в регистр 9.2 - аз1, в регистр 15.2 - Ьц. В ВМ 1.3. Во входные регистры умножителя 7.3

поступают an и bis. В регистр 9.3 поступает an, а а регистр 12.3 - bis.

Шестой такт. В ВМ 1.1. В сумматор 21.1 на второй входе блока 22.1 регистров поступает произведение anbn, оно суммируется с поступившим на первый вход произведение ai2b2i. Результат anbii+ai2b2i записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение 322b22 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают входные данные аз2 и Ь23. В регистр 10.1 поступает 312, в регистр 9.1 - аз2, в регистр 15.1 - Ь23. В ВМ 1.2. В блок 22.1

регистров записывается произведение 32ibi3. В умножителе происходит умножение азтЬп и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают ai2 и D22. В

регистр 10.2 поступает азк в регистр 9.2 - ai2, в регистр 12.2 - Ь22. В ВМ 1.3. В умножителе 7.3 происходит умножение апЬтз и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.3 записываются 321 и Ьц. В регистр 10.3

записывается an, в регистр 9.3 - 321, в регистр 15.3 - fan.

Седьмой такт. В ВМ 1.1 В сумматоре 21.1 происходит суммирование произведений 321012+322022 и сумма записывается в блок 22.1 регистров. В умножителе 7.1 происходит умножение аза и D23 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают ai3 и Ьзь В регистр 10.1 записывается 32., в регистр 9.1 -ai3. а в регистр 12.1 -Ьз1. В ВМ 1.2. В блок 22.2 регистров записывается произведение азтЬп. В умножителе 7,2 происходит умножение ai2D22 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.2 записываются 322 и 023. В регистр 10.2 записывается ai2, в регистр 9.2 - 322, в регистр 15.2 - D23. В ВМ 1.3. В блок 22.3 регистров записывается произведение апЬтз. В умножителе 7.3 происходит умножение 32lbn и произведение записывается в его выходной регистр. Во входные регистры поступают аз1 и bi2. В регистр 10.3 записывается 321, в регистр 9.3 - аз1, в регистр 15.3 - bia.

Восьмой такт, В ВМ 1,1, В сумматоре 21.1 происходит суммирование 33ibi3+a32b23 и результат записывается в блок 22.1 регистров. В умножителе 7,1 происходит умножение 31зЬз1 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают 323 и Ьз2- В регистр 10,1 записывается ai3. в регистр 9.1 - 323. в регистр 15.1 - Ьз2. В ВМ 1.2. В сумматоре 21.2 происходит суммирование 3nbi2+ai2b22 и результат записывается в блок 22.2 регистров. В умножителе 7.2 происходит умножение 322b23 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают 332 и Ь21- В регистр 10.2 записывается 322. в регистр 9.2 - аз2. в регистр 15.2 - Ь21. В ВМ 1.3. В блок 22.3 регистров ззписывается Э21Ьц. В умножителе 7.3 происходит умножение 33ibi2 и результат зэписывается в его выходной регистр. Во входные регистры умножителя 7.3 записываются an и Ь23. В регистр 10.3 записывается азь в регистр 9.3 - ai2, в регистр 12,3 - Ь23.

Девятый такт. В ВМ 1.1. В сумматоре 21.1 происходит суммировзние aiibii+ai2b2i+ai3b3i cii и результат через первый вход мультиплексора 23.1 поступает на выход 5 устройства. В умножителе 7.1 происходит умножение 32зЬз2 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают азз и Ьзз. В регистр 10.1 записывается

323, в регистр 9.1 - азз, в регистр 15,1 - Ьзз. В ВМ 1.2. В сумматоре 21.2 происходит суммирование a2ibi3+a22b23 и результат записывается в блок 22.2 регистров. В

умножителе 7.2 происходит умножение аз2Ь21 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают 331 и bi2. В регистр 10.2 зэписывзется эз2, в регистр 9.2 - Э1з. в

регистр 12.2 - Ьз2. В ВМ 1,3. В блок 22,3 регистров поступает 33ibi2. В умножителе 7.3 происходит умножение ai2b23 и результат записывэется в его выходной регистр. Во входные регистры умножителя 7.3 поступают 322 и Ь21. В регистр 10.3 поступает ai2, в регистр 9.3 - 322, а в регистр 15.3 - Ь21.

Десятый такт. В ВМ 1.1. В сумматоре 21.1 происходит суммирование a2ibi2+322b22+323b32 C22 и результэт выдается на выход 5 устройства. В умножителе 7.1 происходит умножение эззЬзз и произведение записывается в его выходной регистр. В регистр 10.1 записывается азз. В ВМ 1.2. В сумматоре 21.2 происходит суммирование аз1Ьп+аз2Ь21 и результат записывается в блок 22.2 регистров, В умножителе 7.2 происходит умножение 31зЬз2 и произведение записывэется в его выходной регистр. Во входные регистры умножителя 7.2 записывэются 323 и Ьзз. В регистр 10.2 записы- взется 313, в регистр 9.2 - 323, а в регистр 15.2 - Ьзз. В ВМ 1.3. В сумматоре 21.3 происходит суммирование anbi3+ai2b23 и результат записывается в блок 22.3 регистров.

В умножителе 7,3 происходит умножение 322b2i и результат записывается вето выходной регистр. Во входные регистры умножителя 7.3 записывэются аз2 и Ь22. В регистр 10.3 ззписывзется 322, в регистр 9.3 - аз2, з

в регистр 15.3 - Ь22.

Одиннадцатый такт: В ВМ 1.1. В суммэ- торе 21.1 происходит суммировэние эз1Ь13+эз2Ь23+аззЬзз сзз и результэт поступает на выход 5 устройства. В. ВМ 1.2. В

сумматоре 21.2 происходит суммирование 3iibi2+ai2b22+ai3b32 ci2 и результзт через мультиплексор 23.2 ззписывается в блок регистров 4.1. В умножителе 7,2 происходит умножение 32зЬзз и произведение записывэется в его выходной регистр. Во входные регистры умножителя 7,2 поступэют эзз и Ьз1. В регистр 10.2 записывается З2з, в регистр 9.2 - азз, з в регистр 15.2 - Ьзт. В ВМ 1.3, В сумматоре 21.3 происходит суммирование 32ibn+a22b2i и результат записывается в блок 22.3 регистров. В умножителе 7.3 происходит умножение аз2Ь22 и произведение зэписывэется в его выходной регистр. Во входные регистры умножителя 7.3 поступают 313 и Ьзз. В регистр 10.3 записывается аза. в регистр 9.3 - . а в регистр 12.3 - ЬззДвенадцатый такт. В ВМ 1.2. С выхода блока регистров 4.1 через второй вход мультиплексора 23.1 на выход 5 устройства выдается С12. В сумматоре 21.2 происходит суммирование 321Ь1з+а22Ь234а2зЬзз С23 и результат записывается в блок регистров 4.1. В умножителе 7.2 происходит умножение аззЬз1 и результат записывается в его выходной регистр. В регистр 10.2 записывается Э23. В ВМ 1.3. В сумматоре 21.3 происходит суммирование 331012+332022 и сумма записывается в блок 22.3 регистров. В умножителе 7.3 происходит умножение Э1зЬзз и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.3 поступают 323 и Ьз1. В регистр 10.3 записывается 313, в регистр 9.3 - 323. в регистр 15.3 -Ьз1.

Тринадцатый такт. В ВМ 1.2. С выхода блока регистров 4.1 на выход 5 устройства выдается С23. В сумматоре 21.2 происходит суммирование аз1Ьп+аз2Ь21+аззЬз1 сз1 и результат записывается в блок регистров 4.1. В ВМ 1.3. В сумматоре 21.3 происходит суммирование anbi2+ai2b23+ai3b33: ci3 и результат через мультиплексор 23.3 записывается в блок регистров 4.2. В умножителе 7.3 происходит умножение Э2зЬз1 и произведение записывается в его. выходной регистр. Во входные регистры умножителя 7.3 записываются азз и Ьз2. В регистр 10.3 записывается 323, в регистр 9.3 - азз, в регистр

15.3-D32.

Четырнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается сз1. С выхода блока регистров 4.2 в блок регистров 4.1 переписывается С1з. В сумма- торе 21.3 происходит суммирование a2ibn+322b2i+a23b3i C2i и результат записывается в блок регистров 4.2. В умножителе 7.3 происходит умножение аззЬз2 и результат записывается в его выходной ре- гистр. В регистр 10.3 записывается азз.

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

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

Семнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается последний результат матрицы сз2.

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

2 7

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

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

Авторское свидетельство СССР № 1705836, кл. G 06 F 15/347, 1989.

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

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

УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ МАТРИЦ, содержащее N вычислительных модулей (N - размерность перемножаемых матриц), N - 1 блоков регистров и блок синхронизации, каждый вычислительный модуль содержит четыре регистра, два мультиплексора, четыре триггере, блок регистров, умножитель и сумматор, причем первый и второй информационные входы первого вычислительного модуля являются соответственно первым и вторым информационными входами устройства, входы синхронизации ввода и вывода элементов матриц которого подключены соответственно к одноименным входам блока синхронизации, первый и второй выходы которого подключены соответственно к первому и второму управляющим входам первого вычислительного модуля, первый

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

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

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

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

0

5

0

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

Фиг.1

F

Фиг.1

1 г 3 4 SB 7 8 9 10 ft fZ 13 M

-I-I-I-I-I- -I-I-I-I-I-I-I-I

т

.183

Фиг.З

Составитель В. Червяцов Редактор Т, Юрчикова Техред М. МоргенталКорректор П. Гереши

I-I I-L

I