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

(504 С 06 Р 15 ТЕНИЯ ОЖЕНИЯ МАТРИ 15енина полит50-летия Веистической ивска, Р. Выжико кий и В.И. Лози У 52-22218,ик1977.ог 1 СЬщз апдСЕС.-Топгп1982, ч. ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗОБР АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Киевский орденанический институт им.кой Октябрьской социаволюции(56) 1. Заявка Япониикл. С 06 Р 7/38, опуб2. Ис СаЬе. Нем а 1агсЬГесгцгез Гог Ч.БоГ Зсепсе апд ТесЬпоВ 2, рр, 68-75. 801226484 А(54) УСТРОЙСТВО ДЛЯ УИНЦЫ НА ВЕКТОР(57) Изобретение относится к областивычислительной техники и позволяетсократить затраты оборудования иповысить скорость вычислений. Устройство содержит Ь вычислительных модулей и блок управления. На входеблока управления задается один из режимов вычисления: умножение на "ленточную" матрицу или на полностью заполненную матрицу. Входные данныепоступают на информационные входывычислительных модулей, в каждомтакте и с такой же частотой формируются результаты на выходе,первоговычислительного модуля, который является выходом устройства. 4 ил.50122648Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, Функционирующих в реальном масштабе времени,Цель изобретения - уменьшениеобъема оборудования при одновременномувеличении производительности устройства.На фиг. 1 изображена структурная 10схема устройства," на Фиг. 2 - Функциональная схема вычислительного модуля; на фиг. 3 и 4 - блок-схема алгоритма работы устройства при вычислении результата у в случае ленточной 15Кматрицы А,Устройство содержит (Фиг. 1) Ьвычислительных модулей 1.1, 1.21.Ь, блок управления 2. Вычислительный модуль 1.3 содержит (фиг. 2) регистр 3.1 операнда, умножитель 4.1,сумматор 5.1, первый и второй входы.которого соединены соответственно свыходом умножителя 4.1 и вторым информационным входом модуля 1.1; пер. 12 по модулю Ь, вход разрешения счетакоторого является входом блока управления 2, а выход соединен с входомдешифратора 13 (представляющего собой,например, комбинационную схему, опи-сываемую переключательной функциейу = ХХ,Хгде Я= 1 Ход,Ь),выход которого является выходом блокауправления 2. Следует подчеркнуть,что все регистры и триггеры устройст 40ва имеют вход синхронизации, а счетчик 12 - счетный вход (входы не показаны), которые соединены с выходомгенератора тактовых импульсов (непоказан),45При выполнении операции умноженияленточной матрицы А на вектор Х согласно выражению(Ь - ширина ленты матрицы А размеромВхИ+Ь) устройство работает следующим образом.Во время этой операции под воздействием сигнала "Ленточная матрица", поступающего на вход блока управления 2, счетчик 12 по модулю Ь сохраняет свое исходное нулевое состояние,2в результате чего дешифратор 13 поддерживает на выходе блока управления 2 уровень логического "0", передаваемый посредством триггеров управления 10,( и 11.1 на управляющий вход, мультиплексоров 9.3. Элементы Х вход" ного вектора Х (и 0,.1 И+Ь) поступают на первый информационный вход устройства со скоростью одного отсчета на такт, т.е. Х записывается в регистр операнда 3.1 в такте с номером и. Элементы ленточной матрицы А поступают на информационные входы устройства следующим образом: элемент апоступает на второй информационный вход модуля 1. +1) в такте с номером 1 с+21+1.Для того, чтобы сделать более наглядным дальнейшее описание работы устройства, определим базовую операцию, причем под базовой операцией будем понимать повторяющуюся совокупность действий, выполняемых вычислительным модулем. Базовая операция выполняется в течение некоторого такта с номером г в вычислительном модуле 1. следующим образом. В исходный момент времени в первом регистре результата 6.1 и втором регистре результата 7.1 хранятся соответственно частичные результаты Ъ.ф и Ь а в(Ий регистре операнда хранится операнд Х , который затем поступает на вход второго сомножителя умножителя 4.1, на вход первого сомножителя которого с второго информационного входа моду- лЯ 1,1 постУпает опеРанд аз . Затеи умножитель 4.1 Формирует произведение аХ которое поступает на вход первого операнда сумматора 5., на вход второго операнда которого с третьего информационного входа моду" ля 1.1 поступает частичный результатЬ. (в случае модуля 1,1 всегда Ь,(" = О). Сумматор 5.1 формирует сум( ф 2му а Х, + Ь,, которая с приходом тактового импульса записывается в первый регистр результата 6,1, прежнее содержимое которого переписывается во второй регистр результата 7 Поскольку на управляющий вход мультиплексора 9.1 постоянно подается уровень логического 0, то под воздействием тактового импульса осуществляется также перезапись содержимого регистра операнда 3. (1-1) в регистр операнда 3,( (или просто запись нового входного отсчета в регистр 3,1 в случае модуля 1.1).3 1226484 . 1Рассмотрим формирование произвольного элемента У выходного вектора у.кТакт Е. В регистр операнда 3.1записывается входной отсчет ХкТакт Е+1. В модуле 1.1 выполняетсябазовая операция, в результате которой в первый регистр результата 6.1записывается произведение а Х , ав регистр операнда 3.1 поступает новый входной отсчет Хк+Такт 1+2. Произведение а Хк,кпереписывается во второй регистр результата 7.1, отсчет Х поступаетв регистр операнда 3.2, а новый входной отсчет Х записывается в регистрк+2операнда 3.1.Такт ;+3. В модуле 1.2 выполняетсябазовая операция, в результате которой сумма а , Х+ а ,Хзаписывается в первый регистр результата 6.2,а отсчет Х поступает в регистроперанда 3. 2. Кроме этого, новый входной отсчет Х записывается в регистркФ 3операнда 3.1,Такт 1 с+4. Сумма аХк + ак к 1 Хкм 1переписывается во второй регистр результата 7.2, отсчет Х поступаетв регистр операнда 3.3, отсчет Хк, -в регистр операнда 3.2,а новый входнойотсчет Х,записывается в регистр 3.1.Такт Е+5. В модуле 1.3 выполняется базовая операция, в результатезаписывается в регистр 6.3, а отсчетХ поступает в регистр операнда 3.3.к+3Крометого, отсчет Х, поступает врегистр операнда 3.2, а новый входной отсчет Х записывается в регистркФ 5операнда 3.1.Такт +2 Ь) . В модуле 1. (Ь) вы -поляется базовая операция, врезультате которой суммаа Х + а Х ++ а Х(1),к к к,км 1 кч к.к+И к+ эапи"ывается в регистр результата 6(Ь),а отсчет поступает в регистр операнда, 3. (Ь).Такт (К + 2 Ь - 2), Сумма (1) переписывается в регистр результата 7.(Ь),а отсчет Х,поступает в регистр операнда З.Ь. Такт (к + 2 Ь - 1). В модуле 1.Ь выполняется базовая операция, в результате которой окончательное значение отсчета у записывается в регистр 6,Ь. Такт (к + Ь) . Отсчет у перенис ык вается в регистр 7,Ь, откуда поступает на выход устройства.При выполнении операции умножения полностью заполненной матрицы А размером ИИ (И = Ь) на вектор Х согласно выражению й у=. а Х 1 с=01 Б 1 (2) 10устройство работает следующим образом.В исходном состоянии счетчик 12обнулен. Затем на вход блока управления 2 поступает сигнал "Полностью 15заполненная матрица" под воздействиЭем которого счетчик 12 начинает реагировать на поступающие на его счетныйвход тактовые импульсы, осуществляяих счет по модулю И. Содержимое счетчика 12 дешифрируется с помощью дешифратора 13, на выходе которого в течелние такта с номеромтаким, что- 1 шой И, вырабатывается уровеньлогической "1", передаваемый посредством триггеров управления 10.3 и11.) на вход разрешения записи буферных регистров 8,3 и управляющий входмультиплексоров 9,3. Таким образом,в течение такта с номером г таким,что г - 2 (3 - 1) .= 1 тпос И, содержимое регистра операнда 3.3 переписыва-ется в буферный регистр 8.1, прежнеесодержимое которого посредством мультиплексора 9.) передается в регистроперанда 3, (3.+ 1). В течение осталь ных тактов содержимое регистра операнда 3.3 передается непосредственнов регистр операнда 3. Ц + 1). Элементы Х вектора Х поступают напервый информационный вход устройст ва со скоростью одного отсчета натакт, т,е. Х записывается в регистроперанда 3.1 в такте с номером Р.Следовательно, отсчет Х сдвигается вкаждом такте на одну позицию в регист ре сдвига, образованном регистрами3,1,.3,23. (Р + 1), пока в тактес номером 2 Р + 1 не поступит в буферный регистр 8. (Р + 1), где хранитсяв течение Ь тактов, чтобы в такте с 50 номером 2 Р + И + 1 поступить в регистр3. (Р + 2). Затем отсчет Х сдвигаетГся в каждом такте на одну позицию врегистре сдвига, образованном регист-рами 3. (Р + 2), 3. (Р + 3)3 М.Элементы полностью заполненной матрицы А поступают на остальные информационные входы устройства следующим образом; если К 6 Р, то а поступаетна нторой информационный вход модуля(е - 1 с + 1) в такте с номером 1+2,(е) +1=21 - 1+1; если 1 с ) 1, то а,Е поступает на второй инк,Гформационньей вход модуля 1. (И - к + 5 + 1 + 1) в такте с номером1 + 2 (И - 1 + 1) + 1 = 2 И - 1.+ 1+Рассмотрим формирование проиэвольного элемента выходного вектора у,которое производится по следующейрасчетной Формуле:й;К 1 к -1 15Формирование члена у производит,ся в течение тактов 1 - : 1 + 2 (И)== 2 И - Е и осуществляется точно20таким же образом, как в случае ленточной матрицы А. Следовательно, нтакте с номером 2 И - Е значение узаписывается во второй регистр ре-.зультата 7. (И - к),Такт 2 И - к + 1. В модуле 1. (Ит К + 1) выполняется базовая опералция, в результате которой сумма у +к+ а , Х записывается в первый ре-.К,огис тр результата б . ( И - 1 с + 1 ) .л 30Такт 2 И - Е + 2. Сумма у, + а Хк К Опереписывается во второй регистр результата 7. (И - К + 1).Такт 2 И - М + 3. В модуле 1, (И - Е + 2) выполняется базовая операция, в результате которой сумма О + З 5+ а Х переписывается во второйК,1регистр результата 7. (И - К + 2).Такт 2 И - 1 + 2 (1: - 1)+1=1+2 И 1. В модуле 1.И выполняется базовая операция, в результате которой окончательное значение у записыва.кется в регистр б.И.Такт Е + 2 И. Окончательное эначение у переписывается в регистркрезультата 7,И, откуда поступает на выход устройстна.Предлагаемое изобретение позволяет уменьшить объем оборудования еери одновременном увели 1 ении производительности устройства.Уменьшение объема оборудования, 55 lнеобходимого для реализации устройства, выражается в том, что в случае полностью заполненной матрицы А раэмером ИК треб;емое количество МО- дулей в предлагаемом устройстве составляет величину И, что почти н 2 раза меньше, чем и прототипе. Увели.- чение производительности устройства Ьыражается н том, что входные данные поступают на его входы в каждом такте и с такой же частотой Формируютсярезультаты, в то время как н прототипе результаты Формируются в два разаменьшей частотой, Таким образом, предлагаемое устройство позволяет довести,коэффициент использования его обору-.дования до 100 Ж.Формула изобретенияУстройство для умножения матрицы на вектор содержащее Ь вычислительных модулей, причем первый информациОнный вход е-го вычислительного модуля (е = 2, 3, , Ь) соединен с первым информационным выходом (е)-го. нычиснителеного модуля первый инфор мационный вход первого вычислительного модуля является первым информациОнным входом устройства, а второй инФормационный вход 1-го вычислительного модуля (1=1,2,Ь) является, (+1)-ым информационным входом устройства, блок управления, вход которого является входом выбора режима вычислений устройства, каждый иэ вы" числительных модулей содержит регистр операнда, информационный вход которого является первым информационным входом модуля, умножитель, входы первого и второго сомножителей которого соединен с вторым информационным входом модуля и выходом регистра оцеранда соответственно, сумматор, входы первого и второго операндов которого соединены с выходом умножителя и третьим информационным входом модуля соответственно первый регистр результата, информационный вход которого соедиш.н с выходом сумматора, О т л ич а ю щ е е с я тем, что, с целью уменьшения объема оборудования при Одновременном увеличении производи-. гельности устройства, выход блока управления соединен с входом режимавычислений первого вычислительного моцуля, третий информационный вход и вход режима нычислений е-го вычислительного модуля соединены е первым информационным выходом и выходом признака режима вычислений (е)-го7 1226484, 8 модуля соответственно, причем каждый триггер управления, информационный вычислительный модуль содержит буфер- вход которого является входом режима ный регистр, информационный вход ко- вычислений модуля, второй триггер торого соединен с выходом регистра управления, информационный вход ко" операнда, мультиплексор, первый иторого соединен с выходом первого второй информационные входы которого триггера управления, а выход являет- соединены с выходом регистра.операн- ся выходом признака режима вычиследа и выходом буферного регистра, а ний вычислительного модулядуля, вход выход является первым информационным разрешения записи буферного регистра выходом модуля, второй регистр резуль- О и управляющий вход мультиплексора тата, информационный вход которого соединены с выходом второго триггера соединен с выходом йервого регистра управления, второй информационный результата, а выход является вторым выход последнего вычислительного моинформационным выходом модуля, первый дуля является выходом устройства.1226484 иг.3 фиг Составитель Д, Хан-МагомедоТехред Л,Олейник актор С.Лыжо рректор С.Ше каз 2136 сн 4 5 оектная, 4 о-полиграфическое предприятие, г. Ужгород,Производст 1 ИИПИ по д 13035 Тиражсудам изо 671 П твенного комитета СССР ретений и открытий Ж, Раушская наб