Ячейка однородной структуры Советский патент 1992 года по МПК G06F7/00 

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

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

Ё

VI VJ

00

VI ел VI

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

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

Наиболее близкой к предлагаемой по технической сущности является ячейка однородной структуры 2, содержащая мультиплексор, три демультиплексора,

арифметико-логический блок и блок настройки, содержащий счетчик, D-триггер, элемент И, два элемента НЕ, RS-триггер и четыре элемента И-НЕ, причем информационные входы первой группы ячеек сое0 динены с информационными входами мультиплексора, выход которого соединен с первым входом арифметико-логического блока, первый выход которого соединен с информационным входом первого демультиплек5 сора, управляющие входы которого соединены с одноименными входами мультиплексора, первым и вторым выходами счетчика, выходы которого являются первым и вторым выходами блока настройки,

0 третий выход которого соединен с выходом D-триггера, выходы первого демультиплексора соединены с информационными выходами первой группы ячейки, первый вход блока настройки соединен с первыми входа5 ми элемента И, первого элемента И-НЕ и входом первого элемента НЕ, выход которого соединен с информационным входом D- триггера, инверсный выход которого соединен с вторым входом элемента И, вы0 ход которого соединен со счетным входом счетчика, вход сброса которого соединен с одноименными входами D-триггера и RS- триггера и входом начальной установки блока настройки, второй вход которого

5 соединен с входом второго элемента НЕ и вторым входом первого элемента И-НЕ, выход которого соединен с единичным входом RS-триггера, прямой выход которого соединен с первыми входами второго, третьего и

0 четвертого элементов И-НЕ, вторые входы которых соединены соответственно с первым и вторым входами счетчика и прямым выходом D-триггера, установочные входы которых соединены соответственно с выхо5 дами второго, третьего и четвертого элементов И-НЕ, первый и второй выходы блока настройки соединены с управляющими входами второго и третьего демультиплексо- ров, входы синхронизации которых

0 соединены с одноименными входами мультиплексора и первого демультиплексора и с третьим выходом блока настройки, первый и второй входы которого соединены с настроечными входами первой и второй групп.

5 ячейки и информационными входами второго и третьего демультиплексоров, выходы которых соединены с настроечными выходами первой и второй групп ячейки, информационные входы второй группы которой соединены с вторым входом арифметикологического элемента, второй выход которого соединен с информационными выходами второй группы ячейки.

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

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

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

соответственно со входом первого элемента НЕ и выходом второго элемента НЕ блока настройки, первый и второй входы второго элемента И которого соединены соответственно с выходом второго триггера блока на- стройки и входом разрешения записи ячейки.

На фиг. 1 представлена функциональная схема ячейки однородной структуры; на фиг. 2 - фрагмент вычислительной структуры на основе предлагаемой ячейки; на фиг. 3 - пример выполнения корреляционной обработки информации.

Ячейка однородной структуры (фиг. 1) содержит мультиплексор 1 и блок 2 настройки, который содержит счетчик 3, триггеры 4, 5, элементы И 6-9 и элементы НЕ 10. 11, а также информационные входы 12.1-12,4 группы, информационные выходы 13.1-13.4 группы, причем информационные входы 12.1-12.4 группы соединены с входами мультиплексора 1, а информационные выходы 13.1-13.4 группы подключены к прямому выходу триггера 4 блока 2 настройки. Информационный вход 14 и вход разрешения записи 15 ячейки соединены соответственно с первыми входами элементов И б и 7, информационный вход 16 ячейки соединен с первым входом элемента И 9 и через элемент НЕ 11 - с первым входом элемента И 8, а выход элемента И 6 подключен к второму входу элемента И 8 и через элемент НЕ 10 - к второму входу элемента И 9 блока 2 настройки. Выходы элементов И 8 и 9 соединены соответственно с вычитающим и суммирующим входами счетчика 3 блока 2 настройки, тактовый вход которого подключен к тактовому входу триггера 4 и тактовому входу 17 ячейки, вход установки в нуль триггера 4 соединен с входом сброса 18 ячейки, выход признака меньше нуля счетчика 3 блока 2 настройки соединен с входом установки в нуль триггера 5 блока 2 настройки, вход установки в единицу которого подключен к входу обнуления счетчика 3 и входу начальной установки 19 ячейки. Выход триггера 5 блока 2 настройки соединен с вторым входом элемента И 7, выход которого подключен к входу установки в единицу триггера 4 блока 2 настройки, информационный вход которого подключен к выходу мультиплексора 1, управляющие входы которого соединены с настроечными входами 20.1, 20.2 ячейки.

Однородная структура (фиг. 2) содержит матрицу ячеек 21.I.J, где I - номер строки, j - номер столбца матрицы, Информационные входы 14 и 16 каждой ячейки 21 подключены к информационным шинам 22 и 23 матрицы соответственно, управляющие входы 15,17,

18, 19 - к управляющим шинам 24-27 матрицы соответственно, настроечные входы 20.1, 20.2 - к шинам 28 настройки матрицы. Информационные выходы 13.1-13.4 каждой ячейки 21 соединены с информационными входами 12.1-12.4 ячеек 21. являющихся соседними справа, сверху, слева, снизу,

Ячейка однородной структуры работает следующим образом.

Перед началом решения задачи произ- водится установка в нулевое состояние триггера 4 по сигналу на входе 18 сброса ячейки, а затем запись в триггер 4 информации, поступающей по информационному входу 12.1 в мупьтиплексор 1 при наличии на управляющих входах 20.1-20.2 мультиплексора 1 соответствующих настроечных сигналов. Через вход 12.1 ячейки последовательно разряд за разрядом заносится входная информация и продвигается к вы- ходу 13.1 ячейки. Благодаря этому процессу обеспечивается последовательность запись информации по строкам в однородной- вычислительной структуре (фиг. 2). После завершения цикла записи информации работа ячейки может протекать в двух режимах: транзитном и операционно-трэнзитном.

Транзитный режим. В этом режиме осу-, ществляется транзит входных данных через мультиплексор 1 по одному из четырех вхо- дов 12.1-12.4 ячейки, определяемому настроечной информацией на входах 20.1-20.4 ячейки. Таким образом, в однородной вычислительной структуре (фиг. 2) возможен сдвиг информации вправо, влево, вверх, вниз.

Операционно-транзитный режим. В этом режиме происходит обработка данных, поступающих с определенных информационных входов 12.1-12.4, 14 16 ячейки и выдача результата на информационном выходе 13,1 ячейки. Исходные данные подвергаются корреляционной обработке, в процессе которой определяется область множества ячеек 21 однородной вычисли- тельной структуры (фиг. 2), в которых взаим- но-корреляционная функция (ВКФ) текущего изображения F и эталонного изображения G превышает заданный порог Д,

После записи во все ячейки 21 одно- родной вычислительной структуры (фиг. 2) соответствующих значений текущего изображения F {foofN-i,M-i}, где N, М - количество строк и столбцов однородной вычислительной структуры, процесс корре- ляционной обработки начинается с поступления на вход 19 начальной установки ячейки управляющего сигнала, который сбрасывает в нулевое состояние счетчик 3 и устанавливает в единичное состояние триггер 5 блока 2 настройки. Затем синхронно с тактовыми импульсами по входам 14 каждой ячейки поступает последовательность

G {googn-i,m-i), где n,m - размерность

поля эталонного изображения G, а на вход 16 каждой ячейки поступает серия импульсов Л { . сумма единичных значений которых задает степень отличия текущего изображения F от эталонного изображения G, д {0,1}, С помощью логического элемента И 6 блрка 2 настройки выполняется перемножение .величины с текущим значением gi последовательности G, где I - номер тактового импульса, ,.,.,1, i 0N-1,J 0М-1. Поскольку выходы

элементов И 8 и 9 соединены соответственно с вычитающим и суммирующим входами счетчика 3, то выполняются следующие действия в ячейках с приходом переднего фронта 1-го тактового импульса при определенном соотношении величин fy, gi. так, при выполнении условия f,j gr 0, д 1 происходит увеличение на единицу содержимого счетчика 3; при соотношении, когда ту gi 1, 5i 0, - уменьшение на единицу содержимого счетчика 3; aja случае, когда fij gi 0, 5| 0, а также fij gi 1, 3| 1 содержимое счетчика 3 не изменяется. В момент, когда содержимое счетчика 3 становится меньше нуля, единичный сигнал на его выходе признака меньше нуля приведет к обнулению триггера 5. Через L тактов, где , в триггерах 5 будут зафиксированы позиции, в которых ВКФ двумерных изображений F и G будут превышать заданный порог Д. С приходом управляющего сигнала на вход 15 разрешения записи ячейки произойдет запись во всех ячейках информации из триггера 5 в триггер 4 блока 2 настройки. Пример выполнения корреляционной обработки информации в предлагаемой однородной структуре представлен для случая, когда (фиг. За) и (фиг. 36). В процессе корреляционной обработки содержимое всех ячеек 21 однородной вычислительной структуры будет сдвигаться влево, вверх и вправо по заднему фронту соответствующих тактовых импульсов согласно приведенному на фиг. 36 примеру сканирования эталонного изображения G (показано стрелками). В соответствии с принятым сканированием эталонного изображения G, но в противоположном направлении сдвигается текущее изображение F. На фиг. Зв приведена реальная картина корреляционной обработки в однородной вычислительной структуре размерностью (N+n-1)x(M+m-1)6x6 для примера (фиг. За, б) по тактам с указанием окна размерностью N х N (фиг. Зг), информация в котором совпадает с данными на фиг. Зв.

При указанном сканировании эталонного изображения G на информационный вход 14 каждой ячейки однородной вычислительной структуры поступает последовательность сигналов 1001 10010}, а на информационный вход 16 - последовательность сигналов Д {100000000}, т.е. в результате должна быть определена область множества ччеек однородной структуры размерностью NxM, где параметр

L-1 Л Х-.1 в Данном случае равный едини Щ)

це, при неотрицательном значении содержимого счетчика 3 и соответствующем единичном значении триггера 5 определяет местонахождение левого верхнего углового отсчета фрагментов изображения в поле текущего изображения F. совпадающих с точ- ностью до Д отсчетов с эталонным изображением G. Таким образом, при Д 1 определяется область множества точек текущего изображения F, соответствующих левому верхнему угловому отсчету тех фрагментов текущего изображения F, отличие которых от эталонного изображения G не превышает одного отсчета.

С приходом нулевого тактового импульса (фиг. Зг) по его переднему фронту в счетчике 3 тех ячеек однородной структуры, где fij , выполняется увеличение на единицу ехо содержимого, а в остальных ячейках, где fij , состояние счетчика 3 остается без изменений, поскольку в течение этого такта 50 1. По заднему фронту нулевого тактового импульса происходит сдвиг влево содержимого всех, ячеек однородной структуры, С целью сохранения информации о текущем изображении F при его сдвиге размерность однородной структуры должна быть не меньше (N+n-1) x (M+m-1). На 1-м, 2-м, 5-м. 6-м, 8-м тактах не происходит изменения содержимого счетчиков 3 всех ячеек однородной структуры, поскольку для 1 1, 2, 5, 6. 8, следовательно, fij gi 0 и 6 0. На всех тактах, когда , ,4,7, с учетом трго, что д 0. при выполнении условия fy не происходит изменения состояния счетчиков 3 в соответствующих ячейках однородной структуры, а при условии, что fij , выполняется уменьшение на единицу содержимого соответствующих счетчиков 3. На фиг. Зв показаны поля текущего изображения F с соответствующим сдвигом информации, а на фиг. Зг - содержимое счетчиков 3 соответствующих ячеек однородной структуры размерностью NxM,

Таким образом, на 7-м гакте формируется окончател:-ный результат корреляционной обоаботки текущего изображения F, который свидетельствует о том. что ячейки

однородной структуры с координатами 0,0 и 1,1 составляют область левых верхних угловых отсчетов (согласно выбранному способу сканирования эталонного изображения G) двух фрагментов текущего изображения F,

искажения которых по сравнению с эталонным изображением G не превышают одного отсчета. Таким образом, только при условии Д- 0 можно определить фрагменты текущего изображения F, полностью совпадающие с эталонным изображением G. В случае, когда Д 0, в область зафиксированных в соответствующих ячейках однородной структуры начальных отсчетов входят как начальные отсчеты эталонного

изображения G в поле текущего изображения F, у которого искажения равны нулю, так и начальные отсчеты искаженного эталонного изображения G с искажениями 1, 2 Д . Начальные отсчеты обнаруженных

фрагментов изображения F с искажениями в пределах Д фиксируются наличием единичного сигнала на выходе триггера 5 в соответствующих ячейках однородной структуры. В дальнейшем координаты начальных отсчетов обнаруженных фрагментов изображения F можно определить в процессе работы всех ячеек в транзитном режиме, т.е. путем сдвига полученной информации в однородной структуре.

Формула изобретения Ячейка однородной структуры, содержащая мультиплексор и блок настройки, содержащий два триггера, счетчик, два

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

выход второго элемента И соединен с входом установки в 1 первого триггера блока настройки, выход которого является выходом ячейки, настроечные входы которой соединены с управляющими пходами мультиплексора, выход которого соединен с информационным входом первого триггера блока настройки, тактовый вход которого соединен с тактовым входом счетчика блока настройки и тактовым внодом ячейки, вход сброса которой соединен с входом установки в О первого триггера блока настройки, выходы третьего и четвертого элементов И которого соединены соответственно с вычитающим и суммирующим входами счетчика блока настройки, выход признака Меньше нуля счетчика соединен с входом установки в1 О второго триггера блока настройки, вход Начальной установки ячейки соединен с входом обнуления счетчика и входом уста0

5

новки в 1 второго триггера блока настройки, выход первого элемента И которого соединен с входом второго элемента НЕ и первым входом третьего элемента И блока настройки, второй вход третьего элемента И которого соединен с выходом первого элемента НЕ блока настройки, первый и второй входы четвертого элемента И которого соединены соответственно с входом первого элемента НЕ и,выходом второго элемента НЕ блока настройки, первый и второй входы второго элемента И которого соединены соответственно с выходом второго триггера блока настройки и входом разрешения записи ячейки.

Изобретение относится к вычислительной технике и может быть использовано для построения однородных структур, например матричных и систолических процессоров. Цель изобретения - расширение функ- циональных возможностей. Ячейка однородной структуры содержит мультиплексор и блок настройки, состоящий из счетчика, первого и второго триггеров, элементов И и НЕ, группу информационных входов, группу информационных выходов, информационные входы, настроечные входы, управляющие входы. Однородная структура, выполненная на предлагаемых ячейках, обладает функциональными возможностями, позволяющими использовать ее для корреляционной обработки двумерных изображений. 3 ил.

Dili

i г