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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (5i) 4 О 11 С 15/ОО

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 4128394/24-24 (22) 26,09 ° 86 (46) 23.07.88. Бюл. N 27 (71} Специальное конструкторское бюро вычислительной техники Института кибернетики АН ЭССР (72) Х.И.Тани (53) 681.327 (088.8) (56) Авторское свидетельства СССР

11 714499, кл. G ll С, 15/ОО, 1978.

Авторское свидетельства СССР

К 576608, кл. G ll С 15/00, 1975. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОИСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам ЭВМ, в которых обращение к памяти осуществляется не по адресу, а по содержанию хранимой в ней информации. Цель изобретения— повышение быстродействия и расшнре„„SU„,: 14 I 1826 А1 ние функциональных возможностей устройства эа счет выполнения логических операций между фрагментами признака поиска. Устройства содержит залами" нающие ячейки 1, параллельно подключенные к входам и выходам устройства.

Каждая ячейка 1 состоит из блока 2 памяти, который комбинацией адресных шнн разбит на страницы, и логики управления блокам 2 памяти. Последняя включает триггеры 4 и 9, элемент

ИЛИ 3, элементы И 5,7,8-11 и развяэывающую схему, элемент HE 6. Устройство позволяет провести общую ини-, циализацию всех ячеек, селективную инициализацию (инициалиэацию всех ячеек, имеюших одинаковое состояние), запись в ячейку ключа и служебной информации, опрос отклика, а также опрос па ключу с межпоэицианной функцией ИЛИ. 1 ил ° !

1411826

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

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

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

Ассоциативное запоминающее устройство (АЗУ} содержит запоминающие ячейки l в состав которых входят ( блоки 2 памяти, элементы ИЛИ 3, дополнительные триггеры 4, первая груп,. na элементов И 5, элементы НЕ 6, вторая и третья группа элементов И 7 и

8, основные триггеры 9, четвертая и пятая группы элементов И 10 и 11.

Входы записи"чтения и информационные входы блоков 2 объединены соответственно и являются входом 12 записичтения и информационным входом 13 устройства, Адресные входы блоков 2 соответственно объединены и являются признаковыми входами 14 и 15 устройства. Входы 16 выборки блоков 2 подключены к выходам соответствующих элементов НЕ 6. Устройство имеет. информационный выход 17, выход 18 положительного результата поиска, первый 19 и второй 20 входы задания режима (соответственно режима дезак" тивации, т.е. исключения ячеек 1 из поиска, .и режима активации, т.е. включения ячеек 1 в поиск), первый установочный вход 21, вход 22 группового обращения, второй установочный вход 23, вход 24 общего обращения, вход 25 запроса и выход 26 отрицательного результата поиска.

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

Далее, если ячейка 1 доступна чтению или записи, то она называет5 !

О

l5

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

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

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

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

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

Подачей сигнала 24 (здесь и в дальнейшем номер сигнала соответствует номеру входа или выхода устройства) через элемент ИЛИ 3 на входы

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

2. Селективная инициализация. Во время работы может возникнуть необходимость в установлении исходного состояния отдельных или групп ячеек

1 АЗУ. При этом инициализация должна быть селективной — содержимое ос-. тальных ячеек не должно меняться.

Селекция осуществляется по признаку состояния, т.е. инициализация прозводится для всех ячеек. имеющих одинаковое состояние. Для этого триггеры 9 всех ячеек 1 приводятся в актив- ное состояние сигналом 20. Сигнал 22 группового обрашения, проходя элемент

И 10 в элемент ИЛИ 3, образует сиг-: нал 16 выборки для всех блоков 2. На вход 12 подается сигнал чтения, .на вход 14 — код состояния, а на входы

15 адрес служебной страницы. В результате на выходе блоков 2 тех ячеl 4118 ек 1, состояние которых соответствует выбираемым, активизируется сигнал„ что приводит соответствующие триггеры 4 в состояние положительного отк5 лика.

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

3. Запись ключа. Запись ключа может быть произведена в одну иэ ячеек

АЗУ, находящихся в инициализированном состоянии. Для селекции.инициализированных ячеек АЗУ сперва осуществляется опрос всех ячеек на состояние "инициализированное". Сигналом 20 активизируются все ячейки, а сигналом 22 группового обращения через элемент И 10 и элемент ИЛИ 3 образуются сигналы 16 выборки. На вхо- 25 ды 14 подается адрес ячейки блока 2, где хранится код состояния ячейки

АЗУ, а на входы 15 — адрес служебной страницы. На вход 12 подается сигнал чтения. Выходные сигналы блока 2 ини- 30 циализированных ячеек АЗУ активные, они устанавливают триггеры 4 в состояние положительного отклика, сни" мая активный сигнал с их выхода, Далее происходит дезактивация тех ячеек 1 АЗУ, триггеры 4 которых остались в исходном состоянии. Это осуществляется сигналом 19, который, проходя через элементы 7 неинициализированных ячеек, устанавливает последние в пассивное состояние. Таким образом, после опроса состояния ак тивными остаются только инициализированные ячейки.

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

Проходя через этот элемент И 11 и элемент ИЛИ 31, сигнал 25 преобразу- ется в сигнал 16, который, проходя через элемент НЕ 6, возбуждает сиг26

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

15, при этом при записи каждого символа активизируется сигнал 12 записи и дается сигнал на вход 13 ("0" или

II 1 II )

После записи ключа в служебной странице стирается признак инициализированности ячейки 1 и туда записывается признак существования в ячейке ключа. Для этого на входы 15 дается адрес служебной страницы, на входы 14 код "0" ячейки блока I a на вход 13 значение "0" и производится запись сигналом 12 ° Затем на входы 14 дается код наличия ключа (например, "1") и осуществляется запись единицы, Для записи следующего ключа можно начинать процедуру сначала или выбирать следующую ячейку из числа активизированных. Для этого необходимо деэактивизировать ту ячейку, в которую только что закончилась sanuc.b Это осуществляется подачей сигнала 21, поступающего на вход триггера 9 и проводящего последнее в состояние, определяемое сигналом 16, поступающим на другой вход триггера

9.. Поскольку в этом режиме сигнал

16 является активным только у самой левой активной ячейки, то деэактивируется именно эта ячейка. После этого сигнал 25 автоматически распространяется до следующей активной свободной ячейки.

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

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

1826

20

55

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

Механизм логического группообразования дает возможность предна" рительного выбора определенной груп- пы ячеек перед опросом АЗУ, 4. Опрос отклика АЗУ. Эта опера,ция является основной при использо:,вании АЗУ при поиске данных. Для это,го исследуемые данные в виде входных слов подают последовательно на вход

АЗУ и определяется значение отклика.

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

Операция начинается с активизации всех ячеек, содержащих ключ определенной группы. Сигналом 20 активизируются все ячейки 1 АЗУ, а сигналом

22 группового обращения через элемент

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

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

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

Триггеры 4 тех ячеек, ключевые символы которых не. совпали с опрашиваемыми, остаются в исходном состоянии и соответствующие элементы

И 7 пропускают сигнал 19 дезактивации, который подается непосредственно после каждого опроса по символу.

Этот сигнал дезактивирует соответствующие ячейки 1, Итак, число активных ячеек с каждым опросом уменьшается остаются активными только те, которые дали совпадение по всем предыдущим символам. Перед каждым опросом триггеры 4 должны быть установлены сигналом 23 в исходное состояние,После опроса по всем символам входного слова следует произвести общий опрос

АЗУ. Это выполняется подачей сигнала

25 запроса, Если он проходит до выхода 26 АЗУ, то это означает, что активных ячеек не осталось и отклик является отрицательным. Если сигнал 26 не появляется, а вместо него появля" ется сигнал 18, то осталась по крайней мере одна активная ячейка и отклик является положительным. По этому же сигналу автоматически выбрана первая активная ячейка (если оста" лось несколько) и путем подачи номера служебной страницы на входы 15 и сигнала чтения на входы 12 можно выполнить последовательное чтение служебной информации (индекса связи или сообщения) . Считываемая информация при этом через элемент И 5 появляется на выходе 17, 5. Опрос по ключу с межпозиционной функцией ИЛИ. В опиеанной операции между всеми позициями входного слова относительно ключа выполняется функция И как обычно в ассоциативных устройствах. Но часто бывает полезным ослабить это условие и получить положительный отклик .и в том, случае, когда определенный символ появляется хотя бы один раз в нескольких смежных позициях, Это особенно полезно при предварительной сортировке данных. Этой цели служит триггер 4, который при нормальной (чисто коньюнкционной) работе только дублирует функции триггера 9. Для выполнения функции ИЛИ между группой смежных позиций в цикле запроса отклика,:.запрос по символу производится после последнего символа группы. Триггерами 4 запоминаются совпадения внутри группы независимо от того, в какой позиции внутри группы они имели место.

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

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

1411826

Составитель . В, Рудаков

Техред Yi . Дидык

Корректор О.Кравцова

1 Редактор С,Патрушева

Подписное. Тираж 590

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

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

Заказ 3665/48

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

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

И четвертой группы объединены и являются входом группового обращения устройства, первые входы элементов

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

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