Ассоциативное запоминающее устройство

 

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

союз сОВетских

СОЦИАЛ ИС1ИЧГ СКИХ

РЕСПУБЛИК. Ж «1824650 А1 (я >s G 11 С 15/00

ГОсудАРстВенгое пАтентнОГ

ВЕДОМСТВО CCCt (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ,„„,,:„,„

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21l 4891833/24 (22) 13,12.90 (46) 30,06.93. Бюл. № 24 (71) Московский энергетический институт (72) И.В. Огнев и В.В. Борисов (56) Авторское свидетельство СССР

¹ 760187, кл. G 11 С 15/00, 1978.

Авторское свидетельство СССР

¹1718274, кл. G 11 С 15/00, 1990. (54) АССОЦИАТИВНОЕ ЗАГ ОМИНА1ОЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам и может быть использовано в специализированных системах хранения и

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

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

На фиг.1 представлена схема ячейки ассоциативной памяти; на фиг.2 — пример реализации двухканального двухразрядного коммутатора; на фиг.3 — схема предлагаемого ассоциативного запоминающего устройства с матричным ассоциативным накопителем (ограничительные резисторы не показаны); на фиг.4 и фиг.5 — примеры цифровой обработки изображений, при решении информационно-логических задач, задач поиска и сортировки данных. Целью изобретения является расширение области применения устройства эа счет обеспечения ассоциативного поиска по синтезированным из строчного и столбцового аргументам. Ассоциативное запоминающее устройство содержит ассоциативный накопитель, первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры фиксации реакции, первый и второй регистры управления переключением каналов опроса и матрицу элементов

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

Ячейка ассоциативной памяти (фиг.1) содержит триггер 1, входы установки в -1" и

"0" которого подключены к выходам соответственно первого 2 и второго 3 элементов

И вЂ” НЕ, а прямой и инверсный выходы подключены соответственно к первым входам третьего 4 и четвертого 5, а также пятого 6 и шестого 7 элементов И вЂ” НЕ. Выходы первого канала переключателя 8 присоединены соответственно ко вторым входам третьего

4 и четвертого 5 элементов И вЂ” НЕ, а выходы второго канала — соответственно ко вторым входам пятого 6 и шестого 7 элементов ИНЕ, Вторые входы первого и второго 3 элементов И-НЕ присоединены соответственно к первому 9 и второму 10 информационным входам записи. Входы

1824650

55 первого канала двухканального двухразрядного переключателя подключены соответственно к первому 11 и второму 12 входам опроса по столбцу, Первые входы первого 2 и второго 3 элементов И-НЕ присоединены ко входу сигнала 13 записи, Входы второго канала переключателя подключены соответственно к первому 14 и второму 15 входам опроса по строке, а вход коммутации — ко входу 16 управления переключением каналов опроса. При нуле на этом входе осуществляется прямое соответствие входов и выходов каналов-, при единице происходит перекоммутация каналов. Выходы третьего

4 и четвертого 5 элементов И-НЕ объединены и тодключсч ы к Выходу 17 строчного

:coоцнативного поиска, а соединенные ме:кду собой выходы пятого 6 и шестого 7

;леме;;тов И-НЕ подкл)о<ены к выходу 18 столбцового ассоциативного поиска.

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

Выход же 17. присоединенный к выходам эле )оптов И вЂ” НЕ ячеек соответствуюL ) .v строки ассоциативного накопителя, ч;.рез Второй ограничительный элемент 21 под"лючен i o входу 20 потенциала ло) ичесхай единицы. ,)1ухх; нальный двухразрядный кол муга).>г (фиг.2) соде;)жит элементы И r. первого 22 по Восьмой 29, элементы ИЛИ с первого 30 по че) вергый 33 и инвертср 34.

На фиг.3 представлена схема предлагаемого ассоциативного запоминающего устройства, состоящего из ассоциативного накопителя 35, содержащего ячейки 36 и группу 37 элементов И первого 38 и второго

39 блоков регистров опроса и маскирования данных, первого 40 и второго 41 регистров управления переключением каналов:npoса, первого 42 и второго 43 регистров 4)иксации реакций, На фиг.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 - сигнал чтения из накопи) еля 35;

65 — сигнал записи в регистр 44 опроса блока 38:

66 — сигнал записи в ре) истр 15 маск))рования блока 38;

67 — сигнал сброса в "Г регистров опроса 44 и маскирования 45 блока 38 и первого

40 регистра управления пг:реключением каналов опроса;

68 — сигнал записи в регистр 40;

69 — сигнал записи в регистр 54 опроса блока 39;

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

71 — сигнал сброса В 0" регистров опроса 54 и маскиров:.)ния 55 блока 39 и Второго

41 регистра управления переключением каналов о.)роса;

72 — сигн: л за):иси в регистр 41.

Входы:; гна))ов 65-68 — у))равляющие входы пер))ой группы устройства; Входы сигналов ) ", ° --,? — управляющие входы Второй группы устроиства. Входы с яналов ))3, 64 явллютсч общими для первой и второй груггп управляющих входов устройства, 73 и 74 — соответственно перьая и вторая группы входов устройства, 75 и 76 — соответствен).о первая и втора)) группы ВыхОдОВ устройства.

Ячейки ассоциативной памяти благодаря подаче управляющих сигналов позволяют осуществить выполнение следу:ощих операций в ассоциативном запоминающем устройстве: запись информации по заданному адресу (группе адресов) с маскированием произвольных разрядов записываемого слова; считывание информации по заданному адресу аргумента как по строкам, TAK и по столбцам; Konb)OHKTMBное считывание строк и столбцов; параллельный ассоциативный поиск ключевого аргумента по строкам, по столбцам и одновременно по строкам и столбцам накопителя по критерию "равно" с максированием произвольных разрядов: смешанный ассоциативный поиск по строкам и столбцам ассоциативного накопителя по аргументам

ПОИСКа, ГИНтЕЗИРОВаННЫМ ИЗ С) Г)Г)чНОГО И 8246!о столбцового аргументов поиска; фиксацию количества несовпадений аргументов поиска как с отдельными выделенными с роками и столбцами ассоциативного накопителя, так и с конъюнкцией выделенных строк и столбцов.

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

65. Затем в регистр 45 маскирования с этих же входов записывается маска по сигналу

66, Одновременно с этим со входов 74 в регистр 54 блока 39 записывается дешиф рированн A адрес строки по сигналу 69. И при подаче сигнала 63 записи в накопитель 35 на входы 9 и 10 всех элементов 36 памяти накопителя поступит одна из следующих комбинаций сигналов. "10" — при записи единицы, "01" — при записи нуля, "00" — при маскировании записи; на входы 13 элементов 36 памяти адресуемой строки подается уровень логической единицы, Таким образом осуществляется запись по заданному адресу, В случае записи слова по группе адресов в регистр 54 опроса блока 39 должен быть записан аргумент, в котором единицы соответствуют адресуемым строкам накопителя до подачи сигнала 63 записи, При считывании информации по строкам по заданному адресу в разряд регистра

54 опроса блока 39, соответствующий адресу считываемой строки, заносится единица.

Остальные разряди должны быть замаскированы соответствующей маской, записанной в регистр 55 этого блока. Регистры 40 и

41 при этом должны быть сброшены в ноль, И при подаче сигнала 64 на входы 14 и 15 выбранной строки поступает комбинация

"01", которая при нуле на входе 16 элементов памяти подается соответственно на вторые входы пятого б и шестого 7 элементов

И вЂ” НЕ элементов памяти выбранной строки.

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

И по заднему фронту сигнала 64 считываемое слово зафиксируется во втором 43 регистре фиксации реакций.

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

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

1О

55 соответствующий ядр= удач. -i иг; .r. . r.тро ки, И при пода«е сигнала 64 н;.. °,,1.. 11 и

12всехячеекнакопителя поступиr к моинl ция сигналов 01", которая пои едп чще на входе 1б ячеек памяги считыва мо. : строки подается соответственно на вторы в оды пятого 6 и шестого 7 элементов И- НЕ ячеек памяти выбоанной строки, Далее аналогично рассмотренному варианту строчного счи ь вания.

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

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

45 этого блока. Регистры 40 и 41 при этом должны быть сброшены в "0". И пр подаче сигнала 64 на входы 11 и 12 выбранного столбца поступает комбинация "01", которая при нуле на входе 16 элементов памяти подается соответственно на вторые входы третьего 4 и четвертого 5 элементов И-НЕ ячеек памяти выбранного столбца. В случае хранения триггером 1 единицы на выходе 17 соответствующей ячейки памяти сохранится уровень логической единицы, в случае хранения нуля выход l7 06HóëèTñÿ. И по заднему фронту сигнала 64 считываемый столбец зафиксируется в первом 42 регистре фиксации реакций.

В режиме столбцового коньюнктивного считывания единицы должны быть записаны в те разряды регистра 44 опроса блока

38, которые соответствуют адресам считываемых столбцов накопителя. Операция столбцового считывания может быть осуществлена по-другому. В регистр 54 блока 39 и в регистр 41 записываюгся единицы BQ все разряды, Единица также записывается в разряд регистра 40, соответстьующий адресу считываемого столбца. И при подаче сигнала 64 на входы 14 и 15 всех ячеек накопителя поступит комбинация сигналов

"01", которая при единице на входе 16 ячеек памяти считываемого столбца подается соответственно на вторые входы третьего 4 и четвертого 5 элементов И вЂ” НЕ ячеек памяти выбранного столбца. Далее аналогично рассмотренному варианту столбцового считывания.

Используя этот подход, можно осуществить и столбцовое коньюнктивное чтение, В режиме параллельного ассоциативного маскируемого поиска по строкам в регистр 44 опроса блока 38 заносится аргумент поиска, а в регистр 45 этого блока — маска. И при сброшенных в "0"

1824650 регистрах 40 и 41 при подаче этого сигнала

64 на входы 11 и 12 ячеек памяти поступит одна из следующих комбинаций сигналов;

"01" — сравнение с единицей, "10" — сравнение с нулем, "00" — маскирование поиска, При несовпадении содержимого ячейки с признаком опроса обнулится выход 17 этой ячейки и, следовательно, на шине, соединяющей эти выходы 17 элементов памяти соответствующей строки накопителя, установится потенциал логического нуля, Если произошло совпадение или маскирование опроса, то выходы 17 сохранят уровень логической единицы. Результат строчного ассоциативного поиска фиксируется в llepBof 42 регистре фиксации реакций по ".àäíåìó фронту сигнала 64, Единицы в разрядах этого регистра указывают на позиции строк, совпавших с мзскируемой строкой аргументом.

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

18 ячеек памяти соответствующего столбца накопителя сохранят уровень логической единицы. Результат столбцового ассоциаFwBK0r поиска фиксируется во втором 43 регистре фиксации реакций по заднему фронту сигнала 64, Единицы в разрядах этого регистра указывают на позиции столбцов, совпавших с мзскируемым столбцом— аргументом.

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

55 единицы, устанавливающие в единицу выходы элементов 37 И, подключенные ко входам 16 соответствующих ячеек накопителя, Таким образом, осуществляется rleðiênììóтация сгрочного и столбцового каналов опроса указанных ячеек. При этом перед инициализацией поиска сигналом 64 в разряды блока 39, соответствуюв ие заменяемым разрядам строки — аргумента поиска, для каждой участвующей в той замене строки записывается необходимое мзскируемое значение, При смешанном ассоциативном поиске по столбцам rlo синтезированным иэ столбцового и строчного аргументам поиска осуществляется возможность замены одного или нескольких (произвольных) разрядов столбца †аргумен поиска для каждого отдельного столбца ассоциативного накопителя содержимым (в том числе и маскированным) разряда первого 38 блока регистров опроса и маскирования, соответcTBóþùårо этому столбцу. Для этого режима справедливо Все вышесказанное о смешанном ассоциативном поиске по строкам в собственном контексте, При фиксации количесгва несовпадений строки-аргумента поиска с выделенной строкой ассоциативного накопителя до подачи сигнала 64 в регистры блока 38 должен быть записан маскируемый аргумент поиска, в регистр 40 записаны единицы во все разряди. Единица также должна быть занесена в разряд регистра 41, соответствующий строке, сравниваемой с аргументом поиска. Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39, И при подаче сигнала 64 аргумент поиска сравнивается с выделенной строкой с фиксацией результата сравнения во втором 43 регисгре фиксации реакций. Число нулей, зафиксированное в этом регистре, соответствует количеству несовпадений аргумента поиска с выделенной строкой, При осуществлении фиксации количества несовпадений строки-аргумента поиска с конъюнкцией выделенных строк при прочих прежних условиях единицы должны быть занесены в разряды регистра 41, соответствующие строкам, сравниваемым с аргументом поиска. Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39, причем для этих замаскированных для столбцового ассоциативного поиска строк реализуется ассоциативный поиск по строкам, И результат этого строчного поиска фиксируется в раэрядзх первого регистра 42 фиксации реакций, соответствующих этим ззмзскиро1 ванным длЯ сToлб(10()0"" R(.i (!I(.1»Tин)io(0 поиска строкам.

Г1ри осу(цесTI)fief!f1è ф ксацик кили (оства HPсoBï»äåHèë сголбца-3))гуt. i ),-; и; иска с выделенным (:толбцо; ассоциатин«)ofa накопителя до .)Од«н(и сигнала б4 н ро) -.трь(блока 3() ДО()х:())(бь(;ь эапиган л(аск()рус )ь)й Bpгу«102(ио к» регистр 41 записан,,«ОД»)«2ицы )о все ра.(ряды. Ед(1« f((3 TBK В должl!3 бь«ть 3- Iccåfi,) В разряд г)егистра 40, соотн(тст()ую)ц(1(1 строКс, С pf) R!IL)B»et (- Rj)f «(t)е(i Том !10(1 !:.3. «(Се осталь (ые столГ)ц) i долж)(ы быть замас).иpoB3H«соДер)кил ь(л1 регистра 15 масKL)j)0B3HL блока ЗЯ. И fli)LI подаRB cи(«i»ла 04

3PI ((ОНТ ПОИСКа С()»Н)(И(С) .; JCIÄÑ !QHH! If столбц(2м с фиксацией ре.-; RüT3(3 cp:;Bf!ения в первом 42 регистре ф(ксации рзакЦИй. ЧИСЛО НУЛЕИ, ЗафИКСИРОНЗННОЕ f) ЭТОМ регистре, сooòветсleуеT количеству несоBпадений аргумента по«ск» с Выдолоннь)м столбцом.

При осущос) í Ici!L1! фиксации количест. ва несовпадений столбца- »ргул)е(((3 поиска с канък)нкциеЙ ныДеле«!! !l»ix сто/2б!!ОВ при про (их I!реж«их условиях еди«)ицы должны быть занесены и разряды р(.rl)c Tp» 40, саат()етствую)1)(1о ста() бцам., c j)3R«I! IRRR«1bltiI с аргументом (виска. Все ос - л -.н2 о cтолбць(дОлжны быт ь 3»t i»cKL1 j)arsi)HI I (:oäeржимым регистра 45 t ;)s;KLIpoec)»H!) бл()ка 30.

Г!ричем, для эти: замаскиронз«(ны", для строчного ассоц 1:)тинного паис,а столбцов реализуется »ceo (.»тинный п()иcK г)0 столбцам. И результат этого столбцог .ого г)виска фИКСИруЕтСЯ Н раэряр»Х RTC)par «3 рОГИСтр фиксации реакции, соответствующих этим замаскированн«: ) I для гтаОRH" fa поиcк,) стол б ца м.

Ф О р м у л 3 и э О (7 р о т (.", н и (1

Л с с 0 ц и 3 T !1 н > i 0 .;) ) и 0 «1 и I! 3 Io н 1(c. У с т и (i Йство, содержащее асспциат«(нный накопитель, первый и второй блоки регистров опроса и маскиравани)2 дан)(ых, первый и второй perl cгры фиксации реакций. при)ем информационные входы перво(0 бло".3 регистров опроса и маскирова.)ия данных ((Вляются информационнь(ми нходами и .рвай группы устройства, упранля ащими нхсц(нл(и перВОЙ Группы каторОГО явля)атся сООтветствующие управляю(цие входы первого б)лака регистров опроса и маскирова(ия данных, 3 выходы с перного по четверт«й каждой группы voToparo подкл(о )оны соо-;ветственно к четвертым, третьим. Порным ;) »,1

1 0

f)COP!III Н„одам ЭДЕМ iii()R П» ISIfL СП)ТНЕТ< . Т В,г «О (и С! О (. I О Л () () 3 С С 0 l (! 1 3 1 !1 R f «)! 0 «2 () К 0 П Ит".. ", s!, Н) 2фОр ма ц НО! (,1« о нх ОД««BT 0 f)oI o 0)n о К3 (.2(:,;. Оон (2 pai:3 . маскиро(3«(ия д»нных

ЯВ«! )юГС; 11))ф()(7« :аци(7«(н((ми ВХОД»М 1 Второй ру(1 пы устр(7йс f ва, vi I p»RciQ f0(QL it1H входами второй группы Korap0(0 являются соогнс2ствующие уир»нляющие входы второ(О блока регистров опроса и л13скировани» д»нных, а выходы с первого ио третий ((ВЖД(Й ГРУПИЫ КОтОРОгО ПОДКЛЮЧЕНЫ СаатВотсг«)о)(! IO K пятым, седьмым и шестым Входам злемонгов памяти соответс)нующей

cTpoKL" ассоциативного накопителя, первые выходы ко орых Обьодинены и подключены к c(..о, нс2ству)ощему информацио«1«(ому входу первого регистра фиксации реакций.

Вь«х(зды которого являются выходами первой группы устройства, вторые выходы элементов памяти каждого столбца ассоци»тивного накопителя подключены к соотнотстну)о)цел1у информационному входу В) орзго регистра фиксации реакций, выходы «0)0p(2! являются выходами второй г руп и ь(ус г рой ств а, уп ра Вл я ющне входы первого «R) Oporo регистров фиксации реакций обьодинены и являются входом чтения устаойстна. а т л и ч 3 ю ш е е с я том, что, с ц)))ью расц)ирония области применения ус i)(2!lciн».2» счет обеспечения ассоциатинног ) поиска по синтезиронанным из строчного и столбцового аргументам, в него нв д()ны первый и второй регистры управления перокл«о(онием каналов опроса и матрица элементов И, причем ()нформационнь«е входы первого регистра уир»вле)(ия переключением каналов опроса подкл)очены к информационным входам первой группы устройства, управляющими входами тротьсй группы которого являются уиравляюгцие входы пеавого регистра ynpt)Bne«sIIR ПЕРЕКЛЮЧЕНИЕМ КаНаЛОВ ОПрОСа, выходы которого подключены к первым входам зломен) ов И соответствующего столбца матриц злел1ентов И, вторые входы эле. ментов И соответствующей с1 роки матрицы элементов И подключены к соответствующим выходам второгc) регистра управления переключе«)ием каналов опроса, информационные входы которого подключены к инфарл;ационным входам второй группы устройства, управляющими входал)и четвертой группы которого являются управляющие входы второго регистра управления переключением каналов опроса.

1824650 ъ

У .

1874650 Ьг 5, - УЛ

Я г (Ъ h

J r;

f „, о (а : р4

1824650

67игФ

Obzf

Составитель В. Борисов

Техред М.Моргентал Корректор М. Куль

Редактор С, Кулакова

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

Заказ 2226 Тираж Подписное

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

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