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

ОЮЗ СОВЕТСНИХ ОЦИАЛИСТИЧЕСКРЕСПУБЛИК 19) 111) 4 С 11 С 15/ОО ОПИСАНИЕ ИЗОБРЕТЕНИ ЯЯД."СВИДЕТЕП В АВТОРСН е шви свидетельство СССР С 1 С 15/ОО, 19(54) АССОЦИАТИВНРОИСТВО ЗАПОИИНАННЦ Тобласти 57 Иэобретени носит ОСУДАРСТВЕННЫИ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Ленинградский электротехнкий институт им, В.И.Ульянона. с. 11-35.АвторскоеУ 1278976, кл вычислительной техники, в частностик запоминающим устройстнам, и можетбыть использовано в процессоРах сасинхронным управлением нычислениямн для поиска готовых к выполнениюкоманд, а также в информационно-поисковых системах, где необходимо производить ассоциатинный поиск информации одновременно по произвольномуколичеству признаков. Цель изобретения - повышение информационной емкости устройства за счет обеспечениявозможности наращивания элементовструктуры. Устройство содержит дешифратор 1, блоки 2 ассоциативных признаков, шифратор 3, основной блок 4элементов И, блок 5 оперативной памяти, элементы ИЛИ 15 и дополнительныеблоки 16 элементов И. 4 ил.Изобретение относится к вычисли,тельной технике, в частности к за: поминающим устройствам, и может бытьиспользовано, например, впроцессорах с асинхронным управлением вычислениями для поиска готовых к выполнению команд.Цель изобретения - повышение информационной емкости устройства.10На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема блока ассоциативных признаков; на фиг. 3 - структурная схема блока управления; на Фиг. 4 - структурная схема формирователя сигналов состояния.Ассоциативное запоминающее устройство (АЗУ) содержит (фиг, 1) дешифра тор 1, основной 2, и дополнительные 2, - 2 блоки ассоциативных признаков (где К - целое число), шифратор 3, основной блок 4 элементов И, блок 5оперативной памяти, шину 6 управления, объединяющую вход синхронизации, тактовый вход и первый установочный вход устройства, и адресную шину 7, объединяющую адресные входы и выходы устройства, Устройство имеет информа 30 ционные входы 8 и выходы 9.Каждый блок 2 ассоциативных признаков содержит (фиг. 2) блок 10 управления, ассоциативные ячейки 11 .памяти, формирователи 12 сигналов состояния, приоритетный шифратор 13 35 и элемент И 14. Устройство также содержит К+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 А 4 М, М - числоячеек 11 в устройстве); признаки состояния ячейки (для каждого из ассоциативных признаков существуют признак занятости, признак готовности ипризнак наличия связи ассоциативныхпризнаков); адрес основной информации,формируемый на адресных выходах блока2; основная информация, которая находится в блоке 5.Цепочки признаков в составных ячейках Формируются путем установки длякаждого из ассоциативных признаковопределенного разряда либо в "0",ев илибо в 1 . Единичное состояние разряда свидетельствует о том, что соответствующий ему ассоциативный признак является первым в цепочке, аобратное утверждение соответствуетнулевому состоянию этого разряда.Цепочки признаков Формируются в процессе записи информации в АЗУ,Основная информация, соответствующая некоторой составной ячейкеАЗУ: может быть прочитана толькопосле того, как все из ассоциативныхпризнаков, соответствующие даннойячейке, совпадут с входными признаками опроса хотя бы один раз. Признакиопроса последовательно подаются насоответствующий вход АЗУ. В результате успешного поиска считываемая информация автоматически формируетсяна выходе блока 5, при этом на выходе АЗУ формируется сигнал, свидетельствующий о наличии считываемой инфомации,АЗУ работает следующим образом,Установка начального состоянияАЗУ осуществляется путем подачи единичного сигнала на второй установоч- .ный вход АЗУ. При этом триггеры 59всех Формирователей 12 установлены внулевое состояние. Это свидетельствуе" о том, что все ячейки АЗУ пусты ин. находятся в состоянии готовности;9169 ется в блок 5. 10 15 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 блока 1 О с шины6 управления подается сигнал, покоторому блок 1 О формирует сигналпоиска на выходе 27 с помощью элемента И 3 1, подаваемый на входы 54 всехформирователей 12. Для всех признаков, записанных в ячейках 11, совпадающих с входным признаком опроса,появляются сигналы совпадения на соответствующих выходах 19, откуда онипоступают на входы 49 формирователей12. Далее по сигналу на выходе 27,блока 10 все сигналы совпадения записываются в триггеры 64 формирователей 12, устанавливая их в единичное состояние. Если триггер 64 какого- нибудь формирователя 12 находится в единичном состоянии (т.е. признак готов) и данный формирователь соответствует первому признаку в цепочке признаков, то при наличии сигнала на входе 58 формирователя 12 (т.е. всеи признаки, относящиеся к даннои составной ячейке и имеющие адрес, больший, чем адрес текущего признака, в данном случае первого в цепочке, находятся в состоянии готовности) данная составная ячейка АЗУ находится всостоянии готовности, о чем свидетельствует единичный сигнал на выходе элемента И 66 формирователя 1245Таким образом, как только в какойнибудь составной ячейке произошелопрос всех признаков хотя бы по одному разу, на выходе формирователя 12,который соответствует первому признаку в цепочке, появляется сигнал готовности составной ячейки. Ассоциативный поиск составных ячеек осуществляется путем последовательной подачи. признаков опроса на соответствующийвход.Режим считывания.Считывание информации происходитс блока 5, ячейки которого содержатискомую информацию. Для этого наадресный вход блока 5 поступает сфоррованный на шине 7 адреса код адреа первого в цепочке признака, Адресформируется при наличии высокогоуровня сигнала на шине 6 управления(установлен режим чтения), причеммладшие разряды формируются на выходе блока 16 элементов И активногоблока 2, а старшие разряды - на выходе блока 4 элементов И.Если на выходах формирователей12 есть хотя бы один сигнал готовности, то на управляющем выходе АЗУ;наличии на выходе блока 5 считываемой информации. По этому сигналу,внешние по отношению к АЗУ устройства принимают считываемую информацию,после чего формируется сигнал сброса,подаваемый по шине 6 управления навход 23 блока 10, Данный сигнал не обходим для того, чтобы сброситьготовность признаков прочитаннойячейки, после чего эта .составнаяячейка снова может участвовать в процессе ассоциативного поиска,Для сброса готовности составнойячейки на вход 26 блока 10 с выходаблока 16 элементов И поступает адреспервого признака в цепочке признаков,Далее он поступает на дешифратор 34,который формирует сигнал выборки соответствующего признака. С помощьюэлементов И 35 и 36 и ИЛИ 38 Формируется сигнал сброса готовности признака.Сигналы сброса готовности признаков с выходов 29 блока 10 поступаютна соответствующие входы формирователей 12 и переводят триггеры 64 внулевое состояние, тем самым устанавливая составную ячейку в исходноесостояние,Процессы ассоциативного поискаи считывания информации происходятнезависимо друг от друга и поэтомумогут быть совмещены во времени, другими словами, одновременно со считыванием одной ячейки может происходитьпоиск другой. В режиме записи процессы поиска и считывания блокируются спомощью .элементов И 31 и 33 блока 10..Ф о р мул а и з о б р е т е ни яАссоциативное запоминающее устройство, содержащее основной блок ассос45 50 установочному входу устройства, информационные входы дешифратора подключены к адресным входам устройства,управляющий вход дешифратора соединенс входом режима устройства, выходыдешифратора подключены к входам выборки соответствующих блоков ассоциативных признаков, первые входы первого элемента ИЛИ и первого блока элемента И соединены с входом режима устройства, выход -го элемента ИЛИ(х = 1,К) соединен с входом блокировки .-го дополнительного блока ассоциативных признаков, первые входы. циативных признаков и блок оперативной памяти, причем вход записи, входчтения, адресные входы и информационные входы блока оперативной памяти 5являются соответственно входом записи, входом чтенияадресными и информационными входами устройства, инФормационные выходы блока оперативной памяти являются информационнымивыходами устройства, синхровход, тактовый вход и вход сброса результатапоиска основного блока ассоциативныхпризнаков являются соответственно входом синхронизации, тактовым входом ипервым установочным входом устройства, адресные входы основного блокаассоциативных признаков подключенык адресным входам устройства, входпризнака опроса, вход наличия связипризнаков, вход блокировки и установочный вход основного блока ассоциативных признаков являются соответственно признаковым входом, идентифицирующим входом, входом режима и вторым установочным входом устройства,о т л и ч а ю щ е е с я тем, что,с целью повышения информационнойемкости устройства, в него введены З 0 дешифратор, К дополнительных блоковассоциативных признаков (где К -целое число), К+4 элементов ИЛИ, шифратор, основной блок элементов И иК+1 дополнительных блоков элементовИ, причем синхровходы, тактовые вхоЗ 5 ды, входы сброса результата поиска,входы записи-чтения, адресные входы,входы признака опроса, входы наличиясвязи признаков и установочные входыдополнительных блоков ассоциативных аопризнаков подключены соответственнок входу синхронизации, тактовому входу, первому установочному входу,адресным входам, признаковому входу,идентифицирующему входу и второму1-го элемента ИЛИ (12,К+1) и 1-го дополнительного блока элементов И соединены с входом блокировки( - 1)- го дополнительного блока ассоциатив 5 ных признаков, выход результата поиска первого дополнительного блока ассоциативных признаков подключен кинформационному входу основного блока ассоциативных признаков, выход резуль Отата поиска 1-го дополнительного блока ассоциативных признаков (1 = 2, К) подключен к информационному входу (1 - 1)-го дополнительного блока ас 15 социативных признаков, вторые входыэлементов ИЛИ и дополнительных блоков элементов И подключены к информационным выходам соответствующих блоков ассоциативных признаков, выходыэлементов ИЛИ подключены к выходамшифратора, выход которого соединенс первым входом основного блока элементов И, второй вход которого подключен к входу режима устройства, выходы блоков элементов И являютсяадресными выходами устройства и соединены с информационными входами дешифратора,1429169 оставитель В.Рудаков ехред Л.Сердюкова Корректор М.цароя ктор О.Юрковецкая Заказ 5132/4 ираж 59 одписное мите 4/ 130 нно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4 Проиэвод ИИПИ Государственногоделам изобретений и Москва, Ж, Раушс ткрыт я наб