Ассоциативная ячейка памяти

 

COIO3 СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (111 щ)5 G 11 С 15/Од

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

К А BTOPCHGMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4673702/24 (22) 04.04.89 (46) 15.03.91. Бюл. и - 10 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Н.Решетняк, В.П.Карелин, В.Ф.Гузик и А.E.Бознюк (53) 681.327.6 (083.8) (56) Авторское свидетельство СССР

11 - 746728, кл. С 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 с соответствующими связями. Ячейка позволяет реализовать в матрице памяти поиск равного, поиск ближайшего меньшего, поиск ближайшего большего, маскирование, поиск максимума, поиск минимума, а также процедуру упорядоченного поиска в массиве чисел (в сторону увеличения или уменьшения элементов массива).

3а счет этого сокращается количество ячеек, необходимых цля построения ассоциативной матрицы памяти. 1 ил.

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

Ячейка содержит входы 1, 2 мас— кирования и установки, первый триг гер 3, чегвертый элемент И 4, вход

5 синхронизации, счетчик 6, информационный вход 7, вход 8 выборки, узел

9 памяти, первый инвертор 10, элемент 11 сравнения, информационный выход 12, вход 13 опроса, четвертый мультиплексор 14, второй инвертор 15, 1635216 третий мультиплексор 16, вход 17 режима, второй и первый элементы И 18, 19, вход 20 запрета, третий элемент

И 21, первый элемент ИЛИ 22, вход 23 вертикального логического канала,второй элемент И1И 24, выход 25 вертикального Логического канала, элемент

26 задержки, второй и третий триггеры 27, 28, первый и второй выходы 29, 10

30 горизонтальных логических каналов, первый и второй мультиплексоры 31, 32, первый и второй входы 33, 34 горизонтальных логических каналов.

Ал гори тм работы ус тройс тв а следующий, Двоичное слово а ...а;... а и занесено и хранится в узле 9 ячейки. С помощью счетчика 6 разряды слова адре-2р суются и последовательно выбираются из узла 9 старшими разрядами вперед.

Разряды х ...x ...õn признака ассоциаI тивного опроса последовательно поступают старшими разрядами вперед на 25 вход 13 опроса ячейки. Одноименные разряды этих слов поступают на вход встроенной логики анализа ячейки, которая формирует логические переменные (Г у;, z;, v;. Переменная у. поступает 3р на вход 23 вертикального логического канала соседней снизу ячейки. Переменные z,, v; запоминаются в триггерах 27, 28 данной ячейки, а затем при анализе очередных разрядов слов также подаются на вход встроенной л >гики ячейки в виде переменных г.

v . Тем самым производится учет ре1- 1 зультатов анализа предыдущих разрядов и выполняется временная имитация про- 40 странственной обработки разрядов анализируемого слова. При этом в каждый момент времени матрица ячеек выполняет обработку очередного битового среза анализируемого массива. Процесс 45 анализа завершается после обработки младшего битового среза. При этом каждая ячейка матрицы памяти будет хранить в своих триггерах переменные я ° котоРые опРеделЯют РезУль 50 тат ас с оциа ти вного анализа каждого слова исходного массива относительно признака опроса, Сигнал на входе 17 задает возможные режимы работы встроенной логики ячейки, состоящей из элемента 11 сравнения, элементов И 18, 19 и 21, эле— ментов ИЛИ 22, 24. (!) (2) v;, tVz;,а;

УЧ г;,а х,; х;;

У, (3) z;, b;, г, значение двоичной переменной на входе 20, значение двоичной переменной на выходе элемента 11 сравнения, b; = 1 при х; = а;, b = 0 при х = а..

1 I где

2, Если на входе 17 — лог. "1", то ячейка реализует следующие логические функции (i = 1, п): (4) (5) v;,tVz;,а; х;;

v, 1

У;

=yVz; а, х,; (6) z = z; b;.

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

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

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

В узел 9 каждой ячейки матрицы должно быть занесено информационное слово. Для этого подается сигнал "1" на вход 2, который сбрасывает счетчик 6 в нулевое состояние и устанавливает триггер 3 в единичное состояние. При этом синхросигналы с входа 5 каждой ячейки начинают поступать через элемент И 4 и на счетный вход счетчика 6, последовательно адресуя однобитовые ячейки узла 9.

На вход 8 необходимо подать признак записи — "0", а на вход 7 необходимо последовательно подавать старшими разрядами вперед заносимое информационное слово. При этом в каждом такте записи можно производить занесение в матрицу битового среза всего анализируемого массива. После завер1. Если на входе 17 — лог. "0" то т ячейка реализует следующие логические функции (i = 1, n):

16352

10 отдельных режимах.

1, Поиск равного.

В этом режиме на все входы 33 матрицы необходимо подать " 1", на все входы 34 — "0", на вход запрета 20—

"1", Значение сигнала на входе 23 в этом режиме несущественно. На вход опроса 13 необходимо последовательно подавать разряды признака опроса. 20

На вхоц 17 подается признак "0", который, поступая на адресные входы мультиплексоров 14, 16, приводит к подключению к их выходам первых входов данных. Такая коммутация мульти- 25 плексоров 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 шения записи данных должен быть прекращен доступ синхросигналов на вход

5 ячейки. Перед началом работы на вход 2 необходимо подать сигнал "1", на вход 8 необходимо подать признак чтения — "1", на вход 17 — код режима работы, на входы 33, 34, 20, 23— начальные значения соответствующих логических переменных. Рассмотрим работу ассоциативной матрицы памяти в

16 6 поступает на другой вход элемента 11 сравнения и через первый вход мультиплексора 16 — на вход элемента И 18.

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

14 — на вход элемента И 18. Результат сравнения старших разрядов слов поступает с выхода элемента 11 сравнения на вход элемента И 19.

Таким образом, на выходе элемента И 19 формируется логическая функция (3), на выходе элемента ИЛИ 22 формируется логическая функция (1), а на выходе. элемента ИЛИ 24 — функция (2), Первый синхросигнал через элемент 26 задержки с задержкой 2/3 длительности такта поступает на входы триггеров 27, 28, что приводит к занесению в них соответственно значений переменных z < и v

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

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

В той ячейке (или нескольких ячейках), где содержится слово, совпадающее с признаком опроса, сигнал

"1" будет присутствовать на выходе

29 после завершения последнего такта обработки.

2. Поиск ближайшего меньшего (поиск максимума).

В этом режиме на все входы 33 мат11 9! рицы необходимо подать константы 1 на в с е входы 34 — " 0 ", на вх оды 2 3 — " 0 " . Выход 2 5 нижней ячейки матрицы необходимо с оеди1635216 нить через дополнительный инвертор с входом 20 (канал запрета) верхней ячейки матрицы. На вход 17 подается признак 0", который определяет,как в предыдущем режиме, реализацию логических функций (1) — (3). Любая ячейка, в которой после нескольких совпадений на предыдущих тактах впервые окажется, что разряд из узла 9 меньше разряда признака опроса, формирует сигналы "0", " 1" на выходах

29, 30. В отличие от предыдущего, в данном режиме, кроме того, используется возникающий в этой же ячейке 15 в соответствии с (2) сигнал "1", который по вертикальному логическому каналу (23, 25) проходит до нижней ячейки матрицы, инвертируется дополнительным инвертором и устанавливает 20 вход 20 запрета в нулевое состояние.

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

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

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

3. Поиск ближайшего большего (поиск минимума).

Этот режим отличается от предыдущего тем, что на вход 17 подается признак "1", который, поступая на адресные входы мультиплексоров 14, !

6, приводит к подключению к их выходам вторых входов данных. Такая коммутация мультиплексоров 14, 16 позволяет реализовать в ходе поиска логические функции (4) — (6), Разряд с выхода узла 9 поступает через второй вход мультиплексора 14 на вход элемента И 18, Разряд с входа

13 опроса поступает через инвертор

15 на второй вход мультиплексора 16 и с его выхода — на вход элемента

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

22 формируется логическая функция (4), а на выходе элемента ИЛИ 24 функция (5).

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

При этом в конце обработки сигналами "0", "1" выходов 29, 30 будут отмечены те ячейки матрицы, которые содержат числа (равные), ближайшие большие к признаку опроса. В остальном эти режимы идентичны, Если в качестве признака опроса подавать в канал 13 число 00...0, то в конце обработки сигналами "0", "1" выходов 29, 30. будет отмечена ячейка матрицы, содержащей число, в рамках массива минимально отличаю1635216

1О

45

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

4. Маскирование числа.

В этом режиме на вход 1 выбранной ячейки (ячеек) матрицы необходимо подать признак "1", который, поступая на входы триггеров 3, 27 и 25, переводит их в нулевое состояние.

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

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

При этом определяемые на каждом шаге числа составят упорядоченную в сторону увеличения или уменьшения последовательность чисел исходного массива.

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

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

1635216

Моск

cm

CH о( и;

kp8

zi

t У, Составитель С.Королев

Редактор М,Циткина Техред И.дидык Корректор И.Демчик

Тира к 349

Подписное

Заказ 758

BHHHtIH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

11303$, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 вход и вход выборки которого являются информационным входом и входом выборки ячейки соответственно, второй вход данных третьего мультиплексора соединен с выходом второго инвертора вход которого соединен с первым входом элемента сравнения и с первым входом данных четвертого мультиплексора, второй вход данных

5 которого соединен с выходом узла памяти.