Ассоциативное запоминающее устройство

 

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

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

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

РЕСПУБЛИК (51) 4 G 11 С 15/00

OllHGAHHE HSOEPETEHHFI

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ. (21) 4132921/24-24 (22) 09.07.86 (46) 07.10.88. Бюл. У 37 (71) Ленинградский электротехнический институт им. В.И.Ульянова (Ленина) (72) В.П.Емелин и А.Ю.Логачев (53) 681.327 (088.8) (56) Однородные микроэлектройные процессоры./Под ред. И.В.Прангишвили. — M.: Советское радио, 1973, . с. 11-35.

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

N- 1278976, кл. С 11 С 15/00, 1985. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к области

ÄÄSUÄÄ 1429169 вычислительной техники, в частности к запоминающим устройствам, и может быть использовано в процессорах с асинхронным управлением вычислениями для поиска готовых к выполнению команд, а также в информационно-поисковых системах, где необходимо производить ассоциативный поиск информации одновременно по произвольному количеству признаков. Цель изобретения — повышение информационной емкос" ти устройства за счет обеспечения возможности наращивания элементов структуры. Устройство содержит дешифратор 1, блоки 2 ассоциативных признаков, шифратор 3, основной блок 4 элементов И, блок 5 оперативной памяти, элементы ИЛИ 15 и дополнительные блоки t6 элементов И. 4 ил.

1429169

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

Цель изобретения — повышение информационной емкости устройства.

На фиг. 1 изображена структурная схема ассоциативного запоминающего

1 устройства; на фиг. 2 — структурная схема блока ассоциативных признаков; на фиг. 3 — структурная схема блока управления; на фиг. 4 — структурная схема формирователя сигналов состояния.

Ассоциативное запоминающее устройство (АЗУ) содержит (фиг, 1) дешифра- 20 тор 1, основной 2, и дополнительные

2, — 2„ блоки ассоциативных признаков (где К вЂ” целое число), шифратор 3, основной блок 4 элементов И, блок 5 оперативной памяти, шину 6 управления, объединяющую вход синхронизации, тактовый вход и первый установочный вход устройства, и адресную шину 7, объединяющую адресные входы и выходы устройства. Устройство имеет информа30 ционные входы 8 и выходы 9.

Каждый блок 2 ассоциативных признаков содержит (фиг. 2) блок 10 управления, ассоциативные ячейки 11 .памяти, формирователи 12 сигналов состояния, приоритетнь1й шифратор 13 35 и элемент И t4. Устройство также содержит К+1 элементов ИЛИ 15 и К+1 дополнительных блоков 16 элементов И (на фиг. 1 и 2 указанные элементы изображены условно входящими в блоки

2, так как с конструктивной точки зрения их целесообразно включить в эти блоки). Ячейки 11 имеют вход 17: опроса-записи, вход 18 разрешения записи и выход 19 совпадения. На фиг. 2 обозначена адресная шина 20 блока 2. Блок 2 имеет синхровход 21, тактовый вход 22, первый установочный вход 23, вход 24 режима, управляющий вход 25 и адресный вход 26. 50

Блок 10 имеет выход 27, входы 28 и выходы 29 и 30.

Блок 10 управления (фиг. 3) содержит элементы И 31-33, дешифратор 34, элементы И 35-37 и элементы ИЛИ 38, 55

На фиг. 1 и 2 обозначены входы 39 и

40, выход 41, входы 42-44, выходы 45 и 46, входы 47 и 48 блока 2. Формиро= ватель 12 имеет входы 49-52, выход

53, вход 54, выход 55, вход 56, выход 57 и вход 58.

Каждый из формирователей 12 (фиг. 4) содержит триггер 59, элемент И 60, элемент ИЛИ 61, элемент

И 62, триггеры 63 и 64, элементы И

65 и 66 и элемент ИЛИ 67.

В предлагаемом устройстве структура составной ячейки содержит следующие функциональные поля: ассоциативные признаки (их может быть произвольное число А, где 1 А М, M — число ячеек 11 в устройстве); признаки состояния ячейки (для каждого из ассоциативных признаков существуют признак занятости, признак готовности и признак наличия связи ассоциативных признаков); адрес основной информации, формируемый на адресных выходах блока

2; основная информация, которая находится в блоке 5.

Цепочки признаков в составных ячейках формируются путем установки для каждого из ассоциативных признаков определенного разряда либо в "0", юю и либо в 1 . Единичное состояние разряда свидетельствует о том, что соответствующий ему ассоциативный-признак является первым в цепочке, а обратное утверждение соответствует нулевому состоянию этого разряда.

Цепочки признаков формируются в процессе записи информации в АЗУ. !

Основная информация, соответствующая некоторой составной ячейке

АЗУ: может быть прочитана только после того, как все из ассоциативных признаков, соответствующие данной ячейке, совпадут с входными признаками опроса хотя бы один раз. Признаки опроса последовательно подаются на соответствующий вход АЗУ. В результате успешного поиска считываемая информация автоматически формируется на выходе блока 5, при этом на выходе АЗУ формируется сигнал, свидетельствующий о наличии считываемой инфомации.

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

Установка начального состояния

АЗУ осуществляется путем подачи единичного сигнала на второй установоч- . ный вход АЗУ. При этом триггеры 59 всех формирователей 12 установлены в нулевое состояние. Это свидетельствуе" о том, что все ячейки АЗУ пусты и н. находятся в состоянии готовности;

9169 ется в блок 5.

20 з 142

Кроме того,, триггеры 63 установлены в единичное состояние. Это свидетельствует о том, что каждая ячейка АЗУ в данный момент содержит по одному признаку опроса.

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

22 блока 10 ° Тактирование данных операций осуществляется с помощью элементов И 31-33.

Режим записи.

Количество тактов, необходимое для записи информации в одну составную ячейку АЗУ, равно количеству ассоциативных признаков, объединен ных в цепочку. При записи информации в АЗУ ассоциативный признак, сигнал наличия связи признаков, адрес признака и основная информация подаются на соответствующие входы АЗУ, при этом на входе режима АЗУ должен быть установлен сигнал "Запись", что соответствует нулевому уровню входного сигнала. Вход признака опроса для

АЗУ используется как для запйси ассоциативных признаков в ячейку. 11 так и для приема. опроса при поиске информации, так как два этих режима работы АЗУ считаются взаимоисключающими.

Во время записи ассоциативный признак, сигнал наличия связи признаков и адрес признака меняют свое значение после каждого такта записи, причем признаки, относящиеся к одной составной ячейке,. должны записываться в соседние ячейки 11, т.е. адрес признака должен меняться путем увеличения его на "1". Основная информация изменяет свое значение только после записи последнего признака в цепочке признаков.

Запись информации в АЗУ происходит следующим образом. Адрес признака поступает на шину 7 адреса. В режиме записи выходы блоков 4 и 16 элементов отключены (находятся в третьем состоянии) от шины 7. Далее адрес признака поступает на вход дешифратора 34 блока 10 и на адресный вход блока 5. С помощью дешифратора

34 и элемента И 37 на соответствующем входе 18 разрешения записи формируется сигнал, по которому признак запи" сывается в соответствующую ячейку 11, сигнал наличия связи признаков с помощью элемента И 60 записывается в триггер 63, а триггер 59 устанавливается в единичное состояние, что свидетельствует о том, что ячейка 11 занята. По адресу, подаваемому на адресный вход блока 5, основная инфомация по сигналу Запись" записываРежим поиска.

Ассоциативный поиск по одному из признаков опроса осуществляется за один такт. Для этого код признака опроса подается на входы 17 всех ячеек 11. На вход 21 блока 10 с шины

6 управления подается сигнал, по которому блок 10 формирует сигнал поиска на выходе 27 с помощью элемента И 3 1, подаваемый на входы 54 всех формирователей 12. Для всех признаков, записанных в ячейках 11, совпадающих с входным признаком опроса, появляются сигналы совпадения на соответствующих выходах 19, откуда они поступают на входы 49 формирователей

12. Далее по сигналу на выходе 27 .блока 10 все сигналы совпадения записываются в триггеры 64 формирователей 12, устанавливая их в единичное состояние. Если триггер 64 какогонибудь формирователя 12 находится в единичном состоянии (т.е. признак готов) и данный формирователь соответствует первому признаку в цепочке признаков, то при наличии сигнала на входе 58 формирователя 12 (т.е. все признаки, относящиеся к даннои составной ячейке и имеющие адрес, больший, чем адрес текущего признака, в данном случае первого в цепочке, на40 ходятся в состоянии готовности) данная составная ячейка АЗУ находится в состоянии готовности, о чем свидетельствует единичный сигнал на выходе элемента И 66 формирователя 12 °

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

Режим считывания.

Считывание информации происходит с блока 5, ячейки которого содержат

1429169 искомую информацию. Для этого на адресный- вход блока 5 поступает сфоррованный на шине 7 адреса код адреа первого в цепочке признака, Адрес формируется при наличии высокого уровня сигнала на шине 6 управления (установлен режим чтения), причем младшие разряды формируются на выходе блока 16 элементов И активного блока 2, а старшие разряды — на выборе блока 4 элементов И.

Если на выходах формирователей

12 есть хотя бы один сигнал готовнос ти, то на управляющем выходе АЗУ (управляющий выход шифратора 3) по является сигнал, свидетельствующий о !

;наличии на выходе блока 5 считывае мой информации. По этому сигналу, âíåøíèå по отношению к АЗУ устройстI ва принимают считываемую информацию, после чего формируется сигнал сброса, подаваемый по шине 6 управления на

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

Для сброса готовности составной ячейки на вход 26 блока 10 с выхода блока 16 элементов И поступает адрес первого признака в цепочке признаков.

Далее он поступает на дешифратор 34, который формирует сигнал выборки со ответствующего признака. С помощью элементов И. 35 и 36 и ИЛИ 38 формируется сигнал сброса готовности признака.

Сигналы сброса готовности признаков с выходов 29 блока 10 поступают на соответствующие входы формирователей 12 и переводят триггеры 64 в нулевое состояние, тем самым устанавливая составную ячейку в исходное состояние, Процессы ассоциативного поиска и считывания информации происходят независимо друг от друга и поэтому могут быть совмещены во времени, другими словами, одновременно со считыванием одной ячейки может происходить поиск другой. В режиме записи процессы поиска и считывания блокируются с помощью .элементов И 31 и 33 блока 10..Ф о р мул а и з о б р е т е ни я

Ассоциативное запоминающее устройство, содержащее основной блок ассоI

50 установочному входу устройства, информационные входы дешифратора подключены к адресным входам устройства, управляющий вход дешифратора соединен с входом режима устройства, выходы дешифратора подключены к входам выборки соответствующих блоков ассоциативных признаков, первые входы первого элемента ИЛИ и первого блока элемента И соединены с входом режима устройства, выход i-ro элемента ИЛИ (> = L,Ê) соединен с входом блокировки i-го дополнительного блока ассоциативных признаков, первые входы. циативных признаков и блок оперативной памяти, причем вход записи, вход чтения, адресные входы и информационные входы блока оперативной памяти

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

З> дешифратор, К дополнительных блоков ассоциативных признаков (где К— целое число), К+4 элементов ИЛИ, шифратор, основной блок элементов И и

К+1 дополнительных блоков элементов .

И, причем синхровходы, тактовые вхоЗ5 ды, входы сброса результата поиска, входы записи-чтения, адресные входы, входы признака опроса, входы наличия связи признаков и установочные входы дополнительных блоков ассоциативных ао признаков подключены соответственно к входу синхронизации, тактовому входу, первому установочному входу, адресным входам, признаковому входу, идентифицирующему входу и второму

1429169

j-ro элемента ИЛИ (j 2,K+1) и j-го дополнительного блока элементов И соединены с входом блокировки(— 1) го дополнительного блока ассоциатив5 ных признаков, выход результата поиска первого дополнительного блока ассоциативных признаков подключен к, информационному входу основного блока ассоциативных признаков, выход резуль- 1О тата поиска 1-го дополнительного блока ассоциативных признаков (1 = 2, К) подключен к информационному входу (1 — 1)-го дополнительного блока ас15 социативных признаков, вторые входы элементов ИЛИ и дополнительных блоков элементов И подключены к информационным выходам соответствующих блоков ассоциативных признаков, выходы элементов ИЛИ подключены к выходам шифратора, выход которого соединен с первым входом основного блока элементов И, второй вход которого подключен к входу режима устройства, выходы блоков элементов И являются адресными выходами устройства и сое динены с информационными входами дешифратора. а

1429 l69 иг. 3

Составитель В.Рудаков

Редактор О.Юрковецкая Техред Л.Сердюкова Корректор M.t apnmv

Заказ 5132/48 Тираж 590 Подписное

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

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

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