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

 

ОЛ ИСАНИЕ

ИЗЬВРЕТЕН ИЯ

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

< 1877617

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

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

Республик (61) Дополнительное к авт. санд-ву (22) Заявлено 18. 01. 80 (21) 2870547 18-24 с присоединением заявки М (53)М. Кд.

G 11 С 15/00

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

СССР

10 делан нзебретеннй н открытия л (23) Приоритет (53) УДК 681. 327 (088.8) Опубликовано 30.10.81. Бюллетень Рй 40

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

А.А.Бекасов, С.В.Буров, В.А.Торгашев и В.. ки)Утттлв—

I > ! 1

Ленинградский институт авиационного приб ростроення. (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

Известны ассоциативные запоминающие устройства (11 и 323

Одно из известных устройств содержит регистр данных и регистр маски, ассоциативньй накопитель, блок логических операций, блок извлечения многозначного ответа fl) .

Недостатком этого устройства яв10 ляется то, что оно не позволяет эффективно работать с информацией переменной длины..

Наиболее близким техническим решением к предлагаемому является уст1$ ройство, содержащее входной регистр и регистр маски, выходы которых соответственно соединены со вторым н тре" чьим входами накопителя, первый входвыход которого соединен с входомвыходом блока извлечения многозначного ответа, с выходом-входом блока логических операций, с выходом-входом реверсивного сдвигающего регистра. определения границ исследуемых слов, с выходом-входом реверсивного сдвига ющего регистра разрешения считывания-сравнения, второй выход которого соединен со вторым (управляющим) вхо" дом блока. коммуникации, первый вход и выход которого соответственно соединены со вторым выходом и четвертым входом накопителя (21.

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

Цель изобретения — повьппение быстродействия устройства.

Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее накопитель, блок. извлечения многозначттого ответа, входной регистр, регистр маски, регистры сдвига, первый логический блок.8776l7 4 ры сдвига, первый логический блок 8, блоМ 9 извлечения многозначного ответа и второй логический блок 10 с управляющими входами 11 и 12.

25 и коммутатор, причем одни из входов и выходов накопителя подключены к выходам и входам блока извлечения многозначного ответа и первого логического блока и одним из выходов и вхо5 дов регистров сДвига, другие входы и выход накопителя соединены соответственно с выходами входного регистра и регистра маски, выходом и первым входом коммутатора, второй вход ко- 1g торого подключен к управляющему выходу первого регистра сдвига, входы входного регистра, регистра маски и выход блока извлечения многозначного ответа являются соответственно

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

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

30 второго логического блока, перфые входы элементов И первой и второй групп являются первым и вторым управляющими входами второго логического блока, другие входы которого подключены ко вторым входам соответствующих элементов И, выходы которых являются выходами второго логического блока, третий вход первого элемента

И второй группы подключен;ж одному из входов второго логического блока, 4О выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, третьи входы элементов И первой группы подключены к выходам одноименных элементов ИЛИ, третьи входы элементов И второй группы, кроме первого, соединены с выходами предыдущих элемен", тов ИЛИ.

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

Устройств1э.содержит (фиг. 1) вход" 55 ной регистр 1, регистр 2 маски, накопитель 3 с ячейками 4 памяти, комму,татор 5, первый 6 и второй 7 регистОдни из .входов и выходов накопителя 3 подключены к выходам и входам блока 9 извлечения многозначного ответа и первого логического блока 8 и одним из выходов и входов первого 6 и второго 7 регистров сдвига. Другие входы н выход накопителя 3 соединены соответственно с выходамН вход)1ого регистра 1 и регистра 2 маски, выходом и первым входом коммутатора 5, второй вход которого подключен к управляющему выходу первого региатра

6 сдвига. Входы входного регистра I и регистра 2 маски и выход блока 9 извлечения многозначного ответа являются соответственно первым и вторымо входами и выходом устройства. Одни из входов второго логического блока

10 соединены с другими выходами первого регистра 6 сдвига, выходы и другие входы подключены к другим входами и выходам второго регистра 7 сдвига, а управляющие входы 11 и 12 являются соответственно первым и вторым управляющими входами устройства. Рторой логический блок 10 содержит (фиг.u) элементы ИЛИ 10.1-10.3, элементы И

10.4-10.6 первой группы и элементы

И 10.7-10.10 второй группы. Первые входы элементов ИЛИ 10.1-10.3 и второй вход первого элемента ИЛИ IO.I являются одними из входов второго логического блока IO. Первые входы элементов И 10.4-)0.6 первой группы и элементов И 10.7-10.10 второй группы являются соответственно первым

11 и вторым 12 управляющими входами второго логического блока 10. Другие входы второго логического блока 10 подключены ко вторым входам соответствующих элементов И 10.4-.10 ° 10, выход ды которых являются выходами второго логического блока 10. Третий вход первого элемента И 10.7 второй группы подключен к одному as входов второ»

r"o логического блока !О. Выход каж" дого элемента ИЛИ,10.1-10.3, кроме последнего, соединен со: вторым входом последующего элемента ИЛИ. Тре- . тьи входы элементов И 10.4-)0.6 первой группы подключены к выходам одноименных элементов ИЛИ 10.)-)0.3. Третьи входы элементов И 10.8-10.10 второй группы, кроме первого 10.7, сое877617

15

30

40

55 динены соответственно с выходами предыдущих элементов ИЛИ 10.1-10.3.

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

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

Содержимое регистра маски 2 определяет, какие разряды слова участвуют при операции поиска. Коммутатор

5 предназначен для обеспечения возможности сдвига информации в накопителе

3 в пределах от ячейки 4 памяти, отмечен рой единицей в первом регистре

6 сдвига, до конца накопителя 3 как влево при чтении со стиранием, так и вправо при вставке слова.

Регистр 6 сдвига предназначен для указания ячеек 4 памяти накопителя

3, которые должны участвовать в поиске, а по окончании поиска указывают слова, удовлетворяющие признаку поиска (точнее последние ячейки 4 памяти накопителя 3, в которых находятся слова). Второй регистр 7 сдвига содержит информацию о начале слов или массивов, если в устроистве записаны массивы, а также определяет начало свободной памяти, если накопитель 3 не заполнен полностью (самая правая единица в регистре 7 сдвига). Первый логический блок 8 позволяет осуществлять поразрядные логические операции . суммирования по модулю два, конъюнкции, дизъюнкции над содержимым первого регистра 6 сдвига и второго регистра 7 сдвига.

Блок извлечения многозначного ответа 9 позволяет осуществить последовательную выборку нескольких: слов, обладающих одинаковыми ассоциативными признаками и.найденных в резуль" тате одной операции поиска. Второй логический блок 10 предназначен для обеспечения возможности сдвига информации во втором регистре 7 сдвига в пределах от бита, отмеченного единицей в первом регистре сдвига, до конца регистра, как влево при чтении со стиранием, так и вправо лри вставке слова.

Предлагаемое ассоциативное залоиинающее устройство (АЗУ) может вм" полнять команды: чтение по ассоциа.тивному признаку; чтение со стиранием запись в конец информаади, встав» ку слова произвольной длины.

Рассмотрим работу устройства на примере выполнения команд "Вставка слова произвольной длины" и "Зались в конец информации".

Вставка слова пройзвольнай длины.

В результате проведения поиска по ассоциативному признаку в некотором разряде первого регистра 6 сдвига выставляется единица, указывающая на ячейку 4 накопителя 3, в которой размещена последняя часть слова.

При вставке слова произвольной длины к работе подключаются коммутатор 5 и второй логический блок 10. При вставке слова происходит сдвиг содержимого первого регистра 6 сдвига на

Ф один разряд вправо, причем единица в некотором разряде первого регистра

6 сдвига разрешает сдвиг. вправо на одну ячейку 4 памяти информации, хранящейся в накопителе 3,. в пределах от ячейки 4 памяти, отмеченной едим ницей в первом регистре 6 сдвига, до конца накопителя 3 при контроле переполнения накопителя 3 и смещения вправо на один разряд битов, хранящихся во втором регистре 7 сдвига слов, в пределах от, разряда регистра

7, отмеченного единицей в первом регистре 6 сдвига, до конца второго регистра 7 сдвига. Это осуществля" ется с помощью коммутатора 5 и второго логического блока 10.

Благодаря. цепочке очередности все элементы И, имеющиеся в каждом разряде коммутатора 5 и связующие выходы предыдущих ячеек 4 памяти со входами последующих, находящихся правее единицы в первом регистре б сдвига, оказываются открытыми, обеспечивая.тем самым возможность сдвига. информации, хранящейся в накопителе 3, в пределах от ячейки 4 памяти, отмеченной . единицей в первом регистре 6 сдвига, до конца накопителя 3. При этом информация, находящаяся в ячейке 4 памяти накопителя 3, переписывается в г правую соседнюю ячейку памяти 4 и т.д.

В то же время благодаря цепочке двухвходовых элементов ИЛИ 10.1-10 ° 3 (фиг. 2) элементы И 10.7-10.9, имею". щиеся во втором логическом блоке 10, связывают выходы разрядов второго регистра 7 сдвига (фиг. 1) со входами последующих разрядов второго регистра 7 сдвига. При подаче сигнала управления "Вставка слова" на второй управляющий вход 12 устройства происходит смщщение информации, находя877617

50 щейся во втором регистре 7 сдвига, на один разряд вправо в пределах от разряда второго регистра 7 сдвига, отмеченного единицей в первом регистре 6 сдвига, до конца второго регистра 7 сдвига. После сдвига информации вправо происходит запись единицы в разряд второго регистра 7 сдвига, отмеченного единицей в первом регистре 6 сдвига. В то же время о происходит запись слова из входного регистра 1 в ячейку 4 памяти накопителя 3, отмеченной единицей в первом регистре сдвига 6 °

После этого, если слово не кончилось, производят следующие действия: сдвиг вправо на один разряд единицы в первом регистре сдвига 6; сдвиг вправо информации в накопителе 3 на . одну ячейку 4 памяти, начиная с. ячейки, отмеченной единицей в первом регистре 6 сдвига до конца накопителя 3; сдвиг вправо на один разряд информации во втором регистре 7 сдвига, начиная с разряда, отмеченного единицей в первом регистре 6 сдвига, до конца второго регистра 7 сдвига, запись машинного слова в ячейку 4 памяти накопителя 3, отмеченную единицей в первом регистре сдвига 6, запись нуля в разряд второго регистра 7 сдвига, отмеченной единицей в нервом регистре 6 сдвига, и т.д. до конца вводимого слова.

Если при поиске найдено несколько слов, то;.при выполнении команд ".Чте35 ние со стиранием" и "Вставка слова" блок извлечения многоэначного ответа 9 начинает работать с первого ле вого найденного слова и заканчивает работать после обработки первого правого найденного слова накопителя 3., Запись в конец информации.

По команде "Запись в конец" происходит перепись самой правой единицы из второго регистра 7 сдвига в первый .регистр 6 сдвига, который разрешает запись машинного слова в ячейку 4 памяти накопителя.3. После этого единица сдвигается вправо на один разряд в первом регистре 6 сдвига и, если слово кончилось, то единица из первого регистра 6 сдвига переписывается во второй регистр 7 сдвига, При попытке записать в заполненный полностью накопитель 3 выдается сигнал йереполнения.

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

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

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

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

2. Устройство по п. I, о т л и— ч а ю щ е е с я тем, что второй логи-. ческий блок содержит элементы ИЛИ и группы элементов И, причем первые входы элементов ИЛИ и второй вход первого элемента ИЛИ являются одним иэ входов второго логического блока, первые входы элементов И первой и второй групп являются первым н вторым управляющими входами второго логи- . ческого блока, другие входы которого подключены ко вторым входам соответствующих элементов И, выходы которых являются выходами второго логического блока, третий вход первого элемен877617

l0 та И второй группы подключен к од-. ному иэ входов второго логического блока, выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, 5 третьи входы элементов И первой группы подключены к выходам одноименных элементов ИЛИ, третьи входы элементов И второй группы, кроме первого, соединены с выходами предыдуприс элементов ИЛИ.

Источники информации, принятие во внимание при экспертизе

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

У 524226, кл. G ll С l5/00, 1976.

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

9 618793, кл. G 11 С 15/00, 1978 (прототип).

877617.

Составитель Т, Зайцева

Редактор Е.Папп .Техред А. Савка . ..Корректор А.Ференц

Заказ 9625 77 Тираж 648 Подписное

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

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

Филиал ППП Патент, r. Ужгород, ул, Проектная,