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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ 152 О СПУБЛ 04 С 06 Р 1 КОМИТЕТ ОТКР 11 ТИ ГОСУД АРСТВЕНН ПО ИЗОБРЕТЕНИЯ ПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ ВИДЕТЕЛЬСТВ ЭТОРСНО 403676/24-24.04.887.11.89.невский и(72) В.И.Корнейчук, А.П.Марковский(811),Барвадеш Пандиан (1 М), Сон Ки Ен (КР) и Чандр Пракаш (13) (53) 681,325 (088.8)(56) Заявка Великобритании Ф 213 ЬЬ 12, кл. С 06 Р 15/40, 1984.Авторское свидетельство СССР В 813450, кл. С Об Р 15/40, 1981.Авторское свидетельство СССР Ф 1399770, кл. С 06 Р 15/40, 1987. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ В ПАМЯТИ(57) Изобретение относится к вычислительной технике, в частности к устройствам хранения и поиска информации, и может быть использовано в цифровых вычислительных и информационФ но-поисковых системах, выполненных на узлах с большой степенью интеграции. Целью изобретения является сокращение аппаратных затрат за счет уменьшения необходимого объема ассоциативного накопителя. Устройство для поиска информации в памяти содержит основной накопитель 1, ассоциативный накопитель 2, регистр 3 признака поиска, формирователь 4 сигнала адреса, схему 5 сравнения, первый счетчик 6, мультиплексор 7, информационные выход 8 и вход 9 устройства, блок 10 управления, второй счетчик 11. В данном устройстве запись в ассоциативный накопитель производится только в й том случае, если ячейка, соответствуЖ ющая принятому адресу, и следующая за ней ячейка основного накопителя заняты, что требует существенно мень- С шего объема ассоциативной памяти. 5 ил.феейИзобретение относится к вычислительной технике, в частности к устройствам хранения и поиска информацйи, и может быть использовано в циф"ровых вычислительных и информацион -но-поисковых системах, выполненныхна узлах с большой степенью интеграции.Целью изобретения является сокращение аппаратных затрат за счет уменьшения необходимого объема ассоциативного накопителя.На фиг. 1 представлена структурнаясхема устройства для поиска информацин в памяти; на Фиг. 2 - схема блокауправления; на фиг. 3 - 5. - алгоритмыработы устройства соответственно в режимах записи, поиска и исключения информации. 20Устройство содержит основной накопитель 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 в виде мик 55ропрограммного узла управления и содержит узел 36 памяти микропрограмм,счетчик 37 адреса, мультиплексор 39переходов, источник 40 потенциала логической единицы, элемент ИЛИ 41, инвертор 42, преобразователь 43 начального адреса, генератор импульсов,Устройство работает следующим образом.Работа устройства может осуществляться в трех режимах: записи информации, поиска-считывания и исключения информации. Алгоритмы функционирования блока 1 О управления в указанных трех режимах представлены соответственно на фиг. 3 - 5, Обозначение о3 соответствует потенциалу (единичному илн нулевому) на-м входе-выходе блока 10 управления ( = 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выходе 32 сигнал конца операции,Если ячейка, адрес которой зафиксирован на счетчике 6, окажется занятой предшествующими записями, то 10блоком 10 управления Формируется сигнал на выходе 22, по которому код насчетчиках б и 11 увеличивается на единицу, и в следующем такте сигналом свыхода 23 блока 10 производится считы.15вание ячейки, адрес которой на единицу превышает код, сформированный навыходах 35 Формирователя 4. Если указанная ячейка свободна, то по описан.ному выше способу производится запись 20ее информационного слова, в противномслучае вновь увеличивается на единицу содержимое счетчиков б и 11 и описанный цикл повторяется.Если за 1 с циклов не найдена свободная ячейка для записи поступившегоинформационного слова, при увеличениисодержимого счетчиков 6 и 11 на К-мцикле счетчиком 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 блока 1 О управления, формируется единичный сигнал наего выходе 20. Указанным сигналом осуществляется запись поступившего навходы 9 ключевого слова в регистр 3(фиг. 4). Зафиксированное в регистре 3 ключевое слово преобразутсяформирователем 4 адреса в хеш-сигнал,который по сигналу с выхода 21 блока10 управления фиксируется на счетчике 6, этим же сигналом счетчик 11устанавливается в нуль. Одновре;бренносигналом с выхода 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, Если маркерный разряд считанного слова равен нулю, соответственно нулевой сигнал поступаетна вход 13 блока 10 управления, топоследний выдает с выхода 33 сигналокончания поиска, свидетельствующийоб отсутствии слова с заданной ключевой частью в памяти.Если маркерный разряд считанногослова равен единице, то схемой 5 сравниваются ключевые части считанногойз накопителя 1 слова и ключевогослова, хранящегося на регистре 3. Ес 5ли коды на входах схемы 5 совпадают,то она формирует единичный сигнал,поступающий на вход 14 блока 10 управления, В случае наличия указанного сигнала блок 10 выдает сигналы навыходах 23 и 32, первый из которыхобеспечивает повторное считываниенайденного слова из накопителя 1 икоммутацию его (при нулевом сигналена выходе 26) через мультиплексор 7на выходные шины устройства, а второй - является сигналом окончания поиска. Если схема 5 выдает на вход 14нулевой сигнал, то блок 1 О управления .формирует на своем выходе 22 сигналувеличения на единицу содержимогосчетчиков б и 11 и описанный выше циклповторяется.После выполнения циклов поиска . 25счетчик 11 формирует сигнал переполнения, который поступает на вход 12 блока 10 управления и инициирует последним выдачу на выход 33 устройства сигнала окончания операции поиска, сигна лизирующего об отсутствии слова с заданной ключевой частью в памяти,Работа устройства в режиме исключения информации иэ памяти (фиг, 5) аналогична Функционированию в режиме поиСка за тем исключением, что по окончании поиска производится занесение нуля в маркерный разряд ячейки, в котором хранится исключаемое слово,40 Если исключаемое слово хранится в основном накопителе 1, то после того, как найдено слово по ключу блоком 10 управления, Формируется единичный сигнал на выходах 24 и 32 и нулевой на вы ходе 25. Соответственно, производится запись нуля в маркерный разряд ячейки, адрес которой зафиксирован на счетчике б,и выдача сигнала конца операции. Если найденное слово, подлежащее исключению, хранится в ассоциативном накопителе 2, то блок 10 управления формирует единичные сигналы на выходах 28, 29, 31 и 32 и нулевой на выходе 25. Укаэанными сигналами производится запись нуля в маркерный разряд ячейки накопителя 2, где хранится исключаемое слово, и выдача сигнала конца операции. формула изобретения Устройство для поиска информации в памяти, содержащее основной накопитель, регистр признака поиска, формирователь сигнала адреса, схему сравнения, ассоциативный накопитель, блок управления, причем информационный вход устройства соединен с информационным входом регистра признака поиска, выход которого соединен с входом формирователя сигнала адреса, информационными входами ассоциативного и основного накопителей и первым входом схемы сравнения, второй вход которой соединен с выходом данных основного накопителя, выход равенства схемы сравнения соединен с первым входом признака сравнения блока управления, второй вход признака сравнения которого соединен с выходом совпадения ассоциативного накопителя, входы записи, чтения, способа адресации, поиска и маскирования информации которого соединены соответственно с одноименными управляющими выходами блока управления, первый и второй выходы сигнала конца операции которого соединены соответственно с первым и вторым одноименными выхОдами устройства, входы записи, поиска, исключения и начала работы которого соединены соответст- венно с одноименными входами блока управления, первый выход записи которого соединен с входом записи регистра признака поиска, второй выход записи и выход считывания блока управления соединены соответственно с одноименными входами основного накопителя, маркерный разряд выхода данных которого соединен с входом маркерного разряда блока управления, выход записи маркерного разряда которого соединен с одноименными входами основного и ассоциативного накопителей, о т л и ч аю щ е е с я тем, что, с целью сокращения аппаратных затрат эа счет уменьшения необходимого объема ассоциативного накопителя, в него введены первый и второй счетчики и мультиплексор, причем выход формирователя сигнала адреса соединен с установочным входом первого счетчика, вход записи которого соединен с входом сброса в "0" второго счетчика и с первым выходом управляющего сигнала блока управления, выход счета которого соединен со счетными входами первого и второГо счетчиков, выход данных первого счетчика соединен с адресными входами основногонакопителя, информационный выход которого и информационный выход ассоциа"тивного накопителя соединены соответственно с первым и вторым входамимультиплексора, выход которого является информационным выходом устройства, вход переключения мультиплексорасоединен с вторым выходом управляющего сигнала блока управления, входпризнака переполнения которого соединен с выходом переполнения второгосчетчика.Пат Редакт роизводственно-издательский комбинат "Патент", г. Ужгород, ул,ина, 101 Заказ 6760/51 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., д, 4/5