Устройство для вычисления двумерной свертки

 

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