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

(51) 4 О 11 С 15/ОО ОПИСАНИЕ ИЗОБРЕТЕ гичес нак ломи подклюройства ока 2адресных ехникиССР ам и уст из бл выхоостои ые к вход ая ячейка чен Каж пам ти, которыи камбин н клю Об Ю ОСУДАРСТНЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(71) Специальное конструкторское бюро вычислительной т Института кибернетики АН Э(56) Авторское свидетельство СССР У 714499, кл. 0 11 С, 1500, 1978.Авторское свидетельство СССР Кф 576608, кл. 0 11 С 15/00, 1975, (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО(57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам ЭВМ, в которых обращение к памяти осуществляется не по адресу, а по содержанию хранимой в ней информации. Цель изобретения - повышение быстродействия и расшнрение функциональных возможнос ройства за счет выполнения л операций между фрагментами п поиска. Устройство содержит нающие ячейки 1, параллельно шнн разбит на страницы, и логики упле ия блокам 2 памяти, Последняя в чает триггеры 4 и 9, элемент ИЛИ 3, элементы И 5,7,8-11 и развяэывающую схему, элемент НЕ 6. Устройство позволяет провести общую ини-, циализацию всех ячеек, селективную ини 1 иализацию (инициализацию всех ячеек, имеюших одинаковое состояние), запись в ячейку ключа и служебной информации, опрос отклика, а также опрос по ключу с межпоэиционной функцией ИЛИ. 1 илИзобретение относится к вычисли"тельной технике и, в частности кобласти запоминающих устройств ЭВМ,в которых обращение к памяти осуществляется не по адресу, а по содержанию или по фрагменту содержания хранимой в ней информации, и может бытьприменено в специальных блоках ЭВМ,предназначенных для быстрого поискаданных из больших массивов,Цель изобретения - повышение быстродействия и расширение функциональ"ных возможностей устройства за счетвыполнения логических операций междуфрагментами признака поиска.На чертеже представлена функциональная схема ассоциативного запоми"нающего устройства.Ассоциативное запоминающее устройство (АЗУ) содержит запоминающиеячейки 1, в состав которых входятблоки 2 памяти, элементы ИЛИ 3, дополнительные триггеры 4, первая группа элементов И 5, элементы НЕ 6, вторая и третья группа элементов И 7 и8, основные триггеры 9, четвертая ипятая группы элементов И 10 и 11,Входы записи"чтения и информационныевходы блоков 2 объединены соответственно и являются входом 12 записичтения и информационным входом 13устройства, Адресные входы блоков 2соответственно объединены и являются признаковыми входами 14 и 15 устройства. Входы 16 выборки блоков 2подключены к выходам соответствующих элементов НЕ б. Устройство имеетинформационный выход 17, выход 18положительного результата поиска,первый 19 и второй 20 входы заданиярежима (соответственно режима дезак"тивации, т.е. исключения ячеек 1 изпоиска, и режима активации, т.е.включения ячеек 1 в поиск), первыйустановочный вход 21, вход 22 группового обращения, второй установочный вход 23, вход 24 общего обращения, вход 25 запроса и выход 26 отрицательного результата поиска.В зависимости от применения АЗУ,состояние ячейки 1 может иметь несколько значений, например: неопределенное, инициализированное, содержа"щее ключ, т.е. признак поиска, принадлежность к определенной группеячеек и т,д.Далее, если ячейка 1 доступначтению или записи, то она называет 5 О 5 20 25 35 40 45 50 55 ся активной, в противном случаепассивной, Активность ячейки 1 определяется состоянием триггера 9.Рассмотрим операции, выполняемыепредложенным АЗУ.1. Общая инициализация. Послевключения устройства содержимое всехячеек 1 имеет случайное значение.Также имеют случайное состояниетриггеры 4 и 9. Для установления определенного начального состоянияприменяется операция общей инициализации, Для увеличения быстродействияАЗУ, общая инициализапия выполняется параллельно для всех ячеек АЗУ,Подачей сигнала 24 (здесь и вдальнейшем номер сигнала соответствует номеру входа или выхода устройства) через элемент ИЛИ 3 на входы16 всех блоков 2 подается сигнал выборки. На вход 12 подается сигналзаписи, а на вход 13 - значение логического нуля, На входы 14 и 15 подаются последовательно адреса всехячеек и страниц в блоке 2, тем самымпроисходит запись значения нуля вовсе ячейки блоков 2,В конце инициализации ячеек 1 наслужебную страницу записывается приз-.нак инициализированности. Это осуществляется подачей сигнала 24, сигнала 12 записи, единичного значениясигнала 13 данных, адреса служебнойстраницы на входы 15 и кода состояния на входы 14. После этого триггеры 4 и 9 устанавливаются в исходноесостояние подачей сигналов 23 и 21соответственно.2. Селективная инициализация, Вовремя работы может возникнуть необходимость в установлении исходногосостояния отдельных или групп ячеек1 АЗУ. При этом инициализация должна быть селективной - содержимое остальных ячеек не должно меняться.Селекция осуществляется по признакусостояния, т,е, инициализация прозводится для всех ячеек. имеющих одинаковое состояние, Для этого триггеры 9 всех ячеек 1 приводятся в актив-ное состояние сигналом 20, Сигнал 22группового обрашения, проходя элементИ 10 в элемент ИЛИ 3, образует сиг-:нал 16 выборки для всех блоков 2. Навход 12 подается сигнал чтения, .навход 14 - код состояния, а на входы15 адрес служебной страницы, В ре"зультате на выходе блоков 2 тех яче 14118ек 1, состояние которых соответствует выбираемым, активизируется сигнал что приводит соответствующие триггеры 4 в состояние положительного отк 5 лика.Триггеры 4 тех ячеек, состояние которых не совпадает с выбираемым, остаются в исходном состоянии и соответствующие элементы И 1 пропускают сигнал 19, который подается непосредственно после этого. Далее выполняется процесс инициализации аналогич" но операций общей инициализации.3. Запись ключа. Запись ключа мо" жет быть произведена в одну иэ ячеек АЗУ, находящихся в инициализированном состоянии. Для селекции.инициализированных ячеек АЗУ сперва осуществляется опрос всех ячеек на состояние "инициализированное". Сигналом 20 активизируются все ячейки, а сигналом 22 группового обращения че" рез элемент И 10 и элемент ИЛИ 3 образуются сигналы 16 выборки. На вхо ды 14 подается адрес ячейки блока 2, где хранится код состояния ячейки АЗУ, а на входы 15 - адрес служебной страницы. На вход 12 подается сигнал чтения, Выходные сигналы блока 2 ини" 30 циализированных ячеек АЗУ активные, они устанавливают триггеры 4 в состояние положительного отклика, сни" мая активный сигнал с их выхода. Далее происходит дезактивация тех ячеек 1 АЗУ, триггеры 4 которых остались в исходном состоянии. Это осуществляется сигналом 19, который, проходя через элементы 7 неинициализированных ячеек, устанавливает последние в пассивное состояние, Таким образом, после опроса состояния активными остаются только инициализированные ячейки.Для записи ключа выбирается одна 45 ячейка из числа активных ячеек, Это осуществляется по принципу выбора первой активной ячейки. Для этого на вход 25 АЗУ подается сигнал запроса. Если первая (начиная слева) ячейка 1 пассивная, то этот сигнал через открытый элемент И 8 распространяется дальше, до первой активной ячейки, у которой элемент И 8 закрыт сигналом от триггера 9, а элемент И 11 открыт. Проходя через этот элемент И 11 и элемент ИЛИ 31, сигнал 25 преобразу-ется в сигнал 16, который, проходя через элемент НЕ 6, возбуждает сиг 264нал на выходе 18, подтверждающий,чтоимеется по крайней мере одна инициализированная ячейка 1, Если в АЗУнет ни одной инициализированной ячейки, то сигнал 25 появляется на вы"ходе 26 АЗУ в виде сигнала, свидетельствующего о том, что инициализированных ячеек нет. При.наличии инициализированной ячейки начинается .запись ключа посимвольно последовательно. Коды ключевых символов подаются на входы 14, а коды порядкового номера символов в ключе на входы15, при этом при записи каждого символа активизируется сигнал 12 записии дается сигнал на вход 13 ("0" илиН 11 )После записи ключа в служебнойстранице стирается признак инициализированности ячейки 1 и туда записывается признак существования в ячейке ключа. Для этого на входы 15 дается адрес служебной страницы, навходы 14 код "0" ячейки блока 1, ана вход 13 значение "0" и производится запись сигналом 12Затем на входы 14 дается код наличия ключа (например, "1") и осуществляется записьединицы,Для записи следующего ключа можно начинать процедуру сначала иливыбирать следующую ячейку из числаактивизированных. Для этого необходимо деэактивизировать ту ячейку, вкоторую только что закончилась запись, Это осуществляется подачей сиг-нала 21, поступающего на вход триггера 9 и проводящего последнее в состояние, .определяемое сигналом 16,поступающим на другой вход триггера9 Поскольку в этом режиме сигнал16 является активным только у самойлевой активной ячейки, то деэактивируется именно эта ячейка. После этого сигнал 25 автоматически распространяется до следующей активной свободнои ячеикиИэ ячеек АЗУ, содержащих ключи, .можно образовать группы, используяячейки служебной страницы в блоке 2.Эти группы могут иметь лоГическоезначение и их наличие значительнорасширяет возможности использованияпредложенного АЗУ. Каждой группеприсваивается определенный код состояния на служебной странице. Поскольку ячеек на служебной страницемного (столько, сколько ключевых1826 1 О 20 30 3540 45 50 55 5 4символов) то одна ячейка АЗУ можетпринадлежать и нескольким группам.Механизм логического группообразования дает возможность предна"рительного выбора определенной груп-пы ячеек перед опросом АЗУ,4. Опрос отклика АЗУ, Эта опера,ция является основной при использо:,вании АЗУ при поиске данных. Для это,го исследуемые данные в виде входныхслов подают последовательно на входАЗУ и определяется значение отклика.Если входное слово (или его фрагмент)сонпадает по крайней иере с однимключом, записанным н ячейки АЗУ, тоотклик является положительным, в про",тинном случае " отрицательным.Операция начинается с активизациивсех ячеек, содержащих ключ определенной группы. Сигналом 20 активизируются все ячейки 1 АЗУ, а сигналом22 группового обращения через элементИ 10 и элемент ИЛИ 3 образуется сиг"нал 16 выборки для всех блокон 2. Навходы 14 подается код группы (номерсостояния), а на входы 15 - адресслужебной страницы. На вход 12 подается сигнал чтения, Выходные сигналыблоков 2 тех ячеек 1, которые принадлежат к данной группе (активные),,устанавливают триггеры 4 в состояниеположительного отклика, Сигналом 19через элемент 7 дезактивизируютсявсе остальные ячейки АЗУ.Таким образом, активными остаютсятолько ячейки желаемой группы,Опрос происходит параллельно длявсех активных ячеек 1 посимвольно"последонательно. Код очередного символа входного слова подается на входы 14, а код порядкового номера симгвола - на входы 15, По сигналу 12чтения на выходе блоков 2 тех ячеек1,.ключевой символ на данной позициикоторых совпадает с входным символом,.возникает сигнал, что приводит соот-,ветствующие триггеры отклика 4 всостояние положительного отклика.Триггеры 4 тех ячеек, ключевыесимволы которых не. совпали с опрашиваемыми, остаются в исходном состоянии и соответстнующие элементыИ 7 пропускают сигнал 19 дезактивации, который подается непосредственно после каждого опроса по символу,Этот сигнал дезактивирует соответствующие ячейки 1, Итак, число активныхячеек с каждым опросом уменьшается остаются активными толькоте, которые дали совпадение по всем предыдущим символам. Перед каждым опросом триггеры 4 должны быть установлены сигналом 23 н исходное состояние,После опроса по всем симнолам входного слона следует произнести общий опрос АЗУ, Это выполняется подачей сигнала25 запроса, Если он проходит до выхода 26 АЗУ, то это означает, что актинных ячеек не осталось и отклик является отрицательным. Если сигнал 26 не появляется, а вместо него появля" ется сигнал 18, то осталась по крайней мере одна активная ячейка и отклик является положительным. По этому же сигналу автоматически выбрана первая активная ячейка (если оста" лось несколько) и путем подачи номера служебной страницы на входы 15 и сигнала чтения на входы 12 можно выполнить последовательное чтение служебной информации (индекса связи или сообщения). Считываемая информация при этом через элемент И 5 появляется на выходе 17,5. Опрос по ключу с межпозиционной функцией ИЛИ. В опиеанной операции между всеми позициями нходного слова относительно ключа выполняется функция И как обычно в ассоциативных устройствах. Но часто бывает полезным ослабить это условие и получить положительный отклик .и в том, случае, когда определенный символ появляется хотя бы один раз в нескольких смежных позициях, Это особенно полезно при предварительной сортировке данных. Этой цели служит триггер 4, который при нормальной (чисто коньюнкционной) работе только дублирует функции триггера 9. Для выполнения функции ИЛИ между группой смежных позиций в цикле запросаотклика, .запрос по символу производится после последнего символагруппы, Триггерами 4 запоминаютсясовпадения внутри группы независимоот того, в какой позиции внутригруппы они имели место. Формула изобретения Ассоциативное запоминающее уст" ройстно, содержащее блоки памяти и основные триггеры, причем входы записи-чтения и адресные входы блоков памяти объединены соответственно и являются входом записи"чтения и приз".Тираж 590ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Заказ Збб 5/48 Производственно-полиграфическое предприятие, г. ужгород, ул. Проектная, 4 иаковыми входами устройства, о тл и ч а ю щ е е с я тем, что, сцелью повышения быстродействия и расширения функциональных воэможностейустройства за счет выполнения логических операций. между фрагментамипризнака поиска, в него введены дополнительные триггеры, элементы ИЛИ,элементы НЕ и с первой по пятую груп пы элементов И, причем информационные входы блоков памяти объединеныи являются информационным входом устройства, выход каждого элемента ИЛИподключен к входу соответствующегоэлемента НЕ, к входу выборки соответствующего блока памяти, к первомувходу соответствующего элемента Ипервой группы и к первому установочному входу соответствующего основного триггера, выходы элементов И первой группы объединены и являются информационным выходом устройства, выход каждого блока памяти подключенк второму входу соответствующего ,25элемента И первой группы и к информационному входу соответствующего дополнительного триггера, выход которого подключен к первому входу соответствующего элемента И второй группы, выход которого подключен к информационному входу соответствующегоосновного триггера, вторые входыэлементов И второй группы объединены и являются первым входом заданиярежима устройства, выходы элементовНЕ объединены и являются выходом положительного результата поиска, вторые установочные входы основных триггеров объединены и являются вторымвходом режима устройства, третьи установочные входы основных триггеровобъединены и являются первым устано"вочным входом устройства, прямой выход каждого основного триггера подключен к первому входу соответствую"щего элемента И третьей группы, инверсный выход каждого основного триггера соединен с первыми входами соответствующих элементов И четвертойи пятой групп, вторые входы элементовИ четвертой группы объединены и являются входом группового обращенияустройства, первые входы элементовИЛИ объединены и являются входом общего обращения устройства, второй итретий входы каждого элемента ИЛИсоединены соответственно с выходамисоответствующих элементов И четвертой и пятой групп, второй вход каждого элемента И третьей группы соединен с вторым входом соответствующего элемента И пятой группы, устано"вочные входы дополнительных триггеров объединены и являются вторым установочным входом устройства, второйвход первого элемента И третьей груп"пы является входом запроса устройства, второй вход каждого элемента Итретьей группы, кроме первого, подключен к выходу предыдущего элемента И третьей группы, выход последне"го элемента И третьей группы является выходом отрицательного результа"та поиска устройства.