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

 

Изобретение относится к вычислительной технике и позволяет осуществлять граничный ассоциативный поиск в массивах данных. Цель изобретения - расширение области применения блока поиска информации для ассоциативного запоминающего устройства за счет выполнения граничного поиска среди чисел , представленных в кодах Фибоначчи. Блок представляет собой конечный автомат , имеющий семь внутренних состояний , содержит четыре триггера 1-4, одиннадцать элементов И 5-15 шесть элементов ИЛИ 16-21 и два элемента НЕ 22 и 23. Входы 24 и 26 блока подключаются к выходам соответствующего регистра хранимого признака ассоциативного запоминающего устройства (АЗУ) Входы 27 и 25 блока подключаются к выходам регистра признака опроса АЗУ. Коды признаков поступают в блок побитно, начиная со старших разрядов. По входам 28 и 29 подаются сигналы синхронизации и начальной установки. Уровнями логической единицы на ,рдах 30- 34 Отмечаются хранимые признаки, которые меньше, больше или равны, больше, меньше или равны, равны по отношению к признаку опроса. 3 ил., 1 табл. i с со О) СП Фиг.1 гв

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„,SU 1336115 А1 (5ц 4 G 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4061241/24-24 (22) 28.04.86 (46) 07.09.87. Бюл. У 33 (71) Казанский авиационный институт им. А.Н. Туполева (72) В.Б. Матвеев и А.Н. Никонов (53) 681.327(088 ° 8) (56) Авторское свидетельство СССР

У 1153359, кл. G 11 С 15/00, 1983;

Фостер К.Ассоциативные параллельные процессоры. Перев. с англ. M.:

Энергоиздат, 1981, с. 75. (54) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА (57) Изобретение относится к вычислительной технике и позволяет осуществлять граничный ассоциативный поиск в массивах данных. Цель изобретения расширение области применения блока поиска информации для ассоциативного запоминающего устройства за счет выполнения граничного поиска среди чисел, представленных в кодах Фибоначчи.

Блок представляет собой конечный автомат, имеющий семь внутренних .состояний, содержит четыре триггера 1-4, одиннадцать элементов И 5-15, шесть элементов ИЛИ 16-21 и два элемента

НЕ 22 и 23. Входы 24 и 26 блока подключаются к выходам соответствующего регистра хранимого признака ассоциативного запоминающего устройства (АЗУ)

Входы 27 и 25 блока подключаются к выходам регистра признака опроса АЗУ.

Коды признаков поступают в блок побитно, начиная со старших разрядов. По входам 28 и 29 подаются сигналы синхронизации и начальной установки. Уровнями логической единицы на выходах 30-.

34 отмечаются хранимые признаки, которые меньше, больше или равны, больше, меньше или равны, равны по отношению к признаку опроса. 3 ил., 1 табл.

13361

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

Цель изобретения — расширение об5 ласти применения блока за счет выполнения граничного поиска среди чисел, представленных в кодах Фибоначчи.

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

Блок поиска информации (фиг. 1) содержит триггеры 1-4 с первого по четвертый, элементы И 5 — 15 с первого по одиннадцатый, элементы ИЛИ 16-21 с первого по шестой, первый 22 и второй 23 элементы HE входы 24-29 .блока поиска информации с первого по шестой и выходы 30-34 блока с первого по пя25 тыи °

В ассоциативном запоминающем устройстве (фиг. 2) на указанных блоках 35 поиска информации входы 24 и

26 блоков подключены к выходам соответствующих регистров 36 хранимых признаков, входы 27 и 25 блоков 35 подключены к выходам регистра 3? признака опроса, входы 28 и 29 блоков 35 подключены соответственно к входу 38 35 синхронизации и установочному входу 39, а выходы 30-34 блоков 35 являются выходами 40-44 ассоциативного запоминающего устройства.

Граф (фиг. 3) отражает состояние 4о

45-51 с первого по седьмое и возможные переходы в блоке 35 поиска информации. В вершинах графа в виде дроби приведены значения функции ы Г )и м11 7

I 1 (числитель дроби), определяющих со- 45 стояние блока 35 и двоичные коды, соответствующие состояниям триггеров 14 (знаменатель, слева направо) при данных состояниях блока 35 поиска ин-, формации. 50

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

В исходном состоянии сигналом начальной установки по входу 39 триггеры 1-4 устанавливаются в состояния, соответствующие вершине 45 граф», 15 2

Весь поиск занимает т .тактов (где

m — разрядность признаков), в каждом из которых с регистров 36 и 37, считываются очередные разряды (начиная со старших), анализируются с учетом предыдущих состояний в блоках 35 и по синхросигналу с входа. 38 в блоках 35 фиксируются новые состояния.

Работа ассоциативного запоминающего устройства, в которое входят блоки 35, основана на итеративном вычислении функций где . " = х" — у

) 1

S () — ) °

)-1 х(.) "7 = Z х; у(3 J );

Гj-17 у F(3-,7 );

) (х;,у ) определяется аналоГГЯ7 (-27 гично ); х... у;, х;,, у.,е 10,1 ; и

О при . 1 (О.;

Р()) = при 7 = О;

F($-1)+F(j-2) при 7 ) О.

I,m.

I,п (n — число хранимых признаков).

Величины х, и y 7 представ()-17 (-„7 ляют собой зались 7-1 старших разрядов кодов Фибоначчи признаков х; и у и х =,0 х" F(m j);

1 I)

Ill — .> z (-J)

) т.е. двоичных кодов с разрядными весами 1,1,2,3,5,8,13,21,34,55...

Тогда

7+ z j 7+ х"—

Все возможные переходы в блоке 35 поиска информации в зависимости от значений ы,1 ) и ы Г 7 (с учетом исходного состояния и .) " = ы,.1 7= О), 1E 17 значений х, у. и g (сигнала на 1 чальной установки) дает следующая таблица переходов.

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

Первая вершина графа 45 соответствует ы ) 7= ы1) 7= О, вторая вершиз 13361 на 46 соответствует а 1 1= - 1, о, 21= 0; (1- 3 третья вершина 47 соответствует u),.

C j-2 — 1, ю. = О; четвертая вершина 48 соответствует to,. = О, ы ., = -1;.

Г -13 rj-27 пятая вершина 49 соответствует у "3=

О, >(. = 1; шестая вершина 50 со1 10 ответствует (ы; + ы; с-2)

С>- 1 С;-21 г-3

М(2ы, + ы,1 1 (-3) и седьмая вершиС 1-<3 С1-2) на 51 соответствует (ы . + ь>,1 i 2)V

У(2ю 11> ") + ы4 23 у 3) 15

Если на входы 24 и 27 блокбв подаются прямые значения разрядов кодов признаков, а на входы 25 и 26 — инверсные значения, сигналами единицы на выходах 40-44 отмечаются, соответ20 ственно, хранИмые признаки, которые, меньше, больше или равны, больше, меньше или равны, равны по отношению к признаку опроса.

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

Блок поиска информации для ассоциативного запоминающего устройства, содержащий триггеры с первого по тре-, З0 тий, элементы И с первого по четвертый и первый элемент ИЛИ, причем выход первого элемента И подключен к первому входу второго элемента И, BTopoH Bxop KOToporо соеди нен с прямым выходом второго триггера, выход третьего элемента И подключен к первому входу четвертого.элемента И, выход первого элемента ИЛИ подключен к входу асинхронной установ 40 ки в "1" второго триггера, первый и второй входы первого элемента И являются соответственно первыми информационным и признаковым входами блока, первый и второй входы третьего эле- 4ч мента,И являются соответственно .вторыми информационным и признаковым, входами блока, прямые и инверсные выходы первого и третьего триггеров соответственно

"Меньше", "Больше или равно", "Меньше или равно", "Равно" блока; о тл и ч а ю шийся тем, что, с целью расширения области применения блока за счет выполнения граничного поиска чисел, представленных в кддах

Фибоначчи, в него введены четвертый триггер, с пятого по одиннадцатый элементы И, с второго по шестой эле15 менты ИЛИ и первый и второй элементы НЕ, причем выход первого элемента И подключен к первому входу пятого элемента И и входу первого элемента НЕ, выход которого подключен к первым входам шестого и седьмого элементов И, выходы которых подключены к первым входам второго и третьего элементов HJIH соответственно, выходы . которых подключены к входам асинхронной установки в "О" и "1".первого и четвертого триггеров соответственно, выход третьего элемента И подключен к первому входу восьмого элемента И, выход которого подключен к второму входу второго элемента ИЛИ и входу второго элемента НЕ, выход которого. подключен к первым входам девятого и десятого элементов И, выходы которых подключены соответственно к первым входам первого элемента ИЛИ и четвертого элемента ИЛИ, второй вход которого подключен к выходу пятого элемента И, выход четвертого элемента ИЛИ подключен к входу синхронной установки в "О". третьего триггера, прямые выходы первого и третьего триггеров подключены соответственно к входам асинхронной установки в "0" второго и четвертого триггеров, прямой и инверсный выходы четвертого триггера подключены к вторым входам четвертого и десятого элементов И, инверсный выход второго триггера подключен к второму входу шестого элемента И, выходы второго и четвертого элементов И подключены соответственно к первым входам пятого и шестого элементов ИЛИ, выходы которых подключены к входам асинхронной установки в "1" первого и третьего триггеров соответственно, инверсный выход первого триггера подключен к вторым входам пятого и девятого элементов И, инверсный выход третьего триггера подключен к вторым входам седьмого и восьмого элементов И, первый и второй входы одиннадцатого элемента И подключены к инверсным выходам первого и третьего триггеров соответствен но, входы синхронизации триггеров объединены и являются входом синхрони- зации блока, вторые входы первого, третьего, пятого и шестого элементов

ИЛИ объединены и являются установочным входом блока, выход одиннадцатоro элемента И является выходом "Больше" блока.

1336115

О

О х.

О

У.

О 1 0 +1 О О О О

О

О

О- (-) ΠΠ— 1 О О

-1 -1

+1 О О

+1 +! (+) (-) (-) О (+) 0 +1 (+) (-) О

1 (+1 О

13361)5

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

Редактор А. Козориз Техред И.Попович Корректор А. 0бручар

Заказ 4051/50 Тираж 589 Подписное

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

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

Производственно-полиграфическое прецприятие, г. Ужгород, ул. Проектная, 4