Устройство для перемножения потока @ - матриц
Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных вычислительных машинах и устройствах обработки сигналов для перемножения цепочки матриц. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство для перемножения М(пхп) матриц содержит 2п вычислительных модулей, выполняющих основную арифметическую операцию над числами вида с+а«Ь. В основу работы устройства положена параллельногпоточная организация вычислений. 6 ил.
COK)3 СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)з 6 06 F 15/347
ГОСУДАРСТВЕНЮЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4804294/24 (22) 20.02.90 (46) 23.02.93. Бюл. ЬЬ 7 (72) B.Ï.ßêóø и Н.А.Лиходед (56) Авторское свидетельство СССР
N. 1735867, кл. G 06 F 15/347, 1992.
Авторское свидетельство СССР
М 1645969, кл. G 06 F 15/347; 1990. (54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ
ПОТОКА пхп-МАТРИЦ (57) Изобретение относится к области вычислительной техники и может быть испольИзобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных вычислительных машинах и устройствах обработки сигналов для перемножения цепочки матриц.
Цель изобретения — сокращение аппаратурных затрат.
На фиг.1 представлена структурная схема устройства для перемножения М пхпматриц; на фиг2. — структурная схема устройства для случая М=4 и и = 3, на фиг.3 и 4 — функциональные схемы соответственно вычислительных модулей, выполняющие функции, описанные в формуле изобретения, на фиг.5 и 6 — таблицы, поясняющие работу устройства.
Устройство для перемножения потока пхп-матриц (фиг.1) содержит информационные входы первой группы 1i (! = 1,2), информационные входы второй группы 21 () = 1,n), настроечные входы Зь синхровход 4, вычислительные модули 51 и 6J, информационный выходы первой 7 и второй 81 групп.... ЯЛ„» 1797128 А1 зовано в высокопроизводительных вычислительных машинах и устройствах обработки сигналов для перемножения цепочки матриц. Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство для перемножения М(пхп) матриц содержит 2п вычислительных модулей, выполняющих основную арифметическую операцию над числами вида с+а b. В основу работы устройства положена параллельно-поточная организация вычислений, 6 ил.
Вычислительный модуль 5 (фиг.3) содержит первый 9, второй 10 и третий 1? информационные входы, первый 12 и второй 13 разряды настроечного входа, синхровход
14, умножитель 15, сумматор 16, регистры
17, 18 и 19, триггеры 20 и 21, группы элементов И 22, 23, 24 и 25, группы элементов ИЛИ
26, 27, 28, элемент НЕ 29, первый 30, второй . 31 и третий 32 информационные выходы, первый 33 и второй 34 настроечные выходы.
Вычислительный модуль 6 (фиг.4) содержит первый 35 и второй 36 информационные входы, первый 37 и второй 38 настроечные входы, синхровход 39, умножитель 40. сумматор 41, регистры 42, 43 и
44, триггеры 45 и 46,.группу элементов И 47, элемент И 48, первый 49, второй 50 и третий
51 информационные выходы, первый 52 и второй 53 настроечные выходы.
В основу работы устройства положен алгоритм перемножения M nxn-матриц, коTopbIA задается следующими рекуррентными соотношениями:
m = 2,3,...,М:
1797128
blik и = blik-1щ < аФ"1 Ьц 1, k = 2,п
Ь|(" = Ьц.", В обозначении а (индекс m указывает п,t номер матрицы, а индекс t — номер такта работы устройства.
Устройство (фиг,2) рабо гает следующим образом.
На вход 11 подаются элементы матриц (нечетных) А(и А в моменты времени t = (1) (i-1)n + j - 1 + (m - 1)/2(n + 1) на вход 12— элементы матриц (четных) А в моменты времени t = i - 1 + jn + (m - 2)/2(п + 1), на
2 входы 2i — элементы матрицы В в моменты (1) времени t = + J — 2, на входы 31 и 32 — 15 соответствующие управляющие сигналы (6,/)), Значения (а,P) = (*,*) могут быть произвольными. В таблицах на фиг,5 и 6 приведены состояния регистров и триггеров, значения на входах и выходах вычислительных модулей 5 и 6 устройства. На выходах 71 устройства формируются элементы Ь|1 произведения нечетного числа матриц М в моменты времени t =! + /+ (M1)/2(n + 1)-2, причем последний элемент bnr
2. 25 формируется на (2п + (М-1)/2(n + 1)-2)-м такте. На выходах 81 устройства формируются элементы Ь11 произведения четного числа матриц М в моменты времени t = ni + j + (М
- 2)/2 (и + 1) - 1, последний элемент bye
2 30 формируется в момент времени ni+ и+ (М2)/2(n + 1)- 1.
Формула изобретения
Устройство для перемножения потока пхп-матриц, содержащее 2п вычислительных модулей, причем первый и второй информационные входы первой группы . входов устройства подключены к первым информационным входам соответственно 40 первого и (и+1)-ro вычислительных модулей, первые информационные выходы (-ro и (i + и)-ro (i = 1; и - 1) вычислительных модулей подключены к первым информационным входам соответственно (i+ 1)-ro и (i+ и+ 1)-го вычислительных модулей, i-й информацион45 ный вход второй группы входов устройства подключен к второму информационному входу I-ro вычислительного модуля, второй информационный выход которого подключен к второму информационному входу (it
+ и)-ro вычислительного модуля, второй и третий информационные выходы которого подключены соответственно к i-му информационному выходу первой группы выходов устройства и к третьему информационному входу i-ro вычислительного модуля, третий информационный выход которого подключен к I-му информационному выходу второй
С(+1=
4 если (а,/М) =(1,1) если (d,ф r2 ) = (0,1,1) если (rt, j3) = (1,0)
ЕСЛИ (а,Р1, а ) =(0,0,1) а Ь, а Ь, ci+э(Ь(С1+а(bi ", где Q иф — значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;
Ui и Ф вЂ” значения соответственно на первом и втором настроечных. выходах вычислительного модуля на j-м такте; а и А — значения соответственно на первых информационных входе и выходе вычислительного модуля на j-м такте;
Ь вЂ” значения на втором и третьем информационных входах вычислительного модуля на j-м такте; с — значения на втором и третьем информационных выходах вычислительного модуля на J-м такте; вычислительные модули с (и + 1)-го по
2п-й выполнены с возможностью реализации следующих функций;
U "= а
А =а
С( а(б, если (а1, У) = (1,1) а d, если (а,p,p ) = (1,0,1)
Сс "+а б(. если (а(,P) =(0,1) с " +а di, если (а(,/У,/У ) = (0,0,1) где di — значение нэ втором информационном входе вычислительного модуля на j-м такте. группы выходов устройства, синхровход которого подключен к синхровходэм всех вычислительных модулей, первый и второй настроечные входы устройства подключены соответственно к настроечным входам первого и (и + 1)-ro вычислительных модулей, настроечные выходы l-го и (1+ n)-го вычислительных модулей подключены к настроечным входам соответственно (l + 1)-ro и (i + n
+ 1)-ro вычислительных модулей, о т л и ч аю щ е е с я тем, что. с целью сокращения аппаратурных затрат, вычислительные модули с первого по и-й выполнены с возможностью реализации следующих функций:
Ui+1= а1
Ч) + 1 =/3(А(= а(1
° м
C Э
1797128
)
Ф
Фг о
Со
4%
% ъ
1797128
Ег ф Еч а„а ц », » ЕЧ ел,.» р н» .4» ev. »
»» ес» чъ мь ю
3 ФЪ Yl &N (е»
° .-. М ° »Ч e аа С> Ю
Ф а
Фс Есф,у hs +„ev
e4+ ч м » » " "4 "»
° а< а(ъ С» Ф В
g +4+ а » е » с» фг» д О»
У » » е о L N м ef »» -» 4" н -»» » а< ееу съ 3 Ю
4V е, С
ttl ° cv Е а о . Ф. к ф з с 3
tV
» »»,» к л е
М» Ь»
° у, ь Ъ ф -» к еч »
»
%ъ ° е3 с» <;
° ю .,„
Я е.. м »
Ео н»
° с, Ь ф" Ъ 3 ч—
° .ф
Р м
N» ч
hs
%:»
sn »
Фю»
СЪ ве ev
m въ ,Я
Ф
m съ (:
МЪ м»-»
СЪ
ФЪ
М »
)К
1 1!? 71?Я
/ / Ьг. Ю
„(/
1797128
Фе л
° ч л, л
Г ° л
«. Ф Ю
° ч ь с:» е М
«Ф ю
4 \
t ° с»-„ с»-» еч сс»
Фч сс, С»
° » с»
Вч
Ф Ъ с»
ФФ
Фч ° сс:>
Ф Зф
3в\ ь
Ф ° сс»
4 сс» е апач л<ч сс» ас» о о
В у сс» л с:с» е ч сс» л ь с.-> со fV сс» сс
1797128
«Ъ
33Ъ
° 3Ъ
34Ъ
3 \
« \
«Ъ
ФФЪ
3 3 Ъ
Ф4
ФФЪ
° \
ФЪ
ФЪЪ
ФСЬ
-Ъ. чЪ
ФЪ3
ФФЪ
ФСЪ
Ф 4
° ч
° ч ь
44
Ф4 3
3 ь
3 Ъ
t4
"Ъ
ФЪ
ФЪ
«:Ъ
«3 ч
ФФЪ
Ф 4
° ч
° Ч4
44
34
Фч
4.4 tv
° О
ФЪ Ю
«Ъ
ФФЪ
Ъ
ФЪ
° 43
44
° ч
ФЪ
ФФ .Ъ
° Ъ чЗ
«4
Ч:Ъ
4444
° 3» ю
443ч 44
30 «4
Ъ ЪФ»
Фч 4
О к
° 43
° (e a
Составитель К. Кухаренко
Техред М.Моргентал Корректор Л.пилипенко
Редактор
Заказ 654 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35. Раушская наб„4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 ЪЪ
«Ъ
ФФ:Ъ
ФЪ .
° ч
«ЪЪ
"Ъ
3 Ъ
ФЪ;
Ъ.
° 3
ФФЪ
«3
44
ЪЗ
«Ъ
Ф ъ
3 Ъ
ФСЬ
«Ъ
3ЪЪ
Фч ь
° 4 ь
«Ъ
«Ъ
Ф4
"Ъ
ФС>
«\
t4
33
ФФЪ
Ъ
ЪФЪ
33ФЪ
33
333
3 3
ФСЪ
Ъ
343
ФЗЪ
t»
° °
«3
ФФЪ
44
° Ъ ь
3 3
343
«Ъ
ФЪЪ
