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

 

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

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

РЕСПУБЛИК (si>s G 11 С 15/00

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

1 о

| (л ф ср (61) 1679554 (21) 4795557/24 (22) 26.02.90 (46) 30.09.92. Бюл, N. 36 (71) Научно-производственное объединение

"Марс" (72) Г.П,Токмаков (56) Авторское свидетельство СССР

М 1679554, кл. G 11 С 15/00, 1988, (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к ассоциативным запоминающим устройствам, Целью изобретения является повышение быстродейИзобретение относится к области вычислительной техники, в частности к ассоциативным запоминающим устройствам, и является усовершенствованием устройства, описанного в заявке N 4622825/24 от

22.12.88 (1).

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

Анализ словарей морфем и слов показывает, что блок первого уровня содержит 29

Я2,,, 1765848 А2 ствия. Устройство предназначено для ассоциативного поиска информации, причем в качестве опросных признаков используются последовательности произвольной длины. Информация в данном ассоциативном запоминающем устройстве организована в виде структуры поискового дерева, в которой каждый неконечный узел имеет блок узлов нижестоящего уровня. Для поиска элемента в этой структуре используется индексно-последовательный метод. Текущий блок находится по индексу, а требуемый узел в блоке — путем последовательного сравнения ключевого элемента с узлами блока. 3 ил, узлов (букв), блоки второго уровня — 18 — 22 узла, блоки третьего уровня — 10 — 12 узлов, а блоки четвертого и ниже уровней в среднем — 1 — 3 узла.

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

Поставленная цель достигается тем, что в ассоциативном запоминающем устройстве (положительное решение от 01,06.89 г.

1765848

1)), содержащем регистр, информационный вход которого является информационным входом устройства, а выход подключен к первому входу компаратора, блок памяти, каждая ячейка которого содержит поле сим- 5 волов, поле указателей и поле признаков, причем выход поля символов подключен к второму входу комйаратора, выход поля указателей подключен к первому информационному входу сумматора, второй инфор- 10 мационный вход которого является входом единичного приращения, а к третьему информационному входу подключены его выходная шина, подключенная также к адресному входу блока памяти, одновре- 15 менно является информационным входом устройства, выход поля признаков подключен к входу "Признак поиска" блока управления, к которому подключены управляющие входы и выходы устройства, 20 информационный вход устройства соединен с третьим информационным входом сумматора.

Заявляемое устройство отличается от основного изобретения (1) тем что оно снаб- 25 жено дополнительной связью: информационный вход устройства — третий вход сумматора. Таким образом, заявляемое устройство отвечает критерию "новизна". Введение данной связи обеспечивает 30 организацию поиска первых трех символов по индексному способу, значительно повышающему быстродействие устройства, следовательно, обеспечивает устройству наличие свойства, отвечающего критерию 35

"существенное отличие".

На фиг.1 представлена блок-схема устройства; на фиг.2 — структура поискового дерева, записанная в адресном накопителе; на фиг.3 — алгоритм ассоциативного поиска 40 последовательностей произвольной длины.

Основу устройства составляет регистр

1, вход которого является информационным входом устройства, а выход подключен к первому информационному входу компара- 45 тора 2, блок 3 памяти, каждая ячейка 4 памяти которого содержит поле 5 символов, поле 6 указателей и поле 7 признаков, причем выход поля 6 указателей 6 подключен к первому информационному входу суммато- 50 ра 8, второй информационный вход которого является входом "Единичное приращение", а к третьему информационному входу подключена его информационная выходная шина, подключенная также к ад- 55 ресному входу блока 3 памяти и информационному устройству и одновременно является информационным входом устройства, выход поля 7 признаков подключен к входу "Признак поиска" блока 9 управления, управляющие входы "Запись", "Признак конца последовательности", "Поиск" и управляющие входы "Положительный результат поиска", "Ошибка", "Запрос" являются управляющими входами и выходами устройства, выходы х1 и х2 подключены к управляющим входам записи и чтения входного регистра 1, выход х3 соединен с управляющим входом компаратора 2, управляющий выход которого соединен с входом "Наличия совпадения" у4 блока 9 управления, выход х4 подключен к управляющему входу выборки 3 памяти вход "Признак поиска" у5 является информационным входом и соединен с выходом поля 7 признаков, выход х6 соединен с входом "Код операции" сумматора 8, а выходы х5, х7, х8 подключены к управляющим входам приема информации соответственно с первого, второго и третьего входом сумматора 8.

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

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

На первом уровне поискового дерева, начиная с нулевого адреса, выделены 32 ячейки, которые и составляют первый уровень.

На втором уровне выделены 32 блока каждый по 32 ячейки, а на третьем уровне содержится 1024 блока по 32 ячейки.

Причем в ячейках первого уровня содержатся начальные адреса блоков второго уровня, в 1024 ячейках второго уровня содержатся начальные адреса блоков третьего уровня, а в 32768 ячейках третьего уровня содержатся начальные адреса блоков четвертого уровня поискового дерева, Четвертый и нижеследующие уровни организованы аналогично со структурой уровней поискового дерева, описанной в основном изобретении.

В полях символа 5 и указателя 6 ячеек

4 первых трех уровней содержатся начальные адреса соответствующих блоков нижележащих уровней, а для ячеек четвертого и ниже уровней в поле символов 5 хранятся коды букв хранимых последовательностей, в поле 6 указателей приращения адресов между соседними ячейками 4 блока ячеек 4, 1765848

В поле 7 признаков всех уровней хранятся признаки конца последовательности и конца блока.

Фрагмент структуры поискового дерева для хранения корневых морфем приведен 5 на фиг.2. Здесь показаны те участки структуры, в которых хранятся морфемы:

БА

БАЛ

БАЛАБОЛ

БАЛАБОШ

БАЛАГАН

БАЛАГУР

БАЛАК

БАЛАЛА

БАЛАМУТ

БАЛ АМУЧ

БАЛАНД

БАЛАХОН

БАЛБЕС

БАЛД

БАЛ К

БАЛМОШ

БАЛ МОЧ

БАЛТ 25

БАЛЯС

15

30

Г

ГРОБ

ГРОЖ

ГРОЗ

ГРОЗД

ГРОМ

ГРОМАД

ГРОМОЖД 35

ГРОМОЗД

ГРОХ

ГРОШ

Проведенные морфемы взяты из книги (2). 40

Для повышения быстродействия устройства использовано следующее обстоятельство.

B со временн ых вычислител ьн ых устройствах для кодирования букв использует- 45 ся стандартный 8-разрядный код (например, КОИ-8).

Младшие 5 разрядов этого кода определяют конкретные буквы некоторого алфавита, а три старших разряда определяют 50 алфавит(латинский или русский) и характер буквы (строчная или прописная). Таким образом, буква в некотором алфавите однозначно определяется пятью разрядами.

Поэтому на первом уровне код буквы явля- 55 ется адресом ячейки, в которой хранится указатель на начальный адрес блока второго уровня, Код второй буквы последовательности рассматривается как приращение относительно начального адреса выделенного блока второго уровня, в которой хранится указатель на начало блока третьего уровня.

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

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

Блок-схема алгоритма функционирования устройства приведена на фиг.3 и описывается следующим образом.

С внешнего устройства на шину вводавывода данных устройства в сопровождении сигнала "Запись" поступает код первой буквы опросной последовательности. Для более наглядного описания принципа действия устройства в качестве примера возьмем буквенную последовательность, составляющую корневую морфему "БАЛАГУР". Код первой буквы "б" в КОИ-8—

11000010.

Младшие пять разрядов этого кода используются в качестве адреса ячейки 4 блока первого уровня.

В устройстве управления ведется счет импульсам сигнала "Запись" и, если это число не больше трех, то младшие пять разрядов записываются в сумматор 8 по третьему входу и складываются с нулевым кодом по четвертому входу сумматора 8. Затем результат, сложения с выхода сумматора поступает на адресный вход блока 3, памяти, Для этого на вход х7 подается управляющий сигнал записи по третьему информационному входу сумматора 8, затем на выход х9 подается инструкция сложения, :В этом случае мы получаем адрес третьей ячейки 4 блока первого уровня (код

00010), в полях указателей 6 и символа 5 которой хранится начальный адрес блока второго уровня, соотнесенного с первой буквой "б" искомой последовательности.

Содержимое полей указателя и символа данной ячейки 4 заносится в сумматор 8 по четвертому информационному входу, для чего на выход х8 подается сигнал выборки четвертого входа сумматора 8, а на выход х9 — инструкция записи. После этого содержимое поля признаков 7 через вход у2 проверяется на наличие признака конца последовательности.

1765848

10

25

50

Если данный признак отсутствует, то устройство переходит в режим ожидания очередного сигнала "Запись". в противном случае в зависимости от поступления с внешнего устройства сигнала "Запись" или

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

Следующий цикл работы начинается с приходом сигнала "Запись" и кода второй буквы "а" на шину ввода-вывода данных, Так как это будет второй сигнал "Запись", то снова младшие 5 разрядов кода второй буквы (код 00001) заносятся по третьему входу сумматора 8, а затем складывается с содержимым по четвертому входу. При этом мы получаем адрес второй ячейки 4 блока второго уровня, выделенного в первом цикле работы устройства (Адрес =

= Начальный адрес+ код 00001), B соответствующих полях ячейки 4 по вычисленному адресу хранится начальный адрес некоторого блока третьего уровня, Далее вышеописанный процесс повторяется. В данном цикле при проверке поля признаков обнаруживается признак конца последовательности (для морфемы "БА"), однако с внешнего устройства выдается очередной сигнал "Запись" после чего начинается третий цикл работы устройства, который протекает аналогично второму циклу, После выдачи четвертого сигнала "Запись" функционирование устройства совпадает с основным изобретением. При этом код буквы записывается во входной регистр

1, На адресном входе блока 3 памяти в этот момент установлен начальный адрес блока четвертого уровня в ячейках которого записаны коды 4-х букв, которые могут иметь для последовательности БАЛ.

Затем с блока 9 управления на управляющие входы блока 3 пяти и входного регистра 1 поступают сигналы чтения, а на управляющий вход компаратора 2 — сигнал сравнения. В результате в компараторе 2 производится сравнение содержимых поля

5 символов текущей ячейки 4 и входного регистра 1.

Если совпадения при этом не произошло, в сумматоре 8 складываются значения на выходе сумматора 8, поступающее на его третий вход и значение с выхода поля 6 указателей текущей ячейки 4, поступающее на первый вход сумматора 8.

Для этого с блока 9 управления на управляющие входы сумматора 8 подаются сигналы приема информации и код операции сложения над соответствующими операндами. В результате этого сложения получаем адрес следующей ячейки 4 блока, содержимое поля 5 символом которой также сравнивается в компараторе 2 с содержимым входного регистра 1, и т.д. Описанная последовательность операций продолжается до тех пор, пока содержимое поля 5 символов некоторой ячейки 4 данного блока не совпадает с содержимым входного регистра 1,.

Как только совпадение произошло (для нашего примера это происходит в первом цикле сравнения), содержимое сумматора 8 получает единичное приращение. Для этого с блока 9 управления на выходы х6 и х7 подаются сигналы выборки второго и третьего входов сумматора 8, а на выход х9— инструкция сложения. При этом в сумматоре 8 складываются текущее содержимое с выхода сумматора 8 и число "1", поступающее на второй вход сумматора 8.

B результате приращения значения адреса на единицу мы всегда получаем адрес ячейки 4, в которой записан первый элемент блока следующего уровня, После этого во входной регистр 1 заносится код очередного символа опросной последовательности и производится аналогичная процедура поиска этого символа в данном блоке, Процедура поиска адресной последовательности продолжается до тех пор, пока в блок 9 управления с поля признаков 7 соответствующей ячейки 4 блока 3 памяти и с внешнего устройства не поступят соответственно признак конца последовательности и сигнал конца опросной последовательности. В этой ситуации сумматор 8 указывает на ячейку 4, в которой записан последний символ последовательности, хранимой в блоке 3 памяти и тождественной опросной последовательности. Этот адрес однозначно определяет данную последовательность и служит ее кодом, Поэтому блок 9 управления выдачей сигнала "Положительный результат поиска" оповещает внешнее устройство о том, что на выходе устройства имеется результат поиска опросной последовательности в виде кода-адреса. На этом ассоциативный поиск опросной последовательности завершается.

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

1765848

10 обнаруживается признак конца блока. При этом блок 9 управления вырабатывает для внешнего устройства сигнал "Ошибка" и работа устройства на этом завершается.

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

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

Ассоциативное запоминающее устройство, по авт,св, hL 1679554, о т л и ч а ю щ е5 е с я тем, что, с целью повышения быстродействия, в устройстве третий информационный вход сумматора подключен к информационному входу устройства, четвертый информационный вход сумматора

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

ИФВ

ИВЮ

ИВВ

1765848

t1Я11

0000I

OOOI0

ЕЕС3

ЯЯ.) (nn

lXZ3 ПШ

1765848

Составитель Г.Токмаков

Редактор Т,Орловская Техред М,Моргентал Корректор Э,Лончакова

Заказ 3387 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101