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

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

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

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

Устройство содержит (фиг.1) блок 1 управления, блоки 2 ассоциативной памяти, формирователи 3. шифратор 4, элементы И 5, первый G и второй 7 блоки оперативной памяти.

lia фиг.) обозначены 1ервый 8 и второй 9 признаковые входы устройства, установочный вход 10, первый 11 и второй 12 адресные входы устройства. Блок 1 имеет входы , выходы 18 и 19, вход 20 и выходы 21 и 22. Каждый формирователь 3 имеет входы 23-- 26, выходы 27 и 28, входы 29 и 30, выход 31 и вход 32.

Блок управления (фиг.2) содержит элементы И 33-35, дешифратор 36, группы 37- 39 элементов И и группу элементов И 40. Каждый формирователь 3 (фиг.З) содержит триггеры 41--43, элементы И 44--47, элементы ИЛИ 48 и 49. Элементы И 5 имеют устойчивые состояния: логическая «1 и высокое сопротивление (разрыв).

В предложенном устройстве структура составной ячейки АЗУ содержит следующие функциональные поля:

ассоциативные признаки;

признаки состояния ячейки (для каждого из ассоциативных признаков существует признак занятости, признак готовности и тег цепочки ассоциативных признаков);

адрес основной информации, который находится в первом блоке 6;

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

Данные функциональные поля условно объединены в виде составной ячейки АЗУ.

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

Основная информация, соответствующая некоторой составной ячейки АЗУ, может быть

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

чии считываемой информации.

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

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

осуществляется путем нодачи единичного

сигнала на вход 11 устройства. При этом

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

Вьшолнение операции записи, поиска и

считывания происходит в строго определенные моменты времени, задаваемые последовательностью тактовых -HMHyjibcoB, которая подается па вх )д 14 блока 1 управления. Тактирование данных операций осуществляется с помощью элементов И 33--35. Режим записи. Количество тактов, необходимое для записи информации в одну составную ячейку АЗУ, равно количеству ассоциативных признаков, объединенщ ж в цепочку. При записи информации в ассон,иативный признак, тег цепочки признаков, адрес признака, адрес основной информации и основная инфорация подаются на соответствующие входы , при этом на Bxo;ie 16 блока 1 управления должен быть установлен

режим «Запись, что соответствует ну.чевому уровню вхо.дного си-ди)ла. Необходимо отметить, что вход 8 используется как для за- Hi-iCH ассоциативных признаков в блок 2, так и для приема признака опроса при поиске информации, так как два эти режима работы

АЗУ считаются взаимоисключающими. Во время записи ассоциативный признак, тег це- ночки и адрес признака меняют свои значения носле каждого такта записи, причем признаки, относящиеся к одной составной ячейке, должны зап1-1сываться в соседние блоки 2, другими словами адрес признака должен меняться путем увеличения его на «1. Адрес основной информации и сама информация изменяют свое значение только после записи последнего признака в цепочке.

Запись информации в АЗУ происходит следующим образол .

Адрес признака поступает на вход 11 устройства (отметим, что в режиме «Занись выход элементов И 5 с тремя состояниями отключен от входа 11). Далее адрес нризнака ноступает на вход дешифратора 36 блока 1 управления и на адресный вход блока 6. С помонгью дешифратора 36 и элемента И 39 сформируется сигнал, по кото

рому признак запишется в соответствующий блок 2, тег цепочки признаков с помощью элемента И 45 запишется в соответствующий триггер 43, а соответствующий триггер 14 установится в единичное состояние, это соответствует тому, что блок 2 занят. По адресу, подаваемому на вход 12 устройства, и по сигналу на выходе 18 блока 1 управления адрес основной информации запишется в блок 6. В режиме «Запись выход блока 6 отключен от входа 12 устройства. В результате этого на вход 12 устройства будет поступать адрес основной информации и по сигналу с выхода 18 блока 1 управления основная информация запишется в блок 7.

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

Ассоциативный поиск ячеек по одному из признаков опроса осуществляется за один такт. Для этого код признака опроса подается на вход 8 устройства. На вход 13 блока 1 подается «сопровождающий сигнал. По этому сигналу блок 1 управления формирует сигнал поиска на его вы.хо- де 19. Для всех признаков, записанных в блоки 2 и совпадающих с входным признаком опроса, появятся сигналы совпадения на соответствующих выходах блоков 2, откуда они поступают на входы 23 формирователей 3. Далее по сигналу поиска все сигналы совпадения запишутся в соответствующие триггеры 42, установив их в единичное состояние. Если триггер 42 какого-нибудь блока 3 находится в единичном состоянии (т. е. признак готов) и данный блок 3 соответствует первому признаку в цепочке признаков (тег цепочки равен «1), то при наличии сигнала готовности «нижних признаков (т. е. все признаки, относящиеся к одной составной ячейке и имеющие адрес больше адреса текущего признака, в данном случае первого в цепочке, находятся в состоянии готовности) данная составная ячейка АЗУ находится в состоянии готовности, о чем будет свидетельствовать единичный сигнал на выходе элемента И 47. Сигнал готовности «нижних признаков вырабатывается с помощью элементов И 46 и ИЛИ 49, он принимает единичное значение, если тег цепочки для данного блока 3 равен «1, т. е. первый признак в цепочке (это необходимо, чтобы соседние составные ячейки не влияли друг на друга при определении готовности), или если данный признак находится в состоянии готовности (триггер 42 в единичном состоянии) и все «нижние, по отношению к данному, признаки находятся в состоянии готовности (на входе 32 блока будет находиться единичный сигнал).

Таким образом, как только в какой- нибудь составной ячейке произошел опрос всех признаков хотя бы по одному разу (т. е. во всех триггерах 42, относящихся к данной составной ячейке, будет находиться по «1), на выходе 31 блока 3, который соответствует, первому признаку в цепочке.

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

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

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

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

20

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в информационно-поисковых и управляющих системах, где необходимо вести ассоциативный поиск информации по произвольному числу признаков, в частности оно может быть использовано в потоковых процессорах для определения готовности команд к выполнению, которые имеют произвольное число входов по данным или по управлению. Цель изобретения заключается в расширении области применения устройства путем обеспечения поиска информации по произвольному числу признаков поиска. Ассоциативное запоминающее устройство (АЗУ) содержит блоки ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, приоритетный шифратор, элементы И, блоки оперативной памяти и блок управления. Расширение области применения устройства достигается за счет организации работы составных ячеек АЗУ, которые содержат цепочки из произвольного числа признаков, получаемые в результате программирования структуры ячеек АЗУ в процессе записи информации. Причем для поиска информации по к признакам требуется к обращений к АЗУ. 3 ил. (О (Л to 00 со

13

2428

.З