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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (SD 4 G 06 F 15/40

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕКИЯМ И ОТКРЫТИЯМ

ПРИ ГНКТ СССР

1 (21 ) 4403 6 76/24- 24 1 (22) 04.04.88 (46) 07.11.89. Вюл. Р 41 (7 1) Киевский политехнический институт (72) В.И.Корнейчук, А.П.Марковский(80),Барвадеш Пандиан (IN), Сон

Ки Ен (КР) и Чандр Пракаш (IN) (53) 681.325 (088.8) (56) Заявка Великобритании Ф 2136612, кл. G 06 F 15/40, 1984.

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

Р 813450, кл. G 06 F 15/40, 1981.

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

Ф 1399770, кл. G 06 F 15/40, 1987. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ

В ПАМЯТИ (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения и поиска информации, и может быть использовано в цифровых вычислительных и информацион„„SU„„3 52О547

° 2 но-поисковых системах, выполненных на узлах с большой степенью интеграции.

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

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

5 ил.

1520547

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

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

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

Устройство содержит основной накопитель 1, ассоциативный накопитель 2, регистр 3 признака поиска, формирователь 4 сигнала адреса, схему 5 сравнения, первый счетчик 6, мульти" плексор 7, информационные выход 8 и вход 9 устройства, блок 10 управления, второй счетчик 11, Блок 10 управления имеет вход 12 признака переполнения, вход 13 маркер-30 ного разряда, первый вход 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 в виде мик55 ропрограммного узла управления и содержит узел 36 памяти микропрограмм, счетчик 37 адреса, мультиплексор 39 переходов, источник 40 потенциала логической единицы, элемент ИЛИ 41. инвертор 42, преобразователь 43 «ачального адреса, генератор импульсов.

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

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

3 соответствует потенциалу (еднничному илн нулевому) Hà j -м входе-выходе блока 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 управления

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

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

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

30 и 31 формирует сигналы соответственно инициирования ассоциативного поиска в накопителе 2 и маскирования всех входов указанного накопителя 2, 35 кроме маркерного, на который с выхода 25 подается нуль. Таким образом, под действием упомянутых управляющих сигналов в ассоциативном накопителе 2 40 находится первая по порядку свободная ячейка (поскольку поиск производится по критерию нулевого содержания маркерного разряда и при маскировании всех остальных разрядов).

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

25, 27 и 29, по которым соответственно единичный сигнал подается на вход маркерного разряда накопителя 2, производится запись информации с регистра 3 вместе с единицей маркерного разряда в накопитель 2 в ячейку, определяемую результатами ассоциативного поиска на предшествующем такте, т.е. в первую по порядку свободную ячейку (сигнал на выходе 29 указывает на способ адресации). После записи информационного слова блок 10 управле47 ь ния формирует на выходе 32 сигнал конца операции.

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

10 управления фиксируется на счетчике 6, этим же сигналом счетчик,1 устанавливается в нуль. Одновре енно сигналом с выхода 30 блока 10 управления производится ассоциативный опрос накопителя 2 ключевыи словом с регистра 3 единичным значениеи маркерного разряда с выхода 25 блока 10 управления. Если слово с заданной ключевой частью хранится в ассоциативном накопителе 2, то последним формируется сигнал совпадения, который поступает на вход 15 блока 10 управления. По указанному сигналу блок 10 формирует сигналы на входах 28 и 29, которые обеспечивают считывание из накопителя 2 найденного информационного слова. Одновременно блоком 10 выдаются сигналы с выходов 26 и 32, первый из которых обеспечивает коммутацию считанного слова через мультиплексор 7 на выходные шины 8 устройства, а второй является сигналои конца операции.

Если искомое слово не хранится в ассоциативном накопителе 2, то последний не выдает сигнал на вход 14 блока 10 управления, который в этом случае формирует последовательность управляющих сигналов, обеспечивающих поиск в основном накопителе 1 (фиг. 4).

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

1520547

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

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

Работа устройства в режиме исключения информации иэ памяти (фиг. 5) аналогична функционированию в режиме поиСка за тем исключением, что по окончании поиска производится занесение нуля в маркерный разряд ячейки, в котором хранится исключаемое слово.

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

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

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

Фие. 1

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

И л гг

Л га

Л

7I

7/

7d

7У

УР л

УР

1520547

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

Редактор В.Петраш Техред Л.Сердюкова Корректор B.Ïàòàé

Заказ 6760/51 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 101