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

ОЛ ИСАНИЕИЗЬВРЕТЕН ИЯК АВТОРСКОМУ СВИДИНА ЛЬСТВУ и 1877617 Союэ СоветскихСоциалистическихРеспублик(51)М. Кд,6 11 С 15/00 Гооуаарстеаинцй квинтет СССР ио делан нзебретеннВ н открытийОпубликовано 30. 10.8 1. Бюллетень 1 ЧЪ 40 Дата опубликования описаний 30. 10.81,(72) Авторы изобретения А.А,Бекасов, С.В.Буров, В.А.Торгашев и В. . кирттоть - "-= Р г ж) Ленинградский институт авиационного приб рос троення;(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Изобретение относится к запоминающим устройствам.Известны ассоциативные запоминающие устройства 11 и 21.Одно из известных устройств содержит регистр данных и регистр мас" ки, ассоциативньй накопитель, блок логических операций, блок извлечения многозначного ответа 1,1,Недостатком этого устройства яв 10 ляется то, что оно не позволяет эффективно работать с информацией переменной длиныНаиболее близким техническим решением к предлагаемому является уст 1 ройство, содержащее входной регистр и регистр маски, выходы которьцс соответственно соединены со вторым н тре" чьим входами накопителя, первый вход- выход которого соединен с входом- выходом блока извлечения многозначного ответа, с выходом-входом блока логических операций, с выходом-входом реверсивного сдвигающего регистра. определения границ исследуемых сдов, с выходом-входом реверсивного сдвига ющего регистра разрешения считывания-сравнения, второй выход которого соединен со вторым (управляющим)вхо" дом блока. коммуникации, первый вход и выход которого соответственно соединены со вторым выходом и четвертым входом накопителя 21.Недостатком этого устройства яв" ляется невысокое быстродействие вследствие невозможности осуществлять вставку слова переменной длины между словами, находящимися в накопителе, без полной переписи информации. Цель изобретения - повьппение быстродействия устройства.Поставленная цель достигается тем, что в ассоциативное запоминающее уст" ройство, содержащее накопитель, блок извлечения многозначного ответа, входной регистр, регистр маски, регистры сдвига, первый логический блок877617 4ры сдвига, первый логический блок 8,блоМ 9 извлечения многозначного ответа и второй логический блок 10 с управляющими входами 11 и 12. 25 и коммутатор, причем одни из входов и выходов накопителя подключены к выходам и входам блока извлечения многозначного ответа и первого логического блока и одним из выходов и вхо 5дов регистров сДвига, другие входы ивыход накопителя соединены соответственно с выходами входного регистра и регистра маски, выходом и первымвходом коммутатора, второй вход ко Оторого подключен к управляющему выходу первого регистра сдвига, входывходного регистра, регистра маски ивыход блока извлечения многозначного ответа являются соответственно15 первым и вторым входами и выходом устройства, введены второй логический блок, одни из входов которого соедине-. ны с другими выходами первого регистра сдвига, выходы и другие входы подключены к другим входам и выходам второго регистра сдвига, а управляющие входы являются соответственно первым и вторым управляющими входами устройства.При этом второй логический блок содержит элементы ИЛИ и группы эле.ментов И, причем первые входы элементов ИЛИ и второй вход первого элемента ИЛИ являются одним из входов30 второго логического блока, первые входы элементов И первой и второй групп являются первым и .вторым управляющими входами второго логического блока, другие входы которого подключены ко вторым входам соответствующих элементов И, выходы которых являются выходами второго логического блока, третий вход первого элемента И второй группы подключен;ж одному из входов второго логического блока, 40 выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, третьи входы элементов И первой группы подключены к выходам одноименных элемен тов ИЛИ, третьи входы элементов И второй группы, кроме первого, соединены с выходами предыдущих элемен" , тов ИЛИ.На фиг. 1 изображена функциональ ная схема предлагаемого устройства; на фиг. 2 - функциональная схема преимущественного варианта реализации второго логического блока.Устройствэ.содержит (фиг. 1) вход" 55 ной регистр 1, регистр 2 маски, накопитель 3 с ячейками 4 памяти, комму,татор 5, первый 6 и второй 7 регистОдни из .входов и выходов накопителя 3 подключены к выходам и входам блока 9 извлечения многозначного ответа и первого логического блока 8 и одним из выходов и входов первого 6 и второго 7 регистров сдвига. Другие входы н выход накопителя 3 соединены соответственно с выходамН вход 1 ого регистра 1 и регистра 2 маски, выходом и первым входом коммутатора 5, второй вход которого подключен к управляющему выходу первого региатра 6 сдвига. Входы входного регистра 1 и регистра 2 маски и выход блока 9 извлечения многозначного ответа являются соответственно первым и вторымо входами и выходом устройства. Одни из входов второго логического блока 10 соединены с другими выходами первого регистра 6 сдвига, выходы и другие входы подключены к другим входаМ и выходам второго регистра 7 сдвига, а управляющие входы 11 и 12 являются соответственно первым и вторым управляющими входами устройства. Рторой логический блок 10 содержит Фиг. элементы ИЛИ 10.1-10.3, элементы И 10.4-10.6 первой группы и элементы И 10.7-10,10 второй группы. Первые входы элементов ИЛИ 10.1-10.3 и второй вход первого элемента ИЛИ 10.1 являются одними из входов второго логического блока 1 О. Первые входы элементов И 10.4-10.6 первой группы и элементов И 10.7-10.10 второй группы являются соответственно первым 11 и вторым 12 управляющими входами второго логического блока 10. Другие входы второго логического блока 10 подключены ко вторым входам соответствующих элементов И 10.4- 10.10, выход ды которых являются выходами второго логического блока 10. Третий вход первого элемента И 10.7 второй группы подключен к одному из входов второго логического блока О. Выход каж" дого элемента ИЛИ,10.1-10,3, кроме последнего, соединен со: вторым входом последующего элемента ИЛИ. Тре- . тьи входы элементов И 10.4-10.6 первой группы подключены к выходам одноименных элементов ИЛИ 10.1-10.3. Третьи входы элементов И 10.8-10.10 второй группы, кроме первого 10.7, сое877617 10 15 20 30 35 динены соответственно с выходами предыдущих элементов ИЛИ 10.1-10.3.Устройство работает следующим образом,Входной регистр (фиг. 1) служит для ввода либо ассоциативных признакоц при поиске, либо информационных слов при записи.Содержимое регистра маски 2 определяет, какие разряды слова участвуют при операции поиска. Коммутатор 5 предназначен для обеспечения возможности сдвига информации в накопителе 3 в пределах от ячейки 4 памяти, отмеченрой единицей в первом регистре б сдвига, до конца накопителя 3 как влево при чтении со стиранием, так и вправо при вставке слова.Регистр 6 сдвига предназначен для указания ячеек4 памяти накопителя 3, которые должны участвовать в поиске, а по окончании поиска указывают слова, удовлетворяющие признаку поиска (точнее последние ячейки 4 памяти накопителя 3, в которых находятся слова). Второй регистр 7 сдвига содержит информацию о начале слов или массивов, если в устроистве записаны массивы, а также определяет начало свободной памяти, если накопитель 3 не заполнен полностью (самая правая единица в регистре 7 сдвига). Первый логический блок 8 позволяет осуществлять поразрядные логические операции . суммирования по модулю два, конъюнкции, дизъюнкции над содержимым первого регистра 6 сдвига и второго регистра 7 сдвига.Блок извлечения многозначного ответа 9 позволяет осуществить последовательную выборку нескольких: слов, обладающих одинаковыми ассоциативны" ми признаками и.найденных в резуль" тате одной операции поиска. Второйлогический блок 10 предназначен дляобеспечения возможности сдвига информации во втором регистре 7 сдвигав пределах от бита, отмеченного единицей в первом регистре сдвига, доконца регистра, как влево при чтении со стиранием, так и вправо лривставке слова. Предлагаемое ассоциативное запоминающее устройство (АЗУ) может вм" полнять команды: чтение по ассоциа.тивному признаку; чтение со стиранием запись в конец информации, вставку слова произвольной длины. 6Рассмотрим работу устройства на примере выполнения команд "Вставка слова произвольной длины" и "Зались в конец информации".Вставка слова пройзвольнай длины.В результате проведения поиска по ассоциативному признаку в некотором разряде первого регистра 6 сдвига выставляется единица, указывающая на ячейку 4 накопителя 3, в которой размещена последняя часть слова. При вставке слова произвольной длины к работе подключаются коммутатор 5 и второй логический блок 10. При вставке слова происходит сдвиг содержимого первого регистра 6 сдвига на одйн разряд вправо, причем единица в некотором разряде первого регистра 6 сдвига разрешает сдвиг. вправо на одну ячейку 4 памяти информации, хранящейся в накопителе 3 в пределах от ячейки 4 памяти, отмеченной едим ницей в первом регистре 6 сдвига, до конца накопителя 3 при контроле переполнения накопителя 3 и смещения вправо на один разряд битов, хранящихся во втором регистре 7 сдвига слов, в пределах от, разряда регистра 7, отмеченного единицей в первом регистре б сдвига, до конца второго регистра 7 сдвига. Это осуществля" ется с помощью коммутатора 5 и второго логического блока 10.Благодаря цепочке очередности все элементы И, имеющиеся в каждом разряде коммутатора 5 и связующие выходы предыдущих ячеек 4 памяти со входами последующих, находящихсяправее единицы в первом регистре 6 сдвига, оказываются открытыми, обеспечивая тем самым возможность сдвига информации, хранящейся в накопителе 3, в пределах от ячейки 4 памяти, отмеченной . единицей в первом регистре 6 сдвига, до конца накопителя 3. При этом информация, находящаяся в ячейке 4 памяти накопителя 3, переписывается в правую соседнюю ячейку памяти 4 и т.д. В то же время благодаря цепочке двухвходовых элементов ИЛИ 10.1-10.3 (фиг. 2) элементы И 10.7-10.9, имею" щиеся во втором логическом блоке 10, связывают выходы разрядов второго регистра 7 сдвига (фиг. 1) со входаии последующих разрядов второгр регистра 7 сдвига. При подаче сигнала управления "Вставка слова" на второй управляющий вход 12 устройства происходит смещение информации, находя50 щейся во втором регистре 7 сдвига,на один разряд вправо в пределах отразряда второго регистра 7 сдвига,отмеченного единицей в первом регистре б сдвига, до конца второго регистра 7 сдвига. После сдвига информации вправо происходит запись единицы в разряд второго регистра 7сдвига, отмеченного единицей в первомрегистре 6 сдвига. В то же времяопроисходит запись слова из входногорегистра 1 в ячейку 4 памяти накопителя 3, отмеченной единицей в первомрегистре сдвига 6После этого, если слово не кончилось, производят следующие действия:сдвиг вправо на один разряд единицыв первом регистре сдвига 6; сдвигвправо информации в накопителе 3 на .одну ячейку 4 памяти, начиная с. ячейки, отмеченной единицей в первом регистре 6 сдвига до конца накопителя 3; сдвиг вправо на один разрядинформации во втором регистре 7 сдвига, начиная с разряда, отмеченногоединицей в первом регистре 6 сдвига,до конца второго регистра 7 сдвига,запись машинного слова в ячейку 4памяти накопителя 3, отмеченную еди"ницей в первом регистре сдвига 6,запись нуля в разряд второго регистра 7 сдвига, отмеченной единицей внервом регистре 6 сдвига, и т.д, доконца вводимого слова.Если при поиске найдено несколькослов, то:.при выполнении команд ",Чте 35ние со стиранием" и "Вставка слова"блок извлечения многоэначного ответа 9 начинает работать с первого левого найденного слова и заканчиваетработать после обработки первого правого найденного слова накопителя 3.,Запись в конец информации.По команде "Запись в конец" происходит перепись самой правой единицыиз второго регистра 7 сдвига в первый.регистр б сдвига, который разрешаетзапись машинного слова в ячейку 4памяти накопителя,3. После этого единица сдвигается вправо на один разряд в первом регистре 6 сдвига и,если слово кончилось, то единица изпервого регистра 6 сдвига переписывается во второй регистр 7 сдвига,При попытке записать в заполненныйполностью накопитель 3 выдается сигнал йереполнения,Технико-экономическое.преимущество предлагаемого устройства заключается в более высоком быстродействии, достигаемом за счет обеспечения вставки слов переменной длины между словами, находящимися в накопителе ассоциативного запоминающего устройства, без полной переписи за" писанной в него информации.формула изобретения1. Ассоциативное запоминающее устройство, содержащее накопитель, блок извлечения многозначного ответа, входной регистр, регистр маски, регистры сдвига, первый логический блок и коммутатор, причем одни из входов и выходов накопителя подключены к, выходам и входам блока извлечения многозначного ответа и первого логичес-. кого блока и одним из выходов и вхос дов регистров сдвига, другие входы й выход ассоциативного накопителя соединены соответственно с выходами входного регистраи регистра маски, выходом и первьйи входом коммутатора, второй вход которого подключен к управляющему выходу первого регистра сдвига, взводы входного регистра и регистра маски и выход блока извлечения мн 8- гозначного ответа являются соответственно первым и вторым входами н выходом устройства, о т л и ч а ю - щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит второй логический блок, одни нз входов которого соединены с другими выходами первого регистра сдвига, выходы и другие входы подключив", ны к другим входам и выходам второго регистра сдвига, а управляющие входы являются соответственно первым и вторым управляющими входами устройства.2. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что второй логи-. ческий блок содержит элементы ИЛИ и группы элементов И, причем первые входы элементов ИЛИ и второй вход первого элемента ИЛИ являются одним из входов второго логического блока, первые входы элементов И первой и второй групп являются первым н вторым управляющими входами второго логического блока, другие входы которого подключены ко вторым входам соответствующих элементов И, выходы которых являются выходами второго логического блока, третий вход первого элемента И второй группы подключен к од-.ному иэ входов второго логического блока, выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, 5 третьи входы элементов И первой группы подключены к выходам одноименных элементов ИЛИ, третьи входы элементов И второй группы, кроме первого,соединены с выходами предыдуприс элементов ИЛИ.Источники информации, принятые во внимание при экспертизе1. Авторское свидетельство СССР У 524226, кл. О 11 С 15/00, 1976.2. Авторское свидетельство СССР В 618793, кл. 6 11 С 1 ЯОО, 1978 (прототип).атент , г, Ужгород, ул, Проектная,ППП каз 9625 77ф ВНИИПИ Гпо дел113035,аж 648 Подписноедарственного комитета СССРизобретений и открытийква, Ж, Раушская наб., д. 4/