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

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

Иллюстрации

Показать все

Реферат

 

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

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

СОЦИЛЛИСТИЧЕСКИХ

РЕСПУБЛИК

5U 1774347 А1 (я) s G 06 F 15/347

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

hajj) с, Фиг/

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4819890/24 (22) 28.04.90 (46) 07.11.92; Бюл. ЬЬ 41 (72) В.П.Якуш, H.À.Ëèõoäåä, В.В,Косьянчук и П.И.Соболевский (56) Авторское свидетельство СССР

М 1534471, кл. G 06 F 15/347, 1990.

Авторское свидетельство СССР

hL 1677709, кл, G OG F 15/347, 10.05.89. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (nxn)-матрицы на ленточную матрицу.

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

1 — 3 информационные входы, вход 4, синхровход 5, вычислительный модуль 6i (i=

=1, p+g-1), выход 7. 2 ил.

1774347

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

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

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

Устройство для умножения матриц (фиг.

1) содержит первый 1, второй 2 и третий 3 информационные входы. вход 4, синхровход 5, вычислительные модули 6i (i=1, p+q-1) и выход 7, Вычислительный модуль (фиг. 2) содержит первый 8, второй 9 и третий 10 информационные входы, первый 12 и второй 11 входы синхронизации, умножитель 13, сумматор 14. регистры 15. 16, 17, 18 и 19i (i=1,n-1), триггер 20, элемент И 21, первый

22, второй 23, третий 24 и четвертый 25 выходы, В основу работы устройства положен алгоритм перемножения плотной (nxn)-матрицы Л на ленточную матрицу В, основанный на рекуррентных соотношениях (,и)

С!! = О, aJ=max{0, j-q}, j=1,п; (i ) (i — 1)

С!! = Cii +a iybiJ, К= а,Д1; ai=max{0, j-q}

pi=min{ï, p+j-1}, j=1,n; (J)

С!!аа Cij, Д =mln{n, р+!-1}, !,!=1,n.

При описании работыт тстроистаа ааааатсаб, .н;, ;i=bi; при !=max{1,j-q+1), я!п{п,j+p-1}, j=1,п в остальных случаях Ь!!=О.

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

+й — 1 авых авх !

+2.

Ьвых =, Ьвх, \ (!

+1 ! i-f t

Свнх = Свх + авх Ьвх !

+1 внх — бвх, где а вх, Ь вх и С ex — значения соответствен! I но на втором, первом и третьем информационных входах вычислительного модуля на

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

i+A — 1

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

i+2

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

10 i+1

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

i+1 твнх — значение на четвертом выходе

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

f=0,п-1 — параметр, определяемый алго ритмом.

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

На !-м такте элементы а, Ь и С матриц подаются соответственно на входы 9, 8 и 10 и записываются соответственно в регистры

19!, 15 и 17. Кроме того, при подаче на вход

11 единичного сигнала элемент И 21 откоывается и разрешается запись элемента Ь в регистр 18. При этом на выходу умножителя

13 формируется значение а b, на выходе сумматора 14 — значение С+а Ь. которое выдается на выход 24. Элемент а задержива30 ется на и-1 такт регистрами 19i (!=1, п-1) и выдается на выход 23. Элемент Ь задерживается на два такта регистрами 15 и 16 и выдается на выход 22, Управляющий сигнал г задерживается триггером 20 на один такт и выдаетея на выход 25. л

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

40 и

taiJ =i+(j-1)п-1;

tiiJ =(р-1)(п-1)+j+2(q-1)+O-1)п-i; (aJ)

teil =(p-1)(п-1)+i+(j-1)п-с!-2.

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

+(-1)n, в остальные моменты времени — управляющий.сигнал t =О.

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

50 тс!! =(р-1)(n-1)+ р+!+Д-1) и-2.

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

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

n(n+p-1) тактов.

1774347

40

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

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

Cii 0, то реализуется матричная операция вида С+А Б, Формула изобретения

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

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

1774347

Редактор

Корректор С. Пекарь

Заказ 3928 Тираж Подписное

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

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

Проиаеодстеенно-иадатеаьский коибинат "Патент", г. Уктгород, ул. Гагарина. 10т

Составитель В. Якуш

Техред M.Ìîðãåíòàë

graf

Жл