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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

I

Изобретение относится к sanoNMHaющим устройствам и может использоваться в устройствах с многократным циклическим опросом больших массивов информации, например в устройствах и системах отображения графической информации на базе электроннолучевой трубки (ЭЛТ).

Известно ассоциативное запоминающее устройство, задача ассоциативного поиска которого в больших массивах информации решается программным способом l ..

Однако такое решение оказывается неэффективным для устройств и систем, критических к скорости опроса массива по заданному ассоциативному признаку, так как при этоМ; либо сокращается объем выводимой на экран информации (если поиск осуществля:,ется в каждом цикле регенерации), ли.бо увеличивается время ответа ( если поиск выполняется только в случае появления изменений в отображаемых

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

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

Недостатки устройства заключаются в следующем. Устройство н -может обепечить быстрое чтение маркированных данных при динамическом изменении функции маркирования вследствие невозможности пропуска немаркированных данных без предвлрительного формирования дисплейного файла, 3ir;i3 8 -вдтельньй удельньш вес адресной ин|формации при работа со списками прив дит к1 значительным затратам оборудования (памяти ) и, следовательно, к уменьшению эффективного быстродействия по сравнению с памятью с после довательной адресацией. Цель изобретения - упрощение и по вышение быстродействия устройства Поставленная цель достигается тем, что в запоминающее устройство, содержащее накопитель, буферный регистр, два счетчика адресов, коммута тор адреса, причем адресньй и информ ционный входы и информационньгй выход накопителя подключены соответственно к выходу коммутатора адреса, выходу и первому входу буферного регистра, введены компаратор, маркерный регистр сдвига, блок местного управления, элементы НЕ, генератор тактовых импульсов, триггер и логический блок причем выходы счетчиков адресов подключены соответственно ко входам ком паратора и элементов НЕ и одному из входов коммутатора адреса, другие входы которого соединены с выходами элементов НЕ, один из входов логического блока подключен к выходу буферного регистра, а другие входы являются входами устройства, выходы логического блока подключены соответственно к одному из входов маркерного регистра сдвига и первому входу блока местного управления, вто рой и третий входы которого подключе ны соответственно к выходам компаратора и генератора тактовых импульсов другие входы маркерного регистра сдвига соедщ1ены соответственно с выходами буферного регистра и генератора тактовых импульсов, а выходы со вторым входом буферного регистра и первым входом триггера, выход кото рого подключен ко входу генератора тактовых импульсов, выход которого соединен со счетными входами счетчиков адресов, выход блока местного управления подключен ко второму входу триггера и управляющим входам накопителя, маркерного регистра сдэи коммутатора адреса и счетчиков адре сов. При этом логический блок содержит .элемент И, сумматор, регистр и элеме задержки, причем одни из входов сумматора подключены к выходам регистра один из входов которого соединен со 4 входом элемента задержки, выходы сумматора соединены со входами элемента И другие входы сумматора, входы регистра, элемента задержки являются входами логического блока, выходами которого являются выходы элемента И и элемента задержки. На фиГо1 представлена структурная схема устройства; на фиго2 - структурная схема логического блока; на фиг.З - размещение данных в накопителе при работе устройства. Устройство фиг,1) содержит накопитель 1, к-разрядный буферный регистр 2, коммутатор адреса 3, первый 4 и второй 5 счетчики адресов, две группы элементе НЕ 6 и 7, генератор тактовых импульсов 8, компаратор 9, маркерньй регистр сдвига 10, логический блок 11, блок 12 местного управления и триггер 13, Адресный и информационный входы и информационный выход накопителя 1 подключены соответственно к выходу коммутатора 3, выходу и первому входу регистра 2, Выходы счетчиков адресов 4 и 5 . подключены соответственно ко входам компаратора 9 и элементов НЕ 6 и 7 одним из входов коммутатора 3 со сдвигом на М (где М ) разрядов в сторону младшего. Другие входы коммутатора 3 соединены с выходами элет . ментов НЕ 6 и 7, Один из выходов блока 11 подключен к выходу регистра 2, а другие входы являются входами устт ройства. Выходы блока 11 подключены соответственно к одному из входов регистра 10 и первому входу блока 12, второй и третий входы которого подключены соответственно к выходам компаратора 9 и генератора 8, Другие вхо-. ды регистра 10 соединены соответственно с выходами регистра 2 и генератора 8, а выходы - со вторым входом регистра 2 и первым входом триггера 13, выход которого подключен ко входу генератора 8, выход которого соединен со счетными входами счетчиков 4 и 5, Выход блока 12 подключен ко второму входу триггера 13 и управляющим входам накопителя 1, регистра 10, коммутатора 3 и счетчиков 4 и 5, Логический блок 11 содержит (фиг,2 К-входовой элемент И 14, к-разрядный комбинационный сумматор 15, регистр 16, служащий для хранения ассоциативной функции, элемент

58

задержки 17. Одни из входов суммагора 15 подключены к выходам регистра 16, один из входов которого соединен со входом элемента задержки 17. Выходы сумматора 15 соединены со входами элемента И 14, другие входы сумматора 15, входы регистра 16, элемента задержки 17 являются входами блока 11, выходами которого являются выходы элемента И 14 и элемента задержки 17. .

Функционирование устройства применительно к устройствам отображения графической информации заключается в следующем..

Предполагается, что массив данных в накопителе 1 состоит из случайно распределенных данных, подлежащих отображению на экране ЭЛТ, и данных, не подлежащих отображению, например, данные многослойного изображения npto отобра5{ ении данных 1-го слоя,данные, задающие трехмерные изображения с вигдимыми и невидимыми элементами изобржения, данные, отображаемые на экро.не ЭЛТ с применением просмотрового окна и масштабирования (электронной линзы ) с разделением элементов изображения на находящиеся внутри и находящиеся вне окна и т.д.

Каждый раз после внесения изменений .и массив данных или измеканкя ассоциативной функции, выполняется так назьтаемый цикл маркирования, в котором последовательно просматривается массив накопителя 1, каждое информационное слово анализируется на соответствие ассоциативной функции и в зависимости от результата сравнения маркируется единицей или нулем в соответствующем маркерном разряде. После завершения цикла маркирования массива устройство переходит в режим индикации, при.котором маркировнные инфо1 ма«ционные слова (отмеченные 1 в маркерном разряде отображаются на экране ЭЛТ, а немаркированные пропускаются без обращения в накопитель 1 по их адресам.

Также предполагается наличие вьщеленной области памяти для хранения маркерных данных. Каждой ячейк информационного массива выделен 1 бит маркерного массива .таким образом см, фиг.З), что первому инфор.мационному блоку из К-ячеек соот- ветствует последняя маркерная ячейка памяти, второму блоку - предпоI6

следняя и т.д. Такая организация памяти обеспечивает оптимальное использование объемапамяти при обеспечении эффективного программно-независимого перехода от адресации ос новных данных к адресации маркерных данных и наоборот.

Устройство моясет выполнять, маркирванне с упреждением, т.е. использоваться и в том случае, когда элемент изображения кодируется информа1ЩОННЫМ словом, занимающим 2 и более ячеек памяти.

Основные режимы работы устройства режим чтения данных по маркеру с автматическим переходом в режим чтения соответствующей маркерной ячейки, и 0ежим формирования маркерных данных в накопитель 1.

Кроме того, устройство может работать в режимах записи и чтения по адресам, задаваемым на регистровые входы счетчиков 4 и 5.

В исходном состоянии регистры 2 и 10, счетчики 4 и 5, а также триггер 13 установлены в логический О.

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

Блок 12 переходит в режим чтения маркерной ячейки памяти (это осуществляется каждый раз,когда впроцессе счета содержимое счетчика 4 достигае значения, при котором М младших разрядов счетчика становятся равными логическому О и в блок 12 поступает соответствующий сигнал от компаратора 9). На адресные входы накопителя коммутируются инвертированные выходы счетчика 4, сдвинутые на М разрядов в сторону младшего,т.е. устанавливается адрес по которому считывается маркерное слово из последней ячейки памяти, в котором записаны маркерные разряды, соответствуняцие информационным словам первого блока данных на К ячеек. Маркерное слово через регистр 2 поступает в регистр 10, после чего блок 12 переходит В режим чтения по маркеру. При этом, если в старшем разряде регистра 10 оказывается 1, триггер 13 устанавливается в О, выполняется чтение информационного слова па адресу, задаваемому счетчиком 4, после чего триггер 13 . устанавливается в состояние логическая 1, которая разрешает

работу генератора 8. Каждый импульс, поступая на счетный вход счетчика 4 и на вход сдвига регистра 10, осуществляет синхронно прибавление 1 к содержимому счетчика 4 и сдвиг содержимого регистра 10 на один шаг в сторону старших разрядов. Если после этого в старшем разряде регистра 10 оказьшается логический О, осуществляется снова прибавление к содержимому счетчика 4 и сдвиг на один шаг содержимого регистра 10, и т.д. до появления 1 в старшем разряде регистра 10, после чего триггер 13 устанавливается в О, блокируя через генератор 8 работу счетчика 4 и регистра 10. Выполняется чтение информационного слова из накопителя по адресу, задаваемому счетчиком 4. Если содержимое счетчика 4 достигает значения,кратного М (.М младших разрядов счетчика 07, блок 12 переходит снова в режим чтения очередной маркерной ячейки, соот ветствующей очередному информационному блоку из У ячеек, и процесс продожается аналогично вышеописанному до конца информационного массива. Работа счетчика 5 в описанном режиме блокируется сигналом от блока 12.

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

данных осуществляется последовательное чтение данных информационного массива, начиная с нулевой ячейки накопителя 1 по содержимому счетчика 4. Читаются все ячейки памяти, описывающие данный элемент изображения путем пpибaвJJeния единиц к содержимому счетчика 4 и анализируются на соответствие ассоциативной фундии в блоке 11. Затем обобщенный результат сравнения (логический О или логическая 1) устанавливается на входе последовательной записи регистра .10, а на входах блока 12 ко готовности маркерного бита и сигнал завершения чтения полного информа1щонного слова, задающего элемент изображения. Счетный вход счетчика 4

блокируется, разрешается синхронный счет счетчика 5 и сдвиг ( запись по входу сдвига) маркерных данных в регистр 10 со скоростью поступления тактовых импульсов. Процесс продолжается либо до поступления сигнала сравнения содержимого счетчиков 4 и 5 в блок 12 с компаратора 9, либо до появления в счетчике 5 кода, содежащего М единиц в младших разрядах. В первом случае устройство переходит в режим чтения и анализа ячеек памят содержащих следующее-информационное слово (по содержимому счетчика 4, во втором случае устройство переходит в режим записи маркерной информации, для чего на четвертые входы коммутатора 3 коммутируется инверсны код счетчика 5, сдвинутый на М-разрядов в ciTOpOHy мпадшего, маркерные данные с регистр 10 переписываются в регистр 2 и блоком 12 инициируется сигнал записи данных в соответствующую ячейку маркерного массива накопителя 1, после чего устройство переходит в режим чтения и анализа данных следующих ячеек памяти.После завершения цикла чтения массива данных устройство переходит в режим чтения данных по маркеру.

Положительньш эффект от внедрения устройства заключается в следующем.

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

I-

В то же время осуществляется

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

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

98

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

I10

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

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

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

2.Запоминающие устройства. Сборни статей, вып.4. М., Энергия, 1974, с.7 (прототип).