Ассоциативное запоминающее устройство Советский патент 1993 года по МПК G11C15/00 

е

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

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

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

На фиг.1 представлена схема ячейки ассоциативной памяти; на фиг.2 - пример реализации двухканального двухразрядного коммутатора; на фиг.З - схема предлагаемого ассоциативного запоминающего устройства с матричным ассоциативным накопителем (ограничительные резисторы не показаны); на фиг 4 и фиг.5 примеры

реализаций соответстоенно первого и второго блоков регистров опроса и маскирования данных

Ячейка ассоциативной памяти (фиг.1) содержит триггер 1, входы установки в 1 и О которого подключены к выходам соответственно первого 2 и второго 3 элементов И-НЕ, а прямой и инверсный выходы подключены соответственно к первым входам третьего 4 и четвертого 5, а также пятого 6 и шестого 7 элементов И-НЕ. Выходы первого канала переключателя 8 присоединены соответственно ко вторым входам третьего 4 и четвертого 5 элементов И-НЕ, а выходы второго канала - соответственно ко вторым входам пятого 6 и шестого 7 элементов И- НЕ. Вторые входы первого и второго 3 элементовИ-НЕприсоединенысоответственно к первому 9 и второму 10 информационным входам записи Входы

00

ю

4 О СЛ О

первого канала деухканального двухразрядного переключателя подключены соответственно к первому 11 и второму 12 входам опроса по столбцу. Первые входы первого 2 и второго 3 элементов И-НЕ присоединены ко входу сигнала 13 записи. Входы второго канала переключателя подключены соответственно к первому 14 и второму 15 входам опроса по строке, а вход коммутации - ко входу 16 управления переключением каналов опроса. При нуле на этом входе осуществляется прямое соответствие входов и выходов каналов, при единице происходит перекоммутация каналов. Выходы третьего А и четвертого 5 элементов И-НЕ объединены и подключены к выходу 17 строчного пссии иативного поиска, а соединенные между собой выходы пятого б и шестого 7 тлемс;;;т(.н И-Hl: подключены к выходу 18 столбцового ассоциативного поиска.

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

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

Двухспальный двухразрядный комму- га т.д; (фиг.2) содержит элементы И с первого 22 по восьмой 29, элементы ИЛИ с первого 30 по чешергый 33 и иннертср 34.

На фиг.З представлена схема предлагаемого ассоциативного запоминающего устройства, состоящего из ассоциативного накопителя 35, содержащего ячейки 36 и группу 37 элементов И первого 38 и второго 39 блоков регистров опроса и маскирования данных, первого 40 и второго 41 регистров управления переключением каналов .5проса, первого 42 и второго 43 регистров фиксации реакций.

На фиг.4 показан пример реализации первого 38 блока регистров опроса и маскирования, состоящего из регистра 44 опроса, регистра 45 маскирования, первой 46 и второй 47 групп инверторов, первой 48 и второй 49 групп элементов И. Выходы с первого по четвертый (с 50 по 53) каждой группы блока 38 подключены соответственно к соединенным между собой входам 12. 11, 9, 10 ячеек памяти соответствующего столбца накопителя.

На фиг.5 показан пример реализации второго 39 блока регистров опроса и маскирования, состоящего из регистра 54 опроса,

регистра 55 маскирования, первой 56 и второй 57 групп инверторов; первой 58 и второй 59 групп элементов И. Выходы с первого 60 по третий 62 каждой группы блокл 39

подключены соответственно к соединенным между собой входам 13. 15, 14 ячеек памяти соответствующей строки накопителя.

На ассоциативное запоминающее устройстоо подаются следующие управляющие сигналы:

63- сигнал записи в накопитель 35;

64- сигнал чтения из I-ПКОПШРПЧ 35;

65- сигнал записи в регистр 44 опроса 5 блока 38;

66- сигнал записи в регистр 1Р .маскирования блока 38:

67-сигнал сброса в О регистров опроса 44 и маскирования 45 блока 38 и первого 0 40 регистра управления переключением каналов опроса;

68 - сигнал записи о регистр 40; G9 - сигнал записи в регистр 54 опроса блока 39;

570 сигнал записи в регистр 55 маскирования блока 39;

71- сигнлл сброса в О регистров опроса 54 и маскиров-чния 55 блока 39 и второго 41 регистре упраиления переключением ка0 налов сирого;

72- сигнал ззг.иси в регистр 41. Входи сигналов 05-68 - управляющие

входы нерпой группы устройства; входы сигналов CiP-- ; - управляющий входы второй 5 группы устройства. Входы cm налов 63, 64 явллютсч общими для первой и второй групп управляющих входов устройства.

73и 74 - соответственно перьзя и вторая группы входов устройства,

0 75 и 76 соответственно первая и вторая группы выходов устройства.

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

5 операций в ассоциативном запоминающем устройстве; запись информации по заданному адресу (группе адресов) с маскированием произвольных разрядов записываемого слова; считывание инфор0 мации по заданному адресу аргумента как по строкам, так и по столбцам; конъюнктивное считывание строк и столбцов; параллельный ассоциативный поиск ключевого аргумента по строкам, по столбцам и одно

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

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

В режиме маскируемой записи по строкам со входов 73 записываемое слово фиксируется в регистре 44 опроса по сигналу

В случае записи слова по группе адре- сов в регистр 54 опроса блока 39 должен быть записан ар умент, в котором единицы соответствуют адресуемым строкам накопителя до подачи сигналя 63 записи.

При считывании информации по стро- кам по заданному адресу в разряд регистра 54 опроса блока 39, соответствующий адресу считываемой строки, заносится единица. Остальные разряды должны быть замаскированы соответствующей маской, записан- ной в регистр 55 этого блока. Регистры 40 и 41 при этом должны быть сброшены в ноль. И при подаче сигнала 64 на входы 14 и 15 выбранной строки поступает комбинация 01, которая при нуле на входе 16 элемен- тов памяти подается соответственно на вторые входы пятого 6 и шестого 7 элементов И-НЕ элементов памяти выбранной строки. В случае хранения триггером 1 единицы на выходе 18 соответствующей ячейки памяти сохранится уровень логической единицы, в случае хранения нуля выход 18 обнулится. И по заднему фронту сигнала 64 считываемое слово зафиксируется во втором 43 регистре фиксации реакций.

В режиме строчного конъюнктивного считывания единицы должны быть записаны в те разряды регистра 54 опроса блока 39, которые соответствуют адресам считываемых строк накопителя.

Операция считывания по строке может быть также осуществлена по-другому. В регистр 44 блока 38 и в регистр 40 записываются единицы во все разряды. Единица также записывается в разряд регистра 41,

соответствующий адресу сч.-и и г.трп ки. И при подаче сигналя 64 м; n, i,;i, 1 и 12 всех ячеек накопителя nocrynni чрмГчшл ция сигналов 01. которая при едичицп нл 16 ячеек памяти считываемо - строки подг)ется соответственно на вторые гкоды пятого 6 и шестого 7 элементов И- НЕ: ЯЧРСК памяти выбранной строки. Далее аналогично рассмотренному варианту строчного считывания.

Используя этот подход, можно выполнить и строчное конъюнктивное чтение.

При считывании заданного разрядного среза в разряд регистра 44 опроса блока 38, соответствующий адресу считываемого столбца, заносится единица. Остальные разряды должны быть замаскированы соответствующей маской, записанной в регистр 45 этого блока. Регистры 40 и 41 при этом должны быть сброшены в О. И при подаче сигнала 64 на входы 11 и 12 выбранного столбца поступает комбинация 01. которая при нуле на входе 16 элементов памяти подается соответственно на вторые входы третьего 4 и четвертого 5 элементов И-НЕ ячеек памяти выбранного столбца. В случае хранения триггером 1 единицы на выходе 17 соответствующей ячейки памяти сохранится уровень логической единицы, в случае хранения нуля выход 17 обнулится. И по заднему фронту сигнала 64 считываемый столбец зафиксируется в первом 42 регистре фиксации реакций.

В режиме столбцовою конъюнктивного считывания единицы должны быть записаны в те разряды регистра 44 опроса блока 38, которые соответствуют адресам считываемых столбцов накопителя. Операция столбцового считывания может быть осуществлена по-другому. В регистр 54 блока ЗЭ и в регистр 41 записываю ся единицы по все разряды. Единица также записывается в разряд регистра 40, соответствующий адресу считываемого столбца. И при подаче сигнала 64 на входы 14 и 15 есех ячеек накопителя поступит комбинация сигналов 01, которая при единице на входе 16 ячеек памяти считываемого столбца подается соответственно на вторые входы третьего 4 и четвертого 5 элементов И-НЕ ячеек памяти выбранного столбца. Далее аналогично рассмотренному варианту столбцового считывания.

Используя этот подход, можно осуществить и столбцовое конъюнктивное чтение.

В режиме параллельного ассоциативного маскируемого поиска по строкам в регистр 44 опроса блока 38 заносится аргумент поиска, а в регистр 45 этого блока - маска. И при сброшенных в О

регистрах 40 и 41 при подаче этого сигнала 64 на входы 11 и 12 ячеек памяти поступит одна из следующих комбинаций сигналов: 01 - сравнение с единицей, 10 - сравнение с нулем, 00 - маскирование поиска, При несовпадении содержимого ячейки с признаком опроса обнулится выход 17 этой ячейки и, следовательно, на шине, соединяющей эти выходы 17 элементов памяти соответствующей строки накопителя, установится потенциал логического нуля, Если произошло совпадение или маскирование опроса, то выходы 17 сохранят уровень логической единицы. Результат строчного ассоциативного поиска фиксируется о первом 42 регистре фиксации реакций пи заднему Фронту сигнала 64, Единицы в разрядах этого регистра указывают на позиции строк, совпавших с маскируемой строкой - аргументом.

В режиме параллельного ассоциативного маскируемого поиска по столбцам в регистр 54 опроса блока 39 заносится аргумент поиска, а в регистр 55 этого блока - маска И при сброшенных п О ре- гисшах 40 и 41 при подаче сигнала 64 на входы 14 и 15 ячеек памяти поступит одна из следующих комбинаций сигналов: 01 - сравнение с единицей; 10 - сравнение с нулем, 00 - маскирование поиска. При несовпадении содержимого ячейки с признаком опроса обнупитси выход 18 этой ячейки и, следовательно,на шине, соединяющей выходы 18 ячеек памяти соответствующего столбца накопителя, установится потенциал логическою нуля, Если произошло совпадение или маскирование опроса, то выходы (8 ячеек памяти соответствующего столбца накопителя сохранят уровень логической единицы. Результат столбцового ассоциативного поиска фиксируется во втором 43 регистре фиксации реакций по заднему фронту сигнала 64. Единицы в разрядах этого регистра указывают на позиции столбцов, совпавших с маскируемым столбцом - аргументом.

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

При этом в соответствующих разрядах регистров 40 и 41 должны быть записаны

единицы, устанавливающие в единицу выходы элементов 37 И, подключенные ко входам 16 соответствующих ячеек накопителя. Таким образом, осуществляется перекоммутацич строчного и столбцового каналов опроса указанных ячеек. При этом перед инициализацией поиска сигналом 64 в разряды блока 39, соответствующие заменяемым разрядам строки-аргумента поиска,

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

При смешанном ассоциативном поиске по столбцам по синте ;ированным из столб5 цоаого и строчного аргументам поиска осуществляется возможность замены одного или нескольких (произвольных) разрядов столбца-аргумента поиска для каждого отдельного столбца ассоциативного накопи0 теля содержимым (в том числе и маскированным) разряда первого 38 блока регистров опроса и маскирования, соответствующего этому столбцу. Длл этого режима справедливо все вышесказанное о смешан5 ном ассоциативном поиске по строкам в собственном контексте.

При фиксации количества несовпадений строки -аргумента поиска с выделенной строкой ассоциативного накопителя до под0 ачи сигнала 64 в регистры блока 38 должен быть записан маскируемый аргумент поиска, в регистр 40 записаны единицы во все разряды. Единица также должна быть занесена в разряд регистра 41, соогветствую5 щий строке, сравниваемой с аргументом поиска. Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39. И при подаче сигнала 64 аргумент поиска сравнивается с выде0 ленной строкой с фиксацией результата сравнения по втором 43 регистре фиксации реакций. Число нулей, зафиксированное в этом регистре, соответствует количеству несовпадений аргумента поиска с выделенной

5 строкой.

При осуществлении фиксации количества несовпадений строки-аргумента поиска с конъюнкцией выделенных строк при прочих прежних условиях единицы должны

0 быть занесены в разряды регистра 41, соответствующие строкам, сравниваемым с аргументом поиска. Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39, причем

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

При осуществлении ф| , к н.ич сг ва несовпадении столбца --)t r/r iM i по иска с выделенным i ныОцо ° ассоциативного накоп телч до пол-тли cm нала G l в рсп отры бчока 3° до Ь см Чиь записан мяскируг ,й зргуменг иси, регистр 41 записан j од н ицы о псе рачрл ды Единица должна быт о Зччссема п разряд регистра -10, соответствующий строке, сравниваемой с лргум J,TOM иои „ я Все остальные сголбцн допжны быть зямзс1 и содержимым реп стра 15 маскиро вэнич блока 38 И при подач сигнала О

Яр1)МСНГ ПОИСКс. СрОРНИГП - ЛГДО ЧаННЫМ

столбцом с фиксацией ре ультагэ срмзнс ния в первой 42 регистре Фиксации р.эк- ций Число нулей, зяфинсмронэнное п этом регистре, соответствует количеству несов- падрний аргупонтя с ВИДРЛОСЧЫМ столбцом

При осущр л pici in фиксации гопичест ва несовпадений столбцн аргуме г,т поиска с конъюнкцией выделенных столонов при про 1их прежнпч словипх допжны быть занесены в разряды рмисгра 40 соот(зетствую1чи столбцам с аргументом поиска Все нис iiO i6- цы должны бпь зам скироог нп f одержи мым регистра 4Ъ м,л кироа, блока ТО Причем, для эти з масккро змны/ для строчного зсгоцичтинного поиска столбцов реализуется ассоциативный по..гк по стоп бцам И результат этого сгопбцог ого поиска фиксируется п ртзрядях пторого (3 регистра фиксации реакции, соответствующих этим замагкироианннм для ггрмчн мо поисг стоп (щам.

Формула изобретения Ассоциативмое ляпомш яюиюг- уснтп- ство, содержащее1 ассоциэтнпный накопитель, первый и второй блоки регистров опроса и маскирование данных, псрвмч и второй регистры фиксации реакций, при 4РМ информационнып входы первого регистров опроса и Мг)скиропз ия данных ш- ляются информационными т ходами первой группы устройства управляющими входами первой группы которого являются соответствующие управляющие входы первого блока регистров опроса и «аскирочамт данных, а выходы с перпою по четвсотыи каждой группы которого подключены соответственно к четвертым, третьим, порпым и

вторым РАОД,)М элем°г1ов памяц соответ- (твующс сюл(мп ассоцианшною нткппи- чп, I l JiopKii L OMHfie Плиды вто)ого блока Р Ч .DO (. р.сл . маскирорания данных Р яо .чюгс1 имфорг durohunJMH входами ето- роО руппы устройсюа -мрдвляющими входами второй ipyrnw которого являются сооггстствующие управляющие входы второго бьокз регис;ров опроса и мзскирова0 ния , а выходы с первого гю третий Кс.кдоч группы которого подключены соот- СРТС гпснно пятым, седьмым и шестым входам jfit,MCriroo памяти соответствующей строки ассоциативного накопителя, первые

5 выдо/1ь: ко орнх обьодинены и подключены к гею в тсгвующему информационному входу первого регистра фиксации реакций. выходы которого являются выходами первой группы устройства, вторые выходы эле0 ментов памяти каждого столбца асгоиплтивпого накопителя подключены к соответгтрующему информационному входу второе регистра фиксации реакций, выходы I-спорого являются выходами второй

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

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

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

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

5 переключением каналов опроса

ЦМ1

SfSJ i SJ 7/r fift raff JO

50 5t П51

63№

ffS,70,7f

1

67,68 1

1

7/

76

Фиг1

г

I

Зшходы 8/порога канала опроса

JilJL

м

I-

„

Ф

I i i

у у .4i

CC -5 -Lk J СП

ЗшоЗй/ /7ер6я га качала оласса

S4

j

И, -с- i rKMrJ