Устройство для поиска информации в ассоциативной памяти Советский патент 1990 года по МПК G11C15/00 

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

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

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

Устройство содержит регистр 1 результатов поиска, элемент ИЛИ 2, приоритетный шифратор 3, дешифратор 4, коммутатор 5, блок 6 сравнения и блок 7 маскирования.

Кроме Toi o на фиг.1 также показаны информационные входы 8 блока 7, первая группа информационных выходов 9, выход 10 блока 7, выходы 11 сброса регистра 1, управляющий вход 12 блока 7, тактовый вход 13 устройства, вход 14 Начало поиска устройства, вход 15 разрешения записи регистра 1, вход 16 разрешения записи устройства, установочный вход 17 устройства, вход 18 установки в О регистра 1, информационные входы 19 устройства, информационные входы 20 регистра 1, шина 21, объединяющая выходы коммутатора 5, входы дешифратора 4 и вторую группу информационных входов 22 блока 6, вторая группа информационных входов 23 устройства, входы 24 установки начального состояния регистра 1, уп- равляю1 (ий вход 25 и выход 26 блока сравнения, выход 27 Наличие совпадений признаковой и хранимой информа- ции устрбйства, выход 28 регистра 1, первая группа информационных входов 29 и выходы 30 блока 6.

Ре) истр 1 результата поиска содержит двухтактовые RCS-триггеры 31 результата поиска и группу элементов И-HF 32. Причем сброс любого триггера 31 в начальное состояние (логический нуль) происходит сигналом, установ

5

0

5

0

5

0

5

0

5

ленным на входе 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 вьщает информацию (адрес совпадения) в инверсной форме, а дещиф- pfiTop 4 принимает информацию в инверсной форме.

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

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

51

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

На фиг.8 приведен пример реализации модуля 57 ассоциативной памяти, выполненного на одном кристалле. ; Модуль 57 ассоциативной памяти содержит устройство 58 для поиска информации с ассоциативной памяти, первый 59 и второй 60 элементы ИЛИ, демуль- типлексор 61, матрицу 62 ячеек памяти, дешифратор 63 команд, регистр 64 данных, регистр 65 маски, двунаправленную информационную шину 66 и входы 67 задания команд. При этом дешифратор 63 команд имеет следующие выходы

выход 68 выбора направления передачи данных;

выход 69 разрешения записи D регистр 64 данных;

выход 70 разрешения записи в регистр 65 маски;

выход 71 выборки матрицы 62 ячеек памяти;

выход 72 разрешения мультизаписи;

вькод 73 разрешения процесса поиска;

выход 74 разрешения чтения;

выход 75 разрешения записи.

В предлагаемом устройстве запись информации с информационной шины происходит последовательно в регистр 64 данных и регистр 65 маски.

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

Предлагаемое устройство предназначено для поиска совпадений в ассоциативной памяти большого объема, выполненного в виде большой или сверхбольшой интегральной схемы ВИС и СБИС с использованием известных технологий Устройство может быть реализовано на базе серийно выпускаемых микросхемах малой и средней степени интеграции. При том регистр 1 реализуется на микросхемах К 155ТМ2 (К155ЛАЗ), приори74f 0 6

тетный шифратор 3 -. на тжросхемах К153ИВ1 или К155ЛА8, дешифратор 4 - на микросхемах К155ИЛЗ, коммутатор

5- на микросхемах К55КП11, элемент ИЛИ 2 - на микросхемах К155ЛЛ1, блок

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

,д К155Ш11.

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

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

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

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

5 работа приоритетного шифратора 3 в режиме мультиэаписи запрещена. 1а выходах 27 и 26 устройства сформированы нулевые сигналы. Информация по шинам 21 устройства, видоизменяясь дешиф0 рагором 4, поступает на выходы 9 устройства. В таком режиме работы возможна адресная запись (считывание) информация в матрицу 62 ячеек памяти, т.е. шины 21 устройства ивляются в

данном случае адресными вxoдa n модуля 57 ассо1щативной плмлти.

Рассмотрим случай, KOI да выходной каскад коммутатора ) выполнен с открытым коллектором, т.е. MoAyjui 57

0 ассоциативной памяти объединяются ши- нами 21 посредстпом монтажг пго И. При этом приоритетный шифратор 3 выдает, а дешифратор 4 принимает информацию в инверсной форме. Информацион .ный код, в котором единицами отмечаются части слов (слова), совпадающие с соответствуюи1ей частью признака опроса (с признаком опроса), поступает на входы 19 устройства.

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

5,

ется единичный сигнал. Приоритетный шифратор 3 формирует на своих выходах инверсное значение адреса первой (от младших адресов к старшим) единицы, которое через коммутатор 5 поступает на шину 21 устройства. Так как модули 57 ассоциативной памяти объединены шинами 21 посредством монтажного И, то на них устанавливается поразряднре логическое произведение адресов, полученных совпадений. Данное значение кода и собственный адрес совпадения поступают на входы блока 6 сравнения в к&ждом .модуле 57 ассоциативной па- мяти. В блоке 6 происходит сравнение поступивших величин и при их совпадении на выход 26 устройства вьщается сигнал единичного уровня. На выходах 30 блока 6 сравнения форм фуется код (старшие разряды которого являются совпавшими разрядами).поступивших адресов до первого (начиная от старших разрядов) несовпадения, а остальные разряды кода, включая первый несовпавший, заменяются на единичные сигналы. Полученный таким образом код поступает на входы коммутатора 5 Так завершается первый полутакт работы устройства (на синхровходе 43 установлен единичный сигнал), затем на тактовый вход 13 устройства поступает нулевой сигнал (начинается второй полутакт работы устройства) и ин информация входов коммутатора 5 поступает на шины 21 устройства. Установившийся на объединенных шинах 21 код дешифрируется и поступает на входы 8 блока 7 маскирования, Пра зтом на выходе элемента 52 задержки выдается нулевой сигнал, а на выхода 10 блока 7 маскирования совпадений формируется код, в котором нулями отмечены разряды, числовое значение адресоп которых меньше адресов совпа дений. инверсное значение которого установлено на шинах 21 устройства, причем соответствующие разряды регистра 1 (на вход 11 которых поступает нулевой сигнал) устанавливаются в на чальное сбстояние (записьшается логический нуль), т,е. совпадения, адреса KOTopi ix меньше по числовому значению адреса, установленного на шина 21 устройства из дальнейшего процесс поиска исключаЕотся,

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

5

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

В табл.1 приняты следукщие обозначения:m - количество информационных слов;

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

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

Если на входе 29j установлен О, то на шине 221 не может быть 1 (шины 21 объединены посредством монf

тажного И) , поэтому коды 010 и 110 в строках в табл. 1 отсутствуют.

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

После окончания маскирования соот- ветствугадих совпадений в регистре 1 приоритетный пшфратор 3 каждого модуля 57 ассоциативной памяти выделяет очередной сигнал совпадения (инверсное значение его адреса). При зтом ;ia тактовый вход 13 устройства поступает единичный сигнал и информация с выходов приоритетного шифратора 3 поступает на шины 21 устройства, т.е. начинается очередной такт его работы.

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

16

сброс соответствунщего разряда регистра 1 в О (сигнал подается на вход 17 устройства) и процесс поиска нового совпадения продолжается. Работа устройства прекращается поСле того, как на выходе 27 любого модуля 57 ассоциативной памяти сформулируется нулевой сигнал, означающий, что в регистре 1 хотя бы одного модуля 57 больше не зафиксировано совпадений.

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

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

Пусть четыре модуля 57 ассоциативной памяти объединены между собой шинами 21 и содержат по 16 информв - онных слов производной разрядности. На входах 19 ух:тройств 58 всех модуей 57) (,4) установлены сигналы, показанные в табл.2.

В каждом такте работы устройств 58 на их выходах формируются сигналы, показанные в табл.3.

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

1746010

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

0

5

0

5

0

5

0

5

0

5

Устройс г ао для поиска информа1Л1и в ассоциа 1вной памяти, содержащее регистр результатов поиска, элемент ИЛИ, приоритетHbui шифратор и дешифратор, входы которого являются адресными входами устройства, выходы регистра результата поиска подключены к входам злемента tUIH, выход которого является выходом Совпадение признаковой и хранимой информации устройства, выходы первой группы приоритетного шифратора подключены к соответствующим входам установки п начальное состояние регистра результатов поиска и являются информационным выходами первой группы устройства, информационные входы приоритетного шифратора подключены к выходам регистра результата поиска, информационные входы которого являются информационными входами устройства, вход установки в О регистра результатов поиска и управлямций вход приоритетного шифратора является соответственно установочным входом и входом разрешения записи устройства, отличающееся тем, что, с целью повышения информационной емкости устройства, в него введены блок сравнения, коммутатор, блок маскирования, причем выходы блока маскирования подключены к соответствующим входам сброса стра результатов поиска, выходы дешифратора соединены с информационными входами блока маскирования и являются информационными выходами второй группы устройства, управляющие входы блока маскирования и блока сравнения и первый управляющий вход коммутатора объединены и являются тактовым входом устройства, вход разрешения записи регистра результата поиска и второй управляк1дий вход коммутатора объединены и являются входом Начало поиска устройства, информационные входы первый групп блока сравнения и коммутатора поразрядно объединены и подключены к соответствующим выходам приоритетного шифратора, группа выходов блока сравнения соединена с информационными входами второй группы коммутатора, выходы которого являются информационными выходами третьей группы устройства, информационные входы второй группы блока сравнения и входы дешифратора поразрядно объединены и

П161746012

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

коммутатора, выход блока сравнения

является выходом Положител

зультат поиска устройства, Таблица 1

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

Номер такта

Сигналы

На выходах приоритетного шифратора 3

1 l.l.I.-,

1 1 О

о

1 1

о о

о 1 1 1

о о 1 1

1 1

о 1 1 1

о

1 о

1

Таблица 2

ТаблицаЗ

Сигналы

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

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

0111 0111

0000 0011

13

Номер такта

На выходах приоритетного шифратора 3

1 м, f м, Т м

О О .1 1

О

о 1 1

Що

1617460

14

Продолжение табл.3

Сигналы

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

П

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

о о 1 о

0010 0010

28,

ог,

.

Фиг.З

25

Фиг.

L.

LJ

Фиг. 5

X

.0

В

53

5J

В

Л7

I

k..

Ф:/2.7

5

о

./

о

4

Э

J4

54