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

ОПИСАНИЕ 1 Союз Советски вСоциалистическиеРеспублик ВТОРСК СВИДЕТЕЛЬСТВУ(61) Дополнительное к и т. свид-в 22)Заявлено 18.06, 79 21) 2807658/18 С 15/О Государственный комнт ое ием заяв 23) Прнорнте лам нэобретенин аткрытнй бл 4. 81, Бюллетень Ле 16 ДК 681.З 2 н 0 я описания 30.04 опублико 72) Автоты изобретени Таран и Хо 4 яко кий евский научно-иссл довательскии 1) Заявите рийного оборудования ститут пери 4) АССОЦИАТИВНОЕ ЗАПОМИНА 10 ЩЕЕ УСТРОЙСГ ых и при этом каждыи вый массив отоб и ( дисплейный Ф лучае увеличива и сокращаются ративного редак раз фражаемайл .ются руетсяинформа В по- атраопросом б следуем ты памят кличес ьших масси стройства г а ическов возм тиро нос п ния ча ассоциативв больших масс с Изобретение относится к запоминам устройствам и может использоься в устроиствах с многократн информации, например в у х и системах отображения р ф й информации на базе электроннолучев трубки (ЭПТ ).Известно ассоциативное запомина ющее устройство, заданого поиска котороговах информации решается программны способом 1 1,Однако такое решение оказываетс неэффективным для устройств и систем, критических к скорости опроса массива по заданному ассоциативному признаку, так как при этомлибо кращается объем выводимой на экран информации (если поиск осуществля-. ется в каждом цикле регенерации ), бо увеличивается время ответа ( есл поиск выполняется только в случае появления изменений в отображаемых данных,Наиболее близким техническим решением к предлагаемому является запоминающее устройство, содержащее блок памяти, буферный регистр, пер вые входы и выходы которого подключены к выходам и информационным входам блока памяти соответственно, коммутаторы адреса, первый и второй регистры-счетчики адреса 12 .Недостатки устройства заключаются в следующем. Устройство не может обе печить быстрое чтение маркированных данных при динамическом изменении Функции маркирования вследс твие невозможности пропуска немаркированных данных без предварительного формирования дисплейного Файла. Знн40 При этом логический блок. содержит элемент И, сумматор, регистр и элемент: задержки, причем одни из входов сумматора подключены к выходам регистра, один из входов которого соединен со 3 82642 читель;ъй удельный вес адреснои информации при работе со списками приводит к значительным затратам оборудования 1,памяти ) И, следовательно, к уменьшению эффективного быстродей 5 ствия по сравнению с памятью с последовательной адресацией.Цель изобретения - упрощение и повышение быстродействия устройства.Поставленная цель достигается 10 тем, что в запоминающее устройство, содержащее накопитель, буферчый регистр, два счетчика адресов, коммутатор адреса, причем адресный и информациОнный входы и информационный выход, 15 .накопителя подключены соответственно к выходу коммутатора адреса, выходу и первому входу буферного регистра, введены компаратор,. маркерный регистр сдвига, блок местного управле- г 0 ния, элементы НЕ, генератор тактовых импульсов, триггер и логический блок, причем выходы счетчиков адресов подключены соответственно ко входам компаратора и элементов НЕ и одному из 25 входов коммутатора адреса, другие входы которого соединены с выходами элементов НЕ, один из входов логического блока подключен к выходу буферного регистра, а другие входы 30 являются входами устройства, выходы логического блока подключены соответственно к одному из входов маркерного регистра сдвига и первому входу блока местного управления, вто рой и третий входы которого подключены соответственно к выходам компаратора и генератора тактовых импульсов, другие входы маркерного регистра сдвига соединены соответственно с выходами буферного регистра и генератора тактовых импульсов, а выходы - со вторым входом буферного регистра и первым входом триггера, выход которого подключен ко входу генератора 45 тактовых импульсов, выход которого соединен со счетными входами счетчиков адресов, выход блока местного управления подключен ко второму входу триггера и управляющим входам 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 со сдвигом на М (где М = 1 ос К) разрядов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 содержит 1 фиг.2) 11 -входовой элемент И 14, к-разрядный комбинационный сумматор 15, регистр 16, служащий для хранения ассоциативной функции, элементзадержки 7. Одни иэ входов сумматора 15 подключены к выходам регистра 16, один из входов которого соединен со входом элемента задержки 17. Выходы сумматора 15 соединены со входами элемента И 14, другие входы сумматора 15, .входы регист. - ра 16, элемента задержки 17 являются входами блока 11, выходами которого являются выходы элемента И 14 и 1 о элемента задержки 17.функционирование устройства применительно к устройствам отображения графической информации заключается в следующем, 5Предполагается, что массив данных в накопителе 1 состоит из случайно распределенных данных, подлежащих отображению на экране ЭЛТ, и данных, не подлежащих отображению, например, данные многослойного изображения при отображении данных 1-го слоя, данные, задающие трехмерные изображения с ви;: димыми и невидимымн элементами изображения, данные, отображаемые на экране ЭЛТ с применением просмотрового окна и масштабирования ( электронной линзы ) с разделением элементов изображения на находящиеся внутри и находящиеся вне окна и т.д. 30Каждый раз после внесения изменений и массив данных или изменения ассоциативной функции, выполняегся так называемый цикл маркирования, в котором последовательно просматривается массив накопителя 1, каждое информационное слово анализируется на соответствие ассоциативной функции и в зависимости от результата11 ц 1 сравнения маркирует ся единицеи или "нулем" в соответствующем маркерном разряде. После завершения цикла маркирования массива устройство переходит в режим индикации, :при,котором маркировнные информа1 1ционные слова (отмеченные 1 в маркерном разряде отображаются на экране ЭЛТ , а немаркированные - пропускаются б ез обращения в накопитель 1 по их адресам.Также предполагается наличие выделенной области памяти для хра" ненни маркерных данных, Каждой ячейке информационного массива выделен 1 бит маркерного массива таким образом (см, фиг.З), что первому инфор.мационному блоку из К-ячеек соответствует последняя маркерная ячейка памяти, второму блоку - предпоследняя и т.д. Такая. организация памяти обеспечивает оптимальное использование обьемапамяти при обеспечении эффективного програмюю-независимого перехода от адресации ос новных данных к адресации маркерных данных и наоборот.Устройство может выполнять маркиро-. вание с упреждением, т.е. использоваться и.в том случае, когда элемент изображения кодируется информационным словом, занимающим 2 и более ячеек памяти.Основные режимы работы устройства- режим чтения данных по маркеру с авто. матическим переходом в режим чтения соответствующей маркерной ячейки, и режим формирования маркерных данных в накопитель 1Кроме того, устройство может работать в рвкимах записи и чтения по адресам, задаваемым на регистровые входы счетчиков 4 и 5.В исходном состоянии регистры 2и 10, счетчики 4 и 5, а также триггер 13 установлены в логический "О".В режиме чтения данных по маркеруустройство работает следующим образом,Блок 12 переходит в режим чтениямаркерной ячейки памяти ( это осуществляется каждый раз,когда в процессесчета содержимое счетчика 4 достигаетзначения, при котором М младшихразрядов счетчика становятся равными,логическому "О" и в блок 12 поступает соответствующий сигнал от компаратора 9). На адресные входы накопителя коммутируются инвертированныевыходы счетчика 4, сдвинутые на Мразрядов в сторону младшего,т.е.устанавливается адрес по которомусчитывается маркерное слово из последней ячейки памяти, в котором записаны маркерные разряды, соответ-.ствующие информационным словам первого блока данных из К ячеек. Маркерное слово через регистр 2 поступает в регистр 10, после чего блок12 переходит в режим чтения помаркеру. При этом, если в старшемразряде регистра 10 оказывается"1", триггер 13 устанавливается вфО", выполняется чтение информационного слова па адресу, задаваемомусчетчиком 4, после чего триггер 13устанавливается в состояние логическая "1", которая разрешает35 40В режиме формирования маркерных данных осуществляется последовательное чтение данных информационного массива, начиная с "нулевой" ячейки накопителя 1 по содержимому счетчи ка 4. Читаются все ячейки памяти, описывающие данный элемент изображения путем прибавления "единиц" к содержимому счетчика 4 и анализируются на соответствие ассоциативной функ-.50 ции в блоке1. Затем обобщенный результат сравнения логический Ои или логическая "1" ) устанавливается на входе последовательной записи регистра .10, а на входах блока 12 кодготовности маркерного бита и сигнал завершения чтения полного информационного слова, задающего элемент изображения, Счетный вход счетчика 4 7 8264работу генератора 8. Каждый импульс,поступая на счетный вход счетчика 4 и на вход сдвига регистра 10,осуществляет синхронно прибавление"1" к содержимому счетчика 4 и5сдвиг содержимого регистра 1 О наодин шаг в сторону старших разрядов. Если после этого в старшемразряде регистра 10 оказываетсялогический "0", ослцествляется щснова прибавление 1" к содержимому счетчика 4 и сдвиг на одиншаг содержимого регистра 10, ит,д. до появления "1" в старшемразряде регистра 10, после чеготриггер 13 устанавливается в 0",блокируя через генератор 8 работусчетчика 4 и регистра 10. Выполняется чтение информационного слова изнакопителя 1 по адресу, задаваемомусчетчиком 4. Если содержимое счетчика 4 достигает значения, кратного ММ младших разрядов счетчика = 01,блок 12 переходит снова в режим чтения очередной маркерной ячейки, соответствующей очередному информационному блоку из У ячеек, и процесс продолжается аналогично вышеописанному доконца информационного массива. Работа счетчика 5 в описанном режиме блокируется сигналом от блока 12,Таким образом, в режиме чтенияпо маркеру.из накопителя 1 читаютсятолько те слова данных, соотвествующие маргерные разряды которых равнылогической "1". Адреса остальныхинформационных слов сканируются соскоростью поступления синхроимпульсов от генератора 8,21 .8блокируется, разрешается синхронный счет счетчика 5 и сдвигзапись по входу сдвига) маркерных данных в регистр О со скоростью поступления тактовых импульсов, Процесс продолжается либо до поступления сигнала сравнения содержимого счетчиков 4 иР 5 в блок 2 с компаратора 9, либо до появления в счетчике 5 кода, содержащего М единиц в младших разрядах. В первом случае устройство переходит в режим чтения и анализа ячеек памяти, содержащих следующее информационное слово (по содержимому счетчика 4), во втором случае устройство переходит в режим записи маркерной информации, для чего на четвертые входы коммутатора 3 коммутируется инверсный код счетчика 5, сдвинутый на М-разрядов в сторону младшего, маркерные данные с регистрА 10 переписываются в регистр 2 и блоком 12 инициируется сигнал записи данных в соответствующую ячейку маркерного массива накопителя 1, после чего устройство переходит в режим чтения и анализа данных следующих ячеек памяти, После завершения цикла чтения массива данных устройство переходит в режим чтения данных по маркеру.Положительный эффект от внедрения устройства заключается в следующем.Устройство обеспечивает чтение информации по маркеру с пропусканием немаркированной информации без чтения всех ячеек памяти, что позволяет повысить частоту регенерации (сканирования) либо повысить объем отображаемых данных при той же частоте сканирования без формирования дисплейного файла. Указанный эффект в устройстве достигается за счет использования 1/к части памяти.В то же время осуществляется экономия объема памяти в 1,5-2 раза по сравнению с системами и устройствами, требующими выделения памяти для хранения дисплейного файла или с устройствами со списочной организацией информационного массива.Формула изобретения1, Ассоциативное запоминающее устройство, содержащее накопитель,82642 9буферный регистр, счетчики адресов,коммутатор адреса, причем адресныйи инФормационный входы и информаци,онный выход накопителя подключены соотвественно к выходу коммутатора адре 5са, выходу и первому входу буферногорегистра, отличающеесятем, что, с целью упрощения и повышения быстродействия устройства, оносодержит компаратор, маркерный регистр 10сдвига, блок местного управления,элементы НЕ, генератор . тактовыхимпульсов, триггер и логический блок,причем выходы счетчиков адресовподключены соответственно ко входамкомпаратора и элементов НЕ и одномуиз входов коммутатора адреса, другиевходы которого соединены с выходамиэлементов НЕ, один иэ входов логического блока подключен к выходу 20буферного регистра, а другие входыявляются входами устройства, выходылогического блока подключены соответственно к одному из входов маркерного регистра сдвига и первому 25входу блока местного управления,второй и третий входы которого подключены соответственно к выходам компаратора и генератора тактовых импульсов, другие входы маркерного регистра сдвига соединены соответственнос выходами буферного регистра и генератора тактовых импульсов, а выходы - со вторым входом буферного 1 1 Орегистра и первым входом триггера, выход которого подключен ко входу генератора тактовых импульсов, выход которого соединен со счетными входами счетчиков адресов, выход блока местного управления подключен ко,второму входу триггера и управляющим входам накопителя, маркерного регистра сдвига, коммутатора адреса и счетчиков адресов,2. Устройство по п.1, о т л и ч аю щ е е с я тем,что логический блок содержит элемент И, сумматор, регистр и элемент задержки, причем один из входов сумматора подключены к выходам регистра, один из входов которого соединен со входом элемента задержки, выходы сумматора соединены со входами элемента И, другие входы сумматора, входы регистра, элемента задержки являются входами логического блока, выходами которого явл ются выходы элемента И и элемента задержкиИсточники информации,принятые во внимание при экспертизе1. Шигин А. Г., Дерюгин А. А.Цифровые вычислительные машины ( Память ЦВМ ) . М., "Советское радио",197 б, с,415.2, Запоминающие устройства. Сборникстатей, вып.4. М., "Энергия", 1974, с.7 (прототип),