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

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

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

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

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

Однако это устройство также не позволяет хранить в нем слова числа) переменной длины.

Целью изобретения является расширение области применения устройства за счет обеспечения возможности хранения в нем чисел переменной длины.

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

и соединены нецосредств.енно с первым и вторым входами . постоянного накопителя и вторым и третьим входами первого регистра числа и- через первый элемент ИЛИ с первым/входом Третьего регистра числа, второй вход и выход которого соответственно подключены к второму выходу и третьему входу оперативного накопителя, второй выход первого регистра опроса соединен с входом второго шифратора, выходы которого подключены к nepBfciM входам четвертого и пятого элементов И, выходы которых непосредственно соединены с третьим и четвертым входами постоHHt oro накопителя и через второй элемент ИЛИ- с третьим входом третьего регистра числа, выход постоянного накопителя подключен к входу регистра маски, выход четвертого элемента И подключен к первому элементу задержки, выходы четвертого и пятого элементов И через второй и третий элементы задержки соединены соответственно с четвертым и пятым входами регистра числа, вторые входы второго и третьего элементов И и вторые входы четвертого и пятого элементов И объединены соответственно и являются другими управляющими входами устройства, выходами которого являются выходы первых элемента И и элемента задержки.

На чертеже изображена структурна йхема ассоциативного запоминающеГо устройства.

Устройство содержит оперативный накопитель 1, выполненный из ассоциативных ячеек памяти (не показаны первый регистр 2 опроса, регистр 3 маски, второй регистр 4 опроса, первый 5, второй б и третий 7 регистры числа, регистр 8 адреса, первый шифратор9, триггер 10, первый элемент И 11, выход которого яв ляется .первым выходом 12 устройст.ла, второй 13 и третий 14 элементы И, одни из входов которых объединены и являются первым управляющим входом 15 устройства, постоянный накопитель 16, второй шифраTopk 17, четвертый 18 и пятый 19 элементы И, одни из входов которых объединены и являются вторым управляющим входом 20 устройства первый элемент 21 задержки выход которого является вторым выходом 22 устройст ва, первый 23 и второй 24 элементы ИЛИ. Регистр 2 имеет вход, являющийся третьим управляющим вхойом 25 устройства. Устройство также содержит .второй 26 и третий 27 элементы задержки. Регистр 7 служит для хранения управляющей информации. . Устройство работает следующим образом. в исходном состоянии в ячейках памяти накопителя 1 записаны инфор мационные слова производной длины и соответствующие им коды, причем структура записи информации в накопителе 1 следующая: код символов информационного слова записываются в ячейку, начиная с первого ее раз ряда , если длина слова .т .больше чем i символов (где i n-{., причем п - число групп разрядов, содержащихся в ячейке накопителя 1; С число групп разрядов, занимаемых кодом адреса), то под запись этого слова занимается и последукхдая яче ка, куда записывается остаток елова в случае, если m п. Если недостаточно двух ячеек, используется три, четыре и больше ячеек, при этом запись формируется так, что последние 6 групп разрядов в записи ячейки накопителя 1 используютс для хранения кода адреса, а i-я группа разрядов этой ячейки содержит символ - метку конца записи В исходном состоянии триггер 10 установлен в нулевое состояние, в-рё разряды регистра 7 установлены в единичное состояние. . При поиске по информационному слову соответствующего ему кода, слово записывается на регистр 4,. на вход 20 подается сигнал единичного уровня. По сигналу начала раi боты, подаваемому на вход 25, част информационного слова длиной п сим волов поступает на регистр-2, шифратором 17 анализируется i-я группа разрядов регистра 2. В случае отсутствия в указанной группе.сигн ла метки формируется сигнал с выхо да элемента И 19, который, поступая на вход постоянного накопител 1б, формирует на выходах последнего нулевой код, который, поступаяна регистр 3, разрешает сравнение всех разрядов ячейки -накопителя 1 с, соотйетствующими разрядами рёгис ра 2, сигнал единичного уровня фор мируется на шинах поиска тех накопителя 1, содержимое которы поразрядно совпадает с содержимым регистра 2, указанными сигналами перезаписываются единицы в соответ ствующие разряды регистра 6. Одновременно слово, адекватное записанному на регистре 2, считывает ся на регистр 5, Сигналом с выхода элемента И 19 через элемент ИЛИ 24 содержимое регистра 6 сдвигается . На один разряд, при этом единичные сигналы на адресные входы опро са выдаютсялишь для ячеек накопителя 1,. следунхцйх за ячейками, выделенными единичными сигналами в такте опроса. Сигналом .с выхода эл мента-И 19 через элемент 26 задерж ки регистр 5 сбрасывается в нуль. в следующем такте вновь на регистр 2 заносятся следующие п символов из регистра 4, и вновь i-й символ ан-ализируется шифратором 17, и если символ-метка отсутствует, то вновь содержимое регистра 2 срав.нивается с содержимым ячеек накопителя 1, следующих за выделенными на предыдущем такте, и устройство функционирует аналогично описанному. Б.случае, если в i-й группе разрядов, регистра 2 окажется зарисанным символ-метка, то единичный сигнал последовательно будет сформирован на выходе шифратора 17 и элемента И 18, с выхода последнего единичный сигнал поступает на вход постоянного накопителя 16, с выхода которого на регистр маски 3 Считывается код, маскирующий сравнение последних С+1 групп разрядов ячеек накопителя 1 и, таким образом, опрос производится лишь по первым п-2-1 символам регистра 2, на групп разрядов регистра 5, при этом считывается содержимое групп разрядов регистра 2, а в последние группы разрядов заносится искомый код адреса. Сигналом с выхода элемента И 18 через элемент .27 задержки содержимое регистра 5 сдвигается вправо на разрядов так, что на регистре 8 оказывается записанным искомый код адреса. Этим же сигналом через элемент 21 з.адержки с выхода 22 формируется сигнал конца операции поиска. : В случае поиска информационного слова по его коду последний заносится на регистр 4, на вход 15 выдается сигнал единичного уровня. По сигналу начала операции, подаваемого на вход 25, код при сдвиге на п групп разрядов заносится в последние группы разрядов регистра 2, в i-ю группу разрядов этого регис.тра записывается код метки. Маскирование разрядов при этом не производится и сравнение содержимого всех ячеек накопителя 1 и регистра 2 происходит по всем разрядам. В результате цикла опроса на регистр 5 записывается содержимое ячейки накопителя 1, в которой записан конец искомого информационного слова, метка конца и код. При этом записывается единица в соответствующий разряд регистра 7, все остальные разряды которого при этом устанавливаются в нуль. Наличие кода метки в i-й группе разрядов регистра 5 формирует на выходе шифратора 9 сигнал единичного уровня, который поступает на вход триггера 10, который, будучи установлен в нулевое состояние, формирует через открытый элемент и 13 единичный сигнал на входе постоянного накопителя 16.и на входе регистра 5, Указанным сигналом содержимое-первых разрядов регистра 5 сдвигается в регистр 6. Триггер 10 устанавливается в единичное состояние и в этом же такте производится цикл опроса.накопителя 1, На регистре маски 3-при этом записан код, маскирующий сравнение всех разрядов ячеек накопителя 1, :Так что выборка ячейки для считывания на регистр 5 определяется только состоянием разрядов регистра 7 содержимое которого предварительно сигналом с элемента И 13 через элемент ИЛИ 23 сдвига:ется на один разряд, так что на регистр 5 считывается содержимое ячейки, предшествующей выбранной на пре;цзщущем такте опроса, в которой записана либо часть информационного слова, ,уже считанного в предыдущем такте, либо конец другого информационного слова. В первом случае . шифратором 9 код метки не регист; рируется, и единичный сигнал с выхода триггера 10 через элемент И 14 поступает на входрегистра 5, сдвигая на п групп разрядов его

содержимое в .регистр 6. Кроме того, единичный сигнал с выхода элемента И 14 через элемент ИЛИ 23 сдвигает содержимоерегистра 7, подготавливая выборку ячейки в следукщем такте опроса.

Работа в последующем такте аналогична описанной, так что когда в регистре 5 наличием метки в i-й группе разрядов регистра 5 зафиксирован конец другого информационного слова, то в регистре 6 хранится код искомого слова.. Сигнал, поступающий с выхода шифратора 9, в этом случае формирует, пройдя . через открытый элемент И 11, сигнал

единичного уровня на выходе 12.

Таким образом, предлагаемое ассоциативное запоминанядее устройство позволяет хранить и осуществлять мпоиск информационных слов переменной длины по их коду и наоборот . Применение ассоциативных запоминаюих устройств для хранения таких Слов значительно ускоряет процесс х поиска и обработки по -сравнению

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

АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее оперативный накопитель, первый регистр числа, первый выход которого подключен к входу второго регистра числа, регистр маски, первый регистр опроса, первый вход которого соединен с выходом второго регистра опроса, элементы И,, шифраторы,-причем второй вход первого ре- гистра опроса является одним из управляющих входов устройства, первый и второй входы и первый выход оперативного накопителя подключе- ны соответственно к первому выходу первого регистра опроса, выходу регистра маски и первому входу первого регистра числа, о т л и ч а ющ е е с я тем, что, сцелью рас ширения области применения устройства путем обеспечения возможности храхранения в нем чисел переменной ;; длины, в него введены постоянный накопитель, регистр адреса, третий регистр числа, триггер, элементы ИЛИ и элементы задержки, причем , второй и третий выходы первого peiгистра числа подключены соответственно к входам регистра адреса и первого шифратора, выход которого соединен с одним из эходов первого элемента И и входом триггера, инверсный выход которого подключен к первому входу- второго элемента И, а прямой - к другому входу первого элемента И и первому входу третьего элемента И, выходы второго и третьего элементов И соединены непосредственно с первым и вторым входами постоянного накопителя и вторым и третьим входами первого регистра числа и через первый эле. мент ИЛИ с первым входом третьего регистра числа, второй вход и вы ход которого соответственно подключены к второму выходу и третье(Л му входу оперативного накопителя, . второй выход.первого регистра опроса соединен с входом второго шифратора, выходы которого подключены к первым входам четвертого и пятого, элементов И, выходы которых, Непосредственно соединены с третьим и четвертым входами постоянноо го накопителя и через второй, эле4 мент ИЛИ с третьим входом третьего регистра числа, выход постоянного СО накопителя подключен к входу гистра маски, выход четвертого элемента И подключен к первому СП элементу задержки, выходы четвертого и пятого, элементов И через второй и третий элементы задержки соединены соответственно с четвертым ипятым входами регистра числа, вторые входы второго и третьего элементов И и вторые входы четвертого и пятого элементов И объединены соответственно и являются другими управляющими входами устройства, вькодами которого являются выходы первых элемента И и элемента задержки.