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

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

Изобретение относится к области запоминающих устройств. . Известно ассоциативное запоминающее устройство, содержащее запоминающие регистры, регистр опроса, детекторы и компараторы 1. Недостатком этого- устройства является ограниченный набор условий поиска. Наиболее близким техническим решением к данному изобретению является ассоциативное запоминающее устройство, содержащее накопитель, входы которого подключены к выходу регистра опроса и первому выходу блока управления, второй выход которого соединен с входом регистра опроса, разрядные шины . Недостатком этого устройства явля ется большое количество оборудовани и пониженное быстродействие. В устройстве подсчитываются разности межд ассоциативными признаками и признако опроса в целом, что и приводит к ука занным недостаткам., Целью изобретения является упроще ние устройства и повышение его быст родействия. Поставленная цель достигается тем что устройство содержит группы элементов И, блоки местного управления, дополнительные накопители и блоки вывода результата поиска - по числу запоминающих ячеек накопителя, причем входы дополнительных накопителей подключены к выходам соответствующих блоков местного управления, а выходы соответственно к входам блоков вывода результата поиска, одним из входов элементов И и входам первой группы блоков местного управления, разрядные шины соединения с выходами элементов И и входами второй группы блоков местного управления, другие входы элементов И и входы третьей группы блоков местного управления подключены к выходам накопителя, третий выход блока управления соединен с выходами четвёртой группы блоков местного управления. При этом блок местного управления может содержать элементы И и элементы ИЛИ, выходы которых являются выходами блока местного управления, а выходы элементов ИЛИ подключены к выходам элементов И, входы которых являются входами блока местного управления. Блок вывода результата поиска может содержать элемент И и элемент

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

Пусть задано множество двоичных ассоциативных признаковх- J., где

,,2-- -.v, И J.

И признак опроса X и требуется найти некоторый признак такой, что VE-1,nUX)t)л ().)т.e. ближайший к признаку опроса. Примем,i что старшие разряды - первые и номера разрядов возрастают в порядке убывания их веса.

.Введем величину Ю (-j) - (j )-Y (j ), где ...,х...-,-,

J-- величину i)4|OiCo)) ecлиD,(p,Dp( (о - в противном случае. :.-:-.- -/ .

Можно показать, что при ассоциативном поиске невыполнение определенных ограничений на величины D (j) и tj/ f зависящих от конкретного условия поиска, на любом его шаге, влечет исключение i-го ассоциативного признака из числа признаков, которые могут удовлетворять данному признаку опроса.

Напротив, признаки, не нарушившие ограничений по D ( и di,e(j) ни на каком шаге, а также ограничеНИИ по ) (VM) (после m шагов) удовлетворяютданному признаку опроса по данному условию.

Из данного определения ближайшего следует (х - - ближайший кУ) .l(cli,e(.v«)50)(vv,)o. ({) Тогда справедливо: vv.(i)o(T)eCi)o-(d,

vt(DH(jHO)ACDg(j)0)(j)0)v

()()gtj)-0)-((3)0)v {2) (d,j(.j)i2)v(D, (b1)--0)(a,-(n)o)l-:(vi€lЬX . . где В - множество признаков, не удовлетворяющих данному признаку , опроса по условию ближайший, ВсХ.

Из (2) следует, что Для поиска ближайшего достаточно на каждом шаге производить:

1)вьщеление ассоциативных признаков больших и меньших признаков опро са; .

2)поиск наименьшего среди больших и наибольшего среди меньших (остальные, кроме равных, блокируются, т.е. исключаются из дальнейшего рассмотрения);

3)фиксацию двух значений Pi(j/| | D. (.j)j -( и |D(j) i

4)фиксацию двух значений a(,-fj/ и a(j)-1.

где )-м,сшс dijE. t Р , признаки с d(-j) % 2 б7Гокируются.

Среди незаблокированных после m шагов поиска могут быть три разных признака: Хр - равны, Xj- - ближайший больший и )(f - ближайший меньший (или по нескольку совпадающих) . В свою очередь J сГ л могут быть либо равноотстоящими -от признака опроса (тогда (yM))-0), либо оди11 из них например ближе на единицу, т .е. 6 J-()-I, .

Таким образом, ближайшим после всех m шагов является незаблокированный признак (или признаки), у которого ) 0 и d (rt)-0

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

Устройство содержит (с;м.фиг.1) накопитель 1, в состав которого входят п запоминающих регистров 2, регистр 3 опроса, разрядные шины 4, группы 5 элеменЧов И, п блоков б местного управления,п дополнительных накопителей 7, п блоков 8 вывода результата, блок 9 управления

8состав накопителя 1 входит также И схем 10 разрядного сравнения. Входы накопителей 7 подключены к выходам соответствующих блоков 6, а выходы - соответственно к входам блоков 8, одним из входов элементов И группы 5 и входам первой группы блоков 6, разрядные шины 4 соединены с выходами элементов И группы 5 и входами второй группы блоков б, другие входы элементов И группы 5 и входы третьей группы блоков б подключены к выходам накопителя 1. Придем, второй и третий выходы блока

9подключены соответственно к входам накопителя 1, регистра 3 опроса и выходам четвертой группы блоков б. Блок б (см.фиг.2) имеет шину 11 начальной установки и шину 12 синхронизации. Блок 7 содержит триггеры 1317. Каждая группа 5 элементов И со-., держит отдельные элементы И 18. Бло б содержит элементы И 19 и 20 (элементы И 20 выполнены с одним инверсным входом), элементы ИЛИ 21, выходы которых Являются выходами блока б Выходы элементов ИЛИ 21 подключены

к выходам элементов И19 и 20, входы которых являются входами блока б.

Схема 10 содержит элементы НЕ 22. На входы 23 и 24 блока 10 подаются сигналы сЯ| и JU , где

сУ--к,-, ,

Блок 8, имеющий выход 25, являющийся выходом устройства, содержит элемент И 26 и элемент. ИЛИ 27. Первый вход элемента И 26 и входы элемента

ИЛИ 27 являются входами блока 8, а выход элемента ИЛИ 21 соединен с BTO рым входом элемента И 19, выход которого является выходом блока 8. Устройство работает следующим образом,

В запоминающие регистры 2 накопителя 1 заносятся ассоциативные признаки. Для каждого признака результаты сравнения текущего разряда и соответствующего разряда признака опроса поступают со схемы 10 разрядного сравнения на входы элементов И групп 5 и блоков 6. Сигналы с их выходов подаются соответственно на восемь разрядных шин 4 на входы пяти триггеров 13-17 накопителя 1. Состояния триггеров 13-17 управляют элементами И групп 5 и блоками 6. На выходе 25 блока сигнал является логической функцией состояний триггеров 13-17 и означает, что данный признак - ближайший на данном шаге сравнения.

В зависимости от функциональных особенностей накопителя 1 на вход схемы 10 разрядного сравнения могут поступать на каждом шаге либо сигналы

-iiV j

или часть их, если регистры 2 и 3 являются сдвиговыми регистрами или используется накопитель 1 (и ре-. гистр 3) с поразряднь;1м считыванием, либо сигналы

OV, (как показано на фиг. 2)или сигналы

,1,0.

(тогда блок 10 отсутствует), если за:поминающие регистры 2 обладают свойством граничного ассоциативного .поиска.

Поиск ближайшего осуществляется за m тактов, т.е. его время линейно зависит от разрядности признаков, в отличие от степеней зависимости в известном устройстве 2 Количество единиц-оборудования (не .считая накопителя 1) не зависит от m, в известном устройстве 2 имеется логарифмическая (при достаточно больших т) зависимость. Таким образом, описанное устройство проще и обладае повышеннЕом быстродействием.

Формула изобретения i.Ассоциативное запоминающее устройство, содержащее накопитель, вхбды которого подключены к выходу регистра опроса и первому выходу блок управления, второй выход которого соединен с входом регистра опроса, разрядные шины, отличающеес я тем, что, с целью упрощения устройства и повышения его быстродействия, оно содержит группы элементов И, блоки г естного управления, дополнительные накопители и блоки вывода результата поиска - по числу запоминающих ячеек накопителя, причем входы дополнительнШс на:копигёЛей подключены к выходам соответствукЛдих блоков местного управления,а выходы соответственно к входам блоков вывода результата поиска,одним из входов элементов И и входам первой группы блоков местного управления, разрядные шины соединены с выходами элементов И и входами второй группы блоков местного управления, другие входы элементов И и входы третьей группы блоков местного управления подключены к выходам накопителя, третий выход блока управления соединен с выходами четвертой группы блоков местного управления..

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

80043