Устройство для считывания информации из ассоциативной памяти большого объема Советский патент 1991 года по МПК G11C15/00 

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

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

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

Устройство для считывания информации из ассоциативной памяти большого объема (фиг. 1) содержит группу из 1одкт регистров 1 дескрипторов (т - количество информационных входов (выходов) ассоциативной запоминающей матрицы) устройства; К - количество вторых информационных

ы

(поисковых) выходов устройства), группу из 1одкт блоков 2 приоритета, группу из 1одкт элементов ИЛИ 3 и (1одкт - 1) групп блоков 4 логической свертки по К (,2

(logxm - 1) блоков 4 в каждой группе, причем второй управляющий вход 5 устройства подключен к третьему управляющему входу 6 последнего (одкт - 20)-го регистра 1 дескрипторов, третий управляющий вход 7 устройства соединен с дополнительным управляющим входом последнего блока 2 приоритета, а вторые информационные входы 8 - с К2 входами каждого из т/К2 блоков 4 логической свертки, причем второй управляющий вход 9 последнего блока 2 приоритета подключен к третьему управляющему входу б предыдущего (1одкт-1)-20)-го регистра 1 дескрипторов, к выходу соответствующего по группе элемента ИЛИ 3 и является вторым управляющим выходом 10 устройства, (1одкт)-е выходы первой группы 11 информационных выходов которого связаны с выходами последнего блока 2 приоритета, причем информационные входы 12 всех регистров 1 дескрипторов подключены к выходам 13 первого блока 4 логической свертки и являются вторыми информационными выходами 14 устройства, управляющие поразрядные входы 15 соединены с управляющими выходами соответствующих блоков 2 приоритета, а информационные выходы 16- с входами соответствующих блоков 2 приоритета и с входами, кроме первых,элемен- тов ИЛ И 3, первый вход каждого из которых связан с управляющим выходом соответствующего регистра 1 дескрипторов, а выход каждого из которых, кроме последнего, связан с первым управляющим входом 17 последующего по группе регистра 1 дескрипторов, с вторым управляющим входом 9 соответствующего регистра 1 дескрипторов,с третьим управляющим входом 6 предыдущего по группе регистра 1 дескрипторов (выход первого элемента ИЛИ 3 является первымуправляющим выходом 18устройст- ва, первый управляющий вход 19 которого соединен с вторым управляющим входом 9 первого регистра 1 дескрипторов) и с первым управляющим входом 20 блоков 4 логической свертки соответствующей группы, вторые управляющие входы 21 которых подключены к выходам соответствующих блоков 2 приоритета и являются с первого по (одкт.- 1)-й выходами подвой группы 11 информационных ч выходов, устройства, кроме того, К выходов 13 каждого из К блоков 4 логической свёртки 1-й группы связаны с К2 входами 22 соответствующих блоков14 логической свертки 0+1)-й группы, кроме выходов 13 первого блока 4.

Согласно одному из возможных вариантов ассоциативное запоминающее устройство (фиг, 2) содержит первый элемент ИЛИ 23, выход которого подключен к второму

входу 5 блока 24 для считывания информации из ассоциативной памяти большого объема, а первый- 25i и второй 252 входы являются соответственно входами разрешения записи и чтения, ассоциативную запо0 минающую матрицу 26, второй элемент ИЛИ 27, коммутатор 26, группу из одкт дешифраторов 291, количество входов каждого из которых равно logaK, а общее количество входов равно logam, и К-ичный

5 дешифратор 292, каждый разряд К-ичного входного числа которого представлен унитарным кодом (1 из К), причем выходной код из дешифратора 292 поступает в шины управления записью или чтением ассоциа0 тивной запоминающей матрицы 26 в зависимости от сигналов на входах 252 и 25i Чтение и Запись. Кроме того, ассоциативное запоминающее устройство большого объема содержит адресные входы 30,

5 вход 31 управления адресацией от внешнего адреса или блока 24, вход 32 выборки кристалла, входы 33 маски, информационные входы 34 данных, вход 19 Начало поиска, поисковые выходы 14, выход 18

0 Конец поиска, выход 10 (положительный результат поиска) и вход 7 мультизаписи. Группа дешифраторов 29i и дешифратор 292 представляют отдельные части одного дешифратора на Iog2m входов и m выходов.

5 Каждый регистр 1 дескрипторов, например, содержит (фиг. 3) группу из К триггеров 35, группу из К элементов И-НЕ 36, элемент И 37, первый 38 и второй 39 элементы задержки и выход 40 управления сбросом в на0 чальное состояние.

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

5 формирования информационного кода на входах 12 регистров 1 дескрипторов. Второй элемент 39 задержки обеспечивает задержку на время записи информации в триггеры 35. Сброс в начальное состояние

0 выделенного блоком 2 приоритета разряда регистра 1 дескрипторов происходит по заднему фронту сигнала записи (чтения) для последнего регистра 1 либо сигнала, сформированного на выходе элемента ИЛИ 3

5 предыдущей группы. Формирование единичного уровня сигнала управления сбросом происходит на управляющем выходе 40 регистров 1 дескрипторов.

Каждый из триггеров 35 регистра 1 дескрипторов может быть реализован (фиг. 4)

на элементах И-НЕ 41-48 и представляет двухтактный RCS-триггер с дополнительными входами 49 и 50 установки в 1 и в О. Кроме того, триггер 35 содержит первый вход (R) 51, второй вход (S) 52. вход 53 синхронизации и прямой выход 54.

Блок 4 логической свертки образуют (фиг, 5) коммутатор 55, группа элементов ИЛИ 56, группа элементов И 57, группа из К2 информационных входов 22, К вторых управляющих входов 21, первый управляю- зий вход 20 и К информационных выходов 13. При этом коммутатор 55 и группа элементов И 57 могут быть реализованы следующим образом.

Коммутатор 55 содержит (фиг, 6) К групп по К элементов И 58 (выходы каждого элемента выполнены по схеме с тремя состояниями), а группа элементов И 57 выполнена в виде МОНТАЖНОГО И с элементами 59 развязки (резисторы) и источником 60 логической единицы.

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

Перед началом работы устройства все разряды регистров 1 дескрипторов находятся в начальном состоянии (О), на выходах всех элементов ИЛИ 3, на управляющих и информационных выходах блоков 2 приоритета сформированы сигналы нулевого уровня. Следовательно, коммутаторы 55 всех блоков 4 логической свертки заблокированы (на их выходах - высокоомное состояние), а сигналы с информационных входов 8 устройства, проходя через элементы ИЛИ 56, поступают на выходы 14 устройства. На управляющих входах 5, 7 и 19 и выходах 10 и 18 устройства сформированы сигналы О. Таким образом, запись во все регистры 1 дескрипторов запрещена.

На входах 8 устройства сформирован информационный код, в котором единицами отмечаются части слов (слова), хранящиеся в ассоциативной запоминающей матрице 26, которые полностью совпадают незамаскированными разрядами с соответствующей частью признака опроса (с признаком опроса). Данный информационный код разбит на т/К групп по К разрядов в каждой группе. В блоках 4 логической свертки, каждый из которых содержит К2 входов и К выходов, происходит логическое суммирование информации каждой группы, т.е. если в каком-либо разряде любой группы информации содержится единица, то на соответствующем выходе блока 4 логической свертки формируется единичный сигнал. Информационный код в свернутом виде поступает на выходы 14 устройства и входы 12

всех регистров 1 дескрипторов. Применение предлагаемого устройства позволяет легко наращивать отдельные модули ассоциативной памяти по количеству разрядов

хранимых в них слов без существенных потерь быстродействия поиска. При этом отдельные модули ассоциативной памяти связаны между собой выходами (входами) 14 посредством МОНТАЖНОГО И (выход0 ной каскад первого блока 4 логической свертки, как и выходной каскад в известном устройстве, выполнен с открытым коллектором). Поэтому каждый разряд информационного кода на выходах 14 формируется как

5 логическое произведение битов информации, установленных на связанных между собой отдельных выходах 14j (j 1.K) ассоциативных модулей. Сформированный таким образом код поступает на входы 12 ре0 гистров 1 дескрипторов.

При поступлении сигнала Начало поиска (1)на первый управляющий вход 19 устройства в первый регистр 1 дискрипто- ров записывается код, сформированный на

5 выходах 14 устройства. Если в данном коде содержится хотя бы одна единица, то на выходе первого элемента ИЛИ 3 формируется постоянный потенциал 1, т.е. разрешается запись во второй регистр 1 дескрип0 торов, запрещается запись в первый регистр 1 дескрипторов и блокируются элементы ИЛИ 56 первого блока 4 логической свертки. На выходах первого блока 2 приоритета формируется унитарный код, в ко5 тором выделяется первая слева (справа) единица информационного кода, записанного в первом регистре 1 дескрипторов, т.е. разблокируется коммутатор 55 первого блока 4 и информация с его соответствующей

0 группы входов проходит на выход 14 устройства.

После окончания переходных процессов на входах 12 регистров 1 дескрипторов формируется информационный код (пораз5 рядное логическое произведение кодов, установленных на выходах 14 ассоциативных модулей), который записывается во второй регистр 1 дескрипторов (задержка обеспечивается первым элементом 38 задержки).

0 При этом на выходе 40 данного регистра 1 устанавливается единичный потенциал. Если в записанном во второй регистр 1 дескрипторов информационном коде нет единичных сигналов, то единичный сигнал с

5 выхода 40 второго регистра 1 дескрипторов, пройдя через второй элемент ИЛИ 3, формирует на выходе второго элемента 39 задержки (выходе 40) сигнал нулевого уровня. Таким образом формируется сигнал разрешения сброса выделенного первым блоком 2 приоритета разряда первого регистра 1 дескрипторов. Если в перном регистре 1 дескрипторов не содержится более единичных сигналов, то на выходе .8 устройства формируется нулевой сигнал, что свидетельствует об окончании поиска. В противном случае первый блок 2 приоритета выделяет очередной единичный сигнал и описанный процесс поиска продолжается.

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

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

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

Пример. Пусть ассоциативное запоминающее устройство состоит из 4 модулей по 16 () информационных слов произвольной разрядности в каждом. Данные модули соединены выходами (входами) 14 горизонтально (наращивается разрядность) посредством МОНТАЖНОГО И. Количество поисковых выходов равно 4 (). Таким образом, в каждом ассоциативном модуле па0 мяти содержится (Iog416 2) два регистра 1, блока 2 приоритета и элемента ИЛИ 3 и один (Iog4l6 -1 1) блок 4 логической свертки, содержащий 4 (т/К 16/4 4) группы входов 8 по 4 входа в каждой группе (всего

5 К2 16 входов), и 4 (К 4) выхода,

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

0 таблице.

Следовательно, в первые регистры 1 дескрипторов всех ассоциативных модулей записывается код 0011, а на выходе первого блока 2 приоритета устанавливается код

5 0010. Таким образом, информация с третьей (9,10,11,12, см. табл.) группы входов поступает на выходы 14 всех модулей и на них формируется код 0000, который записывается во второй регистр 1 дескрипторов всех

0 модулей памяти. При этом на выходе40 данных регистров 1 вырабатывается сигнал разрешения сброса разряда первого регистра 1 дескрипторов, выделенного соответствующим блоком 2 приорирета. После

5 этого в первый регистр 1 дискрипторов записывается код 0001, на выходах первого блока 2 приоритета устанавливается код 0001, а во второй регистр 1 дескрипторов записывается код 1000. На выходе 10 каж0 дого из блоков 24 формируется единичный сигнал, который разрешает производить чтение (или запись) из выбранной ячейки ассоциативной памяти. После этого сигнал Чтение сбрасывается (формируется О), а

5 следовательно, сбрасывается единица в соответствующем разряде второго регистра 1 дескрипторов. Так как больше единиц в коде, записанном во второй регистр 1 дескрипторов, нет, то на выходе соответст0 вующего элемента ИЛИ 3 устанавливается нулевой потенциал, т.е. формируется сигнал разрешения сброса в начальное состояние выделенного первым блоком 2 приоритета разряда первого регистра 1 дескрипторов.

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

Формула изобретения Устройство для считывания информации из ассоциативной памяти большого обь- ема, содержащее первый регистр дескрипторов, первый блок приоритета и первый элемент ИЛИ, выход которого является выходом признака конца поиска устройства, а входы подключены к информационным выходам первого регистра дескрипторов и к входам первого блока приоритета, информационные выходы которого являются адресными выходами первой группы устройства, а выходы приоритетного выделения единичного бита соединены с соответствующими входами сброса первого регистра дескрипторов, информационные входы которого являются поисковыми выходами устройства, а инверсный вход разрешения записи является входом начала поиска устройства, отличающееся тем, что, с целью увеличения информационной емкости ассоциативной памяти, реализованной на одном кристалле, за счет уменьшения числа внешних выводов поиска устройства, в него введены (1одкт-1) регистров дескрипторов, блоков приоритета, элементов ИЛИ и групп блоков логической свертки (где m - число информационных входов устройства, К - число поисковых выходов устройства), причем в каждой группе блоков логической свертки содержится по (i 1,2,...,(1одкт 1)) блоков, информационные входы регистров дескрипторов с второго по (одкт}-й соединены с информационными входами первого регистра дескрипторов и с выходами первого блока логической свертки, входы сброса регистров дескрипторов с второго по (одкт)-й поразрядно подключены к выходам приоритетного выделения

единичного бита соответствующих блоков приоритета, а информационные выходы соединены с входами соответствующих элементов ИЛИ и с входами соответствующих

блоков приоритета, выходы которых являются адресными выходами с второй по (одкт)-ю группу устройства, К входов каждого блока логической свертки последней (1одкт-1)-й группы являются входами задания совпадений устройства, К выходов каждой подгруппы из К блоков i логической свертки j-й группы 0(1одкт-1)3,2) подключены к К входам соответствующих блоков логической свертки (j-1) й группы,

входы разблокировки блоков логической свертки каждой i-й группы соединены с выходами 1-го блока приоритета, а вход разрешения свертки соединен с выходом 1-го элемента ИЛИ и с прямым входом разрешения записи (i+1)-ro регистра рескрипторов, выход каждого элемента ИЛИ подключен к инверсному входу разрешения записи соответствующего регистра дескрипторов, дополнительный вход эдементов ИЛИ соедииен с выходом формирования сигнала сброса соответствующего регистра дескрипторов, выход каждого р-ro элемента ИЛИ (р; одкт3,2) подключен к входу разрешения сброса единичного бита (р-1)-го регистра дескрипторов, выход (одкт)-го элемента ИЛИ является выходом признака на- чала цикла записи-чтения устройства, вход разрешения сброса единичного бита (одкт)-го регистра дескрипторов является

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

30 1

Изобретение относится к вычислительной технике и может быть использовано для построения высокопроизводительных систем хранения и обработки информации, выполненных с применением БИС ассоциативной памяти. Целью изобретения является увеличение информационной емкости ассоциативной памяти, реализованной на одном кристалле, за счет уменьшения количества внешних выводов поиска. Устройство содержит 1одкт регистров дескрипторов, 1одкт блоков приоритета, 1одкт элементов ИЛИ и (1одкт-1) групп блоков логической свертки по К (1 1, 21одкт-1) блоков в каждой группе, где т- количество входов (выходов) ассоциативной запоминающей матрицы; К- количество поисковых выходов устройства. Цель изобретения достигается тем, что в устройстве осуществляется каскадное логическое суммирование групп выходных сигналов ассоциативной запоминающей матрицы блоками логической свертки. Это позволяет в т/К раз уменьшить количество внешних выводов при т/К-крат- ном увеличении емкости ассоциативной памяти, выполненной на одном кристалле. 6 ил., 1 табл. (Л

f

JJ

is,

25t

J4

ITIS №

Фиг.2

§9

L9

с/

f

2/

гг

9$

е

0

л

95

:

о о о

к я

1091Ј91

Фиг. 6