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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 06 Р 15/34 51) АВТОР ВИДЕТЕЛ ЬСТВУ АТеский институт им ьской социалисти Ю.С. Каневский, менко и С.Г. Овра 144245,СР86. нии М 1985 ьство /347,ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(71) Киевский политехнич50-летия Великой Октябческой революции(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ М РИЦ(57) Изобретение. относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами. Целью изобретения является упрощение устройства за счет уменьшения числа информационных входов. Устройство для умножения матриц содержит матрицу из Й х М вычислительных модулей и блок управления. Вычислительный модуль 1.Ц(1,) =1, М) содержитумножитель 3, регистры 4,5,6,7;10 и 11, сумматор 8, мультиплексор 9 и триггеры 12 и 13. 3 ил,45 50 55 Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализиро- ванных, в том числе и систолических устройств, предназначенных для выполнения операций над матрицами.Цель изобретения - упрощение устройства за счет уменьшения числа информационных входов.На фиг,1 представлена функциональная схема устройства для умножения матриц; на фиг.2 - функциональная схема вычислительного модуля; на фиг,З - функциональная схема блока управления.Устройство для умножения матриц (фиг.1) содержит матрицу из Й х М вычислительных модулей 1(где И - порядок матрицы (й = 2 г+ 1, г = 1,2,3,) и блок управления 2.Вычислительный модуль 1.Ц (1, ) = 1, К) (фиг.2) содержит умнокитель 3, регистры 4 - 7, сумматор 8, мультиплексор 9, регистры 10 и 11 и триггеры 12 и 13,Блок управления 2 (фиг,З) содержит генератор тактовых импульсов 14, счетчик 15 и дешифратор 16,Устройство работает следующим образом.В основу работы устройства положен алгоритм умножения матрицы А = (а 1) на матрицу В = (Ь, определяющий матрицу С = (с 1 Д (1 = 1.п, ) = 1 п, где и - порядок квадратной матрицы): Определение любого элемента С требует и-кратного выполнения операции накопленияС 1 = С 1+ ааЬц,1( - 1(2)Для простоты описания и без потериобщности положим й = 3. Условимся, чтоприем информации в триггеры и регистрыпроисходит по переднему фронту синхроимпульса, Будем рассматривать случайквадратных матриц К = К. В исходном состоянии триггеры и регистры устанавливаютсяв нулевое состояние. На первый информационный вход по тактам подаются элементыаа матрицы А, на второй информационныйвход подаются элементы Ьц матрицы В, Активный сигнал поступает через каждые дватакта на третий,В начале первого такта на входе запускаустройства присутствует единичный сигналпуска, по которому в первом такте триггер12 устанавливается в единицу, Кроме того,на первый информационный вход вычислительного модуля 1,1,1 поступает элемент а 11, нэ второй информационный вход которого поступает элемент Ь 11, эти элементы поступают соответственно в регистры 4.1.1 и 7,1,1 соответственно на первый и второй входы умножителя 3.1.1., с выхода которого произведение а 11 Ь 11 поступает на первый вход сумматора 8,1,1, на второй вход которого с третьего информационного входа поступает нуль, С выхода сумматора 8.1.1 сумма а 11 Ь 11+ 0 поступает в регистр 10.1.1. В вычислительном модуле 1,2,1 на информационные входы соответственно поступают элементы а 21 и Ь 12. Злемент а 21 записывается в регистр 4,2.1, а элемент Ь 12 записывается в регистр 7,2.1 и соответственно в умножитель 3,2,1, с выхода которого произведение а 21 Ь 12 поступает в сумматор 8,2,1, с выхода которого сумма а 21 Ь 12+ 0 поступает в регистр 10.2.1. В вычислительном модуле 1,3,1 в регистр 4,3.1. поступает элемент аз 1,а в регистр 7.3,1 - элемент Ь 1 з. эти элементы соответственно поступают в умножитель 3.3.1, с выхода которого произведение аз 1 Ь 1 з через сумматор 8.3,1 поступает в регистр 10,3.1,Во втором такте в вычислительном модуле 1.1,1 элемента а 11 с выхода регистра 4,1.1 переписывается в регистр 5.1.1, а элемент Ь 11 с выхода регистра 7,1.1 переписывается в регистр 6.1,1, В регистры 4,1.1 и 7,1,1 соответственно записываются элементы аз 2 и Ь 22. С выхода углножителя 3,1,1 выдается произведение аз 2 Ь 22, которое, пройдя через сумматор 8.1.1, записывается в регистр 11.1.1, В вычислительном модуле 1.2.1 элементы а 12 и Ь 12 с выхода регистров 4,2,1 и 7.2.1 соответственно переписываются в регистры 5,2,1 и 6,2,1, а в регистры 4,2.1 и 7,2,1 записываются соответственно а 12 и Ь 2 з. С выхода умножителя 3.2,1 получаем произведение а 12 Ь 2 з, которое, пройдя сумматор 8.2,1, поступает на первый вход мультиплексора 9,2.1, с выхода которого поступает в регистр 11.2,1. В вычислительном модуле 1;3.1 элементы аз 1 и Ь 1 з с выхода регистров 4,3,1 и 7,3.1 переписываются соответственно в регистры 5,3,1 и 6.3.1. С выхода умножителя 3,3,1 получаем произведение, которое, пройдя сумматор 8,3,1 и мультиплексор 9,3.1, поступает в регистр 11,3,1. В третьем такте в вычислительном модуле 1.1.1 элемент аз 2 с выхода регистра 4.1,1 переписывается в регистр 5.1.1, а элемент Ь 22 с выхода регистра 7.1,1 переписывается.в регистр 6,1.1, В регистры 4.1.1 и 7.1.1 соответственно записываются элементы а 2 з и Ьзз, С выхода умножителя 3.1,1 выдается произведение а 2 зЬзз, которое, пройдя через сумматор 8.1,1, записывается в регистрзаписываются соответственно а 2 з и Ьз 1, С 5выхода умножителя 3.2.1 получаем произве 10 15 элементы поступают соответственно в регистры 4.1,2 и 7.1.2 и соответственно на пер 25 30 35 40 11.1.1. В вычислительном модуле 1.2,1 элементы аа и Ь 2 з с выхода регистров 4.2.1 и 7,2,1 соответственно переписываются в регистры 5,2.1 и 6.2.1, а в регистры 4.2.1 и 7.2.1 дение аззЬз 1, которое, пройдя сумматор 8,2,1, поступает на первый вход мультиплексора 9.2.1, с выхода которого поступает в регистр 11.2.1, В вычислительном модуле 1.3.1 элементы а 22 и Ь 21 с выхода регистров 4.3.1 и 7.3.1 переписываются соответственно в регистры 5.3,1 и 6.3,1, С выхода умно- жителя 3.3,1 получаем произведение, которое, пройдя сумматор 8.3,1 и мультиплексор 9.3.1, поступает в регистр 11.3,1, В вычислительный модуль 1.1.2 поступает элемент аз, на второй информационный вход которого поступает элемент Ь 12, эти вый и второй входы умножителя 3."1.2, с выхода которого произведение азЬ 12 поступает на первый вход сумматора 8,1,2, на второй вход которого с третьего информационного входа поступает аз 2 Ь 22 и сумма аз 1 Ь 2 + аз 2 Ь 22 с выхода сумматора 8;1.2 поступает в регистр 10.1.2, В вычислительном модуле 1.2.2 на информационные входы соответственно поступают элементы а 11 и Ь 1 з. Элемент а 11 записывается в регистр в умножитель 3.2.2. с выхода которого произведение а 11 Ь 1 з поступает в сумматор 8,2,2, с выхода которого сумма а 1 Ь 1 з+ аиЬ 2 з поступает в регистр 10,2,2, В вычислительном модуле 1.3,2 в регистр 4,3,2 поступает элемент а 21, а в регистр 7.3.2 - элемент Ь 11, эти элементы соответственно поступают в умножитель 3.3,2, с выхода которого произведение а 21 Ь 11 поступает в сумматор 8.3,2, свыхода которого сумма а 2 Ь 1+ а 22 Ь 2 поступает в регистр 10.3.2. В четвертом такте в вычислительном модуле 1.1.1 элемент а 2 з с выхода регистра 4.1,1 переписывается в регистр 5,1,1, а элемент Ьзз с выхода регистра 7,1,1 переписывается в регистр 6,1,1, В регистры 4,1,1 и 7,1.1 соответственно записываются элементы новых матриц А и В а 1 и Ь и . С выхода умножителя 3.1,1 выдается произведение а 11 Ь 1, которое, пройдя через сумматор 8.1.1, записывается в регистр 10.1.1, В вычислительном модуле 1,2.1 элементы азз и Ьз 1 с выхода регистров 4.2.1 и 7,2,1 соответственно переписываются в регистры 5.2,1 и 6.2.1, а в регистры 4,2,1 и 7.2.1 записываются соответственно элементы а 21 и Ьц . В вычислительном модуле 1.3.1 элементы а 1 з и Ьз 2 с выхода регистров 4.3.1 и 7.3;1 переписываются соответственно в регистры 45 50 55 5,3,1 и 6,3,1. В вычислительном модуле 1.1,2 элементы аз и Ь 12 с выхода регистров 4.1.2 и 7.1.2 соответственно переписываются в регистры 5.1.2 и 6.1.2, а в регистры 4,1,2 и 7.1.2 поступают элементы а 22 и Ь 2 з. которые также поступают на входы умножителя 3.1.2, с выхода которого произведение а 22 Ь 2 з поступает в сумматор 8,1.2, с выхода которого выдается сумма а 22 Ь 2 з+ а 2 зЬзз, которая поступает в регистр 11,1.2, В вычислительном модуле 1,2.2 с выходов регистров 4.,2 л 7,2.2 элементы а1 и Ь 1 з соответственно переписываются в регистры 5.2.2 и 6,2.2, а в регистры 4.2.2 и 7,2,2 соответственно поступают элементы аз 2 и Ь 21, которые также поступают в умножитель 3.2.2, с выхода котооого произведение аз 2 Ь 21 поступает в сумматор 8.2.2, с выхода которого сумма аз 2 Ь 2 + аззЬз поступает в регистр 11.2.2. В вычислительном модуле 1.3,2 с выходов регистров 4.3.2 и 7.3,2 элементы а 21 и Ь 11 соответственно переписываются в регистры 5,3,2 и 6,3,2, а в регистры 4.3.2 и 7.3,2 записываются элементы а 2 и Ь 22. эти элементы поступают в умножитель 3,3.2, с выхода которого произведение ааЬ 22 поступает в сумматор 8,3.2, с выхода которого сумма а 12 Ь 22+ а 1 зЬз 2 поступает в регистр 11,3.2.В пятом такте в вычислительном модуле 1.1.2 элементы а 22 и Ь ц с выхода регистров 4,1,2 и 7.1,2 соответственно переписываются в регистры 5 1.2 и 6.1,2, а в регистры 4.1.2 и 7.1,2 поступают элементы абаз и Ьз 1, которые также поступают на входы умножителя 3,1,2, с выхода которого произведение а 1 зЬз 1 поступает в сумматор 8.1,2, с выхода которого выдается сумма а 1 Ь 11+ а 1 зЬз 1, которая поступает в регистр 11.1.2. В вычислительном модуле 1.2.2 с выходов регистров 4,2.2 и 7.2.2 элементы аз 2 и Ь 21 соответственно переписываются в регистры 5.2.2 и 6.2.2, а в регистры 4.2.2 и 7.2,2 соответственно поступают элементы а 2 з и Ьз 2, которые также поступают в умножитель 3.2.2, с выхода которого произведение а 2 зЬз 2 поступает в сумматор 8.2.2, с выхода которого сумма а 21 Ь 12+ а 2 зЬз 2 поступает в регистр 11.2,2. В вычислительном модуле 1,3,2 с выходов регистров 4.3.2 и 7,3.2 элементы а 2 и Ь 22 соответственно переписываются в регистры 5.3,2 и 6,3.2, а в регистры 4.3.2 и 7.3.2 записываются элементы азз и Ьзз, эти элементы поступают в умножитель 3,3,2, с выхода которого произведение аззЬзз поступает в сумматор 8.3,2, с выхода которого сумма азфЬц+ аззЬзз поступает в регистр 11,3,2, В вычислительном модуле 1.1.3 на первый информационный вход поступает элемент а 2, который поступает в регистр 4.1.3, а на второй информационный вход вычислительно 1835548го модуля поступает элемент Ь 1 з, который поступает в регистр 7,1.3, эти элементы соответственно поступают на первый и второй входы умножителя 3,1,3, с выхода которого произведение а 21 Ь 1 з поступает на первый вход сумматора 8,1.3, на второй вход которого с третьего информационного входа поступает а 22 Ь 2 з + а 2 зЬзз и сумма аг 1 Ь 1 з + а 22 Ь 23 + а 2 зЬЗЗ = С 2 З с выхода сумматора 8.1,3 поступает в регистр 10,1.3.В вычислительном модуле 1.2.3 на информационные входы соответственно поступают элементы аз 1 и Ь 11. Элемент аз 1 записывается в регистр 4,2,3, а элемент Ь 11 записывается в регистр 7,2,3 и соответственно в умножитель 3,2,3, с выхода которого произведение аз 1 Ь 11 поступает в сумматор 8,2.3, с выхода которого сумма аз 1 Ь 11+ аз 2 Ь 21+ аззЬЗ 1 = СЗ 1 поступает в регистр 10,2,3, В вычислительном модуле 1.3,3 в регистр 4,3.3 поступает элемент а 11, а в регистр 7,3,3 - элемент Ь 12, эти элементы соответственно поступают в умножитель 3.3,3, с выхода которого произведение а 11 Ь 12 поступает в сумматор 8,3.3, с выхода которого сумма а 11 Ь ц + а 12 Ь 22+ а 1 зЬз 2 = С 12 поступает в регистр 10,3,3.В шестом такте в вычислительном модуле 1,1,2 элементы аз и Ьз 1 с выхода регистров 4.1.2 и 7,1,2 соответственно переписываются в регистры 5.1,2 и 6.1.2, В . вычислительном модуле 1.2.2 с выходов регистров 4.2,2 и 7.2,2 элементы а 1 з и Ьз 1 соответственно переписываются в регистры 5,2,2 и 6,2.2 В вычислительном модуле 1.3.2 с выходов регистров 4.3,2 и 7.3.2 элементы азз и Ьзз соответственно переписываются в регистры 5 3 2 и 6 3 2. В вычислительном модуле 1.1.3 элементы,а 21 и Ь 1 з с выхода регистров 4.1,3 и 7.1.3 соответственно переписываются в регистры 5,1,3 и 6.1,3, а в регистры 4,1,3 и 7.1,3 соответственно поступают элементы а 12 и Ь 21, эти элементы соответственно поступают на первый и второй входы умножителя 3,1.3, с выхода которого произведение а 12 Ь 21 поступает на первый вход сумматора 8,1.3, на второй вход которого с третьего информационного входа поступают а 11 Ь 11+ а 1 зЬз 1 и сумма а 1 Ь 11+ Э 1 зЬз + а 12 Ь 21- С 11 с выхода сумматора 8.1.3 поступает в регистр 11,1,3, В вычислительном модуле 1,2.3 с выхода регистров 4,2,3 и 7,2,3 соответственно элементы аз 1 и Ь 11 переписываются в регистры 5,2.3 и 6.2.3, а элементы а 22 и Ь 1 соответственно записываются в регистры 4,2.3 и 7.2,3 и в умножитель 3.2.3, с выхода которого произведение а 22 Ьз 2 поступает в сумматор 8.2,3, с выхода которого сумма а 21 Ь 12 +а 2 зЬЗ 2 + а 22 Ьз 2 = С 22 поступает в регистр 1 1,2.3.В вычислительном модуле 1.3.3 с выходов регистров 4.3.3 и 7,3.3 соответственно элементы а 11 и Ь 12 переписываются в регистры 5,3,3 и 7.3.3, эти элементы поступают в умножитель 3,3.3, с выхода которого произведение аз 2 Ь 2 з поступает в сумматор 8.3.3, с выхода которого сумма аз 1 Ь 1 з + аззЬзз + +аз 2 Ь 2 з = Сзз поступает в регистр 11,3,3.В седьмом такте в вычислительном модуле 1.1.3 элементы а 12 и Ь 21 с выхода регистров 4.1,3 и 7,1,3 соответственно переписываются в регистры 5,1,3 и 6,1,3, а в регистры 4,1,3 и 7,1.3 соответственно поступают элементы азз и ЬЗ 2, эти элементь: соответственно поступают на первый и второй входы умножителя 3.1.3, с выхода которого произведение аззЬз 2 поступает на первый вход сумматора 8,1,3, с выхода которого сумма аз 1 Ь 12 + аз 2 Ь 22 + аззЬз 2 = Сз 2 поступает в регистр 11.1.3, с выхода которого С 11 выдается на выход устройства. В вычислительном модуле 1.2,3 с выхода регистров 4,2.3 и 7.2.3 соответственно элементы а 22 и Ьз 2 переписываются в регистры 5,2.3 и 6,2,3, а элементы а 1 з и Ьзз соответственно записываются в регистры 4.2,3 и 7,2,3 и в умножитель 3,2.3, с выхода которого произведение а 22 Ьз 2 поступает в сумматор 8.2.3, с выхода которого сумма а 11 Ь 1 з + а 12 Ь 2 з + а 1 зЬзз = С 1 з поступает в регистр 11.2.3, с выхода которого С 22 выдается на выход устройства. В вычислительном модуле 1,3,3 с выходов регистров 4.3.3 и 7,3.3 соответственно элементы аз 2 и Ь 2 з переписываются в регистры 5.3.3 и 7,3.3, а в регистры 4,3,3 и 7,3,3 поступают элементы а 2 з и ЬЗ 1, эти элементы поступают в умножитель 3.3.3, с выхода которого произведение агзЬз 1 поступает в сумматор 8.3.3, с выхода которого сумма а 21 Ь 11+ а 22 Ь 21+ а 2 зЬз 1 = С 21 поступает в регистр 11.3,3, с выхода которого Сзз поступает на выход устройства.В восьмом такте в вычислительном мо 5 10 15 20 25 30 35 40 45 дуле 1.1.3 элементы азз и Ьз 2 с выхода регистров 4.1,3 и 7,1.3 соответственно 1.2.3 с выхода регистров 4.2,3 и 7,2,3 соответственно элементы а 22 и Ь 32 переписываются в регистры 5,2.3 и 6,2,3, С выхода регистра 11,2.3 С 1 з выдается на выход уст ройства. В вычислительном модуле 1.3.3 с выходов регистров 4.3,3 и 7,3,3 соответственно элементы аз 2 и Ь 2 з переписываются в регистры 5,3,3 и 6.3.3, С выхода регистра11,3.3 С 21 поступает на выход устройства. переписываются в регистры 5,1,3 и 6,1.3. С выхода регистра 11.1,3 Сз 2 выдается на вы.ход устройства. В вычислительном модулеВ девятом такте с выхода регистра 11.1,3 на выход устройства выдается Сгз, С выхода регистра 11.2.3 на выход устройства выдается Сзс. С выхода регистра 11,3.3 на выход устройства выдается Ссг,На этом вычисление матрицы С = А х В заканчивается,Формула изобретения устройство для умножения матриц, содержащее блок управления и матрицу из И х И вычислительных модулей (где И - порядок матрицы, И = 2 г+ 1, г = 1,2), каждый из которых содержит первый, второй и третий регистрь 1, умножитель, сумматор и первый триггер, причем первый информационный выход (Ц)-го вычислительного модуля матрицы (1 = 1,И - 1, ) = 1 И - 1) соединен с первым информационным входом ( + 1, ) + 1)-го вычислительного модуля матрицы, второй информационный выход (К -го вычислительного модуля матрицы (к - 1,;.И) соединен с вторым информационным входом (, ) + 1)-го вычислительного модуля матрицы, третий информационный выход (К И)-го, вычислительного модуля матрицы соединен с Е-м выходом устройства, первьсй и второй информационные входы (К, с)-го вычислительного модуля матрицы соединены соответственно с К-ми информационными входами первой и второй групп устройства, К-й информационный вход задания кода нуля которого соединен с третьим информационным входом (К, с)-го вычислительного модуля матрицы, управляющий вход которого соединен с выходом блока управления, при атом в каждом вьсчислительном модуле информационные входы первого и второго регистров соединены соответственно с первым и вторым информационными входами модуля, управляющий вход которого соединен с входом первого триггера и управляющим входом третьего регистра, выход умножителя соединен с входом первого слагаемого сумматора, о т л и ч а ю щ е ес ятем, что, с целью упрощения устройства за счет уменьшения числа информационных входов, в каждый вычислительный модуль введены четвертый, пятый и шестой регистры, мультиплексор и второй триггер, причем первый информационный выход (И, -говычислительного модуля матрицы соединен с первым информационным входом (1, ) + 1)-го вычислительного модуля матрицы, третий информационный выход (1, И-го вычисли 5 10 тельного модуля матрицы ( = 2, И) соединен с третьим информационным входом (- 1,)+1)-го вычислительного модуля матрицы, третий информационньсй выход (с, -го вычислительного модуля матрицы соединен с третьим информационным входом (И, )-го вьсчислительного модуля матрицы, управляющий выход (К, -го вычислительного модуля матрицы соединен с управляющим входом (К, ) + 1)-го вычислительного модуля матрицы, при атом в каждом вычислитель-, ном модуле матрицы первый и второй информационные входы модуля соединены соответственно с первым и вторым входами 15 20 регистров, выходы которых соединены соответственно с первым и вторым информационными выходами модуля, третий информационный вход которого соединен с входом второго слагаемого сумматора, выход которого соединен с первым информационным входом мультиплексора и информационным входом третьего регистра, выход которого соединен с вторым ин 30 35 формационным входом мультиплексора, выход которого соединен с информационным входом шестого регистра, выход которого соединен с третьим информационным выходом модуля, управляющий выход которого соединен с выходом второго триггера, вход которого соединен с выходом первого 40 триггера, вход которого соединен с управляющим входом мультиплексора,25 умножителя, выходы первого и второго регистров соединены соответственно с информационными входами четвертого и пятогоакаэ 2983 ВНИИП Тираж Подписноесударственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва. Ж, Раушская наб., 4/5