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

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

Иллюстрации

Показать все

Реферат

 

ОПИСЛНИИ„

Союз Советски к

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22)3à><>eHO 18.06,79 (21) 2807658/18-24 (51) М. Кл. с присоединениеM заявки,%

G 11 С 15/00

Государственный комнтет (23) Приоритет по делам нэобретений н открытий

Опубликовано 30.04. 81. Бюллетень Юе 16 (53) УДК 681. 327 (088.8) Дата опубликования описания 30.04. 81

В, Ф. Каплун, .П, - Г. Таран и В. И.„Хол/яков (72) Авторы изобретения

1 ос кий

Киевский научно-исследовательский и институт периферийного оборудования (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИЧА10ЩЕЕ УСТРОЙСТВО

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

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

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

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

Недостатки устройства заключаются в следующем. Устройство не может обеспечить быстрое чтение маркированных данных при динамическом изменении функции маркирования вслед< твис невозможности пропуска пемаркированных данных без предварительногo формирования дисплейного файла. Впп40

3 82642 читель;..6И удельный вес адреснои ин1

- формации при работе со списками приводит IC значительным затратам оборудования (памяти ) и, следовательно, к уменьшению эффективного быстродей5 ствия по сравнению с памятью с последовательной адресацией.

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

Поставленная цель достигается 10 тем, что в запоминающее устройство, содержащее накопитель, буферчый регистр, два счетчика адресов, коммутатор адреса, причем адресный и информационный входы и информационный выход, 15 .накопителя подключены соответственно к Выходу коммутатора адреса, выходу и первому входу буферного регистра, введены компаратор,. маркерный регистр сдвига, блок местного управле- Zo ния, элементы НЕ, генератор тактовых импульсов, триггер и логический блок, причем выходы счетчиков адресов подключены соответственно ко входам компаратора и элементов НЕ и одному из 25 входов коммутатора адреса, другие входы которого соединены с выходами элементов НЕ, один из входов логического блока подключен к выходу буферного регистра, а другие входы 30 являются входами устройства, выходы логического блока подключены соответственно к одному из входов маркерного регистра сдвига и первому входу блока местного управления, вто- 35 рой и третий входы которого подключены соответственно к выходам компаратора и генератора тактовых импульсов, другие входы маркерного регистра сдвига соединены соответственно с выходами буферного регистра и генератора тактовых импульсов, а выходы— со вторым входом буферного регистра и перв6|м входом триггера, выход кбторого подключен ко входу генератора тактОВых импульсов Выход кОтОрогО соединен со счетными входами счетчиков адресов, выход блока местного управления подключен ко второму входу триггера и управляющим входам 50 накопителя, маркерного регистра сдвига, коммутатора адреса и счетчиков адресов. входом элемента задержки, выходы сумматора соединены со входами элемента И другие входы сумматора, входы регистра, элемента задержки являются входами логического блока, выходами которого являются выходы элемента И и элемента задержки.

На фиг. 1 представлена структурная схема устройства; на фиг.2 — структурная схема логического блока; на фиг.3 — размещение данных в накопителе при работе устройства.

Устройство (фиг.1) содержит накопитель 1, к-разрядный буферный регистр 2, коммутатор адреса 3, первый

4 и второй 5 счетчики адресов, две группы элементв НЕ 6 и 7, генератор тактовых импульсов 8, компаратор 9, маркерный регистр сдвига 10, логический блок 11, блок 12 местного управления и триггер 13. Адресный и информационный входы и информационный выход накопителя 1 подключены соответственно к выходу коммутатора

3, выходу и первому входу регистра 2.

Выходы счетчиков адресов 4 и 5 . подключены соответственно ко входам компаратора 9 и элементов НЕ 6 и 7 одним из входов коммутатора 3 со сдвигом на М {где М = loq К) разрядов

2 в сторону младшего, Другие входы коммутатора 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, служащий для хранения ассоциативной функции, элемент

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

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

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

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

Каждый раз после внесения изменений и массив данных или измен,ния ассоциативной функции, выполняегся так называемый цикл маркирования, в котором последовательно просматривается массив накопителя 1, каждое информационное слово анализируется на соответствие ассоциативной функции и в зависимости от результата и II сравнения маркирует ся единицеи 4О или "нулем" в соответствующем маркерном разряде. После завершения цикла маркирования массива устройство переходит в режим индикации, :при.котором маркировнные информа- 4 .1.

lt ll ционные слова (отмеченные 1 в маркерном разряде отображаются на экране ЭЛТ, а немаркированные— пропускаются без обращения в накопитель 1 по их адресам.

Также предполагается наличие выделенной области памяти для хра" ненни маркерных данных. Каждой ячейке информационного массива выделен 1 бит маркерного массива .таким о6ра- 15 зом (см. фиг.3) что первому инфор.мационному блоку из К-ячеек соответствует последняя маркерная ячейка памяти, второму блоку - предпоследняя и т.д. Такая. организация памяти обеспечивает оптимальное использование обьема памяти при обеспечении эффективного програмьыо-независимого перехода от адресации ос» новных данных к адресации маркерных данных и наоборот.

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

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

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

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

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

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

12 переходит в режим чтения по маркеру. При этом, если в старшем разряде регистра 10 оказывается

"1", триггер 13 устанавливается в

"0", выполняется чтение информационного слова па адресу, задаваемому счетчиком 4, после чего триггер 13 устанавливается в состояние логическая "1", которая разрешает

7 8264 работу генератора 8. Каждый импульс, поступая на счетный вход счетчика 4 и на вход сдвига регистра 10, осуществляет синхронно прибавление

"1" к содержимому счетчика 4 и

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

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

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

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

2l .8 блокируется, разрешается синхронный счет счетчика 5 и сдвиг (запись по входу сдвига) маркерных данных в регистр !О со скоростью поступления тактовых импульсов. Процесс продолжа— ется либо до поступления сигнала сравнения содержимого счетчиков 4 и

5 в блок 12 с компаратора 9, либо до появления в счетчике 5 кода, содержащего М единиц в младших разрядах.

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

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

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

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

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

1, Ассоциативное з апоминающее устройство, содержащее накопитель, 82642

9 буферный регистр, счетчики адресов, коммутатор адреса, причем адресный и информационный входы и информаци онный выход накопителя подключены соотвественно к выходу коммутатора адре5 са, выходу и первому входу буферного регистра, отличающееся тем, что, с целью упрощения и повышения быстродействия устройства, оно содержит компаратор, маркерный регистр 10 сдвига, блок местного управления, элементы НЕ, генератор . тактовых импульсов, триггер и логический блок, причем выходы счетчиков адресов подключены соответственно ко входам компаратора и элементов НЕ и одному из входов коммутатора адреса, другие . входы которого соединены с выходами элементов НЕ, один иэ входов логического блока подключен к выходу 20 буферного регистра, а другие входы являются входами устройства, выходы логического блока подключены соответственно к одному из входов маркерного регистра сдвига и первому 25 входу блока местного управления, второй и третий входы которого подключены соответственно к выходам компаратора и генератора тактовь.х импульсов, другие входы маркерного регист- З0 ра сдвига соединены соответственно с выходами буферного регистра и генератора тактовых импульсов, а выходы — со вторым входом буферного

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

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

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

1. Шигин А. Г., Дерюгин А. А.

Цифровые вычислительные машины (Память ЦВИ ) . M., "Советское радио", 197б, с.415.

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