Устройство умножения матрицы на вектор Советский патент 1986 года по МПК G06F17/16 

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

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

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

Устройство содержит (фиг, 1) L

вычислительных модулей 1,1, 1.2

1.L, блок управления 2. Вычислитель- ный модуль 1.j содержит (фиг. 2) ре- 20 гистр 3.J операнда, умножитель 4.j, сумматор 5.J, первый и второй входы которого соединены соответственно с выходом умножителя 4.j и вторым информационным входом модуля 1.J; пер- 25 ,вый 6.J и второй 7.J регистры резуль- |тата, буферный регистр 8.j, мультиплексор 9.J, первьй и второй триггеры управления tO.j и ll.j.

Блок управления 2 содержит счетчик

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

У .il- . S 1 ) , выход которого является выходом блока управления 2. Следует подчеркнуть, что все регистры и триггеры устройства имеют вход синхронизации, а счетчик 12 - счетный вход (входы не показаны) , которые соединень с выходом генератора тактовых импульсов (не показан).

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

У Zrv . 0,1,..,., N-1

(L - ширина ленты матрицы А размером N N+L-1) устройство работает следующим образом.

Во время этой операции под воздействием сигнала Ленточная матрица, поступающего на вход блока управления 2, счетчик 12 по модулю L сохраняет свое исходное нулевое состояние.

в результате чего дешифратор 13 поддерживает на выходе блока управления 2 уровень логического О, передаваемый посредством триггеров управления 10.J и 11.J на управляющий вход, мультиплексоров 9.J. Элементы Х входного вектора X (,.1,..., N+L-1) поступают на первый информационный вход устройства со скоростью одного отсчета на такт, т.е. Х записывается в регистр операнда 3.1 в такте с номером п. Элементы ленточной матрицы А поступают на информационные входы устройства следующим образом: элемент а f поступает на второй информационный вход модуля 1. (1+1) в такте с номером k+2f+1.

Для того, чтобы сделать -более наглядным дальнейшее описание работы устройства, определим базовую операцию, причем под базовой операцией будем понимать повторяющуюся совокупность действий, выполняемых вычисли- -тельным модулем. Базовая операция выполняется в течение некоторого такта с номером г в вычислительном модуле 1.J следуювчим образом. В исходный момент времени в первом регистре результата 6.J и втором регистре результата 7.J хранятся соответственно частичные результаты Ь и Ь , а в регистре операнда хранится операнд Х, который затем поступает на вход второго сомножителя умножителя 4.J, на вход первого сомножителя которого с второго информационного входа модуля 1.J поступает операнд ад Затем умножитель 4.j формирует произведение а. Х,, которое поступает на вход первого операнда сумматора 5.j, на вход второго операнда которого с третьего информационного входа модуля 1.J поступает частичный результат b f (в случае модуля 1.1 всегда b. 0). Сумматор 5.J формирует сумму + Ь , которая с приходом тактового импульса записывается в первый регистр результата 6.j, прежнее содержимое которого переписывается во второй регистр результата 7.J. Поскольку на управляющий вход мультиплексора 9.J постоянно подается уровень логического О, то под воздействием тактового импульса осуществляется также перезапись содержимого регистра операнда 3. (j-1) в регистр операнда 3.J (или просто запись нового входного отсчета в регистр 3.1 в случае модуля 1.1).

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

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

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

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

Такт k+3. В модуле 1.2 выполняется базовая операция, в результате которой сумма а , Х. + а ..„Х записываетК , Кri Ч

ся в первый регистр результата 6.2, а отсчет X jпоступает в регистр операнда 3.2. Кроме этого,новый входной отсчет X записывается в регистр операнда 3.1.

Такт k+4. Сумма а Х + переписывается во второй регистр результата 7.2, отсчет Х, поступает в регистр операнда 3.3, отсчет Х,,,- в регистр операнда 3.2, а новьй входной отсчет Х цЗапксывается в регистр 3.1.

Такт k+5. В модуле 1.3 выполняется базовая операция, в результате которой сумма ,,- записывается в регистр 6.3, а отсчет Х поступает в регистр операнда 3.3. Кроме того, отсчет Х|. поступает в регистр операнда 3.2, а новый входной отсчет X записывается в регистр операнда 3.1.

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

а X + а X +

к. К,К+1

к.,..,(Г)

записывается в регистр резз льтата 61L-1) ,а отсчет поступает в регистр

рперанда. 3. (L-1) .

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

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

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

При выполнении операции умножения полностью заполненной матрицы А размером NJ N (N L) на вектор X согласно выражению

N-1

0

5

Х,

1

k 0,1,..., N-1 (2)

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

В исходном состоянии счетчик 12 обнулен. Затем на вход блока управления 2 поступает сигнал Полностью заполненная матрица, под воздействием которого счетчик 12 начинает реагировать на поступающие на его счетный вход тактовые импульсы, осуществляя их счет по модулю N. Содержимое счетчика 12 дешифрируется с помощью дешифратора 13, на выходе которого в течение такта с номером L таким, что L 1 mod N, вырабатывается уровень логической 1, передаваемый посредством триггеров управления lO.j и 11.j на вход разрешения записи буферных регистров 8.J и управляющий вход мультиплексоров 9.J. Таким образом, в течение такта с номером г таким, что г - 2 (J - 1) 1 mod N, содержи мое регистра операнда 3.J переписывается в буферный регистр 8.J, прежнее содержимое которого посредством мультиплексора 9.J передается в регистр операнда 3. (j.+ 1). В течение осталь5 ных тактов содержимое регистра операнда 3.J передается непосредственно в регистр операнда 3. (j + 1). Элементы X. вектора X поступают на первый информационный вход устройст0 ва со скоростью одного отсчета на такт, т.е. Х, записывается в регистр операнда 3.1 в такте с номером I.Следовательно, отсчет Xj сдвигается в каждом такте на одну позицию в регист5 ре сдвига, образованном регистрами 3.1,.3.2,...,3. (I + 1), пока в такте с номером 21 + 1 не поступит в буферный регистр 8. (I + 1), где хранится в течение N тактов, чтобы в такте с

0 номером 21 + N + 1 поступить в регистр 3. (1+2). Затем отсчет Х- сдвигает- jCH в каждом такте на одну позицию в регистре сдвига, образованном регист- рами 3. (I + 2), 3. (I + 3),...,3:Ы.

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

1,

5

на второй информационный вход модуля 1. (I-k+1)B такте с номером k+2.(T-k)+1 2r-k+1; если k, то а g поступает на второй информационный вход модуля 1, (N - k + + 1 + 1) в такте с номером

k + 2 (N - k + I) + 1 2N -k.+ ft К

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

12264

.

N.-K-f

а X, +

)1,е+к +«

е-о

производитФормирование члена У - ся в течение тактов k f С + 2(N-k)j 2N - k и осуществляется точно таким же o6pa30Mj как в случае ленточной матрицы А. Следовательно, в такте с номером 2N - k значение у записьюается во второй регистр результата 7. (N - k),

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

Такт 2N - k +

. 0

1,0 °

переписывается во второй регистр результата 7. (N - k + 1).

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

ВЫЙ регистр результата 6, /-(N - k+ 2)

Такт 2N - k + 4, Сумма у +

. + а Х переписывается во второй

регистр результата 7. (N - k + 2),

ее

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

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

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

Уменьшение объема оборудования, необходимого для реализации устройства, вьфажается в том, что в случае полностью заполненной матрицы А раз

|Q

6484 6

мером треб%,емое количество модулей, в предлагаемом устройстве составляет величину N, что почти в 2 раза меньше, чем в прототипе. Увели-- 5. -гение производительности устройства . выражается в том, что входные данные поступают на его входы в каждом такте к с такой же частотой формируются

результаты, в то время как в прототипе результаты формируются в два раза меньшей частотой. Таким образом, предлагаемое устройство позволяет довести коэффициент использования его обору-г дования до 100 %.

0

5

5

5

0

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

Устройство для умножения матрицы на вектор, содержащее L вычислительных модулей, причем первый информационный вход i-ro вычислительного модуля Ci 2, 3,..., L) соединен с первым информационным выходом (i-l)-ro. вычислительного модуля, первый инфор- мадионньй вход первого вычислительного модули является первым информационным входом устройства, . а второй информационный вход j-ro вычислительного модуля (,2...,L) является. 0 ()-.ь1м информационным входом устройства, блок управления, вход которого является входом выбора режима вычислений устройства, каждый из вычислительных модулей содержит регистр операнда, информационный вход которого является первым информационным входом модуля, умножитель, входы первого и второго сомножителей которого соединен с вторьнм информационным входом модуля и выходом регистра операнда соответственно, сумматор входы первого и второго -операндов которого соединены с выходом умножителя и третьим информационным входом модуля соответственно,, первый регистр результата, информационный вход которого соединен с выходом сумматора, о т л и- ч а ю Б), е е с я тем, что, с целью уменьшения объема оборудования при одновременном увеличении производи-, -тельности устройства, выход блока управления соединен с входом режима .вычислений первого вычислительного модуля, третий информационный )зход и вход режима вычислений i-ro. вычислительного модуля соединены е первым информационным выходом и выходом признака режима вычислений (i-1)-ro

Модуля соответственно, причем каждый вычислительный модуль содержит буферный регистр, информационный вход которого соединен с выходом регистра операнда, мультиплексор, первый и второй информационные входы которого соединены с выходом регистра.операнда и выходом буферного регистра, а выход является первым информационным выходом модуля, второй регистр результата, информационный вход которого соединен с выходом первого регистра результата, а выход является вторым информационным выходом модуля, первый

I Д-. Д

-- -)

I.

12

/J

8

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

и управляющий вход мультиплексора соединены с выходом второго Триггера управления, второй информационный выход последнего вычислительного модуля является выходом устройства.

W

12

и

.1

8.J

If

J

/

7;

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

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

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

Заказ 2136/50

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушс кая наб., д, 4/5

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

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