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

(45) Дата опубликован Государственный камнтет Саввта Министрав СССР аа делам изобретений и открытийргащ боро енинградский институт авиационно(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВ ить обла чи я групией Известно устройство, регистр мас со входами регистр за слов, блок кон ик ольки гсгПри работе с масстройстве каждое с ивами в известно ово, входящее в м ассоциативным иПри этом содерж исследуемых сло в процессе поиск сть выборки зада седлагаежена схема еже изойсгва,иэине ладат сив долнаком это мого о масси данных 1,двигающий дуемых к ассоци жит регис ерсивный Устройство содеррегистр маски 2 ререгистр 3, регистр25 слов 4, регистр зан а задания изменено мое регистможет бьгготсутствуетго элемент ауннодания иссл сги 5, бл возможно массива,Изобретение относится к областилительной техники и предназначено длповой обработки информации с адресапо признакам. ассоциативное запоминающее содержащее регистр данных и ки, выходы которых соединены блока ассоциативной памяти, ятости, регисгр исследуемых чередности (блок для разрешегных ситуаций при наличии не- впадений с признаком опроса),блок ассоциативной памяти выполненячейках ассоциативной памяти с соотв вующими им логическими элементами,Цель изобретения - расширстьприменения ассоциативного запоминающегоустройства,Поставленная цель достигается тем, чтоустройство содержит реверсивный сдвигающий регистр и блок логических операций,входы и выходы реверсивного сдвигающегорегистра соединены соответственно с выходами и входами регисгра занятости, регистразадания исследуемых слов, блока очередности и блока логических операций, входы ивыходы последнего соединены соответсгвенно с выходами и входами регистра заданияисследуемых слов, выходы реверсивногосдвигающего регистра соединень со входами соответствующих логических элементовблока ассоциативной памяти,ативной памяти 6, блок очередности 7, логические элементы 8, входящие в составкаждой ячейки блока 6, блок логическихопераций 9.Регистр данных 1 служит для ввода либо ассоциативных признаков при поиске, ли.бо для ввода информационных слов при записи. Содержимое регистра маски 2 определяет, какие разряды слова участвуют приоперации поиска. Реверсивный сдвигающий щрегистр 3 предназначен для указания слов,которые должны участвовать в поиске, апосле окончания поиска указывает слова,удовлетворяющие требуемому признаку, "Единицаф в каком-либо разряде реверсивного 15регистра 3 разрешает либо сюавнение соответствующего слова, либо его считываниеИмеющаяся возможность сдвига укаэанной"единицы на заданное число разрядов влюбую сторону позволяет осуществить ос Оращение к любому элементу массива, Призаписи единица" в этом регистре определяет ячейку блока ассоциативной памяти,в которую будет производиться запись, Регистр задания исследуемых слов 4 содержит информацию о начале слов или массивов, если в блоке 6 записаны массивы, Регистр занятости 5 позволяет выделить свободные ячейки блока 6, "Единицаф в этомрегистре указывает на то, что соответствую-ЗОшая ячейка блока 6 занята, Блок очередности 7 позволяет осуществить последовательную выборку нескольких слов, обладающиходинаковыми ассоциативными признаками инайденных в результате одной операции поиска. Блок логических операций 9 позволяетосуществить поразрядные логические операции суммирования по модулю два, конъюнкции, дизыонкции над содержимым реверсивного регистра 3 и регистра задания исследуемых слов 4, Результат указанных операций может быть записан как в реверсивный регистр 3, так и в регистр заданияисследуемых слов 4,Ассоциативное запоминающее устройствоработает следующим образом. При осуществлении поиска в регистр данных 1 вводитсячасть ассоциативного признака, равная длине машинного слова, В регистр маски 2вводится маска, равная длине ассоциативно 50го признака. С помощью маски осуществляется выделение разрядов признака, которыеучаству;ог при поиске, Содержимое регистра задания исследуемых слов 4 заноситсяв реверсивный регистр 3. В сравнении участвуют слова, которым соответствуют "единицы" в регистре 3, После сравнения первого признака производится коррекция содержимого реверсивного регистра 3,При этомв случае несовпадения какогото признака, соответствующий этому словуразряд реверсивного регистра 3 обнуляется,После этого вводится следующая часть ассоциативного признака и соответствующаячасть маски, а содержимое реверсивного регистра 3 сдвигается на один разряд, производится сравнение и т,д. В результате этого в реверсивном регистре 3 остаются метки соответствующие информации, удовлетворяющей ассоциативному признаку и условиям поиска, Оставшаяся в реверсивном регистре 3 "единица" обеспечивает считываниепоследующих слов. Если в результате поиска в реверсивном регистре 3 осталось нед //сколько единиц, последовательное считывание всех слов обеспечивается с помощьюблока разрешения конфликтных ситуаций 7.При записи в реверсивный сдвигающийрегистр 3 заносятся "единицы", соогветствующие свободным ячейкам блока 6, для чего достаточно записать в него инвертированное содер;канне регистра занятости 5, Блокразрешения конфликтных ситуаций 7 выделяет первую группу свободных ячеек блока 6,в которые и производится запись либо слов,либо массива, Это оказывается возможным,так как все слова или массивы, записываемые в блок ассоциативной памяти 6, имекодинаковую длину, кратную длине машинного слова. Одновременно с записью слов вячейки блока 6 производится запись фединиц" в соответствующие им разряды регистра занятости 5, а в регистр задания исследуемых слов 4 заносится фединицами всоответствии с первой частью записываемого слова или массива, равной по длинемашинному слову,Для стирания информации достаточно обнулить соответствующие разряды регистров занятости 5 и задания исследуемых слов 4,Блок логических операций 9 позволяет осуществлять поразрядные операции сложения по модулю два, дизъюнкции, конъюнкции над содержимым регистра задания исследуемых слов 4 и реверсивного сдвигающего регистра 3, а результат операции записывать в любой из указанныхрегистров. Это позволяет существенно расширить возможности ассоциативного обращения.Пусть в результате ассоциативного поиска найдено множество массивов А, удовлетворяющих определенному признаку, которое указано в реверсивном регистре 3. Тогда выполнение операции суммирования по модулю два позволяет выделять множество массивов, не удовлетворяющих данному признаку. Опе5рация конъюнкции позволяет выделить в регистре задания исследуемых слов ьлдожест во массивов, удовлетворяющих данному признаку, что является одним из шагов многоступенчатого поиска, Операция дизъюнкции в сочетании со сдвигом содержимого регистра 3 позволяет осуществить расширение множества массивов, к которым в дальнейшем будет вестись обращение.Оформула изобретенияАссоциативное запоминающее устройство, содержащее регистр данных и регистр мас ки, выходы которых соединены со входами блока ассоциативной памяти, регистр занятости, регистр задания исследуемых слов,блок очередности, а блок ассоциативной памяти выполнен на ячейках ассоциативной памяти с соответствующими им логическими элементами, отличающееся тем, что, с целью расширения области применения, устройство содержит реверсивный сдвигающий регистр и блок логических операций, входы и выходы реверсивного сдвигающего регистра соединены соответственно с выходами и входами регистра занятости, регистра задания исследуемых слов, блока очередности и блока логических операций, входы и выходы последнего соединены соответственно с выходами и входамирегистра задания исследуемых слов, выходы реверсивного сдвигающего регистра соединены со входами соответствующих логических элементов блока ассоциативной памяти.Заказ 4910/399 Тираж 723 Подписное 11 НИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская набд. 4/5 филиал ППП "Патентф, г. Ужгород, ул. Проектная, 4