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

k

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (пхп)-матрицы на ленточную матрицу. Цель изобретения - повышение быстродействия устройства. Цель достигается тем, что устройство содержит с первого по третий 1-3 информационные входы, вход 4, синх- ровход 5. вычислительный модуль 6| (1 1, p+g-1). выход 7. 2 ил.

ffij

ъ

V4 VI

N СО 4 vj

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

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

На фиг. 1 представлена структурная схема устройства для умножения матриц; на фиг. 2 - пример схемы вычислительного мо- дулл.

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

Вычислительный модуль (фиг. 2) содержит первый 8, второй 9 и третий 10 информационные входы, первый 12 и второй 11 входы синхронизации, умножитель 13, сумматор 14. регистры 15. 16, 17, 18 и 19i (,гИ), триггер 20, элемент И 21, первый 22, второй 23, третий 24 и четвертый 25 выходы.

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

(jj)

QJ 0, Oj max{0, J-q}, i,,n;

00(О

Cij Cji +aikbkj,

K «j max{0, j-q} / j mln{n, p+j-1}, i,

{ л Л

Cij Cij . Д min{n, p+j-1}, I,.

При описании работы устройства вве- дем матрицу . Nj-q+1, j+p-1,,n, где при i max{1,j-q+1}, min{n,j- -p-1}, ,n в остальных случаях .

Вычислительный модуль выполнен с возможностью реализации функций

1+П-1 1

ЗВЫУ, ввх;

i+2. Ьоых Ьвх

Н-1 1 I l-f C Свых - Сцх + Эв х Ьвх,

1+ 1 I Твых Твх,

где а вх, b ox и с вх - значения соответственно на втором, первом и третьем информационных входах вычислительного модуля на i-м такте;

0

5

0

5

0

5

0

5

0

5

Нх - значение на втором входе синхронизации вычислительного модуля на 1-м такте;

1+П-1

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

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

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

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

,n-1 - параметр, определяемый алгоритмом.

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

На i-м такте элементы a, b и С матриц подаются соответственно на входы 9, 8 и 10 и записываются соответственно в регистры 19i, 15 и 17. Кроме того, при подаче на вход 11 единичного сигнала элемент И 21 открывается и разрешается запись элемента о в регистр 18. При этом на выходе умножителя 13 формируется значение а Ь, на выходе сумматора 14 -значение C+a G, которое выдается на выход 24. Элемент а задержива- ется на п-1 такт регистрами 19i (, n-1) и выдается на выход 23. Элемент b задерживается на два такта регистрами 15 и 16 и выдается на выход 22. Управляющий сигнал г задерживается триггером 20 на один такт и выдается на выход 25.

л

Элементы а, Ь и Cij подаются соответственно па входы 2, 1 и 3 устройства в моменты времени

(j-1)n-1;

tbV(p-1)(r,-1)+j+2(q-1)KJ-1)n-i;

toy (p-lXn-1)+l+0-1)n-q-2.

На вход 4 управляющий сигнал подается в моменты времени (p-1)(n-1)-(q-1)+ +(j-1)n, в остальные моменты времени - управляющий сигнал ,

На выходе 7 устройства элементы Cij выдаются в моменты времени

tcij (р-1Хп-1)+Р+И-0-1)п-2.

Рассмотрим работу устройства для перемножения плотной (4х4)-матрицы А на ленточную матрицу В (, ). Устройство содержит p+q-1 3 вычислительных модулей.

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

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

Если на вход 3 устройства подавать

Ci) 0, то реализуется матричная операция вида С+А В,

Формула изобретения Устройство для умножения матриц, содержащее () вычислительных модулей (где р и q - соответственно число ненулевых элементов в первом столбце и первой строке ленточной матрицы), причем первый информационный вход первого вычислительного модуля подключен к первому информационному входу устройства, второй информационный вход (р q-1)-ro вычислительного модуля подключен к второму информационному входу устройства, первый вход синхронизации которого подключен к первым входам синхронизации всех вычислительных модулей, первый выход и второй информационный вход 1-го вычислительного модуля (где 1 1p+q2) подключены соответственно к первому информационному входу и второму выходу (i+1)-ro вычислительного модуля, отличающееся тем, что, с целью повышения быстродействия устройства, третий информационный вход и второй вход синхронизации первого вычислительного модуля подключены соответственно к третьему информационному входу и к второму входу синхронизации устройства, третий и четвертый выходы 1-го вычислительного модуля под- ключены соответственно к третьему информационному и к второму входу синхронизации (1+1)-го вычислительного модуля, третий выход (pi-q-1)-ro вычислительного модуля подключен к выходу устройства, причем каждый вычислительный модуль содержит с первого по четвертый регистры, сдвигающий регистр, умножитель, сумматор, триггер и элемент И, при этом в каждом вычислительном модуле первый информационный вход вычислительного модуля подключен к информационным входам первого и второго регистров, выходы которых подключены соответственно к информационному входу третьего регистра и к первому

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

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

элемента I/I, выход которого подключен к входу записи/считывания второго регистра, выход триггера подключен к четвертому выходу вычислительного модуля, первый вход синхронизации которого подключен к входам записи/считывания первого, третьего и четвертого регистров, к входу синхронизации триггера, к второму входу элемента И и к управляющему входу сдвигающего регистра.

Фиг.1