Устройство для адресации по содержанию блока памяти Советский патент 1987 года по МПК G06F12/00 G11C15/00 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки информации с помощью ЭВМ.

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

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

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

10

15

20

регистра-аккумулятора. Узел 22 имеет вход параллельного занесения информации (вход 3) и выход параллельной выдачи информации, вход 4 установки регистра-акуумулятора в О. Вход параллельного занесения информации узла 22 соединен с информационным входом анализатора 3 совпадения. Установка в 1 узла 22 осуществляется фронтом сигнала на входе 1. Разрешение прохождения сигнала на выход осуществляется сигналом с выхода элемента И 18„ Вход сдвига на один разряд узла 22 соединен с входом разрешения сдвига блока.

Элемент 16 задержки в блоке 2 выбирается таким образом, чтобы от момента вьфаботки сигнала совпадения до начала сдвига в регистре 10; завершились переходные процессы занесе- 1, а элементы 15, - 15

Блок 1 ассоциативных признаков (фиг.2) содержит схемы 8, - 8 и регистры 9, - 9ц констант по количеству ансамбля букв кодов ассоциативного признака п. Первый вход схемы 8; сравнения соединен с i линией входа, второй вход соединен с выходом регистра 9;, ,...,п.

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

25

10, - 12

10„, элементы И 11, - 11h 2, - , элемент И 13, элемент ИЛИ 14, элементы 15, - 15„ и 16 задержки, элемент НЕ 17. Регистр 10, логического вектора имеет вход 1 занесения 1 в крайний левый разряд, вход 2 сдвига вправо на один разряд, вход 3 начальной установки в О и выход параллельной выдачи информации. Анализатор 3 совпадения (фиг.4) содержит элемент И 18, элемент ИЛИ 19, элемент 20 задержки, элемент НЕ 21 и узел 22 логического умножения с накапливанием результата. Узел 22 логического укшожения с накапливанием результата содержит регистр-аккумулятор разрядности, равный длине логического вектора, имеет вход 1 установки регистра-аккумулятора в 1, вход 2 сдвига регистра-аккумулятора на один разряд вправо и поразрядную схему логического умножения входного кода с кодом

ния I , а элементы 15, - 15 задержки блока 2 выбираются на время, большее указанного на величину, достаточную для завершения процесса сдвига в регистре 10;. Элемент 20 задержки в анализаторе 3 совпадения выбирается таким образом, чтобы с момента установки сигнала режима в состояние Схемой 8t сравне- ,„ Выдача прошло время, достаточное

- для съема результата с выхода 5, длительность сигнала режима в состоянии Поиск должна быть больше полного времени подачи на вход 4 всего ассоциативного признака. Устройство обес35 печивает работу в режиме Ожидание, Запись, Поиск и Выдача. Переключение устройства в тот или иной режим осуществляется подачей внешнего сигнала на вход 6 регистра. Характер сигнала приведен на фиг.З.

Пример. Поиск информации в блоке памяти по ключевому слову. Блок памяти содержит N единиц информации, которым в качестве ассоциативных признаков приписаны слова-ключи, составленные из ансамбля в п символов. Например , первой информационной единице приписано слово-ключ Дом, второй - Рада и т.д. (табл.1).

40

45

50

Т а б л и ц а 1

55

Дом

Рада

5

0

регистра-аккумулятора. Узел 22 имеет вход параллельного занесения информации (вход 3) и выход параллельной выдачи информации, вход 4 установки регистра-акуумулятора в О. Вход параллельного занесения информации узла 22 соединен с информационным входом анализатора 3 совпадения. Установка в 1 узла 22 осуществляется фронтом сигнала на входе 1. Разрешение прохождения сигнала на выход осуществляется сигналом с выхода элемента И 18„ Вход сдвига на один разряд узла 22 соединен с входом разрешения сдвига блока.

Элемент 16 задержки в блоке 2 выбирается таким образом, чтобы от момента вьфаботки сигнала совпадения до начала сдвига в регистре 10; завершились переходные процессы занесе- 1, а элементы 15, - 15

ния I , а элементы 15, - 15 задержки блока 2 выбираются на время, большее указанного на величину, достаточную для завершения процесса сдвига в регистре 10;. Элемент 20 задержки в анализаторе 3 совпадения выбирается таким образом, чтобы с момента установки сигнала режима в состояние „ Выдача прошло время, достаточное

Т а б л и ц а 1

Дом

Рада

Информационная единица

Ирстдолжение табл.1 Слово-ключ

Род

Драма Мор

Дар Мода

о м

1

1

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

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

3222924

Для простоты в примере N 7, , Д,0,М,Р,А). Для образования логических векторов строится матрица, вдоль горизонтальной стороны которой записываются по порядку слова-ключи, вдоль вертикальной стороны - ансамбль символов и в пересечениях строки i-ro символа со столбцом, над которым имеется аналогичньй символ ставится 1.

10

Логическим вектором символа i является строка символа i из табл.2.

Таблица2

итоенагика. вы ыкаоре. ное ву- р, ис7,

30

35

40

45

50

55

1 J 1

приводящий регистры 10 - 10„ и узел 22 в начальное (нулевое) состояние; на вход 6 на вход 4 подаются последовательно параллельные коды символов слов-ключей всех информационных единиц, размещение которых в блоке памяти осуществляется в последовательности, соответствующей последовательности подаваемых на вход 4 слов-ключей. Константы кодов всего ансамбля п символов содержатся в регистрах 9( - 9„. Поступивший код i-ro символа в блоке 1 вызывает срабатывание i-й схемы 8 сравнения и на соответствующей линии выхода первого блока 1 появляется импульс, который поступает в блок 2 на первый вход элемента И 11; (на втором входе всех элементов И 11; , связанных с выходом элемента НЕ 17, имеется разрешающая 1, полученная в результате инвертирования элементов НЕ 17 сигнала О, пришедшего на второй вход блока 2 по входу 6) и далее на вход 1 занесения 1 в левый разряд регистра 10 блока 2. Одновременно импульс с выхода схемы 8j сравнения через элемент ИЛИ 14 блока 2, пройдя через элемент 16 задержки и через два последовательно соединенных элемента И 13 и 12; , явится сигналом сдвига i-ro регистра 10, так как соответствующий разрешающий сигнал выдает элемент 15j задержки подключений между i линией и первым входом элемента И 12, а элемент И 13 находится в разрешенном состоянии по второму входу выходным сигналом от элемента НЕ 17,

Так как на входе 6 О, содержимое из 1 регистра 10 на вход 3 узла 22 анализатора 3 совпадений не поступает, а так как занесение 1 в ре- гистр-аккумулятор узла 22 осуществляется при подаче высокого уровня сигнала по входу 6 режима, на выходе 5 сохраняется нулевой сигнал.

Режим Поиск. Импульсным сигналом 15 ствует переводу устройства в режим

Выдача), Прекращение режима Выдача возможно подачей сигнала по линии

по линии 7 узел 22 приводится в исходное состояние. Сигнал режима Поиск 1 по входу 6 поступает на вход

режима блока 2. В анализаторе 3 сов- подача сигнала начальной установки падения он разрешает прохождение ин- 20 по линии 7 позволяет подготовить формации к входу 3 узла 22,запрещает (по входу 1) прохождение сигнала через элемент И 18 и через элемент 20 задержки осуществляет исходную устаустройство к перенаименованию всего массива информационных единиц. Формула изобретения

Устройство для адресации по содер- новку регистра-аккумулятора узла 22 25 жанию блока памяти, содержащее блок

в 1. В блоке 2 он, пройдя через элемент НЕ 17, запрещает занесение 1 через элементы И 11, - 11„ и через элементы И 12, - 12„ и 13 сдвига в регистрах 10, - 10 на все время режима Поиск, После подачи сигнала на вход 6 (с задержкой не менее времени установленного элемент 20) на вход 4 подается параллельный код пердает на выходе соответствующей схемы сравнения разрешающий импульс, котового символа слова-ключа, который 35 выборки логического вектора, блока об- при одновременном сопоставлении с ко- работки логических векторов, первый дами всех регистров констант 9, - 9, выход которого соединен с информационным входом анализатора совпадения, второй выход блока обработки логичес- рый открывает шину параллельного вы- 40 ких векторов соединен с входом разре- хода i-ro регистра 10 и логический шения сдвига анализатора совпадения, вектор первого символа поступает по входы задания режима работы блока входу 3 в узел 22, где осуществляется обработки логических векторов и ана- его логическое умножение на начальную лизатор совпадения являются входами константу 1. Одновременно разрешаю- 45 задания режима работы устройства, щий импульс проходит элемент ИЛИ 14 входы начальной установки блока обра- и после прохождения элемента 16 за- ботки логических векторов и анализа- держки поступает на вход 2 узла 22, тора совпадения являются входами на- осуществляя сдвиг вправо на 1 разряд чальной установки устройства, выход полученного результата в регистре-ак- 50 анализатора совпаделия является выхо- кумуляторе узла 22,дом устройства„

После повторения аналогичной процедуры над всеми символами слова-ключа сигнал режима на входе 6 переводится в состояние О. Сигнал внешнего управления, пройдя через элемент 21, разрешит прохождение сигнала через элемент И 18 с выхода элемента ИЛИ 19, который подсоединен к выходам узла 22 и, если результирующий вектор не пуст, соответствующая единица, пройдя элементы ИЛИ 19 и И 18, послужит разрешением выдачи кода из узла 22 в блок памяти по выходу 5 (снятие сигнала внешнего управления соответначальной установки 7.. Отдельная

подача сигнала начальной установки по линии 7 позволяет подготовить

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

Фиг. г

Изобретение относится к вычислк- тельной технике, может быть использовано в автоматизированных системах обработки информации с помощью ЭВМ. Целью изобретения является повышение быстродействия устройства. Устройство содержит блок 1 ассоциативных признаков, блок 2 логических векторов, анализатор-индикатор 2 совпадений, вход 4 аргумента поиска, вход 6 режима работы. В режиме Запись просматривается информация в блоке памяти и в блоке 2 создаются логические векторы символов. В режиме Поиск ведется поиск информации по ключевому слову, поступающему по входу 4, rf если такое слово существует, то на вьгходе 5 устройства появляется информация о местонахождении этого слова в блоке памяти. 2 тгйл., 5 ил. (Л

я

и

Редактор Н.Рогулич

Заказ 2866/46Тираж 672

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. А/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

0)нидание

Фиг.5

Составитель В.Бородин

Техред И.Попович Корректор А.Тяско

Подписное