Устройство для матричных операций Советский патент 1988 года по МПК G06F17/16 

4

ю

Изобретение относится к вычислительной технике и может быть пользовано в специализированных машинах и устройствах цифровой обработки сигналов для перемножения ленточной (пхп)матрицы с шириной ленты и)а на плотную (пхп)-матрицу. Цель изобретения - упрощение устройства - достигается тем, что устройство содержит ленту однотипных операционных блоков, при этом операционный блок содержит пять регистров, сумматор, умножитель, три триггера, элемент И и элемент НЕ. Устройство также реализует матричные операции С + АЪ и АВ ,, АВ, ABj и т.д. Особенностями работы устройства являются параллельно-поточная организаций вычислений, синхронность исполнения и коммутации различтсых частей Щ алгоритма перемножения матриц. 2 ил. (Л

ГчЭ

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

Цель изобретения - упрощение устройства.

На фиг.1 представлена структурная схема устройства для перемножения матриц для случаев п 5, и)с 4, Рц 3 и q 2; на фиг.2 - функциональная схема операционного блока.

Устройство для перемножения матриц (фиг.1) содержит первую группу информационных входов Н (i 1.J, п) , вторую грзшпу информационных входов 2Ц (. ; j ), третью группу информационных входов 3j (j 1, п), синхровход 4, операционные блоки 5ij (i,j 1, n) и выходы 6i (i 1 , п)

Операционный блок 5 (фиг.21 содержит первый- 7, второй 8, третий 9 входы, регистры 10 - 14, триггеры 15- 17, умножитель 1б, сумматор 19, элемент НЕ 21, синхровход 22, первой выход 23, второй выход 24, третий выход 25.

В основу работы устройства положен алгоритм умножения (п х п)-ленточной матрицы А (a-ij ) . с шириной ленты At РО + Яд на плотную (пхп)- матрицу В (bij ), определяющий ре- зультирующую (п X п)-матрицу С (c-jj на основании следующих рекурентных

U(i)) соотношений для 0:

JO

с(к-1)

+

(К)х i jr(K); j,K l,n

) ,

ij j ; i,j i,n

где c( (i) макс(0,1 - PC,); J.(K) « макс(1, К - q + 1); (K) мин(п. Pa + K- l)j E(i) мин(п, i + + q - 1); K, T7n.

Рассмотрим работу операционного блока 5. Регистры 10 и 14, построенные на двухтактных триггерах, регистры 11 - 13, построенные на однотакт- ных триггерах, и двухтактные триггеры 15 - 17 устанавливаются в начальное состояние. На входы 7 и 9 подаются с дополнительным единичным разря

0

5 0

5

0

5

0

дом соответственно элементы Cij , I и btj.l, а на вход 8 - элемент a{j . По переднему фронту тактового импульса элемент a-ij записывается в регистры 11 и 12. Запись элемента atj в регистр 12 осуществляется с выхода регистра 11 при наличии единичного сигнала на входе разрешения записи регистра 12, который подается с инверсного выхода триггера 16. По заднему фронту тактового импульса в регистры 10 и 14 записьгааются соответственно элементы C-ij и Ь/у , в регистр 13 за- письтается элемент aij , триггеры 15- 17 устанавливаются в единичное состояние. Триггер 16 устанавливается в единичное состояние единичным сигналом, который подается на его информационный вход, с выхода элемента И 20, При этом запись в регистр 12 запрещается, так как на инверсном выходе триггера 16 будет нулевой сигнал. На выходе умножителя 18 формируется значение at j bt/ , а на выходе сумматора 19 - значение Ci/ + aij Ы/ . Для записи в регистр 12 нового значения элемента aij необходимо на (т+1)-е разряды входов 7 и 9 подать нулевые сигналы, по заданному фронту тактового импульса триггер 16 устанавливается в начальное coctoяниe и при этом разрешается запись в регистр 12,

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

На первые информационные входы 1| подаются по тактам начальные значения

ь . .Qy , 1,. на вторые 2-ij и третьи 3t

входы подаются соответственно злемен Ф .ft)

ты a-ii и Ь

1, где t - номер такlij и

та, aij - элементы ленточной (п кп)- матрицы А, btj - элементы плотной (п кп)-матрицы. На входы Ч и Зу одновременно с элементами Cv/ и ЬЦ подаются дополнительные единичные разряды (фиг.1).

На нулевом такте на входы 1,2 и 3|( подаются соответственно элементы , 1 ; а и Ь° , 1 . На выходе сумматора 19 в операционном блоке 5

,.CoJ

формируется значение

(С)

/(Ч

+ а Ь,

DI/I .

На первом такте на входы 1 и 1 подаются соответственно значения

-1 -) , 1 и Cjx, , 1, на входы 2 , 2, и

2-12 соответственно элементы а , .

а 4 и , на входы 3 и 3 - соот-fветственно элементы Ь , 1 и Ьм , I.

В операционном блоке 5 элемент aj записьшается в регистр 13, на выходе сумматора 19 формируется значение

ГО (oj С;ц. С + , . . В операционном

блоке в регистр 10 эаписьшается значение С , в регистр 12 - элемент , в регистр 14 - элемент Ьг , на выходе сумматора 19 формируется значение С 0, + Ь„ , которое

подается на.выход 6. В операционном блоке 521 в.регистр 10 записьшается значение С , в регистр 12 - элемент aj в регистр 14 - элемент Ь , на выходе сумматора 19 формируется зна-

() чение Cj ti г (Ч1

На втором такте на входы Л , 1 к Ij, подаются соответственно значения

с4 , и Cj , на. входы 2 , 2 , 2 и 2j3 - соответственно элементы а , а J , agj и а , на входы 3, и 3j - соотв.етственно элементы и

Z

b.j В операционном блоке 5 форми-

. ft) Со) руется значение С + /t-i N5

в регистр 13 записьгоается элемент ah

В операционном блоке 5л формируется

ft) (1) значение С. + а. bj. , которое

подается на выход 6, в регистр 13 записьшается элемент ajj. В операционном блоке 544 формируется значение 1) Со)

Cjj м 4Z ® регистр 13 записьшается 31лемент . В операцион- I.

.ном блоке 52f в регистр 12 записьша-

ется элемент а-, , в регистр 10 - зна (/I) ,

чение Су , в регистр 14 - элементb

на выходе сумматора 19 формируется

М М значение Cj . С, + . . В опера-

цнонном блоке 5j4 в регистр 12 записывается элемент а| , в регистр 10 г, значение , в регистр 14 - элемент

г

Ь , на выходе сумматора 19 формнру-

От) (о) ется значение Cj Cj + , . На

последующих тактах устройство работа

7

ет аналогичным образом. Особенностью работы устройства является то,что элемент aij записьшается и хранится в регистре 12 операци9нного блока 5i y . Сформированные значения Cfj результирующей (п Дс п)-матрицы С () вьща- ются на выходе 6 устройства, где t - номер такта Гфиг.1 ),

Таким образом, если значения элементов С на входе 1 подаются нулевыми, то устройство реализует матричную операцию АВ, если С О - устрой- ство реализует матричную операцию С + АВ.

Кроме того, так как элементы ленточной матрицы А постоянно хранятся в регистрах 2 ПЭ Sjy , то устройство дополнительно выполняет перемножение цепочки матриц АВ, АВ, АВ и т.д.

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

Устройство для матричных операций, содержащее ленточную матрицу из (n-P)(n-P+l)/2-(n-q)(n-q-H)y2 операционных блоков, где п - размерность квадратных матриц, Р и q - количество элементов соответственно первого столбца к первой строки ленточной матрицы, причем J-й информационный вход первой группы устройства подключен к первому входу (i,1)-го операционно- го блока, (1 ), второй вход которого подключен к i-му информационному входу второй группы устройства (i I, Р), второй вход ij-ro операционного блока подключен к j-му информационному входу второй группы устройства, (J 2, q), третий вход ij-ro операционного блока подключен к j-му информационному входу третьей группы устройства, (J 1, , синхровход устройства подключен к синхровходам операционных блоков, отличающее с я тем, что, с целью упрощения, первый вход (i, i - Р + 1)-го операционного блока подключен к i-му информационному входу первой группы устройства, (i ), первый выход iJTp операционного блока подключен к первому входу (i,j + 1)-го операционного блока ( j 1 ; п- l ; J -. q + + j), третий вход (j Ч .1 i j)ro операционного блока подключен к j-му информационному входу

третьей группы устройства, j q+i , п) , -второй выход операционного блока подключен к второму входу (i+1, j + OjIjTO one рационного блока, (i,j 1, n-1; j - j + P) третий 5 выход ij-го операционного блока подключен к третьему входу (з + Г, j)-ro

операционного блока, (i 1, 3 I, п; j -.q i.j + Р-2), первый выход (j - q + 1 j)ro операционного блока подключен к (j - q 1)-му выходу устройства, (j Пи), первый выход (п, п)-го операционного блока подключен к п-му выходу устройства.

фиг. I