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

 

О Il И С А Н И Е ()945902

ИЗОБРЕТЕН ИЯ

К - АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Респубики (61) Дополнительное к авт. свнд-ву

{22)Заявлено 05.01.81 (21) 3229539/18-24 с присоединением заявки № (23) Приоритет (53)M. Кл. 11 С 15/00

3Ъеудвретеапвй кеиитет

СССР ее делам имеретеиий и вткритиЮ

Опубликовано 23.07.82. Бюллетень № 27 (53) УДК681.327 (088.8) Дата опубликования описания 26.07,82 (72) Авторы изобретения

В. М. Трусфус, Р. P. Бикмухаметов и С. Л

Д

Казанский ордена Трудового Красного Знамен авиационный институт им. A. Н. Туполева (7 3 ) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНМОШЕЕ

УСТРОЙСТВО

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

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

В этом устройстве каждое множество признаков задается перечислением членов множества, а для уменьшения числа запоминающих регистров применяется маскиро 5 ванне младших разрядов записываемых в устройстве признаков. Устройство характеризуется повышенными требованиями к числу запоминающих регистров, необхо димых для точного задания множеств приз2о иаков, Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство, содержащее

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

Недостатком этого устройства являет ся низкое быстродействие при поиске множеств признаков, соседних с заданным множеством признаков, что часто требует ся в задачах динамического распределения машинной памяти. В етом случае поиск

3 9459 в устройстве осуществляется дважды. В первом случае в регистр входного признака устройства записывается верхняя граница отрезка, соответствующего соседнему снизу множеству признаков, во втором случае - нижняя граница отрезка, соответствующего соседнему сверху множеству признаков. Кроме того, в задачах динамического распределения машинной памяти множества признаков задаются 16 указанием нижних границ и длин соответст

1 вующих отрезков, которые приходится пересчитывать в границы отрезков.

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

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

Каждый логический блок содержит

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

50 первого триггера, второй выход которого соединен с первыми входами шестого, седьмого и восьмого элементов И, вторые входы второго, шестого и восьмого элементов И соединены с выходом перво- го элемента НЕ, вторые входы первого, третьего и пятого элементов И - с выходом второго элемента НЕ, второй вход

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

На фиг. 1 изображена функциональная схема предложенного устройства; на фиг. 2функциональная схема предпочтительного варианта реализации логического блока; на фиг. 3 - график, состояний логического блока.

Устройство содержит регистр 1 признака поиска, дополнительный регистр 2 признака поиска (каждый из регистров:1 и 2 имеет по m рpа з рpя доoвB, где m - целое число), первую и вторую группы накопителей 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 записываются нижняя граница Хми,4 о H длин КО входного отрезка

В процессе поиска отрезков, соседних с входным отрезком, информация из регистров 1 и 2 и накопителей 3 и 4 поступает на входы 9 — 11 блоков 5 и 6 поразрядно, начиная со старших разрядов.

В каждом блоке 5 и 6 при поступлении сигналов из j -ых разрядов регистров 1 и 2 и соответствующих накопителей 3 и щ

4 определяется значение tA) фиксируемое в виде определенного состояния блока 5 и 6. Значение (A"j . = О фиксируется в виде начального состояния (фиг. 3), 5A3j = -1 - в виде состояния clg . При 15 (А) Е(1, 2 блок 5 и 6 переходит в конечнбе состояние g<, при (А) Е $-2, 3 -

j в конечное состояние с, .

Каждое состояние блоков 5 и 6 кодируется определенным набором состояний gg триггеров 27 и 28: состояние с(кодируется набором (О, 0),4 — набором (О, 1), ñ1 -набором (1, О) и с(4- набором (1, 1).

Если блоки 5 и 6 находятся в состоянии 4<, то при поступлении на входы 9 -25

11 блоков 5 и 6 любого набора из множества сигналов перехода С„= $(0,0,0), (О, 1, 1), (1, 1, 0)) состояние не меняется, при поступлении набора Со (О, 1, О) блоки 5 и 6 переходят в промежуточное

:состояние О, кЪторое сохраняется при .

-поступлении. любого набора из множества

С>- (О,0, 1), (1, О, О), (1,, 1)) .

Из состояния 4 блоки 5 и 6 переходят в начальное состояние с „ под действием набора С4 = (1, О, 1). Любой набор из множества СЗ = СЬUС4 переводит блс ки 5 и 6 из состояния g в конечное состояние С 1, в которбм блоки 5 и 6 не реагируют на сигналы на их входах 9-11.О.

Под действием любого набора из множест ва С С10С блоки 5 и 6 переходят из состояния el a конечное состояние с(+ .

После анализа всех разрядов чисел, поступающих на входы 9 — 11 блоков 5 4 и 6, триггеры 27 и 28 находятся ".оответственно в единичном и нулевом состояниях, если Д =-1. При этом выходной сигнал элемента И 24, выход которого является вь-ходом 12 блоков 5 и 6, ра50 вен единице. Для 1 -ro блока 5 это означает, что Х мин -Хмин 0 " K4 =* 1 а

EBB 1 Î блока 6 что Х -Х „ „ +

+ К, = -1. Выходной сигнал Рлока 5 по» ступает на соответствующий детектор 7, 55 который фиксирует соседний сньзу отрезок. Выходной еигнал блока 6 поступает на детектор 8, который фиксирует соседний сверху отрезок.

02 6

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

Формула изобретения

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

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что каждый логический блок содержит элементы НЕ, элементы И, элементы ИЛИ и первый и второй триггеры, причем первые входы первого и второго элементов И подключены

7 9459 мого и третьи входы второго и шестого элементов И к входу второго элемента

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

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

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

1. Джозеф Каплан. Коррелирование . трасс целей с помошью памяти поиска.« .Зарубежная радиоэлектроника, 1964, No

2. Авторское свидетельство СССР

М 243659, кл. 5 11 С 15/00, 1966 (прототип) .