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

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

Целью изобретения является повышение быстродействия устройства.

На фиг.1 представлена структурная схема устройства для умножения матриц; на фиг.2 - структурная схема устройства для , , , где п - размерность перемножаемых матриц, р и q соответственно число ненулевых элементов первой строки и первого столбца матрицы-множителя; на фиг.З - организация входного потока элементов n x(p+q-1) матрицы В (В получена из исходной ленточной матрицы В путем дополнения ее нулями, описанным на фиг.З способом. Аналитически В задается следующим образом: bij ,i при ,p; ,n+j- р и ,p+q-1, i)-p+l,n, а в остальных случаях bij равно 0); на фиг.4 - пример схемы вычислительного модуля.

Устройство для умножения матриц (фиг,1) содержит первый информационный вход 1, второй информационный вход 2, группу информационных входов 3, синхров- ход4, вычислительные модули 51 ,p+q-1 и выход 6.

Вычислительный модуль 5 (фиг.4) содержит первый информационный вход 7, второй информационный вход 8, третий информационный вход 9, синхровход 10, регистры 11-13, умножитель 14, сумматор 15, узел 16 задержки, регистры узла задержки 171 И,п-2, элемент И 18, первый информаО

J о о

ционный выход 19 и второй информационный выход 20.

В осноау работы устройства положен алгоритм перемножения плотной (пхп)-мат- рицы А на ленточную матрицу В, основанный на рекуррентных соотношениях:

С|)

сц

,(«)

-0, ai

:k) ,,,(H

макс{0, i-q}, l.j 1,n;

CiJ-CIjA

+ aikbkj, k aj-n.n, I.JrJ n; ,/ мин{п, j+p-1}, i,j 1,n

Вычислительный модуль работает следующим образом.

На i-м такте элементы матрицы а,Ь и с подаются соответственно на входы 7, 9 и 8 и записываются соответственно в регистры 11, 13 и 12 (элемент В записывается в регистр 13 при подаче на вход 9 единичного разряда, который открывает элемент И 18 и разрешает запись в регистр 13). При этом на выходе умножителя 14 формируется значение п Ь, на выходе сумматора 15 - значение (с + а Ь), которое задерживается узлом 16 задержки на (п-2) тактов и выдается на выход 20. Элемент а задерживается на один такт регистром 11 и выдается на выход 19.

Организация входного и выходного потоков элементов плотных (n x п)-матриц А и С показана на фиг.1, а ленто«ной матрицы В на фиг.З. Элементы aik, bkj и подаются в моменты времени:

ta, + -n- p+(n-lXq-1)+1,

(n-1)j + (p+q-2Xn-1),

i + flj - П

На выходе 6 устройства формируются

i-clj fl tcij i + nj + (n-lXp+q-2)- 1

элементы GIJ cljlf J/ в моменты времени

При описании работы устройства в обозначении а® - индекс I в скобках указывает номер рекуррентного шага, а в обозначении а индекс I без,скобок указывает номер такта работы устройства.

Рассмотрим работу устройства для перемножения плотной (п х п)-матрицы А на ленточную матрицу В (, , )(фиг.2).

Состояние регистров 11-13 и 17 и формируемое значение на выходе сумматора 15 операционных блоков устройства приведены в таблице.

Загрузка элементов aik в вычислительный модуль 5 осуществляется с второго по семнадцатый такты, загрузка элементов - с первого по шестнадцатый такты. В соответствии с организацией подачи элементов матрицы В (ФигЗ), каждый элемент bij или нулевое значение подаются на соответствующий вход 3i и вместе с дополнительным (т+1)-м единичным разрядом, записываются в регистр вычислительного модуля 5 и хранятся в нем п тактов. Элемент

см( си + амЬп формируется в вычислительном модулу 5з на четвертом такте, элемент cir cir ai2 bai - в вычислительном модуле 52 на седьмом такте, элемент сц ™

cir + ai3 Ьз1 - в вычислительном модуле 5i на десятом такте и выдается на выход 6 устройства на двенадцатом такте. Аналогичным образом формируются остальные элементы С| результирующей матрицы С,

которые выдаются на выход 6 устройства с двенадцатого по двадцать седьмой такты в соответствии с приведенной таблицей.

Время перемножения плотной (пхп)- матрицы на ленточную матрицу равно

n(n+p+q-1)-p-q.

Период ввода элементов матриц очередной задачи перемножения равен п тактов,

Если на вход 2 в предлагаемом устройстве подавать элементы CljJ Ј 0, то устройство реализует матричную операцию С +АВ. Кроме того, предлагаемое устройство может выполнить перемножение ленточной матрицы А на плотную(п х п)-матрицу В, где

ленточная матрица А содержит в переем столбце q элементов, а в первой строке - р элементов. При этом необходимо элементы транспонированной матрицы Вт аналогичным образом подавать на вход 1, а

элементы транспонированной ленточной матрицы Ат - на входы 3i и на выходе 6 устройства формируются элементы транспонированной результирующей матрицы Ст.

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

Устройство для умножения матриц, содержащее вычислительных модулей,, (р и q - соответственно число ненулевых элементов первой строки и первого столбца

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

вычислительных модулей, первый информационный выход и второй информационный вход 1-го вычислительного модуля (,p+q-2) подключены соответственно к первому информационному входу и второму информационному выходу (i+1)-ro вычислительного

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

вход k-ro вычислительного модуля (,p+q- 1) является k-м входом группы информационных входов устройства, причем каждый вычислительный модуль выполнен с возможностью реализации функции:

Эвых Эвх

Свых . Свх + Эвх Ьв

V.

ьвых - Свх авх DBX а , гдеавх.Свх HdBx -значениясоответственно на первом, втором и третьем информационных входах вычислительного модуля на 1-м такте;

авых - значение на первом информационном выходе вычислительного модуля на (1+1}-м такте:

Свых+п - значение на втором информационном выходе вычислительного модуля на (Кп-1)-м такте;

d - значение (m+1)-ro разряда Ьвх1:

п - размерность перемножаемых матриц;

m - разрядность операндов.

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (пхп)-матрицы на ленточную матрицу. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство содержит (р + q -1) вычислительных модулей, где р и q соответственно количество элементов в первом столбце и в первой строке ленточной матрицы. Элементы матрицы-множимого поступают последовательно по столбцам на первый информационный вход устройства, элементы ленточной матрицы-множителя подаются параллельно на р q -1 информационных входов группы. В основу работы устройства положена параллельно-поточ- л ная организация вычислений. 4 ил., 1 табл. 3

«пп - 2п°1п- ап- впапакг ааап

С„2 fyn ln fnit L.cttCyCniCtЈn -Счг Win- Ъп

д

И И;Н fa

& 1$, о1,

Ј &, &, %,

/jff,tf 1в ;

0 S4i 1s}} 18a 1

е°1o ts«,ig,i

Фиг

|3,|J ... JJQ }p ... bp-nf-)

o, 1

BP1 1 Sp-1,1, 1 M,1 il. 10, 1 0, 1

,i врг, 1 Si2,i 8гг 1 8n , 1 o, 1 0,1

Оп-1,,1 1 ,q-i,1 , 1 fyj-f, / 0,1

W, ffplq, 1gq, 1 8q-1,q, 1 gi,f , t 8,1 0,1 fyw.lfyfr,,1 8.1,1 8Jffffi1 ,,1

0 . 1 8П,Л-1,1 8n-1,n-f,1 Sn-t,,1 ,/W/Vw/

Q , 1 0 f 1gnn, ; Ј-/,/,,

Pas 5

o, 1