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

(5)5 6 САНИЕ ИЗОБРЕТЕНИ аТЮ.;": - ." ". ;РМО д,с;,1 (, .г .г, цифровой обработки изображений, при решении информационно-логических задач, задач поиска и сортировки данных. Целью изобретения является расширение области применения устройства за счет обеспечения ассоциативного поиска по синтезированным из строчного и столбцового аргументам. Ассоциативное запоминающее устройство содержит ассоциативный накопитель, первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры фиксации реакции, первый и второй регистры управления переключением каналов опроса и матрицу элементов И, 5 ил. нститут О,1 НА)ОЩЕ Е ислит минающим)ьзовано вранения и реализации сорого блоков рения данных,Ячейка ассоциативной памяти (фиг.1) содержит триггер 1, входы установки в "1" и "0" которого подключены к выходам соответственно первого 2 и второго 3 элементов И - НЕ, а прямой и инверсный выходы подключены соответственно к первым входам третьего 4 и четвертого 5, а также пятого 6 и шестого 7 элементов И - НЕ. Выходы первого канала переключателя 8 присоединены соответственно ко вторым входам третьего 4 и четвертого 5 элементов И - НЕ, а выходы второго канала - соответственно ко вторым входам пятого б и шестого 7 элементов ИНЕ, Вторые входы первого и второго 3 элементов И-НЕ присоединены соответственно к первому 9 и второму 10 информационным входам записи Входы ОСУДАРСТГЗЕН)К)Е ПАТЕНТНОЕДОМСТВО СССРОСГ)АТЕНТ СССР) АВТОРСКОМУ СВИДЕТЕЛЬСТВ(57) Изобретение относится к выной технике, в частности к запоустройствам и может быть испоспециализированных системах Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может найти применение в специализированных системах хранения и цифровой обработки изображений, при решении информационно-ло ических задач, задач поиска и сортировки данных.Целью изобретения является расширение области применения устройства за счет обеспечения ассоциативного поиска по синтезированным иэ строчного и столбцового аргументам.На фиг.1 представлена схема ячейки ассоциативной памяти; на фиг.2 - пример реализации двухканального двухразрядного коммутатора; на фиг.3 - схема предлагаемого ассоциативного запоминающего устройства с матричным ассоциативным накопителем (ограничительные резисторы не показаны); на фиг.4 и фиг.5 - примеры ответственно первого и втогистров опроса и маскирова 18246505 10 15 20 25 30 35 40 45 50 55 первого канала двухканального двухразрядного переключателя подключены соответственно к первому 11 и второму 12 входам опроса по столбцу, Первые входы первого 2 и второго 3 элементов И-НЕ присоединены ко входу сигнала 13 записи, Входы второго канала переключателя подключены соответственно к первому 14 и второму 15 входам опроса по строке, а вход коммутации - ко входу 16 управления переключением каналов опроса. При нуле на этом входе осуществляется прямое соответствие входов и выходов каналов, при единице происходит перекоммутация каналов. Выходы третьего 4 и четвертого 5 элементов И-НЕ обьединеь и ,одключсчы к выходу 17 строчного ассоциативного поиска, а соединенные ме:щу собой выходы пя 1 ого 6 и шестого 7 ;леметоо И-Н подлоченд к выходу 18 столбцового ассоциативного поиска,Кро;е того, выход 18, присоединенный к выходам указанных элементов И-НЕ ячеек соотоегствуощего столбца ассоциативного накопителя, через первый ограичительньй элемент 19 подключен ко входу 20 потенциала логической единицы,Выход же 17, присоединенный к выходам эле оптов И - НЕ ячеек соответстоующеи сгроки ассоциативного накопителя, ч;,роз второй ограничительный элемент 21 под"люнен ко входу 20 потенциала лоиче. сход единицы,Дгухх; аоный двухразрядный колмуга.р фиг.21 содержит элементы И с первого 22 по оосьмой 29, элементы ИЛИ с первого 30 по чеворгый 33 и инзертср 34.На фиг.3 представлена схема предлагаемого ассоциативного запоминающего устройства, состоящего из ассоциативного накопителя 35, содержащего ячейки 36 и группу 37 элементов И первого 38 и второго 39 блоков регистров опроса и маскирования данных, первого 40 и второго 41 регистров управления переключением каналов опроса, первого 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- сигнал чтения из накопиело 35;65 - сигнал записи о регистр 44 опросаблока 38:66 - сигнал записи о реистр 15;1 аскрования блока 38;67 - сигнал сброса о "Г регистров огроса 44 и маскирования 45 блока 38 и первого40 регистра управления пг;реключением каналов опроса;68 - сигнал записи о регистр 40;69 - сигнал записи в регистр 54 опросаблока 39;70 сигнал записи о регистр 55 маскирования блока 39;71 - си нлл сброса о 0" регистров опроса 54 и маскирования 55 блока 39 и второго41 регистра управления переключением каналов о роса;72 - сигнал за.иси о регистр 41,Входы:галов 65-68 - управляющиевходы перой группы устройства; входы сигналов ",", - управляюцие входы второйгруппы устройсва. Входы си налов 63, 64явл.ю 1 сч общими для переой и вгоройгругн управляющих входов устройства,73 и 74 - соответственно перьая и вторая группы входов устройства,75 и 76 - соответственно первая и вторая группы выходов устройстоа.Ячейки ассоциативной памяти благодаря подаче управляющих сигналов позволяют осуществить выполнение следу ощихопераций в ассоциативном запоминающемустройстве: запись информации по заданному адресу (группе адресов) с маскированием произвольных разрядовзаписываемого слова; считывание информации по заданному адресу аргумента какпо строкам, так и по столбцам; коньюнктионое считывание строк и столбцов; параллельный ассоциативный поиск ключевогоаргумента по строкам, по столбцам и одно.временно по строкам и столбцам накопителя по критерию "равно" с максированиемпроизвольных разрядов: смешанный ассоциативный поиск по строкам и столбцамассоциативного накопителя по аргументампоиска, гнтезирооаым из строцогостолбцового аргументов поиска; фиксацию количества несовпадений аргументов по. иска как с отдельными выделенными сроками и столбцами ассоциативного накопителя, так и с конъюнкцией выделенных строк и столбцов.В режиме маскируемой записи по строкам со входов 73 записываемое слово фиксируется в регистре 44 опроса по сигналу 65. Затем в регистр 45 маскирования с этих же входов записывается маска по сигналу бб, Одновременно с этим со входов 74 в регистр 54 блока 39 записывается дешиф рированний адрес строки по сигналу 69. И при подаче сигнала 63 записи в накопитель 35 на олоды 9 и 10 всех элементов 36 памяти накопителя поступит одна из следующих комбинаций сигналов. "10" - при записи единицы, "01" - при записи нуля, "00" - при маскировании записи; на входы 13 элементов 36 памяти адресуемой строки подается уровень логической единицы, Таким образом осуществляется запись по заданному адресу,В случае записи слова по группе адресов в регистр 54 опроса блока 39 должен быть записан аргумент, в котором единицы соответствуют адресуемым строкам накопителя до подачи сигнала 63 записи,При считывании информации по строкам по заданному адресу в разряд регистра 54 опроса блока 39, соответствующий адресу считываемой строки, заносится единица, Остальные разряди должны быть замаскированы соответствующей маской, записанной в регистр 55 этого блока, Регистры 40 и 41 при этом должны быть сброшены в ноль, И при подаче сигнала 64 на входы 14 и 15 выбранной строки поступает комбинация "01", которая при нуле на входе 1 б элементов памяти подается соответственно на вторые входы пятого б и шестого 7 элементов И - НЕ элементов памяти выбранной строки. В случае хранения триггером 1 единицы на выходе 18 соответствующей ячейки памяти сохранится уровень логической единицы, в случае хранения нуля выход 18 обнулится, И по заднему фронту сигнала 64 считываемое слово зафиксируется во втором 43 регистре фиксации реакций. В режиме строчного конъюнктивного считывания единицы должны быть записаны в те разряды регистра 54 опроса блока 39. которые соответствуют адресам считываемых строк накопителя,Операция считывания по строке может быть также осуществлена по-другому. В регистр 44 блока 38 и в регистр 40 записываются единицы во все разряды, Единица также записывается в разряд регистра 41,5 1 О 15 20 25 30 35 40 45 50 55 соответствующий ядрР у сч". игал , в етро ки. И Г 1 ри подае сигнала 64 нл в,11111 и 12 всех ячеек накопителя поступи цбина ция сигналов 01", которая при едн чще нл входе 16 ячеек памяги считиваемо.: строки подается соответственно на вторив воды пятого 6 и шестого 7 элементов И- НЕ ячеек памяти выбоанной строки, Далее аналогично рассмотренному варианту строчного считывания,Используя этот подход, можно выполнить и строчное коньюнктивное чтение,При считыоании заданного разрядного среза в разряд регистра 44 опроса блока 38, соответствующий адресу считываемого столбца, заносится единица, Остальные разряды должны быть замаскированы соответствующей маской, записанной в регистр 45 этого блока, Регистры 40 и 41 при этом должны быть сброшены в "0". И при подаче сигнала 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 этого блока - маска. И при сброшенных в "0"5 10 15 20 25 30 35 40 45 50 55 регистрах 40 и 41 при подаче этого сигнала 64 на входы 11 и 12 ячеек памяти поступит одна из следующих комбинаций сигналов; "01" - сравнение с единицей, "10" - сравнение с нулем, "00" - маскирование поиска, При несовпадении содержимого ячейки с признаком опроса обнулится выход 17 этой ячейки и, следовательно, на шине, соединяющей эти выходы 17 элементов памяти соответствующей строки накопителя, установится потенциал логического нуля, Если произошло совпадение или маскирование опроса, то выходы 17 сохранят уроаень логической единицы. Результат строчного ассоциативного поиска фиксируется о первом 42 регистре фиксации реакций по заднему фронту сигнала 64, Единицы о разрядах этого регистра указывают на позиции строк, совпавших с мзскируемой строкой - аргументом.В режиме параллельного ассоциативного маскируемого поиска по столбцам в регистр 54 опроса блока 39 заносится аргумент поиска, з о регистр 55 этого блока - маска И при сброшенных о "0" регис 1 озх 40 и 41 при подаче сигнала 64 на входы 14 и 15 ячеек памяти поступит одна из следующих комбинаций сигналов: "01" - сравнение с единицей; "10" - сравнение с нулем; "00" - маскиоонание поиска, При несовпадении содержимого ячейки с признаком опросз обнулится выход 18 этой ячейки и, следовательно,нз шине, соединяющей выходы 18 ячеек памяти соответствующего столбца накопителя, установится потенциал логического нуля, Если произошло совпадение или маскирование опроса, то выходы 18 ячеек памяти соответствующего столбца накопителя сохранят уровень логической единицы. Результат столбцового ассоциативного поиска фиксируется оо втором 43 регистре фиксации реакций по заднему фронту сигнала 64, Единицы в разрядах этого регистра указывают на позиции столбцов, совпавших с мзскируемым столбцом - аргументом.Режимы ассоциативного поиска по строкам и столбцам могут быть совмещены,При смешанном ассоциативном поиске по строкам по синтезированным из строчного и столбцового аргументам поиска осуществляется возможность замены одного или нескольких (любых) разрядов строки - аргумента поиска для каждой отдельной строки ассоциативного накопителя содержимым (в том числе и маскированным) разряда второго 39 блока регистров опроса и маскирования, соответствующего этой строке,При этом в соответствующих разрядах регистров 40 и 41 должны быть записаны единицы, устанавливающие в единицу выходы элементов 37 И, подключенные ко входам 16 соответствующих ячеек накопителя, Таким образом, осущестоляется перекоммутация сгрочного и столбцового каналов опроса указанных ячеек. При этом перед инициализацией поиска сигналом 64 в разряды блока 39, соответствуюоие заменяемым разрядам строки - аргумента поиска, для каждой участвующей о той замене строки записывается необходимое мзскируемое значение,При смешанном ассоциативном поиске по столбцам по синтезированным иэ столбцового и строчного аргументам поиска осуществляется возможность замены одного или нескольких (произвольных) разрядов столбца - аргумента поиска для каждого отдельного столбца ассоциативного накопителя содержимым (в том числе и маскированным) разряда первого 38 блока регистров опроса и маскирования, соответствующего этому столбцу. Для этого режима справедливо осе вышесказанное о смешанном ассоциативном поиске по строкам в собственном контексте,При фиксации количесгва несоопадений строки-аргумента поиска с выделенной строкой ассоциативного накопителя до под. ачи сигнала 64 в регистры блока 38 должен быть записан маскируемый аргумент поиска, в регистр 40 записаны единицы оо все разряды. Единица также должна быть занесена о разряд регистра 41, соответствующий строке, сравниваемой с аргументом поиска, Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39, И при подаче сигнала 64 аргумент поиска сравнивается с выделенной строкой с фиксацией результата сравнения оо втором 43 регисгре фиксации реакций. Число нулей, зафиксированное о этом регистре, соответствует количеству несовпадений аргумента поиска с выделенной строкой,При осуществлении фиксации количества несовпадений строки-аргумента поиска с конъюнкцией выделенных строк при прочих прежних условиях единицы должны быть занесены в разряды регистра 41, соответствующие строкам, сравниваемым с аргументом поиска. Все остальные строки должны быть замаскированы содержимым регистра 55 маскирования блока 39, причем для этих замаскированных для столбцового ассоциативного поиска строк реализуется ассоциативный поиск по строкам, И результат этого строчного поиска фиксируется в разрядах первого регистра 42 фиксации реакций, соответствующих этим ззмзскиро 18245 Аванным для столбцовоГГ асц 1 дтл 1 оо поиска строкам.Г 1 ри осуцествлоии ф ксдцик кли ос твд несовпадений столбца-дгу.,ед пс иска с выделеИмл :толбцо л ассоцидтл 1 ого накопителя до ппдди сигнала б 4 В ро стрь блока 39 До 1;1;о 1 бы ь эапиган мдскрус 1 ьЙ аргу.е 1 по .Хдрегистр 41 здиоан, ОД;111 лцы Во Все рд.ряДь, Единица таке должна быль здссо 1 в разряд Г.егистра 40, соотвт тств,юц 1 Й строке, срдвиваомой с артулетом поис:.д. 13 се остальые столбцы должы быть здлдс.и. рованы содержимьм регистра 15 к 1 дскироВды 1 блока ЗЯ. И при подаче си длд 04 др;мо 1 т поиска срзвися .; Вдолоннм столбцо 1 с фиксдЦиой результд 3 ср.Вне ния в первом 42 регистре ф;ксдции редкЦИй. ЧИСЛО НУЛЕИ, ЗафИКСИРОДОЕ В ЭТОМ РРГИСТРР, СООТВРТСВУЕТ КОЛИЧЕСТВУ НОСОВ- падений аргуонтд поскд с Выделенным столбцом.Гри осуцосаленин фиксации количест ва несовпадений стг)лбцд- аргу.Ста поиска с коньюнкцией Выделеых стоб,ов при проих грежпх условиях единицы должны быть занесены В разряды ргистрд 40, соответствую 1 ио столбцал, срдонвдомым с аргумонтол поиска, Все Ос .,но стобцы должны бп ь здл:скирог 1 н 1 сод".ржимым регистра 45 л;1.кировая блгкд 30. Гричем, для эти: здмаскировзн 1 Х для строчОГО дссоци:тивнОГО поиска столбцов реализуется дссо. дтивный птл гк по столбцам. И результат этого столбцог.Ого Гоиска фИКСИруЕтСя В рдэрярдк ВтОрОГ, 43 рОГИСтрд фиксации реакции, соответствующих этим залдскировдн 1:ф 1 для гтооцн 1 о поиска столбцам..1 О р м у л а и э О О р о т .", н и я Лссоцидты В нов за полидк 11 ог. ус ТГзйство, содержащее дссоциат 1 вныЙ накопитель, первый и второй блоки регистров опроса и маскирОВдни)1 ддн 1 ьх, первяй и второй регистры фиксации реакций. причем информационные Входы первого бло"д регистров опроса и мдскировд ия данных я 1- ляются информационньми модами первой группы устройства, управля ощими Входами первой группы которого являотся соответствующие управляющие входы первого блока регистров опроса и мдскироваия данных, а Выходы с первого по четвертый каждой группы которого подоо оны соот. ветственно к четвертым, третьим, первым и Г 10 15 20 25 30 35 40 50 55 Вторьц годам элерон;ОВ плмяи солвет.Тоупцог. СГОЛ 51 д дССОрдТИВНОО НПКППИ- тол 1 11110 рь 1 зцио 111 о ВхОДы ВтороО блока р".1 к.тоО 11 роса л маскирования данных Я 1.1 ЮГС. Иф:Р 1.дЦИОН 111 ЛИ ВХОДЯМИ ВТО- рой гругпы устройсва, у рдвляющими входами Второй группы котороо являются соо Гвотствующие уравляющие входы второго блока регистров опроса и мдскирова 1111 данных, а Выходы с первого по третий тажДкй ГРУПЫ КОТОРОГО ПОДКЛЮЧЕНЫ СООтВОТС ГО 1110 К ПЯТЬм, СЕДЬМЫМ И ЩОСТЬМ ВХО- ддм злемогов памяти соответсвующей строки ассоциативного накопителя, первые выходы ко орьх обьодинены и подключены к со; В:ствуощему информационному входу первого регистра фиксации реакций. вьходы которого являются выходами перВой группы устройства, вторые выходы элементов памяти каждого столбца ассоциативного накопителя подключены к сосп детствуощему информационному Входу Ворого регистра фиксации реакций, выходы которого являются выходами второй группы устройства, управляющие входы первого и Ворого регистров фиксации реакций обьодинены и являются входом чтения устоойствд отличающееся том, что, с целью рдсцирония области применения ус Гройствд . д счет обеспечеия ассоциативногз поиска по синтезированным из строчного и столбцового аргументам, в него Вв доны первый и второй регистры управления перокло ениел каналов опроса и матрица элементов И, причем нформационнье входы первого регистра упрдвле;ия переключением каналов опроса подклочены к информационным входам первой группы устройствд, управляющими Входами тротьсй группы которого являются управляюцие входы пеового регистра управления переключением кандлов опроса, выходы которого подключены к первым входам зтокянк ов И соответствующего столбца мтриц. злеметов И, вторые Входы эле ментов И соответствующей с-роки матрицы элементов И подключены к соответствующим выходам Второго регистра управления переключеием каналов опроса, информационнье входы которого подключены к информационным входам второй группы устройства, управляющими входами четвертой группы которого являются управляющие входы второго регистра управления переключением каналов опроса, 1824 Б 501824650 67 игФ 6 Ьгх едактор С, Кулако Заказ 2226 Тираж Подписное ВНИИХИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва. Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 Ют ей У оставитель В. Борисовехред М,Моргентал Корректор М. Куль