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

СОЮЗ СОВЕТСКИХСОЦИА ЛИСТИЧЕСКИХРЕСПУб ЛИК 981/00 1511 4 КОМИТЕТ СССРЕНИЙ И ОТКРЫТИИ ГОСУДАРСТВЕНН ПО ДЕЛАМ ИЗО Е ИЭОБРЕТЕНИСВИДЕТЕЛЬСТВУ ОПИСА ТОРСКОМ 20.П.СидоренЧернов ельство ССС 15/00) 1978 ьство СССР15/00, 198 РАТИВНОЕ ЗАП 4) АССОЦИАТИВНОЕ ОНАКЦЕЕ УСТРОЙСТВО 57) Из льной ычислиуст" и моых вы- аллели- ормание ойство тся к ности( обретение относ те технике, в час ройствам хранения инфо жет быть использовано числительных системах ванием процессов обраб ции. Цель изобретения быстродействия устройс мации, цифро расп тки и повыш в. Ус(56) Авторское свидеУ 604033, кл, С 11 САвторское свидетеВ 978197, кл. С 11 С содержит первыи и второй ассоциативные блоки постоянной памяти, первыйи второй регистры признака опроса,первый и второй регистры маски, первую, вторую, третью и четвертую группыэлементов И, первый и второй индексныерегистры, первый, второй и третийбуферные регистры, блок оперативнойпамяти, первый и второй регистры числа, первый и второй элементы ИЛИ,первую и вторую группы элементов ИЛИ,первый и второй блоки анализа многократных совпадений, элементы НЕРАВНОЗНАЧНОСТЬ и блок управления. В устройстве существенно повьппается скорость маскированного поиска за счетвыполнения операций маскирования вассоциативных блоках постоянной памяти по сравнению с перебором, реализуемым в блоке оперативной памятипри ассоциативном маскированном поиске, 5 ил.Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в цифровых си 5стемах с распараллеливанием процессов обработки информали,11 ель изобретения - повышецие быстродействия устройства,На фиг.1 представлена структурнаясхема ассоциативного оперативного запоминающего устройства; на фиг,2структурцая схема одного иэ возможных вариантов построения блока микропрограммного управления; ца фиг,3-5 - 15временные диаграммы процессов соответственно записи (фиг.3), исключения (фиг,4) и простого маскированного поиска (фиг,5).Ассоциативное оперативное запоминающее устройство (фиг,1) содержитпервый 1 и второй 2 ассоциативныеблоки постоянной памяти, первые регистр 3 признака опроса и регистр 4маски, вторые регистр 5 признака опроса и регистр 6 маски. Входы регистров 3 и 5 являются соответственностаршими 7 7 п 12 и младшими 7 ьг7 информационными входами устройства (и - разрядность чисел) . Входырегистров 4 и 6 являются соответственно старшими 8, - 8 1 и младшими8 1 , - 8 маскирующими входами устройства, Устройство также содержитпервую группу элементов И 9 - 9(ш"2 ), первый индексный регистр012 3510, первый буферный регистр 11, первый блок 12 анализа многократных совпадений, первый элемент ИЛИ 13, блок14 оперативной памяти, первый регистр15 числа, выходы которого являютсястаршими информационными выходамиустройства 16, - 1612, вторую группу элементов И 17, - 17 , второй индексный регистр 18, второй буферныйрегистр 19, первую группу элементов45ИЛИ 20- 20, третью группу элементов И 21 - 21 , вторую группу элементов ИЛИ 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 объемом ш п/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 строка представляет соибой кодовое слово длиной 2 разрядов, причем единица в этом кодовом слове соответствует хранению в запоминающем устройстве слова, старш510 15 20 25 ЗО 35 40 45 50 55 разряды которого соответствуют адресу строки, в которой находится кодовое слово, а младшие разряды которого соответствуют номеру разряда, в котором записана единица. Например, при и 8 хранение трех слов 10010000, 10011111, 10010011 соответствует тому, что в строке 9(1001) блока 14 хранится кодовое слово, имеющее вид 1000000000001001, т.е. единицы зафиксированы в разрядах 0(0000), 3(0011), 15(1111). С выходов регистра 19 поступает код, содержащий только одну единицу. Запись состоит в том, чтобы записать указанную единицу в кодовое слово, считываемое иэ блока 14. Если в условиях приведенного выше примера записывается еще одно слово, например 10011001, то код, считываемый с регистра 19 имеет вид 0000001000000000 (единица записана в 9-ом (1001) разряде), а скорректированное с учетом записи упомянутого слова кодовое слово должно иметь вид 100000 1000001001, Код, считываемый с элементов ИЛИ 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), инициирующих процедуру поисгка, которая длится 2 тактов при маскировании г старших разрядов и р тактов, при маскировании младших разря" дов (р - количество слов, хранящихся в запоминающем устройстве, отвечающих критерию поиска). Процесс поиска начинается выдачей блоком 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 формируется код, соответствующий конъюнкции указанных ньппе кодов, который сигналом с выхода 3999818 6 5 10 15 20 25 30 35 40 45 50 55 блока 29 фиксирует на регистре 25,Все описанные ньше процедуры происходят в течение первого такта,Операции, проводимые во второмтакте, зависят от сигнала, снимаемого на вход 45 блока 29 с выхода элемента ИЛИ 26. Если упомянутьп 1 сигналимеет единичньп уровень (такт 1,фиг.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 последний с приходом очередноготактового импульса (такт Ч на фиг.5)формирует единичные сигналы на выходах 30, 36, 39, под действием которыхблоком 12 ныделяется очередная единица, производится счиТывание из блока14 очередного слова, которое конъюнктируется с кодом, поступающим с выходов регистра 19 и записывается врегистр 25. С приходом очередноготактового импульса начинается анализединиц, записанных н регистре 25(такты Ч 1, Ч 11 на фиг 5), Описанныйпроцесс продолжается до тех пор, пока на входе 44 блока 29 не появитсянулевой сигнал, свидетельствующийо том, все единицы из регистра 11обработаны. Блок 29 выдает сигналконца операции с выхода 43.Формула и э о б р е т енияАссоциативное оперативное запоминающее устройство, содержащее блок1399818 8 оперативной памяти, первый и второйрегистрь признака опроса, ервь ивторой регистры маски, первый и второй регистры числа, первую, вторуюи третью группы элементов И, первуюгруппу элементов И 1 П 1, первый элементИЛИ и блок управления, причем входырегистров признака опроса и входырегистров маски являются соответственно инФормационными и маскирующимивходами устройства, выходы регистровчисла являются информационными выходами устройства, выходы элементов Итретьей группы соединены с первымивходами элементов И первой группы,первый и второй выходы блока управления соединены соответственно свходами считывания и записи блокаоперативной памяти, третий выход блока управления подключен к входам приема регистров числа, о т л и ч а ю - щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены первый и второй ассоциативные блоки постоянной памяти, первый и второй индексные регистры, первьй, второй и третий буферные регистры, первый и второй блоки анализа многократных совпадений, группа элементов НЕРАВНОЗНАЧНОСТЬ, вторая группа элементов ИЛИ, четвертая группа элементов И и второй элемент ИЛИ, причем выходы первого и второго регистров приэйака опроса и выходы первого и второго регистров маски подключены соответственно к признаковым и маскирующим входам первого и второго ассоциативных блоков постоянной памяти,информаронные вьходь которых соединены с информационными входами первого и второго регистров числа соответственно, выходы результатов поискапервого и второго ассоциативныхблоков постоянной памяти подключенык первым входам элементов И первойи второй групп соответственно и соединены с информационными входами перпервой и второй групп соответственно,выходы элементов И первой группы сое" динены с информаонными входами перза многократных совпадений соединены55 с седьмым вьжодом блока управления,вой группы первого буферного регистра, иформа 1 роье входы второй группы и вьжоды которого соединены соответствеии 1пь 1 ра"и первой группыи информаци 1 иивп пхолач первого вого и второго индексных регистровсоответственно, выходы которых подключены к вторым входам элементов И блока анализа многократных совпадений, вьжоды второй группы которого соединены с входами первого элемента И 1 П 1, адресньпи входами первого ассоративого блока постоянной памяти и адресьми входами блока оперативной памяти, вьжоды которого подключены к первым входам элементов ИЛИ второй группы и элементов И четвертой группы, выходы которых соединены с вторыми входами элементов ИЛИ первой группы, выходы которых подключены к информационным входам первой группы третьего буферного регистра, выходы второго буферного регистра подключены к первым входам элементов НЕРАВНО" ЗНАЧНОСТЬ и вторым входам элементовИ 1 П 1 второй группы, выходы которыхсоединены с первыми входами элементов И третьей группы, выходы элементов НЕРАВНОЗНАЧНОСТЬ соединены с вторььи входами элементов И четвертой группы, выходы элементов И второй 25 группы подключены к информационнымвходам второго буферного регистра, информационные входы второй группы третьего буферного регистра соединены с выходами первой группы второго З 0 блока анализа многократных совпадений, выходы второй группы которого подключены к адресным входам второгоассоциативного блока постоянной памяти, вьжоды третьего буферного регистра подключены к информационным вхо 35 дам второго блока анализа многократных совпадений, информационным входам блока оперативной памяти и входамвторого элемента ИЛИ, третий выход аоблока управления соединен с входамиадресного считывания первого и второго ассоциативных блоков постояннойпамяти, четвертый выход блока управления подключен к входам управлениязаписью нулей первого и второго индексных регистров, вхопь управлениязаписью единиц которых соединены спятым выходом блока управления, шестой выход которого подключен к входу управления поиском первого ассоциа 50тивного блока постояннои памяти ивходу приема первого буферного реги-.стра, установочный вход которого и управляющий вход первого блока аналивосьмой вьжор которого и дпкпюен к входу,управления поиском ятороги ассоциативного блока постоя 1 иой памяти, девя 9 13998 тый выход блока управления подключен к управляющему входу второго блока анализа многократных совпадений и установочному входу третьего буферно 5 го регистра, вход управления приемом которого соединен с десятым выходом блока управления, одиннадцатый и двенадцатый выходы блока управления подключены соответственно к вторым входам элементов И третьей группы и элементов НЕРАВНОЗНАЧНОСТЬ, тринад 18 1 Оцатый и четырнадцатый выходы блока управления являются соответственно выходами "Число найдено" и "Все числа найдены" устройства, входы "Конец обработки" и "Результат поиска" блока управления подключены соответственно к выходам первого и второго элементов ИЛИ, вход кода операции блока управления является входом режима работы устройства.1399818 зо з 1 зя зз ЗФ зз зв зк зв Токе. игл.Щ Вьаодьюл 7,и йlкаРу ф ЫХОЬ 3 Р,У 9 юоиФиг. 4 Таке, Ыфгп. юЛ ыходы И;57 ыходы ЮО,З 659 Составитель В.РудакТехред И.Ходанич едактор ВКовтун орректор Г. Решетн аказ 2671/ Типам 590 сударственного ко ам изобретений и о ва, Ж, Раушска Подписноитета СССРкрытийнаб., д, 4/5 НИИПИ Г по де035, Иос зводстненно-полиграфическое предприятие, г, Ужгород,оектная,Вход Ц ыхооь У 2 М,ФГ