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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4647874/24 (22) 19.12.88 (46) 28.02.91. Бюл. М 8 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) Ю.В.Яблуновский, В.П.Сидоренко, А.П.Марковский и В.И. Корнейчук (53) 681,327.6(088.8) (56) Авторское свидетельство СССР

N 1388949, кл. 6 11 С15/00, 1988.

БИС ассоциативного ЗУ КР583РА1 емкостью 128 бит. — Электронная промышленность, 1986, вып. 4(152), с. 82. (54) УСТРОЙСТВО ДЛЯ СЧИТЫВАНИЯ ИНФОРМАЦИИ ИЗ АССОЦИАТИВНОЙ ПАМЯТИ БОЛЬШОГО ОБЪЕМА (57) Изобретение относится к вычислительной технике и может быть использовано для построения высокопроизводительных систем хранения и обработки информации, выполненных с применением БИС ассоциаИзобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано для построения высокопроизводительных систем хранения и обработки информации, выполненных на узлах с большой и сверхбольшой степенью интеграции.

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

На фиг. 1 представлена функциональная схема устройства для считывания ин„„ А „„1631607 А1 тивной памяти. Целью изобретения является увеличение информационной емкости ассоциативной памяти, реализованной на одном кристалле, эа счет уменьшения количества внешних выводов поиска. Устройство содержит 1оцкт регистров дескрипторов, 1оцкт блоков приоритета, !оцкп элементов

ИЛИ и (1оцкгп — 1) групп блоков логической свертки по К (! = 1, 2,..., !оцкв — 1) блоков в каждой группе, где m — количество входов (выходов) ассоциативной запоминающей матрицы; К вЂ” количество поисковых выходов устройства. Цель изобретения достигается ,тем, что в устройстве осуществляется каскадное логическое суммирование групп выходных сигналов ассоциативной запоминающей матрицы блоками логической свертки. Это позволяет в m/Ê раэ уменьшить количество внешних выводов при m/Ê-кратном увеличении емкости ассоциативной памяти, выполненной на одном кристалле.

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

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

1631607 (поисковых) выходов устройства), группу из

logym блоков 2 приоритета, группу иэ logym элементов ИЛИ 3 и (logym — 1) групп блоков 4 логической свертки по К (i=1,2,..., (logjam -1) блоков 4 в каждой группе, причем, второй управляющий вход 5 устройства подключен к третьему управляющему входу 6 последнего (logjam — 20)-ro регистра 1 дескрипторов, третий управляющий вход 7 устройства соединен с дополнительным управляющим входом последнего блока 2 приоритета, а вторые информационные входы 8 — с К входами каждого из m/Ê блоков

2 2

4 логической свертки, причем второй управляющий вход 9 последнего блока 2 приоритета подключен к третьему управляющему входу 6 предыдущего (log

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

23, выход которого подключен к второму входу 5 блока 24 для считывания информации из ассоциативной памяти большого объема, а первый 251 и второй 252 входы являются соответственно входами разрешения записи и чтения, ассоциативную.запоминающую матрицу 26, второй элемент

ИЛИ 27, коммутатор 26, группу из logjam дешифраторов 29, количество входов каждого из которых равно logzK, а общее количество входов равно logzm, и К-ичный дешифратор 29, каждый разряд К-ичного входного числа которого представлен унитарным кодом ("1 из К"), причем выходной код из дешифратора 292 поступает в шины управления записью или чтением ассоциативной запоминающей матрицы 26 в зависимости от сигналов на входах 252 и 25

"Чтение" и "Запись". Кроме того, ассоциативное запоминающее устройство большого объема содержит адресные входы 30, вход 31 управления адресацией от внешнега адреса или блока 24, вход 32 выборки кристалла, входы 33 маски, информационные входы 34 данных, вход 19 "Начало поиска", поисковые выходы 14, выход 18

"Конец поиска", выход 10 (положительный результат поиска) и вход 7 мультизаписи.

Группа дешифраторов 29> и дешифратор

29z представляют отдельные части одного дешифратора на logjam входов и m выходов.

Каждый регистр 1 дескрипторов, например, содержит (фиг. 3) группу из К триггеров

35, группу из К элементов И вЂ” НЕ 36, элемент

И 37, первый 38 и второй 39 элементы задержки и выход 40 управления сбросом в начальное состояние.

Первый элемент 38 задержки обеспечивает задержку сигнала записи на время прохождения сигналов через соответствующие блоки 4 логической свертки, т.е. на момент формирования информационного кода на входах 12 регистров 1 дескрипторов. Второй элемент 39 задержки обеспечивает задержку на время записи информации s триггеры 35. Сброс в начальное состояние выделенного блоком 2 приоритета разряда регистра 1 дескрипторов происходит по за- днему фронту сигнала записи (чтения) для последнего регистра 1 либо сигнала, сформированного на выходе элемента ИЛИ 3 предыдущей группы. Формирование единичного уровня сигнала управления сбросом происходит на управляющем выходе 40 регистров 1 дескрипторов.

Каждый из триггеров 35 регистра 1 дескрипторов может быть реализован (фиг. 4) 163" 607 на элементах И вЂ” НЕ 41 — 48 и представляет двухтактный RCS-триггер с дополнительными входами 49 и 50 установки в "1" и в "0".

Кроме того, триггер 35 содержит первый вход (R) 51, второй вход (S) 52, вход 53 синхронизации и прямой выход 54.

Блок 4 логической свертки образуют (фиг. 5) коммутатор 55, группа элементов

ИЛИ 56, группа элементов И 57, группа из

К информационных входов 22, К вторых управляющих входов 21, первый управляюзий вход 20 и К информационных выходов

13. При этом коммутатор 55 и группа элементов И 57 могут быть реализованы следующим образом.

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

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

Перед началом работы устройства все разряды регистров 1 дескрипторов находятся в начальном состоянии ("0"), на выходах всех элементов ИЛИ 3, на управляющих и информационных выходах блоков 2 приоритета сформированы сигналы нулевого уровня. Следовательно, коммутаторы 55 всех блоков 4 логической свертки заблокированы (на их выходах — высокоомное состояние), а сигналы с информационных входов

8 устройства, проходя через элементы ИЛИ

56, поступают на выходы 14 устройства, На управляющих входах 5, 7 и 19 и выходах 10 и 18 устройства сформированы сигналы "0".

Таким образом, запись во все регистры 1 дескрипторов запрещена.

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

Информационный код в свернутом виде поступает на выходы 14 устройства и входы 12

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

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

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

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

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

Таким образом формируется сигнал разрешения сброса выделенного первым бло1631607

55 ком 2 приоритета разряда первого регистра

1 дескрипторов. Если в первом регистре 1 дескрипторов не содержится более единичных сигналов, то на выходе .8 устройства формируется нулевой сигнал, что саидетельствует об окончании поиска. В противном случае первый блок 2 приоритета выделяет очередной единичный сигнал и описанный процесс поиска продолжается.

Если в какой-либо разряд второго регистра 1 дескрипторов был записан единичный сигнал, то на выходе второго элемента

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

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

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

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

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

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

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

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

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

0010. Таким образом, информация с третьей (9, 10, 11, 12, см. табл,) группы входов поступает на выходы 14 всех модулей и на них формируе- ся код 0000, который записывается во второй регистр 1 дескрипторов всех модулей памяти. При этом на выходе 40 данных регистров 1 вырабатывается сигнал разрешения сброса разряда первого регистра 1 дескрипторов, выделенного соответствующим блоком 2 приорирета, После этого в первый регистр 1 дискрипторов записывается код 0001, на выходах первого блока 2 приоритета устанавливается код

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

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

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

1631607 l631607

5

15

25

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

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

ИЛИ и групп блоков логической свертки (где

m — число информационных входов устройства, К вЂ” число поисковых выходов устройства), причем в каждой группе блоков логической свертки содержится по К (! =

= 1,2,...,(iogym 1)) блоков, информационные входы регистров дескрипторов с второго по (logjam)-й соединены с информационными входами первого регистра дескрипторов и с выходами первого блока логической свертки, входы сброса регистров дескрипторов с второго по (!оцкпфй поразрядно подключены к выходам приоритетного выделения единичного бита соответствующих блоков приоритета, а информационные выходы соединены с входами соответствующих элементов ИЛИ и с входами соответствующих блоков приоритета, выходы которйх являются адресными выходами с второй по (logjam)-ю группу устройства, К входов каждого блока логической свертки последней (logym — 1)-й группы являются входами задания совпадений устройства, К выходов каждой подгруппы из К блоков логической свертки j-й группы (j=(logym — 1)...„3,2) подключены к К входам соответствующих благ ков логической свертки (j — 1) -й группы, входы разблокировки блоков логической свертки каждой 1-й группы соединены с выходами 1-го блока приоритета, а вход разрешения свертки соединен с выходом i-го элемента ИЛИ и с прямым входом разрешения записи (!+1)-го регистра рескрипторов, выход каждого элемента ИЛИ подключен к инверсному входу разрешения записи соответствующего регистра дескрипторов, дополнительный вход эдементов ИЛИ соединен с выходом формирования сигнала сброса соответствующего регистра дескрипторов, выход каждого р-го элемента ИЛИ (р-.logjam,...,3,2) подключен к входу разрешения сброса единичного бита (р-1)-ro регистра дескрипторов, выход (logKm)-го элемента ИЛИ является выходом признака начала цикла записи-чтения устройства, вход разрешения сброса единичного бита (logym)-го регистра дескрипторов является входом признака конца цикла записи-чтения устройства, вход блокировки анализа приоритета (цацка)-го блока приоритета является входом разрешения мультиэаписи устройства.

1631607

163i607

1631607

2f 2Ю

Фог. д

Составитель О.Исаев

Техред М.Моргентал

Корректор Н.Ревская

Редактор А.Огар

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

Заказ 550 Тираж 343 Подписное .

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

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