Параллельное устройство для вычисления двухмерной свертки Советский патент 1986 года по МПК H03H17/06 G06F17/17 

1

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

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

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

Устройство содержит вычислительных блоков . 1,1 .2 . . . 1 .Р и синхронизатор 2.

Каждьш из вычислительных блоков 1 .q (фиг. 2) содержит первый 3.q и второй 4.q буферные регистры, первый коммутатор 5.q, триггер 6.q управления, второй коммутатор 7.q, первый 8.q и второй 9.q регистры множителя, первый lO.q и второй ll.q умножителя, первый 12,q и второй 13.q регистры коэс})фициентов, первый 14.q и второй 15.q регистры произведения, сумматоры 16,ди 17.q, регистр 18 суммы

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

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

(1-1 )L, где 1а обозначает

ближайшее не меньшее целое для а. По сигналу Пуск устройства, который поступает в.тексте с номером 1, в этом же такте на первый информационный вход устройства со скоростью одного отсчета на такт начинают поступать те отсчеты нечетных столбцов входного с массива х (Т, S), которые принадлежат строкам от первой до (2К-1)-й. Указанные элементы входного массива поступают в следующем порядке: X (1,1); X (2,1)...х(2К-1,1), х(1,3), х(2,3)..,х(2К-1,3)..., причем после передачи в такте с номером Ti/2K-l-ro элемента некоторого нечетного столбца, первый элемент следующего нечетного столбца поступает только в такте с номером Т,+2, В такте с номером K+f на второй информационный вход устройства со скоростью одного отсчета на такт начинают поступать те отсчеты четных столбцов входного массива, которые принадлежа строкам от первой до (2К-1)-й„ Указанные элементы массива хС, S) пос69237

тупают в следующем порядке: х(1,4), х(2,4)...х(2К-1,4)..., причем после передачи в такте с номером Т (2К-1)-го элемента некоторого четного столбца, 5 первый элемент следующего четного столбца поступает только в такте с номером . Любой отсчет входного массива, поступающий на первый или второй информационные входы устрой10 ства, с приходом каждого тактового импульса сдвигается на одну позицию в регистре сдвига, образованном соответственно первыми З.Р, З.Р-1... 3.1 или вторыми 4.Р, 4.Р-1...4.1 буtS ферными регистрами. Таким образом, в такте с номером Р+1 первый элемент (1,1) входного массива хранится в буферном регистре 3.1 и начинается формирование отсчетов входного масси20 ва у(га,п) для miK, п N-L+I. При этом в такте с номером Р- на вход разрешения счета синхронизатора поступает сигнал Пуск. Синхронизатор 2 работает как делитель частоты с коэффици.5 ентом деления К, причем в тактах с номерами T tK+r+P-l (где ,2,4.. .; ,2,...К) на выходе синхронизатора 2 вырабатывается уровень логической 1, а в остальных тактах с номерами

30 Т(t+1)К+г+Р-1 - уровень логического О. Управляющий сигиал с выхода синхронизатора 2 передается посредством триггеров 6 .1,6 .2 ...6.Р на управляющие входы ко№гутаторов 5.1,

35 7,1, 5.2, 7.2,...5.Р, 7.Р. При этом в ВЕ.1числительньгх блоках 1 .q, номера q которых удовлетворяют условию (2), на управляющие входы коммутаторов 5.q и 7.q поступает сигнал с прямого

4Q выхода триггера 6.q, а в остальных блоках l.q, номера q которых удовлетворяют условию

q(H-l)K/2+0; ,4,6,...; й, 1,2,..., К/2,(3)

45 13. управляюпу-ie входы коммутаторов 5.q и 7.q поступает сигнал с инверсного выхода триггера 6.q. В результате этого в течение такта с номером Т таким, что

50T-q tKH-r+P (4)

В вычислительных блоках 1.q, номера которых удовлетворяют условию (2), первьш 5.q и второй 7.q ком таторы с выходов первого 3.q+l и первого

55 3.q буфериз1х регистров пропускают на входы соответственно первого 8,q и второго 9.q регистров множителя элементы x(t+E, 2р+г-1) и x(t4-E, 2 +г-2) соответственно, принадлежащие нечетному столбцу с индексом t+E (,2,3...), а в остальных блоках I.q коммутаторы 5.q и 7.q с выходов второго 4.q+I и второго 4.q буферных регистров пропускают на входы соответственно регистров 8.q и 9. q элемент x(t+, ) и x(t+P, 2/3+Г-2) соответственно, принадлежащие четному столбцу с индексом t-t- (,4,6...). В течение остальных тактов таких, что T-q(t+l)K+r/P, (5) в вычислительных блоках I.q, номера которых удовлетворяют условию (2), коммутаторы 5.q и 7,q с вьгходов буферных регистров 4.q+l и 4.q пропускают на входы соответственно регистров 8,q и 9,q элементы x(t+P+l, 2/3+г -I) и x(t+P-t-l, 2Й+Г-2) соответственно, принадлежащие четному столбцу с индексом t+f+I, а в остальных блоках 1.q коммутаторы 5.q и 7.q с выхо дов регистров 3.q+l и 3.q пропускают на входы соответственно регистров 8.q и 9.q элементы x(t+f+l, 2 4-r-l) и x(, 2p+r-2) принадлежащие нечетному столбцу с индексом t+E+l. С приходом очередного тактового импульса указанные элементы входного массива записываются в регистры множителя 8. q и 9 . q. Рассмотрим формирование произволь ного отсчета y(m,n) выходного массива для n N-L+1, miK согласно выражениюy(m,n) L. у (m,n). где y(m,n)Z: w(k, E)x(m+k-l, п+Е-1) Формирование отсчета у(т,п) начинается в такте с номером (n-l)+ +m, причем сначала формируется у(т. п). При этом, ес:пи номер п столбца нечетный, тогда в формировании у (т, п) участвуют отсчеты входного массива хС, S), принадлежащие столбцу с нечетным индексом (так как ), которые поступают с регистра сдвига, образованного буферными регистрами 3.1...3.К/2+1. Если же номер п столбца - четный, тогда в формировании у (т.п) участвуют отсчеты входного массива, принадлежапще столбцу с четным индексом S«n t+P+l t+2, которые поступают с регистра сдвига, образованного буфер 374 ными регистрами 4.1...4.К/2+1. В дальнейшем описание работы устройства ведется по тактам. Такт S. В первый 8.1 и второй 9. регистры множителя поступают соответственно отсчеты x(m+l,ri) и х(т,п) Такт S+1. Множители x(m+l,n) и x(m,n) с выходов регистра 8.1 и 9.1 поступают на вторые входы умножителей 10.1 и 11.1 соответственно, на первые входы которых с выходов первого 12.1 и второго 13.1 регистров коэффициента поступают коэффициенты w(2,l) и w(,l) соответственно. Затем умножители 10.1 и 11.1 формируют произведения w(2,l) x(m+l,n), которые с приходом тактового импульса записываются соответственно в первом 14.1и втором 15.1 регистрах .произведения. В этом же такте в регистры множителя 8.2 и 9.2 поступают соответственно отсчеты х(т+3,п) и х(т+ +2,п). Такт S+2. Произведения w(2,l)« xx(m+l,n) и w(l,l)x(m,n) поступают на входы сумматора 6.1, который формирует их сумму С (m,n). Указанная сумма поступает затем на вход сумматора 17.1, на другой вход которого постоянно поступает код нуля. Затем сумматор 17.1 формирует сумму у (т,п) с (m,n)+0, которая с приходом тактового импульса записывается в регистр суммы 18.1. В этом же такте умножителя 10.2 и П,2 формирует произведения 7(4,1) кх(га+3,п) и w(3.1) x(m+2,n), которые записываются в регистры произведения 14.2и 15.2 соответственно. Одновременно в регистры множителя 8.3 и 9.3 поступают отсчеты х(т+5,п) и x(m+4,n) соответственно. Такт S+3. Сумматор 16.2 формируВТ сумму с (m,n)w(4, I). x(m+3,n)+w(3,1) x(m+ +2,п.), которая поступает на вход сумматора 17.2, на другой вход которого с выхода регистра суммы 18.1 поступает у (т,п)( . Сформированная на выходе сумматора 18.1 сумма у (m,n)j,y (m,n), -ьс (m,n)2 записывается затем в регистр 18.2, этом же такте умножителя .10.3 и 11.3 формируют произведения w(6,) x(m+5,n) и w(5,1). x(m+4,n), которые аписываются в регистры 14.3 и 15.3 оответственно. Одновременно в реги5стры 8.4 и 9.4 .поступают отсчеты х(т+7,Г) и х{т+6,п) соответственно. Такт S+K/2. Сумматор 6./К(2-1) формирует сумму с Чт,п),,,,., nv(k-2,l)x(m4k-3,n) + +w(k-3,l)x(ra+k-4,n), которая поступает на вход сумматора 17.К/2--1, на другой вход которого с вькода регистра 18.К/2-2 поступает сумма у (m,n) Сформированная на выходе сумматора 17. сумма у(гл,п)к|., у Чт,п)к/2-2 +с(т,п)к;гзаписывается затем в регистр 18.К/2Одновременно произведения w{k,l) x(m+k-,n) HV7(k-l,l) x(m+k-2,n) за писываются в регистры 14.К/2 и 15,К/2 соответствен1 о. В этом же так те начинается формирование у (m,n). При этом, если номер п столбца - нечетный тогда в формировании у (m,n) участвуют отсчеты массива хС., S), принадлежащие столбцу с четным индек сом t+2 (так как ) , которыепоступают с регистра сдвига, образованного регистрами 4.К/2+1.... 4.К+. Если же номер столбца - четный , тогда п формировгании y(in,n) участвуют элементы xCtT, S), принадлежащие столбцу с нечетным индексом t+i;+l t+3. которые поступают с регистра сдвига, образованного регистрам 3 .К/2ч- . , .3 ,К+1 . Формирование (га,п) начинается с того, что в регистры множителя 8.К/2+1 и 9,К/2+ поступают соответствепно отсчеты x(m+l5 п+1) и x(m,n+). Такт S+2/K-I 1 .. Сумматор 16.К/2 фор мирует сумму с(га5п)к.; , которая поступает па второй вход сумматора 17,К/2, на первый вход которого поступает сумма у (га,п)2-( Сформиро ванное в сумматоре 17,К/2 окончательное значение суь1М л у (m,n) запи сывается затем в регистр суммы 18. ,К/2 2, Б этом же такте произведени w(2,2). x(ra+b,ii+l) и w(l ,2) x(m,n+l) записываются в регистры 14.K/2+i и 15.К/2+1 соответственно. Одновременно в регистры 8,К/2+2 и. 9.К/2+2 пос тупают отсчеты х(т+3,п+1) и х(т+2, n-i-1) соответственно. Такт S+K/2+2. Сумматор 16.К/2+1 формирует сумму с (т11,п)к(г41 w(2,2) x(m+l,n+l)+w(l,2) x(m,n+) , котора поступает па второй вход сумматора 17.К/2+, на вход которого поступае сумма y(iin,n). Сформированная в сум 37fe маторе 17.К/2+1 су.мма у-(ni,n) у(т, п)+с(m,n)7n записывается затем в регистр 18,К/2+1. В этом же. такте в регистре произведения w(4,2)x(m+ +3,п+1) и w(3,2)x(m+2,n+) записываются соответственно в регистры 14.К/2+2 и 15.К/2+2, а в регистры В.К/2+3 и 9.К/3+3 постунагот отсчеты x(m+5,n+l) и x(m+4,n+l) соответственно. Такт , где Q(e-l)K/2, Е 2,3.,,L. Сумматор 16.Q-1 формирует сумму (m,n),,j., w(k-2,(m+k-3, n+E-2)+w(k-3,t-l) x(m+k-4, n+Z-2), которая поступает на вход сумматора 17.Q-1, на другой вход которого с выхода регистра 18.Q-1 поступает сумма ()k/2-Z Затем сформированная в сумматоре 17.Q-1 сумма у. (п1,п)к,г-, (m,n),j..2 +с (т,п) Kf2.| занисывается в регистр 18.Q-1. Одновременно произведения w(k,-)x(m+k-l,n+E-2) и w(k-I ,P-I).x(m+k-2, n+E-2) заЕШСываются в регистры 4,Q и 15.Q соответственно. В этом же такте начинается формирование у (m,n). При этом если номер п столбца - нечетный и Н - нечетное, ши номер столбца четный и 2- четное, тогда в формировании у (m,n) участвуют отсчеты x(t, S), принадлежащие столбцу с нечетным индексом I- t+l, если f - нечетное; I, J - Ч ь .о { t+C+l,ecnH I - четное, которые поступают с регистра сдвига, образованного буферными регистрами 3,Q+1 . . .3.Q+K/2+1 . Если же номер п четный и Е - нечетное, или номер п нечетный и Е - четное, тогда в формировании у (m,n) участвуют отсчеты x(i-, S),, принадлежащие столбцу с четным индексом „ , если F - нечетное; Lt+2, если Е - четное, которые поступают с регистра сдвига, образованного буферными регистрами 4.Q+1...4.Q+K/2+1. Формирование у(га, п) начинается с того, что в регистры множителя 8.Q+1 и 9,Q+1 постунают соответственно отсчеты х(п+1,п+Е-1) и x(m,n+E-|). Такт S+1. Сумматор 16.Q формирует сумму (a,n)ktt w(k, E-l).x(m+k-l, п+Ь2) + +w(k-l,E-l) x(in+k-2, n+e-2). 7 которая поступает на второй вход сум матора 17.Q, на первый вход которого поступает сумма (ni,n) Сфор мированное в сумматоре 17.Q окончательное значение суммы у ,М (m,n) записывается затем в регистр 17.Q. В этом же такте произведения w(2,E)x(m+ ,) и w(l,e) x(m,n+P-l) Записываются в регистры 14.Q+1 и 15.Q+1 соответственно, а в регистры 8.Q+2 и 9.Q+2 поступают соответственно отсчеты x(m+3,n+f-l) и x(m+2,n+|-l). Такт S+2. Сумматор 16. +1 формиру ет сумму с (m,n), w(2,.8) x(m+l , )+w(l, Р) x(m, +n-l), которая посту пает на второй вход сумматора 17.Q+ +1, на вход которого поступает сумма (т,п) Сформированная в сумма торе I7.Q+1 сумма y(m,n) (m, n)x|j +с (m,n) записывается затем в регистр 18.Q+1. Одновременно произве дения w(4,E)x(m+3, n+f-1) и w(3, x(m+2,n+I-l) записываются в регистры 16,Q+2 и 15.Q+2 соответственно, а в регистры 8,Q+3 и 9,Q+3 поступают отсчеты x(m+5,n+I-I) и х(т+4,) соответственно. Такт S+3. Сумматор 16.Q+2 формиру ет сумму сЧт,п) w(A,)x(m+3, п+f-l )+xH3, ) x(ra+2,n+b), которая поступает на вход сумматора I7.Q+2, на другой вход которого поступает сумма у (т,п){ . Сформированная в сумматоре 7,Q+2 сумма y(m,n) у (in,n)(+с (m,n)2 записывается зате в регистр 18,0+2, В этом же такте произведения w(6, Е) х (т+5, ) и w(5,) х(т+4, ) записываются соответственно в регистры 14.Q+3 и 15;Q+3, а в регистры 8.Q+4 и 9.Q+4 поступают отсчеты x(m+7,) и x(m+6,n+J-l) соответственно. Такт S+K/2+1, Сумматор 16,Q+K/2 формирует сумму с (т,п)к,2 , которая поступает на вход сумматора 17,Q+ +К/2, на другой вход которого поступает сумма уЧт,п) j-i - С.формированное в сумматоре 17.Q+K/2 окончательное значение суммы у(т,п)к/2 у (m,n)(j +у (п1,п) записывается затем .в регистр 18, Q+K/2. Таким образом,если L, тогда в. такте с номером S S+Q+K/2+l S+LK/2+l в суммато ре 1 7,LK/2 -формируется окончательное 37 значение cyMNn,i у dii,) у(т,п),, которое записывается в регистр 18.LR/2, откуда поступает на информационный выход устройства. Значения отсчетов y(m,n) выходного массива дляоСК+1 6 тб(м+1)К, ItntNiL-l (гд2 cv; 1 , 2 ,3 . . .) формируются точно так же с той лишь разницей, что на информационные входы устройства поступают отсчеты х(Г, S) входного массива, принадлежащие строкам с индексами (у; К+1 с i(oi+2)K-l. Формула, изобретения Параллельное устройство для вычисления двухмерной свертки, содержащее (L, К - размер матрицы коэффициентов) вычислительных блоков и синхронизатор, причем первый и второй информационные входы Р-го вычислительного блока являются соответственно первым и вторым информационными входами устройства, первьм и второй информационные выходы i-ro (, Р) вычислительного блока подключены соответственно к первому и второму информационным входам (i-l)-ro вычислительного блока, причем i-й (,P) вычислительный блок содержит первый и второй буферные регистры, первый и второй комьгутаторы, первый и второй регистры множителя, триггер, первый и второй регистры коэффициентов, первый и второй умножители, первый и второй регистры произведений, первый и второй сумматоры и регистр суммы, при этом информационные входы первого и второго буферных регистров объединены соответственно с первым и вторым информационными входами первого коммутатора и являются первым и Бторьм информационными входами вычислительного блока, выходы первого и второго коммутаторов подключены к информационным входам соответственно первого и второго регистров множителя, выходы которых подключены к первым входам соответственно, первого и второго умно;га1телей, выходы которых подключены к информационным входам соответственно первого и второго регистров произведений, выход второго регистра произведений одключен к первому входу первого умматора, а выход второго сумматоа подключен к информационному входу егистра суммы, выход которого явля91ется третьим информационным зыходом вычислительного блока, а первый вход второго сумматора является третьим информационным входом вычислительного блока, выходы первого и второго регистров коэффициентов подключены к вторым входам соответственно перво го и второго умножителей, вход триггера является еинхровходом вычислительного блока, причем в каждом вычислительном блоке с номером ) К/2+/} (e-l,3,5...,/J 1,2,...,К/2), прямой выход триггера подключен к управляющим входам первого и второго коммутаторов и является синхровыходом вычислительного блока, а в остальных вычислительных блоках инверс ные выходы триггеров подключены к управляюпщм входам первого и второго коммутаторов и являются синхровыхода ми вычислительных блоков, отличающееся тем, что, с целью 3710Vпрощения устройства, выход синхронизатора подключен к синхровходу первого вычислительного блока, синхровход и третий информационный выход m--ro (, Р-1) вычислительного блока подключен соответственно к синхровходу и третьему информационному входу (in+)-ro вычислительного блока, а третий информационный выход Р-го вычислительного блока являетсяинформационным выходом устройства, причем в i-M вычислительном блоке выходы первого и второго буферньпс регистров подключены соответственно к первому и второму информационным входам второго коммутатора и являются соответственно первым и вторым информационными выходами блока, выход первого регистра произведений подключен к второму входу первого сумматора, выход которого подключен к второму входу второго сумматора.

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

i.P

(риг.1

Hai/aj7O)