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

п+1+кт

11

$

)

(Л

С

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

8

+1

ТИ

ь

5

xj

SCO

сл

sQ

о ч

Фиг.1

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

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

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

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

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

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

Сущность работы указанного устройства состоит в том, что в блок оперативной памяти объемом 2n + (п - разрядность чисел) записывается информация о наличии

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

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

5 используется существенный объем памяти. Например, при увеличении разрядности числа в два раза (2п) отношение объема памяти к выбранному необходимому составляет 22п/2п 2П. Это означает, что, например,

0 при п 10 объем памяти более необходимого объема в 2 раз, т.е. более, чем в 1000 раз.

Цель изобретения - повышение информационной емкости устройства.

5Указанная цель достигается тем, что в

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

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

5 выходы которого являются внешними выходами устройства, регистр числа, входы которого являются информационными входами устройства, а выходы являются информационными выходами устройства и младшими

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

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

0 Стирание, выходы последнего модуля, соответствующие выходам счетчика адреса, соединены с информационными входами счетчика адреса, выход последнего модуля, соответствующий входу Стирание, являет5 ся выходом Результат устройства, остальные входы распределителя записи соединены с выходами всех модулей, соответствующими входу Стирание.

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

Введение этих признаков позволяет снизить физический объем памяти при увеличении разрядности числа на m разрядов и сохранении количества хранимых чисел до 2П по сравнению с известным с 2n+ +m бит Ao2m(n+f 2n+1.

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

Ассоциативное запоминающее устройство (фиг.1) содержит блок 1 памяти из модулей памяти 2т - 2m с произвольным доступом, распределитель 3 сигналов записи, первый вход которого является входом 4 Стирание, второй вход является входом 5 Запись-считывание, выходы 61 - 6m распределителя 3 записи соединены с входами Запись-считывание соответствующих модулей, счетчик 7 адреса, выходы 8 которого являются известными выходами устройства, регистр 9 числа, входы которого являются информационными входами 10 устройства, а выходы являются информационными выходами 11 устройства и младшими разрядами соединены с адресными входами первого модуля 2ч, выходы 11 избыточных разрядов регистра 9 числа соединены с первой группой адресных входов второго и последующих модулей 22 - 2т. выходы 12i - 12т-1 и 13i - 13т-1 каждого модуля соединены с второй группой адресных входов следующего модуля, информационные входы модулей 2i - 2m поразрядно объединены и соединены с выходами 8 счетчика 7 адреса и входом Стирание, выходы 12т последнего модуля 2т, соответствующие выходу 8 счетчика 7 адреса, соединены с информационными входами счетчика 7 адреса, выход 13т последнего модуля 2т, соответствующий входу 4 Стирание, является выходом Результат устройства.

остальные входы распределителя 3 записи соединены с выходами 13i - 13m всех модулей, соответствующими входу 4 Стирание. Распределитель 3 записи (фиг.2) содержит мультиплексор 14, информационные входы которого соединены с выходами 13i - 13m блока 1 памяти, его выход 15 соединен с вторым входом схемы ИЛИ 16, первый вход которой соединен с входом 4 Стира0 ние и с входом управления режимом Вычитание-суммирование реверсивного счетчика 17, выход 18 схемы ИЛИ 16 является первым входом схемы И 19, вторым входом схемы И 19 является вход 5

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

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

5Работа устройства заключается в следующем.

В режиме записи в регистр 9 числа заносится слово, на выходах счетчика 7 адреса действует очередной код адреса, счетчик 17

0 установлен низким уровнем на входе 4 в режим Суммирование, инициируется вход 5 Запись-считывание, на котором формируется последовательность чередующихся с тактовой частотой уровней записи и

5 считывания, на выходах распределителя 3 записи последовательно формируются уровни записи в направлении от 6i к 6т, чередуясь с уровнями считывания, при этом на невыбранных выходах действуют только

0 уровни считывания.

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

5 регистра 9 числа, а для первого модуля 2i - считанному из младших разрядов регистра 9 числа. В результате этого в ячейки всех модулей, соответствующих входу 4 Стирание, записываются нули. Это означает, что

0 ячейки заняты. Для обеспечения однозначной адресации запись нуля в любую ячейку однократная. Если ячейка до записи была уже занята, то сигнал записи с входа 5 через схему И 19 не проходит из-за нулевого уров5 ня, поступившего с одного из выходов 13i - 13m блока 1 памяти через мультиплексор 14 и схему ИЛИ 16 на первый вход схемы И 19. Режим записи заканчивается увеличением на единицу содержимого счетчика 7 адреса. Внешние выходы 8 кода адреса используются в этом режиме для контроля заполнения запоминающего массива.

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

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

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

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

В режиме ассоциативного поиска на входе 4 Стирание и на входе 5 Запись- считывание устанавливаются низкие уровни, на выходах 61 - 6m распределителя 3 записи действуют также низкие уровни. Это определяет режим считывания для всех модулей одновременно.

В регистр 9 числа заносится слово, которое устанавливает адрес в модуле 2i и в первых группах адресных входов остальных модулей. Адрес во вторых группах адресных входов модулей 22 - 2т устанавливается по мере считывания из модулей 2т - 2т-1, а так как считывание осуществляется с тактовой частотой, то результат считывания с последнего модуля появится через m тактов.

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

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

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

В предлагаемом техническом решении

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

Таким образом, количество модулей m совпадаете количеством избыточных разря0 дов числа общей разрядности n+m и объем памяти составит 1 модулей прототипа, где (п+1) - количество информационных разрядов модуля предлагаемого технического решения.

5 Объем памяти предлагаемого технического решения должен удовлетворять требованию 2m(n+1) 2m или Iog22m(n+l)m. Это является условием, при выполнении которого достигается цель изобретения,

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

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

5 счетчик адреса и регистр числа, информационные входы которого являются информационными входами устройства, выходы регистра числа являются информационными быходами устройства, младшие разряды

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

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

0

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

Фиг. 2