Ассоциативная ячейка памяти Советский патент 1991 года по МПК G11C15/00 

(21)4673702/24

(22)04.04.89

(46) 15.03.91. Бюл. № 10

(71)Таганрогский радиотехнический институт им. В.Д.Калмыкова

(72)В.Н.Решетник, В.П.Карелин, В.Ф.Гузик и А.Б.Вознюк

(53)681.327.6 (033.8)

(56)Авторское свидетельство СССР И- 746728, кл. G 11 С 15/00, 1978.

Авторское свидетельство СССР № 634372, кл. G 11 С 15/00, 1976.

(54)АССОЦИАТИВНАЯ ЯЧЕЙКА ПАМЯТИ

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

образов. Целью является расширение функциональных возможностей ячейки за счет выполнения операций маскирования и поиска минимума. Ячейка содержит мультиплексоры 14, 16, 31 и 32, триггеры 3, 27 и 28, счетчик 6, узел 9 памяти, дополнительный элемент И 4, элемент задержки 26, инверторы 10, 15 с соответствующими связями. Ячейка позволяет реализовать в матрице памяти поиск равного, поиск ближайшего меньшего, поиск ближайшего большего, маскирование, поиск максимума, поиск минимума, а также процедуру упорядоченного поиска в массиве чисел (в сторону увеличения или уменьшения элементов массива). За счет этого сокращается количество ячеек, необходимых для построения ассоциативной матрицы памяти. 1 ил.

S

(Л

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

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

W СЛ

На чертеже представлена функциональная схема ассоциативной ячейки памяти.

Ячейка содержит входы 1, 2 маскирования и установки, первый триг гер 3, четвертый элемент И 4, вход 5 синхронизации, счетчик 6, информационный вход 7, вход 8 выборки, узел 9 памяти, первый инвертор 10, элемент 11 сравнения, информационный выход 12, вход 13 опроса, четвертый мультиплексор 14, второй инвертор 15,

третий мультиплексор 16, вход 17 режима, второй и первый элементы И 18, 19, вход 20 запрета, третий элемент И 21, первый элемент ИЛИ 22, вход 23 вертикального логического канала,второй элемент ИЛИ 24, выход 25 вертикального Логического канала, элемент 26 задержки, второй и третий триггеры 27, 28, первый и второй выходы 29, 30 горизонтальных логических каналов, первый и второй мультиплексоры 31, 32, первый и второй входы 33, 34 горизонтальных логических каналов.

Алгоритм работы устройства следующий.

Двоичное слово а , . . .a j...а п занесено и хранится в узле 9 ячейки. С помощью счетчика 6 разряды слова адре суются и последовательно выбираются из узла 9 старшими разрядами вперед. Разряды х...х ...хп признака ассоциативного опроса последовательно поступают старшими разрядами вперед на вход 13 опроса ячейки. Одноименные разряды этих слов поступают на вход встроенной логики анализа ячейки, которая формирует логические переменные У; . z, « v, - Переменная у. поступает на вход 23 вертикального логического канала соседней снизу ячейки. Переменные z J, v ; запоминаются в триггерах 27, 28 данной ячейки, а затем при анализе очередных разрядов слов также подаются на вход встроенной логики ячейки в виде переменных Zj, , v, . Тем самым производится учет результатов анализа предыдущих разрядов и выполняется временная имитация про- странственной обработки разрядов анализируемого слова. При этом в каждый момент времени матрица ячеек выполняет обработку очередного битового среза анализируемого массива. Процесс анализа завершается после обработки младшего битового среза. При этом каждая ячейка матрицы памяти будет хранить в своих триггерах переменные zn vn« которые определяют резуль- тат ассоциативного анализа каждого слова исходного массива относительно признака опроса.

Сигнал на входе 17 задает возможные режимы работы встроенной логики ячейки, состоящей из элемента 11 сравнения, элементов И 18, 19 и 21, элементов ИЛИ 22, 24.

0 5 0 ,. Q о

5

v; v-.( t V z., a; x; ; (1) У, yV z,, a; x;;(2)

zj z;, b;,(3)

где t - значение двоичной переменной

на входе 20,

b ( - значение двоичной переменной на выходе элемента 11 сравнения, Ь( 1 при х а , b | 0 при x | я . .

v; v;-, tV z;, a; x;;(4)

У; У V z ;., a ; x; ;(5)

z; z..,b;.(6)

При поступлении на вход 1 лог. Ч задается режим маскирования двоичного слова, хранящегося в узле 9 данной ячейки при котором ото слово исключается из процесса ассоциативной обработки исходного массива.

По входу 8 задается режим работы узла 9 ячейки (чтение или запись).

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

В узел 9 каждой ячейки матрицы должно быть занесено информационное слово. Для этого подается сигнал 1 на вход 2, который сбрасывает счетчик 6 в нулевое состояние и устанавливает триггер 3 в единичное состояние. При этом синхросигналы с входа 5 каждой ячейки начинают поступать через элемент И 4 и на счетный вход счетчика 6, последовательно адресуя однобитовые ячейки узла 9. На вход 8 необходимо подать признак записи - О, а на вход 7 необходимо последовательно подавать старшими разрядами вперед заносимое информационное слово. При этом в каждом такте записи можно производить занесение в матрицу битового среза всего анализируемого массива. После завершения записи данных должен быть прекращен доступ синхросигналов на вход 5 ячейки. Перед началом работы на вход 2 необходимо подать сигнал 1, на вход 8 необходимо подать признак чтения - 1, на вход 17 - код режима работы, на входы 33, 34, 20, 23 - начальные значения соответствующих логических переменных. Рассмотрим работу ассоциативной матрицы памяти в отдельных режимах.

В этом режиме на все входы 33 матрицы необходимо подать 1м, на все входы 34 - О, на вход запрета 20 - 1. Значение сигнала на входе 23 в этом режиме несущественно. На вход опроса 13 необходимо последовательно подавать разряды признака опроса. На вхоц 17 подается признак О, который, поступая на адресные входы мультиплексоров 14, 16, приводит к подключению к их выходам первых входов данных. Такая коммутация мультиплексоров 14, 16 позволяет реализовать в ходе поиска логические функции (1) - (3). После поступления на вход 2 сигнала 1 триггер 3 находится в единичном состоянии, открывая своим единичным выходом элемент И 4, а счетчик 6 находится в нулевом состоянии. Ассоциативный поиск начинается с поступления на вход 5 синхросигналов. Первый из них проходит через элемент И 4 на счетный вхоц счетчика 6, наращивая его содержимое на единицу. При этом на выходе переполнения счетчика 6 появляется нулевой уровень, который, поступая на адресные входы мультиплексоров 31, 32, приводит к подключению к их выходам первых входов данных. Такая коммутация мультиплексоров 31, 32 позволяет в первом такте поиска передавать на вход встроенной логики каждой ячейки начальные константы, которые с входов соответственно 33 и 34 поступают на выходы мультиплексоров 31 и 32, а затем на входы соответственно элементов И 18, 19 и элемента И 21. Содержимое счетчика 6 поступает на адресный вход узла 9, адресуя первую битовую ячейку, в которой находится старший разряд анализируемого слова. Этот разряд с выхода узла 9 поступает на вход элемента 11 сравнения, а его инверсия с выхода инвертора 10

0

поступает на другой вход элемента 11 сравнения и через первый вход мультиплексора 16 - на вход элемента И 18. Разряд с входа опроса 13 поступает на другой вход элемента 11 сравнения и через первый вход мультиплексора 14 - на вход элемента И 18. Результат сравнения старших разрядов слов поступает с выхода элемента 11 сравнения на вход элемента И 19.

Таким образом, на выходе элемента И 19 формируется логическая функция (3), на выходе элемента ИЛИ 22

5 формируется логическая функция (1), а на выходе элемента ИЛИ 24 - функция (2). Первый синхросигнал через элемент 26 задержки с задержкой 2/3 длительности такта поступает на вхо0 Ды триггеров 27, 28, что приводит к занесению в них соответственно значений переменных z я v4 .

Начиная с поступления второго синхросигнала, содержимое счетчика 6

5 становится отличным от единицы и на его выходе переполнения во всех последующих тактах будет присутствовать единичный уровень, который, поступая на адресные входы мультиплексоров 31,

0 32, приводит к подключению к их выходам вторых входов данных. Такая коммутация мультиплексоров 31, 32 позволяет в каждом последующем такте передавать на вход встроенной логики

, каждой ячейки с выходов соответственно триггеров 27 и 28 значения выходов 29, 30, полученные в предыдущем такте и учитывающие результат обработки более старших разрядов ана0 лизируемого слова.

Согласно (3), сигнал 1 будет присутствовать в каждом такте обработки на выходе 29 до тех пор, пока просмотренные разряды анализируемого слова будут совпадать с соответствующими разрядами признака опроса. В той ячейке (или нескольких ячейках) , где содержится слово, совпадающее с признаком опроса, сигнал 1 будет присутствовать на выходе 29 после завершения последнего такта обработки.

В этом режиме на все входы 33 мат- рицы необходимо подать константы 1, на все входы 34 - О, на входы 23 - О. Выход 25 нижней ячейки матрицы необходимо соеди5

0

л

нить через дополнительный инвертор с входом 20 (канал запрета) верхней ячейки матрицы. На вход 17 подается признак О, который определяет,как в предыдущем режиме, реализацию логических функций (1) - (3). Любая ячейка, в которой после нескольких совпадений на предыдущих тактах впервые окажется, что разряд из узла 9 меньше разряда признака опроса, формирует сигналы О, 1 на выходах 29, 30. В отличие от предыдущего, в данном режиме, кроме того, используется возникающий в этой же ячейке в соответствии с (2) сигнал 1, котрый по вертикальному логическому каналу (23, 25) проходит до нижней ячейки матрицы, инвертируется дополнительным инвертором и устанавливает вход 20 запрета в нулевое состояние. Сигналы О и 1 будут присутствовать на выходах 29, 30 данной ячейки до тех пор, пока в очередном такте уже в другой ячейке не возникнет впер вые такая же ситуация, которая определит сигналы О, 1 на выходах 29 30 этой ячейки. При этом в соответствии с (2) на выхоДе 25 будет выработан сигнал 1, который установит в данном такте на входе 20 запрета состояние О. Это приведет к сбросу выхода 30 в нулевое состояние в первой из ячеек, так как сигнал О выхода 29 приведет к появлению нуле- вого уровня на выходе элемента И 18, а сигнал О входа 20 приведет к появлению нулевого уровня на выходе элемента И 21. В итоге на выходе элемента ИЛИ 22 будет сформирован сиг- нал О. Такая ситуация свидетельствует о том, что новая ячейка содержит число большее, чем число, хранящееся в первой ячейке. Поэтому число первой ячейки исключается из поиска, а претендентом на ближайшее меньшее становится число новой ячейки .

Если во всей матрице нет ни одной ячейки, в которой находится чис- ло большее, чем в данной ячейке, то в течение всех остальных тактов на входе 20 запрета будет присутствоват сигнал 1, который не приведет к изменению сигналов на выходах 29, 30 ячейки. После завершения обработки на выходах 29, 30 этой ячейки будут присутствовать сигналы О, 1, свидетельствующие, что данная ячейка

25

- ю15 20, 30 35 4045

зд ь 55 содержит число, ближайшее меньшее к признаку опроса. Если в матрице содержится несколько (равных) чисел, ближайших меньших к признаку опроса, то все соответствующие ячейки будут отмечены на своих выходах 29, 30 сигналами О и 1.

Если в качестве признака опроса подавать на вход 13 число 11...1, то в конце обработки сигналами О, 1 выходов 29, 30 будет отмечена ячейка матрицы, которая содержит число, минимально (в рамках массива) отличающееся от максимально возможной константы. Найденное число и будет являться максимальным элементом исходного массива.

Этот режим отличается от предыдущего тем, что на вход 17 подается признак 1, который, поступая на адресные входы мультиплексоров 14, 16, приводит к подключению к их выходам вторых входов данных. Такая коммутация мультиплексоров 14, 16 позволяет реализовать в ходе поиска логические функции (4) - (6). Разряд с выхода узла 9 поступает через второй вход мультиплексора 14 на вход элемента И 18. Разряд с входа 13 опроса поступает через инвертор 15 на второй вход мультиплексора 16 и с его выхода - на вход элемента И 18. Таким образом, на выходе элемента И 19 формируется логическая функция (6), на выходе элемента ИЛИ 22 формируется логическая функция (4) , а на выходе элемента ИЛИ 24 - функция (5).

В этом режиме сигналы 1, 1, О выходов 25, 29, 30 соответственно будут возникать в той ячейке, в которой впервые после ряда совпадений разряд слова из узла 9 окажется больше разряда признака опроса. При этом в конце обработки сигналами О, 1 выходов 29, 30 будут отмечены те ячейки матрицы, которые содержат числа (равные), ближайшие большие к признаку опроса. В остальном эти режимы идентичны.

Если в качестве признака опроса подавать в канал 13 число 00...О, то в конце обработки сигналами О, 1 выходов 29, 30 будет отмечена ячейка матрицы, содержащей число, в рамках массива минимально отличаю91

щееся от минимально возможной константы. Найденное число будет являться минимальным элементом исходного массива. В общем случае таких элементов в матрице может быть несколько

В этом режиме на вход 1 выбранной ячейки (ячеек) матрицы необходимо подать признак 1, который, пос- тупая на входы триггеров 3, 27 и 25, переводит их в нулевое состояние. При этом на единичном выходе триггера 3 будет присутствовать нулевой уровень, который, поступая на вход элемента И А, блокирует прохождение через него синхросигналов на вход счетчика 6. Это приведет к тому, что выборка разрядов из узла 9 производиться не будет и состояние триг- геров 27, 28 будет неизменно О, О на протяжении всего процесса обработки массива. Фактически это будет- обозначать маскирование числа, хранящегося в узле 9 выбранной ячей- ки (ячеек) матрицы.

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

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

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

« c 0 5

0

5

0

5

0

1610

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

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

Составитель С.Королев Редактор М.Циткина Техред М.Дидык

Заказ 758

Тираж 349

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101

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

Корректор М.Демчик

Подписное