Устройство для вычисления двумерной свертки
Иллюстрации
Показать всеРеферат
Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов для вычисления двумерной свертки. Цель изобретения - повышение быстродействия устройства. Цель достигается параллельно-поточной организацией процесса вычислений в трехмерной матрице I<SP POS="POST">.</SP>J<SP POS="POST">.</SP>Q вычислительных модулей, где I<SP POS="POST">.</SP>J - размерность матрицы-результата P<SP POS="POST">.</SP>Q - размерность "окна свертки". Время вычисления двумерной свертки составляет I+J+P+2Q - 3 тактов, а период вычислений - J+Q-1 такт. 1 з.п. ф-лы, 3 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН
nmSUrui 157 4
А1 (g))5 G 06 F 15/347
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ
ПРИ ГКНТ СССР
f ., 1 (21) 4385084/24-24 (22) 29.02.88 (46) 23.06.90. Бюл. М - 23 (72) В.П.Акуш, Н.А.Лиходед, П.И.Соболевский и В.В.Косьянчук (53) 681.325 (088.8) (56) Авторское свидетельство СССР
У 1401477, кл. G 06 F 15/347, 01.12.88.
Kung Н.Т., Ruane L.М., Yen D.W.L.
А two level pipelined systolik array
for convolutions. Proc. Conf. on
VLSI syst. and comput., ос . 1981.
Springer — Verlag, 1981, р.255-264, fig.4. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОЙ СВЕРТКИ
Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифро- вой обработки сигналов для вычисления двумерной свертки.
Цель изобретения — повышение быстродействия.
На фиг.1 представлена структурная схема устройства с потоками входных и выходных данных для вычисления двумерной свертки для случая E=J=P=
=Q 2; на фиг.2 — функциональная схема (i,j,k)-ro вычислительного модуля (i=1,Ð, j 1, I, k 1,Q), на фиг.3— функциональная схема (i, j (+1)-го вычислительного модуля (i=1,P, j=l,I).
Устройство для вычисления двумерной свертки (фиг.1) содержит с первой по четвертую группы 1-4 информа2 (57) Изобретение относится к вычислительной технике и может быть испольэовано в специализированных вычислительных машинах и устройствах обработки сигналов для вычисления двумерной свертки. Цель изобретения — повышение быстродействия устройства.
Цель достигается параллельно-поточной организацией процесса вычислений в трехмерной матрице IxJxQ вычислительных модулей, где IQ — размерность "окна сверткй".Время вычисления двумерной, свертки составляет
E+J+P+2Q — 3 тактов, а период вычислений — J+Q — 1 такт. 1 з.п.ф-лы, 3 ил. ционных входов, матрицу {i,j,k% (i=
=1 2 j=1 2 k=1 3) вычислительных модулей 5, группу выходов 6, синхровход (не показан). (i,j,k)-й вычислительнй модуль (i,j k=1,2) (фиг.2) содержит первый информационный вход 7, второй информационный вход 8, третий информационный вход 9, синхровход 10, регистры 11 — 14, умножитель 15, сумматор .16, с первого по .четвертый выходы
:17-20. (i,j,Q+1)-й вычислительный модуль (i=1,2, j=1,2, Q=2) (фиг.3) содержит первый 21 и второй 22 информационный входы, синхровход 23, регистры 24 и
25, сумматор 26 и выход 27.
В основу работы устройства положен алгоритм вычисления двумерной свертки
1573460 ние р Р-1 у =у = 2 ° ° р о
Р-I Q-I
У ) (J)pq ф p»-(9 р о 1=0 который состоит из двух частей: ( о -=О -1, j=O, -1, p=O,P-1 р1
1)р Ij/ Цро х л-р, j-q х Q=O„Q 1 о
У =0 1=0, I-1, j =O,.)-1
1 д
У; =У;) +х; p, p=O Р-1
Первая часть алгоритма — вычислеQ- ЦР о И -I 13 вторая часть — вычисление
При описании работы устройства в обозначении х ") индекс (1) в скобках Ч указывает номер такта работы устройства, а индекс k без скобок — номер рекуррентного шага, (i,j,k)-й вычислительный модуль (i=1,Р, j=1,I, k=1,Q) работает следующим образом. В исходном состоянии регистры 11-14 устанавливаются в нулевое состояние. Ha k-м такте на входы 7, 8 и 9 подаются соответственно значения х „, z „ и M „„, íà выходе умножителя 15 формируется произведение х „+у „, а на выходе суммаToра 16 — сумма ко„ +х „ у „, которая подается на выход 18, на выход 20 подается значение с „
На (k+1)-м такте на входы 7-9 подаI ются соответственно значения х „, z z и Ю „, на выходе сумматора 16
I формируется сумма z „ +х „wÿ ц», которая подается на выход 18. В регистр !
11 записывается значение х „, в регистр 12 — значение х „, в регистр
14 — значение Я „ . На выходы 17 и
19 подаются значения х „, на выход
20 — значение Я » (i,j,Q+1)-й вычислительнй модуль (i=1,Ð, )=1,Т) работает следующим образом. Регистры 24 и 25 устнавлива5 l0 l5
55 ются в начальное состояние ° Ha k-м такте на входы 21 и 22 подаются соответственно значения у и z на
bX eX выходе сумматора формируется сумма у +z х, которая подается на выход 27.
Устройство работает следующим образом.
В исходном состоянии регистры устанавливаются в нулевое состояние (не показано). На входы 1 подаются элементы х; .- . На входы 3 посто1 — р янно подаются элементы &lpga (фиг.1), на входы 2 и 4 — нулевые значения.
На нулевом такте на вход 1„,„ подается элемент х о, . В вычислитель(о) ном модуле 5, в регистр 11 записывается элемент х о, lo)
Н"= первом такте на входы 1+„, 1,д, и 1 «, подаются соответственно элементы х îo x - и х - - на вход (1) Ю (<)
3 „, подается элемент Я . В вычислительном модуле 5 „ формируется о оооо= + оо хоо х в РегистР ооо ооо
11 записывается значение хоо а в регистр 12 — значение х о,. В вычислительном модуле 5 „о< в регистр 11 записывается элемент х „ „, а в вычислительном модуле 5«„ в регистр 11 элемент х
На втором такте на входы 1„д, 1,о„ и 1 подаются соответственно элемен9 ты х,, х, и х о . В вычислительном модуле 5<„, формируется значение z о, о
=к о, +Я х,, в регистр 11 записывается элемент хо, а в регистр 12 элемент х оо . В вычислительном модуле о
5хо формируется значение z„oo =z„on+
+ цо х1о, в регистр 11 записывается элемент х о, а в регистр 12 — элемент х, . В вычислительном модуле
5 1 формируется значение оо, =z о +
1 оо1 oî<
+ „),о х о, в регистр 11 записывается элемент х 1о, а в регистр 12 — элемент х 1 4 . В вычислительном. модуле цо ФормируеTc< значение zооо оооо+
+ 4) хо<, в регистр 11 записывается элемент х „
На третьем такте в вычислительном модуле 5 „, формируется значение z„ о = ,о мо
=я „„о + Яо х„,, в регистр 1 t записывается элемент х „4, а регистр 12 — элемент х „. В вьг»ислительном модуле
5 «, формируется значение z „ =z „,.+ о
+ M,охи, в регистр 11 записывается элемент х 1, в регистр 12 — элемент х 4о . В вычислительном модуле 5 формируется значение z„ö„ =. z „о, + о
+ Ящ хоо, в регистр i i записывается
5 15 элемент х, а в регистр 12 — элемент х „, . В вычислительном модуле
Г
Э 112 формируется значение Zo1o zа о+
+Я, x о, в регистр 11 записывается элемент хоо, а в регистр 12 — элемент х „,, В вычислительном модуле 5212 формируется значение z оo1 = г oo1 +
+ Q«x, „, в регистр 11 записывается элемент х, . В вычислительном модуле 5 122 формируется значение
1 г 1оо =21oo +M« + <, в Регистр 11 записывается элемент х <, . В вычислительном модуле 5 11э формируется энао уоо уо +z ooo °
На четвертом такте в вычислитель HoM модуле 5,2, формируется значение о г,„1 =г„„„+Я 1о хо1, в Регистр 11 записывается элемент х ор, а в регистр
12 — элемент xoo . В вычислительном модуле 51zz формируется значение
z11o =г11о + Ио1 х1о . В вычислительном модуле 5212 формируется значение
2 г о11 =гo«+ +11 х «о ° В вычислительном модуле 5222 формируется значение
1 г Äo, =г „о, + 63«х о, . В вычислительном модуле 511 формируется значение у ! о
=уо1+zo1O, В вычислительном модуле
5 21 формируется значение у о =yoo =—
=у +г,, которое подается на выход
6 устройства. В вычислительном
1 модуле 512 формируется значение у1о =
2 у1o +г
2. г „„„= Z 111+ Q „х ро. В вычислительном модуле 521 формируется значение у, =
2 f 2 уо1 ус +z оо1, которое подается на выход 621э устройства. В вычислительном модуле 512 формируется значение у 11 =у„+z „ . В вычислительном модуле 5zzy формируется значение у =у
2 ло 1о
=У1о +г,о1, котоРое подается на выход
6 22з устройства.
На шестом такте в вычислительном модуле 5zzg формируется значение у < = .=У1, =у11 +г 1„, которое подается на выход бд,э.
Формула изобретения
1. Устройство для вычисления двумерной свертки, содержащее PxQ вычислительных модулей (РкЯ вЂ” размер окна свертки), о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены (PkQ)(1-1)+
+IP вычислительных модулей (I — число строк матрицы-результата), причем
73460 6 вычислительные модули образуют трехмерную ллелрииу (i,j,kI (i=i,p, j=1,1, k=1,<)), i-й и (1+Р-1)-й выходы первой группы информационных входов устройства подключены к первым информацион- ным входам соответственно (1,1,1)-го и (1,1,1)-ro вычислительных модулей (1=2, I), (i, j ) -й вход второй и (i, k) -й вход третьей групп информационных входов устройства подключены соответственно к второму информационному входу (i,j,1)-ro и третьему информационному входу (i,1,k)-го вычислительных модулей, )-й вход четвертой группы информационных входов устройства подключен к первому информационному входу (1,j,Q+1)-ro вычислительного
20 модуля, синхровход устройства подклю. чен к синхровходам всех вычислительных модулей, первые информационные входы (i,1,n+1)-го и (1,1,n+i)-го вычислительных модулей подключены к
25 первым выходам соответственно (j,1, п)-ro и (1,1,п)-го вычислительных модулей.(n=1,() — 1), а первый информационный инАормационный вход (ц+1
Q+1)-го вычислительного модуля под30 ключен к первому выходу (q,j,Q+1)-го вычислительного модуля (q=1, Р— 1), второй информационный вход (i,j,k+1)го и первый информационный вход (q+1, р+1,k)-ro вычислительных модулей под35 ключены соответственно к второму вы ходу (i,j,k)-го и третьему выходу (р,q,k)-го вычислительных модулей (р=1, I-1), третий информационный вход (i,р+1,k)-го вычислительного мо4р дуля подключен к четвертому выходу (i,р,k)-го вычислительного модуля, а первый выход (Р,j Q+1)-го вычислительного модуля является j-м выходом группы выходов устройства.
2. Устройство по п.1, о т л и чающее ся тем, что (i,j,k)"é вычислительный модуль содержит четыре регистра, умножитель и сумматор, 5О причем первый, второй и третий информационные входы вычислительного модуля подключены к информационным входам первого, третьего и четвертого регистров, выходы которых подключены соотвественно к первому входу умножителя, к первому входу сумматора и второму входу умножителя, выход которого подключен к второму входу сумматора, первый выход вычислительного модуля подключен к выходу второго регистра, информационный вход которого подключен к выходу первого регистра, Второй, третий и четвертый выходы вычислительного модуля подключены со5
Ответственно к выходам сумматора, второго и четвертого регистров, синхровход вычислительного модуля подключен к синхровходам всех регистров, 1 а (i,j,Q+1)-й вычислительный модуль
Содержит два регистра и сумматор, причем первый информационный вход вычислительного модуля подключен к информационному входу первого регистра, выход которого подключен к первому входу сумматора, выход которого подключен к выходу вычислительного модуля, второй информационный вход которого подключен к информационному входу второго регистра, выход которого подключен к второму входу сумматора, синхровход вычислительного модуля подключен к синхровходам всех регистров. ЮЗ, l5734uO
Составитель К.Кухаренко
Техред М.Ходанич Корректор О. Кравцова
Редактор Н.Лазаренко Заказ 1643
Тираж 570
Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СЧСР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский. комбинат "Патент", r. Ужгород, ул. Гагарина, 101