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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 789 Я 1) 4 6 11 С 15 0 ПИСАНИЕ ИЗОБРЕТЕНИ электроульянов на Ленина Т. Изико ассоци- В. Пран, с. 27. лектронны д ред. И. радио, 197 тво СССР /00, 1979. ОМИ НА)О(54) АССОЦИАТ ШЕЕ УСТРОЙСТ (57) Изобретение ной технике и мо информационно-по системах, где необ ный поиск инфор числу признаков, в НО к вычислитель- использовано вуправляюших ти ассоциативпроизвольному оно может быть относится жет быть исковых и ходимо ве мации по частности ГОСУДАРСТВЕННЫИ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Ленинградский ордетехнический институт им(56) Однородные микроэативные процессоры. Погишвили. М.: СоветскоеАвторское свидетельс773370, кл. Су 11 С 15 использовано в потоковых процессорах для определения готовности команд к выполнению, которые имеют произвольное число входов по данным или по управлению. Цель изобретения заключается в расширении ооласти применения устройства путем обеспечения поиска информации по произвольному числу признаков поиска. Ассоциативное запоминающее устройство (АЗУ) содержит блоки ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, приоритетный шифратор, элементы И, блоки оперативной памяти и блок управления. Расширение области применения устройства достигается за счет организации работы составных ячеек АЗУ, которые содержат цепочки из произвольного числа признаков, получаемь 1 е в результате программирования структуры ячеек АЗУ в процессе записи информаиии. Причем для поиска ин. формапии по к признакам требуется к абра. шений к АЗУ. 3 ил.Изобретение относится к вычислительнойтехнике, в частности к запоминающим устройствам, и может быть использовано, например, в процессорах с асинхронным управлением вычислениями для поиска готовы квыполнению команд.Цель изобретения -- расширение области применения устройства за счет обеспечения поиска по произвольному числу признаков поиска,Нз фиг.1 показана функциональная схема ассоциативного запоминающего устройства; на фиг.2 и 3 - функциональныесхемы блока управления и формирователясигналов состояния ячеек памяти соответственно,Устройство содержит (фиг.) блок 1 управления, блоки 2 ассоциативной памяти,формирователи 3. шифратор 4, элементы И 5,первый 6 и цто 1 аой 7 блоки оперативнойпамяти.11 а фиг 1 обознасны первый 8 и ВторОИ 9 ПрИЗНЗКс 1 ВЫЕ ВХОЛЫ уетройетза, установочный Вход 10, первый 11 и второй 2адресные входы устройства. Блок 1 имеетвходы 13. -17, Выходы 18 и 9, вход 20 ивыходы 21 и 22. Каждый формирователь 3имеет ВХС 1 лы 23 - 26, выхоль 1 27 и 28, входы 29 и 30, выход 31 и вход 32.Блок управления (фиг.2) содержит элементы И 33-35, дешифратор 36, группы 37 -39 элементов И и группу элемснтов И 40.Кзжлый 1 формирователь 3 (фиг.3) содержиттриггеры 41-.-43 элементы И 44 - 47, элементы ИЛИ 48 и 49. Элементы И 5 имеютустойчивые состояния: логическая 1 и высокое сопротивление разрыв).В предложенном устройстге структурасоставной ячейки АЗУ содержит следую 1 циефункциональные по,1 я:ассоциативные признаки;признаки состояния ячейки (лля каждогоиз ассоциативных признаков су 1 цествуетпризнак занятости, признак готовности и тегцепочки ассоциативных признаков);адрес основной информации, который находится в первом блоке 6;основная информация, которая находитсяВО 11 гором Олокс 7.Данные функциональные поля условнообьединены в виде составной ячейки АЗУ.Цепочки признаков в составных ячейкахАЗУ формируются путем установки для каждого из ассоциативных признаков тега цепочки либо в О, либо в 1. Единичноесостояние тегц цепочки свидетсльствует отом, что соответствующий ему ассоциативный признак является первым в цепочке,а обратное утверждение соответствует нулевому состоянию тегз. Цепочки признаковформируются В процессе записи информации в АЗУ, при этом значения тегов цепочек помеща 1 отся в триггера из блоков 3.Основная информация, соответству 101 цзянекоторой составной ячейки АЗУ, мсжет быть5 1 О 15 20 25 30 35 40 45 50 55 прочитана только после того, когда все из ассоциативных признаков, соответствующие данной ячейке, совпадут с входными признаками опроса хотя бы олин раз, Призна. ки опроса последовательно подаются на соответствующий вход АЗУ. В результате успеснного поиска читаемая информация автоматически формируется ца выходе блока 7, при этом на управляющем выходе АЗУ формируется сигнал, свилетельствую 1 ций о наличии считываемой информации.АЗУ работает следующим образом.Установка начального состояния АЗУ осуществляется путем подачи единичного сигнала на вход 11 устройства. При этом триггеры 43 всех блоков 3 будут установлены в единичное состояние. Это соответствует тому, что каждая ячейка АЗУ в данный момент солержаг по Одному признаку опроса.Выпо;1 нение Опе 1,зциц записи, поиска и считывания цроисхс 1151 т В строго определенные моменты нремс;1 и, ззлзвземце последовательностью такговых импульсов, которая подается ца вх ь 1 14 блока 1 управле. ния. Тактировгцие;.зццых Операций осу 1 цествляется с помощью элсме 1 поц И 3335.Режим записи.Количество тактов, необхолимос. лля записи информации г одну состзвцу 1 о ячейкх АЗУ, равно количеству ассоциативных признаков, объелинсццых В цепочку. Прц записи информации В АЗУ ассоциативный признак, тег цецс 5 чки признаков, адрес признака, адрес основной ццфс 1 рх 1 зции и основная ицфс 1 рз 1 ния цолзютс 51 ца соответствх 1 о 1 цие входы АЗУ, при этом ца цхолс 16 блс 1- ка 1 управления лолжсц быть установлен режим Запись, что сс 1 сттветс 1 вует цулевомх уровшо входного си 1 цзла. 11 еобхолимо отметить, что Вх 03 8 используетс 51 кзк для ззццси зссс 1 циа 1 и 1 внь 1 х призцзкс 1 В В О.1 ок 2, так ц для црисма признав.з опроса прц НО 51 ске информации, так как лва эти режима работы АЗУ считаются вззимоисключзюцсими. Во время записи зссоццаивцыи признак, тег цепочки и адрес признака ме 1 як 15 свои значения после каждого такта записи, причем признаки, Отцос 51 щиеся к ОднОЙ состзвнОЙ ячейке, должны записываться в соседние блоки 2, другими словами адрес признака должен меняться путе 1 увеличения его ца 1. Адрес основной информации и сама информация измениот свое значение только после записи послелнегс признака в цепочке.Запись информации в АЗУ происходит следу 1 ощим Образом.Алрсс признака поступает на Вход 11 устройства (отметим, что в режиме Запись выход элементов И 5 с тремя состояниями Отключец от входа 11). Далее адрес признака поступает на вход лешифратора 36 блока 1 управления и на адресный Вход блока 6. С помощью лешифрзтора 36 и элемента И 39 сформирустся сип 1 а., цо кото 12789761 О 15 го Формула изобретения рому признак запишется в соответствующий блок 2, тег цепочки признаков с помощью элемента И 45 запишется в соответствующий триггер 43, а соответствующий триггер 14 установится в единичное состояние, это соответствует тому, что блок 2 занят. По адресу, подаваемому на вход 12 устройства, и по сигналу на выходе 18 блока 1 управления адрес основной информации запишется в блок 6. В режиме Запись выход блока 6 отключен от входа 12 устройства. В результате этого на вход 12 устройства будет поступать адрес основной информации и по сигналу с выхода 18 блока 1 управления основная информация запишется в блок 7.Режим поиска.Ассоциативный поиск ячеек по одному из признаков опроса осуществляется за один такт, Для этого код признака опроса подается на вход 8 устройства. На вход 13 блока 1 подается сопровождающий сигнал. По этому сигналу блокуправления формирует сигнал поиска на его выходе 19. Для всех признаков, записанных в блоки 2 и совпадающих с входным признаком опроса, появятся сигналы совпадения на соответствующих выходах блоков 2, откуда они поступают на входы 23 формирователей 3. Далее по сигналу поиска все сигналы совпадения запишутся в соответствующие триггеры 42, установив их в единичное состояние. Если триггер 42 какого-нибудь блока 3 находится в единичном состоянии (т. е. признак готов) и данный блок 3 соответствует первому признаку в цепочке признаков (тег цепочки равен 1), то при наличии сигнала готовности нижних признаков (т. е. все признаки, относящиеся к одной составной ячейке и имеющие адрес больше адреса текущего признака, в данном случае первого в цепочке, находятся в состоянии готовности) данная составная ячейка АЗУ находится в состоянии готовности, о чем будет свидетельствовать единичный сигнал на выходе элемента И 47. Сигнал готовности нижних признаков вырабатывается с помощью элементов И 46 и ИЛИ 49, он принимает единичное значение, если тег цепочки для данного блока 3 равен 1, т. е. первый признак в цепочке (это необходимо, чтобы соседние составные ячейки не влияли друг на друга при определении готовности), или если данный признак находится в состоянии готовности (триггер 42 в единичном состоянии) и все нижние, по отношению к данному, признаки находятся в состоянии готовности (на входе 32 блока будет находиться единичный сигнал).Таким образом, как только в какой- нибудь составной ячейке произошел опрос всех признаков хотя бы по одному разу (т. е. во всех триггерах 42, относящихся к данной составной ячейке, будет находиться по 1), на выходе 31 блока 3, который соответствует. первому признаку в цепочке,25 30 35 40 45 50 55 появится сигнал готовности составной ячейки. Ассоциативный поиск составных ячеек осуществляется путем последовательной подачи признаков опроса на соответствующий вход. Режим считывания.Считывание информации происходит только из блока 7, каждая ячейка которого содержит искомую информацию (более подробно этот режим не рассматривается).Необходимо отметить, что процессы ассоциативного поиска и считывания информации происходят независимо друг от друга и поэтому могут быть совмещены во времени, другими словами одновременно со считыванием одной ячейки может происходить поиск другой. В режиме записи процессы поиска и считывания блокируются с помощью элементов И ЗЗ, 35 блока 1 управления. Ассоциативное запоминающее устройство, содержащее первый блок оперативной памяти, блок управления, блоки ассоциативной памяти и формирователи, первые входы которых подключены к выходам блоков ассоциативной памяти, первые входы которых являются первым признаковым входом устройства, вторые входы блоков ассоциативной памяти, первый вход первого блока оперативной памяти, вторые, третьи и четвертые входы формирователей соединены с соответствующими выходами блока управления, одни из входов которого соединены с первыми выходами формирователей, отгичающееея тем, что, с целью расширения области применения устройства за счет обеспечения поиска по произвольному числу признаков, в него введены второй блок оперативной памяти, элементы И и шифратор, входы которого подключены к вторым выходам формирователей, один из входов шифратора является управляющим выходом устройства, а другие выходы соединены с первыми входами элементов И, выходы которых соединены с вторым входом первого блока оперативной памяти, который является первым адресным входом устройства, выход первого блока оперативной памяти соединен с первым входом второго блока оперативной памяти, второй вход которого является информационным входом устройства, вторым адресным входом которого являются третий вход. первого блока оперативной памяти и первый вход второго блока оперативной памяти, выход которого является информационным выходом устройства, третий вход второго блока оперативной памяти подключен к одному из выходов блока управления, другие входы блока управления соединены с вторыми входами элементов И, четвертыми входами блоков оперативной памяти и первым адресным вхо1278976 18 га дом устройства, второй признаковый и установочный входы которого соединены соответственно с пятыми и шестыми входами формирователей, третий выход каждого из которых, кроме последнего, соединен с седьмым входом последующего формирователя.Составитель В. Рудаков Редактор В. Данко Техред И. Верес Корректор Л. Обручар Заказ 6847/54 Тираж 543 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж - 35, Раушская наб., д. 4/5 Филиал ППП Патент, г. Ужгород, ул. Проектная, 4