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

ОП ИСАНИ Е ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспубики ц 945902щф(5)М. Кл, б 11 С 3.5/00 3 Ъеудвретееивй кеиитет СССР ие девам изабретеииЮ и вткритиЮ) Авторыизобретен и Трусфус, Р. Р. Бикмухаметов и С Казанский ордена Трудового Красного Знаменавиационный институт им. А. Н. Туполева) Заявитель АТИВНОЕ ЗАПОМИНАЮШЕЕУСТРОИСТВО 54 А 1Изобретение относится к запоминающимустройствам и может быть использованопри ассоциативной обработке информациив задачах динамического распределениямашинной памяти.Известно ассоциативное запоминающее 5устройство, которое содержит регистр входного признака, запоминающие регистры,схемы сравнения и детекторы и выполняет поиск среди заданных множеств приз-.наков 1 .В этом устройстве каждое множествопризнаков задается перечислением членовмножества, а для уменьшения числа запоминающих регистров применяетсямаскиро 5Йание младших разрядов записываемыхв устройстве признаков, Устройство характеризуется повышенными требованиямик числу запоминающих регистров, необходимых для точного задания множеств приз 2 оиаков,Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство, содержащее 2регистр входного признака, регистры верх них границ отрезков, регистры нижних границ отрезков, первые и вторые схемы сравнения, элементы И и детекторы, причем входы первых схем сравнения под" ключены к выходам регистра признака и соответствующих регистров нижних границ отрезков, входы вторых схем сравнения подключены к выходам регистра входного признака и соответствующих регистров верхних границ отрезков, выходы первых и вторых схем сравнения соединяются с входами соответствующих элементов И, выходы которых подключены к детекторам. Устройство реализует поиск по принадлежности входного признака к множествам признаков, которые задаются в виде границ соответствующих отрезков 2 .Недостатком этого устройства являе л. ся низкое быстродействие при поиске множеств признаков, соседних с заданныМ множеством признаков, что часто требует- ся в задачах динамического распределения машинной памяти. В етом случае поиск02 3 9459в устройстве осуществляется дважды. Впервом случае в регистр входного признака устройства записывается верхняяграница отрезка, соответствующего соседнему снизу множеству признаков, во втором случае - нижняя граница отрезка,соответствующего соседнему сверху множеству признаков. Кроме того, в задачахдинамического распределения машиннойпамяти множества признаков задаются 16указанием нижних границ и длин соответствующих отрезков, которые приходится пересчитывать в границы отрезков,Белью изобретения является повышениебыстродействия устройства при поиске 15множеств признаков, соседних с заданныммножеством признаков, а также расширение области применения устройства за счетреализации поиска соседних множеств признаков, заданных путем указания нижних граониц и длин соответствующих отрезков натурального ряда чисел.Поставленная цель достигается тем,что в ассоциативное запоминающее усчъройство, содержащее регистр признака 25поиска, две группы накопителей и двегруппы детекторов, введены дополнительный регистр признака поиска и две группы логических блоковпричем первыевходы логических блоков первой группыи вторые входы соответствующихлогических блоков второй группы подключены квыходам накопителей первой группы, вторые входы логических блоков первой группы и первые входы логических блоков35второй группы соединены с выходом регистра признака опроса, третьи входы логических блоков первой группы подключенык выходам накопителей второй группы,третьи входы логических блоков второйгруппы соединены с выходом дополнительного регистра признака поиска, выходылогических блоков подключены к входамсоответствующих детекторов.Каждый логический блок содержит45элементы НЕ, элементы И, элементы ИЛИи первый и второй триггеры, причем первые входы первого и втгрого элементов Иподключены к выходу второго триггера,первые входы третьего, четвертого и пятого элементов И - к первому выходу50первого триггера, второй выход которогосоединен с первыми входами шестого,седьмого и восьмого элементов И, вторые входы второго, шестого и восьмогоэлементов И соединены с выходом первого элемента НЕ, вторые входы первого,третьего и пятого элементов И - с выходом второго элемента НЕ, второй вход четвертого и третьи входы первого итретьего элементов И - с выходом третьего элемента НЕ, третьи входи четвертого и пятого и четвертый вход первогоэлементов И подключены к входу первого элемента НЕ, второй вход седьмого и третьи входы второго и шестого элементов И - к входу второго элемента НЕ,третьи входы седьмого и восьмого и четвертый вход второго элементов И - квходу третьего элемента НЕ, первый и второй входы первого триггера подключены к выходу первого элемента И и выходу первого элемента ИЛИ, первый входкоторого соединен с выходом второго элемента И, выходы элементов И с третьегопо восьмой соединены с входами второгоэлемента ИЛИ, выход которого подключенк первому входу второго триггера, второйвход которого соединен с вторым входомпервого элемента ИЛИ, входы девятогоэлемента И подключены к первому выходупервого триггера и к выходу второго триггера, третьи входы триггеров объединеныи являются одним из входов блока, другими входами которого являются второйвход первого элемента ИЛИ и входы элементов НЕ, а выходом - выход девятогоэлемента И.На фиг. 1 изображена функциональнаясхема предложенного устройства; на фиг. 2 функциональная схема предпочтительноговарианта реализации логического блока;на фиг. 3 - график, состояний логического блока.Устройство содержит регистр 1 признака поиска, дополнительный регистр 2признака поиска (каждый из регистров 1и 2 имеет по т разрядов, где ю - целоечисло), первую и вторую группы накопителей 3 и 4, первую и вторую группылогических блоков 5 и 6, первую й вторую группы детекторов 7 и 8. Каждыйиз блоков 5 и 6 имеет входы 9- 11 ивыход 12. Кроме того, каждый логический блок 5 или 6 содержит первый 13,второй 14 и третий 15 элементы НЕ,элементы И 16 - 24 (с первого 16 подевятый 24), первый 25 и второй 26элементы ИЛИ, первый 27 и второй 28триггеры, входы 29 и 30.Устройство работает следующим образом,В накопители 3 .и 4 записываются нижние границы Х, и длины К, задаваемых отрезков ( 1 = 1о ), Производитсяустановка в нулевое состояние триггеров27 и 28; блоков 5 и 6 подачей сигналана вход 29 начальной установки. В рек выходу второго триггера, первые входытретьего, четвертого и пятого элементов Ик первому выходу первого триггера, второй выход. которого соединен с первымивходами шестого, седьмого и восьмогоэлементов И, вторые входы второго, шестто и восьмого элементов И соединеныс выходом первого элемента НЕ, вторыевходы первого, третьегс и пятого элементов И - с выходом второго элемента НЕ,второй вход четвертого и третьи входыпервого и третьего элементов И - с выходом третьего элемента НЕ, третьи входы четвертого и пятого и четвертый входпервого элементов И подключены к входупервого элемента НЕ, второй вход седь 5 9459 гистры 1 и 2 записываются нижняя гра ница Х, и длина КО входного отрезка.В процессе поиска отрезков, соседних с входным отрезком, информация из регистров 1 и 2 и накопителей 3 и 4 поступает на входы 9 - 11 блоков 5 и 6 поразрядно, начиная со старших разрядов. В каждом блоке 5 и 6 при поступлении сигналов из 1 -ых разрядов регистров 1 и 2 и соответствующих накопителей 3 и щ 4 определяется значение А ; фиксируемое в виде определенного состояния блока 5 и 6. Значение А 1 = 0 фиксируется в виде начального состояния (фиг. 3), А 1 = -1 - в виде состояния О . При 15 А Е 1, 2 блок 5 и 6 переходит в конечн 3 е состояние О, при АЕ -2, 3-3 в конечное состояние с,.Каждое состояние блоков 5 и 6 кодируется определенным набором состояний 20 триггеров 27 и 28: состояние с( кодируется набором (О, 0), 4 - набором (О, 1), О-набором (1, О) и с 4- набором (1, 1).Если блоки 5 и 6 находятся в состоянии 4, то при поступлении на входы 9 - 25 11 блоков 5 и 6 любого набора из множества сигналов перехода С,= (0, О, 0), (О, 1, 1), (1, 1, 0) состояние не меняется, при поступлении набора С 1 (О, 1, 0) блоки 5 и 6 переходят в промежуточное :состояние О , которое сохраняется при . -поступлении. любого набора из множества С=(О,О,1), (1,0,0), (11) . Из состояния 4 блоки 5 и 6 переходят в начальное состояние с под действием набора С 4 = ( 1, О, 1), Любой набор из множества С = С ОС 4 переводит блоки 5 и 6 из состояния Й в конечное состояние С 1, в котором блоки 5 и 6 не реагируют на сигналы на их входах 9-11.0. Под действием любого набора из множест ва СС 1 ОС блоки 5 и 6 переходят из состояния с 4 в конечное состояние б+ .После анализа всех разрядов чисел, поступающих на входы 9 - 11 блоков 5 4 и 6, триггеры 27 и 28 находятся ",оответственно в единичном и нулевом состояниях, если 4 =-1. При этом выходной сигнал элемента И.24, выход которого является выходом 12 блоков 5 и 6, ра 50 вен единице. Для 1 -го блока 5 это означает, что Х мин -Хмин о " К -1 адпя 4 -го блока 6 - что Хц О-Хц 4 н+ + К, = -1. Выходной сигнал блока 5 по ступает на соответствующий детектор 7,55 который фиксирует соседний сньзу отрезок, Выходной еигнал блока 6 поступает на детектор 8, который фиксирует соседний сверху отрезок. 02 6Технико-економнческое преимушество предлагаемого устройс тва заключается в более высоком быстродействии, так как число опросов устройства по сравнению с известным сокращается вдвое, а также в расширении области применения устройства за счет реализации нового вида поиска, выявляющего отрезки, заданные указанием нижних границ и длин, соседние с входным отрезком,формула изобретения 1, Ассоциативное запоминающее устройство, содержащее регистр признака поиска, две группы накопителей и две группы детекторов, отличающееся тем, что, с целью повышения быстродействия устройства, оно содержит дополнительный регистр признака поиска и две группы логических блоков, причем первые входы логических блоков первой группы и вторые входы соответствующих логическихблоков второй группы подключены к выходам накопителей первой группы, вторыевходы логических блоков первой группы и первые входы логических блоков второйгруппы соединены с выходом регистрапризнака опроса, третьи входы логических блоков первой группы подключены к выходам накопителей второй группы, третьи входы логических блоков второй группы соединены с выходом дополнительного регистра признака поиска, выходы логических блоков подключены к входам соответствующих детекторов.2. Устройство по п, 1, о т л и ч а ю щ е е с я тем, что каждый логический блок содержит элементы НЕ, элементы И, элементы ИЛИ и первый и второй триггеры, причем первые входы первого и второго элементов И подключены7 . 9459 мого и третьи входы второго и шестого элементов Ик входу второго элемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов И- к входу третьего элемента НЕ, первый и второй входы первого триггера подключены к выходу, первого элемента И и выходу первого элемента. ИЛИ, первый вход которого соединен с выходом второго элемента И, выходы элементов И с тре о тбего по восьмой соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу второго триггера, второй вход которого соединен с вторым входом первого элемента ИЛИ, 1 входы девятого элемента И подключены 02 8к первому выходу первого триггера и квыходу второго триггера, третьи входытриггеров объединены и являются однимиз входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы элементов НЕ; авыходом - выход девятого элемента И,Источники информации,принятые во внимание при экспертизе1, Джозеф Каплан. Коррелирование. трасс целей с помощью памяти поиска.фЗарубежная радиоэлектроника", 1964,Яо 12. Авторское свидетельство СССРМц 243659, кл. б 11 С 15/00, 1966945902 .г ВНИИПИ Заказ 5339/7 Тираж 622 Подписное филиал ППП "Патент, г, Ужгород,у и. Проектная