Устройство для поиска информации в ассоциативной памяти

 

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

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

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

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

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

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

lj 14 2

Фиг /

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

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

ПРИ ГКНТ,СССР (21) 4621854/24-24 (22) 19, 12, 88 (46) 30.12.90. Вюл . М- 48 (7 1) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) l0,В.Яблунонский, В.П.Сидоренко, А.П.Марковский и В.И.Корнейчук (53) 681.327 (088.8) (56) Патент США W 4622653, кл . 0 11 С 15/00, опублик. 1986.

Электронная промышленность, 1986, вып. 4(152), с ° 82. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ

В АССОЦИАТИВНОЙ ПАМЯТИ (57) Изобретение относится к вычислительной технике и может быть использовано для построения высокопроизводительных систем хранения и обработки информации, выполненных на узлах с большой степенью интеграции. Цель изобретения — повышение информационной емкости ассоциативной памяти, реализованной на одном кристалле за

„„SU„„1617460 А 1

2 счет исключения из устройства внешних выводов поиска при сохранении возможности горизонтального (по длине информационного слона) наращивания, Устройство содержит регистр 1 результатов поиска, элемент ИЛИ 2, приоритетный шифратор 3, дешифратор 4, коммутатор 5, блок 6 сравнения и блок 7 маскирования. При объединении отдельньг модулей ассицчатинной памяти, содержащих эти устройства, в ассоциа— тинный блок большой емкости обеспечивается определение полного совпадения информационного слова, хранящегося в отдельных модулях ассоциативной памяти, с признаком опроса. Устройство позволяет выделять адрес локального совпадения в каждом модуле ассоциативной памяти и осуществлять поиск оптимального (в лучшем случае максимального) адреса до тех пор, пока выделенные адреса но всех модулях не совпадут между собой. Данный адрес является адресом искомого слова. 8 ил.

3 табл.

9 6

161 7460

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

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

На фиг.1 изображена функциональ- . ная схема предлагаемого устройства; на фиг,2 — регистр результата поиска; на фиг.3 — функциональная схема триггера результата поиска; на фиг.4 блок сравнения; на фиг.5 — структурная схема блока маскирования; на фиг.6 — функциональная схема ячейки формирования сигналов сброса; на фиг.7 — функциональная схема формирования сигналов сброса; на фиг.8 — 0 один из вариантов построения модуля ассоциативной памяти, реализованного на одном кристалле, Устройство содержит регистр 1 результатов поиска, элемент ИЛИ 2 ° при- 25 оритетный шифратор 3, дешифратор 4, коммутатор 5, блок 6 сравнения н блок

7 маскирования.

Кроме того на фиг.1 также показаны информационные входы 8 блока 7, первая группа информационных выходов

9, выход 10 блока 7, выходы 11 сброса регистра 1, управляющий вход 12 блока 7, тактовый вход 13 устройства, вход 14 "Начало поиска" устройства> вход 15 разрешения записи регистра 1, 35 вход 16 разрешения записи устройства, установочный вход 17 устройства, вход

18 установки в "0" регистра 1, информационные входы 19 устройства, инфор—

40 мационные входы 20 регистра 1, шина

2 1, объединяющая выходы коммутатора

5, входы дешифратора 4 и вторую группу информационных входов 22 блока 6, вторая группа информационных входов

23 устройства, входы 24 установки начального состояния регистра 1, управляющий вход 25 и восход 26 блока сравнения, выход 27 "Наличие совпадений приэнаковой и хранимой информаlI ции устройства, выход 28 регистра 1, 50 первая группа информационных входов

29 и выходы 30 блока 6.

Pei истр 1 результата поиска содержит двухтактовые RCS-триггеры 31 результата поиска и группу элементов

И-НЕ 32. Причем сброс любого триггера

31 в нпчалъпое с остонние (логический нуль) происходит сигналом, устанснленным на входе 24 по заднему фронту синхроимпульса, сформированного на входе 18, Установка сигналов совпадений в каждый из триггеров 31 происходит по входам 20, при подаче единичного .сигнала на вход 15 "Начало поиска". Маскирование незначащих сигналов совпадений (сброс соответствующих триггеров 31 в начальное состояние) происходит по входам 11 регистра 1.

Каждый из RCS-триггеров 31, результата поиска содержит элементы

И-НЕ 33-40, вход 41 установки в "1", вход 42 установки в "О" синхровход

43, вход 44 сброса в "1", вход 45 сброса в "0" и прямой выход 46.

Блок 6 сравнения может быть реализован различными способами. Если выходной каскад коммутатора 5 выполнен с открытым коллектором, т.е. на выходах 21 объединенных модулей ассоциативной памяти реализуется функция монтажного И то блок 6 сравнения содержит (фиг.4) элементы НЕРАВНОЗНАЧНОСТЬ 47, элементы ИЛИ 48 и элемент

ИЛИ-НЕ 49. При этом приоритетный шифратор 3 выдает информацию (адрес совпадения) в инверсной форме, а дешифр;,тор 4 принимает информацию в инверсной форме.

Если выходной каскад коммутатора 5 выполнен с открытым эмиттером (реализуется функция логическое ИЛИ), то блок 6 содержит элементы РАВНОЗНАЧНОСТЬ 47, элементы И 48 и дополнительный элемент И 49 ° При этом приоритетный шифратор 3 выпает, а дешифратор 4 принимает информацию в прямой форме.

Для уменьшения влияния помех, свя- занных с наличием обратной связи в блоке 6 сравнения (выходы 30 — входы

22) во втором полутакте работы устройства, на выходе 30 МохНо использовать регистр (не показан), запись в который осуществляется по единичному сигналу, установленному на входе 25 блока 6 сравнения (при подаче нулевого сигнала на вход 25 блока 6 данный регистр находится в режиме хранения и считывания). Кроме того, перенос от старших разрядов к младшим в блоке

6 сравнения может быть реализован последовательно, параллельно (фиг.4) или параллельно по группам разрядов и последовательно между группами .

16174»0 6

Блок 7 маскирования содержит узел

50 формирования сигналов сброса, группу 51 элементов ИЛИ и элемент 52 задержки, Для выполнения узла 50 формирования сигналов сброса использован ячеечный принцип построения, т.е. узел 50 содержит (фиг .7) одинаковые ячейки 53 формирования сигналов сброса, входы 8 и выходы 54. При этом каждая ячейка 53 формирования сигналов сброса содержит (фиг.6) группу иэ четырех "элементов ИЛИ 55 со входом 56 предварительной установки.

На фиг.8 приведен пример реализации модуля 57 ассоциативной памяти, выполненного на одном кристалле.Модуль 57 ассоциативной памяти содержит устройство 58 для поиска информации с ассоциативной памяти, первый

59 и второй 60 элементы ИЛИ, демультиплексор 6 1, матрицу 62 ячеек памяти, дешифратор 63 команд, регистр 64 данных, регистр 65 маски, двунаправленную информационную шину 66 и входы

67 задания команд. При этом дешифратор 63 команд имеет следующие выходы: выход 68 выбора направления передачи данных; ныход 69 разрешения записи в регистр 64 данных; выход 70 разрешения записи в регистр 65 маски; выход 71 выборки матрицы 62 ячеек памяти; выход 72 разрешения мультизаписи; выход 73 разрешения процесса поиска; выход 74 разрешения чтения; выход 75 разрешения записи, В предлагаемом устройстве запись информации с информационной шины происходит последовательно в регистр 64 данных и регистр 65 маски.

Приоритетный шифратор 3 может быть выполнен по схеме одного из известных устройств для считывания информации иэ ассоциативной памяти.

Предлагаемое устройство предназначено для поиска совпадений в ассоциативной памяти большого объема, выполненного в виде большой или сверхбольшой интегральной схемы ВИС и СВИС с использованием известных технологий.

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

При том регистр 1 реализуется на микросхемах K155TM2 (К155ЛАЗ), прионитетный шифратор 3 —. на микросхемах

К155ИВ1 или К155ЛА8, дешифратор 4 на микросхемах К155ИЛЗ, коммутатор

5 — на микросхемах К55КП11 элемент

ИЛИ 2 — на микросхемах К155ЛЛ1, блок

6 сравнения — на микросхемах К55ЛЛ3, К155ЛЕ1 и К155ЛЛ1, блок 7 маскирования совпадений — на микросхемах

К155ЛЛ1 °

Устройство работает следующим образом.

Перед началом работы устройства нсе разряды регистра 1 установлены

1,> н начальное состояние — логический нуль, На входы 14, 16 и 17 устройства подаются сигналы нулевого уровня, а на нход 13 — сигнал единичного уровня. Таким образом, запись (как и

20 сброс и начальное состояние) в регистр 1 запрещена, блок 7 маскирования и коммутатор 5 заблокированы (на их выходах установлены единичные сигналы или нь>сокоомное состояние), 25 работа приоритетного шифратора 3 в режиме мультиэаписи запрещена . На выходах 27 и 26 устройства сфорг>ированы нулевые сигналы, Информация по шинам

21 устройств», видоизг1еняясь дешифрагором 4, поступаег на выходы 9 устройства. В таком режиме работы возможна адресная запись (считывание) информация в матрицу >>2 ячеек памяти> т,е. шины 21 устройства являются в

35 данном случае адресными входами модуля 57 ассоциативной памяти, Рассмотрим случай, ко> да выходной каскад коммутатора > ныполнеп с открьггым коллектором, т.е. модули 57

40 ассоциативной памяти объединяются шинами 21 посредством монтажи го И.

При этом приоритетный шифратор 3 выдает, а дешифратор 4 принимает информацию в инверсной форме. Информацион45 Hb>A код, и котором единицами отмечаются части слов (слова), совпадающие с соотнетствующей частью признака onроса (с признаком опроса), поступает на нходы 19 устройства .

50 Прн поступлении сигнала "Начало поиска" на вход 14 устройства (сигнал единичного уровня), разрешается запись информации в регистр 1 со входов

19 устройства и разблокируется комму55, татор 5 (на его выходы поступает ин формация с выходов приоритетного шифратора). Если н записанном в регистре

1 .коде есть хотя бы одна единица, то на выходе 27 устройства устанавлина1617460 ется единичный сигнал . Приоритетный шифратор 3 формирует на своих выходах инверсное значение адреса первой (от младших адресов к старшим) единицы, которое через коммутатор 5 поступает

5 на шину 21 устройства. Так как модули

57 ассоциативной памяти объединены шинами 21 посредством моятажного И, то на них устанавливается поразрядное 10 логическое произведение адресов, полученных совпадений, Данное значение кода и собственный адрес совпадения поступают на входы блока 6 сравнения в каждом .модуле 57 ассоциативной памяти. В блоке 6 происходит сравнение поступивших величин и при их совпадении на выход 26 устройства выдается сигнал единичного уровня. На выходах

30 блока 6 сравнения формируется код (старшие разряды которого являются совпавшими разрядами).поступивших адресов ло первого (начиная от старших разрядов) несовпадения, а остальные разряды кода, включая первый 25 несовпавший, заменяются на единичные сигналы. Полученный .таким образом код поступает на входы коммутатора 5, Так завершается первый полутакт работы устройства (на синхровходе 43 установлен единичный сигнал), затем на тактовый вход 13 устройства поступает нулевой сигнал (начинается второй полутакт работы устройства) и ининформация входов коммутатора 5 поступает на шины 21 устройства. Установившийся на объединенных шинах 21 код дешифрируется и поступает на входы 8 блока 7 маскирования. При этом на выходе элемента 52 задержки 10 выдается нулен.й сигнал, а на выходах

10 блока 7 маскирования совпадений формируется код, в котором нулями отмечены разряды, числовое значение адресов которых меньше адресов совпа- 45 дений. инверсное значение которого установлено на шинах 21 устройства, причем соответствующие разряды регистра 1 (на вход 11 которых поступает нулевой сигнал) устанавливаются в на чальное сбстояние (записывается логический нуль), т ° е. совпадения, адреса которых меньше по числовому значению адреса, установленного на шинах

21 устройства из дальнейшего процесса

55 поиска исключаются .

Следует отметить, что адрес, установленный на шинах 21 устройства поступает и на входы 22 блока 6 сравнения, .однако код на его выходах

30 не видоизменяет установившееся значение данного адреса, ввиду специфики самого процесса сравнения, что иллюстрируется панными табл.1.

В табл,1 приняты следукщие обозначения:

m - количество информационных слов;

О, если в старших разрядах сравниваемых кодов не было совпадений;

Т=

1, если в. старших разрядах сравниваемых кодов было совпадение.

Если на входе 29 установлен "0", то на .Не 22 ) не может быть "1" (шины 21 объединены посредством монтажного И),поэтому коды 010 и 110 в строках в табл. 1 отсутствуют.

Кроме того, если на выходах 30 блока 6 сравнения установлен регистр, то при подаче на тактовый вход 13 устройства нулевого сигнала (во втором полутакте) запись в данный ре-. гистр запрещается и информация с его выходов считывается на шины 21 устройства до окончания процесса маскирования.

После окончания маскироьания соответствукщих совпадений в регистре 1 приоритетный шифратор 3 каждого модуля 57 ассоциативной vàìÿòè вьщеляет очередной сигнал совпадения (инверсное значение его адреса). При этом ла тактовый вход 13 устройства поступает единичный сигнал и информация с выходов приоритетного шифратора 3 поступает на шины 21 устройства, т.е. начинается очередной такт его работы. !

В данном режиме устройство работает до тех пор, пока на объединенных выходах 26 всех модулей 57 ассоциативной памяти (содержимое одноименных строк которых составляет одно информационное слово) не установится единичный сигнал. Это означает, что на шинах 21 устройства выставлено инверсное значение адреса информационного слова, полностью совпадающего незамаскированными разрядами с признаком опроса, т.е. установленный на шинах

21 адрес совпадает с собственным адресом совпадения в каждом модуле 57 ассоциативной памяти. При этом происходит считывание (или запись) информация из соответствующей ячейки матрицы 62 памяти. Отрицательный фронт сигнала Запись" (" Чтение ) разрешает

9 161 сброс соответствунзцего разряда регистра 1 в "0" (сигнал подается на вход 17 устройства) и процесс поиска нового совпадения продолжается. Работа устройства прекращается после того, как на выходе 27 любого модуля

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

57 больше не зафиксировано совпадений.

Заметим, что если модуль 57 ассоциативной памяти, включающий предла гаемое устройство, используют самостоятельно, то в нем возможно проведение мультиэаписи информации. Для этого на вход 16 устройства подается единичный сигнал.

Рассмотрим работу устройства на примере.

Пусть четыре модуля 57 ассоциативной памяти объединены между собой шинами 21 и содержат по 16 информационных слов производной разрядности.

На входах 19 устройств 58 всех модулей 57 3; (i=1,4) установлены сигналы, показанные н табл.2, В каждом такте работы устройств 58 на их выходах формируются сигналы, показанные н табл.З.

Таким образом, на выходах 26 всех (объединенных между собой шинами 21) модулей 57 ассоциативной памяти на третьем такте работы сформируется единичный сигнал, который свидетельствует о том, что обнарукено полное совпадение всех незамаскированных частей девятого информационного слова с признаком опроса. Происходит считывание (запись) информации иэ девятой ячейки ,каждого модуля 57 ассоциативной памяти. Отрицательный фронт сигнала считывания (записи) разрешает сброс девятого разряда регистра 1 каждого модуля 57 в начальное состояние и процесс поиска продолжается, На шестом такте работы происходит считывание информации из четырнадцатой ячейки данных модулей 57 ассоциативной памяти. После этого на выходе 27 третьего модуля 57, а следовательно, и на объединенном (посредством монтажного И) выходе 27 всех модулей 57 устанавливается нулевой сигнал, свидетельствукщий об окончании процесса поиска.

Формула

55 изобретения

Устройс ао для поиска информации в ассоциа вной памяти, содержащее регистр результатов поиска, элемент

ИЛИ, приоритетный шифратор и дешифратор, входы которого янляются адресными входами устройства, выходы регистра результата поиска подключены к входам элемента И;01, выход которого является выходом "Совпадение" приэнаковой и хранимой информации устройства, выходы первой группы приоритетного шифратора подключены к соответствующим входам установки в начальное состояние регистра результатов поиска и являются информационными выходами перной группы устройства, информационные входы приоритетного шифратора подключены к выходам регистра результата поиска, информационные входы которого являются информационными входами устройства, вход установки н "0 регистра реэультатон поиска и управлякиций нход приоритетного шифратора является соответственно установочным входом и входом разрешения записи устройства, о т л и ч а ю щ е— е с я тем, что, с целью повышения информационной емкости устройства, н него нведены блок сравнения, коммутатор, блок маскирования, причем выходы блока маскирования подключены к соответствующим входам сброса регистра реэультатон поиска, выходы дешифратора соединены с информационными входами блока маскирования и являются информационными выходами второй группы устройства, управляющие входы блока маскирования и блока сравнения и первый управляющий вход коммутатора объединены и являются тактовым входом устройства, вход разрешения записи регистра результата поиска и второй управлякмций вход коммутатора объединены и являются входом "Начало поиска" устройства, информационные входы первый групп блока сравнения и коммутатора поразрядно объединены и подключены к соответствующим выходам приоритетного шифратора, группа выходов блока сравнения соединена с информационными входами второй группы коммутатора, выходы которого являются информационными выходами третьей группы устройства, информационные входы второй группы блока сравнения и входы дешифратора поразрядно объединены и

11 617460 12 подключены к соответствунщим выходам является выходом "Положительный ре-коммутатора, выход. блока сравнения зультат поиска" устройства. выходе блока 6 срав нения

Т 22 29

Та блица 2

t (М, М, М, М

М,, М, М,, М

„М„М>, М

13 О 1

14 1 1 1 1

15 О О О 1

1 О О

9 1 1 1 !

0 О О О

О О О

О О

О О

О О 1

О О 1

О 1 О

О 1 1

О 1

О 0 1 О !

2. О О 1 О

Таблица 3

Сигналы

Номер такта

Ч I

1 1 1

1 1 1

О 1 1

О О 1

1 1 О О 1 1 О О

О 1

1 1

1 О

1 0

0100011.1

О 1 1 1 О 1 1 1

О О О О О 1 1

1 Mi

1. 1

2 О

Э, 0

4 1

Таблица1 игналы, установленные на j-ou (где j = 1, 1оя m) входе

T 1

1 О 0

2 О О

3 О 1

4 1 О

5 1 О

6 1 1

На выходах приоритетного шифратора 3 На шинах 21 устройств 58, объединенных между собой

"a

3 М4 1 полутакт 2 полутакт

l,1617460

Сигналы выходах нркорнтетного акфратора 3 м м

1Ь

Фиг.2

Нона тахт

74

14

ПРодоллгение табл.3

На иннах 21 устройств 58, объединенных мазду собой

1 нолутакт 2 полутакт

0 0 1 0 0 0 1 0

0 0 1 0 0 0 1 0

1617460

) 6! 74бО

21

gJ пй

Фиг. д

Составитель В.Рудаков

Редактор А.Ревин Текред Л.Олийнык Корректор С.Черни

Заказ 4120 Тирам 486 Пог лис нсз

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 10!