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

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

Цель изобретения - расширение области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышение эффективной емкости устройства.

На фиг. 1 представлена структурная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема блока управления.

Устройство содержит (фиг. 1) накопитель I, выполненный из ассоциативных ячеек памяти, регистр 2 опроса, регистр 3 маски, регистр 4 слова, элементы И 5|...5m (ш - число ассоциативных ячеек памяти накопителя 1), регистр 6 адреса, шифратор 7, первый счетчик 8, блок 9 сравнения, дешифратор 10, элемент ИЛИ 11, первый 12 и второй 13 регистры числа, второй счетчик 14, третий 15 и четвертый 16 регистры числа, блок 17 управления, имеющий входы 18-20, выходы 21-32, входы 33-35, выходы 36-38.

Блок 17 управления (фиг. 2) содержит логические элементы 39-69, в том числе элементы 39, 41, 43, 48, 52, 57, 60, 61 задержки, элементы ИЛИ 40, 42, 47, 53, 56, 62, 65, 66,

ОБЪЕКТ - КПИАДРЕСКИЕВЧИСЛОСТУДЕНТОВ1200

необходимо число 1200 заменить на 1257, то

ОБЪЕКТ-КПИ

111111111100000000111111111111110000 .1257

000000000000000000000000000000001111

На входы 19 и 20 блока 17 подаются единичные сигналы соответственно в случае записи информации по ключу или считывания информации по ключу.

По сигналу начала работы, подаваемому на вход 18 блока 17, счетчик 8 устанавливается в нуль, а все разряды регистра6 - в единицу, триггер 70 и счетчик 71 устанавливаются в нуль. Далее сигнал через элемент 39 задержки и элемент ИЛИ 40, 60 и выход 27 блока 17 управления поступает на управляющие входы регистров 2, 3, 12, 13 и вход счетчика 14; часть разрядов регистра 12 к символов поступает на регистр 2 (к - число групп разрядов, содержащихся в ячейке накопителя 1) и к разрядов с второго регистра 13 - на регистр 3.

Сигнал через элемент 41 задержки, элемент ИЛИ 42 и выход 22 блока 17 посту

элементы И 44-46, 49-51, 54, 55, 58, 59, 63, 64, элементы НЕ 67-69.

Устройство также содержит триггер 70j счетчик 71 сдвигов и элемент ИЛИ 72. Все блоки предлагаемого устройства могут быть выполнены в виде интегральных микросхем (одной или нескольких) с большой степенью интеграции или на серийно выпускаемых микросхемах малой и средней степени интеграции.

Устройство работает следующим образом.

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

При поиске информации на регистры 12, 13, 15, 16 записывается следуюидая информация: на регистр 12 заносятся коды ключей поиска (в общем случае их может быть неосколько); на регистр 13 - маска ключей поиска; на регистр 15 - информация, предназначенная для записи (если производится операция записи информации в накопитель 1 по ключу); на регистр 16 - маска информации. Например, если в информационном слове:

в регистры 12, 13, 15 и 16 соответственно заносятся коды:

Ч И С Л О СТУД Е Н ТОВ

5

пает на управляющий вход накопителя 1, происходит ассоциативный опрос накопителя 1, на управляющих выходах которого формируются сигналы единичного уровня, соответствующие совпадению незамаскированных разрядов ячейки с незамаскированными разрядами регистра 2. В случае, если хотя бы на одном из выходов будет сформирован сигнал единичного уровня, что соответствует наличию в накопителе I хотя бы одного слова, начало которого совпадает с началом поля ключей искомого слова, то на выходе элемента ИЛИ 11 будет сформирован сигнал единичного уровня, которым откроется элемент И 46 и сигнал через от- 5 крытый элемент И 51 поступит на выход 26 блока 17. По этому сигналу в регистре 6 записью единицы в соответствующих разрядах зафиксируются ячейки, содержимое которых

0

совпадает с полем ключей, если такая ячейка одна, то через шифратор 7 номер ее записывается на счетчик 8 (если более чем одна, то записи не происходит). Сигналом с выхода элемента 52 задержки триггер 70 устанавливается в единичное состояние, а сам сигнал через элементы ИЛИ 53, И 55, ИЛИ 40, ИЛИ 66, выход 27 блока 17 поступает на регистры 2, 3, 12, 13, вызывая сдвиг их содержимого на к разрядов, при этом на регистре 2 оказываются следующие к разря- дов ключа, а на регистре 3 - следующие к разрядов маски ключа. Сигналом, задержанным элементом 41 задержки, снимаемым с выхода элемента ИЛИ 42 через выход 22 блока 17, накопитель 1 опрашивается на наличие ячейки, содержимое которой в незамаскированных разрядах совпадает с содержимым части ключевой информации, находящейся в регистре 2: в случае совпадения с соответствующих управляющих выходов накопителя 1 снимаются сигналы единич- ного уровня, а на выходах элементов И 5 единичные сигналы формируются лишь в том случае, если найденная ячейка следует за ячейкой, отмеченной в предыдущем цикле поиска, т. е. если находится слово в накопителе 1, первая и вторая часть ключевого поля которого совпадает с заданным ключом. Если такие слова есть и на выходе хотя бы одного из элементов И 5 формируется сигнал единичного уровня, то вновь снимается сигнал с выхода элемента ИЛИ 11 и устройство работает аналогично, сравнивая третью, четвертую и так далее части ключевого поля. Конец поисковой процедуры определится, когда будет проанализировано все поле ключей и счетчик 14, содержимое которого увеличивается на к всякий раз при сдвиге информации на к разрядов в ре- гистрах 2, 3, 12, 13, выдаст сигнал переполнения, который, пройдя через вход 35 блока 17, откроет элемент И 54 и закроет элемент И 5, прекратив тем самым опрос накопителя 1.

Если на одном из циклов поиска на выходах элементов И 5 не бедут сформировано ни одного сигнала, то нулевым сигналом с выхода элемента ИЛИ 11 закроется элемент И 46. Если триггер 70 при этом находился в нулевом состоянии (соответству- ет первому циклу работы устройства), то сигнал через открытый элемент И 44 поступает на счетный вход счетчика 71, на вход установки в единицу регистра 6 и на вход управления вправо на один разряд содержимого регистров 2, 3, 12, 13, 15, 16. Этим же сигна- лом, прошедшим через элемент ИЛИ 42, выдается сигнал опроса на ячейки накопителя 1, при этом единичные сигналы будут сформированы на тех управляющих выходах, в соответствующих ячейках кооторых записана информация, совпадающая незамаскированными разрядами с (к-1)-ми разрядами ключевого поля, сдвинутыми на раз5

0 n

ряд вправо (соответствует тому случаю, если искомое слово записано, начиная с второго разряда). Если такое слово (или слова) будет найдено, то с выхода элемента ИЛИ 11 формируется сигнал единичного уровня и устройство функционирует по описанному способу. Если в момент выдачи нулевого сигнала с выхода элемента ИЛИ 11 триггер 70 находился в единичном положении (соответствует работе устройства на втором и дальнейших циклах), то открывается элемент И 45, на выходе которого формируется сигнал единичного уровня, который, пройдя через элемент ИЛИ 47, поступает далее на управляющие входы регистров 2, 3, 12, 14, вызывая сдвиг вправо на к разрядов. Эта операция повторяется до тех пор, пока блок 9 не выдаст сигнал равенства (соответствует возврату информации в регистрах 2, 12, 3, 13 в исходное состояние перед установкой триггера 70 в единицу). По сигналу равенства, подаваемому на вход 33 блока 17, открывается элемент И 49, триггер 70 устанавливается в нуль и начинается повторное выполнение первого цикла, при этом ключ в регистре 2 оказывается сдвинутым на разряд вправо. Если счетчик 71 при этом выдаст сигнал переполнения по выходу 30, это означает, что искомой информации нет в накопителе 1. В противном случае, будет выдан сигнал с выхода элемента И 54 (в этот момент будет найдено искомое слово, причем адрес его начала хранится на счетчике 8, а информация в регистрах 15 и 16 сдвинута влево на то же число разрядов, что и начало найденного слова относительно начала ячейки).

По сигналу с выхода элемента И 54 происходит перепись информации из регистра 15 на регистр 12 и из регистра 16 на регистр 13.,этим же сигналом через элемент И 56 производится считывание ячейки накопителя 1, в которой хранится начало найденного слова, на регистр слова 4. В режиме чтения (соответствует единичному сигналу на входе 19 блока 17) открытым оказывается элемент И 58, сигналом с выхода которого информация из регистра 4 переписывается на регистр 2, причем переписываются только разряды, отмеченные единицами в регистре 3, затем сигналом с выхода элемента И 64 содержимое счетчика 8 увеличивается на к разрядов. Операция повторяется до тех пор, пока счетчик 14 не выдаст сигнал переполнения, которым откроется элемент И 63, сигнал с выхода которого является сигналом конца операции. При записи информации (соответствует единичному сигналу на входе 20 блока 17) единичным сигналом с выхода элемента И 59 информация из регистра признака 2 переписывается на регистр 4, причем переписываются только разряды, отмеченные единицами в регистре 3. Затем сигналом, задержанным элементом

61 задержки, содержимое регистра 4 записывается в накопитель 1. В остальном устройство при записи работает так, как и в режиме чтения.

После окончания работы устройства в режиме чтения на регистре 12 зафиксирован код считанной информации.

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

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

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

5

21

28

25 J4 W 23133 3S 23 2023 36

27 22

38 31 oo

35 37 2

uz.2

Редактор В. Ковтун Заказ 2702/53

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

Техред И. ВересКорректор Е. Рошко

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий

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

Филиал ППП «Патент, г. Ужгород, ул. Проектная, 4

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в системах хранения и обработки информации, выполненных на узлах с большой степенью интеграции. Цель изобретения - расширение области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышение эффективной емкости устройства. Устройство содержит накопитель 1, состоящий из ассоциативных ячеек памяти, регистры 2-4, 12, 13, 15 и 16, шифратор 7, счетчики 8 и 14, дешифратор 10. При поиске информации в регистр 12 заносятся коды ключей поиска, в регистр 13 записывается маска ключей поиска, в регистр 15 - информация, предназначенная для записи (если производится операция записи по ключу), в регистр 16- маска информации. В устройстве производится поиск слов по произвольному количеству произвольно расположенных ключей, чтение или запись гфоизволь- ной области найденного слова, причем начало слова может располагаться в произвольном порядке, так что накопитель 1 заполняется информацией полностью. 2 ил. Q (Л 00 4 00 00