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

(9) 06 Е 15/347 ЗОБР ЕНИ ИСАНИ СКО ВИДЕТЕЛЬСТ К А ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) йагпасгзЬгпап ,Ч., Рцззе 0.3.,ЯИЬегзЬай А. ЯузтоИз гпатгх патрИса 1 опзоп а Ипеаг аггау, Ргос 20-тп Аплод АИегТопСоМ. Согптцп, Соптг, апб Согпрцт.,Мопссе 1 о, Ост., 6-8, 1982, з. 1, р. 625-626.ТИИЭР, М 9, 1987, с.194, рис,6,(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ(57) Изобретение относится к вычислительной технике и может быть использовано ввысокопроизводительных специализироИзобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (пхп)-матрицы на ленточную матрицу.Целью изобретения является повыше-. ние быстродействия устройства,На фиг.1 представлена структурная схема устройства для умножения матриц; на фиг.2 - структурная схема устройства для п=4, р=З, ц=2, где и - размерность перемножаемых матриц, р и ц соответственно число ненулевых элементов первой строки и первого столбца матрицы-множителя; на фиг.З - органиэация входого потока элементов и х(р+ц) матрицы В (В получена из исходной ленточной матрицы В путем до 1677709 А ванных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (пхп)-матрицы на ленточную матрицу. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство содержит(р+ц - 1) вычислительных модулей, где р и ц соответственно количество элементов в первом столбце и в первой строке ленточной матрицы. Элементы матрицы-множимого поступают последовательно по столбцам на первый информационный вход устройства, элементы ленточной матрицы-мнокителя подаются параллельно на р+ ц -1 информационных входов группы. В основу работы устройства положена параллельно-поточная органиэация вычислений. 4 ил., 1 табл. полнения ее нулями, описанным на фиг,3 способом, Аналитически В задается следующим образом; Ь = Ь-+р, при 1=1,р; =1,п+)- р и при =р+1,р+ц, =.-р+,п, а в остальных случаях Ь равно О); на фиг,4 - пример схемы вычислительного модуля.Устройство для умножения матриц (фиг,1) содержит первый информационный вход 1, второй информационный вход 2, группу информационных входов 3, синхровход 4, вычислительные модули 5 =1,р+ци выход 6,Вычислительный модуль 5 (фиг.4) содержит первый информационный вход 7, второй информационный вход 8, третий информационный вход 9, синхровход 10, регистры 11-13, умножитель 14, сумматор 15, узел 16 задержки, регистры узла задержки 17 =,п, элемент И 18, первый информа1677709 35 40 45 ционный выход 19 и второй информационный выход 20,В основу работы устройства положеналгоритм перемножения плотной (пхп)-матрицы А на ленточную матрицу Б, основанный нуекуррентных соотношениях;сц =О, а=макс(0, 1-ц), Ц=1,п;с 1 =с, +аж Ьц, 1= а+,п, Ц=1,п;с 1 = с 1(" ), Д = мин(п ) р) Ч = 1 иВычислигельный модуль работает следующим образом.На 1-м такте элементы матрицы а,Ь и сподаются сОответственно на входы 7, 9 и 8и записываются соответственно в регистры11, 13 и 12 (элемент В записывается в регистр 13 при подаче на вход 9 единичногоразряда, который открывает элемент И 18 иразрешает запись в регистр 13). При этом навыходе умножителя 14 формируется значение иЬ, на выходе сумматора 15 - значение(с + аЬ), которое задерживается узлом 16задержки на (и) тактов и выдается на выход 20. Элемент а задерживается на одинтакт регистром 11 и выдается на выход 19,Организация входного и выходного потоков элементов плотных (и х и)-матриц А иС показана на фиг.1, а ленточной матрицыВ на фиг,З. Элементы аа, Ьц и с 1 1 подаются в моменты времени.та ф = и1( + 1 - и - р +(и)(Ц) + 1,тГ= и- ( -О + (рЧ)( -1),1тс) -- 1+ и) - иНа выходе 6 устройства формируются элементы с) = с 11 1 в моменты временит, 11 -- 1+ и) + (и)(р+с(-2) - 1При описа 4 нии работы устройства в обозначении а - индекс 1 в скобках указывает номер рекуррентного шага, а в обозначении а индекс 1 без скобок указываетномер такта работы устройства.Рассмотрим работу устройства для перемножения плотной (и х и)-матрицы А на ленточную матрицу В (п=4, р=З, а=2) (фиг,2),Состояние регистров 11 - 13 и 17 и формируемое значение на выходе сумматора 15 операционных блоков устройства приведены в таблице.Загрузка элементов аа в вычислительный модуль 5 осуществляется с второго по семнадцатый такты, загрузка элементов с)( 1) - с первого по шестнадцатый такты. В соответствии с организацией подачи элементов матрицы В (фигЗ), каждый элемент Ь 11 или нулевое значение подаются на соответствующий вход 31 и вместе с дополнительным (щ+1)-м единичным разрядом, записываются в регистр вычислительного модуля 5 и хранятся в нем п тактов. Элемент 5 10 15 20 25 30 сп = сп( ) + апЬп формируется в вычисли(з) (о)тельном модуле 5 з на четвертом такте, элемент си = сп(айаг Ьг 1 - в вычислительн м(г)модуле 5 г на седьмом такте, элемент сп (= =сО + абаз Ьэ 1 - в вычислительном модуле 5 на десятом такте и выдается на выход 6 устройства на двенадцатом такте, Аналогичным образом формируются остальные элементы с) результирующей матрицы С, которые выдаются на выход 6 устройства с двенадцатого по двадцать седьмой такты в соответствии с приведенной таблицей,Время перемножения платной (пхп)- матрицы на ленточную матрицу равно п(п+р+ц)-р-ц,ПерИод ввода элементов матрицгочередной задачи перемножения равен г тактов,Если на вход 2 в предлагаемом устройстве подавать элементы С,О, то устройство реализует матричную операцию С+ АВ.Кроме того, предлагаемое устройство может выполнить перемножение ленточной матрицы А на плотнук(п х и)-матрицу В, где ленточная матрица А содержит в первом/столбце с 1 элементов, а в первой строке - р элементов, При этом необходимо элементы транспонированной матрицы В аналогичным образом подавать на вход 1, а элементы транспонированной ленточной матрицы А - на входы 31 и на выходе 6 устройства формируются элементы транспонированной результирующей матрицы С,Формула изобретения Устройство для умножения матриц, содержащее р+с 1-1 вычислительных модулей (р и ц - соответственно число ненулевых элементов первой строки и первого столбца ленточной матрицы), причем первый информационный вход первого вычислительного модуля подключен к первому информационному входу устройства, синхровход которого подключен к синхравходам всех вычислительных модулей, первый информационный выход и второй информационный вход 1-го вычислительного модуля (1=1,р+Ч) подключены соответственно к первому информационному входу и второму информационному выходу (1+1)-го вычислительного модуля, второй информационный выход первого вычислительного модуля являетсявыходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, третий информационный вход Е-го вычислительного модуля (1=1,р+ц 1) является К-м входом группы информационных входов устройства; причем каждый вычислительный модуль выполнен с вазможностью реализации функции:(и зг с/ Сзг азг з Сгзс Сгз агг ачг 2 Гг Сзз Сг сгагз гз Свз СЧ 2 Сс 2 С/г с Ссзс )Сз Ггз ачг Сгг Сгг Сз( Сьзгз Счг Сзг Сззэс/ Сгч азз чг Счз зч 3(/ Сз сс Сз Сгг Сч( зу Счч СД С/сч)Счг ггС з СзгСгз (ч 1 6 азу 1) ачч Ссг Сг Сгсз) ) ч Счз Сэ/ г ) - гч С сз)Счг чч С(/(с с/ агу Сгз Гч чс) /ч Счч ачч Сзч Ссч чСЗЧ(ь С,С сч/ Счч Г/ч Счз Сгз С/ч Сзз Сгч Сзч Сз С/ч Ссч С СаЬС" Гл/(а(11"(л:"(1 ю 1 л" (лл Яг Н 1двых авх+п 1 1свых = свх + эвх Ьвх б,где авх, свх и бвх - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на 1-м такте;+1эвых - значение на первом информационном выходе вычислительного модуля на (1+1)-м такте; а- ала/л- ал 1-а 11 а(1 ал/- а 1/аа+о свых - значение на втором информационном выходе вычислительного модуля на ( (.и)-м такте; 5 б - значение ,гп+1)-го разряда Ьвх.п - размерность перемножаемых матриц гп - разрядность операндов.1677709 1 Г 1 г 1 С 1 С аС а С 7 т Я С аС Я 7 С 11 11 С 11 н 11 С 6 С б 1 11 3 41 11 и Лн 47 13 15 Э 5 Ю 14 фУ 4 АД М Ьг.4оставитель К, Кухаренкоехред М,Моргентал Редактор С. Лиси ректор Л. Бескид Заказ 3115 Тираж М 6 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская маб 4/5 ононнат "Патент", г, Ужгород, уа.Гагарнна,анно-издатель ои 16 6 11 6 Ф фСфСУСС бфтдГгтфУ 1 п ц,с.,ап,Ц,СВЦ 7 дЦ 71-а-у 11 С 1,11 В Д Ю 11 17 Ю Ю Л 1 1 С 11 И, Н ж И С 11 1 С 1 С 11 С 1 т СцСу Ср Сд С 71 Сц Ст 1 С 11 С С С 1 та ф УД,1 6,1йт ФЮ,1 Р,РЮ 1 Рб 1 да 0ю,С 1 п,У гф,г 01С