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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮШЕЕ УСТРОЙСТВО 3 Анализ функциональных всхзможностей запоминающих устройств показывает, что операции, связанные с ассоциативным поиском в оперативном ЗУ, могут выпол няться непосредственно в самом ЗУ, В основу ассоциативного поиска в ОЗУ положена возможность выполнения операци поразрядного сравнения многоразрядного двоичного слова с одноразрядным двоичным числом за один такт считывания/ Пусть в некоторой числовой линейке ЗУ хранится - разрядное слово X.x. {о, -1 -и разряд слова X . Необходимо выполнить операцию X,j ®Yj. , гдеУ е {од} -J - разряд |Л.2 двоичного числа а j меняется от I до ГП и меняется от Г до П , Обозначим символом X j П -разрядное двоичное слово, хранящееся в числовой линейке ЗУ, а символом X.} - двоично слово, образованное мк разрядами слов X j . Тогда 41 гдеХ ё (ОДЗ -i -и разряд слова X Назовём каждое слово X j признаком 1 -го информационного слова некоторого информационного массива, содержащего П слов, Y - признаком обращения к массиву. Выборка к, 6, -,, t (liK, n.,,f&n ) информационных слов из массива сзсуществляется по совпадению признака обращения Y с признаками X . Сравнениегп - разрядных призна ков X j с Y можно выполнить в ЗУ за m тактов считывания и за п тактов сдвига Сравнивая после каждого сдвига j разряды признаков Xj с j - разрядом Yj признака.Y и накапливая результаты сравнения за ц -тактов сдвига, получим в разрядах, соответствующих совпавшим признакам X , нули. Каждый из разрядов результатов опр деляется по формуле: ...,. m.n ) .и. I4,jcl i Поставим в соответствие каждой числовой линейке ЗУ, отводимой для хр нения i -го информационного слова, при ,ll| /который назовем призн ком занятости - числовой линейки З 72 Причем р| - Т соответствует наличию слов.) в данной числовой линейке. Двоичное слово р:2 iiaaoseM сло i в 1 г 1 вом занятости и отведем для хранения этого слова нулевую ячейку ЗУ. Таким образом, выделяя в накопителе три функционально разделенных поля для хранения Р X j и П -верного информационного масси за, можно производить ассоциативный выбор из устройства в соответствии с признаком Y . На фиг. 1 изображена блок - схема предложенного устройства, на фиг. 2 и 3 соответственно программы работы устройства чтения и записи по ассоциативному признаку. Устройство содержит (см. фиг. 1) входной регистр 1, накопитель 2, блок выборки адреса 3, шину установки адреса 4, выходной регистр 5, блок определения очередности обращения 6, логический блок 7, регистр признака обращения 8, входные информационные шины 9, выходные информационные шины. 10, шину режима работы 11, шину 12. Части 13-15 накопителя 2 служат соответственно для хранения двоичного слова занятости Р, признаков обращения к ЗУ (X) и информационного массива. Информационные входы и выходы блока 6 срответственно подключены к выходам и входам регистров 5 и Ъ, информационные выходы регистра 5 соединены с информационными входами регистра 1, управляющий выход регистра 5 соединен с одйим из входов блока 7 и счетным входом блока 3, выход блока 7 соединен с одним из управляющих входов блока 6. Выход регистра 8 подключен к управл5пощим входам регистров 1 и 5 и другому управляющему входу блока 6, управляющий выход которого соединен с другим нходом блока 7, На фиг. 2 и 3 приняты следующие обозначения: РА- эегистр адреса, находящийся в блоке выборки адреса 3 (см. фиг. 1), ВР-регистр 5,ЯП - t -ая ячейка памяти, находящаяся в накопителе 2, БОО - блок 6, РП- регистр 8,0 -счетчик, находящийся в блоке 3, К -бчетчик сдвигов (на фиг. I не показан), ГЛ и П cooTseTCTBieHHO количество ячеек и разрядов в ячейке ЗУ, Р- слово занятости (хранится в Нулевой ячейке ЗУ), ВИШ - шины 10, ВхР - регистр 1, ВхИШ - шины 9. Запоминающее устройство может работать в следующих режимах: запись и чте- ние по адресу, запись по ассоциативном признаку, чтение по ассоциативному при наку. Первые ава режима работы реализую ся в любом адресном ЗУ, поэтому рассм рим в качестве примера режим чтения п ассоциативному признаку. В этом режиме ЗУ работает по программ представленной на фиг, 2. ТРаботу ЗУ в этом режиме рассмотрим на примере ЗУ небольшого формата: ЯПО1ОIP ЯП11. ОО Поле признако ЯП21О1 ЯП3ОО1 ИнформационЯП411Оный массив При этом Л -3, m -3, Y 0,1,13. В соответствии с программой работы в режиме выборкой информации сначала из ЗУ считывается содержимое ячейки ЯП О и передается в блок 6 (см. фиг, 2 блок 1). При этом БОО: - (1,0, 4), Затем в выходной регистр 5 заносится результат сравнения 1-го разряда при нака VI (О) со всеми разрядами содержимог ЯП Г. ( 100 ® 000 V100 (100) Далее содержимоерегистра 5 склады вается (логически), с содержимым, блока 6 Вр: BPvBOb sr lOOyOlO (l,i,O), Проверяя логическое условие несовпадения первого разряда информационного слова, получаем: ЛЪР 1А1лО 0 m Имеется совпадение по двум р азрядам ячейки ЯП 1. Переходим к проверке следующих разрядов Y на совпадение с содержимым ячеек поля признаков, при это содержимое регистра 8 сдвигается на один разряд и второй разряд Y поступае в регистр 5. Далее проверяется окончание массива, но, так как еще не все ячейки части 14 накопителя 2 просмотрены, происходит переход на повторение предыдущего цикпа анализа совпадения разряда признака Y с разрядами следующего признака счи тываемого с накопителя 2 по адресу ЯП 72.6 В регистре 5 снова формируется результат сравяения: - -- яп ; ВР: ЯП ® ВР ©111 1 1 1 о. 1 о 1 Затем в регистре 5 формируется двоичное слово, единичные разряды которого показывают, что еще не полностью произошло совпадение между разрядами признака обращения и каким-либо признаком информационного Массива: ВР: (ВР) V БОО 11OV01O (100). Далее регистр 8 сдвигается на 1 разряд и в счетчик адреса прибавляется 1, Происходит переходна третий цикл анализа, так как просмотрены только две ячейки поля анализа из трех. В регистре 5 снова формируется результат сравнения: ВР: t ЯП ©ygjV ВР (0 О 0®1 1 l)v 1 1 О (11 1). Затем начинается выборка слова, адрес которого задается положением О регистра 5 после последнего сдвига (после последней операции сравнения). Регистр 5 сдвигается на 1 разряд влево, а в регистр адреса блока выборки ад- реса 3 прибавляется I. Параллельно блок 7 анализирует содержимое сдвигаемой информации с целью выявления тех разря дов регистра 5 в которых записан О. После трех сдвигов в регистре адреса блока 3 будет записан адрес} РА: г m / m 3/ + 3 6, а в блоке 7 зафиксируется появление О в третьем разряде регистра 5, на выходной информационной шине Ю при этдм появится содержимое третьей ячейки памяти информационного массива. Во время сдвигов регистра сдвигается и содержимое блока 6, и в момент появления О на входе блока 7 в соответствующий разряд блока 6 заносится признак освободившейся ячейки (из которой считана информация) О. Таким образом модифицируется двоичное слово занятости Р. Модифицированное слово Р из блока 6 поступает на входной регистр и затем записывается в ячейку ЯП О. После этого исходный массив, который рассмотрен выше в качестве примера, примет вид: ЯП О 10 О ЯП 1 О О О ЯП 2 1 о о Поле признаков ЯП 3 О О О ЯП 3 о о о ЯП 4 1 1 о ЯП 5 О О О Информационный массив ЯП 6 О о О . Форм у л а изобретения Ассоциативное запоминающее устройство, содержащее накопитель, подключен ный к входному и выходному регистрам и блоку выборки адреса, отличаю щееся тем, что, с цепью расширения области применения устройства, оно соде жит логический блок, блок определения очередности обращения и регистр призна ка обращения, причем информационные входы и выходы блока определения очередности обращения подключены соответ ственно к выходам выходного и входам

8 вхопногО регистров, информациояшло В1Л- хоп(1 выхоаного регистра соединены с ияформзяионными входами входного, регистра, управляющий выход выходного югистра соединен с одним из входов логического блока и счетным входом блока выборки адреса, выход логического блока соединен с одним из управляющих входе блока определения очередности обращения, выход регистра признака обращения подключен к управляющим входам входного и выходного регистров и другому управляющему входу блока определения очередности обращения, управляющий выход которого соединен с другим входом логического блока. Источники информации, принятые во внимание при экспертизе 1,Патент Франции № 2012714, кл. Q 11 С 11/00, 1972. 2.Авторское свидетельство СССР NO 4461 ОТ, кл. Q С1 С 11/06, 1Й72.

...-- ,;, ,.,., , . .i;V/.l-I-H

662972

662972

Запись

fwrim-J-f7.- «У; РА-.0 ВР- -1ЯП 01; О.

КП

Hem

BX.. 1ЙШ1; PA: /ffv/; SOO; /SOO/; ЯП: /Вя.Р/.,

SOOi9lBOOl;K--Ki-1

Hem

PA 6;8P: Inn/iSJt.P: /SOO/ Y/BP/ СЦ-1; ЯП О: /8Л.Р

3P lnnjj SX,P:(/SPA Ш/) VfSвOлy J

f).P/;Cf: Cv+7 /.T

S.I

нет

11, JZ

13.If