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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

1. Изобретение относится к запоминающим устройствам и может быть использовано при ассоциативной обработке информации в задачах динамического распределения машинной памяти. Известно ассоциативное запоминающее устройство, которое содержит регистр вход ного признака, запоминающие регистры, схемы сравнения и детекторы и вьшолняет поиск среди заданных множеств признаков С1 В этом устройстве каждое множество признаков задается перечислением членов множества, а для уменьшения числа запо- Минающюс гистров применяется маскироi mie младших разрядов записываемых в устройстве признаков. Устройство характеризуется повьпиенными требованиями к числу запоминающих регистров, необхскдимых для точного задания множеств приз наков. ,: . Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство, содержащее регистр входного признака, регистры верхних границ отрезков, регистры нижних границ отрезков, первые и вторые схемы сравнения, элементы И и детекторы, причем входь первых схем сравнения под-ключены к выходам регистра признака и соответствующих регистров нижних границ отрезков, входы вторых схем сравнения подключены к выходам регистра входного признака и соответствующих регистров верхних границ отрезков, выходы первьЬс и вторых схем сравнения соединяются с входами соответствующих,элементов И, выходы которых подключены к детекторам. Устройство реализует поиск по принадлежности входного признака к множествам признаков, которые задаются в виде границ соответствующих отрезков- 2 , Недостатком этого устройства являет ся низкое быстродействие при поиске множеств признаков, соседних с заданны 1 множеством признаков, что часто требует ся в задачах динамического распределения машинной памяти, В STOM случае поиск 394 в устройстве осуществляется дважды. В первом случае в регистр входного признака устройства записывается верхняя граница отрезка, соответствующего сосед нему снизу множеству признаков, во втором случае - нижняя граница отрезка, соответствующего соседнему сверху множеству признаков. Кроме того, в задачах динамического распределения машинной памяти множества признаков задаются указанием нижних границ и длин соответс вующих отрезков, которые приходится пересчитывать в границы отрезков. Целью изобретения является повышение быстродействия устройства при поиске множеств признаков, соседних с заданным множеством признаков, а также расширение области применения устройства за счет реализации поиска соседних множеств признаков, заданных путем указания нижних гра ниц и длин соответствующих,отрезков натурального ряда чисел. Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее регистр признака поиска, две группы накопителей и две группы детекторов, введены дополнительный регистр признака поиска и две группы логических блоков, причем первые входы логических блоков первой группы и вторые входы соответствующих логических блоков второй группы подключены к выходам накопителей первой группы, входы логических блоков первой груп пы и первые входы логических блоков второй группы соединены с выходом регистра признака опроса, третьи входы логических блоков первой группы подключен к выходам накопителей второй группы, третьи входы логических блоков второй группы соединены с выходом дополнитель ного регистра признака поиска, вьгходы логических блоков подключены к входам соответствующих детекторов. Каждый логический б,лок содержит элементь НЕ, элементы И, элементы ИЛИ и первый и второй триггеры, причем первые входы первого и втгрого элементов И подключены к выходу второго триггера, первые входь третьего, четвертого и пятого элементов И - к первому выходу первого триггера, второй выход которого соединен с первыми входами шестого, седьмого и восьмого элементов И, вторые входы второго, шестого и восьмого элементов И соединены с выходом первого элемента НЕ, вторые входьт первого, третьего и пятого элементов И - с выходом второго элемента НЕ, второй вход 2 четвертого н третьи входы первого и третьего элементов И - с выходом третьего элемента НЕ, третьи входы четвертого и пятого и четвертый вход первого элементов И подключены к входу первого элемента НЕ, второй вход седьмого и третьи входы второго и шестого элементов И - к входу второго элемента НЕ, третьи входы седьмого и- восьмого и чет вертый вход второго элементов И - к ходу третьего элемента НЕ, первый и второй входы первого триггера подключены к выходу первого элемента И и выходу первого элемента ИЛИ, первый вход которого соединен с выходом второго элемента И, выходы элементов И с третьего по восьмой соединены с входами второго элемента ИЛИ, выход которого подключен к первому входу второго триггера, второй вход которого соединен с вторым входом первого элемента ИЛИ, входы девятого элемента И подключены к первому выходу первого триггера и к выходу второго триггера, третьи входы триггеров объединены и являю1х;я одним из входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы элементов НЕ, а выходом - вьпсод девятого элемента И. На фиг. 1 изображена функциональная схема предложенного устройства ; на фиг. 2функциональная схема предпочтительного варианта реализации логического блока | на фиг. 5 - график .состояний логического блока. Устройство содержит регистр 1 признака поиска, дополнительный регистр 2 признака поиска (каждый из регистров 1 и 2 имеет по т разрядов, где m - целое число), первую и вторую группы накопителей 3 и 4, первую и вторую группь логических блоков 5 и 6, первую и вторую группы детекторов 7 и 8. Каждый VS3 блоков 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 начальной установки. В ре 59459 гистры 1 и 2 записываются нижняя грани мино Дпина KO входного отрезка. В процессе поиска отрезков, соседних с входным отрезком, 1гаформация из р8 гистров 1 и 2 и накопителей 3 И4 по- g ступает на входы 9 - 11 блоков 5 и 6 поразрядно, начиная со старших разрядов. В каждом блоке 5 и 6 при поступлении сигналов из j -ых разрядов регистров 1 и 2 и соответствующих накопителей 3 и ю 4 определяется значение АЪ фиксируемое в виде определенного состояния блока 5 и 6. Значение А3,{ О фиксируется в виде начального состояния (фиг. 3), CAlj -1 - в виде состояния d При 15 2 блок 5 и 6 переходит в ко- нечное состояние С1л, при } „ в конечное состояние с(. Каждое состояние блоков 5 и б кодируется определенным набором состояний триггеров 27 и 28: состояние с( кодируется набором (О, 0),с(2 - набором (О, 1), С31а-набором (1, О) и 0( набором (1, 1). Если блоки 5 и 6 находятся в состояНИИ С(-, то при поступлении на входы 9 -25 11 блоков 5 и 6 любого набора из множества сигналов перехода С (0,0,0) (О, i, 1), (1, 1, О) состояние не меняется, при поступлении набора CQ (О, 1, блоки 5 и 6 переходят в промежуточное состояние di , KUTOpoe сохраняется при поступлении-любого набора из множества С,, Т(0, О, 1), (1, О, О), (1, 1, l)j . Из состояния с|л блоки 5 и 6 переходят в начальное состояние с( под действием набора Сд (1, О, 1). Любой набор из множества C;j CjUC переводит блоки 5 и 6 из состояния Ят в конечное со- сто5шие Qtj, в котором блоки 5 и 6 не реагируют на сигналы на их входах 9-1 Под действием любого набора из множест ва С блоки 5 и 6 переходят из состояния Оьв конечное состояние . . После анализа всех разрядов чисел, поступающих на входы 9-11 блоков 5 и 6, триггеры 27 и 28 находятся оответственно в единичном и нулевом состоя ниях, если А -1. При этом выходкой сигнал элемента И 24, выход которого является выходом 12 блоков 5 и 6, равен единице. Для i -го блока 5 это озна чает, что XV M -XMMHO- 1 - « ) для -t блока 6 - что X. + KQ -1. Выходной сигнал блока 5 поступает на соответствующий детектор 7, который фиксирует соседний сньзу отрезок. Выходной вигнал блока 6 поступает на детектор 8, который фиксирует соседний сверху отрезок. 20 2б Технико-экономическое преимушество предлагаемого устройстеа заключается в более высоком быстродействии, так как число опросов устройства по сравнению с известным сокращается вдвое, а Б расщирента- области применения устройства за счет реализации нового вида поиска, выявляющего отрезки, заданные указанием нижних границ и длин, соседние с входным отрезком. Формула изобретения 1. Ассоциативное запоминающее устрой- ство, содержащее регистр признака поиска, группы накопителей и две группы детекторов, отличающееся тем, что, с целью првьпиения быстродействия устройства, оно содержит дополнительный регистр признака поиска и две группы логических блоков, причем первые входы логических блоков первой группы и вторые входы соответствующих логических блоков второй группы подключены к выходам накопителей первой группы, вторые входы логических блоков первой группы и первые входь логических блоков второй группы соединены с выходом регистра признака опроса, третьи входы логических блоков первой группы подключены к выходам накопителей второй группы, третьи входы логических блоков второй группы соединены с выходом дополнительного регистра признака поиска, выходы логических блоков подключены к входам соответствующих детекторов. 2. Устройство по п. 1, о т-л и чающееся тем, что каждый логический блок содержит элементы НЕ, элементы И, элементы ИЛИ и первый и второй триггеры, причем первые входы первого и второго элементов И подключены к выходу второго триггера, первые входы третьего, четвертого и пятогоэлементов И - к первому выходу первого триггера, второй выход, которого соединен с первыми входами щестого, седьмого и восьмого элементов И, вторые входы второго, щестого и восьмого элементов И соединены с выходом первого элемента НЕ, вторые входы первого, третьего и ПЕТОГО элементов И - с выходом второго элемента НЕ, второй вход четвертого и третьи входы первого и третьего элементов И - с выходом третьего элемента НЕ, трптьи входы четвертого и пятого и четвертый вход первого элементов И подключены к входу первого элемента НЕ, второй вход седь-

мого и третьи входы второго и шестого элементов И - к входу второго эпемента НЕ, третьи входы седьмого и восьмого и четвертый вход второго элементов И - к входу третьего элемента НЕ, первый и второй входы первого триггера подключены к выходу; первого элемента И и выходу первот о элемента ИЛИ, первый вход которого соединен с выходом второго элемента И, выходы элементов И с третьего по восьмой соединены с входами второго Элемента ИЛИ, выход которого подключен к первому входу второго триггера, второй вход которого соединен с вторым входом первого элемента ИЛИ, входы девятого элемента И подключены

К первому выходу первого триггера и к выходу второго триггера, третьи входы триггеров объединены и являются одним из входов блока, другими входами которого являются второй вход первого элемента ИЛИ и входы элементов НЕ, а выходом - выход девятого элемента И.

Источники информации, принятые во внимание при экспертизе

М

12

ги

Z1

IS

15

гь