Параллельное устройство для вычисления двухмерной свертки

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционируюпщх в реальном масштабе времени . Цель изобретения - упрощение устройства . Поставленная цель достигается за счет того, что устройство состоит из (L, К - размер матрицы коэффициентов) вычислительных блоков и синхронизатора, причем каждый вычислительный блок содержит два сумматора, два умножителя, два буферных регистра, регистр суммы, два коммутатора, триггер, два регист (Л ра множителя, два регистра коэффициентов , два регистра произведений и соответствующие связи между узлами устройства. 3 ил.

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

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

РЕСПУБЛИК

1 ,1

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

M А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ll0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3855399/24-24 (22) 11.02.85 (46) 07.11.86. Бюл. У 41 (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) А.В. Выжиковска, P. Выжиковски (PL) Ю.С. Каневский, В.И. Лозинский и С. Мичорек (PL) (53) 681.32(088.8) (56) Авторское свидетельство СССР

В 1057940, кл . G 06 F 7/38, 1983.

Kung Н.Т., Picard R.L.. Hardware

pipelines for multidimensional convolution and resampling, 1981, IEEE, Computer Society Markskop on Computer Architecture for Pattern Analysis and Image Database Maragement, 1981, р. 273-278.

„.Я0„„12692 7 А 1 (51) 4 Н 03 Н 17/06 G 06 F 15/353 (54) ПАРАЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ВЫ ЧИСЛЕНИЯ ДВУХМЕРНОЙ. СВЕРТКИ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе време-. ни. Цель изобретения — упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из P=Lk/2 (Ь, К вЂ” размер матрицы коэффициентов) вычислительных блоков и синхронизатора, причем каждый вычислительный блок содержит два сумматора, два умножителя, два буферных регистра, регистр суммы, два коммутатора, триггер, два регистра множителя, два регистра коэффициентов, два регистра произведений и соответствующие связи между узлами устройства. 3 ил.!

269237 зовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времени

Целью изобретения является упрощение устройства.

На фиг. 1 изображена общая схема устройства; на фиг, 2 — схема вычислительного блока, на фиг. 3 — блоксхема алгоритма работы q-го вычислительного блока (q=1,2...P).

Устро»»ство содержит Р=ЕК/2 вычислительных блоков 1.1,1.2...1.P и синхронизатор 2.

Каждьп» из вычислительных блоков

I.q (фиг. 2) содержит первый З.q u второй 4.q буферные регистры, первый коммутатор 5.q, триггер б.q управления, второй коммутатор 7.q, первый

8.»! и второй 9.»! регистры множителя, первый 10.q и второй Il.q умножителя, первый 12.q и второй 13.q регистры коэффициентов, первый 14.q z» второй 15.q регистры произведения, сумматоры Iб.q z» 17.q, регистр !.8 суммы.

Устройство работает следующим образом.

В исходном состоянии в регистрах коэффициентов 12.q и 13.q записаны коэффициенты w(k, I .), такие, что

P 2)+ (1-1 ) L где 1 а tL o o3HB "» BPT ближайшее не меньшее целое для а.

По сигналу пПуск устройства, кото-рый поступает в тексте с номером 1, в этом же такте на первый информационный вход устройства со скоростью одного отсчета на такт начинают поступать те отсчеты нечетных столбцов входного с массива х (о, Б), которые принадлежат строкам от первой до (2К-1)-й. Указа»»нь»е элементы входного массива посту»»ают в следующем порядке: х (1,1); х (2,1)...x(ZK-1,1), х(1,3), х(2,3)...х(2К-1,3)..„., причем после передачи в такте с номером

Т,/2К-1-го элемента некоторого нечетного столбца, первый элемент следующего нечетного столбца поступает только в такте с номером ;" +2, В так- . те с номером К+1 на второй информационный вход устройства. со скоростью одного отсчета на такт начинают поступать те отсчеты четных столбцов входного массива, которые принадлежат строкам от первой до (2К-1)-й„ Указанные элементы массива х(, S) пос50

Изобретение относится к вычислительной технике и может быть исполь° 5

45 тупают в следующем порядке . х(1,4), х(2,4)...х(2К-1,4)..., причем после передачи в такте с номером Т (2К вЂ” 1)-го

1 элемента некоторого четного столбца, первый элемент следующего четного столбца поступает только в такте с номером Т +2. Любой отсчет входного массива, поступающий на первый или второй информационные входы устройства, с приходом каждого тактового импульса сдвигается на одну позицию в регистре сдвига, образованном соответственно первыми 3.Р, 3.P-I... .3.1 или вторыми 4.Р, 4.Р†1 ° ..4.1 буферными регистрами. Таким образом, в такте с номером Р+1 первый элемент (1,1) входного массива хранится в буферном регистре 3.1 и начинается формирование отсчетов входного массива y(m n) для m

r=1,2,...К) на выходе синхронизатора

Z вырабатывается уровень логической

II u

1, а в остальных тактах с номерами

r=(t+l)K+r+P-1 — уровень логического

1I и

0 . Управляющий сигнал с выхода синхронизатора 2 передается посредством триггеров 6.1,6.2. ..6.Р на управляющ»»е входы коммутаторов 5.1, 7.1, 5.2, 7.2,...5.Р, 7.Р. При этом в вычислительных блоках I.q, номера

q которых удовлетворяют условию (2), на управляющие входы коммутаторов

5.q и 7.q поступает сигнал с прямого выхода триггера б.q, а в остальных блоках I.q, номера q которых удовлетворяют условию

q=(I. -1)К/2+(; I. =2,4,6,...; р =1,2,..., K/2> (3) на управляющие входы коммутаторов

5.q и 7.q поступает сигнал с инверсного выхода триггера б.q. В результате этого в течение такта с номером

Т таким, что

T-q=tK+r+P (4) в вычислительных блоках I.q, номера которых удовлетворяют условию (2), первьа» 5.q и второй 7.q коммутаторы с выходов первого З.q+1 и первого

3.»1 буфер»»ых регистров пропускают на входы соответственно первого 8.q u второго 9.q регистров множителя элементы x(t+8, ZP+r-1) и х(+1,, 2 +r3 1269

-2) соответственно, принадлежащие нечетному столбцу с индексом t+ p (Р=),2,3...), а в остальных блоках

I.q коммутаторы 5.q и 7.q с выходов второго 4,q+1 » второго 4.q буферных регистров пропускают на входы соответственно регистров 8. q и 9. q элементы

x(t+ 3, 2$+r-1) и x(t+0, 2P+r-2) соответственно, принадлежащие четному столбцу с индексом +т (0=2,4,6...) . IO

В течение остальных тактов таких, что

Т-q= (t+1 ) K+r /Р (5) в вычислительных блоках I.q, номера которых удовлетворяют условию (2), : коммутаторы 5.q и 7.q с выходов буферных регистров 4.q+I и 4.т! проттускают на входы соответственно регистров 8.q и 9.q элементы x(t+ 0+I, 3P+r—

-1) и x(t+Р+1, 2p+r-2) соответствен- 20 но, принадлежащие четному столбцу с индексом t+C+I, а в остальных блоках I.q коммутаторы 5.q и 7.q с выходов регистров З.q+1 и З.q пропускают на входы соответственно регистров 25

8.q и 9.q элементы x(t+ 8+1, 2P+r-1) и x(t+f+I 2p+r-2) принадлежащие нечетному столбцу с индексом t+E+1.

С приходом очередного тактового им— пульса указанные элементы входного ЗО массива записываются в регистры множителя 8.q и 9.q.

Рассмотрим формирование произвольного отсчета y(m,п) выходного массива для тиН-Ь+1, шК согласно выра— жению ,е у (m, n) = Г :: у (ш, n), Я= а где у (m,n)= w(k, 0)х(ш+1с-l, и+т -1) . то

Формирование отсчета у (m,n) начинается в такте с номером S=P+K(n-1)+

+ш, причем сначала формируется у (тп, (n). При этом, если номер и столбца— нечетный, тогда в формировании у (m, и) участвуют отсчеты входного массива х(, S), принадлежащие столбцу с нечетным индексом S=n=t+R=t+I (так как 1=1), которые поступают с регистра сдвига, образованного буферными регистрами 3.1...3.K/2+1.

Если же номер и столбца — четный, 1 тогда в формировании у (ш.n) участвуют отсчеты входного массива, при= надлежащие столбцу с четным индексом

S n=t+R+I=t+2, которые поступают с регистра сдвига, образованного буфер237 4 ными регистрами 4.1...4.К/2+l. В дальнейшем описание работы устройства ведется по тактам.

Такт S. В первый 8.1 и второй 9.! регистры множителя поступают соответственно отсчеты x(m+1,n) и x(m,п)

Такт S+1. Множители х(m+I,n) и

x(m n) с выходов регистра 8.1 и 9.1 поступают на вторые входы умножителей 10.1 и 11.1 соответственно, на первые входы которых с выходов первого 12.1 и второго 13.1 регистров коэффициента поступают коэффициенты

w(2,1) и w(1,1) соответственно. 3атем умножители 10.1 и 11.1 формируют произведения w(2,1) x(m+I,п), которые с приходом тактового импульса записываются соответственно в первом

14.1 и втором 15.1 регистрах произведения. В этом же такте в регистры множителя 8.2 и 9.2 поступают соответственно отсчеты х(ш+З,п) и х(m+

+2,n).

Такт S+2. Произведения w(2,1)

r x (m+ I, n) и w (l, I ) x (m, и) поступают на входы сумматора 16.1, который фор( мирует их сумму С (m,n). Указанная сумма поступает затем на вход сумматора 17.1, на другой вход которого постоянно поступает код нуля. Затем сумматор 17.1 формирует сумму у (m,n) =c (m,n)+0, которая с приходом тактового импульса записывается в регистр суммы 18.1.

В этом же такте умножителя 10.2 и

11,2 формирует произведения тт(4,1)» х(m+3,п) и w(3 1) x(m+2 n), которые записываются в регистры произведения

14.2 и 15.2 соответственно. Одновременно в регистры множителя 8.3 и 9.3 поступают отсчеты х(ш+5,n) и x(m+4,n) соответственно.

Такт S+3. Сумматор 16.2 формиру-ет сумму с (m,n)=тт(4,1) ° х(ш+З,n)+w(3,1) x(m+

+2,n), которая поступает на вход сумматора

17.2, на другой вход которого с выхода регистра суммы )8.1 поступает у (m,n) . Сформированная на выходе

t сумматора 18 „1 сумма у (m,n}., =у (ш,п), +с (m,n)< записывается затем в регистр 18.2.

В этом же такте умножителя ° 10.3 и

11.3 формируют произведения ь (6, 1)

x(m+5,n) и w(5,1) ° x(m+4,n), которые з аписываются в регистры 14. 3 и 15, 3 соответственно. Одновременно в реги5 стры 8.4 и 9.4 .поступают отсчеты

x(m+7,ï) z» x(m+6,п) соответственно.

1269

Такт S+1C/2. Сумматор 16./К(2-1) формирует сумму

5 с (m, п ) к г, =ъх (k-2, 1 ) х (»и+ k-3, п.) +

+w (k-3, 1 ) x (m+k-4, n), которая поступает на вход сумматора

17,К/2-1, на другой вход которого с вьг<ода регистра 18.К/2-2 поступает !0 сумма у {m,n)„1 . Сформированная на выходе сумматора 17.К/2-1 сумма ((( у (m n) к!г- =у (m п)к!г г +с (m п)к(г-! записывается затем в регистр 18.К/2-1

Одновременно произведения w(ksl) х(m+k-l,n) и v(k-l,l) x(m+k-2,n) записываются в регистры 14.К/2 и

15.К/2 соответственно. В этом же такг те начинается формирование у (,m,n).

При этом, если номер и столбца — не- 20 г четный„тогда в формировании у (m,п) участвую r отсчеты массива х (ь „Б), принадлежащие столбцу с четным индексои S=n+l=t+l.=t+2 (так как Я=-2) которые поступают с регистра сдвига, 25 образованного регистрами 4.К/2+1... .К+1. Если же номер столбца - четI!bI»I, тогда в фориироваш»!» у (m,n) уч !cтвуюг элементы х((, S}, принадлежа»пие столбцу с нечетным индексом 30

S=-!1+1.-(-(-!+1=-t+3. которые поступают с регистра сдвига, образованного регпстраьп» З.К/2+1...3.К+1. Фориирова— пие у" (ьп,n) начинается с того, что в регистры множителя 8.К/2+1 и 9.К/2+1 поступают соответственно отсчеты х (и»+1, и+1) и х(»п,п+1) .

Такт 8+2/К(1. Сумматор 16.К/2 формирует сумму с (m,n)„(z, которая по-. ! ступает на Brîðñ I» вход сумматора Ц)

17.К/2, на первый вход которого поступке r сумма у (m, n) г (. Сфориирот ванное в сумматоре 17.К/2 окончательное значение сук,иы у (Ill n) запи1 сывается затеи в регистр суммы 18,,К/2 -2. В этом >ке такте произведения ъ»(2,2) х(»п+!,п+1} и»г(1,2) x(m,n+1) записываются в регистрь» !4.К/2+1 и

15.К/2+1 соответственно. Одновременно и регистры 8.К/2+? и 9.K/2+2 пос- 50 тупают отсчеты x(m+3,п+1) и x(m+2 п+1) соответстве»»»»о.

Такт S+K/2+2. Сумматор 16.К/2+1 фор.»ирует сумму с (m,n)((lz,; =.-v(2,2) х(»п+l,n+! )+»»(1,2) х((п,n+1), которая поступает па второй вход сумматора

17.К/2+1, на вход которого поступает сумма у (»п,п). Сформированная в сум237 Ь маторе 17.К/2+1 су..(((а уг- {m,n) =y (m, и)+с (m, n) z „записывается затем в регистр 18.К/2+1. Б этом же такте в регистре произведения w(4,2) x{m+

+З,п+1) и w(3,2) x(m+2,n+1) записываются соответственно в регистры

14.К/2+2 и 15.К/2+2, а в регистры

8.К/2+3 и 9.К/3+3 поступают отсчеты х(тп+5,п+1) и х(m+4,n+1) соответственно.

Ф

Такт S=S+0, где Q=(E-1)К/2

=2,3...L. Сумматор 16.Q-1 формирует сумму с (m,n)„,, .»(k-2, (.-1),х(m+k-3, n+ f.-2)+w(k-3, -! ) x(m+k-4, n+ E-2), которая поступает на вход сумматора

17.Q-1, на другой вход которого с выхода регистра 18.Q-1 поступает сумма у (п»,п)k(z z . Затем сформирован -! ная в сумматоре !7.Q-1 сумма е-! В -! 9-! у (m n) к(г-(у (m п)к!г-г +с (m n) к(г-! записывается в регистр 18.Q-1. Одновременно произведения »г(1с, E-l)x(m+k†!,n+E-2) и w(k-l,2-1) x(m+k-2, и+ -2) записываются в регистры 14,Q и 15.Q соответственно. В этои же такте начиЙается формирование у (m,n} При этом

6 если номер и столбца — нечетный и ь — нечетное, или номер столбца— четный и — четное, тогда в формировании у (m,n) участвуют отсчеты x((., S), принадлежащие столбцу с нечетным индексом +.(, если 2 — нечетное; 1+ 1+1,если F — четное, которые поступают с регистра сдвига, образованного буферными регистрами

З.Q+1...3.Q+I

x((, S), принадлежащие столбцу с четным индексом

ГС+»+1, если !. — нечетное;

Я=п+ -1= t+ 1(. если» .— четное, которые поступают с регистра сдвига, образованного буферными регистрами

4.(1+1...4.С!+К/2+1. Формирование у (m, Р и) начинается с того, что в регистры множителя 8.Q+1 и 9.Q+1 поступают соответственно отсчеты х(п+l,п+(.-1) и

x(m,n+E-J).

Такт S+1. Сумматор 16.Q формирует сумму е-( ((m n) к(г =v(k, 0-1) x(m+k-l, n+7-2)+

+v(k-1, 6-1) x(m+k-2, п+ С-2), 7 269 которая поступает в» второй вход сумматора 17.Q, на первый вход которого поступает сумма у (m,n) g q . Сформированное в сумматоре 17.Q окончаетельное значение суммы у (m,n)„,, + (2

+у (m,n) записывается затем в регистр 17.Q. В этом же такте произведения w(2,Й)х(в+1,п+К-1) и w(1, Р)

x(m,п+2-1) 1аписываются в регистры

14.!1+1 и 15.Q+1 соответственно, а в !и регистры 8.Q+2 и 9.Q+2 поступают соответственно отсчеты x(m+3,п+1-1) и

x(m+2,n+1-1) .

Такт S+2. Сумматор 16. +1 формирует сумму с (m,n), =ч(2, R) x(m+1, n+C— е — 1 )+w (1, Р) x (m, E+n- I ), которая посту— пает на второй вход сумматора 17.Q+

+1, на вход которого поступает сумма у (m,n)„ . Сформированная в сумматоре 17.Q+1 (m,n)=y (m, 2п

n) 12 +с (тп,n) записывается затем в регистр 18.Q+1. Одновременно произведения w (4, f ) x (m+3, n+ P-1 ) и ы (3, Х)

x(m+2,п+Х-1) записываются в регистры !

6.Q+2 и 15.Q+2 соответственно, а в 25 регистры 8.Q+3 и 9.Q+3 поступают отсчеты х(m+5,п+Х-1) и х(m+4,п+К-1) соответственно.

Такт 1+3. Сумматор 16.Q+2 формиру 0 ет сумму с (m,n) =w(4, К) x(m+3, п+Ы вЂ” 1)+ч(3, У)

x(m+2,n+7.-1), которая поступает на вход сумматора

17.Q+2 на другой вход которого поступает сумма у (m,n)r . Сформироване ная в сумматоре 17.Q+2 сумма у (m,n)2 =

=у (m,n)r +с (m,n)2 записывается затем в регистр 18.Q+2. В этом же такте произведения w(6, Р) х(m+5, n+Z-1 ) и

w(5, Р) x(m+4, n+К-1) записываются со40 ответственно в регистры 14.Q+3 и

15.Q+3, а в регистры 8.Q+4 и 9.Q+4 поступают отсчеты x(m+7 n+Р-1) и

x(m+6,n+E-1) соответственно.

Такт S+K/2+1. Сумматор 16.Q+K/2 формирует сумму с (m,n)x12, которая е поступает на вход сумматора 17.0+

+К/2, на другой вход которого поступает сумма у (m,n) «12t . Сформированное в сумматоре 17.Q+K/2 окончательное значение суммы у (m n)

1,- 8 э (2

=у (m,n) „! +у (m,ï) записывается затем в регистр !8. Q+K/2. Таким образом, если E=L, тогда в. такте с номером S†-"" S+Q+K/2+1=S+LK/2+1 в сумматоре 17.LK/2 формируется окончател юе

237

Й значение сумГ ч! " (и\ и } ъ (IT) 11), ко торое записывает<.я в регистр !8.1,К/2, I В откуда поступает на информационный выход устройства. Значения с тсчетоь у(тп,п) выходного массива для 5 .К+1 гпе(о+1) К, 1ьп ИФ!.-1 (где д, =1,2,3... ) формируются точно так же с той лишь разницей, что на информационные входы устройства поступают отсчеты

x(c., S) входного массива, принадлежащие строкам с индексами у K+1 (сс+2) К-1.

Формула. изобретения

Параллельное устройство для вычисления двухмерной свертки, содержащее

P=LK/2 (L, К вЂ” размер матрицы коэффициентов) вычислительных блоков и синхронизатор, причем первый и второй информационные входы P-ro вычислительного блока являются соответственно первым и вторым информационными входами устройства, первый и второй информационные выходы i ro (i=2, Р) вычислительного блока подключены соответственно к первому и второму информационным входам (i — 1) — ro вычислительного блока, причем i-й (j =1,Р) вычислительный блок содержит первый и второй буферные регистры, первый и второй коммутаторы, первый и второй регистры множителя, триггер, первый и второй регистры коэффициентов, первый и второй умножители, первый и второй регистры произведений, первый и второй сумматоры и регистр суммы, при этом информационные входы первого и второго буферных регистров объединены соответственно с первым и вторым информационными входами первого коммутатора и являются первым и вторым информационными входами вычислительного блока, выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго регистров множителя, выходы которых подключены к первым входам соответственно.первого и второго умножителей, выходы которых подключены к информационным входам соответственно первого и второго регистров пр6изведений, выход второго регистра произведений подключен к первому входу первого сумматора, а выход второго сумматора подключен к информационному входу регистра суммы, выход которого явля2

1

1

9 12642 ется третьим информационным выходом вычислительного блока, а первый вход второго сумматора является третьим информационным входом вычислительного блока, выходы первого и второго регистров коэффициентов подключены к вторым входам соответственно первого и второго умножителей, вход триггера является синхровходом вычислительного блока, причем в каждом вы- 10 числительном блоке с номером q (E-1)

К/2+ P (E-1,3,5..., P "1,2,...,К/2), прямой выход триггера подключен к управляющим входам первого и второго коммутаторов и является синхровы- !5 ходом вычислительного блока, а в остальных вычислительных блоках инверсные выходы триггеров подключены к управляющим входам первого и второго коммутаторов и являются синхровыхода- 20 ми вычислительных блоков, о т л и— ч а ю щ е е с я тем, что, с целью

37 1О. упрощения устройства, выход синхронизатора подключен к синхровходу первого вычислительного блока, синхровход и третий информационный выход

Bl-r0 (ш=1, P-1) вычислительного блока подключен соответственно к синхровходу и третьему информационному входу (m+!)-го вычислительного блока, а третий информационный выход Р-ro вычислительного блока является.информационным выходом устройства, причем в i-м вычислительном блоке выходы первого и второго буферных регистров подключены соответственно к первому и второму информационным входам второго коммутатора и являются соответственно первым и вторым информационными выходами блока, выход первого регистра произведений подключен к второму входу первого сумматора, выход которого подключен к второму входу второго сумматора.

1269237

Составитель А. Баранов

Редактор В. Иванова Техред Л.Олейник Корректор И. Пожо

Заказ 6044/56 Тираж 816 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная„ 4