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

ИСАНИЕ ИЗОБРЕТЕН союз совктскихСОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИКгосудАРствкннок ПАткнтноквкдомство сссР госплткнт сссР К АВТОРСКОМУ СВИДЕТЕЛЬ(71) Киевский политехнический институт(54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯМАТРИЦ(57) Устройство дпя перемножения матриц относится к вычислительной технике и может быть использовано при построении специализированныхвычислительных систем, функционирующих в реальном масштабе времени. Известное устройстводпя перемножения матриц имеет большое количество вычислительных модулей. Заявляемое устройство обладает на 2 й - 2 меньшим количествомвычислительных модулей за счет их соединения впоследовательную цепочку. Устройство для перем(19) Я 7 (1 Ц 1839262 А 1(1) 5 0 66 Р 15347 ножения матриц содержит М вычислительных модулей, Ч - 1 блоков регистров и блок синхрониза - ции, Вычислительный модуль содержит умножитель, четыре регистра, два мультиплексора, четыре триггера, сумматор и блок регистров. Блок синхронизации содержит два счетчика и два дешифратора. На информационные входы устройства поступают элементы матриц А и В, причем элементы матрицы А поступают по столбцам, а элементы матрицы В - по строкам. Во входные регистры умножителя поступают входные данные. С выхода умножителя произведения поступают в сумматор. Промежуточные результаты суммирования поступают в блок регистров, а окончательные результаты через мультиплексор поступают на выход устройства. Через регистры информация передается в следующие вычислительные модули 3 ил.Изобретение относится к вычислительной технике и может быть использовано при построении специализированных выцислительных систем, функционирующих в реальном масштабе времени.Известно устройство для умножения матрицы на вектор (авт,св, СССР М 1226484, кл, б 06 Р 15/31, опублик, 23.04.86), содержащее М вычислительных модулей (ВМ) и блок управления, Алгоритм умножения матриц на атолл устройстве осуществляется последовательно подачей на его первый информационный вход столбцов матрицы операнда, Недостатком этого устройства является большое количество информационных входов,Наиболее близким к изобретению является устройство для перемножения матриц (авт.св. СССР М. 1705836, кл. 6 06 Р 15/347, 17,10,89), содержащее М ВМ, где И=1 К - размерность перемножаемых матриц, Кблоков регистров и блок синхронизации, Оно выбрано в качестве прототипа, Недостатком прототипа являются большие аппаратурные затраты.Целью изобретения является сокращение аппаратных затрат,На фиг, 1 изображена структурная схема устройства, на фиг, 2 - функциональная схема ВМ; на фиг. 3 - диаграмма работы устройства,Устройство для перемножения матриц (фиг, 1) содержит ВМ 1, (=1, 1 ч), блоки регистров 4. (1=1, й - 1) и блок б синхронизации, причем первый 2 и второй 3 информационные входы ВМ 1,1 являются соответственно первым и вторым информационными входами устройства, входы синхронизации ввода и вывода элементов матриц которого подключены соответственно к одноименным входам блока б синхронизации, первый и второй выходы которого подключены соотве 1 ственно к первому и второму управляющим входам ВМ 1,1. Первый и второй информационные выходы -го ВМ 1, (=1, Ь) подключены соответственно к первому и второму информационным входам ВМ 1.1+1, первый и второй управляющие входы которого подключены соответственно к первому и второму управляющим выходам -го ВМ 1 л, Третий информационный выход 5 ВМ 1.1 является выходом устройства, третий информационный вход -го ВМ подклюцен к третьему информационному выходу ВМ 1,+1 через -й блок регистров 4 л.ВМ 1. (фиг, 2) содержит умножитель 7, первый 9 и третий 10 регистры, первый мультиплексор 14, четвертый регистр 15, первый 17 и второй 20 триггеры, сумматор 21, блок 22 регистров, второй мультиплек 5 10 15 20 25 30 35 40 45 50 55 сор 23, третий 26 и четвертый 29 триггеры. Первый информационный вход 8 подключен к информационному входу первого регистра 9 и первому входу умножителя 7, второй вход которого подключен к второму информационному входу 13 ВМ, информационному входу второго регистра 12 и первому информационному входу первого мультиплексора 14, Второй информационный вход и управляющий вход последнего подключены соответственно к выходу второго регистра 12 и первому управляющему входу 18 ВМ, обьединенному с информационным входом первого триггера 17, выход которого подключен к информационному входу второго триггера 20, выход которого является первым управляющим выходом 19 ВМ, Первый 11 и второй 16 информационные выходы ВМ подключены соответственно к выходам третьего 10 и четвертого 15 регистров, информационные входы которых подключены соответственно к выходам первых регистра 9 и мультиплексора 14. Выход умножителя 7 подключен к первому входу сумматора 21, второй вход и выход которого подключены соответственно к выходу и информационному входу блока 22 регистров. Информационный вход блока 22 регистров подклюцен к первому информационному входу второго мультиплексора 23, второй информационный вход которого является третьим информационным входом 24 ВМ. Третий информационный выход 25 ВМ подключен к выходу второго мультиплексора 23, управляющий вход которого подключен к выходу цетвертого триггера 29 и второму управляющему выходу 28 ВМ, Второй управляющий вход 27 ВМ подключен к информационному входу третьего триггера 26, выход которого подключен к информационному входу четвертого триггера 29,Блок синхронизации содержит счетчики 30 и 31, входы 32 и 33, дешифраторы 34 и 35.При реализации процедуры умножения матрицы на матрицу устройство должно выцислять выражение видаС=А В=(а;)(Ьп)=(с;4 (1)кгде св= а Ь;,; А - матрица А порядка М х=1хК; а; - элемент матрицы А; В - матрица В порядка К х М; Ьп - элемент матрицы В; С - матрица С порядка М х К, полученная в результате произведения; =1, 2, , М; )=1, 2, ,К;п=1,2М,Рассмотрим работу устройства при К=3 ВМ (для простоты рассмотрим случай квадратных матриц К=М). Предполагается, что на вход 2 устройства подаются элементы матрицы А, на вход 3 - матрицы В. Количе 1839262ство регистров в блоке регистров 4 К. В данном устройстве в блоке 22 регистров будут три регистра, а в блоке регистров 4 - один. Все регистры внутри блоков регистров соединены последовательно и информация передается с входного регистра е последующие, Условимся, что информация в регистры принимается по переднему перепаду синхроимпульса, Элементы а 1 матрицы А поступают на первый информационный вход 2 устройства по столбцам, а элементы Ь 1 п матрицы В - на второй информационный вход 3 по строкам, Умножение матрицы А на В заключается в вычислении элементов матрицы С по формуле (1),С 11 С 22 сззС 12 сгз СЗ 1С 1 З С 21 СЗ 2На выходе первого дешифратора 34формируется сигнал (условимся логический "0"), который выдается при поступлении на вход устройства первого элемента строки Ь 1. При подаче на первый управляющий вход ВМ активного управляющего сигнала происходит разрешение записи информации в регистр 12, а мультиплексор 14 производит передачу информации с второго входа на его выход, Активный сигнал поступает через каждые три такта,Первый такт, В ВМ 1,1. Во входные регистры умножителя 7,1 поступают данные а 11 и Ь 11, в регистр 9.1 записываются а 11. а в регистр 12,1 - Ь 11. Управляющий сигнал с входа 18.1 записывается в триггер 17.1.Второй такт, В ВМ 1.1. В умножителе 7.1 происходит умножение а 11 Ь 11 и произведение записывается в его выходной регистр, а во входные регистры записываются новые исходные данные а 21 и Ь 12, В регистр 10,1 записывается а 11, в регистр 9.1 - а 21, а в регистр 15.1 - Ь 1 г, Управляющий сигнал с выхода триггера 17.1 записывается в триггер 20.1.Третий такт, В ВМ 1.1. Произведение а 11 Ь 11 с выхода умножителя 7.1 в сумматоре 21.1 складывается с нулем и результат записывается ео входной регистр бока 22.1 регистров, В умножителе 7.1 происходит умножение а 21 Ь 12 и произведение записывается в его выходной регистр, На входы умножителя 7.1 поступают аз 1 и Ь 1 э. В регистр 10.1 записывается а 21, е регистр 9,1 - аз 1, в регистр 15.1 Ь 1 з. В ВМ 1.2. На входы умножителя 7,2 поступают соответственно а 11 и Ь 12. В регистр 9,2 записывается а 11, а в регистр 12.2 - Ь 1 г. Управляющий сигнал с выхода триггера 20.1 через выход 19.1 ВМ 1,1 поступает на управляющий вход 18,2 и фиксируется в триггере 17.2.Четвертый такт, В ВМ 1,1, Произведение а 21 Ь 12 в сумматоре 21.1 складывается с нулем и результат записывается в блок 22,1 регистров. В умножителе 7,1 происходит умножение аз 1 Ь 1 з и произведение записывается в его выходной регистр, а во входные регистры умножителя 7,1 записываются входные данные а 12 и Ь 21. В регистр 10.1 записывается аз 1, в регистр 9.1 - а 12, а в регистр 12.1 - Ь 21. В ВМ 1.2, В умножителе 7.2 происходит умножение а 11 Ь 12 и произведение записывается в его выходной регистр. В регистр 10.2 переписывается а 11 с регистра 9,2. а в него записывается а 21. В регистр 15,2 записывается Ь 1 з,Пятый такт. В ВМ 1.1. Произведение аз 1 Ь 1 з, пройдя через сумматор 21.1, записывается в блок 22.1 регистров, В умножителе 7.1 происходит умножение а 11 Ь 12 и произведение.записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают новые входные данные аг 2 и Ь 22. В регистр 10,1 переписывается данное а 12 с регистра 9.1. В регистр 9.1 записывается аг 2, а в регистр 15.1 - Ь 22. В ВМ 1.2. Произведение а 11 Ь 12 с выхода умножителя 7.2 переписывается в блок 22.2 регистров, В умножителе 7,2 происходит умножение а 21 Ь 1 з и произведение записывается в его выходной регистр. Во входные регистры умножителя 7,2 поступают входные данные аз 1 и Ь 11, В регистр 10,2 записывается а 21, в регистр 9,2 - аз 1, в регистр 15.2 - Ь 11, В ВМ 1.3. Во входные регистры умножителя 7.3 поступают а 11 и Ь 1 э. В регистр 9.3 поступает а 11, а в регистр 12.3 - Ь 1 з,5101520 25 30 35 40 45 50 55 Шестой такт. В ВМ 1,1. В сумматор 21.1 на второй вход с блока 22,1 регистров поступает произведение а 11 Ь 11, оно суммируется с поступившим на первый вход произведение а 12 Ь 21, Результат а 11 Ь 11+а 12 Ь 21 записывается е блок 22,1 регистров, В умножителе 7.1 происходит умножение а 22 Ь 22 и и роизведение записывается в его выходной регистр, Во входные регистры умножителя 7,1 поступают входные данные аз 2 и Ь 2 з. В регистр 10.1 поступает а 12, в регистр 9.1 - азг, в регистр 15,1 - Ьгз. В ВМ 1.2, В блок 22,1 регистров записывается произведение а 21 Ь 1 з. В умножителе 7,2 происходит умножение аз 1 Ь 11 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.2 поступают а 12 и Ь 22. В регистр 10,2 поступает аз 1, е регистр 9.2 - а 12, в регистр 12,2 - Ь 22. В ВМ 1.3, В умно- жителе 7.3 происходит умножение а 11 Ь 1 з и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.3 записываются а 21 и Ь 11, В регистр 10.3записывается а 11, в регистр 9,3 - а 21, в регистр 15,3 - Ь 11Седьмой такт. В ВМ 1.1 В сумматоре 21,1 происходит суммирование произведений а 21 Ь 12+а 22 Ь 22 и сумма записывается в блок 22.1 регистров, В умножителе 7,1 происходит умножение аз 2 и Ь 2 з и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.1 поступают аз и Ь 31, В регистр 10.1 записывается а 22, в регистр 9.1 - а 1 з, а в регистр 12.1 - Ьз 1, В ВМ 1,2, В блок 22.2 регистров записывается произведение аз 1 Ь 11. В умножителе 7,2 происходит умножение а 12 Ь 22 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7,2 записываются аг 2 и Ь 23. В регистр 10,2 записывается а 12, в регистр 9.2 - а 22, в регистр 15,2 - Ь 23. В ВМ 1.3. В блок 22.3 регистров записывается произведение а 11 Ь 13, В умножителе 7.3 происходит умножение а 21 Ь 11 и произведение записывается в его выходной регистр, Во входные регистры поступают аз 1 и Ь 12, В регистр 10,3 записывается а 21, в регистр 9.3 - аз 1, в регистр 15.3 - Ь 12,Восьмой такт, В ВМ 1,1, В сумматоре 21,1 происходит суммирование а 31 Ь 13+аз 2 Ь 23 и результат записывается в блок 22,1 регистров. В умножителе 7.1 происходит умножение а 13 Ь 31 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.1 поступают а 2 з и Ьз 2. В регистр 10,1 записывается а 13, в регистр 9,1 - а 23. в регистр 15.1 - ЬЗ 2. В ВМ 1.2, В сумматоре 21.2 происходит суммирование а 11 Ь 12+а 12 Ь 22 и результат записывается в блок 22,2 регистров, В умножителе 7.2 происходит умножение д 22 Ь 23 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.2 поступают аз 2 и Ь 21. В регистр 10,2 записывается а 22, в регистр 9.2 - а 32, в регистр 15.2 - Ь 21, В ВМ 1,3. В блок 22,3 регистров записывается а 21 Ь 11. В умножителе 7,3 происходит умножение аз 1 Ь 12 и результат записывается в его выходной регистр. Во входные регистры умножителя 7.3 записываются а 12 и Ь 23, В регистр 10,3 записывается аз 1, в регистр 9,3 - а 12, в регистр 12,3 - Ь 23. Девятый такт, В ВМ 1.1. В сумматоре 21,1 происходит суммирование а 11 Ь 11+а 12 Ь 2+а 13 Ь 31=с 11 и результат через первый вход мультиплексора 23,1 поступает на выход 5 устройства. В умножителе 7.1 происходит умножение а 23 Ь 32 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.1 поступают азз и Ьзз, В регистр 10.1 записывается 5 10 15 20 25 30 35 40 50 55 а 23, в регистр 9.1 - азз, в регистр 15,1 - Ьзз, В ВМ 1.2. В сумматоре 21,2 происходит суммирование а 21 Ь 13+а 22 Ь 23 и результат записывается в блок 22.2 регистров, В умножителе 7,2 происходит умножение аз 2 Ь 21 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7,2 поступают аз 1 и Ь 12 В регистр 10,2 записывается аз 2, в регистр 9,2 - а 1 з, в регистр 12.2 - Ь 32. В ВМ 1,3. В блок 22,3 регистров поступает аз 1 Ь 12. В умножителе 7,3 происходит умножение а 12 Ь 23 и результат записывается в его выходной регистр. Во входные регистры умножителя 7.3 поступают а 22 и Ь 21, В регистр 10,3 поступает а 12. в регистр 9,3 - а 22, а в регистр 15.3 - Ь 21.Десятый такт. В ВМ 1.1. В сумматоре 21.1 происходит суммирование а 21 Ь 12+а 22 Ь 22+а 23 Ьз 2=с 22 и результат выдается на выход 5 устройства. В умножителе 7,1 происходит умножение аззЬзз и произведение записывается в его выходной регистр. В регистр 10.1 записывается азз. В ВМ 1.2. В сумматоре 21,2 происходит суммирование аз 1 Ь 11+аз 2 Ь 21 и результат записывается в блок 22,2 регистров, В умножителе 7.2 происходит умножение а 1 зЬз 2 и произведение записывается в его выходной регистр, Во входные регистры умножителя 7.2 записываются а 23 и Ьзз. В регистр 10.2 записывается а 1 з, в регистр 9.2 - агз, а в регистр 15.2 - Ьзз. В ВМ 1.3, В сумматоре 21.3 происходит суммирование э 11 Ь 13+а 12 Ь 23 и результат записывается в блок 22.3 регистров. В умножителе 7,3 происходит умножение а 22 Ь 21 и результатзаписывается в его выходной регистр. Во входные регистры умножителя 7,3 записываются аз 2 и Ь 22. В регистр 10,3 записывается а 22, в регистр 9.3 - аз 2, а в регистр 15.3 - Ь 22.Одиннадцатый такт. В ВМ 1,1. В сумматоре 21,1 происходит суммирование аЗЬ 13+аз 2 Ь 23+аззЬзз=сзз и результат поступает на выход 5 устройства, В ВМ 1.2, В сумматоре 21.2 происходит суммирование а 1 Ь 12+а 12 Ь 22+а 13 Ь 32=с 12 и результат через мультиплексор 23.2 записывается в блок регистров 4,1. В умножителе 7,2 происходит умножение а 2 зЬЗЗ и произведение записывается в его выходной регистр, Во входные регистры умножителя 7,2 поступают азз и Ьз 1, В регистр 10,2 записывается а 23, в регистр 9.2 - азз, а в регистр 15,2 - Ь 31, В ВМ 1,3, В сумматоре 21,3 происходит суммирование а 21 Ь 11+а 22 Ь 21 и результат записывается в блок 22,3 регистров, В умножителе 7.3 происходит умножение аз 2 Ь 22 и произведение записывается в его выходной регистр. Во входные регистры умножителя 7.3 посту1839262 10 35 и второй информационные выходы 1-го вычислительного модуля (=1, М - 1), подключены соответственно к первому и второму информационным входам (1 + 1)-го вычислительного модуля, первый и второй управляющие входы которого подключены соответственно к первому и второму управляющим выходам 1-го вычислительного модуля, третий информационный выход первого вычислительного модуля является Выходом устройстВа, В каждом Вычислительном модуле первый информационный вход подключен к информационному входу первого регистра и первому входу умножителя, второй вход которого подключен к второму информационному входу вычислительного модуля, информационному входу второго регистра и первому информационному входу первого мультиплексора, Второй информационный вход и управляющий. вход которого подключены соответственно 40 45 50 55 пают а 1 з и Ьзз. В регистр 10,3 записывается аз 2, в регистр 9,3 - а 1 з, а в регистр 12,3 - Ьзз.Двенадцатый такт. В ВМ 1,2. С выхода блока регистров 4.1 через второй вход мультиплексора 23,1 на выход 5 устройства выдается с 12 В сумматоре 21.2 происходит суммирование а 21 Ь 1 з+а 22 Ь 2 з+а 2 збзз=с 2 з и результат записывается в блок регистров 4.1, В умножителе 72 происходит умножение аззЬз 1 и результат записывается в его выходной регистр. В регистр 10.2 записывается а 2 з. В ВМ 1,3, В сумматоре 21.3 происходит суммирование аз 1 Ь 12+аз 2 Ь 22 и сумма записывается в блок 22.3 регистров. В умно- жителе 7,3 происходит умножение а 1 зЬзз и произведение записывается в его выходной регистр, Во входные регистры умножителя 7,3 поступают а 2 з и Ьз 1, В регистр 10.3 записывается а 1 з, в регистр 9,3 - а 2 з, в регистр 15.3 - Ьз 1,Тринадцатый такт, В ВМ 1,2, С выхода блока регистров 4.1 на выход 5 устройства выдается с 2 з В сумматоре 21.2 происходит суммирование аз 1 Ь 11+аз 2 Ь 21+аззЬ 31=сз 1 и результат записывается в блок регистров 4,1. В ВМ 1,3. В сумматоре 21,3 происходит суммирование а 11 Ь 12+а 12 Ь 2 з+а 1 ЗЬзз=с 1 з и результат через мультиплексор 23.3 записывается в блок регистров 4.2, В умножителе 7.3 происходит умножение а 2 зЬз 1 и и роиэведение записывается в его выходной регистр, Во входные регистры умножителя 7.3 записываются азз и Ьз 2, В регистр 10,3 записывается а 2 з, в регистр 9.3 - азз, в регистр 15,3 - Ьз 2. Формула изобретения УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ МАТРИЦ, содержащее М вычислительных модулей (Й - размерность перемножаемых матриц), 1 ч - 1 блоков регистров и блок синхронизации, каждый вычислительный модуль содержит четыре регистра, два мультиплексора, четыре триггерв, блок регистров, умножитель и сумматор, причем первый и второй информационные входы первого вычислительного модуля являются соответственно первым и вторым информационными входами устройства, входы синхронизации ввода и вывода элементов матриц которого подключены соответственно к одноименным входам блока синхронизации, первый и второй выходы которого подключены соответственно к первому и второму управляющим входам первого вычислительного модуля, первый 10 15 20 25 30 Четырнадцатый такт, С выхода блока регистров 4.1 на выход 5 устройства выдается сз 1. С выхода блока регистров 4.2 в блок регистров 4,1 переписывается с 1 з, В сумматоре 21.3 происходит суммирование а 21 Ь 11+а 22 Ь 21+а 2 ЗЬЗ 1=с 21 и результат записывается в блок регистров 4,2, В умножителе 7,3 происходит умножение аззЬз 2 и результат записывается в его выходной регистр. В регистр 10.3 записывается азз,Пятнадцатый такт. С выхода блока буферных регистров 4.1 на выход 5 устройства выдается с 1 з, а в блок регистров 4.1 с выхода блока регистров 4.2 переписывается с 21, В сумматоре 21.3 происходит суммирование аз 1 Ь 12+аз 2 Ь 22+аззЬз 2=сз 2 и результат записывается в блок регистров 4.2.Шестнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается с 21, а в блок регистров 4,1 записывается сз 2Семнадцатый такт. С выхода блока регистров 4.1 на выход 5 устройства выдается последний результат матрицы сз 2.Таким образом, предложенное устройство вь 1 годно отличается от прототипа, так как содержит на 2 1 ч - 2 ВМ меньше, чем прототип, Кроме того, время вычисления произведения матриц в прототипе составляет Зх хй -1, а в заявляемом устройстве - 2 М,2 2(56) Джахадиш Х.В, и др. Матричные структуры для реализации итерационных алгоритмов, ТИИЭР, т, 75, 1987, рис, 6,Авторское свидетельство СССР К 1705836, кл. 6 06 Е 15/347, 1989.к выходу второго регистра и первому управляющему входу вычислительного модуля, объединенному с управляющим входом второго регистра и с информационным входом первого триггера, выход которого подключен к информационному входу второго триггера, выход которого является первым управляющим выходом вычислительного модуля, отличающееся тем, что. с целью сокращения аппэратурных затрат, третий информационный вход 1-го вычислительного модуля подключен к третьему информационному выходу (1 + 1)-го вычислительного модуля через 1-ый блок регистров, в каждом вычислительном модуле первый и второй информационные выходы подключены соответственно к выходам третьего и четвертого регистров, информационные входы которых подключены соответственно к выходам первых регистра и мультиплексора, выход умножителя подключен к первому входу сумматора, второй вход и выход которого подключены соответственно к выходу и информационному 5 входу блока регистров, информационныйвход которого подключен к первому информационному входу второго мультиплексора, второй информационный вход которого является третьим информацион ным входом вычислительного модуля, третий информационный выход которого подключен к выходу второго мультиплексора, управляющий вход которого подключен к выходу четвертого триггера и второму управляющему выходу вычислительного модуля, второй управляющий вход которого подключен к информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера,1839262 1 с 1 Г 3 4 Х Е 7 В У Ю и Уг 13 Я аг Составитель В, ЧервяцовТехред М, Моргентал Корректор П. Герещи Редактор Т. Юрчикова Тираж Подписное НПО "Поиск" Роспатента113035, Москва, Ж, Раувская наб., 4/5 Закаэ 3407 Производственно-издательский комбинат "Патент", г, ужгород, ул,Гагарина, 101