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

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

Иллюстрации

Показать все

Реферат

 

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

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

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 030178(21) 2566755/18-24 с присоединением заявки 11о — . (23) Приоритет

Опубликовано 25.05.80. Бюллетень М 19

Государственный комитет

СССР по делам нзобретеннй н открытий

Дата опубликования описания 288580 (72) Авторы изобретения

В.М.Трусфус и В.Б.Матвеев (71) Заявитель казанский ордена Трудового Красного Знамени авиационный институт им. A.Í. Туполева (5 4 ) АССОПИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

Изобретение относится к запоминающим устройствам.

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

Недостаток этого устоойства — отсутствие воэможности поиска по экстремальным условиям без применения алгоритмов, требующих многократного О обращения к устройству.

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

Недостатком этого устройства является повышенная сложность и понижение быстродействия вследствие последовательной организации межразрядной обратной связи. 25

Пель изобретения — упрощение устройство и повышение его быстродействия, Эта цель достигается тем, что ycr ройство содержит блоки обратной свя- 30 зи,одни входы каждого из которых подключены к одноименным первым разрядным шинам, а выходЫ вЂ” к предыдущим вторым разрядным шинам и к другим входам предыдущих блоков обратной связи.

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

Пусть в некотором запоминающем устройстве содержится n m разрядных слов, в которых записаны ассоциатив-. ные признаки

Х Х4 Х Г" Х," Х (1С1 -",н), а также имеется регистр, содержащий

m-разрядный признак опроса:

Примем, что старшие разряды— первые и номера разрядов. возрастают в порядке убывания их веса.

При экстремальном поиске характер ассоциативных связей между признаками выявляется в процессе самого поиска, т.е. он требует сравнения ассоциативных признаков как с признаком onроса, так и между собой.

736171

Полностью параллельная реализация экстремального поиска требуе наличия рас пределительной логики (t}xm блоков сравнения, связанных с соотнетствующими признаками разрядами), и, наряду с е}азрядными и межраэряд}161 ие обратныл}}! связями, наличия

t}ðÿûIõ межразрядных связей между логическими выходами предыду((их H логическими входами последую!}их в слонах блоков сравнения.

Обозначим Е ° — сигнал на первом

1 3 логическом выходе -того /на первом логическом входе j +1-ого) блока оран н нения i òîãî слова; Е; — сигнал на втором логическом выходе -того (на втором логическом входе ) +1-oro) блока сравнения i òîãî слова, и будем называть сон падением выполнение в не Ko" Ор0;,I блntca- с —,,=!D!iе}lиct г0}HЧPсK0й ф: нкции блоков сравнения образуется в тех словах, где первое (старшее} в дан— ном слове положительное несонпаде— ние, при условии совпадения во всех п)редыду((их разрядах, наступило не ранее,. чем н любом другом слове: — 1I} 1(К-1} 1}; .. „11 1(j })

1-.1 }=К

II

Единица Z„ =1 не образуется ни в одном слове, если все слова либо равны признаку опроса, либо мен ttte (при поиске ближ айше го большего) или боль— ше приз н ак а опроса (при поиске бли— жайшего меньшего), Единица мо)кет образоваться в одно— именных К-тых разрядах нескольки слов (это означает, что старшие К паз ряе!он хранимых ассоциативных признаков равны) . Однако последую*: ие разряды признаков могут быть раэ—

ЛИЧН61МИ, }-.=х. (, х,. (.

"} () 1 1} } (1)

При поиc«e по условиям бли)кайн(ее большее и наименьшее будем

itàçt aaòü положительным несовпадением

I-.t t}I0sIH EIi}Ic в некотором блоке сра вн ен и я 4) }," }1 к ц и 11

Сигнал Z (C)K} равен 1 в

i() тех словах, где

Z4 ((. 1!

2) в ланном разряде имеет-место приоритет. (2) а приоритетои — < )ун кции

1,. = х)- "1 u x . Я. = х .

1) 1) } .j j 1}

Если пп. 1 и 2 (ota} не выполня— ются ни в одном слове, то Z,e =1 во всех слонах, где выполняется условие и. 1: (3) При поиске по условиям ближайв!ее менывее и наибольшее соответствую!цие Функции: (2 ) Объеди н я я процессы образования

П и распространения единицы 7,;1 =1 полу чи м: (3 ) (.} ., р 1 1р 1(р }!

С .гнал Zг,. равен 1 в ( словах, где во всех i предыдч рядах зафиксировано сог.паден та«как задача сосТОНТ н расп нии исходного rttгнала 1 ( для любого 1):

1 .(} 21()-1.} 11

4(} т е }к

11!и х р а 3— ие, ростране} ). ) и

} (7)

}:1

4$ (4) 1 си гн ала Е;„, =1 означает, вую}чий ассоциативный признаку опроса, а

=-1, Ето он является ьшим (меHüøèì), HO не

Появление

Ето соотнетст признак равен и сигнал Z.;Ií ближайшим бол равным.

Для аппаратной реализ ации з кстремал ьно го пои с к а необходимо по строить комбинационнуKI логическую сеть,. реализуюшую для каждого разряда функции (4) и (7) .

B данном устройстне, в отличие от известного, реализован сквозной перенос си гн ала

=4(17 7„1, „} р=! 1Р (Р " фи г, 1 изображ.-}на е тру кт урн ая схема ассоциативного заполз} наю})}е го

Он ачен и е c«} H aëa Е"„. определ як)т два п}зоцесс а: образование един и ч}!ого сигнала и егo распространение. э(3

Единица на втором логическом выходе К-того блока сравнения (Kt.l, In } -того сло-а образуется в том се}у чае, если

1) Z„,„., =1, т.е. во всех предыду}}1}(х разрядах зафиксировано совпадение.

2) в дан to}c) разряде имеет место по— лсякительное несовпадение;

3) среди остальных (п — 1} слов нет таких, в которых укаэанные в пп. } и t()G

2 ограничения (оба) выполнялись бье н последуюших (младших) (m-к) оа=-— реедах, Таким образом, единица на втором логическом выходе соответствуюших (} 5

73617) (О

tL i<

2,() 11Х1 =и

1V с(-2 )Х ° . (6.

30

40 (9) у.=.rр.иста-> (r.åý целей записи, считывания), на <Ьиг.2 — функциональная схема блоков сравнения.

Устройство (фиг ° 1) содержит п х m элементов 1 памяти, выходы 2 которых присоединены к приэчаконым входам соответствующих блоков 3 сравнения, межразрядные шины 4, соединяющие логические выходы и входы предыдущих и, соответственно, последующих блоков сравнсния (m-1) первых 5, m вторых 6, m третих 7, m четнертых

8 разрядных шин и (m — 1) блоков обратной связи, например, элементов И 9, одни нходы которых подключены к одноименным первым разрядным шинам 5, а выходы присоединены к предыдущим вторым разрядным шинам 6 и к другим входам предыдущих блоков 9 обратной связи.

Межразрядные 4 и четвертые разрядные шины 8-двухфазные. Каждый блок 3 сравнения (фиг.2) представляет собой комбинационную логическую схему,содержащую элементы И 10-14,элементы ИЛИ 15 и 16 и элементы HE 17 и 18 и имеет первый 19 и второй 20 входы опроса, первый 21 и второй 22 логические входы, первый 23 и второй 24 логические выходы, выходы разрядной 25 и межразрядной 26 обратной связи, входы разрядной 27 и межразрядной 28 обратной связи и первый 29 и второй

30 входы опроса.

Устройство работает следующим образом.

Запись и считывание в устройстве могут быть организованы любым из известных способов.

При поиске ближайшего большего (наименьшего) в исходном состоянии на первый 19 и второй 20 признаконые входы 3 -того блока 3 сраннения i-того слова поданы прямое и инверсное значения Х;. и Х„ соответствующего ассоциативного приз— нака, а на первый 29 и второй 30 входы опроса поданы прямое и инверсное значения 1 и Э j-òîãî разряда признака опроса, Предположим, что на первый 21 и второй 22 логические входы поданы сигналы Z,"(,) и

2;(),определенные согласно формулам (4) и (6),на вход разрядной обратной связи 27 подан сигнал а на вход межразрядной обратной связи — си гн ал S.

Р определенный согласно (8) .

Тогда на первом 23 и втором 24 логических выходах реализуются функции, соответственно:

„() 1) 13 (1" Х ) 1

i< i а =Е„. ° 1)Х„.. .В. 1ч

ii г;(; „)(х. чн)) Учитывая (1) — (4), (7) — (9) получим

4 << Ф, а =Е „. и а =Е„ > . На выходе разрядной обратной связи 25 реализована функ1иЯ третья разрядная шина 7 выполняет функцию монтажного И, поэтому сигнал на ней т.е.предположение о сигнале на входе разрядной обратной связи 27 справедливо.

На выходе межразрядной обратной связи 26 реализована функция первая разрядная шина 5 выполняет функцию монтажного И, поэтому сигнал на ней

l<

" т (1,Х„., 1

Можно показать, что сигнал на выходе соответствующего блока обратной связи 9 и является сигналом на входах межразрядной обратной связи 28 (g — 1)-ых блоков S равнения, что также подтверждает сделанное выше предположение.

Для полного соответствия математической модели (4) и (7) и аппаратной реализации экстремального поиска необходимо определить начальные условия. Так как признаки имеют m известных разрядов, следует считать, что незаданные разряды, старшие первого и младшие m-того, равны у всех признаков, откуда следует, что

8щб

Z = Z " =0 Для любОГО о о т.е. при поиске на второй вход последнего блока 9 обратной связи (на последнюю третью разрядную шину 7) и на первые логические входы 21 первых блоков 3 сравнения должны быть поданы логические 1, а на вторые логические нходы 22 первых блоков 3 сравнения — логические 0 . 0 Описанное устройство, кроме общего с известным устрОйстВОМ оборудования, содержит (m-1) элементов И, которые в аппаратном отношении заменяют n (m-1) элементов ИЛИ и n (m-1) элементов НЕ, т.е.оно проще изнест736171 ного. также оно является и более быст роде и от в ующи м.

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

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

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блоки обратной св язи. выполнены в виде элементов И, входы и выходы которых подключены к соответствующим входам и выходам блоков обратной связи, tО

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

1, Авторское свидетельство СССР

V 2778»7, кл.С 11 С 15/00, 1970.

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

9 564656, кл.G 11 С 15/00, 1975 (про15 тоти п), /36 171 фиг.2

Составитель В. Рудакова

Редактор В. Зарванская Техред N.Êóýüìà Корректор Г. Назарова

Заказ 2278/8 Тираж 662 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб.,д.4/5

Филиал ППП Патент, r.Óæãoðîä, ул.Проектная,4