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

IJ

регистр 10, коммутатор 11, элемент ИЛИ 12, группу 13 элементов задержки, шифратор 1А, коммуд-атор 15, адресный вход 16, адресньй выход 17, вход 18

13

1

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

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

На фиг. 1 представлена схема устройства; на фиг. 2 - схема блока уп- равления.

Устройство содержит блоки 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, генератор 31 тактовых импульсов, элемент 32 задержки, элементы И 33 и 34, элементы ИЛИ 35 и 36 и элемент НЕ 37.

Каждый из коммутаторов 2(,L) представляет собой комбинационную схему, формирующую на своих выходах двоичный код числа (1-1) при отсутствии потенциала на управлякщем вхо- де и код, идентичный входному при единичном управляющем сигнале.

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

IJ

1309041

признака, вход 19 задания маски, регистр 20 маски, блок 21 управления, входы 22-25 и выходы 26-30 блока 21 управления. 1 з.п. ф-лы, 2 ил.

выходной сигнал представляет собой конъюнкцию входных сигналов.

Коммутатор 11 представляет собой комбинационную схему с одинаковым числом входом и выходом, причем сигнал на 1-м его выходе формируется в случае наличия единицы на 1-м входе и отсутствии единичных сигналом на г-х входах ().

Устройство может быть -реализовано в виде большой интегральной схемы (БИС) с доступом к памяти как по адресу. Так и по содержанию. Другим вариантом выполнения устройства является реализация его на микросхемах малой и средней степени интеграции.

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

Информационные слова, хранящиеся в устройстве, разбиты на L частей, . записанных в одноименных ячейках L блоков 1 памяти

В режиме адресного чтения (записи соответствующий адрес подается на адресный вход 16, а управляющий сигнал адресного обращения подается на вход 22 устройства. На выходе коммутатора 15 под действием единичного управляющего сигнала с выхода 30 блока 21 формируется код, идентичный старшим разрядам кода адреса, подаваемого на входы 16, который поступает на информационные входы всех коммутаторов 2; младвше разряды кода адреса, подаваемого на вход 16, заносится на счетчик 3 адреса и поступают на адресные входы младших разрядов всех блоков 1 памяти, блок 21 управления на своем выходе 27 формирует единич- ньш сигнал, открьшающий коммутаторы 2 для пропускания кода с выхода коммутатора 15 на адресные входы старших разрядов всех блоков 1, Соответственно на адресные входы каждого из блоков 1 памяти подается одинаковый адрес, идентичный поданному на вход 16.

По сигналу, снимаемому с выхода 26 блока 21 управления, содержимое соответствующих одноименных ячеек всех блоков 1 памяти считывается на инфор- мациоиньй выход 4 устройства (или за- писывается с выхода 4 в соответствующие ячейки блоков 1).

В режиме поиска информации признак (аргумент) поиска заносится по входу 18 в регистр 6 признака, а поле поиска задается записью по входу 19 единиц в регистр 20 маски (остальные разряды которого обнулены). В случае если полем опроса выступает все ело- во, все разряды регистра 20 устанавливаются в единицу. На младшие разряды входа 16 подаются сигналы нулевого уровня, а управляющий сигнал ассоциативного поиска подается на вход 23 устройства. Соответственно все разряды счетчика 3 обнуляются, а с выхода 27 блока 21 управления снимается нулевой потенциал. При этом на младшие разряды адресных входов всех блоков 1 памяти подается код со счетчика 3, а коммутаторы 2 закрыты, так что с выхода первого коммутатора 2 на старшие разряды адресного входа первого блока 1 выдается код 00 ... О, с выхода второго коммутатора 2 на соответствующие входы блока 1 - код О ... 1, с выхода 1-го коммутатора 2 на старшие разряды адресного входа соответствующего ему блока 1 памяти выдается код (1-1). Соответственно просмотр ячеек в каждом 1-м блоке наNчинается с (1-1) - -и ячейки (N - чисLI

ло ячеек в блоке 1). По сигналу считы вания, снимаемому с выхода 26, с выходов блоков 1 памяти считьшается информация, которая сравнивается на схемах 5 сравнения с соответствующими полями регистра 6 признака, причём Ha каждой схеме 5 сравнения сравнивается 1-е поле регистра 6 и 1-е поле

N

(1-1) т-го слова, хранимого в бло- ij

ках 1. Результат сравнения формируется н а выходе схем 5 в виде единиць при совпадении и нуля при несовпадении. Сигналы с выходов схем 5 сравнения поступают на входы узла 7 маскирования, который селектирует указан- ные сигналы так, что сигналы на этой группе выходов узла 7 формируются в случае, если соответствующий результат сравнения равен единицы или разряд маскируется, а сигналы на второй группе выходов узла 7 формируются в том случае, если единичный результат сравнения не маскируется в соответствующем поле. Сигналы с выходов второй группы узла 7 фиксируются на регистре 10 по сигналу, снимаемому с выхода 28 блока 21, и подаются на входы элемента ИЛИ 12..

Если во всех разрядах регистра 10 зафиксируются нули (соответствует тому, что ни одно из незамаскированных полей сравниваемых слов не совпадает своим соответствующим полем с со- ответствующим полем признака опроса), то на выходе элемента ИЛИ 12 формируется нулевой потенциал, разрешающий выдачу импульса с выхода 20 блока 21 управления на счетный вход счетчика 3 так, что в следующем такте сравнивается на схемах 5 сравнения 1-е поля регистра 6 признака поиска с 1-м полем

a-o-f.,го слова.

Если же хотя бы в одном из разрядов регистра 10 будет зафиксирована единица (соответствует совпадению поля одного из сравниваемых в текущем такте слов с соответствующим полем признака поиска), то на вькоде элемента ИЛИ 12 формируется единич- ньш сигнал, запрещающий выдачу сигнала на счетный вход счетчика 3. Если, например, в текущем такте совпали

с соответствующими полями признака

поиска поля i-ro и j-ro слов (,NJ, jG|1,Njи i j ) , то в последующих двух тактах работы устройства производится сначала сравнение всего j-ro слова с признаком поиска, а затем всего i-ro слова с признаком поиска. В общем случае, если зафиксировано совпадение соответствующих полей d слов (diL), то в d последующих тактах производится сравнение в порядке их адресов слов с признаком поиска.

Указанные операции проверки полных слов, отдельные поля которых совпали в текущем такте с соответствующими полями признака поиска, осуществляются следующим образом. На выходе коммутатора 11 формируется сигнал на выходе, соответствующем полю и на котором выявлено совпадение (если таких полей несколько, то сначала сигнал формируется на выходе, номер которого совпадает с номером соответствующего поля меньше)j с выхода шифратора 14

снимается номер соответствующего поля который через коммутатор 15 поступает на информационные входы всех коммута- торов 2. Одновременно блок 21 формирует сигнал на выходе 27, открывающий коммутаторы 2 так, что на адресные входы всех блоков 1 подаются одинаковые адреса, равные адресу слова, поле которого совпало с соответствующим полем признака поиска. По сигналу считывания, снимаемому с выхода 26 блока 21 управления, указанное слово полностью считывается из блоков 1 и сравнивается на схемах 5 с признаком опроса. Если выявится совпадение незамаскированных полей слова с признаком поиска, то на всех выходах второй группы узла 7 маскирования будут сформированы сигналы единичного потенциала, которые, поступая на от- крытый сигналом с элемента ИЛИ 12 элемент И 8, сформируют сигнал на выходе 9, свидетельствующий о том, что искомое слово найдено;.само слово в этот момент снимается с выхода 4, а его адрес - с выхода 17. Если слово не равно признаку поиска, то сигнал на выходе 9 не формируется. По истечении времени, определяемого элементами задержки группы 13, сигналом с их выхода устанавливается в ноль разряд регистра 10, выделенный коммутатором 1 на предыдущем такте. Если на-регистре 10 еще окажутся разряды, установленные в единицу, то коммутатор 11 опять выделит такой разряд с наименьшим номером, и повторится описанная процедура проверки полного слова, в течение которой присутствует единичный потенциал на выходе элемента ИЛИ 12, который препятствует выдаче блоком 21 управления сигналов на счетный вход счетчика 3 и сигналов приема кода на регистр 10. По обнулении регистра 10 к счетчику 3 прибавляется единица, и процесс поиска про- .должается до тех пор, пока не будет сформирован сигнал на выходе устройства. В процессе описанной процедуры находятся все слова, совпадающие в незамаскированных полях с признаком поиска.

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

1. Устройство для поиска информации в памяти, содержащее блок памяти, регистр признака, регистр, схему сравнения, блок управления, первый

w

15

, j20

090416

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

30 подключены соответственно к входам первой группы узла маскирования, входы второй группы которого соединены соответственно с выходами разрядов регистра маски, вход которого являетJ-5 ся входом задания маски- устройства, выходы первой группы узла маскирования и выход элемента ИЛИ соединены соответственно с входами элемента И, выход которого является выходом признака обнаружения информации устройства, выходы второй группы узла маскирования соединены соответственно с информационьшми входами разрядов регистра, выходы первого коммутатора соединены соответственно с входами шифратора и через элементы задержки группы - с установочными входами разрядов регистра, выход шифратора подключен к первому информационному вхоCQ ДУ второго коммутатора, второй инфор40

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

713090418

устройства, выход переполнения счет- НЕ, задержки и генератор тактовых имрульсов, выход которого соединен с первыми входами первого элемента И, первого элемента ИЛИ и через элемент задержки с первым входом второго элемента И, первьй вход блока подключен к первому входу второго, элемента ИЛИ, к второму входу первого элемента ИЛИ и к пятому выходу блока, запускающие входы генератора тактовых импульсов соединены соответственно с вторым и четвертым входами блока, третий вход блока подключен к второму входу второго элемента ИЛИ и через элемент НЕ

10

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

второго элемента ИЛИ, первого элемен- 2. Устройство по п. 1, о т л и - та ИЛИ, второго элемента И являются

,чающееся тем, что блок уп- соответственно с первого по четвертый равления содержит элементы ИЛИ, И, 20 выходами блока.

Составитель А. Жеренов Редактор А. Ворович Техред М.Ходанич Корректор М. Демчик

Заказ 1800/42 Тираж 673. Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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