Устройство для адресации по содержанию блока памяти

 

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

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

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

РЕСПУБЛИК (19) (11), 13 е

Т!

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

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

» !

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4046392/24-24 (22) 03„03.86 (46) 07.07,87, Бюл. У 25 (71) Калужское отделение Всесоюзного научно-исследовательского института экономики минерального сырья и геолого-разведочных работ (72) Б.А.Кулик, Э.В.Рахов, В.М.Питерский и Б.Н.Лысков (53) 681.325(088.8) (56) Крайзмер Л.П. и др, Ассоциативные запоминанхцие устройства.

Л.: Энергия, 1967, с. 33.

Кохонен Т. Ассоциативные запоминающие устройства, — М.: Мир, 1982, с. 13-16, 168-170, рис, 1. 1 и 3.9. (54) УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПО СОДЕРЖАНИЮ БЛОКА ПАМЯТИ (51) 4 G 06 F 12/00 G 11 С 15/00 (57) Изобретение относится к вычислительной технике, может быть использовано в автоматизированных системах обработки информации с помощью ЭВМ.

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

1322292

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

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

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

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

15

55

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

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

10< — 10„, элементы И 11, — 11„, 12,—

12„, элемент И 13, элемент ИЛИ 14, элементы 15, — 15„ и 16 задержки, 40 элемент НЕ 17. Регистр 1О; логического вектора имеет вход 1 занесения

"1" в крайний левый разряд, вход 2 сдвига вправо на один разряд, вход 3 начальной установки в "0" и выход па- 45 раллельной выдачи информации. Анализатор 3 совпадения (фиг.4) содержит элемент И 18, элемент ИЛИ 19, элемент

20 задержки, элемент НЕ 21 и узел 22 логического умножения с накапливанием результата. Узел 22 логического умножения с накапливанием результата содержит регистр-аккуиулятор разрядности, равный длине логического вектора, имеет вход 1 установки регистра-аккумулятора в "1", вход 2 сдвига регистра-аккумулятора на один разряд вправо и поразрядную схему логического умножения входного кода с кодом

Т а блица1

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

Слово-ключ

Дом

Рада регистра-аккумулятора. Узел 22 имеет вход параллельного занесения инфориации (вход 3) и выход параллельной выдачи информации, вход 4 установки регистра-акуумулятора в "0". Вход параллельного занесения информации узла 22 соединен с информационныи входом анализатора 3 совпадения.

Установка в "1" узла 22 осуществляется фронтом "0"-"1" сигнала на входе

1. Разрешение прохождения сигнала на выход осуществляется сигналом с выхода элемента И 18. Вход сдвига на один разряд узла 22 соединен с входом разрешения сдвига блока.

Элемент 16 задержки в блоке 2 выбирается таким образом, чтобы от момента выработки сигнала совпадения до начала сдвига в регистре 10 за1 вершились переходные процессы занесения "1", а элементы 15, — 15„ задержки блока 2 выбираются на время, большее уКазанного на величину, достаточную для завершения процесса сдвига

<в регистре 10; . Элемент 20 задержки в анализаторе 3 совпадения выбирается такии образом, чтобы с момента установки сигнала режима в состояние

"Выдача" прошло время, достаточное для съема результата с выхода 5, длительность сигнала режима в состоянии

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

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

1322292!!рополжение табл.1

Слово-ключ

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

Род

Драма

Мор

10

Дар

Мода и ц Рада Н Род Н Драиа Н Иор Н Дар U Иода U

34 567 891011 12 13 14 1516 17 18 1920 21 22 23 24 252627 28 29 30 31 32 33

Н 1

1 1 1 1 1 1

Д 1

0 1

1 1

1 1

Чтобы найти информационную единицу, ассоциативНым словом-ключом которой является, например, "Драма, необходимо логический вектор первой буквы слова-ключа, сдвинув вправо на

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

19 позиция). Однозначность этого указания позволяет полученный вектор превратить в удобное двоичное число или применить непосредственно для реализации известными механизмами вы- 45 борки при обращении к блоку памяти.

Если полученный вектор пуст, заданное слово-ключ в списке ключей отсутствует, если в полученном векторе содержится более, чем одна "1", столько же слов-ключей содержится в списке (вектор укажет позиции их всех) .

Не описывая известные процедуры занесения информации в блок памяти, рассматривают работу устройства в режиме "Запись" (режим подготовки логических векторов). От внешнего источника подается импульсный сигнал начальной установки на входы 7, и 7, Для простоты в примере N=7, п=Ь (Ll, Д,O,M,P,А). Для образования лсгических векторов строится матрица, вдоль горизонтальной стороны которой записываются по порядку слова-ключи, вдоль вергикальной стороны — ансамбпь символов и в пересечениях строки i-ro символа со столбцом, над которым име1! l! ется аналогичный символ ставится 1

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

Таблица2 приводящий регистры 10, — 10 „и узел

22 в начальное (нулевое) состояние; на вход 6 "0"; на вход 4 подаются последовательно параллельные коды символов слов-ключей всех информационных единиц, размещение которых в блоке памяти осуществляется в последовательности, соответствующей последовательности подаваемых на вход 4 слов-ключей. Константы кодов всего ансамбля п символов содержатся в регистрах 9, — 9„. Поступивший код i ãî символа в блоке 1 вызывает срабатывание i-й схемы 8 сравнения и на соответствующей линии выхода первого блока 1 появляется импульс, который поступает в блок 2 на первый вход элемента И 11; (на втором входе всех элементов И 11,, связанных с выходом элемента HF. 17, имеется разрешающая

"1", полученная в результате инвертирования элементов НЕ 17 сигнала "О", пришедшего на второй вход блока 2 по входу 6) и далее на вход 1 занесения

"1" в левый разряд регистра 10 блока

2. Одновременно импульс с выхода схемы 8; сравнения через элемент ИЛИ 14 блока 2, пройдя через элемент 16 задержки и через два последовательно соединенных элемента И 13 и 12,, явится сигналом сдвига i-го регистра

10, так как соответствующий разрешающий сигнал выдает элемент 15, задер1322292 жки .подключений между i линией и первым входом элемента И 12, а элемент И 13 находится в разрешенном состоянии по второму входу выходным сигналом от элемента НЕ 17, Так как на входе 6 "0", содержимое из регистра 10 на вход 3 узла

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

Режим "Поиск". Импульсным сигналом по линии 7 узел 22 приводится в иск

ll ходное состояние. Сигнал режима Поиск" "1" по входу 6 поступает íà sxop режима блока 2. В анализаторе 3 совпадения он разрешает прохождение информации к входу 3 узла 22,запрещает (по входу 1) прохождение сигнала через элемент И 18 и через элемент 20 задержки осуществляет исходную установку регистра-аккумулятора узла 22 в "1". В блоке 2 он, пройдя через элемент НЕ 17, запрещает занесение

"1" через элементы И 11, - 11„ и через элементы И 12< - 12 „ и 13 сдвига в регистрах 10, — 10 „ на все время режима "Поиск". После подачи сигнала на вход 6 (с задержкой не менее времени установленного элемент 20) на вход 4 подается параллельный код первого символа слова-ключа, который при одновременном сопоставлении с кодами всех регистров констант 9, - 9„ дает на выходе соответствующей схемы сравнения разрешающий импульс, который открывает шину параллельного выхода i-го регистра 10 и логический вектор первого символа поступает по входу 3 в узел 22, где осуществляется его логическое умножение на начальную константу "1". Одновременно разрешающий импульс проходит элемент ИЛИ 14 и после прохождения элемента 16 задержки поступает на вход 2 узла 22, осуществляя сдвиг вправо на 1 разряд полученного результата в регистре-аккумуляторе узла 22.

После повторения аналогичной процедуры над всеми символами слова-ключа сигнал режима на входе 6 переводится в состояние "О". Сигнал внешнего управления, пройдя через элемент

21, разрешит прохождение сигнала через элемент И 18 с выхода элемента

ИЛИ 19, который подсоединен к выходам узла 22 и, если результирующий вектор не пуст, соответствующая единица, пройдя элементы ИЛИ 19 и И 18, послужит разрешением выдачи кода из узла

22 в блок памяти по выходу 5 (снятие сигнала внешнего управления соответствует переводу устройства в режим

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

1322292

Фие.5

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

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

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

Подписное

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

"ожидание

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

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

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

/ИИ 3виУаиаг"