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

 

Изобретение относится к вычислительной технике и может быть исг пользовано в системах управления базами данных или в программно-аппаратных средствах, осуществляющих «« перевод с языков программирования высокого уровня на машииньа язык Целью изобретения является повышение производительности за счет динамического включения и ввода данных в реальном времени работы. Устройство содержит группу 1 элементов ЮИ, регистр 2 адреса, регистр 3 информации, имеющий поле 4 ключа, поле 5 данных и поле 6 ссылки, блок 7 памяти, дешифратор 8, регистр 9 ключа, 10 сравнения, генератор 11 тактовых импульсов, злемент 12 задержки, элемент 1 ШИ 13, группы 14-20 элементов И, элe ieнты И 21-23, регистр 24 данных, блок 25 сложения по модулю два, сумматор 26. регистр 27 базы, регистр 28 адреса, блок 29 управления . 1 з.п. ф-лы, 6 iin, S3 07./

союз советских социАлистичесник

Респувлин (5D 4 0 06 1 "-5/40 госудАРственчый ноыитет

ПО изсБРетеииям и ОТКРытиям при гкнт ссС (21) 4178576/24-24 (22) 08,01.87 (46) 15.01.89. Бюл. Р 2 (71) Ленинградский электротехнический институт им.В.И.Ульянова (Ленина) (72) В.С.Фомичев, Г.В.Разумовский (SU) и Уве Пютчлер (DD) (53) 681.3.016(088.8) (56) Авторское свидетельство СССР

1208563ь кл. С. 06 F 15/38, 1984.

Авторское свидетельство СССР

Р 1206810, кл. С 06 P 15/40, 1984. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть ис пользовано в системах управления базами данных нли в программно-аппаратных средствах, осуществляющих

„„SU„„f45 l 725 .А 1 перевод с языков программирования высокого уровня на маши ;.:-и язык.

Целью изобретения является повышение производительности за счет д1п-:;-.мического включения и ввода данных в реальном времени работы. Устройство содержит группу 1 элементов IHH, регистр 2 адреса, регистр 3 r:H4 ñрмации, имеющий поле 4 клкча, поле 5 ",анных и поле 6 ссылк.<, блок 7 памят, дешифратор 8, регистр 9 ключа, =.åë 10 сравнения, генератор 11 так-.оных импульсов, элемент 12 задержки, элемент ИЛИ 13 группы 14-20 элементов И, элементы И 21-23, регистр 24 данных, .блок 25 сложения Ji0 мо вЂ,,:i два, сумматор 26. регистр 27 базы, регистр 28 адреса, блок 29 упр;.влення, 1 з.i i. д>-лы, 6

145 t725

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

Целью изобретения является повышение производительности за счет динамического включения и ввода данных в реальном времени работы. 15

На фиг. 1 представлена схема предлагаемого устройства; на фиг. 2— применяемое в устройстве представление данных," на фиг. З.и 4 — временные диаграммы работы устройства 20 в режимах поиска и включения; на фиг. 5 — схема блока управления; на фиг. 6 — пример определения адреса входа в хештаблицу.

Устройство содержит группу 1 элементов ИЛИ, регистр 2 адреса, регистр

3 информации, имеющий поле 4 ключа, поле 5 данных и поле 6 ссылки, блок 7 памяти, дешифратор 8, регистр 9 ключа, узел 10 сравнения, генератор 11 тактовых импульсов, элемент 12 задержки, элемент ИЛИ 13, группы 1420 .элементов И, элементы И 21-23, регистр 24 данных, блок 25 сложения по модулю два, сумматор 26, регистр 35

27 базы, регистр 28 адреса, блок 29 управления с входами 30-34 и выходами

35-42, входы 43-50 устройства, выходы 51-53 устройства, регистр 54 сдвига, триггеры 55 и 56, элементы 40

57 и 58 задержки, элементы ИЛИ 59-61 и элементы И 62-70.

Для работы устройства используется следующее представление данных. Память разделена на две области: в 45 первой области хранится хештаблица, а во второй области хранятся данные.

Хештаблица содержит адреса данных.

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

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

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

В исходном состоянии все записи хештаблицы обнулены. По входу 46 поступает базовый адрес хештаблицы в регистр 27 базы, По входам 48 и 49 устанавливается режим работы устройства. Устройство может работать в режиме включения и в режиме поиска, устанавливаемых соответственно сигналами на входах 48 и 49. В исходном состоянии перед каждым рабочим циклом устройства генератор 11 за-. торможен и блок 29 управления установлен в начальное состояние сигналом, подаваемым на вход 50 установки.

В режиме поиска устройство работает следующим образом.

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

30 блока 29 управления. Последний выдает импульс по выходу 35 на вход сумматора 26, вызывающий сложение содержимого регистра 27 базы с выходом блока 25, представляющим собой значение хешфункции ключа, находящегося в регистре 9 ключа. По второму импульсу блок 29 управления вы1451725 дает сигнал по выходу 37. Содержимое сумматора 26 через группу 20 элементов И и группу 1 элементов ИЛИ передается на регистр 2 адреса. По третьему импульсу, переданному блоком 29 управления на выход 39, осуществляется прием записи из блока 7 памяти на регистр 3 информации ° В дельнейшем работа устройства может продолжаться двумя путями, Ключ считанной записи не совпадает с ключом искомой записи. Такая ситуация будет всегда возникать при чте-. нии записи из хештаблицы, в поле ключа которой записаны нули. В этом случае появляется сигнал на выходе неравенства узла 10 сравнения, подготавливающий к открытию элемент

И 22. Если в поле 6 ссылки прочитанной записи coäåðæèòñÿ отличное от нуля значение, то на выходе дешифратора 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

45 лаются данные этой записи по выходу

55

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 блока управле- 1 ния и записывает содержимое регистра

3 информации в блок 7 памяти. Таким

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

Операция определения адреса входа в хештаблицу выполняется как в режиме поиска, так и в режиме включения.

Базовый адрес хештаблицы БА (фиг. 6) установлен в регистре 27 базы, а в регистр 9 ключа занесен ключ. В режиме поиска первый импульс, выдаваемый блоком управления, вызывает сложение содержимого регистра 27 базы с выходом блока 25, представляющим собой значение хешфункции ключа, на ходящегося в регистре 9 ключа. В выбранном примере блок 25 выполняет сложение по модулю два двух байтов слова ключа, содержащегося в регистре 9 (16 разрядов). Результат выполнения этой логической операции (8 разрядов) складывается в сумматоре 26 с базовым адресом 0010,6 хештаблицы, хранящимся в регистре 27 базы, Следовательно, значение хешфункции может изменяться в диапазоне от 00, до FF u хештаблица имеет соответственно 256 элементов, расположенных в блоке 7 памяти, начиная с адреса 0010 включая адрес 010F, . Ha выходе сумматора 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 появился сигнал, означающий, что в поле ссыл ки прочитанной записи содержится

Зр нуль, то он передается через эле-, мент И 68 и элемент ИЛИ 60 на выходы

40 и 4 1. С выхода 40 импульс поступает на вход генератора 11 и останавливает его, а с выхода 41 он передается на признаковый выход 52 устроиства.

Режим включения.

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

4р того, он проходит через элемент

И 70 на выход 36 и через элемент

58 задержки на выход 42, с которого импульс поступает на вхер; записи блока 7 памяти и второй синхрони45 зирующий вход регистра. 3 информации.

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

5р нулевой ccbUIKGH появляется сигнал на входе 31, который передается через элементы И 69 и ИЛИ 59 на единичный вход триггера 55, переведя его в единичное состояние. После установки триггера 55 в единичное состояние импульс тактовой последовательности бупет передаваться через элемент

57 задержки, сдвигать содержимое регистра 54 на один разряд. Следую725

7 1451 щий импульс проходит через элементы

И 66 и 65 и элемент ИЛИ 60 на выходы

40 и 41, а через элементы И 66 и 65, элемент ИЛИ 61 и элемент 58 задерж"

5 ки — на выход 42. формула изобретения

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

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

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

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит регистр сдвига, два триггера, два элемента задержки, три элемента ИЛИ и девять элементов

И, причем синхронизирующий вход блока соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к единичному и нулевому выходам первого триггера соответственно, единичный вход которого соединен с выходом первого элемента ИЛИ, первый вход которого соединен с выходом третьего элемента И, установочный вход блока соединен с вторым входом первого элемента ИЛИ и с установочным входом регистра сдвига, вход сдвига которого соединен с выходом первого элемента

Регисщо МР задержки, выход первого элемента И соединен с входом первого элемента задержки и с первыми входами четвертого, пятого, шестого и седьмого элементов И, вторые входы которых соединены с выходами первого, второго, третьего и четвертого разрядов регистра сдвига соответственно, вы10 ход четвертого элемента И соединен с первым входом восьмого элемента И и с первым выходом блока, выход восьмого элемента И соединен с первым входом второго элемента ИЛИ и с вто1I5 рым выходом блока, выход пятого элемента И соединен с третьим выходом блока и с нулевым входом первого триггера, выход второго элемента ИЛИ через второй элемент задержки соеди20 нен с восьмым выходом блока, выход шестого элемента И является четвертым выходом блока, выход седьмого элемента И соединен с вторым входом второго элемента ИЛИ и с первым

2 входом третьего элемента ИЛИ, вы ход которого является первым и седьмым выходами блока, единичный и нулевой входы второго триггера являются входами включения и поиска

30 блока соответственно, единичный выход второго триггера соединен с вторым входом восьмого элемента И и с первым входом третьего элемента И, нулевой выход второго триггера подЗ5 ключен к первому входу девятого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, вход признака поля ссылки блока соединен с вторыми входами третьего и

10 девятого элементов И, выход второго элемента И является пятым выходом блока.

1451725 йФФ

ВыаО дылда

ЖмЮzi/а

Йюд 6/У

ЬгмУЯ

1451725

11 I Ф

Выход длока О

1(5t41I 3 1! 3 1IÝÔ

Сумматор N

8ыхо8 сумкапюра 26 (андрес 3яа8а Ю хаишадлицу)

Составитель А. Жеренов

Редактор А. Лежнина Техред A. KpaB yK Корректор Л.Патай

Заказ 7082/48 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР, 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно — полиграфическое предприятие, г. Ужгород, ул. Проектная, 4