Ассоциативное оперативное запоминающее устройство

 

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в цифровых вычислительных системах с распараллеливанием процессов обработки информации . Цепь изобретения - повышение быстродействия устройств. Устройство содержит первый и второй ассоциативные блоки постоянной памяти, первьпЧ и второй регистры признака опроса, первый и второй регистры маски, первую , вторую, третью и четвертую группы элементов И, первый и второй индексные регистры, первый, второй и третий буферные регистры, блок оперативной памяти, первый и второй регистры числа , первый и второй элементы ИЛИ, первую и вторую группы элементов ИЛИ, первый и второй блоки анализа многократных совпадений, элементы НЕРАВНОЗНАЧНОСТЬ и блок управления. В устройстве существенно повышается скорость маскированного поиска за счет выполнения операций маскирования в ассоциативных блоках постоянной памяти по сравнению с перебором, реализуемым в блоке оперативной памяти при ассоциативном маскированном поиске . 5 ил. С « С/)

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

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

РЕСПУб ЛИК (Ч> 1 С 11 С 15/00

ОГ)ИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4 159626/24-24 (22) 15.08.86 (46) 30.05.88. Бюл. У 20 (72) В.И.Корнейчук, В.П.Сидоренко, А.П.Марковский и А.В.Чернов (53) 681.327 (088.8) (56) Авторское свидетельство СССР

Р 604033, кл. G 11 С 15/00, 1978.

Авторское свидетельство СССР

В 978197, кл. G 11 С 15/00, 1982. (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНАКП!ЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в цифровых вычислительных системах с распараллеливанием процессов обработки информации. Цель изобретения — повышение быстродействия устройств. Устройство

„.Я0„„! 99818 А1 содержит первый и второй ассоциативные блоки постоянной памяти, первый и второй регистры признака опроса, первый и второй регистры маски, первую, вторую, третью и четвертую группы элементов И, первый и второй индексные регистры, первый, второй и третий буферные регистры, блок оперативной памяти, первый и второй регистры числа, первый и второй элементы ИЛИ, первую и вторую группы элементов ИЛИ, первый и второй блоки анализа многократных совпадений, элементы НЕРАВНОЗНАЧНОСТЬ и блок управления. В устройстве существенно повышается скорость маскированного поиска за счет а выполнения операций маскирования в

Ф ассоциативных блоках постоянной памяти по сравнению с перебором, реализуемым в блоке оперативной памяти при ассоциативном маскированном поиске. 5 ил.

1399818

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

На фиг.1 предста»лена структурная схема ассоциативного операrn»noro запоминающего устройства; на фиг.2 структурная схема одного и < »озможных вариантов построения блока микропрограммного управления; на фиг.3-5 — 15 временные диаграммы процессов соответственно записи (фиг.3), исключения (фиг.4) и простого маскированного поиска (фиг.5).

Ассоциативное оперативное эапоми- 20 нающее устройство (фиг.1) содержит первый 1 и второй 2 ассоциативные блоки постоянной памяти, первые регистр 3 признака опроса и регистр 4 маски, вторые регистр 5 признака onроса и регистр 6 маски. Входы регистров 3 и 5 являются соответственно стаРшими 7< 7ч12 и млаДшими 7ь!г

7„информационными входами устройства (n — разрядность чисел) . Входы регистров 4 и 6 являются соответственно старшими 8< — 8 „1 и младшими

8 „, — 8„ маскирующими входами устройства. Устройство также содержит первую группу элементов И 9„ — 9 (m 2 ), первый индексный регистр

012 35

10, первый буферный регистр 11, первый блок 12 анализа многократных совпадений, первый элемент ИЛИ 13, блок

14 оперативной памяти, первый регистр

15 числа, выходы которого являются старшими информационными выходами устройства 16 < — 16nl2 вторую группу элементов И 17< — 17, второй индексный регистр 18, второй буферный регистр 19, первую группу элементов

ИЛИ 20< — 20, третью группу элементов И 21< — 21, вторую группу элементов ИЛ1 22< — 22ь„ четвертую группу элементов И 23, — 23» элементы

НЕРАВНОЗНАЧНОСТЬ 24» — 24„,, третий 50 буферный регистр 25, второй элемент

К1Н 26, второй блок 27 анализа многократных совпадений, второй регистр

28 числа, блок 29 управления, имеющий выходы 30-43 и входы 44-46. 55

Блок 29 управления может быть выполнен различным образом. Один из возможных »ариачтов блока 29 содержит (фиг.2) блок 47 памяти микропрограмм, регистр 48 микрокоманды, счетчик 49 адреса микрокоманд, блок 50 памяти начальных адресов микропрограмм, мультиплексор 51 записи, мультиплексор 52 условий и вход 53 подачи тактовых импульсов.

Ассоциативное оперативное запоминающее устройство работает следующим образом.

В каждом иэ блоков 1 и 2 объемом

m п/2-разрядных чисел (слов) в процессе изготовления записываются и постоянно хранятся все возможные значения п/2-разрядного двоичного кода.

В режиме записи информации (фиг.3) п-разрядный код записываемого слова подается на входы 7 устройства, на входы 8 — нулевой потенциал, а на входы 46 — код операции записи. Операция записи длится два такта. В первом такте единичные сигналы формируются на выходах 30, 34-37, 39, 40 блока 29 управления, по которым осуществляется ассоциативный опрос первого 1 и второго 2 блоков памяти соответственно старшей и младшей частями записываемого слова, в результате чего единичный сигнал формируется на одном из выходов блока 1 и на одном из выходов блока 2. В соответствующие разряды индексных регистров 10, 18 по сигналу с выхода 34 блока 29 производится запись единицы, свидетельствующей о наличии записываемого слова в запоминающем устройстве. Сигналами с выходов 35 и 37 блока 29 производится запись единицы в регистрах 11 и 19. Поскольку в регистре

11 оказывается записанной только одна единица, блок 12 анализа многократных совпадений формирует на своих выходах код, аналогичный подаваемому на его вход, т.е. код, содержащий одну единицу, позиция которой определяется кодом, поданным на входы 7. Указанным кодом выбирается одна из строк блока 14, которая по сигналу с выхода 30 блока 29 считывается на информационные выходы блока 14 и поступает на входы соответствующих элементов ИЛИ 22 и И 23. Считываемая из блока 14 строка представляет соII /2 бой кодовое слово длиной 2 разрядов, причем единица в этом кодовом слове соответствует хранению в запоминающем устройстве слова, старши<.

1399818

10

55 разряды которого соответствуют адресу строки, в которой находится кодовое слово, а младшие разряды которого соответствуют номеру разряда, в котором записана единица. Например, при и 8 хранение трех слов 10010000, 10011111, 10010011 соответствует тому, что в строке 9(1001) блока 14 хранится кодовое слово, имеющее вид

1000000000001001, т.е. единицы зафиксированы в разрядах 0(0000), 3(0011), 15(1111). С выходов регистра 19 поступает код, содержащий только одну единицу, Запись состоит в том, чтобы записать указанную единицу в кодовое слово, считываемое иэ блока 14. Если в условиях приведенного выше примера записывается еще одно слово, например

10011001, то код, считываемый с регистра 19 имеет вид 0000001000000000 (единица записана в 9-ом (1001) разряде), а скорректированное с учетом записи упомянутого слова кодовое слово должно иметь вид 1000001000001001.

Код, считываемый с элементов ИЛИ 20, представляет собой дизъюнкцию кодово-. го слова, считываемого из блока 14, и слова, поступающего из регистра 19, Указанный код проходит через открытые сигналом с выхода 40 блока 29 элементы И 2 1 и поступает на первые входы элементов ИЛИ 20, на другие входы которого поступает код, являющийся конъюнкцией кодового слова, считываемого из блока 14, и слова, считываемого с выходов регистра 19 (упомянутая конъюнкция формируется на выходах элементов И 23), так, что на выходах элементов ИЛИ 20 формируется код, идентичный коду, формируемому на выходах элементов ИЛИ 22.

Этот код по сигналу с выхода 39 блока 29 записывается в регистр 25 и поступает на входы элемента ИЛИ 26.

Все описанные вьппе операции производятся в течение первого такта. Во втором такте с выхода 31 блока 29 выдается единичный управляниций сигнал записи содержимого регистра 25 . в блок 14.

В режиме исключения информации исключаемое слово подается на информационные входы 7 устройства, на выходы 8 устройства подается нулевой потенциал, а на вход 46 блока 29 подается код операции исключения, по которому с приходом очередного тактового импульса на вход 53 блок 29 осуществляет вьдачу последовательности управляющих сигналов (фиг.4), инициирующих выполнение процедуры исключения слова, которая длится либо два,. либо три такта. В течение первого такта выдаются сигналы с выходов 30, 35-37, 39, 41 блока 29. Аналогично, как н описанном вьппе процессе записи, производится считывание кодового слова иэ блока 14 и формирование кода на выходе регистра 19. Последний иэ упомянутых кодов инвертируется элементами НЕРАВНОЗНАЧНОСТЬ 24 (на входи которых подается единица с выхода 41 блока 29) и поступает на один иэ выходов элементов И 23, на другие входы которого подается кодовое слово с выходов блока 14 так, что на выходах элементов И 23 формируется скорректированное кодовое слово, идентичное считанному с блока 14 во всех разрядах за исключением одного, в котором записывается нуль (указанный разряд соответствует разряду, отме» ченному единицей в коде, считываемом с выходов регистра 19). Например, если, в условиях приведенного вьппе примера исключается слово 10010011, то на выходах регистра 19 формируется код 0000000000001000, который инвертируется на элементах НЕРАВНОЗНАЧНОСТЬ 24 (1111 1111 1111 0111) и поразрядно конъюнктируется с кодовым словом 1000 0000 0000 1001, в реэультате чего на выходе элементов И 23 формируется скорректированное кодовое слово: 1000 0000 0000 0001. Скорректированное описанным вьппе способом слово без изменений проходит через элементы ИЛИ 20 и поступает на входы элемента ИЛИ 26, а также по сигналу с выхода 39 фиксируется на регистре

25. В продолжение второго такта производится зались скорректированного кодового слова из регистра 25 в блок

14. Если скорректированное слово окажется состоящим из одних нулей, то нулевой сигнал на выходе элемента

ИЛИ 26, поступая на вход 45 блока

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

Помимо записи и исключения одного слова возможна также и множественная . апись и исключение, реализуемые с. помощью маскирования разрядов записываемого (исключаемого) слова. При

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

12 анализа многократных совпадений на входы блока 14 единичных сигналон с выходов блока 1, В режиме просчого маскированного поиска код признака опроса поступает через входы 7 на регистры 3, 5 признака опроса, а маска заносится по входам 8 на регистры 4, 5 маски. На вход 46 подается код операции простого маскированного поиска, по которому блок 29 с приходом очередного тактового импульса формирует последовательность управляющих сигналов (фиг.5), инициирующих процедуру поисr ка, которая длится 2 тактов при маскировании r старших разрядов и р тактов, при маскировании младших разрядов (р — количество слов, хранящихся в запоминающем устройстве, отвечающих критерию поиска). Процесс поиска начинается выдачей блоком 29 единичных сигналов с выходов 35, 37, по которым производится ассоциативный опрос блоков 1, 2 с фиксацией реэультатов опроса на регистрах 11, 19 соответственно. В этом же такте форми" руются единичные сигналы на выходах

36, 30, по которым блок 12 формирует на своем выходе код, сЬдержащий ровно одну единицу, соответствующую первой из единиц, зафиксированных на регистре 11. Указанный код поступает на адресные входы блока 14, с которого по сигналу с выхода 30 блока

29 считывается кодовое слово. С выходов 40, 4 1 блока 29 снимаются сигналы нулевого потенциала, которыми закрываются элементы И 21 и на выходе элементов НЕРАВНОЗНАЧНОСТЬ 24 формируется код, идентичный снимаемому с выходов регистра 19, который поступает на одно из выходов элементов И

23, на другие входы которых поступает считанное из блока 14 кодовое слово так, что на выходах элементов И 23 и ИЛИ 20 формируется код, соответствующий конъюнкции указанных ньппе кодов, который сигналом с выхода 39

99818 6

55 блока 29 фиксирует на регистре 25.

Все описанные ньш е процедуры происходят в течение первого такта.

Операции, проводимые во втором такте, зависят от сигнала, снимаемого на вход 45 блока 29 с ныхода элемента ИЛИ 26. Если упомянутьп1 сигнал имеет единичньп уровень (такт I, фиг.5), то блок 29 формирует сигналы на выходах 32, 38, по которым блок

27 формирует на своих выходах код, имеющий одну единицу, положение которой соответствует перной единице кода, зафиксированного на регистре 25.

Указанный код поступает на адресные входы блока 2, в то время как код с блока 12 совпадений поступает на адресные входы накопителя блока 1, с информационных выходов блоков 1, 2 под действием единичного сигнала с выхода 32 блока 29 на регистры 15, 28 и далее на выходы 16 устройства.

Считывается первое слово, отвечающее критерию поиска. Считывание слова на выходы 16 стробируется сигналом на выходе 42 блока 29. Сигналом с блока 27 разряд регистра 25 обнуляется и анализируется следующий разряд регистра 25. Описанньп выше процесс при этом повторяется столько тактов, сколько единиц содержится в коде, хранящемся в регистре 25 до его обнуления (на временной диаграмме, приведенной на фиг.5 число таких тактов равно трем). При появлении нулевого сигнала на входе 45 блока

29 последний с приходом очередного тактового импульса (такт V на фиг.5) 9 формирует единичные сигналы на выходах 30, 36, 39, под действием которых блоком 12 ныделяется очередная единица, производится счиТывание из блока

14 очередного слова, которое конъюнктируется с кодом, поступающим с выходов регистра 19 и записывается в регистр 25. С приходом очередного тактового импульса начинается анализ единиц, записанных н регистре 25 (такты VI, VII на фиг„5). Описанный процесс продолжается до тех пор, пока на входе 44 блока 29 не появится нулевой сигнал, свидетельствующий о том, все единицы из регистра 11 обработаны. Блок 29 выдает сигнал конца операции с выхода 43.

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

Ассоциативное оперативное запоминающее устройство, содержащее блок

7 139<<8 18 8 ка управления подключен к входам приния быстродействия устройства, в него соответственно к признаковым и маскиинформа»»»»онные вь»ходь< которых соединены с информационными входами первого и второго регистров числа соответдинены с информационными входами пердинены с информа»»»»онными входами перза многократных совпадений соединены

55 с седьмым вьжодом блока управления, вой группы первого буферного регистра, t»t»$npt»at»ttnttttt t< входы второй групоперативной памяти, первый и второй регистры признака опроса, »»ервь»»» и второй регистры маски, первый и второй регистры числа, первую, вторую и третью группы элементов И, первую группу элементов И1П1, первый элемент

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

НЕРАВНОЗНАЧНОСТЬ, вторая группа элементов ИЛИ, четвертая группа элементов И и второй элемент ИЛИ, причем выходы первого и второго регистров приэйака опроса и выходы первого и второго регистров маски подключены рующим входам первого и второго ассоциативных блоков постоянной памяти, ственно, выходы результатов поиска первого и второго ассоциативных блоков постоянной памяти подключены к первым входам элементов И первой и второй групп соответственно и соевого и второго индексных регистров соответственно, выходы которых подключены к вторым входам элементов И первой и второй групп соответственно, выходы элементов И первой группы соепы и вьж<»ды которого соединены соответствеии « пь«.: да".<è первой группы и информани <п<и<ьп» «:»îäë<»t» иер» ого блока анализа многократных совпадений, вьжоды второй группы которого соединены с входами первого элемента

И1П1, адреснь»»»и входами первого ассо5

»в»атив»»ого блока постоянной памяти и адрес»»ь»ми входами блока оперативной памяти, вьжоды которого подклкчены к первым входам элементов ИЛИ второй группы и элементов И четвертой группы, выходы которых соединены с вторыми входами элементов ИЛИ первой группы, выходы которых подключены к информационным входам первой группы третьего буферного регистра, выходы второго буферного регистра подключены к первым входам элементов НЕРАВНО"

ЗНАЧНОСТЬ и вторым входам элементов

И1П1 второй группы, выходы которых соединены с первыми входами элементов И третьей группы, выходы элементов НЕРАВНОЗНАЧНОСТЬ соединены с втоpttt»t» входами элементов И четвертой группы, выходы элементов И второй

25 группы подключены к информационным входам второго буферного регистра, информационные входы второй группы третьего буферного регистра соединены с выходами первой группы второго

»О блока анализа многократных совпадений, выходы второй группы которого подключены к адресным входам второго ассоциативного блока постоянной памяти, выходы третьего буферного регистра подключены к информационным вхо35 дам второго блока анализа многократных совпадений, информационным входам блока оперативной памяти и входам второго элемента ИЛИ, третий выход

40 блока управления соединен с входами адресного считывания первого и второго ассоциативных блоков постоянной памяти, четвертый выход блока управления подключен к входам управления записью нулей первого и второго ин45 дексных регистров, вхоць» управления записью единиц которых соединены с пятым выходом блока управления, шестой выход которого подключен к входу управления поиском первого ассоциа50 тивного блока постояниои памяти и входу приема первого буферного реги-. стра, установочный вход которого и управляющий вход первого блока аналивосьмой вьжод которого .< дкпю<»ен к входу ,уиравления»<оиском яторог

ro регистра, вход управления приемом которого соединен с десятым выходом блока управления, одиннадцатый и двенадцатый выходы блока управления подключены соответственно к вторым входам элементов И третьей группы и элементов НЕРАВНОЗНАЧНОСТЬ, тринад18 1О цатый и четырнадцатый выходы блока управления являются соответственно выходами "Число найдено и "Все числа найдены" устройства, входы "Конец обработки" и "Результат поиска" блока управления подключены соответственно к выходам первого и второго элементов ИЛИ, вход кода операции блока управления является входом ре кима работы устройства.

1399818 зо

st и зз

39

ss зв

ы зв и фД

М а з

ФФ 45

@иг.2

Тока. игл.

ps) д

8ьаодь!

Ух57, И, ым Р9 hP

bNOlb

_#_,59

Зыкод

Л

Риа 3

1399818

Тцнт аппп. (Х5) Выхо

4 юг. 4 дьиоды

ЯО,З6ЮУ

Вход

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

Техред М.Ходанич

Редактор В ° Ковтун

Корректор Г Решетник

Заказ 2671/52

Типам 590 Подписное

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

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

Производстненно-полиграфическое предприятие г У г. жгород, ул. Проектная, 4

Такт.

&ll. о

ыходы

F5 7 в.ог

Выход

У2,М,42

Выходь цуги

Ведь|

У7МЛ

Выход

Ло

ЬоЯВ