Ассоциативное запоминающее устройство
Союз Советских
Социалистических
Республик
ОП И
ИЗОБРЕТЕНИЯ
<н780043
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6 t ) Дополнительное к звт. свид-ву— (51)М. Кл. (22) Заявлено 06.12.78 (21) 2694300/18-24
G 11 С 15/00 с присоединением заявки Мо— (23) Приоритет—
Государственный комитет
СССР но делам изобретений и открытий
Опубликовано 15.1180, Бюллетень Мо 42
Дата опубликования описания 181180 (53) УДК 681. 327 (088.8) В.М.TpycAyc, B.Á.Èàòâååâ и Т.Г.Мартынюк (72) Авторы изобретения
Казанский ордена Трудового Красного Знамени авиационный институт игл. А.Н.Туполева (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО
Изобретение относится к области запоминающих устройств.
Известно ассоциативное запоминающее устрсйство, содер>кащее запоминающие регистры, регистр опроса, 5 детекторы и компараторы (1 .
Недостатком этого- устройства является ограниченный набор условий поиска.
Наиболее близким техническим 10 решением к данному изобретению является ассоциативное запоминающее устройство, содержащее накопитель, входы которого подключены к выходу регистра опроса и первому выходу блока 15 управления, второй выход которого соединен с входом регистра опроса, разрядные шины (21 .
Недостатком этого устройства является большое количество оборудования 2П и пониженг.:ое быстродействие. В устройстве подсчитываются разности между ассоциативными признаками и признаком опроса в целом, что и приводит к указанным недостаткам. 25
Целью изобретения является упрощение устройства и повышение его быстродействия.
Поставленная цель достигается тем, что устройство содержит группы эле- Зп ментов И, блоки местного управления, дополнительные накопители и блоки вывода результата поиска — по числу запоминающих ячеек накопителя, причем входы дополнительных накопителей подключены к выходам соответствующих блоков местного управления, а выходы соответственно к входам блоков вывода результата поиска, одним из входов элементов И и входам первой группы блоков местного управления, разрядные шины соединения с выходами элементов И и входами второй группы блоков местного управления, другие входы элементов И и входы третьей группы блоков местного управления подключены к выходам накопителя, третий выход блока управления соединен с выходами четвертой группы блоков местного управления.
При этом блок местного управления может содержать элементы И и элеМенты ИЛИ, выходы которых являются выходами блока местного управления, а выходы элементов ИЛИ подключены к выходам элементов И, входы которых являются входами блока местного управления.
Блок вывода результата поиска может содержать элемент И и элемент
780043
ИЛИ, причем первый вход элемента И и входы элемента ИЛИ являются входами блока вывода результата поиска, а выход элемента ИЛИ соединен с вторйм входом элемента И, выход которого является выходом блока вывода результата поиска.
Пусть задано множество двоичных ассоциативных признаков Х = j х, ), где
Х Х„„)<„ . Х,, ) - )>и и признак опроса Y = 3„ 9р," 9, и требуется найти некоторый признак
Аxá х такой, что МГ = I,п: (Xx Ф"Y)А (1Х„- <1 ) Х б -
Введем величину D„.(j)= Х„.<))-Y <<), где )<„(j) =Х„. „Х„....,х,, (()) =У„,...,Ч, t0 и величи- 20 ну д„ (j ) =)J3, 10 в противном случае. Можно показать, что при ассоциативном поиске невыполнение определенных ограничений на величины Р„ ()) и д„. Напротив, признаки, не нарушившие ограничений по Э„ ()) .и с)„ () ни на каком шаге, а также ограниче- ний по Э,(м)и<3„. (и) (после m шагов) удовлетворяют данному признаку опроса по данному условию. Из данного определения "ближайшего" следует (x „- — "ближайший" к Y)= -(V(.:t.(d. < (чи) 0)л(Э„<и ) Ф03). (у) ф) Тогда справедливо: М :Ц )В,j:t t,))„(j) >О) ())(i)>О (3<,Е<))>О1Ч Ч(()) ())аО) л (Э <)) О) (d; < ()) >О) ) Ч ч((Э() 0) л(2 1)) 0) - (dq g < j)>0)lV { ) 45 <(dq g(j) > 2) l5 < (В„ (» = 0) Из (2) следует, что для поиска "ближайшего" достаточно на каждом шаге производить: 1)выделение ассоциативных признаков больших и меньших признаков опро55 са, 2)поиск наименьшего среди больших и наибольшего среди меньших (остальные, кроме равных, блокируются, т.е. исключаются иэ дальнейшего рассмотрения); 3) фиксацию двух значений 1 . ()) t I D„. 4) фиксацию двух значений d„- dÄ. () > 2. блокируются. Среди незаблокированных после m шагов поиска могут быть три разных признака: X — "равны" X — "ближайший больший" и X — "ближайший меньший"(или по нескольку совпадающих), В свою очередь,Х и X могут быть либо равноотстоящими от признака опроса (тогда d+ (v)= d (щ)=0), либо один,из них например Х ближе на единицу, т.е. д . (и ) =<, d< 0. , н Таким образом, "ближайшим" после всех m шагов является незаблокированный признак (или признаки), у когорого Ъ (м) 0 и д„(и) =0 На фиг. 1 изображена структурная схема устройства, на фиг. 2 — предпочтительный вариант выполнения части устройства, относящейся к одному признаку. Устройство содержит (c:м,фиг.1) накопитель 1, в состав которого входят и запоминающих регистров 2, регистр 3 опроса, разрядные шины 4, группы 5 элементов И, и блоков б местного управления, и дополнительных накопителей 7, и блоков 8 вывода результата, блок 9 управления. В состав накопителя 1 входит также и схем 10 разрядного сравнения. Входы накопителей 7 подключены к выходам соответствующих блоков 6, а выходы — соответственно к входам блоков 8, одним из входов элементов И группы 5 и входам первой группы блоков 6, разрядные шины 4 соединены с выходами элементов И группы 5 и входами второй группы блоков б, другие входы элементов И группы 5 и входы третьей группы блоков б подключены к выходам накопителя 1. ПриЧем, второй и третий выХОды блока 9 подключены соответственно к входам накопителя 1, регистра 3 опроса и выходам четвертой группы блоков б. Блок 6 (см.фиг.2) имеет шину 11 начальной установки и шину 12 синхронизации. Блок 7 сбдержит триггеры 1317. Каждая группа 5 элементов И со-., цержит отдельные элементы И 18. Блок б содержит элементы И 19 и 20 (элементы И 20 выполнены с одним инверсным входом), элементы ИЛИ 21, выходы которых являются выходами блока б. Выходы элементов ИЛИ 21 подключены к выходам элементов И 19 и 20, входы которых являются входами блока б. Схема 10 содержит элементы НЕ 22. На входы 23 и 24 блока 10 подаются сигналы б „ и,<<;, где 81 х,.) 3) << х,3 )j Блок 8, имеющий выход 25, являющийся выходом устройства, содержит элемент И 26 и элемент. ИЛИ 27. Первый вход элемента И 26 и входы элемента 780043 ИЛИ 27 являются входами блока 8, а выход элемента ИЛИ 21 соединен с вто1 рым входом элемента И 19, выход которого является выходом блока 8. Устройство работает следующим образом. В запоминающие регистры 2 накопи-. теля 1 заносятся ассоциативные признаки. Для каждого признака результаты сравнения текущего разряда и соответствующего разряда признака опроса поступают со схемы 10 разрядного сравнения на входы элементов И групп 5 и блоков б. Сигналы с их выходов подаются соответственно на восемь разрядных шин 4 на входы пяти триггеров 13-17 накопителя 1. Состояния триггеров 13-17 управляют элементами И групп 5 и блоками 6. На выходе 25 блока сигнал является логической функцией состояний триггеров 13-17 и означает, что данный признак — "ближайший" на данном шаге сравнения. В зависимости от функциональных особенностей накопителя 1 на вход схемы 10 разрядного сравнения могут поступать на каждом шаге либо сигналы Х1), х„. » Ч9 ) или часть их, если регистры 2 и 3 являются сдвиговыми регистрами или используется накопитель 1 (и ре-. гистр 3) с поразрядным считыванием, либо сигналы д1, Х" 1 1как показано на фиг. 2) или сигналы 1 >+1 1 1, 61 (тогда блок 10 отсутствует), если запоминающие регистры 2 обладают свойством граничного ассоциативного поиска. Поиск "ближайшего" осуществляется за m тактов, т.е. его время линейно зависит от разрядности признаков, в отличие от степеней зависимости в известном устройстве L2) . Количество единиц оборудования (не считая накопителя 1) не зависит от m, в известном устройстве f2) имеется логарифмическая (при достаточно больших m) зависимость. Таким образом> описанное устройство проще и обладает повышенным быстродействием. Формула изобретения 1. Ассоциативное запоминающее устройство, содержащее накопитель, вхбды которого подключены к выходу регистра опроса и первому выходу блока управления, второй выход которого соединен с входом регистра опроса, разрядные шины, о т л и ч а ю щ е ес я тем, что, с целью упрощения устройства и повышения его быстродействия, оно содержит группы элементов И, блоки местного управления, дополнительные накопители и блоки вывода результата поиска — по числу запо10 минающих ячеек накопителя, причем входы дополнительнйх накопителей подключены к выходам соответствующих блоков местного управления,а выходы— соответственно к входам блоков вывода 15 результата поиска, одним из входов элементов И и входам первой группы блоков местного управления, разрядные шины .соединены с выходами элементов И и входами второй группы блоков местноу0 го управления, др I He Bxo+b1 BJIeMeHтов И и входы третьей группы блоков местного управления подключены к выходам накопителя, третий выход блока управления соединен с выхо- дами четвертой группы блоков мест- ного управления. Устройство по п.1, о т л ич а ю щ е е с я тем, ято блок местного управления содержит элементы И и элементы ИЛИ, выходы которых являются выходами блока местного управления, а входы элементов ИЛИ подключены к выходам элементов И, входы которых являются входами блока местного управления. 3. Устройство по пп. 1 и 2, о т л и ч а ю щ е е с я тем, что блок вывода результата поиска содер>кит элемент И и элемент ИЛИ; причем первый вход элемента И и входы элемента ИЛИ являются входами блока вывода результата поиска, а выход Элемента ИЛИ соединен с вторым входом элемента И, выход которого является выходом блока вывода результата поиска. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР Р 277857, кл. G 11 С 15/00, 1968. 2.Авторское свидетельство СССР Р 332502, кл. G 11 С 15/00, 1970 (прототип).
