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

 

Союз Советских

Социалистических

Республик (11) 524226 (61) Дополнительное к авт. свид-ву» (22) Заявлено 27.08.7 4 (21) 2052302/24 с присоединением заявки № (23) Приоритет(43) Опубликовано 05.08.76.Бюллетень №29 (45) Дата опубликования описания 21.10.76 (51) N. Кл.е

G 1i С 15/00

Государственный камнтет

Саввтв Министрав СССР аа делам изобретений и открытий (53) УД1, 681.327.66 (088.8 ) (72) Авторы изобретения

М. Б. Игнатьев, B. А. Мясников, В, Б. Смирнов, B. A. Торгашев и B. И. Шкиргиль

Ленинградский институт авиационного приборостроения (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮШЕЕ УСТРОЙСТВО

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

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

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

Цель изобретения — расширить область применения ассоциативного запоминающего устройства, Поставленная цель достигается тем, что устройство содержит реверсивный сдвигающий регистр и блок логических операций, входы и выходы реверсивного сдвигающего регистра соединены соответственно с выходами и входами регисгра занятости, регистра задания исследуемых слов, блока очередности и блока логических операций, входы и выходы последнего соединены соответсгвенно с выходами и входами регистра задания исследуемь-х слов, выходы реверсивного сдвигающего регистра соединены со входами соответствующих логических элементов блока ассоциативной памяти, На чертеже изображена схема предлагаемого устройства, Устройство содержит регистр данных 1, регистр маски 2, реверсивный сдвигающий регистр 3, регистр задания исследуемых слов 4, регистр занятости 5, олок ассоци=524226 ативной памяти 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 осталось неII I/ сколько единиц, последовательное считывание всех слов обеспечивается с помощью блока разрешения конфликтных ситуаций 7.

При записи в реверсивный сдвигаюший регистр 3 заносятся "единицы", соогветст» вуюшие свободным ячейкам блока 6, для чего достаточно записать в него инвертированное содер;канне регистра занятости 5, Блок разрешения конфликтных ситуаций 7 выделяет первую группу свободных ячеек блока 6, в которые и производится запись либо слов, либо массива. Это оказывается возможным, так как все слова или массивы, записываемые в блок ассоциативной памяти 6, имек одинаковую длину, кратную длине машинного слова. Одновременно с записью слов в ячейки блока 6 производится запись "единиц" в соогветсгвуюшие им разряды региcrpa занятости 5, а в регистр задания исследуемых слов 4 заносится "единица" в соответствии с первой частью записываемого слова или массива, равной по длине машинному слову, Лля стирания информации достаточно обнулить с оответствуюшие разряды регистров занятости 5 и задания исследуемых слов 4.

Блок логических операций 9 позволяет осушесгвлять поразрядные операции сложения по модулю два, дизъюнкции, конъюнкции над содержимым регистра задания исследуемых слов 4 и реверсивного сдвигающего регистра 3, а результат операции записывать в любой из указанныхрегистров. Это позволяет существенно расширить возможности ассоциативного обращения.

Пусть в результате ассоциативного поиска найдено множество массивов А, удовлетворяюших определенному признаку, которое указано в реверсивном регистре 3. Тогда выполнение операции суммирования по модулю два позволяет выделять множество массивов, не удовлетворяюших данному признаку. One5 рация конъюнкции позволяет выделить в регистре задания исследуемых слов лтожест во массивов, удовлетворяющих данному признаку, что является одним из шагов многоступенчатого поиска, Операция дизъюнкции в сочетании со сдвигом содержимого регистра 3 позволяет осуществить расширение множества массивов, к которым в дальнейшем будет вестись обращение.

<0

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

Ассоциативное запоминающее ycrpoAcrao„ содержащее регистр данных и регистр мас- Ы ки, выходы которых соединены со входами блока ассоциативной памяти, регистр занятости, регистр задания исследуемых слов, блок очередности, а блок ассоциативной памяти выполнен на ячейках ассоциативной памяти с cooòâåòñòâóþùèìè им логическими элементами, отличающееся тем, что, с целью расширения области применения, устройство содержит реверсивный сдвигающий регистр и блок логических операций, входы и выходы реверсивного сдвигающего регистра соединены соответственно с выходами и входами регистра занятости, регистра задания исследуемых слов, блока очередности и блока логических операций, входы и выходы последнего соединены соответственно с выходами и входами регистра задания исследуемых слов, выходы реверсивного сдвигающего регистра соединены со входами соответствующих логических элементов блока ассоциативной памяти.

Составитель З. Сечина

Редактор В. Фельдман Техред А. Богдан Корректор А. Гриценко

Заказ 491 0/399 Тираж 723 Подписное

Е1НИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4