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

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

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

Ассоциативное запоми1иющее устройство, содержащее регистр данных и регистр маски, выходы которых соединены со входами блока ассоциативной памяти, регистр занятости, регистр задания исследуемых слов,

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

U/