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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 4 0 11 С 15/О ОПИСАНИЕ ИЗОБРЕТЕН льФеаф ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ К А ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство ССУ 1153359, кл. О 11 С 15/00, 19Фостер К.Ассоциативные параллные процессоры, Перев. с англ.Энергоиздат, 1981, с, 75.(54) БЛОК ПОИСКА ИНФОРМАЦИИ ДЛЯ АССОЦИАТИВНОГО ЗАПОМИНАЮЩЕГО УСТРОЙСТВА(57) Изобретение относится к вычислительной технике и позволяет осуществлять граничный ассоциативный поискв массивах данных. Цель изобретениярасширение области применения блокапоиска информации для ассоциативногозапоминающего устройства за счет вы,801336115 А 1 полнения граничного поиска среди чисел, представленных в кодах Фибоначчи.Блок представляет собой конечный автомат, имеющий семь внутренних .состояний, содержит четыре триггера 1-4,одиннадцать элементов И 5-15, шестьэлементов ИЛИ 16-21 и два элементаНЕ 22 и 23. Входы 24 и 26 блока подключаются к выходам соответствующегорегистра хранимого признака ассоциативного запоминающего устройства (АЗУ)Входы 27 и 25 блока подключаются квыходам регистра признака опроса АЗУ.Коды признаков поступают в блок побитно, начиная со старших разрядов, Повходам 28 и 29 подаются сигналы синх- йронизации и начальной установки. Уровнями логической единицы на выходах 30-.34 отмечаются хранимые признаки, которые меньше, больше или равны, больше,меньше или равны, равны по отношениюк признаку опроса. 3 ил 1 табл.13361Изобретение относится к вычислительной технике, в частности к ассоциативным запоминающим устройствам.Цель изобретения - расширение об 5ласти применения блока за счет выполнения граничного поиска среди чисел,представленных в кодах Фибоначчи.На фиг. 1 изображена функциональнаясхема блока поиска информации для ассоциативного запоминающего устройства; на,фиг. 2 - схема ассоциативногозапоминающего устройства, в котороевходят указанные блоки; на фиг. 3 -график состояний и переходов блока по иска информации, поясняющий его работу,Блок поиска информации (фиг. 1)содержит триггеры 1-4 с первого почетвертый, элементы И 5-15 с первогопо одиннадцатый, элементы ИЛИ 16-21с первого по шестой, первый 22 и второй 23 элементы НЕ, входы 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) отражает состояние 4045-51 с первого по седьмое и возможные переходы в блоке 35 поиска информации. В вершинах графа в виде дробиприведены значения функции ы 9 и ,о 1 гЛ1(числитель дроби), определяющих состояние блока 35 и двоичные коды, соответствующие состояниям триггеров 14 (знаменатель, слева направо) приданных состояниях блока 35 поиска ин-,формации. 50 Блок 35 поиска информации для ассоциативного запоминающего устройства работает следующим образом.В исходном состоянии сигналом начальной установки по входу 39 триггеры 1-4 устанавливаются в состояния, соответствующие вершине 45 граф,15 2Весь поиск занимает ш тактов (где ш - разрядность признаков), в каждом из которых с регистров 36 и 37, считываются очередные разряды (начиная со старших), анализируются с учетом предыдущих состояний в блоках 35 и по синхросигналу с входа. 38 в блоках 35 фиксируются новые состояния,Работа ассоциативного запоминающего устройства, в которое входят блоки 35, основана на итеративном вычислении функцийгде я " = х- уФгх 1.Г " = 7". х" Р(- );3-13Е у РОЗ );(х; ,уопределяется аналоГгЗ-1гично );х.,у;,х ,уе 01;4Опри(ОР(Д) = 1 прид =0;Р(Д)+Р(Д) при Д ) О.3 =1 ш1,п (п - число хранимых признаков).Величины х, и упредстав 1-3-аляют собой запись )-1 старших разрядов кодов Фибоначчи признаков х; и уих =,Я х . Р(ш 1);у = .- у Р(ш-),т.е. двоичных кодов с разрядными весами 1,1,2,3,5,8,13,21,34,55ТогдаыЛ -13+ ы г 3Все возможные переходы в блоке 35поиска информации в зависимости отзначений ы ,1 и ыГ (с учетомисходного состояния М .1 " = Ы= 0),значений х , у. и я (сигнала на 1чальной установки) дает следующаятаблица переходов,В связи с этим для реализации итеративной процедуры предложен блок, граф состояний и переходов которого имеет семь вершин.Первая вершина графа 45 соответствует ы 1= ы ,= О, вторая верши з 1336146 соответствует1 1 фБ 21 О11-1 Э третья вершина 47 соответствует ю,.С 1.2 Э- 1, ю= 0; четвертая вершина 48 соответствует ы,1 Э= О,ы; = -1;Г . Э 11-2 Э пятая вершина 49 соответствует о 1, "Э=О, и(. = 1; шестая вершина 50 со 1 О ответствует ( ы; + ы; (-2)С; Э С;-21Ггз С -гУ(2 ы . + ы .1 Э (-3) и седьмая вершиС 1-лЭ С 1-2 Э на 51 соответствует (ы . + ь,1 з 2)Ч1ГГЭ + ГГ 2 Э 7 3) 15Если на входы 24 и 27 блокбв подаются прямые значения разрядов кодов признаков, а на входы 25 и 26 - инверсные значения, сигналами единицы на выходах 40-44 отмечаются, соответ 20 ственно, хранИмые признаки, которые, меньше, больше или равны, больше, меньше или равны, равны по отношению к признаку опроса. Формула изобретенияБлок поиска информации для ассоциативного запоминающего устройства, содержащий триггеры с первого по тре-, ЗО тий, элементы И с первого по четвертый и первый элемент ИЛИ, причем выход первого элемента И подключен к первому входу второго элемента И, вторй вход которого сОЙдинен с прямым выходом второго триггера, выход третьего элемента И подключен к первому входу четвертого.элемента И, выход первого элемента ИЛИ подключен к входу асинхронной установки в "1" второго триггера, первый и второй входы первого элемента И являются соответственно первыми информационным и признаковым входами блока, первый и второй входы третьего эле б мента,И являются соответственно .вторыми информационным и признаковым, входами блока, прямые и инверсные выходы первого и третьего триггеров влся свесео выходам "Меньше", "Больше или равно", "Меньше или равно", "Равно" блока; о тл и ч а ю щ и й с я тем, что, с целью расширения области применения блока за счет выполнения граничного поиска чисел, представленных в кддах Фибоначчи, в него введены четвертый триггер, с пятого по одиннадцатый элементы И, с второго по шестой элементы ИЛИ и первый и второй элементы НЕ, причем выход первого элемента И подключен к первому входу пятогоэлемента И и входу первого элемента НЕ, выход которого подключен кпервым входам шестого и седьмого элементов И, выходы которых подключенык первым входам второго и третьегоэлементов й 1 И соответственно, выходыкоторых подключены к входам асинхронной установки в "0" и "1",первого и четвертого триггеров соответственно, выход третьего элемента И подключен к первому входу восьмого элемента И, выход которого подключен к второму входу второго элемента ИЛИ и входу второго элемента НЕ, выход которого подключен к первым входам девятого и десятого элементов И, выходы которых подключены соответственно к первым входам первого элемента ИЛИ и четвертого элемента ИЛИ, второй входкоторого подключен к выходу пятого элемента И, выход четвертого элемента ИЛИ подключен к входу синхронной установки в "0". третьего триггера, прямые выходы первого и третьего триггеров подключены соответственно к входам асинхронной установки в "Он второго и четвертого триггеров, прямой и инверсный выходы четвертого триггера подключены к вторым входам четвертого и десятого элементов И,инверсный выход второго триггера подключен к второму входу шестого элемента И, выходы второго и четвертого элементов И подключены соответственно к первым входам пятого и шестогоэлементов ИЛИ, выходы которых подключены к входам асинхронной установки в "1" первого и третьего триггеров соответственно, инверсный выход первого триггера подключен к вторым входам пятого и девятого элементов И, инверсный выход третьего триггера подключен к вторым входам седьмогои восьмого элементов И, первый и второй входы одиннадцатого элемента И подключены к инверсным выходам первого и третьего триггеров соответствен- но, входы синхронизации триггеров объединены и являются входом синхрони- зации блока, вторые входы первого, третьего, пятого и шестого элементов ИЛИ объединены и являются установочным входом блока, выход одиннадцатого элемента И является выходом "Больше" блока.