Устройство для умножения матриц
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения плотной (пхп)-матрицы на ленточную матрицу. Цель изобретения - повышение быстродействия устройства. Цель достигается тем, что устройство содержит с первого по третий 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
Жл
