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

СООЭ СОВЕТСКИХсоцидлистичеснихРЕСПУБЛИК у)5 С 06 Р 15/3 аппаратуржит вы нижени иство сод и, сгрупп модули, б ые ов оки с рь,уммиы онные ды иждый нфор лекс ления.содержи и 144245,ционы,вхо ы, мульти оки п и е и волок суммирования сонные входы и выходы, ительный блок содере входы и выходы, в, умножитель и ре- В основу работы уст екуррентный алгоритм матриц, разбитых на ю р х р (и кратно р),для высоий, ТИИЭР,ис. 8. ОЖЕНИЯ МАТ к вычиссит ожет быть изво оцессорах для сивов данных. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРИГИЯПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Заявка Великобританиикл. С 06 Р 7/52, 1985.Гун Суньюань, Систоличеновые матричные процессорыкопроиэводительных вычислет; 72, 1984, 11 7, с. 140,(54) УСТРОЙСТВО ДЛЯ (57) Изобретение отн лительной технике и пользовано в высокоп специализированных и обработки больших ма О 1585804 Цель изобретения - ных затрат. Устро" числительные блок в вычислительные рования, ннформаци ходы, входы управ лительный модуль ные входы и выход элементы задержки, ды управления, Бл дерыт информацио сумматоры. Вычисл жит информационны регистры операндо гистр результата. ройства положен р перемножения и х п блоки размерность 3 э.п. ф-лы, 5 ил.1ар арв ар фро а, авв а всвр ср, сс срв с, с рр с ев Ъв, Ьвв ЬвещЬр = с р: в сввсвв ав, ав авв ав ЬВ, ЬВр ЬВЬрр р в " в в " в- " вв ар, авв а авв( 1 ) 5 5Каждый элемент с результирующей матрицей С определяется по рекуррентной формуле Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специа-лизированных процессорах для обработки больших Массивов данных,Цель изобретения - снижение аппаратурных затрат,На фиг. 1 представлена структурнаясхема устройства для умножения мат 1 Ориц А и В размерности и хп (пунктиром выделен фрагмент, вход управленияне показан); на фиг. 2-4 - составныеэлементы устройства дггя умноженияматриц А и В дпя случая и х и = 8 х 8и р х р = 2 х 2, где р - размерностьблоков, на которые разбиваются перемножаемые матрицы (на фиг, 2 - структурная схема вычислительного модуля,на фиг. 3 - структурная схема блока20суммирования; на фиг. 4 - структурнаясхема вычислительного блока); наФиг, 5 - последовательность вводаданных и получения результатов.Устройство (Фиг. 1) содержит информационные входы 1, вычислительныемодули выходы 3 вычислительных модулей, входы блоков 4 суммирования,блоки 5 суммирования, выходы 6 блоковсуммирования, вхоцы 7 блока суммирования, блок 8 суммирования, выход 9устройства.Вычислительный модуль (фиг. 2) содержит первую 10, и 102 и вторую 10 Зи 104 группы информационных входов,мультиплексоры 11, элементы 12 задерж ки, вычислительные блоки 13, блоки14 памяти, первый 15 и второй 16 управляющие входы, группу выходов 17,Блок суммирования (Фиг. 3) содержит первую 18 и вторую 19 группы вхо дов, сумматоры 20, группу выходов 21,Вычислительный блок (фиг. 4) содержит первый 22 и второй 23 входы, ре-, .гистры 24 и 25, умножитель 26, первый27 .и второй 28 выходы регистр 29 итретий выход 30.Работу устройства можно пояснитьна примере умножения квадратных 8 х 8матриц А и В: А р В = С50(1) в блоки размерности р х р = 2 х 2и обозначим блоки матрицы А Ь;(1=1,1=1,4; 1=1 1 1,4), а блоки матрицырВ Ч,. (1.1, 1; 1=1,1). Ч рв Ч рв Ч вЧвввь ЬЬЬ,в Ь 1 в Ьв Ьвв Ьвр 1 Ь р С ЬврЧЬр Чъ Ч З Чв Чвр Чва ЧЬ Чв ЬЗ Зв Ьва Ьвв ввРезультирующая матрица С также будет разбита на блоки р х р = 2 х 231 32 ЭЭ сЭ 441 4243 Л 4 Блоки Г; матрицы С также будут вычисляться йо рекуррентной формуле (2)о2 р=0,1 4 ав 11;йк, = Х +Ь Ч К=1 1=1 4.рл= 13 1 к к в ввСледовательно, по рекуррентной формуле (3) сразу будут вычисляться р элементов результирующей матрицы С одного блока Й; . Соотношение (3) положено в основу работы предлагаемого устройства для умножения матриц.Устройство работает следующим образом.В статическом режиме на входы 15 и 16 управдения подается разрешающий сигнал логической "1". 11 ри этогл через мультиплексоры 11 разрешается прохождение данных с информационных входов устройства к вычислительным блокам, Все регистры и сумматоры обнулены.1На первом такте (фиг. 5) на информационные входы устройства 1;(2.=14) поступают 4 элемента а соответст 11венно блоков Ь 1 Ь 12 в Ь 13 в Ь ла и 4элемента Ь , блоков Ч, в Ч а Ч э Ч11 2 р Э"41 причем элементы а;в поступают на.входы 10, а элементы Ь; - на входы 10 э вычислительных модулей 2, (1=11;1=1,4). На входы 15 и 16 управления подается разрешающий сигнал логическая "1". Операнды ачерез мультиплексоры 11, поступают ча первые входы вычислительного блока 13 а операнды Ь, через мультиплексоры 11 э - на вторые входы вычислительного блока 1314, оНа четвертом такте сигналы логического 0, задержанные на один такт в, элементах 12 блоков 2; (=1,4), поступают соответственно на третьи входы мультиплексоров 11. Эти сигналы запрещают прием операндов по первым и одновременно разрешают прохождение операндов по вторым входам мультиплексоров 11. Через эти мультиплексоры проходят операнды соответственно с первых выходов вычислительных блоков 13 . Кроме этого, операнды Ь, блоков2Ч 1 Ч 1 Ч 1, Ч с вторых выходов.11 111 91 1вычислительных блоков 13 записываются соответственно в первые регистры блоков 14памяти всех вычислительных модулейВычислительные операции выполняются аналогично описанным. Исключение составляют операции сложения в сумматорах последнего блока 8 суммирования, в котором в накапливающих сумматорах 20 к ранее вычисленным операндам производится прибавление операндов, поступающих на первые и вторые входы блока 8 суммирования. Обнуле 1ние этих сумматоров происходит на следующем такте после вычисления каждого элемента с результирующей матрицы С.На чертертом такте на первые входы 18 блока 8 суммирования поступают операции с выходов 21 блока 5 суммирования, а на вторые входы 19 - с выходов 21 блока 5 суммирования.В конце четвертого такта работы устройства на выходах блока 8, суммирования будут сформированы следующие операнды; на выходе 21, - с =а Ь;, + +а 1 э Ьэ 1+ а Ь 1+ а 1 Ь.,+ а Ь 1+ + а, Ь 1+ аЬ 1+ а 1 Ь 1, н выход+ а 1 ьЬХ+ а 1 Ь+ а 1 цЬ 11 фна выходе 21- а,Ь 11+ аЗЬ э 1+ ау + аЬ ; на выходе 211 - О.Таким образом, в конце 4 такта на сумматоре 20, блока 8 суммирования будет сформирован первый элемент с11 результирующей матрицы С, а на сумматорах 21 и 21начнется формирование соответственно элементов с, и с 1.Аналогично вычисляются остальные элементы матрицы-результата С. 5 158580 (фиг. 2), Операнды а записываются в первые 24, а операнды Ь- во вторые25 регистры операндов (фиг. 4). После этого умножители 26 вычислительных блоков 13, выполняют операцию умноже ния а Ь и результаты записываются в регистры 29 результатов. На этом первый такт работы устройства заканчивается. Остальные вычислительные блоки 13 вычислительных модулей 2; и сумма 1 О торы 20 блоков 5 и 8 суммирования произ водят операции с нулевыми операндами, так как перед началом работы они были обнулены.15Таким образом, после первого такта работы в регистрах 29 результата вычислительного блока 13 вычислитель 11ных модулей 2 будут следующие операнды: а Ь, - в вычислительном модуле 21, а, Ъ 1 в в вычислительном модуле 2; а 1 Ь 1 - в вычислительном модуле 2 з, аЬ , - в вычислительном модуле 2.На втором такте на информационные входы устройства поступают элементы а , а 1, Ь 1, Ь г тех же блоков Ь;(1=1,4) и Ч;,(1=1,4), причем элементы а, поступают на входы 10, а эпементы а , - на входы 10, элементы Ь 1 в на входы 10 , элементы Ь - на входы 10 всех вычислительных блоков 2 (=1,4), Элементы апереписываются из регистров 24 вычислительных блоков 13 и в регистры 24 вычислительных блоков 13 Элементы Ь, переписы 11ваются из регистров 25 вычислительных 35 блоков 13 в регистры 25 вычислитель 11ных блоков 13,. Операнды из регистров 29 результата вычислительных блоков 13 всех вычислительных модулей поипарно поступают,на сумматоры 20 бло ков 5и 5суммирования. Элементы а , а , ЬЬ записываются в перИ 1 фвые 24 и вторые 25 регистры вычислительных блоков 13 1 1313 1результате выполнения операций умно жения в регистрах 29 результата вычислительных модулей 2, в конце 2-го такта будут следующие операнды: а 1 Ь а 1 ц Ь а,Ь и (. = 1); на выходе 21, блока 5, - а 1 Ь 1+ а 11 Ъ 1, 50 на выходе 21 блока 5 я. - а Ь+ + а Ь, на выходе 21 блока 5 а Ь 1 + а Ь ; на выходе 21 блока 5- О.В регистрах 29 результата вычислительных блоков 13 вычислительных мо-. дулей 2 будут сформированы произведения в соответствии с поступивпями операндами (фиг. 2 и 5). Формула из обретения 1. Устройство для умножения матриц. содержащее ш = рп вычислительных модулей (п - размерность обрабатываемых матриц, кратная р; р - размер 7 1585804 8ности блоков обрабатываемых матриц) 3.-е и З-е информационные входы которых (=1,р; 1=р+1;2 р) образуют соответственно первую и вторую груп 5 пы информационных входов устройства, о т л и ч а ю щ е е с я тем, что, с целью снижения аппаратурных затрат, устройство содержит 1-1 блоков суммирования (1=п/р), причем входы первой и второй групп К-го (К=1,1/2) блока суммирования подключены к соответствующим выходам групп выходов соответственно (2 К)-го и 2 К-го вычислительнЫх модулей, группа выходов (1-1,)=го блока сумматоров является группой выходов устройства, входы первой и второй групп Б-го блока суммирования (Б г+1; г+; г 1/2+1/4++1/2 Т;-.1,1/2) подключены к соответствующим вы О ходам групп выходов соответственно (Б)-го и (Б+2 т+1)-го блоков суммирования, управляющие входы вычислительных модулей образуют группу управляющих входов устройства. 252. Устройство по п, 1, о т л и - ч а ю щ е е с я тем, что,каждый вычислительный модуль содержит 2 р мультиплексоров, 2 рэлементов задержки, р вычислительных блоков и р блс- ЗО йов памяти, причем -е входы первой и второй групп информационных входов вычислительного модуля соединены с первыми информационными входами соответственно 1-го и (+р)-го мультиплексоров, первый и второй управляющие входы вычислительного модуля, подключены соответственно к управляющим входам первого и (р+1)-го мультиплексоров, управляющие выходы х-го и (х+р)- го мультиплексоров подключены к вхо 4 О дам соответственно -го и (х+р)- го элементов задержки, выходы которыхподключены к управляющим входам соответственно (х+1)-го и (+р+1)-го муль.типлексоров, информационный выход45 1-го мультиплексора подключен к первому входу (, 1)-го вычислительного блока, первый выход (, ч)-го вычислительного блока (ч=1,р) подключен к первому входу (.,ч+1)-го вычислительного блока, а первый выход (1,р)-го вычислительного блока подключен к второму информационному входу -го мультиплексора, информационный выход (1+р)-го мультиплексора подключен к второму входу (1,1)-го вычислительного блока, второй выход (ч,1)-го вычислчтельного блока подключен к второму входу (ч+1,1)-го вычислительного блока, второй выход (р,х)-го вычислительного блока подключен к входу -го блока памяти, вы-. ход которого подключен к второму информационному входу (+р)-го мультиплексора, третий выход (,1)-го вычислительного блока подключен к 1-1)р+1)-му выходу вычислительного модуля.3. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок суммирования содержит р сумматоров, первые и вторые входы которых образуют соответственно первую и вторую группы входов блока суммирования, группу выходов .которого образуют выходы сумматоров.4. Устройство по п, 2, о т л ич а ю щ е е с я тем, что вычислитель. ный блок содержит три регистра и умножитель, первый и второй входы которого подключены соответственно к первому и второму выходам вычислительного блока, первый и второй входы которого подключены к входам соответственно первого и второго регистров, выходы которых подключены соответственно к первому и второму входам умножителя, выход которого является третьим выходом вычислительного блока.1585804 Составитель К. ККопча Техред Л,сердюков е Корректор В. Гири едакто 5 б 9 каз 232 исное В Гову бретениям и открытиям при ГКНТ СССРаушская наб., д. 4/5 роиэводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101 ственного комитета по 113035, Москва, Ж чав Ф р л