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

ts

00

ю

05

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

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

На чертеже представлена функциональная схема ассоциативного запоминающего устройства.

Ассоциативное запоминающее устройство () содержит запоминающие ячейки 1, в состав которьк входят ;.; j блоки 2 памяти, элементы ИЛИ 3, до- I полнительные триггеры 4, первая груп {. па элементов И 5, элементы PIE 6, в то I рая и третья группа элементов И 7 и I 8, основные триггеры 9, четвертая и I пятая группы элементов И 10 и IK I Входы записи-чтения- и информационные ; входы блоков 2 объединены соответст- I венно и являются входом 12 записи- чтения и информационным входом I3 устройства. Адресные входы блоков 2 соответственно объединены и являются признаковыми входами 14 и 15 устройства. Входы 16 выборки блоков 2 подключены к выходам соответствующих элементов НЕ 6 Устройство имеет информационный выход 17, выход 18 положительного результата поиска, первый 19 и второй 20 входы задания релсима (соответственно режима дезактивации, Тое. исключения ячеек I из поиска,, и режима активации, т,е, включения ячеек 1 в поиск), первый установочный вход 21, вход 22 группового обращения, второй установочный вход 23, вход 24 общего обращения j, вход 25 запроса и выход 26 отрицательного результата поиска.

В зависимости от применения АЗУ, состояние ячейки i может иметь несколько значенийр например неопределенное, инициализированное, содержащее ключ, т обо признак поиска, принадлежность к определенной группе ячеек и т«д.

Далее, если ячейка 1 доступна чтению шш записи, то она назьшает-

ся активной, в противном случае - пассивной. Активность ячейки 1 определяется состоянием триггера 9

Рассмотрим операции, выполняемые предложенным АЗУо

I о Общая инициализация о После включения устройства содержимое всех ячеек 1 имеет случайное значение о

Также .имеют случайное состояние

триггеры 4 и 9. Для установления определенного начального состояния применяется операция общей инициализации Для увеличения быстродействия

АЗУ, общая инициализация выполняется параллельно для всех ячеек АЗУ.

Подачей сигнала 24 (здесь и в дальнейшем номер сигнала соответствует номеру входа или выхода устройства) через элемент ИЛИ 3 на входы 16 всех блоков 2 подается сигнал выборки На вход 12 подается сигнал записи, а на вход 13 - значение логического нуля. На входы 14 и 15 по-.

даются последовательно адреса всех

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

В конце инициализации ячеек на

служебную страницу записывается приз-, нак инициализированности. Это осуществляется подачей сигнала 24, сигнала 12 записи, единичного значения сигнала 13 данных, .адреса служебной страницы на входы 15 и кода состояния на входы 14. После этого триггеры 4 и 9 устанавливаются в исходное состояние подачей сигналов 23 и 21 соответственно.

2о Селективная инициализация. Во время работы может возникнуть необходимость в установлении исходного состояния отдельных или групп ячеек 1 АЗУо При этом инициализация должна быть селективной - содержимое ос-- тальных ячеек не должно меняться Селекция осуществляется по признаку состояния, т.е инициализация проз- водится для всех ячеек, имеющих одинаковое состояние. Для этого триггеры 9 всех ячеек I приводятся в активное состояние сигналом 20„ Сигнал 22 группового обращения, проходя элемент И 10 в элемент ИЛИ 3, образует сиг-: нал 16 выборки для всех блоков 2 На вход 12 подается сигнал чтения,-на вход 14 - код состояния, а на входы 15 адрес служебной страницы В результате на выходе блоков 2 тех яче

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

Триггеры 4 тех ячеек, состояние которых не совпадает с выбираемым, остаются в исходном состоянии и соответствующие элементы И 7 пропускают сигнал 19, который подается непосредственно после этого. Далее выполняется процесс инигщализации аналогично операций общей инициализации.

3, Запись ключа. Запись ключа может быть произведена в одну из ячеек АЗУ, находящихся в инициализированном состоянии, Дпя селекции, инициали зированньгх ячеек АЗУ сперва осуществляется опрос всех ячеек на состояние инициализированное. Сигналом 20 активизируются все ячейки, а сигналом 22 группового обращения через элемент И 10 и элемент ИЛИ 3 образуются сигналы 16 выборки. На входы 14 подается адрес ячейки блока 2, где хранится код состояния ячейки АЗУ, а на входы 15 - адрес служебной страницы, H( вход 12 подается сигнал чтения. Выходные сигналы блока 2 инициализированных ячеек АЗУ активные, они устанавливают триггеры 4 в состояние положительного отклика, снимая активный сигнал с их выхода, Далее происходит дезактивация тех ячеек 1 АЗУ, триггеры 4 которых остались Б исходном состоянии. Это осуществляется сигналом 19, который, проходя через элементы 7 неинициализированных ячеек, устанавливает последние в пассивное состояние. Таким образом, после опроса состояния ак- тивными остаются только инициализированные ячейки.

Для записи ключа выбирается одйа ячейка ИЗ числа активных ячеек. Это осуществляется по принципу выбора первой активной ячейки. Для этого на вход 25 АЗУ подается сигнал запроса Если первая (начиная слева) ячейка 1 пассивная, то этот сигнал через открытый элемент И 8 распространяется дальше, до первой активной ячейки у которой элемент И 8 закрыт сигнало от триггера 9, а элемент И 11 открыт Проходя через этот элемент И 11 и элемент ИЛИ 31, сигнал 25 преобразуется в сигнал 16, который, проходя через элемент НЕ 6, возбуждает сиг

0

5

нал на выходе 18, подтверждающий,что имеется по крайней мере одна инициализированная ячейка 1, Если в АЗУ нет ни одной инициализированной ячейки, то сигнал 25 появляется на выходе 26 АЗУ в виде сигнала, свидетельствующего о том, что инициализированных ячеек нет. При наличии инициализированной ячейки начинается запись ключа посимвольно последовательно. Коды ключевых символов подаются на входы 14, а коды порядкового номера символов в ключе на входы 15, при этом при записи каждого символа активизируется сигнал 12 записи и дается сигнал на вход 13 (О или 1),

После записи ключа в служебной странице стирается признак инициали- зированности ячейки 1 и туда записывается признак существования в ячейке ключа. Для этого на входы 15 дается адрес служебной страницы, на входы 14 код О ячейки блока I, а на вход 13 значение О и производится запись сигналом 12 Затем на входы 14 дается код наличия ключа (например, I) и осуществляется запись единицы.

Для записи следующего ключа можно начинать процедуру сначала или выбирать следующую ячейку из числа активизированных. Для этого необхо димо дезактивизировать ту ячейку, в , которую только что закончилась запись Это осуществляется подачей сигнала 2, поступающего на вход триггера 9 и проводящего последнее в состояние, .определяемое сигналом 16, поступающим на другой вход триггера 9., Поскольку в этом режиме сигнал 16 является активньм только у самой левой активной ячейки, то дезактивн5 руется именно эта ячейка После этого сигнал 25 автоматически распространяется до следующей активной свободной ячейки.

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

0

0

0

5

символов) то одна ячейка АЗУ может принадлежать и нескольким группам

Механизм логического группооб- разования дает возможность предварительного выбора определенной группы ячеек перед опросом АЗУ.

А. Опрос отклика АЗУ, Эта операция является основной при использовании АЗУ при поиске данных. Для го исследуемые данные в виде входных слов подают последовательно на вход АЗУ и определяется значение отклика. Если входное слово (или его фрагмент) совпадает по крайней мере с одним ключом, записанным в ячейки АЗУ, то отклик является положительным, в противном случае - отрицательным.

Операция начинается с активизации всех ячеек, содержащих ключ определенной группы Сигналом 20 активизируются все ячейки 1 АЗУ, а сигналом 22 группового обращения через элемент И 10 и элемент ИЛИ 3 образуется сигнал 16 выборки для всех блоков 2, На входы 14 подается код группы (номер состояния), а на входы 15 - адрес служебной страницы. На вход 12 подается сигнал чтения. Выходные сигналы блоков 2 тех ячеек 1, которые принадлежат к данной группе (активные),. устанавливают триггеры 4 в состояние положительного отклика. Сигналом 19 1через элемент 7 дезактивизируются все остальные ячейки АЗУ„ Таким образом, активными остаются только ячейки желаемой группы.

Опрос происходит параллельно для всех активных ячеек 1 посимвольно- последовательно. Код очередного символа входного слова подается на входы 14, а код порядкового номера симг вола - на входы 15с По сигналу 12 чтения на выходе блоков 2 тех ячеек 1,. ключевой символ на данной позиции которых совпадает с входным символом, возникает сигнал, что приводит соотг вётствующие триггеры отклика 4 в состояние положительного отклика.

Триггеры 4 тех ячеек, ключевые символы которых не совпали с опраши-; ваемыми, остаются в исходном состоянии и соответствующие элементы И 7 пропускают сигнал 19 дезактивации, который подается непосредственно после каждого опроса по символу. Этот сигнал дезактивирует соответст- зующие ячейки 1 Итак, число активных ячеек с каждым опросом уменьшается 14118266

остаются активными только те, которые дали совпадение по всем предыдущим символам.- Перед каждым опросом

J. триггеры 4 должны быть установлены сигналом 23 в исходное состояние,После опроса по всем символам входного слова следует произвести общий опрос АЗУо Это выполняется подачей сигнала это-10 25 запроса. Если он проходит до выхода 26 АЗУ, то это означает, что активных ячеек не осталось и отклик является отрицательным. Если сигнал 26 не появляется, а вместо него появля15 ется сигнал 18, то осталась по крайней мере одна активная ячейка и отклик является положительным. По этому же сигналу автоматически выбрана первая активная ячейка (если оста20 лось несколько) и путем подачи номера служебной страницы на входы 15 и сигнала чтения на входы 12 можно выполнить последовательное чт ение служебной информации (индекса связи

25 или сообщения), Считьшаемая информация при этом через элемент И 5 появ- .ляется на выходе 17,

5 в Опрос по ключу с межпозиционной функцией ИЛИ, В описанной опера30 ции между всеми позициями входного слова относительно ключа выполняется функция И как обычно в ассоциативных устройствах. Но часто бывает полезным ослабить это условие и поng лучить положительный отклик и в том , случае, когда определенный символ появляется хотя -бы один раз в нескольких смежных позициях. Это особенно полезно при предварительной сор40 тировке данных. Этой цели служит триггер 4, который при нормальной (чисто коньюнкционной) работе только, дублирует функции триггера 9, Для вьшолнения функции ИЛИ между груп45 пой смежных позиций в цикле запроса отклика, .-Запрос по символу производится после последнего символа группы. Триггерами 4 запоминаются совпадения внутри группы независимо

50 от того, в какой позиции внутри . группы они имели, место.

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

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

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

пы, выход которого подключен к информационному входу соответствующего основного триггера, вторые входы элементов И второй группы объединены и являются первым входом задания режима устройства, выходы элементов НЕ объединены и являются выходом положительного результата поиска, втод0 5

0

5

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

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам ЭВМ, в которых обращение к памяти осуществляется не по адресу, а по содержанию хранимой в ней информации. Цель изобретения - повьшение быстродействия и расширение функциональных возможностей устройства за счет выполнения логических операций между фрагментами признака поиска о. Устройство содержит запоминающие ячейки 1, параллельно подключенные к входам и выходам устройства. Каждая ячейка 1 состоит из блока 2 памяти5 который комбинацией адресных шин разбит на страницы, и логики управления блоком 2 памяти Последняя включает триггеры 4 и 9, элемент ИЛИ 3, элементы И 5,7,8-11 и развя- зьшающую схему, элемент НЕ 6 Устройство позволяет провести общую иниг циализацию всех ячеек, селективную ини диализацию (инициализацию всех ячеек, имеющих одинаковое состояние), запись в ячейку ключа и служебной информации, опрос отклика, а также опрос по ключу с межпозиционной функцией ИЛИ. 1 ил. I S (О