Устройство для параллельной обработки видеоинформации

 

СС8ОЗ СОВЕТСНИХ

СООИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (g)) 4 С 06 Р 15/66

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

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3988515/24-24 (22) 12. 12. 85 (46) 23.09.88. Бюл. и 35 (71) Ленинградский институт точной механики и оптики (72) С.E.Äîí÷åíêî, К.И.Кучеренко, E.Ô.0÷èí и А.Ю.Тропченко (53) 681. 3. 019 (088. 8) (56) Заявка ЕПВ Р 149516, кл. G 06 F 15/68, опублик. 1985.

Swartz1ander Е.Е., Gilbert В.К., Reed I.S. Inner product сопьраСегз.

IEEE Transactions on Computers, 1978, Ф 1, р. 21-31. (54) (57) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ

ОБРАБОТКИ ВИДЕОИНФОРМАЦИИ, содержащее

N умножителей и древовидную сеть, содержащую из N-1 сумматоров, входы сумматоров каждой ступени древовидной сети, кроме первой ступени, сое. динены с выходами двух сумматоров предыдущей ступени, выход сумматора последней ступени древрвидной сети является выходом устройства, вход первого сомножителя i-го умножителя, (i=1 Б) соединен с входом загрузки элемента А; устройства, о т л и ч а— ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции определения ранга произвольного элемента вектора, в него введены N мультиплексоров, мультиплексор выбора элемента вектора, блок постоянной памяти, элемент НЕ, N групп элементов И, каждая из которых состоит из 2Q+1 элементов, где Q — разрядность информационных входов умножителей, N элементов ИЛИ, причем первый информационный вход

„„SU„„1425722 А 1

i-го мультиплексора (i=1 N) соединен с входом загрузки элемента В; устройства, вторые информационные входы мультиплексоров соединены с выходом блока постоянной памяти, адресный вход которого соединен с выходом мультиплексора выбора элемента вектора, информационные входы мультиплексора выбора элемента вектора соединены с входами загрузки элементов А;, управляющий вход мультиплексора выбора элемента вектора соединен с входом выбора элемента устройства, выход i-го мультиплексора соединен с входом второго сомножителя i-го умножителя, q-й разряд выхода каждого умножителя (q = 1,2Q), соединен с первым входом

q-ro элемента И соответствующей группы, 2Q-й разряд выхода каждого умно- ( жителя соединен с первым входом (2Я+

+1)-го элемента И соответствующей ф группы, выходы первого элемента И и (2Q+1)-го элемента И каждой группы соединены с первым и вторым входами соответствующего элемента ИЛИ, входы сумматоров первой ступени древовидной сети соединены с выходами соответствующих двух элементов ИЛИ и с выходами соответствующих двух групп

q-х элементов И (q=2,2Q), первые и вторые входы синхронизации умножителей соединены соответственно с первыми и вторым входами синхронизации устройства, вход задания операции устройства соединен с входом элемента НЕ, с управляющими входами мультиплексоров и вторыми входами q-х элементов И каждой группы, выход элемента НЕ соединен с вторыми входами

2Q+1 элементов И каждой группы.

1425722

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

Цепь изобретения — расширение функциональных возможностей за счет выполнения операции определения ранга произвольного элемента вектора.

На чертеже представлена схема устройства.

Устройство содержит умножители 1, мультиплексоры 2, мультиплексор 3 выбора элемента вектора, блок 4 пос- 15 тоянной памяти, элементы И 5 и 6, элементы ИЛИ, 7, сумматоры 8, элемент

НЕ 9, входы 10 и 11 загрузки векторов устройства, вход 12 задания операции. устройства, выход 13 устройства, вхо- 2Q ды 14 и 15 синхронизации устройства, .вход 16 выбора элемента вектора устройства.

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

При выполнении операции скалярного произведения двух векторов к

R =,> А;В; посредством входа 12 устройства мультиплексоры 2 включены в режим переда-! чи элементов вектора В на информационные входы умножителей 1; Передача сигналов с выходов умножителей t че- 35 рез элементы И 5 и элементы ИЛИ 7 на входы сумматоров 8 разрешена. Та.ким образом, в каждом умножителе 1 выполняется операция умножения элементов векторов, результаты произведений транслируются через элементы

И 5 и элементы ИЛИ 7 на входы сумматоров 8 древовидной сети, на выходе

13 устройства формируется результат операции скалярного произведения

45 двух векторов (1).

Так как большинство стандартных умножителей содержат внутренние регистры приема входных данных и выходные регистры, запись элементов векто-50 ров А и В во внутренние регистры умножителей 1 синхронизируется синхросигналом, поступающим с входа 14 устройства на входы синхронизации умножителей 1, запись произведения в каж- 55 дом умножителе 1 во внутренний регистр производится по синхросигналу, поступающему на второй вход синхронизации

Aj ° К(А ) «» P, (3) умножителей 1 с входа 15 устройства.

Синхросигнал, поступающий на второй вход синхронизации умножителей 1, сдвинут по времени относительно синхросигнала, поступающего на первый вход синхронизации умножителей 1.

При выполнении операции определения ранга элемента вектора А посредством сигнала на входе 12 устройства мультиплексоры 2 установлены в режим трансляции данных с выхода блока 4 на информационные входы умножителей передача информации через элементы

И 5 запрещена, посредством элемента

НЕ 9 разрешена передача данных через элементы И 6. Так как элементы И

6 соединены со старшими (2Q-ми) разрядами выходов умножителей 1, осуществляется трансляция содержимого 2g-õ разрядов вьмодов умножителей 1 через соответствующие элементы И 6 на входы соответствующих элементов ИЛИ 7, а так как выходы элементов ИЛИ 7 соединены с младшими разрядами входов соответствующих сумматоров 8 первой ступени древовидной сети, то осуществляется трансляция содержимого 20-х разрядов выходов умножителей 1 через соответствующие элементы 6 и 7 на младшие разряды входов соответствующих сумматоров 8. Посредством управляющего кода, поступающего с входа

16 устройства на управляющие входы мультиплексора 3 выбора элемента вектора, осуществляется передача заданного элемента с входа 10 загрузки элемента на выход мультиплексора 3 .и, соответственно, на адресный вход блока 4.

Операция определения ранга R; элемента вектора А в устройстве реализуется следующим образом. Определение ранга элемента вектора А выполняется посредством подсчета числа элементов, . меньших и равных элементу А н

R =+(А а А;) (2)

5=

1, если А; А, где

О, если А;> А;

Пля реализации выражения (2) необходимо операции сравнения выполнять в умножителях 1. Для достижения этой цели величина А; заменяется на такое значение K(A;), что для А; 6 А; выполняется условие

1425722 а для A А; — усл ови е

А ° К(А;) > P. (4) 35 (5) С =N-R

Для определения истинного значения ранга R, элемента А во внешнем 4 устройстве по отношению к рассматриваемому устройству производится операция нормирования

R; =N-C„ °

Значение P выбирается таким, чтобы

5 результат сравнения А и A опреде3 лялся по старшему разряду произведения А К(А;), т.е. по старшему разряду выхода умножителя 1. Преобразование К(А;) выполняется в блоке 4;

А,, переданное с входа 10 через мультипчексор 3 на адресный вход блока 4, определяет адрес ячейки блока 4, в которой записано значение К(А;) . В блоке 4 хранятся заранее вычисленные значения К(А,) для всех допустимых значений А,. С выхода блока 4 величина К(А;) поступает на информационные входы умножителей 1 и умножается. на соответствующие элементы вектора А.

Для элементов вектора А, больших элемента А,, старший разряд выхода соответствующего умножителя 1 будет равным единице, а для элементов вектора 25

А, меньших А; старший разряд выхода соответствующего умножителя 1 равен нулю. Так как передача данных через элементы И 5 запрещена, то будет суммироваться древовидной сетью суммато- 3Ъ ров 8 содержимое только старших разрядов выходов умножителей 1. Содержимое выхода 13 устройства определит число элементов С,, больших элемента

А °, В случае использования в устройстве Инверсного представления элементов вектора А (инверсия элементов вектора А может выполняться посредством устройства, входящего в состав измерительно-вычислительного комплекса и являющегося внешним по отношению к устройству параллельной обработки видеоинформации) операции сравнения реализуются следующим образом. Значения К(А;) подбираются таким образом, что для А> с A;Ф т е. Для А> А В

1 выполняется условие

А1 К(А1) > P, (7) а для А; > А;, т.е. для А. а А,, выполняется условие

А К(А;) с (8)

При использовании инверсного представления элементов вектора А для элементов А1 6 А; старшие разряды выходов умножителей 1 равны единице, а для элементов А А старшие разряды выходов умножителей 1 равны нулю. Посредством древовидной сети сумматоров

8 осуществляется суммирование числа единичных старших разрядов выходов умножителей 1, что эквивалентно определению ранга элемента вектора А, Посредством управляющего кода, поступающего с входа 16 устройства на управляющие входы мультиплексора 3, всзможно задать произвольный элемент вектора А, для которого можно онределить его ранг. Синхронизация записи данных во внутренние регистры умножителей 1 и синхронизация записи произведений во внутренних регистрах умножителей 1 осуществляется посредством синхросигналов (сдвинутых по времени), поступающих на входы синхронизации умножителей 1 с входов 14 и 15 устройства.

1425722

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

Редактор Н.Тупица Техред М.Дндык Корректор С.Черни

Заказ 4773/49 Тираж 704 Подписное

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

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

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