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

1

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

Цель изобретения - повышение быстродействия устройства.

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

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

13

старшими 7, - 7г,,2 младшими 7,|,j, - 7 информационными входами устройства (п - разрядность чисел). Входы регистров 4 и 6 являются соответственно старшими 8 , - 8 ,,|2 и младшими - 8f, маскирующими входами устройства. Устройство также содержит первую группу элементов И 9, 9 ( ) , первьв1 индексньй регистр 10, первьй буферный регистр 11, первый блок 12 анализа многократных совпадений, первый элемент ИЛИ 13, блок

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

15числа, выходы которого являются старшими информационными выходами устройства 16 I - 16( , вторую группу элементов И 17, - 17, второй индексный регистр 18, второй буферньп1 регистр 19, первую rpymiy элементов ИЛИ 20 ( - 20, третью группу элементов И 21, - 21,, вторую группу элементов ИЛИ 22, - 22,, четвертую группу элементов И 23 , - 23, элементы НЕРАВНОЗНАЧНОСТЬ 24, - 24, третий буферный регистр 25, второй элемент ИЛИ 26, второй блок 27 анализа многократных совпадений, второй регистр 28 числа, блок 29 управления, имеющий выходы 30-43 и входы 44-46.

Блок 29 управления может быть выполнен различньм образом. Один з возможных вариантов блока 29 содер10

1520

998182

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

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

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

В режиме записи информации (фиг.З) п-разрядный код записываемого слова подается на входы 7 устройства, на входы 8 - нулевой пoтeнц aл, а на входы 46 - код операции записи. Опе- записи длится два такта. В первом такте единичные сигналы формиру25 ются на выходах 30, 34-37, 39, 40 блока 29 управления, по которым осуществляется ассоциативный опрос первого 1 и второго 2 блоков памяти соответственно старшей и младшей частя30 ми записываемого слова, в результате чего единичньм сигнал формируется на одном из выходов блока 1 и на одном из выходов блока 2. В соответствую- mjie разряды индексных регистров 10, 18 по сигналу с выхода 34 блока 29 производится запись единицы, свиде тельствующей о наличии записываемого слова в запоминающем устройстве. Сигналами с выходов 35 и 37 блока 29 производится запись единицы в регистрах 11 и 19. Поскольку в регистре 11 оказывается записанной только одна единица, блок 12 анализа многократных совпадений формирует на своих выходах код, аналогичный подаваемому на его вход, т.е. код, содержащий одну единицу, позиция которой определяется кодом, поданным на входы 7. Указанным кодом выбирается одна из строк блока 14, которая по сиг50 налу с выхода 30 блока 29 считывается на информационные выходы блока 14 и поступает на входы соответствукяцих элементов ИЛИ 22 и И 23. Считываемая из блока 14 строка представляет со35

40

45

строка представляет

.- oi -i

бои кодовое слово длиной 2 разрядов, причем единица в этогч кодовом слове соответствует хранению в запоминающем устройстве слова, старшир

313

разряды которого соответствуют адресу строки, в которой находится кодовое слово, а младшие разряды которог соответствуют номеру разряда, в котором записана единица. Например, при хранение трех слов 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 элементы И 21 и поступает на первые входы элементов ИЛИ 20, на другие входы которого поступает код, явля- кяцийся конъюнкцией кодового слова, считываемого из блока 14, и слова, считываемого с выходов регистра 19 (упомянутая конъюнкция формируется на выходах элементов И 23), так, что на выходах элементов ИЛИ 20 формируется код, идентичный коду, формируемому на выходах элементов ИЛИ 22, Этот код по сигналу с выхода 39 блока 29 записывается в регистр 25 и поступает на входы элемента ИЛИ 26. Все описанные выше операции производятся в течение первого такта. Во втором такте с выхода 31 блока 29 выдается единичный управляющий сигнал записи содержимого регистра 25 в блок 14,

В реясиме исключения информации исключаемое слово подается на информационные входы 7 устройства, на выходы 8 устройства подается нулевой потенциал, а на вход 46 блока 29 подается код операции исключения, по которому с приходом очередного тактового импульса на вход 53 блок 29 осу

0

5

8

5

0

5

0

5

0

5

18

ществляет вьщачу последовательности управляющих сигналов (фиг.4), инициирующих выполнение процедуры исключения слова, которая длится либо два,- либо три такта. В течение первого такта вьдаются сигналы с выходов 30, 35-37, 39, 41 блока 29. Аналогично, как в описанном выше процессе записи, производится считывание кодового слова из блока 14 и формирование кода на выходе регистра 19, Последний из упомянутых кодов инвертируется элементами НЕРАВНОЗНАЧНОСТЬ 24 (на входы которых подается единица с выхода 41 блока 29) и поступает, на один из выходов элементов И 23, на другие входы которого подается кодовое слово с выходов блока 14 так, что на выходах элементов И 23 формируется скорректированное кодовое слово, идентичное считанному с блока 14 во всех разрядах за исключением одного, в котором записывается нуль (указанный разряд соответствует разряду, отмеченному единицей в коде, считываемом с выходов регистра 19). Например, если, в условиях приведенного вьш1е примера исключается слово 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.

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

513998186

ЛОМ, если осуществляется мяскирова-блока 29 фиксирует на регистре 25, ние младших разрядов, то время запи-Все описанные Bbmie процедуры проис- си (исключения) не изменяется походят в течение первого такта, сравнению со временем, потребным для Операции, проводимые во втором записи (исключения) одного числа. Ее-такте, зависят от сигнала, снимаемо- ли осуществляется маскирование стар-го на вход 45 блока 29 с выхода эле- ших разрядов, то время записи (исклю-мента ИЛИ 26. Если упомянутьп сигнал чения) увеличивается, а сама записьимеет единичньв1 уровень (такт I, осуществляется последовательно, пу- д фиг.5), то блок 29 формирует сигналы тем поочередной коммутагщей блокомна выходах 32, 38, по которым блок 12 анализа многократных совпадений27 формирует на своих выходах код, на входы блока 1А един1гчньк сигналовимеющий одну единицу, положение кото- с выходов блока 1.рой соответствует первой единице ко- В режиме простого маскированного да, зафиксированного на регистре 25. поиска код признака опроса поступаетУказанный код поступает на адресные через входы 7 на регистры 3, 5 приз-входы блока 2, в то время как код с нака опроса, а маска заносится поблока 12 совпадений поступает на ад- входам 8 на регистры 4, 5 маски. Наресные входы накопителя блока 1, с вход 46 подается код операции просто- 2Q информационных выходов блоков 1, 2 го маскированного поиска, по которо-под действием единичного сигнала с му блок 29 с приходом очередного так-выхода 32 блока 29 на регистры 15, тового импульса формирует последова-28 и далее на выходы 16 устройства, тельность управляющих сигналовСчитывается первое слово, отвечающее (фиг.5), инищшрующих процедуру поис- 25 критерию поиска. Считьшание слова ка, которая длится 2 тактов при мае-на выходы 16 стробируется сигналом кировании г старших разрядов и р так-на выходе 42 блока 29. Сигналом с тов, при маскировании младших разря-блока 27 разряд регистра 25 обнуля- дов (р - количество слов, хранящих-ется и анализируется следующий раз- ся в запоминающем устройстве, отве- -jo регистра 25. Описанньп выше про- чающих критерию поиска). Процесс по-цесс при этом повторяется столько иска начинается вьщачей блоком 29тактов, сколько единиц содержится в единичных сигналов с вькодов 35, 37,коде, хранящемся в регистре 25 до по которым производится ассоциативныйего обнуления (на временной диаграм- опрос блоков 1,2с фиксацией резуль-ме, приведенной на фиг.5 число таких татов опроса на регистрах 11, 19 со-тактов равно трем) При появлении ответственно В этом же такте форми-нулевого сигнала на входе 45 блока руются единичные сигналы на выходах29 последний с приходом очередного 36, 30, по которым блок 12 формируеттактового импульса (такт V на фиг.5) на своем выходе код, содержащий ров-формирует единичные сигналы на выхо- но одну единицу, соответствующую пер-дах 30, 36, 39, под действием которых вой из единиц, зафиксированных на ре-блоком 12 вьделяется очередная едини- гистре 11. Указанный код поступаетца, производится cчиtывaниe из блока на адресные входы блока 14, с кото- 14 очередного слова, которое конъюнк- рого по сигналу с вьсхода 30 блокатируется с кодом, поступающим с вы- 29 считывается кодовое слово. С вы-ходов регистра 19 и записывается в ходов 40, 41 блока 29 снимаются сиг- , регистр 25. С приходом очередного налы нулевого потенциала, которымитактового импульса начинается анализ закрываются элементы И 21 и на выходеединиц, записанных в регистре 25 элементов НЕРАВНОЗНАЧНОСТЬ 24 форми-(такты VI, VII на фиг„5). Описанный руется код, идентичный снимаемому процесс продолжается до тех пор, по- с выходов регистра 19, который посту-ка на входе 44 блока 29 не появится пает на одно из выходов элементов Инулевой сигнал, свидетельствуниций 23, на другие входы которых поступаето том, все единицы из регистра 11 считанное из блока 14 кодовое словообработаны. Блок 29 вьц.ает сигнал так, что на выходах элементов И 23 конца операции с выхода 43. и ИЛИ 20 формируется код, соответст-Формула изобретения вующий кoнIJЮикIq и указанных выше ко- Ассоциативное оперативное запоми- дов, который сигналом с выходя 3 нающве устройство, содержащее блок

71

оперативной памяти, первьпЧ и второй регистры признака опроса, первьв и второй регистры маски, первый и второй регистры числа, первую, вторую и третью группы элементов И, первую группу элементов Н1Ш, первый элемент ИЛИ и блок управления, причем входы регистров признака опроса и входы регистров маски являются соответст- венно информационными и маскирующими входами устройства, выходы регистров числа являются информационными выходами устройства, выходы элементов И третьей группы соединены с первыми входами элементов И первой группы, первый и второй выходы блока управления соединены соответственно с входами считьгоания и записи блока оперативной памяти, третий пыход бло- ка управления подключен к входам приема регистров числа, отличающееся тем, что, с целью повьше- ния быстродействия устройства, в нег введены первьй и второй ассоциатив- ные блоки постоянной памяти, первый и второй индексные регистры, первый, второй и третий буферные регистры, первый и второй блоки анализа многократных совпадений, группа элементов НЕРАВНОЗНАЧНОСТЬ, вторая группа элементов ИЛИ, четвертая группа элементов И и второй элемент ИЛИ, причем выходы первого и второго регистров признака опроса и выходы первого и второго регистров маски подключены соответственно к признаковым и маскирующим входам первого и второго ассоциативных блоков постоянной памяти информационные вьсходы которых соединены с информационными входами первого и второго регистров числа соответственно, выходы результатов поиска первого и второго ассоциативных блоков постоянной памяти подключены к первым входам элементов И первой и второй групп соответственно и соединены с информационными входами первого и второго индексных регистров соответстве П{о, выходы которых подключены к вторым входам элементов И первой и второй групп соответственно выходы элементов И первой группы соединены с информа1Д онными входами первой группы первого буферного регистра, информаштонные входы второй груп- пы и выходы которого соединены соот- ветственк) с пьь(1ламя тгервой группы и инфгфмаииимимм пходлг-п первого

в

98

IQ 15 о 25 jg

35

0

5

0

188

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

29

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

4 5

фуг. 2

Фиг

Я1

,. kikiki

п п п п л п (си

Фиг

Я1

a

А

t t t

Фиг 5