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

 

Изобретение относится к области вычислительной техники и позволяет сократить затраты оборудования и повысить скорость вычислений. Устройство содержит L вычислительных модулей и блок управления. На входе блока управления задается один из режимов вычисления: умножение на ленточную матрицу или на полностью заполненную матрицу. Входные данные пос тупают на информационные входы вычислительных модулей, в каждом такте и с такой же частотой формируются результаты на выходе первого вычислительного модуля, который является выходом устройства. 4 ил. «Л ю ISD О5 4; 00 4::

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК сЬЬ 4 G 06 F 15 31

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3804605/24-24 (22) 23.10.84 (46) 23.04.86. Бюл. И - 15 (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) А.B. Выжиковска, Р. Выжиковски (Р1.), N.С. Каневский и В.И. Лозинс.— . кий (53) 681,325(088.8) (56) 1 ° Заявка Японии У 52-22218, кл. G 06 F 7/38, опублик ° 1977.

2. Ис СаЬе. New algorithms and

architectures for VLSI GEC.-TonrnaI

of Science and Technof., 1982, v. 48, В 2, рр. 68-75.

„SU„„1226484 A (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦЫ НА ВЕКТОР (57) Изобретение относится к области вычислительной техники и позволяет сократить затраты оборудования и повысить скорость вычислений. Устройство содержит L вычислительных модулей и блок управления. На входе блока управления задается один из режимов вычисления: умножение на "ленточную" матрицу или на полностью saполненную матрицу. Входные данные поступают на информационные входы вычислительных модулей, в каждом такте и с такой же частотой формируются результаты на выходе,первого вычислительного модуля, который является выходом устройства. 4 ил.

50! 122648

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времени.

Цель изобретения — уменьшение объема оборудования при одновременном увеличении производительности устройства.

На фиг. 1 изображена структурная 10 схема устройства," на фиг. 2 — функциональная схема вычислительного модуля; на фиг. 3 и 4 — блок-схема алгоритма работы устройства при вычислении результата у в случае ленточной 15

К матрицы А.

Устройство содержит (фиг. 1) L вычислительных модулей 1.1, 1.2,..., 1.L блок управления 2. Вычислитель° ный модуль 1.j содержит (фиг. 2) ре- д» гистр 3.1 операнда, умножитель 4. 1, сумматор 5.j, первый и второй входы

-которого соединены соответственно с выходом умножителя 4.j и вторым информационным входом модуля 1.1; пер- 25 ,вый б.j и второй 7.j регистры резуль тата, буферный регистр 8.j, мультиплексор 9.j первый и второй триггеры

S управления 10.j и 11.j.

Блок управления 2 содержит счетчик . 12 по модулю Е, вход разрешения счета которого является входом блока управления 2, а выход соединен с входом дешифратора 13 (представляющего собой, например, комбинационную схему, опи- сываемую переключательной функцией у = Х„х,...х,,где $= ) Ход,т. I ), выход которого является выходом блока управления 2. Следует подчеркнуть, что все регистры и триггеры устройст40 ва имеют вход синхронизации, а счетчик 12 — счетный вход (входы не показаны), которые соединены с выходом генератора тактовых импульсов (не показан).

При выполнении операции умножения ленточной матрицы А на вектор Х согласно выражению

L" "1 ь = а Х, К = 0,1,.„., N-1 е= (L — ширина ленты матрицы А размером

Н И+Е-1) устройство работает следующим образом.

Во время этой операции под воздействием сигнала "Ленточная матрица", поступающего на вход блока управления 2, счетчик 12 по модулю L сохраняет свое исходное нулевое состояние, 4 2 в результате чего дешифратор 13 поддерживает на выходе блока управления

2 уровень логического "О", передаваемый посредством триггеров управления

10.j и 11.j на управляющий вход, мультиплексоров 9.j. Элементы X„ вход" ного вектора X (n0,.1,..., N+L-1} поступают на первый информационный вход устройства со скоростью одного отсчета на такт, т.е. Х„ записывается в регистр операнда 3.1 в такте с номером и. Элементы ленточной матрицы

А поступают на информационные входы устройства следующим образом: элемент a„ » поступает на второй информационный вход модуля 1. ((+1) в такте с .номером k+2f+1.

Для того, чтобы сделать более наглядным дальнейшее описание работы устройства, определим базовую операцию, причем под базовой операцией будем понимать повторяющуюся совокупность действий, выполняемых вычислительным модулем. Базовая операция выполняется в течение некоторого такта с номером r в вычислительном модуле 1.» следующим образом. В исходный момент времени в первом регистре результата б.j и втором регистре результата 7.j хранятся соответственно частичные результаты Ъ. и b,, a в (1» и регистре операнда хранится операнд

Х, который затем поступает на вход второго сомножителя умножителя 4.j, на вход первого сомножителя которого с второго информационного входа модуля 1.j поступает операнд а . Затеи умножитель 4.j формирует произведение а Х... которое поступает на вход

t первого операнда сумматора 5.j на вход второго операнда которого с третьего информационного входа моду" ля 1.j поступает частичный результат ()

b. (в случае модуля 1.1 всегда

Ь," = О). Сумматор 5.) формирует сумJ - t (2) му а Х, + b,„, которая с приходом тактового импульса записывается в первый регистр результата б.j, прежнее содержимое которого переписывается во второй регистр результата 7.j.

Поскольку на управляющий вход мультиплексора 9.j постоянно подается уровень логического "0", то под воздействием тактового импульса осуществляется также перезапись содержимого регистра операнда 3. (j-1) в регистр операнда 3 j (или просто запись нового входного отсчета в регистр

3,1 в случае модуля 1.1). з 1226484 . 4

Рассмотрим формирование произвольного элемента У выходного вектора у. к

Такт k. В регистр операнда 3.1 записывается входной отсчет Х к

Такт k+1. В модуле 1.1 выполняется базовая операция, в результате которой в первый регистр результата 6.1 записывается.произведение а Х, а

K,к к в регистр операнда 3.1 поступает новый входной стсчет Х к+1

Такт k+2. Произведение а Х„ к,к переписывается во второй регистр результата 7.1, отсчет Х„ поступает в регистр операнда 3.2, а новый входной отсчет Х записывается в регистр к+ операнда 3.1.

Такт k+3. В модуле 1.2 выполняется базовая операция, в результате которой сумма а, Х „ + а„,Х„„записывается в первый регистр результата 6.2, а отсчет Х„„ поступает в регистр операнда 3. 2. Кроме этого, новый входной отсчет Х записывается в регистр к з операнда 3.1.

Такт k+4. Сумма a„ „ X„ + а„ „X„„

I переписывается во второй регистр результата 7.2, отсчет Х„„ поступает в регистр операнда 3.3, отсчет Х„,,— в регистр операнда 3.2,а новый входной отсчет Хк,„записывается в регистр 3.1.

Такт k+5. В модуле 1.3 выполняется базовая операция, в результате записывается в регистр 6.3, а отсчет

Х поступает в регистр операнда 3.3.

K+/

Кроме того, отсчет Х„ „ поступает в регистр операнда 3.2, а новый входной отсчет Х записывается в регистр к+ 5 операнда 3.1.

° ° ° °

Такт (k+2L-3) .В модуле 1. (L-1) вы— поляется базовая операция, в результате которой сумма а Х + а Х + .. ° + à X„„ (i)

Q,ê к K,ê» кч K.к+Ь к+ -2 эапи "ывается в регистр результата

6(L-1),а отсчет поступает в регистр операнда 3. (L-1).

Такт (k + 2L — 2). Сумма (1) пере1исывается в регистр результата 7.(L-1),а отсчет Х„„,поступает в регистр операнда 3.Ь.

Такт (k + 2Ь вЂ” 1) . В модуле 1.Ь выполняется базовая операция, в результате которой окончательное значение отсчета у записывается в регистр

6.L.

Такт (к + Ь) . Отсчет у перенис ыК вается в регистр 7.Ь, откуда поступает на выход устройства.

При выполнении операции умножения полностью заполненной матрицы А размером И И (И = Ь) на вектор Х согласно выражению

N-1 у =",а Х, k = 0,1,..., N-1 (2)

10 устройство работает следующим образом.

В исходном состоянии счетчик 12 обнулен. Затем на вход блока управления 2 поступает сигнал "Полностью

15 заполненная матрица" под воздействиЭ ем которого счетчик 12 начинает реагировать на поступающие на его счетный вход тактовые импульсы, осуществляя их счет по модулю N. Содержимое счет20 чика 12 дешифрируется с помощью дешифратора 13, на выходе которого в течеЛ ние такта с номером таким, что — 1 mod N, вырабатывается уровень логической "1", передаваемый посред25 ством триггеров управления 10.j u

11.j на вход разрешения записи буферных регистров 8.j и управляющий вход мультиплексоров 9.j. Таким образом, в течение такта с номером r таким, что r — 2 (j — 1) = 1 mod N содержимое регистра операнда З.j переписыва- ется в буферный регистр 8.j прежнее содержимое которого посредством мультиплексора 9.j передается в регистр операнда 3. (j.+ 1). В течение осталь35 ных тактов содержимое регистра операнда З.j передается непосредственно в регистр операнда 3. (j + 1). Элементы Х вектора Х поступают на первый информационный вход устройст40 ва со скоростью одного отсчета на такт, т.е ° Х записывается в регистр операнда 3.1 в такте с номером I.Ñëåдовательно, отсчет Х сдвигается в каждом такте на одну позицию в регист45 ре сдвига, образованном регистрами

3.1,.3.2,...,3. (I + 1), пока в такте с номером 2Р + 1 не поступит в буферный регистр 8. (Т + 1), где хранится в течение N тактов, чтобы в такте с

50 номером 2I + N + 1 поступить в регистр

3. (I + 2). Затем отсчет Х сдвигаетP

1ся в каждом такте на одну позицию в регистре сдвига, образованном регист- рами 3. (Х + 2), 3. (I + 3),...,3 N.

Элементы полностью заполненной матрицы А поступают на остальные информационные входы устройства следующим образом: если К 7, то а е поступает

1226484 на нторой информационный вход модуля

1. (2 — k + 1) в такте с номером

k+ 2,(Х -k) + 1 =27 — k+ 1; если

k > 1, то а . е поступает на второй инк,Г формационный вход модуля 1. (N — k +

+ 1 + 1) в такте с номером

k+2 (И-k+ Х) + 1 =2N — k.+I +1.

Рассмотрим формирование проиэволь- 10 ного элемента выходного вектора у, которое производится по следующей расчетной формуле:

N.-K.f К-1 15

Формирование члена у производит«, ся в течение тактов k —: Pk + 2 (N-k)j=

= 2N — Е и осуществляется точно

20 таким же образом, как в случае ленточной матрицы А. Следовательно, н такте с номером 2N — k значение у записывается во второй регистр ре-. зультата 7. (N — k) .

Такт 2N — k + 1. В модуле 1. (Mт k + 1) выполняется базовая операл ция, в результате которой сумма у + к

+ а, Х записывается в первый ре-K,o гистр результата 6. (N — 1с + 1). л 30

Такт 2N — k + . Сумма у, + а Х к К,о а переписывается во второй регистр результата 7. (N — k + 1).

Такт 2N — k + 3. В модуле 1, {N+ 2) выполняется базовая операция, в результате которой сумма 9„ +

+а Х + а Х записывается в пер- о ь к выи регистр результата 6. -(N — k + 3).

Такт 2N — k + 4, Сумма у + а Х„+

+ а„ Х„ переписывается во второй к,1 регистр результата 7. (N — k + 2).

Такт 2N — k + 2 (1с — 1)+1=k+2N1. В модуле 1.N выполняется базовая операция, в результате которой окончательное значение у записыва--к ется в регистр 6.N.

Такт k + 2N. Окончательное эначение у переписывается в регистр к результата 7.N, откуда поступает на выход устройс тн а.

Предлагаемое изобретение позволяет уменьшить объем оборудования при одновременном увеличении производительности устройства.

Уменьшение объема оборудования, / необходимого для реализации устройства, выражается в том, что в случае полностью заполненной матрицы A раэмером И«К треб;емое количество МОдулей в предлагаемом устройстве составляет величину N что почти н 2 раза меньше, чем и прототипе. Увели-чение производительности устройства выражается н том, что входные данные / поступают на его входы в каждом такте и с такой же частотой формируются результаты, в то время как н прототипе результаты формируются в два раза меньшей частотой. Таким образом, пред лагаемое устройство позволяет довести ,коэффициент использования его обору-. дования до 100 Ж.

Формула изобретения

Устройство для умножения матрицы на вектор„ содержащее T. вычислительных модулей, причем первый информациОнный вход i-го вычислительного модуля {i = 2, 3,..., ?.) соединен с первым информационным выходом (r-1)-го. нь чиснителенОГО модуля> первый инфор мационный вход первого вычислительноГО модуля является первым информациОнным входом устройства, а второй информационный вход 1-го вычислительноГО модуля {j=1,2...,1.) Является, (+,)-ым информационным входом устройства, блок управления, вход которого является входом выбора режима вычислений устройства, каждый нэ вы" числительных модулей содержит регистр операнда, информационный вход котороГо является первым информационным входом модуля, умножитель, входы первого и второго сомножителей которого соединен с вторым информационным входом модуля и выходом регистра оцеранда соответственно, сумматор, входы первого и второго операндов которого соединены с выходом умножителя и третьим информационным входом модуля соответственно,, первый регистр результата, информационный вход которого ,"Оединен с выходом сумматора, О т л ич а ю щ е е с я тем, что, с целью уменьшения объема оборудования при

Одновременном увеличении производи-.

-гельности устройства, выход блока управления соединен с входом режима вычислений первого вычислительного моцуля, третий информационный вход и вход режима нычислений ь-гG вычислительного модуля соединены е первым информационным выходом и выходом признака режима вычислений (i-1)-rn

7 1226484 . 8 модуля соответственно, причем каждый триггер управления, информационный вычислительный модуль содержит буфер- вход которого является входом режима ный регистр, информационный вход ко- вычислений модуля, второй триггер торого соединен с выходом регистра управления, информационный вход ко" операнда, мультиплексор, первый и торого соединен с выходом первого второй информационные входы которого триггера управления, а выход являет соединены с выходом регистра.операн- ся выходом признака режима вычиследа и выходом буферного регистра, а ний вычислительного модуля дуля, вход выход является первым информационным разрешения записи буферного регистра выходом модуля, второй регистр резуль- 0 и управляющий вход мультиплексора тата, информационный вход которого соединены с выходом второго триггера соединен с выходом йервого регистра управления, второй информационный результата, а выход является вторым выход последнего вычислительного моинформационным выходом модуля, первый дуля является выходом устройства.

1226484

Фиг.3

Фиг1

Составитель Д, Хан-Магомедов

Техред Л.Олейник Корректор С.Шекмар

Редактор С.Лыкова

Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушс!кая наб., д. 4/5

Заказ 2136/50

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4