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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН

„„SU„, 1234880 А 1 (5D 4 G 11 С 15 00

f»

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3821087/24-24 (22) 06.12.84 (46) 30.05.86. Бюл. № 20 (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Гойял Раджив Кумар (IN), Гавад

Фадль Хасан (YD), В. И. Корнейчук и А. П. Марковский (53) 681.327 (088.8) (56) Авторское свидетельство СССР № 773729, кл. G !1 С 15/00, 1979.

Авторское свидетельство СССР № 1043750, кл. G 11 С 15/00, 1983. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в системах хранения и обработки информации, выполненных на узлах с большой степенью интеграции. Цель изобретения— расширение области применения устройства за счет обеспечения поиска слов переменной длины по совокупности признаков и повышение эффективной емкости устройства.

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

1234880

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

Устройство содержит (фиг. 1) накопитель 1, выполненный из ассоциативных ячеек памяти, регистр 2 опроса, регистр 3 маски, регистр 4 слова, элементы И 5ь..5 (m — число ассоциативных ячеек памяти накопителя 1), регистр 6 адреса, шифратор 20

7, первый счетчик 8, блок 9 сравнения, дешифратор 10, элемент ИЛИ 11, первый

12 и второй 13 регистры числа, второй счетчик 14, третий 15 и четвертый 1 6 регистры числа, блок 17 управления, имеющий входы

l8 — 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

ОБЪЕКТ вЂ” КПИ

ЧИ СЛОСТУДEHTOB

lll111111100000000111111111111110000

1257

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

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

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

На входы 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.

Устройство также содержит триггер 70, счетчик 71 сдвигов и элемент ИЛИ 72.

Все блоки предлагаемого устройства могут быть выполнены в виде интегральных микросхем (одной или нескольких) с большой степенью интеграции или на серийно выпускаемых микросхемах малой и средней степени интеграции.

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

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

При поиске информации на регистры

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

1234880 совпадает с полем ключей, если такая ячейка одна, то через шифратор 7 номер ее записывается на счетчик 8 (если более чем одна, то записи не происходит). Сигналом с выхода элемента 52 задержки триггер 70 устанавливается в единичное состояние, а сам сигнал через элементы ИЛИ 53, И 55, ИЛИ

40, ИЛИ 66, выход 27 блока 17 поступает на регистры 2, 3, 12, 13, вызывая сдвиг их содержимого на к разрядов, при этом на регистре 2 оказываются следующие к разрядов ключа, а на регистре 3 — следующие к разрядов маски ключа. Сигналом, задержанным элементом 41 задержки, снимаемым с выхода элемента ИЛИ 42 через выход 22 блока 1?, накопитель 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

55 ряд вправо (соответствует тому случаю, если искомое слово записано, начиная с второго разряда). Если такое слово (или слова) будет найдено, то с выхода элемента ИЛИ 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 и из регистра 1 6 на регистр 13, этим же сигналом через элемент

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

3. Затем сигналом, задержанным элементом

1234880

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

Дис, 1

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

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

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

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

2Е Ю 37 2Ф

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

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

Заказ 2702/53 Тираж 543 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий! 13035, Москва, Ж вЂ” 35, Раушская наб.. д. 4/5

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