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

ел ю

о

01 4i

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

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

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

Устройство содержит основной накопитель 1, ассоциативный накопитель 2, регистр 3 признака поиска, формиро- ватель 4 сигнала адреса, схему 5 сравнения, первый счетчик 6, мульти- плексор 7, информационные выход 8 и вход 9 устройства, блок 10 управления второй счетчик 11.

Блок 10 управления имеет вход 12 признака переполнения, вход 13 маркер ного разряда, первый вход 14 признака сравнения, второй вход 15 признака сравнения, вход 16 записи, вход 17 поиска, вход 18 исключения, вход 19 начала работы, первый выход 20 запи- си, первый выход 21 управляющего сиг- нала, выход 22 счета, выход 23 считывания, второй выход 24 записи, выход 25 записи маркерного, разряда, второй выход 26 управляющего сигнала, вы- ход 27 управления записи, выход 28 управления чтения, выход 29 управления способа адресации, выход 30 управления поиском, выход 31 управления маскированием информации, первый 32 и второй 33 выходы сигналов конца операции.

Формирователь 4 имеет вход 34 и выход 35.

Блок 10 управления может быть вы

полнен, в частности, в виде управляющего автомата с жесткой логикой или в виде микропрограммного узла управления. На фиг. 2 показан вариант построения блока 10 в ввде микропрограммного узла управления и содержит узел 36 памяти микропрограмм, счетчик 37 адреса, мультиплексор 39 переходов, источник 40 потенциала

,

5 0

5

д . Q

0

5

логической единицы, элемент ИЛИ 41. инвертор 42, преобразователь 43 начального адреса, генератор импульсов.

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

Работа устройства может осуществляться в трех режимах: записи информации, поиска-считывания и исключения информации. Алгоритмы функционирования блока 10 управления в указанных трех режимах представлены соответственно на фиг. 3-5. Обозначение U- соответствует потенциалу (единичному или нулевому) на j -м входе ; вь1ходе блока 10 управления (j 20,33).

В режиме записи информационное слово подается на входы 9 устройства. Одновременно на вход 16 блока 10 управления поступает в виде единичного потенциала сигнал команды записи. По сигналу начала работы, подаваемому на вход 19 блока 10 управления, последним формируется единичный сигнал с выхода 20 (фиг. 3), по которому информационное слово записывается на регистр 3 признака поиска. Ключевая часть принятого информационного слова преобразуется формирователем 4 адреса в хеш-адрес.

Одновременно код с выходов регистра 3 подается на информационные входы накопителя 1 и ассоциативного накопителя 2. По сигналу с выхода 21 блока 10 управления счетчик 11 обнуляется и хеш-адрес с выхода 35 формирователя 4 фиксируется на первом счетчике 6, с разрядных выходов которого он поступает на адресные входы накопителя 1. По сигналу с выхода 23 блока 10 управления реализуется считывание слова из основного накопителя 1. Если значение маркерного разряда считываемого слова равно нулю, то ячейка, к которой производится обращение, является свободной, в противном случае (если значение маркерного разряда равно единице)- занятой. Потенциал маркерного разряда считанного из накопителя 1 слова поступает на вход 13 блока 10 управления. Если ячейка, соответствующая сформированному по коду ключевой части записываемого слова хеш-адресу, свободна, то блок .10 управления формирует единичные сигналы на вьосодах 24 и 25, причем последний из упомянутых сигналов подается на информацион- ный вход маркерного разряда. Сигналом с выхода 24 блока 10 управления

s

код с регистра 3 вместе с единице маркерного разряда записывается в ячейку основного накопителя 1, адрес которой определяется кодом на счетчике 6. Блок 10 управления выдает на выходе 32 сигнал конца операции.

Если ячейка, адрес которой зафиксирован на счетчике 6, окажется занятой предшествующими записями, то блоком 10 управления формируется сигнал на выходе 22, по которому код на сч1 тчиках 6 и 11 увеличивается на единицу, и в следующем такте сигналом с

15205476

НИН формирует на.выходе 32 сигнал конца операции.

В режиме поиска-считываМия ключевое слово поступает на входы 9 устройства. Одновременно на вход 17 блока 10 управления поступает в виде единичного потенциала сигнал команды поиска. По сигналу начала работы, подаваемому на вход 19 блока 10 управления, формируется единичный сигнал на его выходе 20. Указанным сигналом осуществляется запись поступившего на входы 9 ключевого слова в регистр 3

10

выхода 23 блока 10 производится считы-15 (фиг. 4). Зафиксированное в регист25

30

вание ячейки, адрес которой на едцни- цу превышает код, сформированный на выходах 35 формирователя 4. Если указанная ячейка свободна, то по описан- .ному выше способу производится запись 20 ее информационного слова, в противном случае вновь увеличивается на единицу содержимое счетчиков 6 и 11 и описанный цикл повторяется.

Если за k циклов не найдена свободная ячейка для записи поступившего информационного слова, при увеличении содержимого счетчиков 6 и 11 на k-м цикле счетчиком 11 формируется сигнал переполнения, который поступает на вход 12 блока 10 управления, по которому последний на своих выходах 30 и 31 формирует сигналы соответственно инициирования ассоциативного поиска в накопителе 2 и маскирования всех входов указанного накопителя 2, кроме маркерного, на который с выхода 25 подается нуль. Таким образом, под действием упомянутых управляющих сигналов в ассоциативном накопителе 2 находится первая по порядку свободная ячейка (поскольку поиск производится по критерию нулевого содержания маркерного разряда и при маскировании всех остальных разрядов).

В следующем такте блоком 10 управления формируются сигналы на выходах 25, 27 и 29, по которым соответственно единичный сигнал подается на вход

35

40

45

ре 3 ключевое слово преобразуется формирователем 4 адреса в хеш-сигнал, который по сигналу с выхода 21 блока 10 управления фиксируется на счетчике 6, этим же сигналом счетчик 11 устанавливается в нуль. Одновре11енно сигналом с выхода 30 блока 10 управления производится ассоциативный опрос накопителя 2 ключевым словом с регистра 3 единичным значением маркерного разряда с выхода 25 блока 10 управления. Если слово с заданной ключевой частью хранится в ассоциативном накопителе 2, то последним формируется сигнал совпадения, который поступает на вход 15 блока 10 управления. По указанному сигналу блок 10 формирует сигналы на входах 28 и 29, которые обеспечивают считывание из накопителя 2 найденного информационного слова. Одновременно блоком 10 выдаются сигналы с выходов 26 и 32, первый из которых обеспечивает коммутацию считанного слова через мультиплексор 7 на выходные шины 8 устройства, а второй является сигналом конца операции. Если искомое слово не хранится в ассоциативном накопителе 2, то последний не выдает сигнал на вход 14 блока 10 управления, который в этом случае формирует последовательность управляющих сигналов, обеспечивающих поиск в основном накопителе 1 (фиг. 4). Цикл поиска начинается выдачей бломаркерного разряда накопителя 2, про- 50 ° управления сигнала считывания изводится запись информации с регист- информации из накопителя 1, выдав ае- ра 3 вместе с единицей маркерного раз- мого по выходу 23. Если маркерный разряда в накопитель 2 в ячейку, опреде- РЯД считанного слова равен нулю, со- ляемую результатами ассоциативного поиска на предшествующем такте, т.е. в первую по порядку свободную ячейку

55

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

(сигнал на выходе 29 указывает на способ адресации). После записи информационного слова блок 10 управлере 3 ключевое слово преобразуется формирователем 4 адреса в хеш-сигнал, который по сигналу с выхода 21 блока 10 управления фиксируется на счетчике 6, этим же сигналом счетчик 11 устанавливается в нуль. Одновре11енно сигналом с выхода 30 блока 10 управления производится ассоциативный опрос накопителя 2 ключевым словом с регистра 3 единичным значением маркерного разряда с выхода 25 блока 10 управления. Если слово с заданной ключевой частью хранится в ассоциативном накопителе 2, то последним формируется сигнал совпадения, который поступает на вход 15 блока 10 управления. По указанному сигналу блок 10 формирует сигналы на входах 28 и 29, которые обеспечивают считывание из накопителя 2 найденного информационного слова. Одновременно блоком 10 выдаются сигналы с выходов 26 и 32, первый из которых обеспечивает коммутацию считанного слова через мультиплексор 7 на выходные шины 8 устройства, а второй является сигналом конца операции. Если искомое слово не хранится в ассоциативном накопителе 2, то последний не выдает сигнал на вход 14 блока 10 управления, который в этом случае формирует последовательность управляющих сигналов, обеспечивающих поиск в основном накопителе 1 (фиг. 4) Цикл поиска начинается выдачей управления сигнала считывания информации из накопителя 1, выдав ае- мого по выходу 23. Если маркерный разРЯД считанного слова равен нулю, со-

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

7

Если маркернь разряд считанного с.пова равен единице, то схемой 5 сравниваются ключевые части считанного из накопителя I слова и ключевого . слова, хранящегося на регистре 3. Если коды на входах схемы 5 совпадают, то она формирует единичный сигнал, поступающий на вход 14 блока 10 управления.. В случае наличия указанного сигнала блок 10 выдает сигналы на выходах 23 и 32, первый из которых обеспечивает повторное считывание найденного слова из накопителя 1 и коммутацию его (при нулевом сигнале на выходе 26) через мультиплексор 7 на выходные шины устройства, а второй - является сигналом окончания поиска. Если схема 5 выдает на вход 14 нулевой сигнал, то блок 10 управления формирует на своем выходе 22 сигнал увеличения на единицу содержимого счетчиков 6 и 11 и описанный выше цикл повторяется.

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

Работа устройства в режиме исключения информации из памяти (фиг, 5) аналогична функционированию в режиме поиска за тем исключением, что по окончании поиска производится занесение нуля в маркерный разряд ячейки, в котором хранится исключаемое слово Если исключаемое слово хранится в основном накопителе 1, то после того, как найдено слово по ключу блоком 10 управления, формируется единичный сигнал на выходах 24 и 32 и нулевой на выходе 25. Соответственно, производится запись нуля в маркерный разряд ячейки, адрес которой зафиксирован на счетчике 6,и выдача сигнала конца операции. Если найденное слово, подлежащее исключению, хранится в ассоциативном накопителе 2, то блок 10 управления формирует единичные сигналы на выходах 28, 29, 31 и 32 и нулевой на выходе 25. Указанными сигйала- ми производится запись нуля в маркер ный разряд ячейки накопителя 2, где хранится исключаемое слово, и выдача сигнала конца операции.

.

рмула

изобретения

10

15

25 20

35

40

45

50

55

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

Изобретение относится к вычислительной технике, в частности к устройствам хранения и поиска информации, и может быть использовано в цифровых вычислительных и информационно-поисковых системах, выполненных на узлах с большей степенью интеграции. Целью изобретения является сокращение аппаратных затрат за счет уменьшения необходимого объема ассоциативного накопителя. Устройство для поиска информации в памяти содержит основной накопитель 1, ассоциативный накопитель 2, регистр 3 признака поиска, формирователь 4 сигнала адреса, схему 5 сравнения, первый счетчик 6, мультиплексор 7, информационные выход 8 и вход 9 устройства, блок 10 управления, второй счетчик 11. В данном устройстве запись в ассоциативный накопитель производится только в том случае, если ячейка, соответствующая принятому адресу, и следующая за ней ячейка основного накопителя заняты, что требует существенно меньшего объема ассоциативной памяти. 5 ил.

И

а 17

№

( Начала )

игл, иг

фиг. 5