Ассоциативное запоминающее устройство Советский патент 1981 года по МПК G11C15/00 

I

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

Известны ассоциативные запоминающие устройства ГО Г23.

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

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

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

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

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

15

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

Поставленная цель достигается тем, что в Ассоциативное запоминающее устМройство, содержащее накопитель блокизвлечения многозначного ответа, входной регистр, регистр маски, регистры сдвига, первый логический блок И коммутатор, причем одни из входов и выходов накопителя подключены к вы ходам и входам блока извлечения многозначного ответа и первого логического блока и одним из выходов и входоз регистров сДвига, другие входы и выход накопителя соединены соответственно с выходами входного регистра и регистра маски, вькодом и первы входом коммутатора, второй вход которого подключен к управляющему выходу первого регистра сдвига, входы входного регистра, регистра маски и выход блока извлечения многозначного ответа являются соответственно первым и вторым входами и выходом устройства, введены второй логически блок, одни из входов которого соедин ны с другими выходами первого регист ра сдвига, выходы и другие входы под ключены к другим входам и выходам второго регистра сдвига, а управляющие входы являются соответственно пе вым и вторьм управляняцими входами устройства. При этом второй логический блок содержит элементы ИЛИ и группы элементов И, причем первые входы элементов ИЛИ и второй вход первого эле мента ИЛИ являются одним из входов второго логического блока, первые входы элементов И первой и второй групп являются первым и .вторым управ ющими входами второго логического блока, другие входы которого подключены ко вторым входам соответствующих элементов И, выходы которых явля ются выходами второго логического блока, третий вход первого элемента И второй группы подключен; ж одному из входов второго логического блока, выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, треть входы элементов И первой группы подключены к выходам одноименных элемен тов ИЛИ, третьи входы элементов И второй группы, кроме первого, соединены с выходами предьщущих элемен, тов или. На фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 - функциональная схема пре имущественного варианта реализации второго логического блока Устройства содержит (фиг. l) вход ной регистр 1, регистр 2 маски, нако питель 3 с ячейками 4 памяти, комму.татор 5, первый 6 и второй 7 регист174ры сдвига, первый логический блок 8, блок 9 извлечения многозна:чного ответа и второй логический блок 10 с управляющими входами 11 и 12. Одни иэ .входов и выходов накопителя 3 подключены к выходам и входам блока 9 извлечения многозначного ответа и первого логического блока 8 и одним из выходов и входов первого 6 и второго 7 регистров сдвига. Другие входы и выход накопителя 3 соединены соответственно с выходами входрого регистра и регистра 2 маски, выходом и первым входом коммутатора 5, второй вход которого подключен к управляющему выходу первого регистра 6 сдвига. Входы входного регистра 1 и регистра 2 маски и выход блока,9 извлечения многозначного ответа являются соответственно первым и вторымо входами и выходом устройства. Одни из входов второго логического блока 10соединены с другими выходами первого регистра 6 сдвига, выходы и другие входы подключены к другим входай и выходам второго регистра 7 сдвига, а управляющие входы II и 12 являюtcя соответственно первым и вторым управлякщими входами устройства. Второй логический блок 10 содержит (фиг.; элементы ИЛИ 10,1-10.3, элементы И 10.4-10i6 первой группы и элементы И 10.7-10.10 второй группы. Первые входы элементов ИЛИ 10.1-10.3 и второй вход первого элемента ИЛИ 10.1 являются одними из входов второго логического блока 10. Первые входы элементов И 10.4-10.6 первой Группы к элементов И 10,7-10.10 второй группы являются соответственно первым 11и вторым 12 управлякяцими входами второго логического блока 10, Другие входы второго логического блока 10 подключены ко вторым входам соответствующих элементов И 10.4-10.10, выход ды являются выходами второго логического блока 10, Третий вход первого элемента И 10,7 второй группы подключен к .одному из входов второго логического блока 10, Выход каж-. дого элемента ИЛИ ,10,1-10,3, кроме последнего, соединен со; вторым входом последующего элемента ИЛИ, Тре- . тьи входы элементов И 10,4-10,6 первой группы подключены к выходам одноименных элементов ИЛИ 10,1-10,3, Третьи входы элементов И 10,8-10,10 второй группы, кроме первого 10,7, соединены соответственно с выходами предыдущих элементов ИЛИ 10.1-10.3.

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

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

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

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

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

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

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

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

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

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

Б результате проведения поиска по ассоциативному признаку в некотором разряде первого регистра 6 сдвига выставляется единица, указывакхцая

0 на ячейку 4 накопителя 3, в которой размещена последняя часть слова. При вставке слова произвольной длины к работе подключаются коммутатор 5 и второй логический блок 10. При

5 вставке слова происходит сдвиг содержимого первого регистра 6 сдвига на один разряд вправо, причем единица в некотором разряде первого регистра 6 сдвига разрешает сдвиг вправо на

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

5 переполнения накопителя 3 и смещения вправо на один разряд битов, хранящихся во втором регистре 7 сдвига слов, в пределах от, разряда регистра 7, отмеченного единицей в первом

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

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

- до конца накопителя 3. При зтом ииформация, находящаяся в ячейке 4 памяти накопителя 3, переписывается в правую соседнюю ячейку памяти 4 и Т.Д. В то же время благодаря цепочке двухвходовых злементов ИЛИ 10.1-10.3 (фиг. 2) злементы И 10.7-10.9, имеющиеся во втором логическом блоке 10 связывают выходы разрядов второго регистра 7 сдвига (фиг. 1) со входами последующих разрядов второго рв гистра 7 сдвига. При подаче сигиалй управления Вставка слова на второй управляющий вход 12 устройства происходит смсдцеиие информации, находящейся во втором регистре 7 сдвига, на один разряд вправо в пределах от разряда второго регистра 7 сдвига, отмеченного единицей в первом регист ре 6 сдвига, до конца второго регистра 7 сдвига. После сдвига информации вправо происходит запись единицы в разряд второго регистра 7 сдвига, отмеченного единицей в перво регистре 6 сдвига. В то же время происходит запись слова из входного регистра 1 в ячейку 4 памяти накопителя 3, отмеченной единицей в первом регистре сдвига 6. После этого, если слово не кончилось, производят следующие действия сдвиг вправо на один разряд единицы в первом регистре сдвига 6; сдвиг вправо информации в накопителе 3 на одну ячейку 4 памяти, начиная с ячей ки, отмеченной единицей в первом регистре 6 сдвига до конца накопителя 3; сдвиг вправо на один разряд информации во втором регистре 7 сдви га, начиная с разряда, отмеченного единицей в первом регистре 6 сдвига, до конца второго регистра 7 сдвига, запись машинного слова в ячейку 4 памяти накопителя 3, отмеченную единицей в первом регистре сдвига 6, запись нуля в разряд второго р гистра 7 сдвига, отмеченной единицей в первом регистре 6 сдвига, и т.д. до концд вводимого слова. Если при поиске найдено несколько слов, тр.:при выполнении команд Чтение со стиранием и Вставка слова блок извлечения многозначного ответа 9 начинает работать с первого левого найденного слова и заканчивает работать после обработки первого пра вого найденного слова накопителя 3.. Запись в конец информации, По команде Запись в конец проис ходит перепись самой правой единицы из второго регистра 7 сдвига в первь регистр 6 сдвига, который разрешает запись машинного слова в ячейку 4 памяти накопителя , 3. После зтого еди ница сдвигается вправо на один разряд в первом регистре 6 сдвига и, если слово кончилось, то единица из первого регистра 6 сдвига переписывается во вто.рой регистр 7 сдвига. При попытке зешисать в заполненный полностью накопитель 3 выдается сигнал Переполнения Технико-экономическое.преимущество предлагаемого устройства заклю чается в более высоком быстродействии, достигаемом за счет обеспечения вставки слов переменной длины между словами, находящимися в накопителе ассоциативного запоминающего устройства, без полной переписи записанной в него информации. Формула изобретения 1. Ассоциативное запоминающее устройство, содержащее накопитель, блок извлечения многозначного ответа, входной регистр, регистр маски, регистры сдвига, первый логический блок и коммутатор, причем одни из входов и выходов накопителя подключены к , выходам и входам блока извлечения многозначного Ответа и первого логического блока и одним из выходов и вхоо дов регистров сдвига, другие входьг и выход ассоциативного накопителя соединены соответственно с выходами входного регистра и регистра маски, выходом и первым входом коммутатора, второй вход которого подключен к управляющему выходу первого регистра сдвига, входного регистра и регистра маски и выход блока извлечения мн8гозначного ответа являются соответственно первым и вторым входами и выходом устройства, отличающееся тем, что, с целью повышения быстродействия устройства, оно содержит второй логический блок, одни из входов которого соединены с другими выходами первого регистра сдвига, выходы и другие входы подключи-, ны к другим входам и выходам второго регистра сдвига, а управлякицие входы являются соответственно первым и вторым управляющими входами устройства. 2. Устройство по п. I, отличающееся тем, что второй логический блок содержит элементы ИЛИ и группы элементов И, причем первые входы элементов ИЛИ и второй вход первого элемента ИЛИ являются одним из входов второго логического блока, первые входы элементов И первой и второй групп являются первым и вторым управляющими входами второго логического блока, другие входа которого подключены ко вторым входам соответствующих элементов И, выходы которьг являются выходами второго логического блока, третий вход первого элемента И второй группы подключен к одному из входов второго логического блока, выход каждого элемента ИЛИ, кроме последнего, соединен со вторым входом последующего элемента ИЛИ, третьи входы элементов И первой груп пы подключены к выходам одноименных элементов ИЛИ, третьи входы элементов И второй группы, кроме первого. 7 10 соединены с выходами предьщу цих элементов ИЛИ. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР №524226, кл. G 11 С 15/00, 1976. 2.Авторское свидетельство СССР № 618793, кл. G 11 С 1.5/00, 1978 (прототип).

в

н

10

12

L А

VV

(flut.f