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

(51) 5 (3 ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(71) Киевский политехнический институт им,50-летия Великой Октябрьской социалистической революции(72) Р.Выжиковский, Ю.С.Каневский, М,К.Клименко и С,Г,Овраменко (73) Киевский политехнический институт (56) Авторское свидетельство СССР М 1363247, кл. О 06 В 15/347, 1986.Авторское свидетельство СССР М 1552200, кл. 6 06 Р 15/347, 1988. 4) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТ- ИЦ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе систолических устройств, предназначенных для выполнения операций над матрицами, Целью изобретения является повышение быстродействия, Новым вустройстве для умножения матриц, содержащем пхп вычислительных модулей 1 первого типа и блок 3 управления, является введение пхп вычислительных модулей 2 второго типа, что дает возможность организовать непрерывную обработку потока трех матриц, а это, в свою о 4 Ьредь, обеспечивает повышение производительности устройства в 2 раза. 2 з,п, ф-лы, 4 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами.Целью изобретения является повышение быстродействия устройства,На фиг, 1,представлена структурная схема устройства для умножения матриц; на фиг, 2 - структурная схема вычислительного модуля первого тра на фиг. 3 - структурная схема вычислительного модуля второго типа; на фиг. 4 - структурная схема блока управления, вариант реализации.Устройство для умножения матриц (фиг, 1) содержит пхп вычислительных модулей 1 первого типа, пхп вычислительных модулей 2 второго типа и блок 3 управления.Вычислительный модуль первого типа (фиг, 2) содержит регистры 4, 5, умножитель 6, сумматор 7, регистр 8 и триггер 9.Вычислительный модуль второго типа (фиг. 3) содержит регистр 10, умножитель 11, регистр 12, сумматор 13 и регистр 14,Блок 3 управления (фиг, 4) содержит элемент ИЛИ 15, счетчик 16, дешифратор 17, регистр 18,Устройство предназначено для умножения матриц АхВхС = Р, где А, В и С - матрицы размерности Кхй, и может быть реализовано при следующих формулах;бц =-айЬц:пб;= ,с; б;,где а к, Ь и С 1 - элементы матриц А, В и С;б; - элементы промежуточной матрицы; Ь - элемент конечной матрицы Е.Кратко рассмотрим работу устройства, Для простоты описания и без потери общности положим М = 3. Условимся, что прием информации во все регистры осуществляется по переднему фронту синхроимпульса, то есть в начале такта. Считаем, что перед началом вычислений все регистры установлены в нулевое состояние. Имйульс пуска поступает на первый вход блока управления 3 (вход запуска) через элемент ИЛИ 15 поступает на второй вход счетчика 16 (вход разрешения записи в счетчик 16), Счетчик 16 работает в режиме вычитания. Дешифратор 17 дешифрирует состояние нуля. На первые входы вычислительных модулей 1 первого типа первого столбца поступают элементы, а матрицы А по строкам. На вторые входы - элементы матрицы В по столбцам. Элементы С 1 матрицы С поступают на первые входы вычислительных модулей 2 второго типа 5 первого столбца по строкам,а 11 а 12 а 1 з Ь 11 Ь 12 Ь 13б 11 б 12 б 13 а 21 а 22 а 23Ь 21 Ь 22 Ь 23 = б 21 б 22 б 23 10 аз 1 азгазз Ь 31 ЬзгЬЗЗ, бз 1 бзгбзз б 11 б 12 б 13 С 11 С 12 С 13 т 11 т 12 т 13 б 21 б 22 б 23С 21 С 22 С 23 = т 21 тггт 23 б 31 б 32 бзЗ с 31 С 32 СЗЗ 31 т 32 т 33 15Результирующая матрица получена следующим образом; т 11 = б 11 с 11+ б 13 с 13+ б 12 с 12: т 12 = б 22 с 12+ б 21 с 11+ б 23 с 13: т 13 = бЗЗс 13+ б 32 с 22+ б 31 с 11; т 21 = б 11 с 21 + б 13 с 13 + б 12 с 22; тгг = б 22 с 22 + б 21 с 21 + б 23 с 23; т 23 = бЗЗС 23+ б 32 С 22 + б 31 С 21 т 31 = б 11 с 31+ б 13 с 33+ б 12 с 32 т 32 = б 22 с 32 + б 21 с 31 + б 23 с 33; тзз = бЗЗсзЗ + б 32 С 32 + б 31 с 31. 20 25 Нулевой такт, На первый и второй входы 30 вычислительного модуля 1.1,1 соответственно поступают элементы а 11 и Ь 11 и записываются соответственно в регистры 4,1,1 и 5,1.1, На первый и второй входы вычислительного модуля 1.2.1 соответственно поступают а 21 и Ь 12 и записываются соответственно в регистры 4,2,1 и 5,2.1. На первый и второй входы вычислительного модуля 1,3,1 соответственно поступают аз 1 и Ь 13 и записываются соответственно в реги стры 4.3.1 и 5.3.1,В первом такте с вь 1 ходов регистров4.1.1 и 5,1.1 элементы а 11 и Ь 11 поступают на первый и второй выходы вычислительного модуля 1.1,1 и на первый и второй входы 45 умножителя 6,1,1, с выхода которого произведение а 11 Ь 11 поступает в сумматор 7,1,1, где складывается с нулем а 11 Ь 11+О и записывается в регистр 8.1.1. На входы вычислительного модуля 1,1.1 поступают следующие элементы а 12 и Ь 21 и записываются в регистры 4.1.1 и 5.1,1. На входы вычислительного модуля 1,1.2 поступают элементы а 11 и Ь 13 и записываются в регистры 4,1,2 и 5.1,2. На первый вход сумматора 7,2,1 вычислительного модуля 1.2.1 поступает произведение а 21 Ь 12, где складывается с нулем и а 21 Ь 12+О записывается в регистр 8.2.1, В регистры 4,2.1 и 5.2.1 соответственно записываются а 22 и Ь 22. В регистры 4,2,2и 5,2.2 вычислительного модуля 1,2.2 соответственно записываются элементы а 21 и Ь 11, На первый вход сумматора 7.3.1 вычислительного модуля 1.3.1 поступает произведение аз 1 Ь 1 з и складывается с нулем, результат аз 1 Ь 1 з+О записывается в регистр 8,3.1. В регистры 4,3.2 и 5.3,2 вычислительного модуля 1.3,2 соответственно записываются элементы аз 1 и Ь 12.Во втором такте с выхода регистра 8,1,1 вычислительного модуля 1,1,1 на второй 510 вход сумматора 7,1,1 поступает произведение а 11 Ь 11, на первый вход которого с выхода умножителя 6,1.1 поступает а 12 Ь 21 и результат а 11 Ь 11+а 21 Ь 21 снова записывается в регистр 8,1,1, В регистры 4.1.1 и 5,1,1 соответственно записываются элементы а 1 з и Ьз 1. На выходе сумматора 7.1,2 вычислительного модуля 1.1.2 будет сумма а 11 Ь 1 з+О, которая записывается в регистр 8.1.2. В регистры 4,1,2 и 5,1,2 записываются а 12 и Ь 2 з. В регистры 4.1,3 и 5;1,3 вычислительного модуля 1,1,3 записываются а 11 и Ь 12. На входы сумматора 7.2.1 вычислительного модуля 1,2.1 поступают произведения а 21 Ь 12 и а 22 Ь 22 и с его выхода сумма а 21 Ь 12+а 22 Ь 22 записываются в регистр 8,2.1, В регистры 4,2,1 и 5.2.1 записываются а 2 З и Ьз 2, На выходе сумматора 7,2.2 вычислительного 20 25 30 35 40 45 1.1,1 на третий выход поступает 50 а 11 Ь 11+а 12 Ь 21+а 1 зЬз 1 = б 11 и б 11 записы вается в регистр 10 вычислительного модуля 2,1.1, На входы регистров 4.1,1 и 5.1,1 поступают элементы а 11 и Ь 11 новых матриц А и В. В 55 регистр 12,2,1 с первого входа вычислительного модуля 2,1.1 записывается элемент с 11 матрицы С, С выхода сумматора 7.1.2 вычислительного модуля 1,1.2 в регистр 8,1,2 записывается а 11 Ь 1 з+а 12 Ь 2 з. В регистры 4.1,2 и 5.1.2 соответственно записываются а 1 з и модуля 1,2,2 появляется сумма а 21 Ь 11+О и записывается в регистр 8.2.2, В регистры 4.2,2 и 5.2.2 записываются а 22 и Ь 21, В регистры 4.2.3 и 5.2.3 вычислительного модуля 1.2.3 записываются а 21 и ь 1 з, на входы сумматора 7 вычислительного модуля 1.3.1 поступают произведения аз 1 Ь 1 з и аз 2 Ь 2 з и результат аз 1 Ь 1 з+аз 2 Ь 2 з записывается в регистр 8,3,1. В регистры 4.3.1 и 5.3,1 записываются азз и Ьзз. С выхода сумматора 7.3,2 вычислительного модуля 1.3.2 аз 1 ь 12+О записывается в регистр 8.3.2. В регистры 4,3,2 и 5,3,2 записываются аз 2 и Ь 22, В регистры 4.3.3 и 5.3.3 вычислительного модуля 1.3.3 записываются аз 1 и Ь 11,В третьем такте в сумматорах 7.1.1 - 7,7. п вы числ ител ьн ых модулей 1.1,1 - 1,1, п получаем первые элементы бц промежуточной матрицы О, Таким образом, с выхода сумматора 7.1.1 вычислительного модуля Ьзз, С выхода сумматора 7.1.3 вычислительного модуля 1,1.3 в регистр 8,1,3 записывается а 11 Ь 12+О. В регистры 4.1.3 и 5,1,3 записываются а 12 и Ь 22. В сумматоре 7.2,1 вычислительного модуля 1.2,1 получаем д 21 Ь 12+д 22 Ь 22+а 23 Ьз 2 = б 22 и элемент б 22 записывается в регистр 10.2,1 вычислительного модуля 2,2,1, На входы регистров 4,2,1 и 5.2,1 поступают элементы новых матриц, В регистр 12,2.1 записывается с 12, С выхода сумматора 7.2.2 вычислительного модуля 1.2,2 в регистр 8.2.2 записывается сумма а 21 Ь 11+а 22 Ь 21, В регистры 4,2,2 и 5,2,2 записываются элементы а 2 з и Ьз 1, С выхода сумматора 7,2.3 вычислительного модуля 1.2.3 в регистр 8,2,3 записывается а 21 Ь 1 з+О, В регистры 4.2,3 и 5,2,3 записываются а 22 и Ь 2 з В сумматоре 7,3,1 вычислительного модуля 1,3.1 получаем аз 1 Ь 1 з+аз 2 Ь 2 з+аззЬзз = бзз и элемент бзз записывается в регистр 10.3.1 вычислительного модуля 2,3.1, В регистры 4.3,1 и 5,3.1 записываются элементы новых матриц. В регистр 12,3,1 записывается с 1 з. С выхода сумматора 7.3,2 вычислительного модуля 1,3.2 в регистр 8.3,2 записывается аз 1 Ь 12+аз 2 Ь 22. В регистры 4,3,2 и 5.3.2 записываются азз и Ьз 2. С выхода сумматора 7,3.3 вычислительного модуля 1,3.3 в регистр 8.3.3 записывается аз 1 Ь 11+О. В регистры 4,3,3 и 5,3.3 записываются аз 2 и Ь 21,В четвертом такте в сумматоре 7.1,2 вычислительного модуля 1,1.2 получаем сумму а 11 Ь 1 з+а 12 Ь 2 з+а 1 зЬзз = б 1 з и элемент б 13 записывается в регистр 10,1,2 вычислительного модуля 2.1,1. В регистр 12,1,2 записывается с 1 з. С восхода сумматора 7.1,3 вычислительного модуля 1.1,3 поступает а 11 Ь 12+а 11 Ь 22 и записывается в регистр 8,1,3. В регистры 4,1,3 и 5,1,3 записываются а 1 з и Ь 2 з. На входы умножителя 11.1.1 вычислительного модуля 2,1.1 поступают элементы б 11 и с 11, где происходит умножение б 11 с 1; и произведение поступает в сумматор 13.1,1, где складывается с нулем и записывается в регистр 14.1,1, В регистр 12.1.1 записывается элемент с 22, а элемент с 11 передается в вычислительный модуль 2.2,2 и записывается в регистр 12,2,2, В сумматоре 7,2,2 вычислительного модуля 1,2,2 получаем а 21 Ь 11+а 22 Ь 21+а 2 зЬз 1 = б 21 и элемент б 21 записывается в регистр 10.2,2, С выхода сумматора 7,2.3 вычислительного модуля 1,2,3 получаем а 21 Ь 1 з+а 22 Ь 2 з и эта сумма записывается в регистр 8,2,3, В регистры 4,2,3 и 5.2,3, Записываются а 2 з и Ьзз, В сумматоре 13,2.1 вычислительного модуля 2.2.1 получаем сумму б 22 с 21+О, которая записывается в регистр 14.2,1. В регистр 2.2,1 записывается с 22, В сумматоре 7.3.2 вы 179078551015 55 т 31, тзг и тзз числительного модуля 1,3,2 получается аз 1 Ь 12+аз 2 Ь 22+аззЬз 2 = бзг и записывается в регистр 10,3,2 вычислительного модуля 2,3,2, В регистр 12.3,2 записывается с 12. С выхода сумматора 7,3,3 вычислительного модуля 1.3,3 поступает азтЬ 11+аз 2 Ь 21 записывается в регистр 8,3.3, В регистры 4,3,3 и 5,3.3 записываются азз и Ьз 1, С выхода сумматора 13.3.1 вычислительного модуля 2.3,1 поступает бззс 1 з+О записывается в регистр 14,3.1. В регистр 12,3,1 записывается с 2 з.В пятом такте в сумматоре 7.1.3 вычислител ьного модуля 1.1,3 получаем а 11 Ь 12+а 12 Ь 22+а 13 Ь 32 = б 12 и элемент б 12 записывается в регистр 10,1,3 вычислительного модуля 2,1.3, В регистр 12,1,3 записывается с 12. С выхода сумматора 13,1.2 вычислительного модуля 2,1.2 поступает б 11 с 1 б 13 с 1 з и записывается в регистр 14,1.2 вычислительного модуля 2.1.2, В регистр 12.1.2 записывается элемент с 2 з. С выхода сумматора 13.1.1 вычислительногоо модуля 2,1.1 выдается б 11 с 21+О и записывается в регистр 14,1,1, В регистр 12.1.1 записывается сз 1, В сумматоре 7.2.3 получаем а 21 Ь 1 з+а 22 Ь 2 з+а 22 Ьзз = б 2 з и элемент б 2 з записывается в регистр 10,2.3 вычислительного модуля 2,2.3. В регистр 12,2.3 записывается с 1 з, С выхода сумматора 13.2,2 вычислительного модуля 2,2,2 выдается б 22 с 12+б 21 с 11 и записывается в регистр 14,2,2, В регистр 12,2,2 записывается сз 2 В сумматоре 7.3.3 вычислительного модуля 1,3.3 получаем аз 1 Ь 11+азгЬ 21+аззЬз 1 = бз 1 и элемент бз 1 записывается в регистр 10,3,3 вычислительного модуля 2.3.3, В регистр 12.3,3 вычислительного модуля 2,3.3 записывается с 11. С выхода сумматора 13.2.2 вычислительного модуля 2,3,2 поступает бззс 1 з+бз 2 с 12 и записывается в регистр 14,2,3, В регистр 12,3.2 записывается сгг С выхода сумматора 13.3.1 вычислительного модуля 2,3,1 поступает бззс 2 з+О и записывается в регистр 14.3.1. В регистр 12,3,1 записывается - сзз. В шестом такте в сумматоре 13.1.3 вычислительного модуля 2.1,3 получаем первый окончательный результат б 11 с 11+б 1 зс 13+бтгстг = 011, который записывается в регистр 14,1,3, В регистр 12,1.3 записывается - с 22. С выхода сумматора 13,1,2 вычислительного модуля 2.1.2 поступает бттс 21+бтзсгз и записывается в регистр 14,1,2, В регистр 12.1,2 записывается - сзз. С выхода сумматора 13.1.1 вычислительного модуля 2.1,1 поступает б 11 сз 1+О и записывается в регистр 14,1,1, В сумматоре 13,2,3 вычислительного модуля 2,2,3 получаем б 22 с 12+б 21 С 11+б 23 с 13 = т 12 и результат т 12 за 20 25 30 35 40 45 50 писывается в регистр 14.2,3, В регистр 14,2,3 записывается - сгз. С выхода сумматора 13.2,2 вычислительного модуля 2.2.2 поступает б 2 гсгг+б 21 с 21 и записывается в регистр 14.2.2, В регистр 12,2.2 записывается сз 1. С выхода сумматора 13,2.1 вычислительного модуля 2.2.1 поступает бггсзг+О и записывается в регистр в регистр 14.2,1, В сумматоре 13,3,3 вычислительного модуля 2.3.3 получаем бззб 1 з+бзгс 12+бз 1 с 11 = ттз и результат записывается в регистр 14.3.3. В регистр 12,3,3 записывается с 21, С выхода сумматора 13,3.2 вычислительного модуля 2.3,2 поступает бззсгз+бзгсг 2 и записывается в регистр 14,3.2, В регистр 12,3,2 записывается сз 2. С выхода сумматора 13,3,1 вычислительного модуля 2,3,1 поступает бззсзз+О и записывается в регистр 14.3.1,В седьмом такте в сумматоре 13.1.3 вычислительного модуля 2.1.3 получаем б 11 сг 1+бтзсгз+бтгсгг = 121 и результат записывается в регистр 14,1.3, а с его выхода на выход устройства выдается т 11, В регистр 12.1,3 записывается сз 2. С выхода сумматора 13,1,2 вычислительного модуля 2.1,2 поступает б 11 сз 1+бтзсзз и записывается в регистр 14,1.2, В сумматоре 14,2,3 вычислительного модуля 2,2,3 получаем б 22 с 22+бгтсгт+бгзс 2 з = тгг и результат записывается в регистр 14.2,3, с выхода которого на выход устройства выдается1 г. В регистр 12,2.3 записывается сзз, С выхода сумматора 13.2.2 вычислительного модуля 2,2,2 поступает бггсзг+бгтсзт и записывается в регистр 14,2,2, В сумматоре 13.3,3 вычислительного модуля 2.3,3 получаем бззсгз+бзгсгг+бзтс 21 = 123 и результат записывается в регистр 14.3.3, с выхода которого выдается 113. В регистр 12,3,3 записывается сзт. С выхода сумматора 13,3.2 вычислительного модуля 2,3.2 поступает бззсзз+бзгсз 2 и записывается в регистр 14,3.2.В восьмом такте в сумматоре 13.1.3 вычислительного модуля 2.1.3 получаем б 11 сз 1+б 1 зсзз+бтгсзг = тз 1 и результат записывается в регистр 14,1,3, с выхода которого выдается 121, В сумматоре 13,2,3 вычислительного модуля 2,2.3 получаем б 22 сзг+бгтсз 1+бгзсзз = тзг и результат записывается в регистр 14,2,3, с выхода которого выдается 122, В сумматоре 13,3,3 вычислительного модуля 2.3.3 получаем бззсзз+бг 1 сзг+б 31 сз 1 = тзз и результат записывается в регистр 14.3.3, с выхода которого выдается зз В девятом такте с выхода вычислительных модулей 2.1,3, 2,2,3 и 2.3.3 соответственно выдаются окончательные результаты-55 На этом работа устройства по вычислению матрицы Р = АхВхС заканчивается.Формула изобретения 1. Устройство для умножения матриц, содержащее пхп вычислительных модулей первого типа и блок управления (где и - размерность матриц), причем первый информационный выход (Ц)-го вычислительного модуля первого типа ( = 1, , и; ) = 1, и) соединен с первым информационным входом (Ц+1)-го вычислительного модуля первого типа, входы запуска, сброса, записи и счетный вход устройства соединены с соответствующими входами блока управления, выход которого соединен с входом разрешения записи (1,1)-го вычислительного модуля первого типа, первый и второй информационные входы которого соединены соответственно с первым и вторым информационными входами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены пхп вычислительных модулей второго типа, причем первый информационный вход (1,1)-го вычислительного модуля второго типа соединен с третьим информационным входом устройства, вход логического нуля которого соединен с вторым информационным входом (,1)-го вычислительного модуля второго типа, второй информационный выход (Ц)-го вычислительного модуля первого типа (1=1, , и) соединен с вторым информационным входом (1+1, )+1)-го вычислительного модуля первого типа, второй информационный выход (п,-го вычислительного модуля первого типа соединен с вторым информационным входом (1, )+1)-го вычислительного модуля первого типа, третий информационный выход (,1)-го вычислительного модуля первого типа (1=1, .и) соединен с третьим информационным входом (Ц)-го вычислительного модуля второго типа, первый информационный выход (КД- го вычислительного модуля второго типа соединен с первым информационным входом (1+1, )+1)-го вычислительного модуля второго типа, первый информационный выход (п,-го вычислительного модуля второго типа соединен с первым информационным входом (1, /+1)-го вычислительного модуля второго типа, второй информационный выход (,Д-го вычислительного модуля второго типа соединен с вторым информационным 5 10 15 20 25 30 35 40 45 50 входом (1, 1+1)-го вычислительного модуля второго типа, вторые выходы (1, и)-ных вычислительных модулей второго типа соединен с выходами устройства, выход разрешения записи (1,)-го вычислительного модуля первого типа соединен с входами разрешения записи (, 1+1)-го вычислительного модуля первого типа и (, 1)-го вычислительного модуля второго типа.2, Устройство по и, 1, о т л и ч а ю щ е ес я тем что каждый вычислительный модуль первого типа содержит три регистра, умно- житель, сумматор и триггер, выход которого соединен с выходом разрешения записи модуля, первый информационный вход которого соединен с информационным входом первого регистра, выход которого соединен с первым информационным выходом модуля и первым входом умножителя, второй вход которого соединен с вторым информационным выходом модуля и выходом второго регистра, информационный вход которого соединен с вторым информационным входом модуля, вход разрешения записи которого соединен с входом триггера, выход умножителя соединен с входом триггера, выход умножителя соединен с входом первого слагаемого сумматора, выход которого соединен с третьим информационным выходом модуля информационным входом регистра, выход которого соединен с входом второго слагаемого сумматора,3, Устройство по и, 1, о т л и ч а ю щ е ес я тем, что каждый вычислительный модуль второго типа содержит три регистра, умно- житель и сумматор, выход которого соединен с информационным входом первого регистра, выход которого соединен с вторым информационным выходом модуля, второй информационный вход которого соединен с входом первого слагаемого сумматора, вход второго слагаемого которого соединен с выходом умножителя, первый вход которого соединен с выходом второго регистра, информационный вход и вход разрешения записи которого соединен соответственно с третьим информационным входом и входом разрешения записи модуля, первый информационный вход которого соединен с вторым входом умножителя и выходом третьего регистра, информационный вход которого соединен с первым информационным входом модуля.1790785евае а а едактор Заказ 375 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 изводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина Р1 Составитель Ю.КаТехред М.Моргент ский Корректор З.Сал