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

(54) ПАРАЛЛЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ВЫ ЧИСЛЕНИЯ ДВУХМЕРНОЙ. СВЕРТКИ(57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе време-. ни, Цель изобретения - упрощение устройства. Поставленная цель достигается за счет того, что устройство состоит из Р=ЬК/2 (Ь, К - размер матрицы коэффициентов) вычислительных блоков и синхронизатора, причем каждый вычислительный блок содержит два сумматора, два умножителя, два буферных регистра, регистр суммы, два коммутатора, триггер, два регистра множителя, два регистра коэффициентов, два регистра произведений и соответствующие связи между узлами устройства. 3 ил. СУДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции(56) Авторское свидетельство СССР В 1057940, кл. О 06 Р 7/38, 1983.Кцщ Н.Т., Р.сагй К.Ь. НагЫаге рре 11 пез Еог шц 1 г,Ышепз 1 опа 1 соптто 1 цгоп апй гезашр 1 дпд, 981, 1 ЕЕЕ, Сошрцйег Яос 1 еу ИагЕзКор оп Сошрцгег АгсЬдгесгцге Еог Раггегп Апа 1 уз 1 з апй 1 шаее ПагаЬазе Мага 8 ешепг, 1981, р. 273-278. 3 Н 17/06 О 06 Р 15/35269237 50 Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времениЦелью изобретения является упрощение устройства.На фиг. 1 изображена общая схема устройства; на фиг, 2 - схема вычислительного блока; на фиг, 3 - блоксхема алгоритма работы 1-го вычислительного блока (ц=1,2 Р).Устройство содержит Р=ЕК/2 вычислительных блоков 1.1,1.21.Р и синхронизатор 2.Каждьп из вычислительных блоков 1. (фиг. 2) содержит первый З.ц и второй 4.с буферные регистры, первый коммутатор 5.1, триггер б.ц управления, второй коммутатор ,с 1, первый 8. и второй 9. регистры множителя, первый 10.с и второй 11,Ч умножителя, первый 12. и второй 13. регистры коэффициентов, первый 14.Ч и второй 15, регистры произведения, сумматоры 1 б.си 1.о, регистр 8 суммы,Устройство работает следующим образом.В исходном состоянии в регистрах коэффициентов 12. и 13. записаны коэффициенты ы(1 с, 1), такие, что Р= 2(1-1)1., где 1 а" обозначаетСближайшее не меньшее целое для а. По сигналу пПуск устроства, который поступает в тексте с номером 1, в этом же такте на первый информационный вход устройства со скоростью одного отсчета на такт начинают поступать те отсчеты нечетных столбцов входного с массива х (о, Б), которые принадлежат строкам от первой до (2 К)-й. Указанье элементы входного массива постуают в следующем порядке: х (1,1); х (2,1)х(2 К,1), х(1,3), х(2,3)х(2 К,.3),. причем после передачи в такте с номером Т,/2 К-го элемента некоторого нечетного столбца, первый элемент следующего нечетного столбца поступаеттолько в такте с номером Т, +2, В такте с номером К+1 на второй информационный вход устройства. со скоростьюодного отсчета на такт начинают поступать те отсчеты четных столбцоввходного массива, которые принадлежат строкам от первой до (2 К)-й Указанные элементы массива х(о, 8) пос 5 10 15 20 25 30 35 Ю 45 тупают в следующем порядке: х(1,4), х(2,4)х(2 К,4), причем после передачи в такте с номером Т (2 К)-го2 элемента некоторого четного столбца, первый элемент следующего четного столбца поступает только в такте с номером Т +2. Любой отсчет входного массива, поступающий на первый или второй информационные входы устройства, с приходом каждого тактового импульса сдвигается на одну позицию в регистре сдвига, образованном соответственно первыми З,Р, З.Р 3.1 или вторыми 4.Р, 4,Р 4.1 буферными регистрами, Таким образом, в такте с номером Р+1 первый элемент (1,1) входного массива хранится в буферном регистре 3.1 и начинается формирование отсчетов входного массива у(ш,п) для шбК, и 11-,+1. При этом в такте с номером Рна вход разрешения счета синхронизатора поступает сигнал "Пуск", Синхронизатор 2 работает как делитель частоты с коэффициентом деления К, причем в тактах с номерами Т=Ж+г+Р- (где г.=0,2,4; г=1,2, ,К) на выходе синхронизатора 2 вырабатывается уровень логической и и1 , а в остальных тактах с номерами Т=(1+1)К+г+Р- уровень логического и и0 , Управляющий сигнал с выхода синхронизатора 2 передается посредством триггеров 6.1,6.2,6.Р на управляюще входы коммутаторов 5.1, 7.1, 5,2, 7,2, ,5.Р, 7.Р. При этом в вычислительных блоках 1.Ч, номера Ч которых удовлетворяют условию (2), на управляющие входы коммутаторов 5. и .и поступает сигнал с прямого выхода триггера б.ц, а в остальных блоках 1.1, номеракоторых удовлетворяют условиюг=(-1)К/2+3; =2,4,6,; Р =1,2,К/2 (3) на управляющие входы коммутаторов 5, и 7. поступает сигнал с инверсного выхода триггера б.ч. В результате этого в течение такта с номером Т таким, что Т-Ч=ТК+г+Р (4) в вычислительных блоках 1.с 1, номера которых удовлетворяют условию (2), первьп 5. и второй .с коммутаторы с выходов первого 3.1+ и первого 3. буферых регистров пропускают на входы соответственно первого 8. и второго 9,с регистров множителя элементы х (Т+ Р, 2+г) и х (+ 1 2 +г 3 1269 -2) соответственно, принадлежащие нечетному столбцу с индексом г+ 1 (Р=1,2,3), а в остальных блоках 1.Ч коммутаторы 5,( и .о с выходов второго 4,ц+ и второго 4.ц буферных регистров пропускают на входы соответственно регистров 8.ци 9.о элементы х(+1, 23+г) и х(+0, 23+г) соответственно, принадлежащие четному столбцу с индексом +1 (1=2,4,6). О В течение остальных тактов таких, чтоТ-(1= (г+1) К+г/Р (5)в вычислительных блоках 1.п, номеракоторых удовлетворяют условию (2), 15коммутаторы 5. и 7.( с выходов буферных регистров 4.ц+1 и 4.( пропускают на входы соответственно регистров 8.ц и 9. элементы х(г+ 0+1, 2+г --1) и х(.+1+1, 2+г) соответственно, принадлежащие четному столбцус индексом С+1+1, а в остальных блоках 1.ц коммутаторы 5.ц и 7.ц с выходов регистров З.Ч+1 и 3. пропускаютна входы соответственно регистров 258,( и 9.( элементы х(С+0+1, 2+г) и х(Т+К+1., 21(+г) принадлежащие нечетному столбцу с индексом +1:+1.С приходом очередного тактового импульса указанные элементы входного 30массива записываются в регистры множителя 8.с и 9Рассмотрим формирование произвольного отсчета у(ш,п) выходного массива для пБ-Ь+1, ш К согласно выражению,е у(ш,п)= . у (ш,п),е= егде у (ш,п)=Е ч(1 с, Я)х(ш+1 с, и+д).,Формирование отсчета у (ш,п) начинается в такте с номером Я=Р+К(п)+ +ш, причем сначала формируется у (ш, и), При этом, если номер и столбца - нечетный, тогда в Формировании у(ш, и) участвуют отсчеты входного массива х, Я), принадлежащие столбцу с нечетным индексом Я=п=й+1=Е+ (так как е=1), которые поступают с регистра сдвига, образованного буферными регистрами 3.13.К/2+1, Если же номер и столбца - четный, тогда в формировании у (ш.п) участвуют отсчеты входного массива, при= надлежащие столбцу с четным индексом Я(:(п=+Р+1=+2, которые поступают с регистра сдвига, образованного буфер 237 4ными регистрами 4.14.К/2+1, Вдальнейшем описание работы устройства ведется по тактам,Такт Я. В первый 8,1 и второй 9.регистры множителя поступают соответственно отсчеты х(ш+1,п) и х(ш,п)Такт Я+1. Множители х(ш+1,п) их(ш,п) с выходов регистра 8.1 и 9.1поступают на вторые входы умножителей 0,1 и 11. соответственно, напервые входы которых с выходов первого 12,1 и второго 13.1 регистровкоэффициента поступают коэффициентыы(2,) и ч(1,1) соответственно. Затем умножители 10,1 и 11.1 формируютпроизведения ч(2,1) х(ш+1,п), которые с приходом тактового импульса записываются соответственно в первом14.1 и втором 15.1 регистрах произведения. В этом же такте в регистрымножителя 8.2 и 9.2 поступают соответственно отсчеты х(ш+З,п) и х(ш++2,п).Такт Я+2. Произведения ът(2,1)хх(ш+1,и) и ъ 1,1) х(ш,п) поступаютна входы сумматора 16.1, который Фор(мирует их сумму С (ш,п), Указаннаясумма поступает затем на вход сумматора 17.1, на другой вход которогопостоянно поступает код нуля. Затемсумматор 17.1 формирует суммуу(ш,п) =с(ш,п)+О,которая с приходом тактового импульса записывается в регистр суммы 18.1.В этом же такте умножителя 10.2 и11,2 формирует произведения ь 4,1)х(ш+З,п) и ч(3.1) х(ш+2,п), которыезаписываются в регистры произведения14.2 и 15.2 соответственно. Одновременно в регистры множителя 8.3 и 9.3поступают отсчеты х(ш+5,п) и х(ш+4,п)соответственно.Такт Я+3. Сумматор 16.2 Формирует суммус (ш,п) =ъ 4, 1)1 х(ш+З,п)+ът(3,1) х(ш+ +2,п),которая поступает на вход сумматора .2, на другой вход которого с выхода регистра суммы 18.1 поступает у (ш,п) Сформированная на выходе сумматора 181 суммау (ш,п)., =у (ш,п), +с (ш,п)записывается затем в регистр 18,2.В этом же такте умножителя 10.3 и 11.3 формируют произведения ы(6,1) х(ш+5,п) и ю(5,1)х(ш+4,п), которыезаписываются в регистры 14.3 и 15,3 соответственно. Одновременно в реги+ът(1 с,1)х(в+1 с,и),которая поступает на вход сумматора17.К/2-1, ца другой вход которогос вьгсода регистра 18.К/2-2 поступает Осумма У (п 1 к и) к 1 г г е Сфорл(иров е(инаяна выходе сумматора 17.К/2-1 сумма( (У (Г 1 эи) к(г-( У (ви)к 1 г-г +с (птки)к 1 г-(записывается затем в регистр 18,К/2-1Одновременно произведения ьг(1 с,1) 5х(тп+1 с,и) и ьг(1 с,1) х(гп+1 с,и) записываются в регистры 14.К/2 и15.К/2 соответственно. В этом же такгте начинается формирование у (,в,и).11 ри этом, если номер и столбца - негчетный тогда в Формировании у (в,и)участвуют отсчеты массива х(ьБ),принадлежащие столбцу с четным индексом Б=тт+1=+.=т:+2 (так как т=:2) которыепоступают с регистра сдвига, 25образованного регистрами 4.К/2+14.К+1, Если же номер столбца -четформироватти(т у (тп, и)участвуюг элементы х( ( Я 1, принад -лехтат 11(ие столбцу с нечетным индексолт 30Я=-и+1:+1+1 т+3. которые поступаютс регистра сдвига, образоваццого регцстралпт З.К/2+13.К+1. Формирование у" (в,и) начинается с того, что врегистры множителя 8,К/2+1 и 9,К/2+1поступают соответственно отсчетых(и+1, и+1) и х(тп,п+1).Такт Я+2/К.(1. Сумматор 16,К/2 формирует сул(му с (в,и)1 г , которая по-.стуг(ает ца второй вход сумматора 4017.К/2, ца первый вход которого поступает сумма у (тп,и)г ( , Сформированное в сумматоре 17.К/2 окончательное значение сул,мы у (пт и) запи 1сывается затем в регистр суммы 18,,К/2 -2, В этом ке такте произведенияъг(2,2) х(тп+,и+1) и тг(1,2) х(в,и+1)записываются в регистры с(.К/2+1 и15.К/2+1 соответственно, Одновременно и регистры 8.К/2+2 и 9.1(/2+2 поступают отсчеты х(в+З,и+1) и х(в+2,и+1) соответствешто.Такт Б+К/2+2. Сумматор 16,К/2+1фор.(ирует сумму с (в,и)к(г( =:ьг(2,2)х(тп+1,и+ )+ьт(1,2) х(в,и+1), котораяпоступает ца второй вход сумматора17,К/2+1, на вход которого поступаетсумма у (тп,и), Сформированная в сум 237 Ьматоре 17.К/2+1 слл(л(а у(в,п) =у (тп,и)+с (гп,и)г записывается затемв регистр 18.К/2+1. В этом же тактев регистре произведения ч(4,2)х(тп+=2,31 Сумматор 16.с 1-1 Формируетсуммус (тп, и) к (г-( =ът (1 с, 1-1). х (в+1 с-З,и+2-2)+ч(1 с-З, Е- ) х(тп+1 с, и+К),которая поступает на вход сумматора17.Я, на другой вход которого с выхода регистра 18.(-1 поступает суммаУ (ви)к(г-г . Затем сформированЕ ная в сумматоре 7.ЯсуммаЕ.( Е(тп,и) к(г 1записывается в регистр 18.(1-1. Одновременно произведения тг(1 с, с)х(в+1 с,и+7-2) и ът(1 с,2-1) х(в+с, и+0-2)записываются в регистры 14,(;1 и 15.(1соответственно. В этом же такте начиЙается формирование у (в,и). При этомеесли номер и столбца - нечетный иь - нечетное, или номер столбца -четный и и - четное, тогда в Формировании у (гп,и) участвуют отсчеты х(с,Я), принадлежащие столбцу с нечетныминдексом+.г, если г. - нечетное;1+ 1+1,если 3 - четное,которые поступают с регистра сдвига,образованного буферными регистрамиЗ.Я+1 З.Я+К/2+1. Если же номер и -четный и Р - нечетное, или номер и -нечетный и 1 - четное, тогда в Формировании у (тп,и) участвуют отсчетых(ь, Б), принадлежащие столбцу с четным индексом+1+1, если . - нечетное;Я=и+1-1=Т+2, если ь - четное,которые поступают с регистра сдвига,образованного буферными регистрами4,с 1+14.С+К/2+1. Формирование у (в,Ри) начинается с того, что в регистрымножителя 8.(.+ и 9,(.+ поступают соответственно отсчеты х(и+1,и+И) их(тп,и+К-).Такт Б+1. Сумматор 16,Я формирует суммуе-(+тг(1 с, 6-1) х(в+1 с, и+ 0-2), 9 126 ч 2 ется третьим информационным выходом вычислительного блока, а первый вход второго сумматора является третьим информационным входом вычислительного блока, выходы первого и второго регистров коэффициентов подключены к вторым входам соответственно первого и второго умножителей, вход триггера является синхровходом вычислительного блока, причем в каждом вы числительном блоке с номером и (-1) К/2+(Г 1,3,5,(3 "1,2. К/2), прямой выход триггера подключен к управляющим входам первого и второго коммутаторов и является синхровы ходом вычислительного блока, а в остальных вычислительных блоках инверсные выходы триггеров подключены к управляющим входам первого и второго коммутаторов и являются синхровыхода ми вычислительных блоков, о т л и - ч а ю щ е е с я тем, что, с целью 37 1 Оупрощения устройства, выход синхронизатора подключен к синхровходу первого вычислительного блока, синхровход и третий информационный выходв-го (ш=1, Р) вычислительного блокаподключен соответственно к синхровходу и третьему информационному входу(щ+1)-го вычислительного блока, атретий информационный выход Р-го вычислительного блока является.информационным выходом устройства, причемв -м вычислительном блоке выходыпервого и второго буферных регистровподключены соответственно к первомуи второму информационным входам второго коммутатора и являются соответственно первым и вторым информационными выходами блока, выход первогорегистра произведений подключен квторому входу первого сумматора, выход которого подключен к второму входу второго сумматора,1269237 РР 3 тель А, БаЛ.Олейник СостРедактор В, Иванова Техр Тираж 816рственногообретений и, Ж, Рауш ПодписноеССР омитетаоткрытииская на д, 4 Проиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная 4 каз 6044/56 ВНИИПИ по 113035