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

 

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

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

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

РЕСПУБЛИН (50 4 G 11 С 15 00

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

К АBTOPCHOMV СВИДЕТЕЛЬСТВУ

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

llO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3905922/24-24 (22) 04.06.85 (46) 23.12.86. Бюл. № 47 (71) Ленинградский ордена Ленина электротехнический институт им. В. И. Ульянова (Ленина) (72) В. П. Емелин и В. Т. Изиков (53) 681.327 (088.8) (56) Однородные микроэлектронные ассоциативные процессоры. Под ред. И. В. Прангишвили. М.: Советское радио, 1973, с. 27.

Авторское свидетельство СССР № 773370, кл. G 11 С 15/00, 1979. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в информационно-поисковых и управляющих системах, где необходимо вести ассоциативный поиск информации по произвольному числу признаков, в частности оно может быть

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

1278976

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

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

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

Устройство содержит (фиг.!) блок 1 управления, блоки 2 ассоциативной памяти, формир<>BBTeли 3. шифратор 4, элементы И 5, I1CPBhlH (> И ИTO!:ËH > 0,:!ОКИ 0!IBPBTH8!!OH памяти.

1!а фиг.1 обозна «сны первый 8 H BToрои 9 признаковые B.>0;<û устройства, установочный вход 10, первый 11 и второй !2 адресные входы устройства. Блок 1 имеет входы 13- -17, выходы 18 и !9, вход 20 и выходы 21 и 22. Каждый формирователь 3 имеет входы 23- — 26, выходы 27 и 28. входы 29 и 30, выход 31 и вход 32, Блок 1 управления (фиг.2) содержи" .элементы И 33-35, дешифратор 36, группы 37—

39 элементов И и группу э IB cHT0B И 40.

Каждый формирователь 3 (фиг.3) содержит триггеры 41---43„элементы И 44- — 47, элементы ИЛИ 48 и 49. Элементы И 5 имеют устойчивые состояния: логическая «1» и высокое сопротивление (разрыв).

В предложенном ycTpoHcтге структура составной ячейки АЗУ содержит следующие функционал ьные по.<я: ассоциативные признаки; признаки состояния ячейки (для каждогO из ассоциативных llpHBHBK08 су<цествует признак занятости, признак .-отовности H тег цепочки ассоциативных признаков); адрес основной информации, который HBходится в первом блоке 6; основная информация, которая находится

Во в гором блоке 7.

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

Цепочки признаков в составных ячейках

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

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

49

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

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

Установка нача..ьного состояния АЗУ осуществляется путем подачи единичного сигнала на вход 11 устройства. При этом триггеры 43 всех блоков 3 будут установлены в единичное состояние. Это соответствует тому, что каждая ячейка АЗУ в данный момент содержат по <>д1-:ому признаку опроса.

Выполнение операции записи, поиска и считыван ия lip 0èñ õî <НТ в строго оп ределенные моменты иремс;IH, задаваемые последователь!ocTblo такговых импульсов, которая подается на вх >д 14 блока управления. Тактировг><ие; ан>:ых операций осущеcTB;IHeTcB с помощью эл< ме1пов И 33--35.

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

Количество тактов, необходимое для записи информации L од«у составну10 ячейку АЗУ, равно количеству ассоциативных признаков, объединенных в не>>очку. При записи информации в АЗУ ассоциативный llpHзнак, тег цепочки II;,>изнаков, адрес признака, адрес основной и> <Ьорх>с>ции и основная инфорация подаются на <Оответствх>о1цие входы АЗУ, при этом на в одс 16 блока 1 управления .<олжс.ll бь>ть установлен режим «Запись», что соответс>вует пулевомх. уровшо входногO cH. HB !B. 11еобходимо отметить, чтО ВхОд 8 ис>1ол ь 11BTÑH к<1 к тл я за—

11НсН Bc<0циаз ивнь<х приз> !ННВ ь О. IQK 2, TBi; H для присма признав.il 01!pÎcB при п<>иске информации, так как два 0TH режима работы

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

Адрес основной информации а сама информация измениот свое значение только после записи последнегс признака B цепочке.

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

Адрсc признак поступает на вход 11 устройства (отметим, что в режиме «Запись» выход элементов И 5 с тремя состояниями

Отключен от входа 11). Далее адрес признака поступает íà B>:îl дешифратора 36 блока 1 управления и на адресный вход блока 6. С помощью дешифратора 36 и элемента И 39 сформируется сип1ал, по кото1278976

1О

20

Формула изобретения рому признак запишется в соответствующий блок 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, который соответствует. первому признаку в цепочке, 25

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

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

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

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

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

Фиг 1

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

1278976

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

Редактор В. Данко Техред И. Верес Корректор A. Обручар

Заказ 6847/54 Тираж 543 Подписное

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

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4