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

разрядов, блоки памяти старших 11 и младших 12 разрядов, блок 14 управления,группу 5 элементов И, группу 6 элементов НЕРАВНОЗНАЧНОСТЬ, Олок памяти 19 ссылок, блок памяти 20 свободных ячеек, реверсивный счетчик 22, индексный регистр 24, элемент ИЛИ 25, элемент НЕ 26, регистр

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

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целью изобретения является упрощение устройства. Устройство содержит первый 1 и второй 21 коммутаторы, регистр числа 3, блок 7 модификации кода опроса старших разрядов, блок 27 модификации кода опроса младших разрядов, регистры маски старших 9 и младших 28 разрядов, блоки памяти старших 11 и младших 12 разрядов, блок управления 14, группу 5 элементов И, группу 6 элементов НЕРАВНОЗНАЧНОСТЬ, блок памяти 19 ссылок, блок памяти 20 свободных ячеек, реверсивный счетчик 22, индексный регистр 24, элемент ИЛИ 25, элемент НЕ 26, регистр 29 старших разрядов адреса. Работа устройства аналогична функционированию ассоциативного запоминающего устройства на основе дешифратора адреса, однако память выполняется из двух частей и вместо полного дешифратора используется двухступенчатый. 8 ил.

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

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

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

Устройство (фиг.1) содержит первый коммутатор 1, входы первой группы которого являются информационными входами 2.1-2.П устройства (где п - разрядность числа), регистр числа 3 с информационными выходами 4.1-4.П, группу 5 элементов И, группу 6 элементов НЕРАВНОЗНАЧНОСТЬ, блок 7 модификации кода опроса старших разрядов, управляющие входы которого соединены с выходами 8.1-8.n-g (где g - количество младших разрядов) регистра маски старших 9 разрядов, выходы блока 8 модификации кода старших разрядов соединены с входами адреса 10..n-g+1 блока памяти старших разрядов 11, блок памяти младших разрядов 12 с информационным входом 13, блок 14 управления с выходами записи блока 15 памяти старших разрядов, записи блока 16 памяти младших разрядов, записи блока 17 памяти ссылок и записи блока памяти 13 свободных ячеек, блок памяти 19 ссылок, блок памяти 20 свободных ячеек, второй коммутатор 21, реверсивный счетчик 22 с выходом переполнения 23, индексный регистр 24, элемент 25, элемент НЕ 26, блок 27 модификации кода

опроса младших разрядов, регистр 28 маски младших разрядов, регистр 29 старших разрядов адреса. Блок управления (фиг.1, фиг.З) имеет выходы: 30 - установка регистра числа, 31 - сброс регистра числа, 32 - запись в регистр числа, 33 - управление первым коммутатором, 34 - управление вторым коммутатором, 35-установка старшего разряда и сброс остальных разрядов, 36 установка младшего разряда и сброс остальных разрядов индексного регистра, 37, 38 - управление сдвигом влево и вправо индексного регистра, 39 -установка (п-д)-го разряда и сброс остальных разрядов индексного регистра, 40 - положительный результат поиска, 41 - отрицательный результат поиска, 42 - установка регистров 28 маски младших и старших 9 разрядов, 43 - установка старшего разряда и сброса остальных

разрядов регистров 28 маски младших и старших 9 разрядов, 44, 45 управление сдвигом вправо и влево регистра 9 маски старших разрядов, 46, 47 - управление сдвигом вправо и влево регистра 28, маски

младших разрядов, 48,49 - управление прямым и обратным счетом реверсивного счетчика 22, 50 - сброс реверсивного счетчика 22, 51 - запись в регистр старших разрядов адреса.

Блок управления (фиг.1, фиг.З) имеет входы: 52 - запись, 53 стирание, 54 -экстремум, 55 - ближайшее к заданному, 56 - максимум-минимум, 57 - равенство, 58 - начальная установка, 59,60 - анализа прямого и инверсного значений младшего разряда признака поиска, 61, 62 - первый и второй входы результата поиска, 63-66 - информационные входы (n-g)-ro, (n-g+1)-ro, первого и п-го разрядов индексного регистра.

Блок 14 управления (фиг.З) содержит блок 67 постоянной памяти начальных адресов, блок 68 элементов ИЛИ, счетчик адреса микрокоманд 69, блок постоянной памяти

микропрограмм 70. регистр микрокоманд 71, мультиплексор условий ветвления 72, элемент И 73, элемент ИЛИ 74.

Блок 7 модификации кода опроса старших разрядов и блок 27 модификации кода опроса младших разрядов представляют собой комбинационные схемы, которые могут быть, например, реализованы в соответст- вии со схемой, представленной на фиг.2 м содержат группы элементов И 75, элементы И 76, элементы НЕ 77, элементы ИЛИ 78. Применительно к блоку 7 модификации кода опроса старших разрядов К на схеме, представленной на фиг,2, равно n-g, применительно к блоку 27 модификации кода опроса младших разрядов .

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

Перед началом работы устройства выполняется цикл начальной установки, инициируемый подачей единичного потенциала на вход 58 устройства. По получении указанного сигнала блок 14 упрзпле- ния формирует последовательность сигналов, обеспечивающих заполнение всех m ячеек блока 20 памяти свободных ячеек (т - количество слов, записываемых в ассоциативное оперативное запоминаю- щее устройство).

Цикл начальной установки начинается выдачей блоком 15 управления сигнала с выхода 50, которым реверсивный счетчик 22 сбрасывается в нуль. Затем производится запись содержимого счетчика 22 через второй коммутатор 21 в ячейку блока 20 памяти свободных ячеек, адресуемых кодом с выходов счетчика 22 под действием единичных сигналов с выходов 17, 34 блока 14 управле- ния. Затем сигналом с выхода 48 блока 14 осуществляется прибавление единицы к содержимому счетчика 22 и вновь повторяются описанные выше два последних такта до тех пор, пока после m-того увеличения со- держимого счетчика 22, последний форми- руетсигнал переполнения, поступающий на вход 23 блока 14 управления и свидетельствующий о том, что цикл начальной установки завершен.

Ассоциативное оперативное запоминающее устройство позволяет реализовать следующие команды Запись слова, Исключение слова, Поиск по совпадению, Поиск экстремума, Поиск ближайшего (большего или меньшего) к заданному.

При выполнении команды Запись единичный сигнал подается на вход 52 устройства, а само слово - на входы 2 устройства. Блок 14 управления формирует последовательность сигналов в соответствии с алгоритмом, представленном на фиг.4. Выполнение команды Запись начинается выдачей блоком 14 управления единичного сигнала на выходе 42, которым

устанавливаются все разряды регистров 9, 28 маски а единицу выдарземыи одновременно единичной CHI нал с выхода 33 управ- тчвг прохождением кода записываемого слова со входов 2 через оммутатор 1 на регистр 3 числа, где по пи налу с выхода 32 блока 14 управления оно фиксируется. Одновременно формируемый на выходе 35 блока 14 управления сигнал устанавливает в единицу старший разряд и сбрасывает в нуль все остачьные разряды индексного регистра 24. С прямых выходов регистра 3 чиглд n-g старших разрядов (п - разрядность записываемых слов) записываемого слова поступают ня гервые входы 4.1-4.n-g б;.ока 7 модификации кода опроса старших разрядов, на другие которого поступает (п-д)-разрядный код с ре.тстра 9 маски сгэршш разрядов а ИР выходах 10.1-10.п- п+1 которого формирую ся (л-дН)-разряд- ный модифицированный код опроса старших разрьдоп, причем последний разряд формируется следующим образом: код маски состоит из группы единиц, занимающих т старших разрядоп t Ј {0,n-g}; модифицированный код опроса имеет в своем г-том разряде нуль ( 1), в разрядах с номерами, меньшими г т.е. в разрядах с 1-го по (г-1)-й,

-единицы, в разрядах с (г+1)-го по (п-д+1)-ый

-t старших разрядов немодифицированного кода опроса (кода, подаваемого на входы блока модификации кода опроса старших разрядов). Например если код маски имеет вид 11110000, то (, ), а код на регистре - 11001СЮ, то и модифицированный код опроса имеет вид 111101000, если код маски имеет вид 11111111, то модифи- цированный код опроса будет иметь вид 011001010 (, ). Модифицированный код опроса с выхода блока поступает на адресные входы блока 11 памяти старших разрядов. Под действием нулевого сигнала с выхода 15 блока управления в первом такте осуществляется цикл считывания из блока 11 памяти пг адресу, состоящему из нуля о старшем разряде и (п-д)-разрядного кода совпадающего с (n-g) старшими разрядами заппсывозмого слова.

Если по указанному адресу в блоке 11 п .мяти храните, единичный бит, что соответствует ситуации, когда до записи, в памяти хранились слова, совпадающие с записываемым в (n-g) старших разрядов, то оСработкз старших разрядов окончена в указанный выше адрес поступает на адресные входы блока 19 памяти ссылок. Под действием сигнала, поступающего с выхода 17 блока 14 управления на вход записи-чтения блокз 19 памяти ссылок код ссылки считывается ка регистр 29 старших разрядов адреса Дэлуе след/ег цикл записи в блок 12 памяти младших разрядов,

Если по адресу, состоящего из нуля и (n-g) старших рязрядоа записываемого слова в блоке 11 памяти старших разрядов хранится нулевой бит, то под действием нулевого сигнала с выхода 18 и единичных сигналов с выходов 17, 51, 49 блока 14 управления осуществляется считывание из блока 20 памяти кода ссылки и запись его в блок памяп 19 ссылок по адресу, опредепя- емому кодом на выходах 10 блока 7 модификации коди опроса с последующим считыванием упомянутого кода ссылки из блока памяти 19 на регистр 29 и уменьшением на единицу содержимого реверсивного 22 Считанный код ссыпки на регистр 29 .-1арлпет собой старшие разряды адреса для б/.ока 12 памяти младших расрядии

Дачес (фиг.л) ледует цикл записи старших разрядов тела в блок 1 i памяти старших рлзрт С В, j по окончании ею, как и в случае, ког ч а до записи в памя ги хранились слова, совпадающие с записываемым Q (n-g) старших рэзря in, производится запись младш- х разрядов числа в блок 12 памяти младши;, ратоядов.

Запись старших разрядов слова состоит в записи с;.иниц в (n-g) ячеек блока 11 памяти старших разряд лч, адреса которых однозначно оправляются (n-g) старшими разрядами саписываемого слова. Соответственно, процесс зтписи длится (п-д)тактов, причем в каждом гэкте производится сдвиг влево нд один разряд регистра 9 маски старших разрядов под действием единичного сигнала с выхода 44 блока 14 управления, а также сдвиг вправо индексного регистра 24 под действием единичного сигнала с выхода 38 блока 14 управления с заполнением освободившихся разрядов указанных регистров 9 и 24 нулями. С изменением маски (n-g) раз меняется модифицированный код опроса старших разрядов на выходах 10, образуя последовательность адресов, по которым в блох 1 i памяти осуществляется запись единицы. В (р.-д)-ом такте с (п-д)-го разряда индексного реестра 24 на вход 64 блока 14 управления поступает единичный сигнал, и после записи единицы в 6 ijK 11 памяти старших разрядов по эдресу, состоящему из старшего разряда записываемого слова в (п-д)-см разряде, нуля - в (n-g- 1)-ом разряде и единиц- со всех остальных разрядах, цикл записи в блоч 11 памяти заканчивается.

Запись младших разрядов с/ ова состоит е записи единиц в о ячеек 12 пзмя- ти младших разрядов, старшее разряды адресе которых однознаино определяются

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

0 такте происходит сдвиг влево на один разряд регистра 28 маски младших разрядов под действием единичного сигнала с выхода 46 блока 14 управления, а модифицированный код опроса формируется на выходах

5 блока 27 модификации кода опроса младших разрядов. По окончании процесса записи слова (на вход 66 блока 14 управления поступает единичный сигнал с младшего разряда индексного регистра 24) формиру0 ется единичный сигнап на выходе 40 блока 14 управления.

При выполнении команды Исключение слова единичный сигнал подается на вход 53 устройства, под действием которого блок

5 14 управления формирует последовательность управляющих сигналов, реализующих стирание слова, подаваемого на входы 2 устройства Алгоритм процедуры стирания представлен на фиг,5. Указанная последо0 вательность начинается выдачей блоком 14 управления единичного сигнала с выхода 33 и единичного сигнала с выхода 32, по которым стираемое слово с входов 2 через первый коммутатор 1 записывается в регистр 3

5 -мела. Единичными сигналами с выхода 42 блока 14 управления все разряды регистров 9, 28 маски устанавливаются в единицу, а единичным сигналом с выхода 36 блока 14 управления все разряды индексного регист0 ра 24, кроме младшего (п-го), в который записывается единица, устанавливаются в нуль, Процесс стирания слова состоит в записи нулей в ячейки, единицы в которых отражали факт хранения только данного

5 числа. Для этого вначале производится под действием единичного сигнала с выхода 17 и единичного сигнала с выхода 32 блока 14 управления считывание на регистр 29 из блока 19 памяти кода старших разрядов ад0 реса для блока 12 памяти младших разрядов, хранящегося по адресу, состоящему из (n-g) старших разрядов исключаемого слова. Затем выполняется операция стирания слова из блока 12 памяти младших разрядов.

5 Как следует из описания процесса записи, единица, записанная в ячейках блока 12 памяти младших разрядов, старшие разряды адреса которых совпадают с кодом ссылки (код ссылки однозначно определяется старшими разрядами числа), а младшие начинаются с нуля, свидетельствует о хранении в устройстве числа, совпадающего младшими g разрядами с кодом, следующим в адресе после указанного нуля. Соответственно, каждая указанная ячейка соответствует только одному информационному слову. В то же время ячейки, в номепэу которых после кода ссылки, упоминавшегося выше, следует комбинация 10, соответствуют двум числам, отличающимся младшем разряде и т.д. При стирании чи.ля обнуление ячеек производится только тогда, когда единица в данной ячейке обусловлена наличием Б памяти только данного числа. В первом такте операции стирания по адресу старшие разряды которого зафиксированы на регистре 29, а младшие определяются модифицированным кодом опроса, при установленных в единицу всех разрядах 28 маски младших разрядов В следующем такте сигналами с выходов 33 и 32 блока 14 управления в регистр 3 числа записывается исключаемое слово, n-ый разряд которого инвертирован подразрядным сложением по модулю два в элементах G НЕРАВНОЗНАЧНОСТЬ содержимого реш- стра 3 числа и индексного регистра 24, все разряды которого, кроме n-го обнулены. Формируемым в этом случае модифицированным кодом опроса производи гея опрос соответствующей ячейки блока 12 памяти младших разрядов. Если в этой ячейке записана единица, то процесс стирания на этом завершается, а если нуль, то сигналами с выходов 46 и 39 блока 14 управления производится сдвиг влево соответственно регистра 28 маски младших разрядов и индексного регистра 24 с заполнением нулями освободившихся разрядов. По адресу, определяемому кодом ссылки и модифицированным кодом опроса в блоке 12 памяти записывается нуль, затем по способу, описанному выше инвертируется (п-1)-ый разряд регистра 3 числа и процесс исключения продолжается по способу, описанному выше. Если в процессе стирания информации в блоке 12 памяти будет найдено слово, совпадающее с исключаемым в более чем (n-g) старших разрядах, то операция стирания заканчивается. В противном случае, по окончании процесса стирания в блоке 12 памяти под действием единичных сигналов с выходов 39 и 48 блока 14 управления производится сдвиг влево индексного регистра 24 и к содержимому реверсивного счетчика 22 прибавляется единица. Затем под действием единичного сигнала с выходов 34 и 18 блока 14 управления осуществляется запись содержимого регистра 29 старших разрядов адреса в блок 20 памяти свободных ячеек по

адресу, определяемому содержимым счетчика 22, и запись нуля в блок 11 памяти старших разрядов по адресу, состоящему из муля в старшем разряде и (n-g) старших разрядов признака опроса. Далее процесс сти- ряния продолжается в блоке 11 памяти старшмх разряде 1 чнологично процессу стирания в блоке 12 памяти младших разрядов, отличающийся тем. что в каждом такте под

0 дейстдием сигнала с оыхода 44 блока управления производится влево содержимого регистра 9 масю; старших разрядов, а адрес для блока 11 памяти старших разрядов формируется нэ выходах блока 7 моди5 фикации кода опроса старших разрядов и определяется старшими разрядами числа.

При выполнении команды Поиск по совпадению признак опроса подается на входы 2 устройства одновременно с пода0 чей единичного сигнала на вход 57 устройства, который инициирует формирование блоком 14 управления последовательности управляющих сигналов в соответствии с алгоритмом поиска, представленном нафиг.6.

5 Блок 14 управления формирует единичные сигналы на выходах 33 и 32, под управлением которых признак опроса со входов 2 записывается и на выходе 42, по которому устанавливаются в нуль все разряды регист0 ров 9 и 28 маски. Затем сигналом с выхода 15 блога управления инициируется считывание из блока 11 памяти содержимого ячейки, лдрес которой состоит из нуля в старшем разряде и (n q) старших разрядов слова 5 признака опроса. Одновременно по адресу, идентичному коду (n-g) старших разрядов признака опроса сигналами с оыходов 17 и 51 блока 14 управления производите обращение к блоку 19 памяти ссылок с фикса0 цией считанного кода на регистре 29. Если считанный из блока 11 памяти старших разрядов бит равен единице, то производится обращение к блоку 12 памяти младших раз- рчдов по адресу, состоящему из кода ссыл5 ки, зафиксированного на регистре 29 старших разрядов о.црссо, нуы и g младших разрядов npi.jHaL a опроса под действием нулевого сигнала с выхода 16 блока 14 уп- равлг-ния. Если в соответствующей ячейке

0 Стока 12 памяти младших разрядов записана единица, то единичный сигнал формируется на выходе 40 устройства, о противном случае, как и в ситуации, когда считанный из блока 11 памяти старших разрядов бит ра5 вен нулю, единичный сигнал Формируется на выходе 41 устройства.

При выполнении команды Поиск экстремума ii3 числа хранящихся в устройстве, на его вход 54 подается единичный сигнал и единичный (нулевой) сигнал - на вход 56,

причем сигнал, подаваемый на последний сход, определяет направленно поиска, при единичном сигнале на входе 56 осуществляется поиск максимального, а при нулевом поиск минимального среди записанных в устройстве чисел.

Под дейстивем этих управляющих сигналов блок 14 управления формирует последовательность управляющих сигналов, обеспечивающих выполнение процедуры поиска экстремума (фиг.7). Сигналами с выходов 35,43,30,31 блока управления устанавливаются в единицу первые разряды индексного регистра 24 и регистров маски старших 9 и младших 28 разрядов, все остальные разряды которых устанавливаются в нуль; все разряды регистра числа устанавливаются в единицу (нуль). Сначала производится цикл поиска в блоке 11 памяти старших разрядов. В первом такте производится считывание информации из блока 11 памяти старших разрядов по адресу, определяемому модифицированным кодом опроса старших разрядов. Если по данному адресу в блоке 11 памяти старших разрядов записан нуль, соответствующий отсутствию числа с единицей (нулем) в старших разрядах, то сигналами с выходов 33, 32 блока 14 управления на регистр 3 числа с выходов элементов неравнозначность 6, через коммутатор 1 записывается код, ранее хранившийся на регистре 3 числа, но с инвертированным старшим разрядом. Если по упомянутому выше адресу в блоке 11 памяти старших разрядов записана единица, соответствующая наличию хотя бы одного чиспа среды хранящихся в устройстве с единицей (нулем) в старшем разряде, то цикл инвертирования отдельного разряда регистра 3 опускается. Затем по сигналам с выходов 45 и 38 блока 14 управления производится сдвиг вправо содержимого регистра 9 маски старших разрядов, с заполнением освободившегося разряда единицей, и индексного регистра 24, с заполнением освободившегося разряда нулем. Описанный выше процесс повторяется (n-g) раз, т.е. пока на входе 65 блока 14 управления не появится единичный сигнал с (п-д+1}-го разряда индексного регистра 24. После чего по адресу, определяемому (n-g) старшими разрядами кода, сформированного в результате поиска экстремума в блоке 11 памяти старших разрядов и зафиксированного в старших разрядах регистра 3 числа, осуществляется обращение к блоку 19 памяти ссылок под действием сигнала с выхода 18 блока 14 управления. Считанный из блока 19 памяти ссылок код фиксируется на регистре 29 старших разрядов адреса и определяет значение старших разрядов адреса при поиске экстремума в блоке 11 памяти. Процесс поиска экстремума в блоке 12 памяти младших разрядов

осуществляется аналогично процессу поиска экстремума в блоке 11 памяти старших разрядов и повторяется g тактов. Отличительным является то, что в каждом такте происходит сдвиг вправо, с заполнением

0 единицей освободившегося разряда регистра маски 28 младших разрядов под действием сигнала с выхода 47 блока 14 управления. Таким образом после окончания поиска экстремума в регисре 3 числа фиксируется мак5 симальное (минимальное) из чисел, которое может быть считано с выходов 4 устройства при появлении единичного сигнала на выходе 40 устройства. Последний формируется при наличии на входе 66 блока 14 управле0 ния единичного сигнала.

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

0 управляющих сигналов, обеспечивающих поиск ближайшего, к заданному (фиг.8). которое подается на входы устройства. В соответствии с упомянутым алгоритмом блок 14 управления формирует единичные сигна5 лы на выходах 33,32,37,42, которыми заданное слово с входов 2 через первый коммутатор 1 записывается в регистр 3, (п- д)-ый разряд индексного регистра 24 устанавливается в единицу, а все остальные его

0 разряды в нуль. Все разряды регистров маски старших 9 и младших 28 разрядов устанавливаются в единицу. Одновременно нулевым сигналом с выхода 15 блока управления производится считывание из блока 11

5 памяти старших разрядов, на адресные входы которого подается код, состоящий из нуля в старшем разряде и кода заданного слова в разрядах с первого по (п-д)-ый. Если с выхода блока 11 памяти старших разрядов

0 считывается сигнал нулевого уровня (соответствует отсутствию чисел, совпадающих с заданным в старших разрядах), блоком управления анализируются сигналы на входах 59 и 60, представляющие прямое и инверс5 нов значение (n-g)-ro разряда заданного слова. Если указанный разряд заданного слова равен нулю (единице), то с выхода 33 на коммутатор 1 подается сигнал, открывающий коммутатор 1 так, что в регистр 3 перезаписывается заданное слово с инверированным тем разрядом, которому в инексном регистре 24 соответствует единица для первого такта (п-д)-ый разряд), после его опять производится опрос блока 11 паяти старших разрядов Если в соответствующей ячейке блока 11 памяти старших разрядов записана единица, то микропрограмма продолжается с метки 1 (фиг.8). Йна е, как и в случае когда (п-д)-ый разряд заданного слова равен единице (нулю), производится сдвиг, сигналами с выходов 44,39 блока 14 управления, влево содержимою регистров 24, 9, описанная процедура проолжается до тех пор, пока не будет осуществлен переход по метке 1, либо не будет сформирован сигнал с выхода 41, Этот сигнал формируется в том случае, если в режиме поиска ближайшего большего меньшего) к заданному в запоминающем устройстве хранятся числа, каждое из которых меньше (больше) заданного Микропрограмма, начинающаяся с метки 1, реализует поиск минимального (максимального) из множества чисег. найденных на описанном выше этапе поиска. На каждом шаге этой процедуры сдвигается вправо содержимое регистров 9 и 24 сигналами с выходов 45, 37 блока 14 управления и производится опрос соответствующей ячейки блока 11 памяти старших разрядов. Если при опросе с выходов блока 11 памяти старших разрядов считывается нуль, то произвоится инвертирование разряда регистра 3, причем позиция инвертируемого разряда определяется положением единицы в индексном регистре 24. По окончании указанного поиска (на входе 64 блока 14 управления появляется единичный сигнал), производится установка младшего разряда индексного регистра 24 в единицу, а всех остальных его разрядов в нуль сигналом с выхода 36 блока 14 управления и далее, как и в случае, когда в первом такте с выхода блока 11 памяти старших разрядов считывается единица. Это соответствует тому, что в устройстве хранится число, совпадающее с заданными старшими разрядами, производится обращение к блоку 19 памяти ссылок. Адрес совпадает с (n-g) старшими разрядами кода найденного в предыдущем цикле поиска и запись содержимого соответствующей ячейки в регистр 29 старших разрядов под действием сигналов с выходов 18 и 51 блока управления. Далее процесс поиска ближайшего большего (меньшего) осуществляется в блоке 12 памяти младших разрядов, аналогично описанному выше,

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

ОТСУТСТВИЮ в устройство чм ;л Полыиих или павмых (меньших или рдяных заданному), либо выдачей единичного сигнала из выхсд 40, который свидетельствует о том, чго ближйпшсо большее (меньк.ее) найдено и зафиксировано на регистре 3 чиста. Формула изобретения Ассоциативное оперативное запоминающее устройство, содг жэщее блок управ0 ления, блок памяти старших разрядов, регистр числа, регистр маски старших разрядов, индексный регистр, блок модиб жа- , 1и кода опроса старших разрядов, первой коммутатор, группу эл ментов И, группу

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

0 разрядов соединены с выходами регистра числа с первого по (n-g)-и разряд, где п - разрядность исла, g - число младших разрядов, выходы регистра маски старших разрядов соединены соответственно с

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

5 поразрядно соединены с первыми входами элементов И группы и первыми входами элементов НЕРАВНОЗНАЧНОСТЬ группы, вторые входы которых соединены соответственно с вторыми входами элементов И

0 группы и с выходами индексного регистра, входы установки старшего разряда, установки младшего разряда, управления сдви- rcjM вправо, управления сдвигом влево которого соединены с соответствующими

5 выходами блока управления, входы Запись. Стирание, Экстремум, Ближайшие к заданному, Максимум-минимум, Равенство которого являются соответствующими входами устройства, выходы зле0 ментов НЕРАВНОЗНАЧНОСТЬ гр, г-г-ы соединены с информационными сходами первой группы первого коммутатора, информационные входы оторой группы которого являются информационными входами

5 устройства, выходы первого коммутатора соединены с информационными входами регистра числа, вход установки и вход сброса которого соединены с соответствующими выходами блока управления, выход управления первым коммутатором которого соединен с управляющим входом первого коммутатора, выходы элементов И группы соединены с входами элемента ИЛИ, выход которого соединен с входом элемента НЕ, выход которого и выход элемента ИЛИ соединены соответственно с входами анализа инверсного и прямого значений младшего разряда и признака поиска блока управления, выходы которого Положительнный результат поиска и Отрицательный результат поиска являются соответствующими выходами устройства, входы управления сдвигом вправо, управления сдвигом влево, установки старшего разряда, установки всех разрядов регистра маски старших разрядов соединены с соответствующими выходами блока управления, отличающее-ся тем, что, с целью упрощения устройства, в него введены регистр маски младших разрядов, блок модификации кода опроса младших разрядов, блок памяти ссылок, регистр старших разрядов адреса, блок памяти младших разрядов, второй коммутатор, реверсивный счетчик, блок памяти свободных ячеек, информационные входы блока модификации кода опроса млад иих разрядов соединены с выходами с g-го по n-ый регистра мисла, выходи регистра маски младших разрядов соединены с управляющими входами блока модификации кода опроса младших разрядов, выходы которого соединены с входами адреса первой группы блока памяти младших разрядов, входы адреса вт. рой группы которого соединены с выходами регистра старших разрядов адреса и с информационными входами первой группы второго коммутатора, информационные входы второй группы которого соединены с выходами реверсивного счетчг э и с входами адреса блока памяти свободных рчеек, информационные входы которого соединены с выходами аторого коммутатора, управляющий вход которого соединен с выходом управления вторым коммутатором блока управления,

выход записи блока памяти свободных ячеек которого соединен с входом записи блока памяти свободных ячеек, выходы которого соединены с информационными входами

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

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

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

входы сброса, прямого и обратного счета реверсивного счетчика соединены с соответствующими выходами блока управления, вход анализа переполнения реверсивного счетчика которого соединен с выходом переполнения реверсивного счетчика, вход ус- тановки (n-g)-ro разряда индексного регистра соединен с соответствующим выходом блока управления, выход записи регистра числа которого соединен с входом

записи регистра числа, вход записи блока памяти ссылок соединен с соответствующим выходом блока управления, вход Начальная установка которого является соответствующим входом устройства, выхсды (n-g)-ro, (n-g-H)-ro, (n}-ro и первого разрядов индексного регистра соединены с соответствующими входами блока управления.

10,1 10 10$ 10 Фиг 2

ттштттт

аяааеакаа

42

4H-f fy К

I С(40)1 I

С конец Фиг.4

С запись ) П

tfS2,ttjf41)--f

c()f |

(ммммм-m w

С(Э8,4б)--1

С Чдаленщр

фП,М,4ЦЩ

/j/y

та/;-/

(1S)1

/W /

С конец ) Фиг 5

С Равенстдо

С(ъгмЖ51М

СС15,17) ff

/ С(41)--1/

Фиг. б

/С(40)1 /

С конец )

ю in

Ј

CO

to

$

s

(Ближайшее }

C{23,.42J:f ; С(15)О 1

C(32)--1;Cfo)--Q

Щ-hsM-O

C(44,59)-i

Г Ш-O I

с(зз)о

/ C(4Q)-1 /

С конец j

C(H)0

(im.5iM

5

С (15)0

Sffjrf

/ /