Ассоциативное запоминающее устройство Советский патент 1988 года по МПК G11C15/00 

го

;о

О5

со

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

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

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

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

Каждый блок 2 ассоциативных признаков содержит (фиг. 2) блок 10 управления, ассоциативные ячейки 11 .памяти, формирователи 12 сигналов состояния, приоритетный шифратор 13 и элемент И 14. Устройство также содержит К+1 элементов ИЛИ 15 и К+1 дополнительных блоков 16 элементов И (на фиг. 1 и 2 указанные элементы изображены условно входящими в блоки 2, так как с конструктивной точки зрения их целесообразно включить в эти блоки). Ячейки 11 имеют вход 17 опроса-записи, вход 18 разрешения . записи и выход 19 совпадения. На фиг. 2 обозначена адресная шина 20 блока 2. Блок 2 имеет синхровход 21, тактовый вход 22, первый установочный вход 23, вход 24 режима, управляющий вход 25 и адресный вход 26. Блок 10 имеет выход 27, входы 28 и выходы 29 и 30.

Блок 10 управления (фиг. 3) содержит элементы И 31-33, дешифратор 34, элементы И 35-37 и элементы ИЛИ 38. .На фиг. 1 и 2 обозначены входы 39 и 40, выход 41, входы 42-44, выходы 45 и 46, входы 47 и 48 блока 2. Формиро0

5

0

S

0

5

0

5

0

5

ватель 12 имеет входы 49-52, выход 53, вход 54, выход 55, вход 56, выход 57 и вход 58.

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

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

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

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

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

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

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

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

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

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

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

0

5

0

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

Режим поиска.

Ассоциативный поиск по одному из признаков опроса осуществляется за один такт. Для этого код признака опроса подается на входы 17 всех ячеек 11. На вход 21 блока 10 с шины 6 управления подается сигнал, по которому блок 10 формирует сигнал поиска на выходе 27 с помощью элемента И 31, подаваемый на входы 54 всех формирователей 12. Для всех признаков, записанных в ячейках 11, совпадающих с входным признаком опроса, появляются сигналы совпадения на соответствующих выходах 19, откуда они 5 поступают на входы 49 формирователей 12. Далее по сигналу на выходе 27 ..блока 10 все сигналы совпадения записываются в триггеры 64 формирователей 12, устанавливая их в единичное состояние. Если триггер 64 какого- нибудь формирователя 12 находится в единичном состоянии (т.е. признак готов) и данный формирователь соответствует первому признаку в цепочке признаков, то при наличии сигнала на входе 58 формирователя 12 (т.е. все признаки, относящиеся к данной составной ячейке и имеющие адрес, больший, чем адрес текущего признака, в данном случае первого в цепочке, находятся в состоянии готовности) данная составная ячейка АЗУ находится в состоянии готовности, о чем свидетельствует единичный сигнал на выходе элемента И 66 формирователя 12.

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

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

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

0

5

0

5

0

искомую информацию. Для этого на .4дреснЕ.ш вход блока 5 поступает сфор- ь|1ированный на шине 7 адреса код адре- фа первого в цепочке признака. Адрес формируется при наличии высокого уровня сигнала на шине 6 управления (установле режим чтения) , причем младшие разряды формируются на выходе блока 16 элементов И активного лока 2, а старшие разряды - на вы- рсоде блока 4 элементов И. : Если на выходах формирователей 12 есть хотя бы один сигнал готовности, то на управляюш;ем выходе АЗУ I(управляющий выход шифратора 3) по- 1является сигнал, свидетельствующий о Наличии на выходе блока 5 считывае- мой информации. По этому сигналу 1 внешние по отношению к АЗУ устройст- Iва принимают считываемую информацию, I после чего формируется сигнал сброса, подаваемый по шине 6 управления на I вход 23 блока 10. Данный сигнал необходим для того, чтобы сбросить готовность признаков прочитанной ячейки, после чего эта .составная ячейка снбва может участвовать в процессе ассоциативного поиска.

Для сброса готовности составной ячейки на вход 26 блока 10с выхода блока 16, элементов И поступает адрес первого признака в цепочке признаков. Далее он поступает на дешифратор ЗА, который формирует сигнал выборки со- ответствующего признака. С помощью элементов И.35 и 36 и ИЛИ 38 формируется сигнал сброса готовности при- .

Сигналы сброса готовности признаков с выходов 29 блока 10 поступают на соответствующие входы фор1 1ировате- лей 12 и переводят триггеры 64 в нулевое состояние, тем, самым устанавливая составную ячейку в исходное состояние.

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

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

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

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

5

0

5

на, адресные входы основного блока ассоциативных признаков подключены к адресным входам устройства, вход признака опроса, вход наличия связи признаков, вход блокировки и установочный вход основного блока ассоциативных признаков являются соответственно признаковым входом, идентифи- цируюш;им входом, входом режима и вторым установочным входом устройства, отличающееся тем, что, с целью повьшхения информационной емкости устройства, в него введены дешифратор, К дополнительных блоков ассопдативных признаков (где К - целое число), К+4 элементов ИЛИ, шифратор, основной блок элементов И и К+1 дополнительных блоков элементов И, причем синхровходы, тактовые входы, входы сброса результата поиска, входы записи-чтения, адресные входы, входы признака опроса,,входы наличия связи признаков и установочные входы дополнительных блоков ассоциативных признаков подключены соответственно к входу синхронизации, тактовому входу, первому установочному входу, адресным входам, признаковому входу, идентифицирующему входу и второму установочному входу устройства, информационные входы дешифратора подключены к адресным входам устройства, управляюший вход дешифратора соединен с входом режима устройства, выходы дешифратора подключены к входам выборки соответствуюших блоков ассоциативных признаков, первые входы первого элемента ИЖ и первого блока элемента И соединены с входом режима устройства, выход i-ro элемента ИЛИ

(i 1,К) соединен с входом блокировки i-ro дополнительного блока ассоциативных признаков, п€;рвые входы

0

5

5

j-го элемента ИЛИ (j « 2,К+1) и j-ro дополнительного блока элементов И соединены с входом блокировки(j - 1)- го дополнительного блока ассоциативных признаков, выход результата поиска первого дополнительного блока ассоциативных признаков подключен к

i информационному входу основного блока ассоциативных признаков, выход резуль-

тата поиска 1-го дополнительного блока ассоциативньпс признаков (1 2, К) подключен к информационному входу (1 - 1)-го дополнительного блока ас

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

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

47

f2

fi

5

фив.2

50

53