Блок поиска информации для ассоциативного запоминающего устройства

Блок поиска информации для ассоциативного запоминающего устройства

Иллюстрации

Показать все

Реферат

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ,3(sD 6.11 С 15/00

PQF;,",! Qqqe rq

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц..;,"„;.,";,":" .;,,3, Н АВТОРСКОМУ СВИДЕТЕЛЬС ГВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3454289/18-24 (22) 18,06.82 (46) 23,10.83. Бюл. И 39 (72) В.Б.Матвеев (71) Казанский ордена Трудового Крас" ного Знамени и ордена Дружбы народов авиационный институт им. А.Н.Туполева (53) 681.327(088.8) (56) I. Фостер К . Ассоциативные параллельные процессоры. М., Энергоиздат, 1981, с. 84, рис. 5.15.

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

Е 883972, кл. G 11 С 15/00, 1980 (гцзототип). (54) (57) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ

АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙ-.

СТВА, содержащий первый и втррой триггеры, элементы И с первого по восьмой, первый и второй элементы

ИЛИ, первый, второй и третий элементы НЕ, причем первые входы перво"

ro, второго и третьего элементов И, первые входы четвертого, пятого.и .шестого элементов И, первый вход седь мого и вторые входы четвертого и пятого элементов И, первый вход вось. мого и вторые входы первого и третье" го элементов И соответственно объединены и являются входами блока с первого по.четвертый, первый вход пер." вого элемента ИЛИ является .пятым входом блока, первые входы первого и, второго триггеров, вторые входы второго и восьмого и третий вход первого элемента Й соответственно объеди-. нены и являются шестым"и седьмым входами блока, восьмым входом которого является второй вход шестого. элемента И, выход первого элемента

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

Ф ч а ю щ е е с я тем, что, с целью расширения области применения блока эа счет увеличения числа критериев поисков, в него введены элементы И с девятого по двадцать третий, эле- . Я менты ИЛИ с третьего по пятый,третий триггер и элементы И-НЕ с первого по четвертый, причем первые входы девятого, десятого и одиннадцатого элементов И, первые входы ьф двенадцатого,. тринадцатого и четырнадцатого элементов И, первые входы р пятнадцатого, шестнадцатого и сем"надцатого элементов И первого элемент@ И-НЕ и второй вход четырнадцатого элемента И, первые входы восемнадцатого, девятнадцатого и двад- цатого элементов И и второго элемента И"НЕ и второй вход десятого элемента И, первые входы третьего .и четвертого элементов ИЛИ., первый вход третьего триггера подключены соответственно к входам блока с пер. ,вого по шестой, первые входы двад10499 цать первого, двадцать второго и двадцать третьего, второй вход седьмого, третьи входы пятого, шестого и четырнадцатого, и четвертый вход третьего элементов И и вход второго элемента HE подключены к седьмому входу блока, второй вход одиннадцатого и четырнадцатый вход второго элементов И и вход третьего элемента НЕ подключены к восьмому входу блока, второй вход двенадцатого, четвертый вход шестого и пятый вход второго элемента И и вход четвертого элемента НЕ, второй вход двадцать третьего, третий вход седьмого и четвертый вход первого элементов И, третий вход двадцать третьего и четвертый вход восьмого и четырнадцатого элементов И соответственно объединены и являются входами блока, с девятого по одиннадцатый выходом которого является выход пятого элемента ИЛИ, выход первого элемента НЕ и выходы элементов И-НЕ с первого по четвертый соединены соответственно с входами блока с седьмого по одиннадцатый., первый, второй, третий и четвертый входы пятого элемента ИЛИ подключены соответственно к выходам двадцать первого, двадцать второго и двадцать третьего элементов И и второму выходу второго триггера, подключенному также к входу первого элемента НЕ первый выход первого триггера подключен к вторым входам пятнадцатого и двадцать первого и третьему входу двенадцатого элементов И и первому в входу третьего и второму входу второго элементов И-НЕ, второй выход первого триггера подключен к пятому входу четырнадцатого элемента И, выход которого подключен к второму входу третьего триггера, третий вход которого подключен к выходу третьего элемента ИЛИ, второй, третий, четвертый и пятый входы которого подключены соответственно к выходам девятого, десятого, девятнадцатого и двадцатого элементов И, первый выход второго триггера подключен к вторым входам девятого, тринадцатого, шестнадцатого и девятнадцатого и третьему входу десятого элементов И и первому входу четвертого и второму входу тре-.. тьего элементов И-НЕ, первый выход третьего триггера подключен к вторым входам восемнадцатого и двадцать второго, третьему входу одиннадцатого,четвертым входам пятого и седьмого и пятому входу шестого элементов И и вторым входам первого и четвертого элементов И-НЕ, второй выход третьего триггера подключен к пятому входу первого элемента И, .выход второго элемента НЕ подключен к третьим входам девятого, тринадцатого, шестнадцатого и девятнадцатого, элементов И, выход третьего элемента НЕ подключен к второму входу двадцатого, третьему входу восемнадцатого и четвертым входам четвертого, двенадцатого и шестнадцатого элементов И, выход четвертого элемента

НЕ подключен к второму входу семнадцатого, третьему входу пятнадцатого и иетвертым входам десятого, одиннадцатого и девятнадцатого элемен" тов И, выходы тринадцатого, шестнадцатого и семнадцатого элементов И подключены соответственно к третье" му, четвертому и пятому входам перво. го элемента ИЛИ, а выходы одиннадцатого, двенадцатого,гнтнадцатого и восемнадцатого элементов И "îäêëþ÷åны соответственно к второму, третьему, четвертому и пятому входам четвертого элемента ИЛИ, выход которого подключен к третьему входу второго триггера.

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

Известен блок поиска информации для осуществления последовательного no разрядам ассоциативного поис2 ка, содержащий триггеры, элементы

И и элемент НЕ; причем первый вывод блока подключен к первому входу перcoro элемента И и входу элемента НЕ, выход которого подключен к первому входу второго элемента И, второй выявляется пятым входом блока, первые. входы первого и вторЬго триггеров, 3 1049 вод блока подключен к вторым входам первого и второго элементов И, а третий вывод блока подключен к первому входу третьего элемента И, второй !

1 вход которого подключен к выходу первого триггера, а выход подключен к входу второго триггера, выход ко" торого подключен к третьим входам первого и второго элементов И, выходы которых подключены соответствен 30 но к первому и второму входам первого триггера 11.

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

Наиболее близким к изобретению по технической сущности является блок поиска информации, содержащий триг;:. геры, элементы И, элементы ИЛИ и элементы НЕ, s котором первый вывод блока подключен к первым входам пер" вого.„ второго и третьего элементов

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

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

И подключен к второму входу перво" го триггера, третий вход которого подключен к выходу первого элемента

ИЛИ, а первый выход подключен к .:. 45 третьим входам второго, третьего и восьмого элементов. И, выход второго: элемента ИЛИ, первый, второй, третий, четвертый, пятый и щестой вхоФ ды. которого подключены .соответствен- .:.50 на к выходам второго, третьего, пя" . того, шестого, седьмого я восьмого элементов И, п одключен к второму входу второго триггера, первый вы". ход которого подключен к третьему S5 входу четвертого элемента И, выход . которого подключен к второму входу

nepsoro элемента ИЛИ f2) .

973 4

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

Цель изобретения - расширение области применения блока за счет вы.полнения поиска в массиве хранимых признаков (x,$, .1=1,п таких признаков x åI õ;, что д = <,<: I x„-÷j/ х,- (, где Y - признак опроса.

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

И с девятого по двадцать третий, элементы -ИЛИ с .третьего по пятый, третий триггер и элементы И-HE .с первого по четвертый,.причем первые

1049973

5 входы девятого,десято -о и одиннадцатого элементов Й,: первые входы двенадцатого, тринадцатого и четырнадцатого элементов И, первые .входы пятнадцатого, шестнадцатого и семнадцатого .элементов И и первого эле- . мента И-HE и второй-вход четырнадцатогц элемента И, первые входы во.семнадцатого, девятнадцатого и двадцатого элементов И и второго эле- . >0 мента И-HE и втором вход десятого элемента И., первые входы третьего и четвертого элементов ИЛИ, первый вход третьего триггера подключены соответственно к .входам блока с пер- 35 вого по.шестой, первые входы .дцадцать первого, двадцать второго и дцадцать третьего, второй вход .седьмого, третьи входы пятого, шестого и четырнадцатого и четвертый 20 вход третьего элементов И и вход второго элемента HE подключены к седьмому входу блока, второй вход одиннадцатый и четырнадцатый вход. второго элементов И и вход третьего г5 элемента НЕ подключены к восьмому входу блока, второй вход двенадцато- . го> четвертый вход шестого и пятый вход второго элементов И и вход четвертого элемента HE второй вход . дцадцать третьего, третий вход седьмого и четвертый вход первого эле-ментов И, гретий вход третьего и . четвертый вход восьмого и четырнадцатого элементов И соответственно объединены и являются входами блока с девятого по одиннадцатый, выходом которого является выход пятого элемента ИЛИ, выход первого элемента

HE и выходы элементов И-HE с перво- 40 го по четвертый соединены соответственно с входами блока .с седьмого по одиннадцатый, первый, второй, третий и четвертый входы пятого элемента ИЛИ подключены.соответственно к выходам дцадцать первого, двадцать второго и двадцать третье» го элементов И и второму выходу второго триггера, подключенному также к входу первого элемента НЕ, 50 первый выход первого триггера,подключен к вторым входам пятнадцатого и двадцать первого и третьему входу двенадцатого элементов И и первому входу третьего и второму входу второго элементов И-НЕ, второй выход первого триггера подключен к пятому входу четырнадцатого элемента И, выход которого подключен к второму б входу третьего триггера, третий вход которого подключен, к выходу третьего элемента ИЛИ, второй, третий, чет- вертый и пятый входы которого подключены соответственно выходам девятого, десятого, девятнадцатого и двадцатого элементов И, первый выход второго триггера подключен квторым входам девятого, тринадцатого, шестнадцатого и девятнадцатого ,и третьему входу десятого элементов

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

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

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

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

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

Блок поиска информации (фиг. 1) содержит элементы И 1"23, элементы

ИЛИ 24-28, элементы НЕ 29-32, элемснты И-НЕ 33-36, и первый 37, вто7 1 рой 38 и третий 39 триггеры. Блок .имеет входы 40-50 и выход 51.

Ассоциативное запоминающее уст" ройство (фиг. 2) содержит блоки 52 поиска информации, регистр .53 признака, опроса, регистры 54 хранимых признаков;. Первые 40 и вторые

41 входы всех блоков подключены соответственно к первому и второму выходам регистра 53 признака,а тре" тий 42 и четвертый 43.входы каждо" го блока подключены к двум выходам одноименного регистра 54. Входы ..46-50 всех блоков подключены через резисторы 55 K источнику 56 опор- ного напряжения, Пятые входы 44 всех блоков подключены к входу 57начальной установки, а шестые вхо-. ды 45 всех блоков подключены к вхо.ду 58 синхронизации. Выходы 51 всех блоков являются логическими выхода .ми устройства.

График переходов ассоциативного блока (фиг. 3) имеет пять вершин .59-63. Под номерами вершин приведены коды состояний блока, в которых двоичные цифры соответствуют . (слева направо) состояниям третье го 39, первого 37"и второго 38 триггеров.

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

В исходном состоянии сигналом по входу.57 все блоки 52 устанавливаются в состояние 59.

Ассоциативный поиск производится. за m- тактов поразрядного сравнения (m -разрядность признаков). В каждом такте на блок 52 по входам 40 и 41 поступают соответственно иняерс ное и. прямое .значения текущего раз" ряда признака опроса, а по входам

42 и 43 - соответственно инверсное и прямое значения текущего разряда одноименного хранимого признака.

Эти сигналы поступают в порядке убы. вания их весов.

В зависимости от предыдущего

j -1 -го состояния блока 52 и значений текущих j-x разрядов признака опроса и одноименного хранимого признака, а также в зависимости от

j-1-х состояний остальных блоков 52 и значений текущих разрядов. призна" ков на их выходах, на установочных. входах триггеров i-ão блока 52 вырабатываются следующие сигналы: Sy", u Rq; на входах первого 37, S ; и Rp1

049973 8 на входах второго 38 и 5„", и R< >,на входах третьего 39 триггеров, кото- рые определяются следующим образом: (-" " С, - б„;=;; (; в;с,. а„,.,; б "=Х ч Х15Y;E;) 7

t5 ; =Тч Х< Е ч@з,, (Ч Сч Х;; ;П v

«Х,.,Ч, 5ij = "С 2, 1 1(Х;.1 Ejч Yj33 ).1) ч где х, 1 - значение,g --ro разряда i-ro

25 хранимого признака; y> - значение

j-го разряда признака опроса;

Q, и Q, < - текущие состояния первого 37, второго 38 и третьего 39 триггеров,".Т - сигнал начальной установки, а А1, З.j, С ., D j и Е1 определяются следующим образом:

А.=QЛ . Я

31,j-t .

8j = V Q2j Ji 3 qadi)1 1

35 с =.ч д

1 "1 )

I о =.ч х„ g„

E; =yx„„g ;-,, .

При поступлении сигнала на вход

45 58 в триггерах 37-39 фиксируются новые, j --e состояния блоков 52. и на чинается j+E-й такт поиска.

Результат поиска. определяется. состояниями всех триггеров 37-39. блоков 52..Появление сйгнала С,; на ; выходах 51 некоторых блоков 52 в результате последнего такта. поиска 3ат (hi " я т tnt Nit m41ст

55 означает, что одноименные хранимые признаки удовлетворяют условию по иска.

1049973, ip

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

3049973

Фиа2

1049973

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

Редактор 0.4ерниченко Техред ц.Тепер

Корректор Т.Вашковичфилиал ППП "Патент", r. Ужгород, ул. Проектная, Заказ 8436/49 Тираж 594. Подписное

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

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