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

сооз советскииСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 04 С 06 Р 15 ОМИТЕТ СССРЕНИЙ И ОТКРЫТ ГОСУД АРСТВЕННЦИПО ДЕЛАМ ИЗОБ ЗОБРЕТ ЕНИЯ ЬСТВ(71) Киевский политехническтут им. 50-летия Великой Оксоциалистической революции(56) Авторское свидетельствУ 813450, кл. С 06 Г 15/40,Авторское свидетельствоУ 809206, кл. С 06 Р 15/40,(54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНфОРИАЦИИВ ПАМЯТИ(57) Изобретение относитсятельной технике. Целью иэоявляется расширение функционвозможностей за счет обеспресного и ассоциативного дсокращение объема памяти.содержит блоки 1 памяти, к2 адреса, счетчик 3 адресационный выход 4, схемы 5 срегистр 6 признака, узел 7ния, элемент И 8, выход 9 к вычибретени иальных яб ь арковский ССС978СР979 ОПИСАНИЕ ечения адоступа и Устройство оммутаторыинформаравнения, маскирова признака,35 Блок 7 маскирования представляетсобой комбинационную схему, каждыйразряд которой формирует на своемпервом выходе ноль в случае, еслина его первый вход подан ноль, а навторой - единица, а на втором выходе Изобретение относится к вычислительной технике, в частности к устройствам хранения и поиска информации, и может быть использовано в цифровых вычислительных системах для реализации доступа к информации как по ее адресу, так и по произвольной части ее содержимого.Цель изобретения - расширение функциональных возможностей за счет 10 обеспечения адресного и ассоциативного доступа и сокращение объема памяти.На фиг. 1 представлена схема устройства; на фиг, 2 - схема блока уп- равления. 15Устройство содержит блоки 1 памяти, коммутаторы 2 адреса, счетчик 3 адреса, информационный выход 4 устройства, схемы 5 сравнения, регистр 6 признака, узел 7 маскирования, эле мент И 8, выход 9 узла признака и устройства, регистр 10, коммутатор 11, элемент ИЛИ 12, группу 13 элементов задержки, шифратор 14, коммутатор 15, адресный вход 16 устройства, адресный выход 17 устройства, вход 18 признака устройства, вход 19 задания маски устройства, регистр 20 маски, блок 21 управления, входы 22-25 блока 21, выходы 26-30 блока 21, 30 генератор 31 тактовых импульсов, элемент 32 задержки, элементы И 33 и 34, элементы ИЛИ 35 и 36 и элемент НЕ 37.Каждый из коммутаторов 2(1=1,1 ) представляет собой комбинационную схему, Формирующую на своих выходах двоичный код числа (1-1) при отсутствии потенциала на управляющем входе и код, идентичный входному при единичном управляющем сигнале. 40 2выходной сигнал представляет собой конъюнкцию входных сигналов.Коммутатор 11 представляет собой комбинационную схему с одинаковым числом входом и выходом, причем сигнал на 1-м его выходе Формируется в случае наличия единицы на 1-м входе и отсутствии единичных сигналом на г-х входах (г).Устройство может быть реализовано в виде большой интегральной схемы (БИС) с доступом к памяти как по адресу, так и по содержанию. Другим вариантом выполнения устройства является реализация его на микросхемах малой и средней степени интеграции.Устройство работает следующим образом.Информационные слова, хранящиеся в устройстве, разбиты на Ь частей, записанных в одноименных ячейках 1. блоков 1 памяти.В режиме адресного чтения (записи) соответствующий адрес подается на адресный вход 16, а управляющий сиг-. нал адресного обращения подается на вход 22 устройства. На выходе ком" мутатора 15 под действием единичного управляющего сигнала с выхода 30 блока 21 формируется код, идентичный старшим разрядам кода адреса, подава" емого на входы 16, который поступает на информационные входы всех коммутаторов 2; младшие разряды кода адреса, подаваемого на вход 16, заносится на счетчик 3 адреса и поступают на адресные входы младших разрядов всех блоков 1 памяти, блок 21 управления на своем выходе 27 формирует единичный сигнал, открывающий коммутаторы 2 для пропускания кода с выхода коммутатора 15 на адресные входы старших разрядов всех блоков 1. Соответственно на адресные входы каждого из блоков 1 памяти подается одинаковый адрес, идентичный поданному на вход 16.3 13090 По сигналу, снимаемому с выхода 26 блока 21 управления, содержимое соответствующих одноименных ячеек всех блоков 1 памяти считывается на инфор- мационный выход 4 устройства (или за писывается с выхода 4 в. соответствующие ячейки блоков 1),В режиме поиска информации признак (аргумент) поиска заносится по входу 18 в регистр 6 признака, а поле поиска задается записью по входу 19 единиц в регистр 20 маски (остальные разряды которого обнулены). В случае если полем опроса выступает все слово, все разряды регистра 20 устанавливаются в единицу. На младшие разряды входа 16 подаются сигналы нулевого уровня, а управляющий сигнал ассоциативного поиска подается на вход 23 устройства. Соответственно все разряды счетчика 3 обнуляются, а с выхода 27 блока 2 1 управления снимается нулевой потенциал. При этом на младшие разряды адресных входов всех бло ков 1 памяти подается код со счетчика 3, а коммутаторы 2 закрыты, так что с выхода первого коммутатора 2 на старшие разряды адресного входа первого блока 1 выдается код 00О, 30 с выхода второго коммутатора 2 на соответствующие входы блока 1 - код 01, с выхода 1-го коммутатора 2 на старшие разряды адресного входа соответствующего ему блока 1 памяти выдается код (1-1). Соответственно просмотр ячеек в каждом 1-м блоке наМчинается с (1-1) - -й ячейки (М - число ячеек в блоке 1). По сигналу считы 40 вания, снимаемому с выхода 26, с выходов блоков 1 памяти считывается информация, которая сравнивается на схемах 5 сравнения с соответствующими полями регистра 6 признака, причем накаждой схеме 5 сравнения сравнивается 1-е поле регистра 6 и 1-е полеМ(1-1) - -го слова хранимого в блоЬуках 1. Результат сравнения формирует ся на выходе схем 5 в виде единицы при совпадении и нуля при несовпаде-. нии, Сигналы с выходов схем 5 сравнения поступают на входы узла 7 маскирования, который селектирует указанные сигналы так, что сигналы на этой группе выходов узла 7 формируются в случае, если соответствующий результат сравнения равен единицы или раз 41 4ряд маскируется, а сигналы на второй группе выходов узла 7 формируются в том случае, если единичный результат сравнения не маскируется в соответствующем поле. Сигналы с выходов второй группы узла 7 фиксируются на регистре 10 по сигналу, снимаемому с выхода 28 блока 21, и подаются на входы элемента ИЛИ 12.Если во всех разрядах регистра 10 зафиксируются нули (соответствует тому, что ни одно из незамаскированных полей сравниваемых слов не совпадает своим соответствующим полем с соответствующим полем признака опроса), то на выходе элемента ИЛИ 12 формируется нулевой потенциал, разрешающий выдачу импульса с выхода 20 блока 2 1 управления на счетный вход счетчика 3 так, что в следующем такте сравнивается на схемах 5 сравнения 1-е поля регистра 6 признака поиска с 1-м поМлем (1-1) + 1"-го слова.ЬЕсли же хотя бы в одном из разрядов регистра 10 будет зафиксирована единица (соответствует совпадению поля одного из сравниваемых в текущем такте слов с соответствующим полем признака поиска), то на выходе элемента ИЛИ 12 формируется единичный сигнал, запрещающий выдачу сигнала на счетный вход счетчика 3. Если, например, в текущем такте совпали с соответствующими полями признака поиска поля 1-го и 1-го слов (161,М), ) Б ),Ы)и х, то в последующих двух тактах работы устройства производится сначала сравнение всего 1-го слова с признаком поиска, а затем всего х-го слова с признаком поиска. В об" щем случае, если зафиксировано совпадение соответствующих полей Й слов (йЬ), то в й последующих тактах производится сравнение в порядке их адресов слов с признаком поиска. Указанные операции проверки полных слов., отдельные поля которых совпали в текущем такте с соответствующими полями признака поиска, осуществляются следующим образом. На выходе коммутатора 11 формируется сигнал на выходе, соответствующем полю и на котором выявлено совпадение (если таких полей несколько, то сначала сигнал формируется на выходе, номер которого, совпадает с номером соответствующего поля меньше), с выхода шифратора 14снимается номер соответствующего поля,который через коммутатор 15 поступаетна информационные входы всех коммута-торов 2. Одновременно блок 21 формирует сигнал на выходе 27, открывающий 5коммутаторы 2 так, что на адресныевходы всех блоков 1 подаются одинаковые адреса, равные адресу слова, полекоторого совпало с соответствующимполем признака поиска. По сигналу 10считывания, снимаемому с выхода 26блока 21 управления, указанное слово полностью считывается из блоков 1и сравнивается на схемах 5 с признаком опроса, Если выявится совпадениенезамаскированных полей слова с признаком поиска, то на всех выходахвторой группы узла 7 маскирования будут сформированы сигналы единичногопотенциала, которые, поступая на открытый сигналом с элемента ИЛИ 12 элемент И 8, сформируют сигнал на выходе 9, свидетельствующий о том, чтоискомое слово найдено;.само слово вэтот момент снимается с выхода 4, аего адрес - с выхода 17. Если словоне равно признаку поиска, то сигнална выходе 9 не формируется. По истечении времени, определяемого элементами задержки группы 13, сигналом сих выхсда устанавливается в ноль разряд регистра 10, выделенный коммутатором 11 на предыдущем такте. Еслина регистре 10 еще окажутся разряды,установленные в единицу, то коммутатор 11 опять выделит такой разряд снаименьшим номером, и повторится описанная процедура проверки полногослова, в течение которой присутствует единичный потенциал на выходе элемента ИЛИ 12, который препятствуетвыдаче блоком 21 управления сигналовна счетный вход счетчика 3 и сигналовприема кода на регистр 10. По обнулении регистра 10 к счетчику 3 прибавляется единица, и процесс поиска про.должается до тех пор, пока не будетсформирован сигнал на выходе устройства. В процессе описанной процедурынаходятся все слова, совпадающие в 50незамаскированных полях с признакомпоиска. Формула изобретения551. Устройство для поиска информации в памяти, содержащее блок памяти, регистр признака, регистр, схему сравнения, блок управления, первый выход которого подключен к входу разрешения приема. регистра, вход регистра признака является входом признакаустройства, о т л и ч а ю.щ е е с ятем, что, с целью расширения функциональных воэможностей за счет обеспечения адресного и ассоциативного доступа и сокращения объема памяти, в него введены, 1-1 блоков памяти, 1-1 схем сравнения, 1 коммутаторов адреса, узел маскирования, два коммутатора, регистр маски, группа элементовзадержки, шифратор, счетчик адреса,элемент И и элемент ИЛИ, входы которого и входы первого коммутатора соединены соответственно с выходами разрядов регистра, старшие разряды адресного входа каждого блока памяти подключены к выходу соответствующегокоммутатора адреса, младшие разрядыадресного входа каждого блока памятисоединены с выходами разрядов счетчика адреса, выход каждого блока памяти соединен с первым входом соответствующей схемы сравнения и с информационным выходом устройства, вторыевходы схем сравнения соединены соответственно с выходами разрядов регистра признака, выходы схем сравнения подключены соответственно к входампервои группы узла маскирования, входы второй группы которого соединенысоответственно с выходами разрядоврегистра маски, вход которого является входом задания маски устройства, выходы первой группы узла маскирования и выход элемента ИЛИ соединены соответственно с входами элемента И, выход которого является выходом признака обнаружения информации устройства, выходы второй группы узла маскирования соединены соответственно с информационными входами разрядов регистра, выходы первого коммутатора соединены соответственно с входами шифратора и через элементы задержки группы - с установочными входами разрядов регистра, выход шифратора подключен к первому информационному входу второго коммутатора, второй информационный вхоц которого соединен со старшими разрядами адресного входа устройства, младшие разряды которого подключены к информационному входу счетчика адреса, выход второго коммутатора подключен к информационным входам коммутаторов адреса, выходыразрядов счетчика и выход второго коммутатора соединены с адресным выходом1309041 2) г.8 Составитель А, ЖеТехред М.Ходанич о Воро Редакт емчи орректо ж 673 венно ретен 5, Ра Подписямитета СССРоткрытийя наб., д. 4/5 го к ий и ушс устройства, выход переполнения счетчика адреса соединен с выходом сигнала окончания работы устройства, первый, второй, третий и четвертый входы блока управления соединены соответственно с входом адресного обращения, с входом ассоциативного обращения устройства, с выходом элементаИЛИ и с выходом переполнения счетчика адреса, с второго по пятый выходы 10блока управления подключены соответственно к управляющим. входам коммутаторов адреса, к входай считывания блоков памяти, к счетному входу счетчика адреса и к управляющему входу вто эрого коммутатора. 2Устройство по п,1, о т л и - ч а ю щ е е с я тем, что блок управления содержит элементы ИЛИ, И, 20 аказ 1800/42 Ти ВНИИПИ Государ по делам из 113035, Москва, ЖПроизводственно-полиграфическое п НЕ, задержки и генератор такТовых импульсов, выход которого соединен с первыми входами первого элемента И, первого элемента ИЛИ и через элемент задержки с первым входом второго элемента И, первый вход блока подключенк первому входу второго элемента ИЛИ, к второму входу первого элемента ИЛИ и к пятому выходу блока, запускающие входы генератора тактовых импульсов соединены соответственно с вторым и четвертым входами блока, третий вход блока подключен к второму входу второго элемента ИЛИ и через элемент НЕ к вторым входам первого и второго элементов И, выходы первого элемента И, второго элемента ИЛИ, первого элемента ИЛИ, второго элемента И являются соответственно с первого по четвертый выходами блока. ятие, г. Ужгород, ул. Проектная, 4