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

(5 ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОбРЕТЕНК ПАТЕНТУ 0(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(72) Р,Выжиковский, Ю.С,Каневский, М.К.Клименко и С,Г.Овраменко (73) Киевский политехнический институт (56) Авторское свидетельство СССР М 1363247, кл, 6 06 Р 15/347, 1986.Авторское свидетельство СССР М 1552200, кл, 0 06 Е 15/347, 1988,(54) УСТРОЙСТВО Дл: УМНОЖЕНИЯ МАТ РИЦ(57) Устройство для умножения матриц относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами. Целью изобретения является повышение быстродействия, Новым в устройстве для умножения матриц, содержащем пхп вычислительных модулей первого 1 типа и блок 3 управления, является введение вычислительных модулей 2 второго типа и два коммутатора 4, 5, которое позволяет организовать непрерывную обработку трех матриц. за счет чего быстродействие повышается в 2 раза 2 3 и ф-лы, 4 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами.Целью изобретения является повышение быстродействия устройства,На фиг, 1 представлена структурная схема устройства для умножения матриц; на фиг, 2 - структурная схема вычислительного модуля первого типа; на фиг. 3 - структурная схема вычислительного модуля второго типа; на фиг. 4 - структурная схема блока управления, вариант,Усройство для умножения матриц (фиг. 1) содержит пхп вычислительных модулей 1 первого типа, пхп вычислительных модулей 2 второго типа, блок 3 управления, коммутаторы первой 4 и второй 5 групп.Вычислительный модуль первого типа (фиг. 2) содержит первый регистры 6, 7, умножитель 8, сумматор 9, регистр 10, триггер 11.Вычислительный модуль второго типа (фиг, 3) содержит первый регистр 12, сумматор 13, умножитель 14, регистры 15, 16.Блок 3 управления (фиг,4) содержит элемент ИЛИ 17, счетчик 1,8, дешифратор 19, элемент НЕ 20, регистры 21.Устройство предназначено для умножения матриц АхВхС = Г, где А, В и С - матрицы размерности Мхй, и может быть реализовано на следующих формулах;б = дкЬц,ОФ;с;где аа, Ьц, с; - элементы матриц А, В и С;б 1 - элементы промежуточной матрицы;1 ь - элементы конечной матрицы Г, Рассмотрим работу устройства, Для простоты описания и без потери общности положим М = 3, Условимся, что прием информации во все регистры осуществляется по переднему фронту синхроимпульса, то есть в начале такте. Считаем, что перед началом вычислений все регистры установлены в нулевое состояние. Импульс пуска поступает на первый вход блока управления 3 (вход запуска), через элемент ИЛИ 17 поступает на второй вход счетчика 18 (вход разрешения записи в счетчик 18), Счетчик 18 работает в режиме вычитания, Дешифратор19 дешифрирует состояние нуля. На первые входы вычислительных модулей первого типа первого столбца поступают элементы аа матрицы А по строкам, на вторые входы - 5 элементы Ьк 1 матрицы В по столбцам, Элементы С 18 матрицы С поступают на первые входы вычислительных модулей 2,1,1 - 2.п,1 по строкам 10 Ь 11 Ь 12 Ь 13 Ь 21 Ь 22 Ь 23 Ь 31 Ь 32 ЬЗЗ б 11 б 12 б 13 б 21 б 22 б 23 б 31 б 32 бзз а 11 а 1 га 1 з аг 1 аггагз аз 1 азгазз т 11 т 12 т 13 т 21 тггтгз 1 здзг 133 б 11 б 1 гб 1 з б 21 б 22 б 23 б 31 б 32 бзз с 11 с 1 гс 1 з С 21 С 22 С 23 С 31 С 32 СЗЗ Результирующая матрица получена сле 20 дующим образом: т 11 = б 11 С 11 + б 21 С 21 + б 31 СЗ 1 т 21 = б 22 с 21+ б 32 с 31+ б 12 с 11: т 31 = бззс 31+ б 13 с 11+ б 23 с 21, т 12 = б 11 С 12+ б 21 С 22+ б 31 С 32, тгг = б 22 С 22 + б 32 с 32 + б 12 с 12, тзг = бЗЗС 32 + б 13 С 12 + б 23 С 22; т 13 = б 11 с 13+ б 21 с 23+ б 31 сзз: тгз = б 22 С 23 + б 32 СЗЗ + б 12 С 13 тзз = бЗЗСЗЗ + б 13 С 13 + б 23 С 23,25 30 Нулевой такт. На первый и второй входывычислительного модуля 1,1.1 соответственно поступают элементы Ь 11 и а 11 и записываются соответственно в регистры 6,1.1 и 7,1,1, На первый и второй входы вычислительного модуля 1.2.1 соответственно поступают Ь 12 и а 21 и записываются соответственно в регистры 6,2,1 и 7.2.1. На первый и второй входы вычислительного модуля 1,3,1 соответственно поступают Ь 1 з и аз 1 и записываются соответственно в регистры 6,3,1 и 7,3,1,В первом такте с выходов регистров 45 6.1.1 и 7,1.1 элементы Ь 11 и а 11 поступают напервый и второй выходы вычислительного модуля 1.1.1 и на первый и второй входы умножителя 8,1.1, с выхода которого произведение Ь 11 а 11 поступает в сумматор 9.1.1, где складывается с нулем и записывается в регистр 10.1,1. На входы вычислительного модуля 1,1,1 поступают следующие элементы Ь 21 и а 12 и записываются в регистры 6,1,1 и 7.1,1. На входы вычислительного модуля 1.1.2 поступают элементы Ь 12 и а 21 и записываются в регистры 6.1.2 и 7.1,2. На первый вход сумматора 9,2,1 вычислительного модуля 1.2,1 поступает произведение аг 1 Ь 12, где складывается с нулем и записывается врегистр 10.2.1. В регистры 6,2.1 и 7,2,1 соответственно записываются Ь 22 и агг, В регистры 6,2.2 и 7,2.2 вычислительного модуля 1.2.2 соответственно записываются элементы Ь 1 з и а 11. На первый вход сумматора 9,3.1 вычислительного модуля 1,3.1 поступает произведение аз 1 Ь 1 з и складывается с нулем, результат записывается в регистр 10,3.1. В регистры 6.3,2 и 7.3,2 вычислительного модуля 1,3,2 соответственно записываются элементы Ь 12 и аз 1.Во втором такте с выхода регистра 10,1,1 вычислительного модуля 1.1.1 на второй вход сумматора 9.1,1 поступает произведение а 11 Ь 11, на первый вход которого с выхода умножителя 8,1,1 поступает а 12 Ь 21 и результат а 11 Ь 11+а 12 Ь 21 снова записывается в регистр 10.1,1. В регистры 6,1.1 и 7.1.1 соответственно записываются элементы Ьз 1 и а 1 з, На выходе сумматора 9.1,2 вычислительного модуля 1.1,2 будет сумма а 21 Ь 11+О, которая записывается в регистр 1 Р.1,2, В регистры 6.1.2 и 7,1,2 записываются Ь 21 и а 22. В регистры 6,1.3 и 7,1,3 вычислительного модуля 1.1.3 записываются Ь 1 з и аг 1, На входы сумматора 9.2.1 вычислительного модуля 1.2,1 поступают произведения а 21 Ь 12 и а 22 Ь 2 г и с его выхода сумма а 21 Ь;2+аггЬгг записывается в регистр 10.2.1. В регистры 6,2,1 и 7.2,1 записываются агз и Ьзг На выходе сумматора 9.2,2 вычислительного модуля 1,2,2 появляется сумма а 11 Ь 1 з+О и записывается в регистр 10.2,2. В регистры 7,2,2 и 6.2.2 записываются а 12 и Ьгз В регистры 7.2,3 и 6.2.3 вычислительного модуля 1.2,3 записываются аз 1 и Ь 11. На входы сумматора 9.3.1 вычислительного модуля 1,3,1 поступают произведения аз 1 Ь 1 з и азгЬгз и результат аз 1 Ь 1 з+азгЬгз записывается в регистр 10,3.1. В регистры 7.3.1 и 6.3,1 записываются азз и Ьзз. С выхода сумматора 9.3,2 аз 1 Ь 12+0 вычислительного модуля 1.3,2 записывается в регистр 10,3,2, В регистры 7.3,2 и 6,3.2 записываются аз 2 и Ь 22. В регистры 7,3,3 и 6,3,3 вычислительного модуля 1,3,3 записываются элементы а 11 и Ь 1 г соответственно.В третьем такте в сумматорах 9,1,1 - 9.1.п вычислительных модулей 1.1.1 - 1,1,п получаем первые элементы Ф промежуточной матрицы О. Таким образом, с выхода сумматора 9,1.1 вычислительного модуля 1.1,1 на третий выход поступает а 11 Ь 11+а 12 Ь 21+а 1 зЬз 1 = б 11 и записывается в регистр 12,1,1 вычислительного модуля 12.1,1. На входы регистров 7,1,1 и 6.1.1 поступают элементы а 11 и Ь 11 новых матриц1А и В, В регистр 15,1,1 со второго входа вычислительного модуля 2.1.1 записывается элемент с 1 матрицы С, С выхода сумматора 9,1.2 вычислительного модуля 1,1,2 в 5 10 15 20 25 30 35 40 45 50 55 регистр 10.1,2 записывается а 21 Ь 11+а 22 Ь 21. В регистры 7.1,2 и 6,1,2 соответственно записываются агз и Ьз 1, С выхода сумматора 9,1.3 вычислительного модуля 1,1,3 в регистр 10,1,3, записывается аг 1 Ь 1 з+О, В регистры 7,1,3 и 6.1.3 записываются а 22 и Ьгз В сумматоре 9.2,1 вычислительного модуля 1.2,1 получаем а 21 Ь 12+а 22 Ь 22+а 2 зЬзг = б 22 и элемент бгг записывается в регистр 12,2,1 вычислительного модуля 2,2.1. На входы регистров 7.2.1 и 6.2,1 поступают элементы новых матриц. В регистр 15.2.1 записывается - сг 1, С выхода сумматора 9.2.2 вычислительного модуля 1,2,2 в регистр 10.2,2 записывается сумма а 11 Ь 1 з+а 12 Ь 2 з, В регистры 7.2.2 и 6,2.2 записываются элементы абаз и Ьзз. С выхода сумматора 9,2.3 вычислительного модуля 1,2.3 в регистр 10.2.3 записывается аз 1 Ь 11+О. В регистры 7,2.3 и 6,2.3 записываются азг и Ь 21. В сумматоре 9.3.1 вычислительного модуля 1.3.1 получаем аз 1 Ь 1 з+азгЬ 2 з+аззЬзз = бзз и элемент бзз записывается в регистр 12.3.1 вычислительного модуля 2.3.1. В регистры 7.3.1 и 6.3.1 записываются элементы новыхматриц. В регистр 15,3,1 записывается сз 1. С выхода сумматора 9,3.1 вычислительного модуля 1,3,2 в регистр 10.3,2 записывается аз 1 Ь 12+азгЬ 22, В регистры 7,3.2 и 6.3.2 записываются азз и Ьзг. С выхода сумматора 9.3.3 вычислительного модуля 1.3,3 в регистр 10,3,3 записывается а 11 Ь 12+О. В регистры 7.3,3, и 6.3,3 записываются а 12 и Ь 22.В четвертом такте в сумматоре 9,1,2 вычислительного модуля 1,1.2 получаем сумму а 21 Ь 11+а 22 Ь 21+агзЬз 1 = бг 1 и элемент б 21 записывается в регистр 12.1.2 вычислительного модуля 2,1,2, В регистр 15.1.2 записывается с 21. С выхода сумматора 9.1,3 вычислительного модуля 1.1.3 поступает аг 1 Ь 1 з+аггЬ 2 з и записывается в регистр 10.1,3. В регистры 7,1,3 и 6.1.3 записываются а 2 з и Ьзз. На входы умножителя 14,1,1 вычислительного модуля 2.1.1 поступают элементы б 11 и с 11, где происходитумножение б 11 с 11 и произведение поступает в сумматор 13,1,1, где складывается с нулем и б 11 с 11+О записывается в регистр 16,1,1, В регистр 12,1,1 записывается элемент б 11, а элемент с 11 передается в вычислительный модуль 2.2,2 и записывается в регистр 15,2,2, В сумматоре 9,2,2 вычислительного модуля 1,2.2 получаем а 11 Ь 1 з+а 12 Ь 2 з+а 1 зЬзз= = б 1 з и элемент б 1 з записывается в регистр 12.2.2, С выхода сумматора 9.2.3 вычислительного модуля 1.2.3 получаем аз 1 Ь 1+аз 2 Ь 22 и эта сумма записывается в регистр 10.2.3. В регистры 6.2,3 и 7.2.3 записываются Ьз 1 и азз. В сумматоре 9.2.1 вычислительного модуля 2.2.1 получаем сумму55 б 22 с 21+О, которая записывается в регистр 10.2,1, В регистр 12,2.1 записывается б 22. В сумматоре 9,2.1, В регистр 12.2.1 записывается б 22. В сумматоре 9.3,2 вычислительного модуля 1.3,2 получаетсяаз 1 Ь 12+аз 2 Ь 22+аззЬ 32 = бз 2 и записывается в регистр 12.3.1 вычислительного модуля 2.3.2, В регистр 15.3,2 записывается сз 1. С выхода сумматора 9,3,3 вычислительногомодуля 1,3.3 поступает а 11 Ь 12+а 12 Ь 22 записывается в регистр 10,3,3. В регистры 7.3.3 и 6,3,3 записывается а 1 з и Ьз 2. С выхода сумматора 13,3.1 вычислительного модуля 2,3,1 поступает бззсз 1+О и записывается врегистр 16.3,1. В регистр 12.3.1 записывается бзз.В пятом такте в сумматоре 9.1.3 вычислительного модуля 1.1,3 получаем а 21 Ь 13+а 22 Ьгз+а 2 зЬзз = б 23 и элемент б 2 з записывается в регистр 12.1.3 вычислительного модуля 2,1,3. В регистр 15,1, 3 записывается с 21. С выхода сумматора 13.1,2 вычислительного модуля 2.1.2 поступает б 11 с 11+б 21 с 21 и записывается в регистр16.1.2 вычислительного модуля 2.1.2. В регистр 12,1.2 записываетсяэлемент б 21, С выхода сумматора 13.1,1 вычислительного модуля 2.1.1 выдается б 11 с 12+О и записывается в регистр 16,1,1, В регистр 12.1.1 записывается б 11, В сумматоре 9,2.3 вычислительного модуля 1,2,3 получаем аз 1 Ь 11+аз 2 Ь 22+аззЬЗ 1 =- бз 1 и элемент б 31 записывается в регистр 10,2,3 вычислительного модуля 2,2.3, В регистр 15.2,3 записывается сз 1, С выхода сумматора 13,2.2 вычислительного модуля 2.2.2 выдается бззсз 1+б 1 зс 11 и записывается в регистр 16,2.2, В регистр 12,2,2 записывается б 1 з, С выхода сумматора 13.2.1 вычислительного модуля 2,2,1 поступает б 22 с 22+О и записывается в регистр 16,2,1, В регистр 15.2,1 записывается с 2 з, В сумматоре 9,3,3 вычисл ител ьн ого модуля 1.3.3 получаем а 11 Ь 12+а 12 Ь 22+а 13 Ь 32 = б 12 и элемент б 12 записывается в регистр 12,3.3 вычислительного модуля 2.3,3. В регистр 15.3.3 записывается с 11, С выхода сумматора 13,3,2 вычислительного модуля 2,3.2 поступает б 22 сз 2+О и записывается в регистр 16.3,2. В регистр 12.3,2 записывается бз 2, С выхода сумматора 13.3.1 вычислительного модуля 2,3,1 поступает бззсз 2+О и записывается в регистр 16,3.1, В регистр 15.3.1 записывается сзз. В шестом такте в сумматоре 13,1.3 вычислительного модуля 2,1,3 получаем первый окончательный результат бззсз 1+б 1 зс 11+б 2 зс 21 = тз 1, который записывается в регистр 14.1.3, В регистр 12.1.3 записывается б 23, С выхода сумматора 1015202530 354045 50 13,1,2 вычислительного модуля 2,1,2 поступает б 11 с 12+б 21 с 22 и записывается в регистр 16,1,2, В регистр 12.1.2 записывается б 21, С выхода сумматора 13.1,1 вычислительного модуля 2,1,1 поступает б 11 с 13 и записывается в регистр 16.1,1. В сумматоре 13,2.3 вычислительного модуля 2,2,3 получаем б 11 С 11+б 21 с 21+б 31 с 31 = т 11 и результат т 11 записывается в регистр 16,2.3. В регистр 15,2,3 записывается сз 2, С выхода сумматора 13.2.2 вычислительного модуля 2,2,2 поступает бззсз 2+б 1 зс 12 и записывается в регистр 16,2,2, В регистр 15.2.2 записывается с 1 з. С выхода сумматора 13.2.1 вычислительного модуля 2.2.1 поступает б 22 с 2 з+О и записывается в регистр 16.2,1. В сумматоре 13.3.3 вычислительного модуля 2.3.3 получаем б 22 с 21+бз 2 сз 1+б 1 гс 11 = т 21, а результат записывается в регистр 16.3.3, В регистр 12,3,3 записывается б 12. С выхода сумматора 13,3.2 вычислительного модуля 2.3,2 поступает б 22 с 22+бз 2 сзз и записывается в регистр 16,3.2. В регистр 12.3.2 записывается бз 2. С выхода сумматора 13.3.1 вычислительного модуля 2,3,1 поступает бззсзз+О и записывается в регистр 16,3.1,В седьмом такте в сумматоре 13,1.3 вычислительного модуля 2,1,3 получаем бззс 32+б 13 с 12+б 23 С 22 = зз и результат тзз записывается в регистр 16.1.3, а с его выхода на выход устройства выдается 131, С выхода сумматора 13.1.2 вычислительного модуля 2.1.2 поступает б 11 с 13+б 21 с 23 и записывается в регистр 16,1,2, В сумматоре 13,2,3 вычислительного модуля 2.2.3 получаем б 11 с 12+б 21 с 22+бз 1 сз 2 = т 12 и результат записывается в регистр 16,2.3, с выхода которого на выход устройства выдается 111. В регистр 12.2,3 записывается бз 1, С выхода сумматора 13,2,2 вычислительного модуля 2.2,2 поступает бззсзз+б 1 зс 1 з и записывается в регистр 16,2.2, В сумматоре 13,3.3 вычислительного модуля 2.3,3 получаем б 22 с 22+б 32 сз 2+б 12 с 12 = т 22 и результат записывается в регистр 16.3,3, с выхода которого выдается 121. В регистр 12,3,3 записывается б 12. С выхода сумматора 13,3.2 вычислительного модуля 2,3,3 поступает б 22 с 23+бз 2 сзз и записывается в регистр 16.3.2,В восьмом такте в сумматоре 13,1.3 вычислительного модуля 2,1.3 получаем бззсзз+б 1 зс 1 з+б 2 зс 2 з = 133 и результат 133 записывается в регистр 16,1,3, с выхода которого выдается 132. В сумматоре 13,2.3 вычислительного модуля 2,2,3 получаем б 11 с 1 з+бг 1 с 2 з+бг 1 сзз = бз и результат записывается в регистр 16.2,3, с выхода которого выдается т 12. В сумматоре 13,3.3 вычислительного модуля 2.3.3 получаемо 22 с 23+о 32 с 33+а 12 с 13 = т 23 и результат записывается в регистр 14.3,3, с выхода которого выдается 122.В девятом такте с выходов вычислительных модулей 2,1.3, 2,2,3 и 2.3.3 соответственно выдаются окончательные результаты т 33, т 23 т 13На этом работа устройства по вычислению матрицы Р = АхВхС заканчивается. Формула изобретения 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 55 го и второго типов соединены соответственно с вторыми информационными входами (+1,з)-х вычислительных модулей первого и второго типов (где з = )-1 и ри (+) - четном или з =)+1 при (+ - нечетном, причем 3 =) при ) = 1, ) = и), третий информационный выход (Ц)-го вычислительного модуля первого типа соединен с третьим информационным входом (1,1)-го вычислительного модуля второго типа.2. Устройство по и, 1, отл и ча ю щеес я тем, что каждый вычислительный модуль первого типа содержит три регистра, умно- житель, сумматор и триггер, причем информационный вход первого регистра подключен к первому информационному входу модуля, второй информационный вход которого подключен к информационному входу второго регистра, выход первого регистра подключен к первому входу умно- жителя и первому информационному выходу модуля, второй информационный выход которого подключен к выходу второго регистра и второму входу умножителя, выход которого подключен к входу первого слагаемого сумматора, вход второго слагаемого которого подключен к выходу третьего регистра, информационный вход которого подключен к выходу сумматора и третьему информационному выходу модуля, вход разрешения записи которого подключен к входу разрешения сброса третьего регистра и входу триггера, выход которого подключен к выходу разрешения записи модуля, вход синхронизации которого соединен с синхровходами всех резисторов,3, Устройство по и, 1, о т л и ч а ю щ е ес я тем, что каждый вычислительный модуль второго типа содержит три регистра, умно- житель и сумматор, причем информационный вход первого регистра подключен к третьему информационному входу модуля, первый информационный вход которого подключен к входу первого слагаемого сумматора, вход второго слагаемого которого подключен к выходу умножителя, первый вход которого подключен к выходу первого регистра, второй вход умножителя подключен к выходу второго регистра и второму информационному выходу модуля, второй информационный вход которого подключен к информационному входу второго регистра, выход сумматора подключен к информационному входу третьего регистра, выход которого подключен к первому информационному выходу модуля, вход разрешения записи которого соединен с входом записи первого регистра, вход синхронизации модуля соединен с синхровходами всех регистров.1790786 Корректор Т,Вашкови еда енно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 10 Произ Составитель Е.МурзиТехред М.Моргентал каз 375 Тираж Под ВНИИПИ Государственного комитета по изобретениям и 113035, Москва, Ж, Раушская наб, сное крытиям при ГКНТ ССС