Ассоциативное запоминающее устройство Советский патент 1988 года по МПК G11C15/00 

ел

00

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

Цель изобретения - повышение быстродействия устройства при выполнении ассоциативного поиска по критерию «ближайшее большее (меньшее) к заданному.

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

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

Блок 1 имеет адресный вход 5, первую группу информационных входов 6, первую группу информационных выходов 7.

Вторая группа информационных входов 8 устройства и вторая группа информационных выходов 9 устройства соединены соответственно с одними из информационных уходов коммутатора 10 и выходами регистра 2. Выходы регистра 2 соединены с информационными входами lli -11„ блока 12 модификации признака поиска (п - разрядность обрабатываемых данных). Входы 13i-13„ промежуточных значений признака блока 12 подключены к информационным выходам буферного регистра 14, информационные выходы которого соединены с выходами 15i -15„ промежуточных значений признака блока 12. Информационные выходы 16i - 16л блока 12 соединены с информационными входами коммутатора 10.

Блок 12 содержит п преобразователей 17| - 7п кодов, причем выход 18,- переноса (, п-1) преобразователя 17/ подключен к задающему входу (j + l)-ro преобразователя 17/+I. Вход 19| подключен к ис- точнику 20 потенциала логического нуля.

Устройство также содержит блок 21 управления, имеющий вход «Результат поиска 22, вход «Конец модификации 23 вход «Конец поиска 24 и вход «Начало работы 25. Блок 21 имеет выходы 26-28. Выход 28 блока 21 подключен к входам 29i - 29„ управления приемом блока 12. Блок 21 имеет также выходы 30-33. Выходы 32 и 33 являются соответственно выходами «Слово найдено и «Слово не найдено устройства.

Вход 34 режима поиска устройства соединен с входами 35i-35 управления видом поиска блока 12. Входы 36 и 37 блока 1 являются соответственно входом записи и входом чтения устройства.

Каждый преобразователь 17 (фиг. 2) содержит элемент НЕРАВНОЗНАЧНОСТБ 38, выходом связанный непосредственно с

5

0

0

5

0

5

5

0

входом элемента И 39 и через элемент НЕ 40 - с входом элемента И 41, элемент ИЛИ 42, элементНЕРАВНОЗНАЧНОСТЬ 43.

Блок 21 управления может быть реализован в виде микропрограммного устройства управления либо в виде управляющего автомата с жесткой логикой. Один из возможных вариантов реализации блока 21 в виде управляющего автомата (фиг. 3) содержит триггер 44, элементы И 45 и 46, элемент ИЛИ 47, триггер 48, элементы И 49 и 50, триггер 51, элементы И 52 и 53, элемент ИЛИ 54, триггер 55, элемент И 56, триггер 57, элемент И 58, триггер 59, элементы И 60 и 61, элементы НЕ 62-64, элементы ИЛИ 65-67, вход 68 синхронизации.

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

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

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

21управления, подачей сигнала на вход 34 устройства (единичного сигнала - при поиске ближайшего большего к заданному и нулевого сигнала - при поиске ближайшего меньшего к заданному), подачей заданного числа на входы 8 устройства. Единичный сигнал на входе 25 блока 21 управления инициирует формирование блоком 21 единичных сигналов на выходах 26 и 27 (фиг. 4, такт 1), которые осуществляют управление прохождением двоичного кода заданного числа с входов 8 через коммутатор 10 на входы регистра 2, прием упомянутого кода на регистр 2, установку регистров 3 и 14 ,в исходное.состояние (в исходном состоянии регистра 3 все его разряды установлены в единицу, а в исходном состоянии регистра 14 все его разряды, кроме младшего, обнулены, а младший установлен в единицу). Таким образом, на регистре 2 зафиксируется заданное слово, а все разряды регистра 3 будут установлены в единицу, что соответствует отсутствию маскирования.

В следующем такте блок 21 управления формирует единичный сигнал на выходе 30, которым инициируется опрос всех ячеек блока 1 кодом заданного числа. Если среди хранящихся в блоке 1 чисел имеется хотя бы одно, совпадающее с заданным, то, естественно, оно и будет ближайшим и на соответствующем выходе блока 1 будет сформирован сигнал единичного уровня, который через элемент ИЛИ 4 поступает на вход

22блока 21 управления, который формирует на своем выходе 33 сигнал успешного конца операции поиска. Код числа, ближайшего к заданному, при этом снимается с информационных выходов 9 устройства.

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

Поиск ближайшего большего к заданному осуществляется следующим образом.

В следующем за опросом блока 1 такте блок 21 управления формирует единичные сигналы на выходах 27 и 28. По первому из указанных сигналов осуществляется прием кода с выходов 16 блока 12 через открытый нулевым сигналом с выхода 26 коммутатор 10 на регистр 2, Второй из них разрешает установку в «О разрядов регистра 3 маски, отмеченных единицами кода, снимаемого с выходов 18 блока 12, и инициирует прием кода с выходов 15 блока 12 на регистр 14.

Код, снимаемый с выходов 16i -16„ блока 12 формируется следующим образом. Сигнал на выходе 16( (i 1, п) соответствует сигналу на входе И,-, если , где d - номер разряда (начиная с младших) в котором код на входах 111 -11„ содержит первый (начиная с младщих разрядов) нуль, в противном случае () сигнал на выходе 16/ является инверсией сигнала, подаваемого на вход 11,. Например, если на входы 11 подается код 01101011 (в приведенной записи младший разряд находится справа, , ), то на выходах 16i - 16л формируется код 01101100 (отмечены инвертируемые разряды).

Рассмотренное преобразование осуществляется следующим образом. Сигнал на входе 11, преобразователя 17,- инвертируется элементом НЕРАВНОЗНАЧНОСТЬ 43/, если имеются единичные сигналы на входах 13,- или 19,. В частности, поскольку на вход I3i поступает единичный сигнал с младщего разряда регистра 14, то на выходе 16i формируется сигнал, инверсный поданному на вход Пь На выходе элемента НЕРАВНО- ЗНАЧНОСТЬ 38, сигнал единичного уровня формируется в том случае, если на вход 11; подается нуль при поиске ближайщего больщего (на вход 35t при этом подается единица), и в противном случае при поиске ближайшего меньшего (на вход 35/ при этом подается нуль). Соответственно, если на вход 111 подан сигнал единичного потенциала, то сформируется сигнал единичного уровня на выходе 18i, который поступает на вход установки в «О младшего разряда регистра 3 маски и на вход 102 следующего преобразователя 172.

Преобразования, аналогичные имевшим место в преобразователе 17i, происходят последовательно во втором, третьем и т.д. преобразователях 17 вплоть до d-ro, на вход 7d которого поступает нуль, закрывающий момент 41rf, так что сигнал на выходе 18d имеет нулевой потенциал и не инициирует работу последующих преобразователей

5

0

0

0

5

5

5

0

17. На выходе 15 преобразователя формируется единичный сигнал, который записывает единицу в d-й разряд регистра 14. Таким образом, в рамках приведенного примера на регистре 3 и регистре 14 зафиксируются соответственно коды 11111100 и 00000100.

В следующем такте сигналом с выхода 30 блока 21 управления инициируется опрос блока 1. В случае, если в блоке 1 не содержится ни одного слова, совпадающего с содержимым регистра 2, на выходе элемента ИЛИ 4 и на входе 22 блока 21 сохраняется потенциал нулевого уровня. Блок 21 формирует сигналы на выходах 27 и 28.

На регистры 2, 3 и 14 с соответствующих выходов блока 12 кода опроса заносятся коды, формируемые по описанному способу, причем роль d при втором цикле преобразований играет величина dg - номер позиции второго нуля в заданном слове. Так, в условиях приведенного примера d2 5, а коды, подаваемые на регистры 2, 3 и 14, имеют соответственно вид: 01110000, 11110000, 0010000. Если в текущем цикле преобразования кода сформируется сигнал на выходе 18 старщего преобразователя 17„, что соответствует отсутствию в коде заданного числа непреобразованных на предыдущих циклах нулей, то блоком 21 управления формируется еиничный сигнал на выходе 32, который свидетельствует о том, что среди чисел, хранящихся в накопителе, отсутствуют числа, большие заданного.

После каждого цикла преобразования содержимого регистров 2, 3 и 14 производится опрос блока 1. Указанная процедура продолжается до появления сигнала на выходе 32 или входе 22 блока 21 управления. Во втором случае блок 21 управления сформирует сигнал сдвига вправо содержимого регистров 3 и 14 (фиг. 4, такт 7) на своем выходе 31, а затем сформирует сигнал опроса на своем выходе 30. Если результат опроса блока 1 отрицателен (т.е. на входе 22 блока 21 управления сохраняется нулевой сигнал), то содержимое регистра 2 корректируется путем принятия на регистр 2 кода с выходов 16 блока 12 (при этом блок 21 управления формирует сигналы на своих выходах 27). Указанный код отличается от кода на входах 11 инверсным значением одного разряда, позиция которого определяется единицей в регистре 14.

После коррекции вновь повторяется рассмотренный цикл, включающий сдвиг вправо содержимого регистров 3 и 14, опрос блока 1 и, при необходимости, коррекцию содержимого регистра 2. Последним циклом является цикл, в котором в младшем разряде регистра 14 появляется единица, которая, поступая на вход 24 блока 21 управления, инициирует появление сигнала успешного конца операции на выходе 33.

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

Ассоциативное запоминающее устройство, содержащее блок ассоциативной памяти, регистр признака поиска, регистр маски, элемент ИЛИ, буферный регистр и блок управления, причем выходы результата поиска блока ассоциативной памяти подключены к входам элемента ИЛИ, выход которого соединен с входом «Результат поиска блока управления, выход младщего разряда буферного регистра соединен с входом «Конец поиска блока управления, вход «Начало работы блока управления является входом запуска устройства, первый выход блока управления подключен к входу управления записью регистра признака поиска, выходы разрядов которого подключены к входам поиска блока памяти и являются информационными выходами первой группы устройства, выходы разрядов регистра маски соединены с входами маскирования блока ассоциативной памяти, второй выход блока управления подключен к входу управления сдвигом вправо буферного регистра и к входу управления сдвигом вправо регистра маски, третий выход блока управления подключен к вхоДу управления поиском блока ассоциативной памяти; адресный вход блока ассоциативной памяти является адресным входом устройства, информационные входы блока ассоциативной памяти являются информационными входами второй группы устройства, вход управления записью и вход управления чтением блока ассоциативной памяти являются соответственно входом записи и входом чтения устройства, информационные выходы блока ассоциативной памяти являются информационными выходами второй группы устройства, четвертый и пятый выходы блока управления являются соответственно выхо

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

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

0 соединен с входом «Конец модификации блока управления, седьмой выход блока управления подключен к управляющему входу коммутатора, к входам установки в «О разрядов буферного регистра, кроме младщего разряда, к входу буферного регистра, к входу установки в «1 регистра маски, вход разрешения установки в «О разрядов регистра маски соединен с шестым выходом блока управления.

0

5

5

27 Зг 35

Vus.l

Hofiefl

/77l7/ /77(7

123 56183 Ю 11 1Z 13 7 75

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

%

0

r n

л n A/A

%1

A П

л A

ф//.4