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

 

.Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано при построении ассоциативных запоминающих устройств на основе модулей памяти с произвольным доступом. Целью изобретения является повышение информационной емкости устройства. Устройство содержит блок 1 памяти, состоящий из модулей памяти 2i - 2m с произвольным доступом , распределитель 3 сигналов записи, счетчик 7 адреса и регистр 9 числа. Устройство позволяет сократить физический объем памяти при увеличении разрядности чисел, являющихся признаками ассоциативного поиска. 2 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5))5 G 11 С 15/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ4ЕТЕЛЬСТВУ

7<

tQ

«Ъ (21) 4765086/24 (22) 04,12.89 (46) 23,05.92. Бюл. N 19 (71) Научно-исследовательский институт электротехники (72} Ю.Ф. Федосов и В.Н. Ка ря ки н (53) 681.327 (088,8) (56) Авторское свидетельство СССР

Мт 1251178, кл, G 11 С 15/00, 1985, Авторское свидетельство СССР

N - 1363307, кл. G 11 С 15/00, 1987. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57} Изобретение относится к вычислительной технике, в частности к устройствам хра„„543 1735907 А1 нения информации, и может быть использовано при построении ассоциативных запоминающих устройств на основе модулей памяти с произвольным доступом, Целью изобретения является повышение информационной емкости устройства. Устройство содержит блок 1 памяти, состоящий из модулей памяти 21 — 2m с произвольным доступом, распределитель 3 сигналов записи, счетчик 7 адреса и регистр 9 числа. Устройство позволяет сократить физический объем памяти при увеличении разрядности чисел, являющихся признаками ассоциативного поиска. 2 ил.

1735907

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

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

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

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

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

Наиболее близким по технической сущности к предлагаемому является ассоциативное оперативное запоминающее устройство, содержащее коммутатор, блок памяти, регистр числа, регистр маски. индексный регистр, блок модификации признака поиска, блок управления, элементы И, элемент ИЛИ, элемент НЕ, элементы НЕРАВНОЗНАЧНОСТЬ, К существенным признакам устройства, имеющим сходство с признаками изобретения, следует отнести наличие блока памяти на основе модулей с . произвольным доступом, на адресные входы которого подается информация, а на информационный вход подается сигнал управления регистра числа, выходы которого являются информационными выходами устройства, выходы "Положительный результат поиска" и входов "Запись", "Стирание", 10

Сущность работы указанного устройства состоит в том, что в блок оперативной памяти объемом 2 (и — разрядность чиn+1 сел) записывается информация о наличии заносимого в память слова, что позволяет осуществлять ассоциативный поиск за один цикл обращения к памяти произвольного доступа. Таким образом, в памяти может храниться информация о наличии или отсутстВии до 2" слОВ

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

Например, при увеличении разрядности числа в два раза (2n) отношение обьема памяти к выбранному необходимому составляет 2 "/2" = 2". Это означает, что, например, 20 при и = 10 объем памяти более необходимого объема в 2 раз, т.е, более, чем в 1000

10 раз.

Цель изобретения — повышение информационной емкости устройства, 25 Указанная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее блок памяти из модулей памяти с произвольным доступом, распределитель записи, первый вход которого является

30 внешним входом "Стирание", второй вход является внешним входом "Запись-Считывание", выходы распределителя записи соединены с входами "Запись-Считывание" соответствующих модулей, счетчик адреса, 35 выходы которого являются внешними выходами устройства, регистр числа, входы которого являются информационными входами устройства, а выходы являются информационными выходами устройства и младшими

40 разрядами соединены с адресными входами первого модуля, введены следующие отличия: выходы избыточных разрядов регистра числа соединены с первой группой адресных входов второго и последующих

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

50 "Стирание", выходы последнего модуля, соответствующие выходам счетчика адреса, соединены с информационными входами счетчика адреса, выход последнего модуля, соответствующий входу "Стирание", являет55 ся выходом "Результат" устройства, остальные входы распределителя записи соединены с выходами всех модулей, соответствующими входу "Стирание", Существенные признаки, отличающие предлагаемое ассоциативное запоминаю1735907 щее устройство от известного, состоят в следующих отличиях; выходы избыточных разрядов регистра числа соединены с первой группой адресных входов второго и последующих модулей, выходы каждого модуля соединены с второй группой адресных входов следующего модуля, информационные входы модулей поразрядно объединены с выходами счетчика адреса и входом "Стирание", выходы последнего модуля, соответствующие выходам счетчика адреса, соединены с информационными входами счетчика адреса, выход последнего модуля, соответствующий входу "Стирание", является выходом "Результат" устройства, остальные входы распределителя записи соединены с выходами всех модулей, соответствующими входу "Стирание", Введение этих признаков позволяет снизить физический объем памяти при увеличении разрядности числа на m разрядов и сохранении количества хранимых чисел . до2" посравнениюсизвестнымс2" бит

2m(n+1), 2n+1

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

Ассоциативное запоминающее устройство (фиг.1) содержит блок 1 памяти из модУлей памЯти 21 — 2m с пРоизвольным доступом, распределитель 3 сигналов записи, первый вход которого является входом 4

"Стирание", второй вход является входом 5

"Запись-считывание", выходы 61 — 6 распределителя 3 записи соединены с входами . "Запись-считывание" соответствующих модулей, счетчик 7 адреса, выходы 8 которого являются известными выходами устройства, регистр 9 числа, входы которого являются информационными входами 10 устройства, а выходы являются информационными выходами 11 устройства и младшими разрядами соединены с адресными входами первого модуля 21, выходы 11 избыточных разрядов регистра 9 числа соединены с первой группой адресных входов второго и последующих модулей 22 — 2m, выходы 121 — 12m-1 и 131 — 13m-1 каждого модуля соединены с второй группой адресных входов следующего модуля, информационные входы модулей 2> — 2m поразрядно объединены и соединены с выходами 8 счетчика 7 адреса и входом "Стирание". выходы

12m последнего модуля 2m, соответствующие выходу 8 счетчика 7 адреса, соединены с информационными входами счетчика 7 адреса, выход 13m последнего модуля 2m, соответствующий входу 4 "Стирание", является выходом "Результат" устройства, 5

55 остальные входы распределителя 3 записи соединены с выходами 13 — 13п всех модулей, соответствующими входу 4 "Стирание".

Распределитель 3 записи (фиг.2) содержит мультиплексор 14, информационные входы которого соединены с выходами 131—

13 блока 1 памяти, его выход 15 соединен с вторым входом схемы ИЛИ 16, первый вход которой соединен с входом 4 "Стирание" и с входом управления режимом "Вычитание-суммирование" реверсивного счетчика 17, выход 18 схемы ИЛИ 16 является первым входом схемы И 19, вторым входом схемы И 19 является вход 5

"Запись-считывание", выход 20 схемы И 19 соединен с информационным входом демультиплексора 21, выходы 22 реверсивного счетчика 17 соединены с управляющими входами мультиплексора 14 и демультиплексора 21, выходы 6> — 6П которого являются выходами распределителя 3 записи.

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

Работа устройства заключается в следующем, В режиме записи в регистр 9 числа заносится слово, на выходах счетчика 7 адреса действует очередной код адреса, счетчик 17 установлен низким уровнем на входе 4 в режим "Суммирование", инициируется вход

5 "Запись-считывание", на котором формируется последовательность чередующихся с тактовой частотой уровней записи и считывания, на выходах 61 — ám распределителя 3 записи последовательно формируются уровни записи в направлении от 6> к 6m, чередуясь с уровнями считывания, при этом на невыбранных выходах действуют только уровни считывания.

Таким образом, запись в выбранный модуль производится по адресу, считанному из предыдущего модуля в предыдущем такте и дополненному избыточными разрядами регистра 9 числа, а для первого модуля 2>— считанному из младших разрядов регистра

9 числа, В результате этого в ячейки всех модулей, соответствующих входу 4 "Стирание", записываются нули. Это означает, что ячейки заняты. Для обеспечения однозначной адресации запись нуля в любую ячейку однократная. Если ячейка до записи была уже занята, то сигнал записи с входа 5 через схему И 19 не проходит из-за нулевого уровня, поступившего с одного из выходов 131—

13m блока 1 памяти через мультиплексор 14 и схему ИЛИ 16 на первый вход схемы И 19.

Режим записи заканчивается увеличением на единицу содержимого счетчика 7 адреса. Внешние выходы 8 кода адреса ис1735907 пользуются в этом режиме для контроля заполнения запоминающего массива, В режиме стирания счетчик 7 адреса сбрасывается в нулевое состояние, в регистр 9 числа заносится слово с нулевым кодом, счетчик 17 установлен низким уровнем на входе 4 в режим "Суммирование", осуществляется режим записи установленного слова без изменения кода адреса, затем инициируется вход 4 "Стирание", высокий уровень на котором устанавливает счетчик 17 в режим "Вычитание", инициируется вход 5 "Запись-считывание", на котором формируется уровень записи, на выходах 61 — ám распределителя 3 записи последовательно формируются уровни записи в направлении от 6 к 61, такая последовательность повторяется дважды.

Таким образом, стирание в выбранном модуле производится по адресу, считанному в предыдущем такте. В результате этого в ячейки всех модулей, соответствующих входу 4 "Стирание", записываются единицы. Это означает, что ячейки освобождены, Запись единицы в любую ячейку производится независимо от занятости ячейки, так как в этом случае на входе 4 "Стирание" действует высокий уровень, который через схему ИЛИ 16 дает разрешение на прохождение сигнала записи с входа 5 через схему

И 19.

Далее сигнал стирания снимается, содержимое счетчика 7 адреса увеличивается на единицу, и все повторяется до заполнения счетчика 7 адреса.

Затем счетчик 7 адреса сбрасывается в нулевое состояние, в регистр 9 числа заносится новое слово, для которого производится указанный процесс стирания, Для уменьшения времени стирания каждое новое слово отличается от предыдущих слов одновременно во всех группах избыточных разрядов регистра 9 числа, В режиме. ассоциативного поиска на входе 4 "Стирание" и на входе 5 "Записьсчитывание" устанавливаются низкие уровНИ, На ВЫХОдаХ 61 — 6m раСПрЕдЕЛИтЕЛя 3 записи действуют также низкие уровни. Это определяет режим считывания для всех модулей одновременно, В регистр 9 числа заносится слово, которое устанавливает адрес в модуле 21 и в первых группах адресных входов остальных модулей. Адрес во вторых группах адресных входов модулей 22 — 2m устанавливается по мере считывания из модулей

21 — 2 1, а так как считывание осуществляется с тактовой частотой, то результат считывания с последнего модуля появится через m тактов.

Если в блоке 1 памяти есть информация о записи слова, которое находится в регистре 9 числа, то через m тактов на выход 13

"Результат" устройства будет считан сигнал низкого уровня, в остальных случаях будет считан код адреса записанного слова (номер слова).

По сравнению с известным предлагаемое техническое решение позволяет существенно сократить объем памяти при увеличении разрядности числа и неизменности объема хранимых слов, Например, при увеличении разрядности и числа на m разрядов для блока памяти известного устройства, имеющего объем 2" бита требуи+)+п ется увеличить объем памяти до 2", т.е, до 2() (= 2 модулей известного уст(n+1+m)-(и+1) m ройства.

B предлагаемом техническом решении расчет необходимого объема памяти удобно произвести в количестве модулей, примененных в известном устройстве, с распределением избыточных разрядов регистра 9 числа, например, по одному разряду на каждый модуль, В этом случае можно считать, что на первый модуль тоже подан избыточный разряд.

Таким образом, количество модулей m совпадает с количеством избыточных разрядов числа общей разрядности n+m и объем памяти составит 2 (" ) модулей прототипа, где(п+1) — количество информационных разрядов модуля предлагаемого технического решения, Объем памяти предлагаемого технического решения должен удовлетворять требованию 2 " ) <2 или logz2m(n+1)cm. Это является условием, при выполнении которого достигается цель изобретения, Формула изобретения

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

1735907

E) Z

45

Составитель М,Лапушкин

Техред М,Моргентал Корректор О,Кравцова

Редактор Е.Папп

Заказ 1819 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 адреса являются соответственно входом синхронизации и входом задания режима устройства, от л и ч а ю щ е е с я тем, что, с целью повышения информационной емкости устройства, выходы старших разрядов регистра числа соединены с адресными входами первых групп соответствующих модулей памяти блока памяти, выходы каждого модуля блока памяти соединены с адресными входами второй группы последующего модуля блока памяти, выходы последнего модуля памяти блока памяти соединены с информационными входами счетчика адреса, информационные входы разрядов модулей памяти блока памяти, кроме последних, поразрядно объединены и соединены с выходами счетчика адреса, информационные

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