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

801043750 А СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 15 ГОСУДАРСТВЕКК ДЕЛАМ ИЗОБРЕ КОМИТЕТ СССР ЕНИЙ И ОТКРЫТИ ОПИСАНИЕ И К АВТОРСКОМУ СВИДЕ БРЕТЕН ЕЛЬСТВУ(21) 3433941/18-24 венно к входам регистра адреса и (22) 05.05.82 первого шифратора, выход ксторого (46) 23.09.83:., Бюл. Р 35 соединен с одним из входов первого (72) В.И. Корнейчук, В.И. Павловс- элемента И и входом триггера; инкий, Марта Зеебауэр, И.П. дробязковерсный выход которого подключен и А.П. Марковский к первому входу второго элемента И, 71) Киевский ордена Ленина политех- а прямой - к другому входу первого .нический институт им. 50-летия , . элемента И и первому входу третье- Великой Октябрьской социалистичес-го элемента И, выходы второго и кой. революции третьего элементов И соединены (53) 681.327(088.8), непосредственно с первым и вторым (56) 1. Авторское свидетельство СССР входами постоянного накопителя и В 410462,"кл. С 11 С 15/00, 1974. . вторым и третьим входами первого2,. Авторское свидетельство СССР , регистра числа и через первый эле- Ф 773729, кл. С 11, С 15/00, 1979 ..мент ИЛИ с первым входом третьего (прототип).. . . регистра числа, второй вход и вы -ход которого соответственно под- (54)(57) .АССОЦИАТИВНОЕ ЗАПОМИНАЮ- . ключены к второму выходу и третьее ЩЕЕ УСТРОЙСТВО, содержащее опера- . му входу оперативного накопителя, тивный накопитель, первый регистр .. второй выход. первого регистра опчисла, первый выход которого под- роса соединен с входом второго шифключен к входу второго регистра ратора, выходы которого подключенЫ числа, .регистр маски, первый ре-к первым входам четвертого и пягистр опроса, первый вход которо-того, элементов И,выходы которых, го соединен с выходом второго ре- . непосредственио соединены с треть- ще гистра опроса, элементы И, шифрато. им и четвертым входами постоянноры,.причем второй вход первого ре- го накопителя и через второй, эле- СЬ гистра опроса является одним из уп- мент ИЛИ с третьим входом третьего ф равЛяющих входов устройства, пер-регистра числа, выход постоянного вый и второй входы и первый выход" . накопителя подключен к входу ре-оперативного накопителя подключе-. . гистра маски, выход четвертого а ны соответственно к первому выходу. . элемента И подключен к первому первого регистра. опроса, выходу ре, : элементу задержки, выходы четвергистра маски и первому входу пер-.того и пятого. элементов И через втового регистра числа, о т л и ч а -. рой и третий элементы задержки ющ е. е с я тем, что, с целью рас.: соединены соответственно с четверширения области применения устройст- . тым ипятым входами регистра чисва путем обеспечения возможности хра-ла, вторые входы второго и третьего хранения в.нем чисел переменной; . элементов И и вторые входы четвер- длины, в него введены постоянный : того и пятого элементов И объединакопитель, регистр адреса, третий , иены соответственно и являются регистр числа, триггер, элементы , другими управляющими входами устрой- ИЛИ и элементы задержки, причем , ства, выходами которого являются второй и третий выходы первого ре- выходы первых элемента И и элеме гистра числа подключены соответст- та задержки. нИзобретение относится к вычислительной технике н может быть использовано в электронной цифровой вычислительной системе для обработки информации, выполненной на узлах с большой степенью интеграции.Известно ассоциативное запоминающее устройство, содержащее матрицу ассоциативных признаков, регистр маски, блок первичных индикаторов совпадения, счетчики, .блок управления 1.Это устройство не позволяет хранить и считывать слова переменной длины, особенно в случае, когда длина слова превышает длину строки матрицы.Наиболее близким по технической сущности к изобретению является ассоциативное запоминающее устройство, содержащее накопители, регистр слова,.регистр признака опроса, регистры адреса, блок управления, элементы И., коммутатор, схемы сравнения и регистры общего признака2 Д.Однако это устройство также не повволяет хранить в нем слова висла переменной длины.Целью изобретения является рас.ширение области применения устройства за счет обеспечения возможности хранения в нем чисел переменной длины.Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее оперативный накопитель, первый регистр, числа, первый выход которого подключен к входу второго регистра числа, регистр маски, первый регистр опроса, первый вход которого соединен с выходом второго .регистра опроса, элементы И, шифраторы, причем второй вход первого регист-ра опроса является одним из управляющих входов устройства, первый и второй входы и первый выход оперативного накопителя подключены соответственно к первому выходу первого регистра опроса, выХоду регистра маски и первому входу перного регистра числа, введены постоянный накопитель, регистр адреса, третий регистр числа, триггер, ;элементы ИЛИ и элементы задержки, причем второй и третий выходы пер.- вого регистра числа подключены соответственно к входам регистра адреса и первого шифратора, выход которого соединен с одним из вхо-дов первого элемента И и вхОдом триггера, инверсный выход .которого подключен к первому входу второго элемента И, а прямой - к другому входу первого элемента И и перво-му входу третьего элемента И, выходы второго и третьего элементов И соединены непосредственно с первым и вторым входами постоянногонакопителя и вторым и третьим входа.ми первого регистра числа и через.первый элемент ИЛИ с первым входом5 третьего регистра числа, второйвход и выход которого соответственно подключены к второму выходу итретьему входу оперативного нако.пителя, второй выход первого регист 10 ра опроса соединен с входом второгошифратора, выходы которого подключены к первым входам четвертого и пятого элементов И, выходыкоторыхнепосредственно соединеныс третьим и четвертым входами постоянного накопителя и через второйэлемент ИЛИ с третьим входом третьего регистра числа, выход посто.- янного накопителя подключен к входу регистра маски, выход четвер 2 О того элемента И подключен к первому элементу задержки, выходы четвертого и пятого элементов И черезвторой и третий элементы задержкисоединены соответственно с четвер-тым и пятым входами регистра числа, вторые входы второго и третьего элементов И и вторые входы четвертого и пятого элементов И объединены соответственно и являются30 другими управляющими входами устройства, выходами которого являютсявыходы первых элемента И и элемента задержки.На чертеже изображена структурнаяЗ 5 схема ассоциативного запоминающего устройства.Устройство содержит оперативныйнакопитель 1, выполненный из ассоциативных ячеек памяти (не показаны)первый регистр 2 опроса, регистр 3маски, второй регистр 4 опроса,первый 5, второй 6 и третий 7 регистры числа, регистр 8 адреса, первый шифратор 9, триггер 10, первыйэлемент И 11, выход которого яв 45 ляется, первым выходом 12 устройст-,ва второй 13 и третий 14 элементы И, одни из входов которых объединены и являются первым управляющим входом 15 устройства, постоян 50 ный накопитель 16, второй шифратор 17, четвертый 18 и пятый 19элементы И, одни из входов которыхобъединены и являются вторым управляющим входом 20 устройства,55 первый элемент 21 задержки, выходкоторого является вторым выходом 22устройства, первый 23 и второй 24элементы ИЛИ. Регистр 2 имеет вход,являющийся третьим управляющимвхоДом 25 устройства, Устройствотакже содержит второй 26 и третий27 элементы задержки. Регистр 7 служит для хранения управляющей информации,Устройство работает следующим65 образом.В исходном состоянии в ячейках памяти накопителя 1 записаны информационные слова производной длйны и соответствующие им коды, причем структура записи информации в накопителе 1 следующая: код символов информационного слова записываются в ячейку, начиная с первого ее разрядаф, если длина слова.в .больше, чем 1 символов (где 1=и-., причем и - число групп разрядов, содержащихся в ячейке накопителя 1, число групп разрядов, занимаемых кодом адреса), то под запись этого слова занимается и последующая ячейка, куда записывается остаток сло-. ва в случае, если щ ъп. Если недоСтаточно двух ячеек, используется три, четыре и больше ячеек, при этом запись Формируется так, что последние Ф групп разрядов в записи ячейки накопителя 1 используются для хранения кода адреса, а 1-я группа разрядов .этой ячейки содержит символ - метку конца записи. В исходном состоянии триггер 10 установлен в нулевое состояние, вре разряды регистра 7 установлены в единичное состояние. При поиске по информационному слову соответствующего ему кода, слово записывается на регистр 4,. на вход 2 д подается сигнал единичного уровня, По сигналу начала ра, боты, подаваемому на вход 25, частьинформационного слова длиной и символов поступает на регистр 2, шиф- . ратором 17 анализируется 1-я группа разрядов регистра 2. В случае отсутствия в укаэанной группе. сигнала метки формируется сигнал с выхода элемента И 19, который, посту. пая на вход постоянного накопителя 16, формирует на выходах последнего нулевой код, который, поступая" на регистр 3, разрешает сравнение всех разрядов ячейки накопителя 1 с, соответствующими разрядами регистр. ра 2, сигнал единичного уровня Фор-мируется на шинах поиска тех ячечк накопителя 1, содержимое которых поразрядно совпадает с содержимым регистра 2, указанными сигналами перезаписываются единицы в соответ-. ствующие разряд регистра б. Одновременно слово, адекватное за" писанному на регистре 2, считывает-ся на регистр 5, Сигналом с выхода элемента И 19 через элемент ИЛИ 24 содержимое регистра б сдвигается . на один разряд, при этом единичные сигналы на адресные входы опроса выдаются лишь для ячеек накопителя 1,.следующйх за ячейками, выделенными единичными сигналами в такте опроса. Сигналом с выхода элемента,И 19 через элемент 26 задержки регистр 5 сбрасывается в нуль. В следующем такте вновь на регистр 2 заносятся следующие п символов из регистра 4, и вновь 1-йсимвол анализируется шифратором 17,и если символ-метка отсутствует, 5 то вновь содержимое регистра 2 сравнивается с содержимым ячеек накопителя 1, следующих за выделеннымина предыдущем такте, и устройствофункционирует аналогично описанно ОВ случае, если в 1-й групперазрядов. регистра 2 окажется записанным символ-метка, то единичный сигнал последовательно будетсформирован на выходе шифратора 17и элемента И 18, с выхода последнего единичный сигнал поступает навход постоянного накопителя 16, свыхода которого на регистр маски 3Считывается код, маскирующий срав кение последних +1 групп разрядов. ячеек накопителя 1 и, таким образом, опрос производится лишь по первым и-1 символам регистра 2, наи-1 групп разрядов регистра 5, при 25 этом считывается содержимое и- 1групп разрядов регистра 2, а в последние 2 группы разрядов заносится искомый код адреса. Сигналом свыхода элемента И 18 через элемент.27 задержки содержимое регистра 5сдвигается вправо на Ю разрядовтак, что на регистре 8 оказываетсязаписанным искомый код адреса. Этимже сигналом через элемент 21 задержки с выхода 22 формируется сигнал конца операции поиска.В случае поиска информационного слова по его коду последний заносится на регистр 4, на вход 15выдается сигнал единичного уровня.40 По сигналу начала операции, подаваемого на вход 25, код при сдвигена и групп разрядов заносится в последние Х группы разрядов регистра2, в 1-ю группу разрядов этого ре гистра записывается код метки.Маскирование разрядов при этом непроизводится и сравнение содержимого всех ячеек накопителя 1 и регистра 2 происходит по всем разря-дам. В результате цикла опроса нарегистр 5 записывается содержимоеячейки накопителя 1, в которой записан конец искомого информационного слова, метка конца и код. Приэтом записывается единица в соответствующий. разряд регистра 7, всеостальные разряды которого приэтом устанавливаются в нуль, Наличие кода метки в 1-й группе разрядов регистра 5 Формирует на выхо де шифратора 9 сигнал единичногоуровня, который поступает на входтриггера 10, который, будучи установлен в нулевое соСтояние, Формирует через открытый элемент И 13 65 единичный сигнал на входе постоян1043750 ИИПИ Эаказ 7348/57 Тираж 5 одписн филй ПП "Патент", г од,ул.Проектная,4 ного накопителя 1 б.и на входе ре. -гистра 5. Указанным сигналом содер"жимое первых п-1 разрядов регистра 5 сдвигается в регистр 6. Триг-.гер 10 устанавливается в единичноесостояние и в этом же такте производится цикл опроса накопителя 1.На регистре маски 3 при этом записан код, маскирующий сравнениевсех разрядов ячеек накопителя 1,так что выборка ячейки для считывания на регистр 5 определяется только состоянием разрядов регистра 7,содержимое которого предварительно сигналом с элемента И 13 черезэлемент ИЛИ .23 сдвигается на один .разряд, так что на регистр 5 считывается содержимое ячейки, предшествующей выбранной на предыдущем такте опроса, в которой записана либо часть информационногословауже считанного в предыдущемтакте, либо конец другого информационного слова. В первом случаешифратором 9 код метки не регист -рируется, и единичный сигнал с выхода триггера 10 через элемент И14 поступает на входрегистра 5,сдвигая на и групп разрядов его содержимое в .регистр б. Кроме того,единичный сигнал с выхода элемента И 14 через элемент ИЛИ 23 сдвигает содержимоерегистра 7, подготавливая выборку ячейки Ю следующем 5 т о"роса.Работа в последующем такте аналогична описанной, так что когдав регистре 5 наличием метки в 1-йгруппе разрядов регистра 5 зафиксио рован конец другого информационного слова, то в регистре 6 хранится код искомого слова Сигнал,поступающий с выхода шифратора 9,в этом случае Формирует, пройдячерез открытый элемент И. 11, сигналединичного уровня на выходе 12.Таким образом, предлагаемое ассоциативное запоминающее устройствопозволяет хранить и осуществлятьпоиск информационных слов перемен ной длиныпо их коду и наоборот.Применение ассоциативных запоминающих устройств для хранения такихслов значительно ускоряет процессих поиска и обработки по сравнению 25 с адресными устройствами, в которыхиспользуется списковая структуразаписей