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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХ РЕСПУБ 15/ Я)4 С ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ЗОБРЕТЕН ЛЬСТВУ АВТОРСКОМУ С 89513/24-24.12.87. Бюл. Иевский политехническ50-летия Великой Окстической революцииИ.Корнейчук, А,П,МарМарта Зеебауэр (НП)1.327 (088.8) инсти ьс вски 56) Автор 493165,Авторск 978197, зг а ззкизу(21) 4 (22) 1 (46) 3 (71) Ки тут им социал (72) В (811) и (53) 6 кое свидетельство СССРкл. С 11 С 15/00, 1975. е свидетельство СССРкл, С 11 С 15/00, 1981.(54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО(57) Изобретение относится к вычислительной технике, в частности кустройствам хранения информации цифровых вычислительных систем с возможностью параллельной обработки информации. Цель изобретения - повышениебыстродействия устройства при выполнении процедур поиска экстремумовили ближайшего большего (меньшего) кзаданному в ассоциативной памяти,построенной на основе модулей памяти с произвольным доступом. Ассоциа1363307 5 10 1 Г 20 30 тивное оперативное запоминающее устройство содержит коммутатор 1, блок 11 памяти, регистр 3 числа, регистр 9 маски, индексный регистр 13, блок 7 модификации признака поиска, блок 16 управления, элементы И 5, элемент ИЛИ 14, элемент НЕ 15, элементы НЕРАВНОЗНАЧНОСТЬ 6. Сущность работы устройства состоит в том, что в блоклч оперативной памяти объемом 2 (и разрядность чисел) записывается инИзобретение относится к вычислительной технике, в частности к устройствам хранения информации,и может,быть использовано в цифровых системах параллельной обработки информации.Цель изобретения - повышение быстродействия устройства,На Фиг,1 представлена структурнаясхема ассоциативного оперативноГозапоминающего устройства; на Фиг.2 -структурная схема блока модификациипризнака поиска; на Фиг.З - структурная схема блока управления (вариант выполнения); на фиг. 4 - граф"схема алгоритма записи информациив у 5:тройство; на Фиг,5 - граф-схемаалгоритма стирания информации; нафиг, 6 - граф-схема алгоритма ассо-циативного поиска по совпадению;на фиг.7 - граф-схема алгоритма поиска экстремума; на Фиг.8 - графсхема алгоритма поиска ближайшего кзаданному.Ассоциативное оперативное запоминающее устройство (Фиг.11 содержиткоммутатор 1, входами первой группыкоторого являются информационныевходы 2-2 устройствар регистр 3числа, выходы которого являются информационными выходами 4,-4, устройства, элементы И 5, элементы НЕРАВНОЗНАЧНОСТЬ бр блок 7 модификациипризнака поиска, входы которого подключены к выходам 8,-8 р, регистра 9маски, а выходы 10, "10, связаныс адресными входами блока 11 памяти,Выходы 12 -12 р, индексного регистра13 подключены к одним из входов элеформация о наличии заносимого в память слова с учетом маскирования группразрядов. Указанный метод записи позволяет осуществлять маскированныйпоиск (для определенных ограниченных видов маски) за один цикл обращения к памяти произвольного доступа,Применяемых видов масок достаточнодля ассоциативного нахождения экстремума и поиска ближайшего к заданномуо 8 ил,ментов И 5 и элементов НЕРАВНОЗНАЧНОСТЬ 6. Устройство также содержитэлемент ИЛИ 14, элемент НЕ 15 и блок16 управления.,Блок 16 имеет выходы17-23, Устройство имеет выход 24"Положительный результат поискаивыход 25 "Отрицательный результатпоиска". Блок 16 имеет также выходы26-31. Устройство содержит входы 3237 соответственно. "Запись", "Стирание" "Экстремум", "Ближайший к признаку поиска", "Максимум-минимум","Равенство", Блок 16 управления содержит входы 38 и 39 анализа соответственно прямого и инверсного значениймладшего разряда поиска и вход 40результата поиска. Блок 7 (фиг.2) содержит группы элементов И 41, элементы И 42, элементы НЕ 43, элементы ИЛИ 44.Блок 16 управления может быть выполнен, например, в виде микропрограммного устройства управления см.фиг.З) и содержит блок 45 постоянной памяти начальных адресов микропрограммр блок 46 элементов ИЛИ, счетчик 47 адреса микрокоманд,блок 48 постоянной памяти микропрограмм, регистр 49 микрокоманд, муль-. типлексор 50 условий ветвления микропрограмм, элемент И 51, элемент ИЛИ 52, вход 53.Устройство работает следующим образом.При записи слова в блок 11 памяти оно подается на входы 2 устройства, а на вход 32 "Запись" подается единичный потенциал, под действием которого блок 16 управления форжругистра 9 маски заполняются нулями.Например, при п=8 код маски в циклезаписи меняется, образуя последовательность кодов: 11111111, 11111110,11111100 10000000, 00000000, Сизменением маски п раэ меняется модифицированный код опроса на выходах10, образуя последовательность адре 10 сов блока 11 памяти, по которым осуществляется запись единицы,В режиме стирания слова из запоминающего устройства единичный сигнал подается на вход 33 устройства,15 под действием этого сигнала блок 16управления формирует последовательность сигналов, реализующих процессстирания слова, подаваемого на информационные входы 2 устройстваИ (фиг.5), Указанная последовательностьначинается выдачей блоком 16 управления единичного сигнала с выхода 26,по которому стираемое слово с входов2 через коммутатор 1 записывается в25 регистр 3. Единичным сигналом с выхода 31 блока 16 управления все разряды регистра 9 маски устанавливаются в единицу, а единичным сигналом свыхода 21 блока 16 управления всеЗО разряды индексного регистра 13, кроме п-го, в который записывается единица, устанавливаются в нуль. Процессстирания слова состоит в записи нулей в ячейки, единицы в которых отраЗ 5 жали факт хранения только данногочисла, Как следует из описания процесса записи, единица, записанная вячейках, адреса которых начинаютсяс нуля, свидетельствует О хранении40 в устройстве числа, совпадающего скодом, следующим в адресе после первого нуля, Соответственно, каждайуказанная ячейка соответствует только одному информационному слову. В45 то же время ячейки, номера которыхначинаются с комбинации 10, соответствуют двум числам, Отличающимсяв младшем разряде, Ячейки, номеракоторых начинаются с комбинации 110,50 соответствуют четырем числам, отличающимся в двух, младших разрядах,и т.дПри стирании числа обнулениеячеек производится только тогда, когда единица в данной ячейке обусловле 55 на наличием В памяти тОлькО данногочисла, В первом такте операции стира"ния по адресу, определяемому модифицированным кодом опроса, при установленных в единицу всех разрядах ре 3 13 ет последовательность управляющих сиг налов (Фиг,4), В частности блок 16 управления Формирует единичный сигнал на выходе 31, который устанавливает все разряды регистра 9 маски в единицур а нулевой сигнал на выходе 26 управляет прохождением информационного слова с выходов 2 через коммутатор 1 на регистр 3 числа. С прямых выходов регистра 3 записываемое слово поступает на один из входов 4 блока 7, на другие входы которого поступает и-разрядный код с регистра 9 маски, а на выходе 10 которого формируется (и+1)-разрядный модифицированный код опроса, причем последний Формируется следующим образом. код маски состоит из группы единиц, заиииаююих С стариих Разрядов тСЕ О,п 1) модифицированный код опроса имеет в своем г-м разряде нуль (г=й+1), в разрядах с номерами, меньшими г, т.е, в разрядах с 1-го по (т)-й, единицы, в разрядах с(г+1)-го.по (и+1)-й - с старших разрядов немодифицированного кода опроса (кода, подаваемого на входы блока 7) . Например, если код маски имеет внд 11110000 (п=8, =4), а код на регистэ 6 3 - 11001010, то г=5, модифицированный код опроса имеет вид 111101100; если код маски имеет вид 00000000, то модифицированный код опро са будет иметь вид 011001010 (г =1, С = О). Модифицированный код опроса с выхода блока 7 поступает на адресные входы блока 11 памяти. Сигнал управления записью поступает в виде единичного сигнала с выхода 17 блока 16 управления на вход записи"чтения блока 11 памяти, на инфор" мационный вход которого единичный сигнал поступает с выхода 27 блока 16 управления. Запись слова состоит в записи единиц в п ячеек блока 11 памяти, адреса которых однозначно определяются записываемым словом, Соответственно, процесс записи длится и тактов, причем в каждом такте производится сдвиг влево на один разряд содержимого регистра 9 маски (первоначально все разряды регистра 9 сигналом с выхода 31 блока 16 управления устанавливаются в единицу) . Сдвиг влево осуществляется под действием единичного сигнала с выхода 29 блока 16 управления, При сдвиге освободившиеся разряды ре 6330745 13гистра 9 маски в блоке 11 памяти за"писывается нуль. В следующем тактенулевым сигналом с выхода 26 блока16 управления в регистр 3 записывается исключаемае слово, и-й разрядкоторого инвертирован поразряднымсложением по модулю два в элементахНЕРАВНОЗНАЧНОСТЬ б содержимого регистра 3 и индексного регистра 13,все разряды которого, кроме и-го,обнулены, формируемым в этом случаемодифицированным кодам опроса производится опрос соответствующей ячейки блока 11 памяти: если в этой ячей"ке записана единица, то процесс стирания на этом завершается, а если -нуль, то сигналами с выходов 29 и23 блока 16 управления производитсясдвиг влево соответсвенно регистра9 маски и индексного регистра 13 сзаполнением кулями освободившихсяразрядов, По адресу, определяемомумодифицированным кодом опроса, вблоке 11 памяти записывается нуль,затем по способу, описанному вьппе,инвертируется (и)-й разряд регистра 3, и соответствующим модифицированным кодом опроса, выбираемым вкачестве адреса блока 11 памяти, производится опрос соответствующейячейки блока 11 памяти. Если в упомянутой ячейке записана единица, топроцесс стирания заканчивается, аесли нуль - то производится сдвиговлево регистра 9 маски и индексногорегистра 13, и процесс исключенияпродолжается по способу, описанномувьппе,При поиске слова в предлагаемомустройстве по совпадению (см.фиг.б)единичный сигнал подается на вход37 устройства, который инициируетвыдачу блоком 16 управления единичного сигнала с выхода 26 на коммутатор1, под действием которого слово свходов 2 устройства записывается нарегистр 3 единичными сигналами с выходов 17 и 31 устанавливаются в единицу все разряды регистра 9 маски иинициируется считывание иэ блока11 памяти содержимого ячейки, адрескоторой задается модифицированным. кодам опроса, состоящим в укаэанномрежиме поиска иэ нуля в старшем разряде и кода слава в разрядах с второго по (и+1)-й, Если в соответствующей ячейке блока 11 памяти записанаединица, то единичный сигнал Форми 633076руется на выходе 24 устройства, впротивном случае единичный сигналформируется на выходе 25 устройства.В режиме поиска максимального(минимального) числа иэ хранящихся вассоциативном оперативном запоминающем устройстве подается единичныйсигнал на вход 34 и единичный (нулевой) сигнал, - на вход 36, причем сиг.нал, подаваемый на последний вход,определяет направление поиска; приединичном потенциале на входе 36осуществляется поиск максимально го, а при нулевом потенциале навходе 36 - поиск минимального среди записанных в устройстве чисел .Под действием упомянутых внешнихуправляющих сигналов блок 16 управ ления формирует последовательностьуправляющих сигналов, обеспечивающихвыполнение процедуры поиска экстремума (см.фиг.7). Сигналами с выходов20 и 19 (18) блока 16 управления ус танавливаются в единицу первые разряды индексного регистра 13 и регистра 9 маски, все остальные разряды регистров 13 и 9 устанавливаются в нуль; все разряды регистра 3 ЗО устанавливаются в единицу (нуль) .Производится считывание информациииэ блока 11 памяти по адресу, опреде-,ляемому модифицированным кодом опроса: если по данному адресу в блоке З 5 11 памяти записан нуль (соответствует отсутствию чисел с единицей (нулем) в старшем разряде), то сигналомс выхода 26 блока 16 управления нарегистр 3 с выходов элементов НЕРАВ 4 О НОЗНАЧНОСТЬ 6 через коммутатор 1 за"писывается код, ранее хранившийся нарегистре 3, но с инвертированным старшим разрядом, если по упомянутомувыше адресу в блоке 11 памяти запи сана единица (соответствует наличиюхотя бы одного числа среди хранящихся в устройстве с единицей в старшемразряде), то цикл инвертирования отдельного разряда регистра 3 опуска ется, Затем по сигналам с выходов 28,22 блока 16 управления производитсясдвиг вправо содержимого регистра 9маски (с заполнением освободившегося разряда единицей) и индексного ре гистра 13 (с заполнением освободивгшегося разряда нулем), Описанныйвьппе процесс повторяется и раз, пос"ле чего в регистре 3 фиксируетсямаксимальное (минимальное) иэ чисел, 713 которое может быть считано с выходов 4 устройства при появлении единичного сигнала на выходе 24 устройства.В режиме поиска ближайшего большего (меньшего) к заданному из чисел, хранящихся в устройстве, единичный сигнал подается на вход 35 и соответствующий потенциал (при поиске ближайшего большего - Единичный, а при поиске ближайшего меньшего - нулевой) подается на вход 36, эти сигналы инициируют выдачу блоком 16 управления последовательности управляющих сигналов, обеспечивающих почск ближайшего к заданному (фиг,8) которое подается на входы 2 устройства, В соответствии с упомянутым алгоритмом блок 16 управления формирует единичные сигналы на выходах 21,26,31, которыми заданное слово с входов 2 через коммутатор 1 записывается в регистр 3, и-й разряд индексного регистра 13 устанавливается в единицу, а все остальные его разряды - в нуль, все разряды регистра 9 маски устанавливаются в единицу. Одновременно нулевым сигналом с вы" хода 17 блока 16 управления производится считывание иэ блока 11 памяти информации на вход 40 блока 16 управления (на адресные входы 10 блока 11 памяти подается код, состоящий из нуля в старшем разряде и кода заданного слова в разрядах с второго по (и+1)-й). Если с выхода блока 11 памяти снимается сигнал единичного потенциала, то блок 16 управления формирует единичный сигнал на выходе 24 устройства, Укаэанная ситуация имеет место, если в устройстве хранится число, совпадающее с заданными. В противном случае, т.е. если с блока 11 памяти считывается нуль, блоком 16 управления анализируются сигналы на входах 38 и 39, предсталяющие прямое и инверсное значения младшего разряда заданного слова, Если младший разряд заданного слова равен нулю (единице), то с выхода 26 на коммутатор 1 подается сигнал, открывающий коммутатор 1, так что в регистр 3 нерезаписывается заданное слово с инвертированным младшим разрядом, после чего опять производится опрос блока 11 памяти, Если в соответствующей ячейке блока 11 памяти записана единица, то микропрограмма продолжа 63307 8ется с метки 1 (см,фиг,8), Иначе, как и в случае, когда младший разряд заданного слова равен единице (нулю), 5производится сдвиг (сигналами с выходов 29 и 23 блока 16 управления) влево содержимого регистров 9 и 13, описанная процедура продолжается до тех пор, пока не будет осуществлен 10 переход по метке 1, либо не будетсформирован сигнал с выхода 25 (этот сигнал формируется в том случае, если в режиме поиска ближайшего большего (меньшего) к заданному в запоми нающем устройстве хранятся числа,каждое из которых меньше (больше) заданного). Микропрограмма, начинающаяся с метки 1, реализует поиск минимального(максимального) из множест ва чисел, найденныхна описанном выше этапе поиска, На каждом шаге этой процедуры сдвигается вправо содержимое регистров 9 и 13 (сигналами с выходов 22 и 28 блока 16 управле ния) и производится опрос соответствующей ячейки блока 11 памяти.Если при опросе с выходов блока 11 памяти считывается нуль, то производится инвертирование разряда реЗ 0 гистра 3, причем позиция инвертируемого разряда определяется положением единицы в индексном регистре 13. формула изобр етения 35Ассоциативное оперативное запоминающее устройство, содержащее блокпамяти, блок управления, регистрчисла, регистр маски, индексный ре гистр и блок модификации признакапоиска, причем выходы регистра числа являются информационными выходами устройства и подключены к информационным входам блока модификации 45 признака поиска, управляющие входыкоторого соединены с выходами регистра маски, выходы блока модификации признака поиска соединены садресными входами блока памяти, вход 50- записи-чтения которого соединен спервым выходом блока управления, второй и третий выходы которого подключены соответственно к входу установки в "1" и входу установки в "О"555 регистрачисла, о тли ч ающе ес я тем, что, с целью повышениябыстродействия устройства, в неговведены коммутатор, элементы И, элементы НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИи элемент НЕ, причем информационныевходы первой группы коммутатора являются входами признака поиска устройства, информационные входы второй группы коммутатора подключены квыходам элементов НЕРАВНОЗНАЧНОСТЬвыходы коммутатора соединены с входами регистра числа, выходы которогоподключены поразрядно к первым входам элементов И и элементов НЕРАВНОЗНАЧНОСТЬ, выходы индексного регистра соединены поразрядно с вторымивходами элементов И и элементов НЕРАВНОЗНАЧНОСТЬ, выходы элементов Ичерез элемент ИЛИ подключены к входу элемента НЕ, четвертый выходблока управления соединен с управляющим входом коммутатора, с пятогопо восьмой выходы блока управленияподключены соответственно к входуустановки в "1" старшего разряда ив "О" всех остальных разрядов индексного регистра, к входу установки в "1" младшего разряда и в "О"всех остальных разрядов индексногорегистра, к входу управления сдвигом вправо индексного регистра ик входу управления сдвигом влево ин-дексного регистра, девятый и десятый выходы блока управления являются соответственно выходом "Положительныйрезультат поиска" и выходом Отрицательный результат поиска" устройства, одиннадцатый выход блока управления подключен к информационномувходу блока памяти, с двенадцатогопо пятнадцатый выходы блока управле ния подключены соответственно к входу управления сдвигом вправо регистра маски, к входу управления сдвигом влево регистра маски, к входу установки старшего разряда в и в 15 "О" всех остальных разрядов регистрамаски, к входу установки в "1" регистра маски, с первого по шестойвходы блока управления являются соответственно входами "Запись", "Стира ние", "Экстремум", "Ближайшее кпризнаку поиска", "Максимум-минимум"и "Равенство" устройства, выходы элемента ИЛИ и элемента НЕ подключенысоответственно к входу анализа прямого значения младшего разряда признака поиска и входу анализа инверсногозначения младшего разряда признакапоиска блока управления, выход блокапамяти соединен с входом результата ЭО поиска блока управления.1363307 Составитель В,РудаРедактор Л.Веселовская Техред Л.ОлийныкЮ йа Е 4 В орректор И.Муска аказ 6369/4 одписное Производственно-полигра 4 аческое предприятие, г.ужгород, ул.Проектная 5 Тираж 588ВНИИПИ Государственнпо делам изобрет 13035, Москва, Ж, Ра о комитета СССРний и открытий ская наб., д.4/5