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

 

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

СООЗ СОВЕТСНИХ

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

РЕСПУБЛИК (19) (li) (5D 4 С 06 F 15 40

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3984963/24-24 (22) 02. 12 ° 85 (46) 07.05.87. Бюл. gг 17 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И. Корнейчук и А.П. Марковский (53) 681. 325 (088.8) (56) Авторское свидетельство СССР 11 813450, кл. G 06 F 15/40, 1978.

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

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

В ПАМЯТИ (57) Изобретение .относится к вычислительной технике. Целью изобретения является расширение функционапьных возможностей за счет обеспечения адресного и ассоциативного доступа и сокращение объема памяти. Устройство содержит блоки 1 памяти, коммутаторы

2 адреса, счетчик 3 адреса, информационный выход 4, схемы 5 сравнения, регистр 6 признака, узел 7 маскирования, элемент И 8, выход 9 признака, 1309041 регистр 10, коммутатор 11, элемент признака, вход 19 задания маски, реИЛИ 12, группу 13 элементов задержки, гистр 20 маски, блок 21 управления, шифратор 14, коммутатор 15, адресный входы 22-25 и выходы 26-30 блока 21 вход 16, адресный выход 17, вход 18 управления. 1 э. п. ф-лы, 2 ил.

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

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

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

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

Устройство содержит блоки 1 памяти, коммутаторы 2 адреса, счетчик 3 адреса, информационный выход 4 устройства, схемы 5 сравнения, регистр

6 признака, узел 7 маскирования, эле- 20 мент И 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,L) представляет собой комбинационную схему, формирующую на своих выходах двоичный код числа (1-1) при отсутствии потенциала на управляющем вхо де и код, идентичный входному при единичном управляющем сигнале. 40

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

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

r-х входах (r l).

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

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

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

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

2 для пропускания кода с выхода коммутатора 15 на адресные входы старших разрядов всех блоков 1. Соответственно на адресные входы каждого из блоков 1 памяти подается одинаковый адрес, идентичный поданному на вход 16.

3 13090

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

В режиме поиска информации признак (аргумент) поиска заносится по входу

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

0 ... 1, с выхода 1-го коммутатора 2 на старшие разряды адресного входа соответствующего ему блока 1 памяти выдается код (1-1). Соответственно просмотр ячеек в каждом 1-м блоке наN чинается с (1-1) — -й ячейки (N — чисL ло ячеек в блоке 1) . По сигналу считы40 вания, снимаемому с выхода 26, с выходов блоков 1 памяти считывается информация, которая сравнивается на схемах 5 сравнения с соответствующими полями регистра 6 признака, причем на каждой схеме 5 сравнения сравнивается

1-е поле регистра 6 и 1-е поле

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

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

3 так, что в следующем такте сравнивается на схемах 5 сравнения 1-е поля регистра 6 признака поиска с 1-м поN лем (1-1) + 1"-го слова.

Ь

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

i-го слова с признаком поиска. В общем случае, если зафиксировано совпадение соответствующих полей d слов (й<Ь), то в d последующих тактах производится сравнение в порядке их адресов слов с признаком поиска.

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

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

его адрес — с выхода 17. Если слово не равно признаку поиска, то сигнал . на выходе 9 не формируется. По истечении времени, определяемого элементами задержки группы 13, сигналом с их выхода устанавливается в ноль разряд регистра 10, выделенный коммутатором 11 на предыдущем такте. Если на.регистре 10 еще окажутся разряды, установленные в единицу, то коммута- 35 тор 11 опять выделит такой разряд с наименьшим номером, и повторится описанная процедура проверки полного слова, в течение которой присутствует единичный потенциал на выходе эле- 40 мента ИЛИ 12, который препятствует выдаче блоком 21 управления сигналов на счетный вход счетчика 3 и сигналов приема кода на регистр 10. По обнулении регистра 10 к счетчику 3 прибав- 5 ляется единица, и процесс поиска про.должается до тех пор, пока не будет сформирован сигнал на выходе устройства. В процессе описанной процедуры находятся все слова, совпадающие в 50 незамаскированных полях с признаком поиска.

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

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

1309041

27, 2Х

Ж Ю

Фиг. g

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

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

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

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

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

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

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

2 ° Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок управления содержит элементы ИЛИ, И, 20

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