Устройство для поиска информации Советский патент 1989 года по МПК G06F17/30 

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

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

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

Устройство содержит группу 1 элементов ИЖ, регистр 2 адреса, регистр 3 информации, имеющий поле 4 ключа, поле 5 данных и поле 6 ссылки, блок. 7 памяти, дешифратор 8, регистр 9 ключа, узел 10 сравнения, генератор 11 тактовых импульсов, элемент 12 задержки, элемент ИЛИ 13, группы 14- 20 -элементов И, элементы И 21-23, регистр 24 данных, блок 25 сложения по модулю два, сумматор 26, регистр 27 базы, регистр 28 адреса, блок 29 управления с входами 30-34 и выходами 35-42, входы 43-50 устройства, выходы 51-53 устройства, регистр 54 сдвига, триггеры 55 и 56, элементы 57 и 58 задержки, элементы ИЛИ 59-61 и элементы И 62-70.

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

5

0

5 0

5 0 5

ленных последовательностей разрядов, вьщеленных в поле ключа.

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

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

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

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

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

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

Ключ считанной записи не совпадает с ключом искомой записи. Такая ситуация будет всегда возникать при чтеНИИ записи из хештаблицы, в поле клю- 15 вход 45, в результате чего запускача которой записаны нули. В этом случае появляется сигнал на выходе неравенства ,узла 10 сравнения, подготавливающий к открытию элемент И 22. Если в поле 6 ссылки прочитанной записи додержится отличное от нуля значение, то на выходе дешифратора 8 отсутствует сигнал, и выход элемента И 22 подготавливает к открытию группу 14 элементов И, По импульсу с выхода элемента 12 задержки открывается группа 14 элементов И и адрес из поля 6 ссыпки регистра информации переписывается в регистр 2 адреса. По следующему импульсу, поступающему с выхода 39 блока управления в регистр 3, будет прочитана из блока 7 памяти следующая запись, которая анализируется аналогичным образом. Если в поле 6 ссьшки содержатся нули, то на выходе дешифратора 8 появляется сигнал, запрещающий передачу поля 6 ссылки через группу 14 элементов И на регистр 2 и подготавливающий элемент И 23 к открытию. По импульсу с выхода элемента 12 задержки поступает сигнал на вход 31 блока управления, который вырабатывает на выходе 40

20

25

30

35

40

ется генератор 11. По первому импульсу аналогично режиму поиска выполняется сложение в сумматоре 26. , Одновременно блок управления выдает на выход 36 сигнал, открывающий группы 15, 17 и 18 элементов И. По этому же сигналу в регистр 2 адреса записывается адрес свободной ячейки памяти с регистра 28 адреса, в разряды поля 4 ключа регистра информации передается ключ с регистра 9 ключа, в разряды поля 5 данных регистра информации загружаются данные из регистра 24 данных, а разряды поля 6 ссылки регистра информации сбрасываются в нуль. Тот же импульс, появляющийся с задержкой на выходе 42 блока 29 управления, записывает сформированную на регистре 3 информации запись в блок 7 памяти. Начиная с второго импульса вьшолня- ются те же действия, что и в режиме поиска, т.е. осуществляется поиск записи, имеющей заданный в регистре 9 ключ. Дальнейшая работа в зависимости от результата поиска может происходить двумя путями.

В таблице уже существует запись

заданным ключом. В этом случае высигнал, останавливающий генератор 11, 45 даются данные этой записи по выходу

51 и признак по выходу 53. Новая запись в область данных не включается, и генератор 11 останавливается. В таблице отсутствует запись с за50 данным ключом. В этом случае появление сигнала на выходе 31 блока управления вызывает следующие действия. В отличие от режима поиска сигнал останова по выходу 40 не выдается бло55 ком управления. Следующий импульс передается блоком управления на выход 38, в результате чего содержимое второго регистра 28 адреса (адрес новой записи) записывается через

и одновременно вырабатывает на выходе 41 сигнал, указывающий на отсутствие в таблице искомой записи.

Если ключ считанной записи совпадает с ключом искомой записи, то появляется сигнал на выходе равенства узла 10 сравнения, подготавливающий к срабатыванию элемент И 21. При появлении импульса на выходе элемента 12 задержки срабатывает элемент И 21, в результате чего поле 5 данных искомой записи через группу 16 элементов И поступает на выход 51 устройства, а генератор 11

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

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

По входу 44 в регистр 9 ключа заносится ключ, по входу 43 в регистр 24 данных загр жаются данные вносимой записи и по входу 47 записывается адрес свободной ячейки памяти в регистр 28 адреса. Включение инициируется подачей импульса на

0

5

0

5

0

ется генератор 11. По первому импульсу аналогично режиму поиска выполняется сложение в сумматоре 26. , Одновременно блок управления выдает на выход 36 сигнал, открывающий группы 15, 17 и 18 элементов И. По этому же сигналу в регистр 2 адреса записывается адрес свободной ячейки памяти с регистра 28 адреса, в разряды поля 4 ключа регистра информации передается ключ с регистра 9 ключа, в разряды поля 5 данных регистра информации загружаются данные из регистра 24 данных, а разряды поля 6 ссылки регистра информации сбрасываются в нуль. Тот же импульс, появляющийся с задержкой на выходе 42 блока 29 управления, записывает сформированную на регистре- 3 информации запись в блок 7 памяти. Начиная с второго импульса вьшолня- ются те же действия, что и в режиме поиска, т.е. осуществляется поиск записи, имеющей заданный в регистре 9 ключ. Дальнейшая работа в зависимости от результата поиска может происходить двумя путями.

В таблице уже существует запись

элементы И группы 19 в разряды поля 6 ссылки регистра информации. Следующий импульс, выдаваемьш на выходы 40 и 41 блока управления, останавливает генератор 11 и является признаком конца операции включения, который передается на выход 52 устройства. Этот же импульс с задержкой

вающий триггер 56 в единичное состояние (режим включения), или на вход 33, устанавливающий триггер 56 в нулевое состояние (режим поиска). После запуска устройства тактовые импульсы поступают на вход 30 блока управления. Дальнейшая работа блока 29 управления в зависимости от уста

Изобретение относится к вычислительной технике и может быть исг пользовано в системах управления базами данных или в программно-аппаратных средствах, осуществляющих «« перевод с языков программирования высокого уровня на машииньа язык Целью изобретения является повышение производительности за счет динамического включения и ввода данных в реальном времени работы. Устройство содержит группу 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./

поступает с выхода 42 блока управле- IQ новленного режима может происходить

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

Операция определения адреса входа в хештаблицу выполняется как в режиме поиска, так и в режиме включения. Базовый адрес хбштаблицы БА (фиг. 6) установлен в регистре 27 базы, а в регистр 9 ключа занесен ключ. В режиме поиска первьй импульс, выда ваемый блоком управления, вызывает

сложение содержимого регистра 27 базы 25 ра 54. Третий и последующие импуль- с выходом блока 25, представляющим собой значение хешфункции ключа, находящегося в регистре 9 ключа. В выбранном примере блок 25 выполняйт сложение по модулю два двух байтов ело- зо ва ключа, содержащегося в регистре 9 (16 разрядов). Результат вьшолнения этой логической операции (8 разрядов) складывается в сумматоре 26 с базовым

сы проходят через элемент И 67 на выход 39. Если на входе 31 появился сигнал, означающий, что в поле ссып ки прочитанной записи содержится нуль, то он передается через злег- мент И 68 и элемент ИПИ 60 на выходы 40 и 41. С выхода 40 импульс поступает на вход генератора 11 и останавливает его, а с выхода 41 он

адресом 0010, хештаблицы, хранящимся « передается на признаковый выход 52 в регистре 27 базы. Следовательно, устройства, значение хешфункции может изменяться Режим включений, в диапазоне от 00 , до FF и хеш-, таблица имеет соответственно 256 элеПервьй импульс аналогично режим поиска передается на выход 35. Кро

ментов, расположенных в блоке 7 памяти, начиная с адреса , включая адрес . На выходе сумматора 26 формируется адрес элемента хещтабли -, цы, с KciToporo начинается поиск.

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

Исходное состояние блока управления устанавливается по сигналу на входе 34, а в регистр 54 записывается код 1000. Триггер 55 этим же сигналом переводится в единичное состояние. Режим работы устройства устанавливается подачей сигнала на вход 32 блока управления, устанавлидвумя путями. Режим поиска.

Первый импульс тактовой последовательности проходит через элементы И 66 и 62 на выход 35. Элемент И 70 закрыт. Этот же импульс, проходя через элемент 57 задержки, сдвигает содержимое регистра 54 на один разряд. Второй импульс проходит через элементы И 66 и 63 на выход 37 и поступает на нулевой вход триггера 55, устанавливая его в нулевое состояние. После этого происходит сдвиг единицы в третий разряд регистра 54. Третий и последующие импуль-

сы проходят через элемент И 67 на выход 39. Если на входе 31 появился сигнал, означающий, что в поле ссып- ки прочитанной записи содержится нуль, то он передается через злег- мент И 68 и элемент ИПИ 60 на выходы 40 и 41. С выхода 40 импульс поступает на вход генератора 11 и останавливает его, а с выхода 41 он

передается на признаковый выход 52 устройства, Режим включений,

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

того, он проходит через элемент И 70 на выход 36 и через элемент 58 задержки на выход 42, с которого импульс поступает на вх«д записи блока 7 памяти и второй синхронизирующий вход регистра. 3 информации. Второй, третий и последующие импульсы проходят через блок управления аналогично режиму поиска. После чтения из блока памяти записи с

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

триггера 55 в единичное состояние импульс тактовой последовательности будет передаваться через элемент . 57 задержки, сдвигать содержимое регистра 54 на один разряд. Следую7

щий импульс проходит через элементы И 66 и 65 и элемент ИЛИ 60 на выходы 40 и 41, а через элементы И 66 и 65 элемент ИЛИ 61 и элемент 58 задерж- ки - на выход 42.

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

7258

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

задержки, выход первого элемента И соединен с входом первого элемента задержки и с первыми входами чет- вертого, пятого, шестого и седьмого элементов И, вторые входы которых соединены с выходами первого, второго, третьего и четвертого разрядов регистра сдвига соответственно, вы- ход четвертого элемента И соединен

с первым входом восьмого элемента И и с первым выходом блока, выход восьмого элемента И соединен с первым входом второго элемента ИЛИ и с вто- 5 рым выходом блока, выход пятого элемента И соединен с третьим выходом блока и с нулевым входом первого триггера, выход второго элемента ИЛИ через второй элемент задержки соеди- 0 нен с восьмым выходом блока, выход шестого элемента И является четвертым выходом блока, выход седьмого элемента И соединен с вторым входом второго элемента ИЛИ и с первым 5 входом третьего элемента ИЛИ, ход которого является первым и седьмым выходами блока, единичный и нулевой входы второго триггера являются входами включения и поиска 0 блока соответственно, единичный выход второго триггера соединен с вторым входом восьмого элемента И и с первым входом третьего элемента И, нулевой выход второго триггера под- 35 ключен к первому входу девятого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, вход признака поля ссылки блока соединен с вторыми входами третьего и 40 девятого элементов И, выход второго элемента И является пятым выходом блока.

Шкотш

Вшод35 Выход 26 Вы)(одЛ

l iffec в ешшй6лт

Вы)(од59 Папе Папе 5

Пале 5 Вьтд Ю

Выхо Ю

W&iCfn

ВьтдВ Выход22

Вшод21/53

у

п

гт

с хештаблице Айр&с б лештаолице Adosc 7

Фие.З

е.5

3 б

Ключ 3

ООП0110 01101011 I

блок 25

Регистр 27

Выход регистра 27 (базоЬый адрес xew/fJoS- лицы 5А)

5лок 26

00000000: 01101101

Выход 25

Сумматор 26

Выход сумматора 26 {адрес hoda д хеш- таблицу)

Фие.В