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

(5, г.11.;.Ф,1лю ТЕНИЯ АНИЕ И К АВТОРСК с ТЕЛЬСТВУ оео ьединение о СССР, 1988,ОМИНАЮ к вычислитель- ассоциативным ам, Целью изоние быстродейасти вык ассоцивам,)ОО ф я тся тем, что м устройст,06,89 г,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР 61) 167955421) 4795557 24"Марс"72) Г,П,Токмаков56) Авторское свидетельствМ 1679554, кл. 0 11 С 15/0054) АССОЦИАТИВНОЕ ЗАПУСТРОЙСТВО57) Изобретение относитсяной технике, в частности кзапоминающим устройствбретения является повыше Изобретение относится к об ислительнойтехники,вчастност тивным запоминающим устро является усовершенствованием устр описанного в заявке М 4622825 т 22.12,88 11.Данное устройство используется для ассоциативного поиска информации, где в качестве опросных признаков используются последовательности произвольной длины, Информация в данном ассоциативном запоминающем устройстве организована в виде структуры поискового дерева, в которой каждый неконечный узел имеет блок узлов нижестоящего уровня. Для поиска элемента в этой структуре используется индексно-последовательный метод; текущий блок находится по индексу, а требуемый узел в блоке - путем последовательного сравнения ключевого элемента с узлами блока.Анализ словарей морфем и слов показывает, что блок первого уровня содержит 29 ствия. Устроиство предназначено для ассоциативного поиска информации, причем в качестве опросных признаков используются последовательности произвольной длины, Информация в данном ассоциативном запоминающем устройстве организована в виде структуры поискового дерева, в которой каждый неконечный узел имеет блок узлов нижестоящего уровня. Для поиска элемента в этой структуре используется индексно-последовательный метод, Текущий блок находится по индексу, а требуемый узел в блоке - путем последовательного сравнения ключевого элемента с узлами блока, 3 ил,узлов букв), блоки второго уровня - 18 - 22 узла, блоки третьего уровня - 10 - 12 узлов, а блоки четвертого и ниже уровней в среднем - 1 - 3 узла.Таким образом, самое большое количество операций сравнения приходится на первьге три уровня, т,е при поискепервых трех символов опросной последовательности, Процесс поиска последовательности можно значительно ускорить, если применить индексный способ поиска на первых трех уровнях структуры поискового дерева, а на остальных, как и в основном изобретении, - индексно-последовательный,Целью дополнительного изобретения является повышение быстродействия устройства за счет использования смешанного способа поиска на разных уровнях структуры поискового дерева.Поставленная цель достигаев ассоциативном запоминающеве положительное решение от1), содержащем регистр, информационныйзход которого является информационнымвходом устройства, а выход подключен кпервому входу компаратора, блок памяти,каждая ячейка которого содержит поле символов, поле указателей и поле признаков,причем выход поля символов подключен квторому входу комйаратора, выход поляуказателей подключен к первому информационному входу сумматора, второй информационный вход которого является входомединичного приращения, а к третьему информационному входу подключены его выходная шина, подключенная также кадресному входу блока памяти, одновременно является информационным входомустройства, выход поля признаков подключен к входу "Признак поиска" блока управления, к которому подключеныуправляющие входы и выходы устройства, 20информационный вход устройства соединен с третьим информационным входомсумматора.Заявляемое устройство отличается отосновного изобретения Ц тем что оно снабжено дополнительной связью: информационный вход устройства - третий входсумматора. Таким образом, заявляемое устройство отвечает критерию "новизна". Введение данной связи обеспечивает 30организацию поиска первых трех символовпо индексному способу, значительно повышающему быстродействие устройства, следовательно, обеспечивает устройствуналичие свойства, отвечающего критерию 35"существенное отличие",На фиг.1 представлена блок-схема устройства; на фиг.2 - структура поисковогодерева, записанная в адресном накопителе;на фиг.3 - алгоритм ассоциативного поиска 40последовательностей произвольной длины.Основу устройства составляет регистр1, вход которого является информационнымвходом устройства, а выход подключен кпервому информационному входу компаратора 2, блок 3 памяти, каждая ячейка 4 памяти которого содержит поле 5 символов,поле 6 указателей и поле 7 признаков, причем выход поля 6 указателей 6 подключен кпервому информационному входу сумматора 8, второй информационный вход которого является входом "Единичноеприращение", а к третьему информационному входу подключена его информационнаявыходная шина, подключенная также к адресному входу блока 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,В поле 7 признаков всех уровней хранятся признаки конца последовательности и конца блока,Фрагмент структуры поискового дерева для хранения корневых морфем приведен 5 на фиг.2. Здесь показаны те участки структуры, в которых хранятся морфемы:БАБАЛБАЛАБОЛБАЛАБОШБАЛАГАНБАЛАГУРБАЛАКБАЛАЛАБАЛАМУТБАЛ АМУЧБАЛАНДБАЛАХОНБАЛБЕСБАЛДБАЛ КБАЛМОШБАЛ МОЧБАЛТ 25БАЛЯС 10 15 20 30 ГГРОБГРОЖГРОЗГРОЗДГРОМГРОМАДГРОМОЖД 35 ГРОМОЗДГРОХГРОШПроведенные морфемы взяты из книги 2, 40Для повышения быстродействия устройства использовано следующее обстоятельство.В со временн ых вычислител ьн ых устройствах для кодирования букв использует ся стандартный 8-разрядный код (например, КОИ).Младшие 5 разрядов этого кода определяют конкретные буквы некоторого алфавита, а три старших разряда определяют 50 алфавит(латинский или русский) и характер буквы (строчная или прописная). Таким образом, буква в некотором алфавите однозначно определяется пятью разрядами. Поэтому на первом уровне код буквы явля ется адресом ячейки, в которой хранится указатель на начальный адрес блока второго уровня, Код второй буквы последовательности рассматривается как приращение относительно начального адреса выделенного блока второго уровня, в которой хранится указатель на начало блока третьего уровня.Код третьей буквы опросной последовательности рассматривается как приращение относительно начального адреса, выделенного блока третьего уровня, по которому хранится начальный адрес блока четвертого уровня,Начиная с четвертого уровня код четвертой буквы ищется в выделенном блоке путем последовательного сравнения данного кода с содержимым символьного поля ячеек выделенного блока. Далее процесс поиска проходит аналогично процессу ассоциативного поиска, описанного в основном изобретении.Блок-схема алгоритма функционирования устройства приведена на фиг.3 и описывается следующим образом.С внешнего устройства на шину ввода- вывода данных устройства в сопровождении сигнала "Запись" поступает код первой буквы опросной последовательности. Для более наглядного описания принципа действия устройства в качестве примера возьмем буквенную последовательность, составляющую корневую морфему "БАЛАГУР", Код первой буквы "б" в КОИ- 11000010.Младшие пять разрядов этого кода используются в качестве адреса ячейки 4 блока первого уровня.В устройстве управления ведется счет импульсам сигнала "Запись" и, если это число не больше трех, то младшие пять разрядов записываются в сумматор 8 по третьему входу и складываются с нулевым кодом по четвертому входу сумматора 8. Затем результат, сложения с выхода сумматора поступает на адресный вход блока 3, памяти,Для этого на вход х 7 подается управляющий сигнал записи по третьему информационному входу сумматора 8, затем на выход х 9 подается инструкция сложения,В этом случае мы получаем адрес третьей ячейки 4 блока первого уровня (код 00010), в полях указателей 6 и символа 5 которой хранится начальный адрес блока второго уровня, соотнесенного с первой буквой "б" искомой последовательности.Содержимое полей указателя и символа данной ячейки 4 заносится в сумматор 8 по четвертому информационному входу, для чего на выход х 8 подается сигнал выборки четвертого входа сумматора 8, а на выход х 9 - инструкция записи. После этого содержимое поля признаков 7 через вход у 2 проверяется на наличие признака конца последовательности.5 10 20 25 30 35 40 50 55 Если данный признак отсутствует, то устройство переходит в режим ожидания очередного сигнала "Запись", в противном случае в зависимости от поступления с внешнего устройства сигнала "Запись" или "Конец" устройство либо начинает работу выдачей сигнала "Положительный результат поиска" и адреса последней ячейки искомой последовательности на информационную шину ввода-вывода данных, который одновременно является кодом данной последовательности.Следующий цикл работы начинается с приходом сигнала "Запись" и кода второй буквы "а" на шину ввода-вывода данных,Так как это будет второй сигнал "Запись", то снова младшие 5 разрядов кода второй буквы (код 00001) заносятся по третьему входу сумматора 8, а затем складывается с содержимым по четвертому входу. При этом мы получаем адрес второй ячейки 4 блока второго уровня, выделенного в первом цикле работы устройства (Адрес = = Начальный адрес+ код 00001), В соответствующих полях ячейки 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.В результате приращения значения адреса на единицу мы всегда получаем адресячейки 4, в которой записан первый элемент блока следующего уровня, После этого во входной регистр 1 заносится код очередного символа опросной последовательности ипроизводится аналогичная процедура поиска этого символа в данном блоке, Процедура поиска адресной последовательности продолжается до тех пор, пока в блок 9 управления с поля признаков 7 соответствующей ячейки 4 блока 3 памяти и с внешнего устройства не поступят соответственно признак конца последовательности и сигнал конца опросной последовательности. В этой ситуации сумматор 8 указывает на ячейку 4, в которой записан последний символ последовательности, хранимой вблоке 3 памяти и тождественной опросной последовательности. Этот адрес однозначно определяет данную последовательность и служит ее кодом, Поэтому блок 9 управления выдачей сигнала "Положительный результат поиска" оповещает внешнееустройство о том, что на выходе устройства имеется результат поиска опросной последовательности в виде кода-адреса. На этом ассоциативный поиск опросной последовательности завершается,В ходе ассоциативного поиска возможна такая ситуация, когда при сравнении очередного элемента опросной последовательности ни один элемент опрашиваемого блока не совпадает с данным входным элементом. Эта ситуация выявляется тогда, когда после очередного несовпадения в поле 7 признаков данной ячейки 4обнаруживается признак конца блока. При этом блок 9 управления вырабатывает для внешнего устройства сигнал "Ошибка" и работа устройства на этом завершается.Введение связей информационной шины ввода-вывода устройства с третьим входом сумматора, выхода полей указателей и символов адресного накопителя с четвертым входом сумматора, позволяет значительно ускорить процесс ассоциативного поиска первых символов опросной последовательности на которые приходится значительный обьем операций сравнения,Формула изобретения Ассоциативное запоминающее устройство, по авт,св, М 1679554, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройстве третий информационный вход сумматора подключен к информационному входу устройства, четвертый информационный вход сумматора 10 соединен с третьим и четвертым выходамиблока памяти, четвертый вход разрешения приема информации сумматора соединен с двенадцатым выходом блока управления,1765848 Составитель Г.ТокмаковТехред М,Моргентал Корректор Э,Лончаков ктор Т,Орловска Заказ 3387 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101