Устройство для поиска информации

(511 4 ( 06 1 15(40 госуддрстеенчый нсиыитетПО ИЗСБРЕТЕИИЯМ И ОТНРЫТИЯМпри гкнт сссР(71) Ленинградский электротехнически институт им,В.И.Ульянова (Ленина) (72) В.С.фомичев, Г.В.Разумовский (8(3 и Уве Пютчлер (03)(56) Авторское свидетельство СССР Р 1208563, кл. С,06 Р 15/38, 1984,Авторское свидетельство СССР Р 1206810, кл. С Об Р 15/40, 1984. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНфОРИАЦИИ (57) Изобретение относится к вычислительной технике и может быть ис.пользовано в системах управления базами данных нли в программно-аппаратных средствах, осуществляющих перевод с языков программированиявысокого уровня на машин;.:и яэь 1 к,.Целью изобретения является повышениепроизводительности за счет динамического включения и ввода данных вреальном времени работы. Устройствосодержит группу 1 элементов 1 БИ, регистр 2 адреса, регистр 3 инФормацииимеющий поле 4 клкча, поле 5 данныхи поле 6 ссылки, блок 7 памяти, дешифр тор 8, регистр 9 ключа,зел 10сравнения, генератор 11 тактвыхимпульсов, элемент 12 задержки,элемент ИЛИ 13 группы 14-20 элементов И, элементы И 21-23, регистр 24данных, ,блок 25 сложения по модулюдва, сумматор 26. регистр 27 базы,регистр 28 адреса, блок 29 упр;.вления, ( з.п, д-лы, о нл,Изобретение относится к вычислительной технике и может быть использовано в системах управления базамиданных, системах автоматическогопроектирования или в специализированных программно-аппаратных средствах, осуществляющих перевод сязыков программирования высокогоуровня на промежуточный или машинный язык.Целью изобретения является повышение производительности за счетдинамического включения и ввода данных в реальном времени работы, 15На фиг. 1 представлена схемапредлагаемого устройства; на фиг. 2 -применяемое в устройстве представление данных," на фиг. 3 и 4 - временные диаграммы работы устройства 20в режимах поиска и включения; наФиг. 5 - схема блока управления; наФиг. 6 - пример определения адресавхода в хештаблицу.Устройство содержит группу 1 элементов ИЛИ, регистр 2 адреса, регистр3 информации, имеющий поле 4 ключа,поле 5 данных и поле 6 ссылки, блок 7памяти, дешифратор 8, регистр 9 ключа, узел 10 сравнения, генератор 11тактовых импульсов, элемент 12 задержки, элемент ИЛИ 13, группы 1420 элементов И, элементы И 21-23,регистр 24 данных, блок 25 сложенияпо модулю два, сумматор 26, регистр 3527 базы, регистр 28 адреса, блок 29управления с входами 30-34 и выходами35-42, входы 43-50 устройства, выходы 51-53 устройства, регистр 54сдвига, триггеры 55 и 56, элементы 4057 и 58 задержки, элементы ИЛИ 59-61и элементы И 62-70,Для работы устройства используетсяследующее представление данных. Память разделена на две области: в 45первой области хранится хештаблица,а во второй области хранятся данные.Хештаблица содержит адреса данных.Местоположение адреса данных в хештаблице вычисляется с помощью хешфункции. Среди хешфункций можновыделить класс Функций, которые могутбыть реализованы с помощью логическойсхемы и не требует больших аппаратных затрат, Такой способ определения 55хешфункции называется методом свертывания. Например, можно реализоватьтакую хешфункцию. которая вычисляетсяпутем сложения по модулю два опредеи ленных последовательностей разрядов,выделенных в поле ключа.Данные хранятся в памяти в видезаписей. Каждая запись состоит изполя ключа, поля значения данных,поля ссылки и считывается за однообращение к памяти, Поиск записи вобласти данных осуществляется поключу, значение которого должно бытьотличным от нуля. Все записи, ключикоторых имеют одинаковые значенияхешфункции, в области данных связы"ваются в цепочку при помощи поляссылки. Конец цепочки записей определяется уникальным значением поляссылки. В устройстве таким уникальным значением являются нули во всехразрядах поля ссылки.Хештаблица представляет собойпоследовательность записей, в поляхссылки которых содержатся адреса.первых элементов цепочек записей,имеющих одинаковое значение хешфункции, а другие поля этих записей содержат нули,Устройство работает следующимобразом.В исходном состоянии все записихештаблицы обнулены. По входу 46поступает базовый адрес хештаблицыв регистр 27 базы, По входам 48 и 49устанавливается режим работы устройства. Устройство может работать врежиме включения и в режиме поиска,устанавливаемых соответственно сигналами на входах 48 и 49. В исходном состоянии перед каждым рабочимциклом устройства генератор 11 за-.торможен и блок 29 управления установлен в начальное состояние сигналом, подаваемым на вход 50 установки.В режиме поиска устройство работает следующим образом,По входу 44 в регистр 9 ключазаносится ключ искомой записи. Поиск инициируется подачей импульсана вход 45, в результате запускаетсягенератор 11. Первый импульс поступает с выхода генератора 11 на вход30 блока 29 управления. Последнийвыдает импульс по выходу 35 на входсумматора 26, вызывающий сложениесодержимого регистра 27 базы с выходом блока 25, представляющим собой значение хешфункции ключа, находящегося в регистре 9 ключа. По второму импульсу блок 29 управления вы1451725 45 даются данные этой записи по выходу 50 55 дает сигнал по выходу 37. Содержимое сумматора 26 через группу 20элементов И и группу 1 элементов ИЛИпередается на регистр 2 адреса. Потретьему импульсу, переданному блоком 29 управления на выход 39, осуществляется прием записи из блока 7памяти на регистр 3 информацииВдельнейшем работа устройства можетпродолжаться двумя путями,Ключ считанной записи не совпадаетс ключом искомой записи. Такая ситуация будет всегда возникать при чте-.нии записи из хештаблицы, в поле клю"ча которой записаны нули. В этомслучае появляется сигнал на выходенеравенства узла 10 сравнения, подготавливающий к открытию элементИ 22. Если в поле 6 ссылки прочитанной записи содержится отличное отнуля значение, то на выходе дешифратора 8 отсутствует сигнал, и выходэлемента И 22 подготавливает к открытию группу 14 элементов И, Поимпульсу с выхода элемента 12 задержки открывается группа 14 элементов И и адрес из поля 6 ссыпки регистра информации переписывается врегистр 2 адреса. По следующему импульсу, поступающему с выхода 39блока управления в регистр 3, будетпрочитана из блока 7 памяти следующая запись, которая анализируетсяаналогичным образом, Если в поле 6ссылки содержатся нули, то ча выходедешифратора 8 появляется сигнал,запрещающий передачу поля 6 ссылкичерез группу 14 элементов И на регистр 2 и подготавливающий элементИ 23 к открытию. По импульсу с выхода элемента 12 задержки поступаетсигнал на вход 31 блока управления,который вырабатывает на выходе 40сигнал, останавливающий генератор 11,и одновременно вырабатывает на выходе41 сигнал, указывающий на отсутствиев таблице искомой записи.Если ключ считанной записи совпадает с ключом искомой записи,то появляется сигнал на выходеравенства узла 10 сравнения, подготавливающий к срабатыванию элементИ 21, При появлении импульса навыходе элемента 12 задержки срабатывает элемент И 21, в результате чегополе 5 данных искомой записи черезгруппу 16 элементов И поступает навыход 51 устройства, а генератор 11 5 1 О 15 20 25 30 35 40 останавливается. Одновременно на выходе 53 появляется импульс, указывающий, что запись с заданным ключомнайдено в таблице,В режиме включения устройствоработает следующим образом,По входу 44 в регистр 9 ключазаносится ключ, по входу 43 в регистр 24 данных загружаются данныевносимой записи и по входу 47 записывается адрес свободной ячейки памяти в регистр 28 адреса. Включениеинициируется подачей импульса навход 45, в результате чего запускается генератор 11По первому импульсу аналогично режиму поиска выполняется сложение в сумматоре 26.Одновременно блок управления выдаетна выход 36 сигнал, открывающийгруппы 15, .17 и 18 элементов И, Поэтому же сигналу в регистр 2 адресазаписывается адрес свободной ячейкипамяти с регистра 28 адреса, вразряды поля 4 ключа регистра информации передается ключ с регистра9 ключа, в разряды поля 5 данныхрегистра информации загружаютсяданчые из регистра 24 данных, аразряды поля 6 ссылки регистра информации сбрасываются в нуль, Тот жеимпульс, появляющийся с задержкойна выходе 42 блока 29 управления,записывает сформированную на регистре3 информации запись в блок 7 памяти.Начиная с второго импульса выполняются те же действия, что и в режимепоиска, т.еосуществляется поискзаписи, имеющей заданный в регистре9 ключ. Дальнейшая работа в зависимости от результата поиска можетпроисходить двумя путями,В таблице уже существует запись с заданным ключом, В этом случае вы 51 и признак по выходу 53. Новая запись в область данных не включается, и генератор 11 останавливается,В таблице отсутствует запись с заданным ключом. В этом случае появление сигнала на выходе 31 блока управления вызывает следующие действия.В отличие от режима поиска сигнал останова по выходу 40 не выдается блоком управления. Следующий импульспередается блоком управления на вв" ход 38, в результате чего содержимоевторого регистра 28 адреса (адресновой записи) записывается черЕз5 145 элементы И группы 19 в разряды поля 6 ссылки регистра информации. Следующий импульс, выдаваемый на выходы 40 и 41 блока управления, останавливает генератор 11 и является признаком конца операции включения, который передается на выход 52 устройства. Этот же импульс с задержкой поступает с выхода 42 блока управле ния и записывает содержимое регистра 3 информации в блок 7 памяти, Таким/ образом, в поле ссылки обновленной записи будет содержаться адрес вклю т.чаемой записи, продолжая цепочку записей имеющих одинаковую хешфункцию.ФОперация определения адреса входа в хештаблицу выполняется как в режиме поиска, так и в режиме включения. Базовый адрес хештаблицы БА (фиг. 6) установлен в регистре 27 базы, а в регистр 9 ключа занесен ключ, В режиме поиска первый импульс, выдаваемый блоком управления, вызывает сложение содержимого регистра 27 базь 1 с выходом блока 25, представляющим собой значение хешфункции ключа, на ходящегося в регистре 9 ключа. В выбранном примере блок 25 выполняет сложение по модулю два двух байтов слова ключа, содержащегося в регистре 9 (16 разрядов). Результат выполнения этой логической операции (8 разрядов) складывается в сумматоре 26 с базовым адресом 0010,6 хештаблицы, хранящимся в регистре 27 базы, Следовательно, значение хешфункции может изменяться в диапазоне от 00, до РР, и хештаблица имеет соответственно 256 элементов, расположенных в блоке 7 памяти, начиная с адреса 0010 , включая адрес 010 Р, . На выходе сумматора 26 формируется адрес элемента хештабли; цы, с которого начинается поиск.Представленный пример раскрывает лишь одну из последовательностей нулей и единиц в ключе и показывает назначение выполнения операции сложения по модулю два и как этот результат используется при работе устройства.Исходное состояние блока управления устанавливается по сигналу на входе 34, а в регистр 54 записывается код 1000, Триггер 55 этим же сигналом переводится в единичное состояние. Режим работы устройства устанавливается подачей сигнала на вход 32 блока управления, устанавли 1725 6вающий триггер 56 в единичное состояние (режим включения), или на вход33, устанавливающий триггер 56 внулевое состояние (режим поиска).После запуска устройства тактовыеимпульсы поступают на вход 30 блокауправления, Дальнейшая работа блока29 управления в зависимости от уста новленного режима может происходитьдвумя путями.Режим поиска.Первый импульс тактовой последовательности проходит через элементы 5 И 66 и 62 на выход 35. Элемент И 70закрыт, Этот же импульс, проходячерез элемент 57 задержки, сдвигаетсодержимое регистра 54 на один разряд. Второй импульс проходит через 20 элементы И 66 и 63 на выход 37 ипоступает на нулевой вход триггера55, устанавливая его в нулевоесостояние, После этого происходитсдвиг единицы в третий разряд регистра 54. Третий и последующие импульсы проходят через элемент И 67 навыход 39. Если на входе 31 появилсясигнал, означающий, что в поле ссылки прочитанной записи содержится 30 нуль, то он передается через эле-,.мент И 68 и элемент ИЛИ 60 на выходы40 и 4 1. С выхода 40 импульс поступает на вход генератора 11 и останавливает его, а с выхода 41 онпередается на признаковый выход 52устроиства.Режим включения.Первый импульс аналогично режимупоиска передается на выход 35, Кроме 40 того, он проходит через элементИ 70 на выход 36 и через элемент58 задержки на выход 42, с которогоимпульс поступает на вход записиблока 7 памяти и второй синхрони зирующий вход регистра. 3 информации.Второй, третий и последующие импульсы проходят через блок управленияаналогично режиму поиска. Послечтения из блока памяти записи с 50 нулевой ссылкой появляется сигнал навходе 31, который передается черезэлементы И 69 и ИЛИ 59 на единичныйвход триггера 55, переведя его вединичное состояние. После установки 55 тРиггера 55 в единичное состояниеимпульс тактовой последовательностибудет передаваться через элемент57 задержки, сдвигать содержимоерегистра 54 на один разряд, Следую725 1, Устройство для поиска информа ции, содержащее группу элементов ИЛИ, первый регистр адреса, регистр информации, блок памяти, дешифратор, регистр ключа, узел сравнения, генератор тактовых импульсов, элемент за держки, элемент ИЛИ, три группы элементов И и первый элемент И, причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, вход останова которого 20 соединен с выходом элемента ИЛИ, выходы элементов И первой и второй. групп соединены соответственно с первыми и вторыми входами элементов ИЛИ группы, выходы которых соединены с входом первого регистра адреса, выход которого соединен.с адресным входом блока памяти, вход признака поиска устройства является входом регистра ключа, выход которого под ключен к первому входу узла сравнения, второй вход которого соединен с выходами разрядов поля ключа регистра информации, выходы разрядов поля данных которого соединены с первыми входами элементов И третьей группы, вторые входы которых и первый вход элемента ИЛИ соединены с выходом первого элемента И, первый вход которого подключен к выходу равенства узла сравнения, выход элементы задержки соединен с вторым входом первого элемента И и с первыми входами элементов И первой Группы, вторые входы которых подклю чены к выходам разрядов поля ссыпки регистра информации, выходы элементов И третьей группы являются выходом данных устройства, о т л ич а ю щ е е с я тем, что, с целью 50 повышения производительности за счет динамического включения и ввода данных в реальном времени работы, в него введены регистр данных, блок сложения по модулю два, сумматоР, 55 регистр базы, второй регистр адреса, блок управления, четыре группы элементов И, два элемента И, причем вход данных устройства подключен к 40 7 1451щий импульс пРоходит через элементыИ 66 и 65 и элемент ИЛИ 60 на выходы40 и 41, а через элементы И 66 и 65,элемент ИЛИ 61 и элемент 58 задерж"5ки - на выход 42. Формула изобретения входу регистра данных, выход которого соединен с первыми входами элементов И четвертой группы, выходы которых соединены с входами разрядов поля данных регистра информации соответственно, информационные вход и выход которого соединены с информационными выходом и входом блока памяти, соответственно, выход регистра ключа соединен с первыми входами элементов И пятой группы и с выходом блока сложения по модулю два, выход которого подключен к входу первого слагаемого сумматора, вход второго слагаемого которого соединен с выходом регистра базы, вход которого является первым адресным входом устройства, управляющий вход сумматора соединен с первым выходом блока управления, синхронизирующий вход которого подключен к выходу генератора тактовых импульсов, второй адресный вход устройства подключен к входу второго регистра адреса, выход которого соединен с первыми вхоами элементов И второй и шестой Групп, выходы элементов И шестой группы соединены с входами разрядов поля ссылки регистра информации соответственно, входы разрядов поля ключа которого соединены с выходами элементов И пятой группы соответственно, второй выход блока управления соединен с вторыми входами элементов И второй, четвертой, пятой групп и с входом установки в "Он разрядов поля ссылки регистра информации, третий выход блока управления соединен с первыми входами элементов И седьмой группы, выходы которых соединены с третьими входами элементов ИЛИ группы соответственно, вторые входы элементов И шестой группы соединены с четвертым выходом блока управления, пятый выход которого подключен к входу элемента задержки, к входу чтения блока памяти и к первому синхронизирующему входу регистра информации, выходы разрядов поля ссылки которого соединены с входом дешифратора, выход которого соединен с инвертирующим входом второго элемента И и с первым входом третьего элемента И, выход которого соединен с входом признака поля ссылки блока управления, шестой вход которого подключен к второму входу элемента ИЛИ, установочные входы режи 1451125мов включения и поиска соединены соответственно с входами включенияи поиска блока управления, установочный вход которого соединен с входом установки устройства, выход неравенства узла сравнения соединен с вторым входом второго элемента И, выход которого соединен с третьими входами элементов И первой группы,я. выход сумматора соединен с вторыми входами элементов И седьмой группы, седьмой выход блока управления соединен с выходом окончания операции включения устройства, признаковый выход устройства соединен с выходом первого элемента И, второй вход третьего элемента И соединен с выходом элемента задержки, восьмой выход блока управления соединен с входом записи блока памяти и с вторым синхронизирующим входом регистра информации,12. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит регистр сдвига, два триггера, два элемента задержки, три элемента ИЛИ и девять элементов И, причем синхронизирующий вход блока соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к единичному и нулевому выходам первого триггера соответственно, единичный вход которого соединен с выходом первого элемента ИЛИ, первый вход которого соединен с выходом третьего элемента И, установочный вход блока соединен с вторым входом первого элемента ИЛИ и с установочным входом регистра сдвига, вход сдвига которого соединен с выходом первого элементаРегистР АР задержки, выход первого элемента И.соединен с входом первого элементазадержки и с первыми входами четвертого, пятого, шестого и седьмогоэлементов И, вторые входы которыхсоединены с выходами первого, второго, третьего и четвертого разрядоврегистра сдвига соответственно, вы 10 ход четвертого элемента И соединенс первым входом восьмого элемента Ии с первым выходом блока, выход восьмого элемента И соединен с первымвходом второго элемента ИЛИ и с вто 15 рым выходом блока, выход пятого элемента И соединен с третьим выходомблока и с нулевым входом первоготриггера, выход второго элемента ИЛИчерез второй элемент задержки соеди 20 нен с восьмым выходом блока, выходшестого элемента И является четвертым выходом блока, выход седьмогоэлемента И соединен с вторым входомвторого элемента ИЛИ и с первым25 входом третьего элемента ИЛИ, выход которого является первым иседьмым выходами блока, единичныйи нулевой входы второго триггераявляются входами включения и поиска30 блока соответственно, единичный выход второго триггера соединен с вторым входом восьмого элемента И и спервым входом третьего элемента И,нулевой выход второго триггера подЗб ключен к первому входу девятого элемента И, выход которого соединен свторым входом третьего элемента ИЛИ,вход признака поля ссылки блока соединен с вторыми входами третьего и40 девятого элементов И, выход второго элемента И является пятым выходом блока,1451725 В Ю стра йище Виад вамаьаВ1351311 1 1 111 Ф 1451725 Выход длока О ОРУ ставитель А. Жерено хред А. Кра вчук орректор Л.Патай Редактор А. Лежнина 082/4 Госуд Зака ВНИИ Производственно-полиграфическое предприятие, г. Ужгоро оектная, 4 Тираж 667 твенного комитет 113035, Москва, 8 ыхо 8 сумматора Ж(а 8 рес Зноби д хйиФРдлиф) Подписноео изобретениям и открытиям при ГКНТ СССР,35, Раушская наб д. 4/5