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

тивное оперативное запоминающее устройство содержит коммутатор 1, блок 11 памяти, регистр 3 числа, регистр 9 маски, индексный регистр 13, блок 7 модификации признака поиска, блок 16 управления, элементы И 5, элемент ИЛИ 14, элемент НЕ 15, элементы НЕРАВНОЗНАЧНОСТЬ 6. Сущность работы устройства состоит в том, что в блок оперативной памяти объемом 2 (п - разрядность чисел) записывается ин1

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

ЦИИо

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

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

Ассоциативное оперативное запоминающее устройство (фиГоО содержит коммутатор 15 входами первой группы которого являются информационные входы 2(-2 устройства, регистр 3 числа, выходы которого являются информационными выхода;ми 4,-4„ устройства, элементы И 5, элементы НЕРАВНОЗНАЧНОСТЬ 6, блок 7 модификации признака поиска, входы которого под ключены к выходам 8, -8 регистра 9 маски, а выходы 10, -lOn+i связаны с адресными входами блока 11 -памяти Выходы 12 12 индексного регистра 13 подключены к одним из входов эле63307

формация о наличии заносимого в память слова с учетом маскирования групп разрядов. Указанный метод записи позволяет осуществлять маскированный поиск (для определенных ограниченных видов маски) за один цикл обращения к памяти произвольного доступао Применяемых видов масок достаточно для ассоциативного нахождения экстремума и поиска ближайшего к заданно- муо 8 ил„

ментов И 5 и элементов НЕРАВНОЗНАЧНОСТЬ 6 о Устройство также содержит элемент ИЛИ 14, элемент НЕ 15 и блок 16 управления,Блок 16 имеет выходы 17-23, Устройство имеет выход 24 Положительный результат поиска и выход 25 Отрицательный результат поиска о Блок 16 имеет также выхода

26-31, Устройство содержит входы 32- 37 соответственное Запись, Стирание,, Экстремум, Ближайший к признаку поиска, Максимум-минимум, Равенство, Блок 16 управления содерP жит входы 38 и 39 анализа соответственно прямого.и инверсного значений мпадшего разряда поиска и вход 40 результата Поиска

Блок 7 (фиг,2) содержит группы

0 элементов И 41, элементы И 42, элементы НЕ 43, элементы ИДИ 44,

Блок 16 управления может быть выполнен, например, в виде микропрограммного устройства управления

5 (смофиг,3) и содержит блок 45 пос- . тоянной памяти начальных адресов микропрограмм, блок 46 элементов ИЛИ, счетчик 47 адреса микрокоманд, блок 48 постоянной памяти микропрог0 рамм, регистр 49 микрокоманд, муль- типлексор 50 условий ветвления мик- ропрограмм, элемент И 51, элемент ИЛИ 52, вход 53..

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

При записи слова в блок 11 памя- : ти оно подаете) на входы 2 устройства, а на вход 32 Запись подается единичный потенциал, под действием которого блок 16 управления фор1дару5

ет последовательность управлякщих сигналов (фиг,4), В частности блок 16 управления фop бIpyeт единичный сигнал на выходе 31, который устанавливает все разряды регистра 9 маски в единицу, а нулевой сигнал на выходе 26 управляет прохождением информационного слова с выходов 2 через коммутатор 1 на регистр 3 числа, С пряьых выходов регистра 3 записываемое слово поступает на один из входов 4 блока 7, на другие входы которого поступает п-разрядньй код с регистра 9 маски, а на выходе 10 которого формируется (п+1)-разрядный модифицированный код опроса, причем последний формируется следуншщм образом: код маски состоит из группы единиц, занимающих t старших разрядов (tGfoTnljjJO модифицированный код опроса имеет в своем г-м разряде нуль (), в разрядах с номерами, меньшими г, т.е. в разрядах с 1-го по (г-1)-й, - единицы, в разрядах с(г+1)-го по (п+1)-й - t старших разрядов немодифицированного кода опроса (кода, подаваемого на входы блока 7). Например, если код маски имеет вид

гистра 9 маски заполняются нулями о Например, при код маски в цикле записи меняется, образуя последоваg тельность кодов: 11111111, 11111110, 11111100,00., 10000000, ООООООООо С изменением маски п раз меняется модифицированный код опроса на выходах 10, образуя последовательность адре10 сов блока 11 памяти, по которым осуществляется запись единицы.

В режиме стирания слова из запо- минанщего устройства единичный сигнал подается на вход 33 устройства,

15 под действием этого сигнала блок 16 управления формирует последовательность сигналов, реализующих процесс стирания слова, подаваемого на информационные входы 2 устройства (фиГо5)о Указанная последовательность начинается вьщачей блоком 16 управления единичного сигнала с выхода 26, по которому стираемое слово с входов 2 через коммутатор 1 записывается в

25 регистр 3. Единичным сигналом с выхода 31 блока 16 управления все разряды регистра 9 маски устанавливаются в единицу, а единичным сигналом с выхода 21 блока 16 управления все

11110000 (, ), а код на .регист- 30 разряды индексного регистра 13, 3 - 11001010, то , модифицированный код опроса имеет вид 111101100; если код маски имеет вид 00000000, то модифицированный код .опроса будет иметь вид 011001010 (г 1, t О). Модифицированный код опроса с выхода блока 7 поступает на адресные входы блока 11 памятио Сигнал управления записью поступает в виде единичного сигнала с выхода 17 блока 16 управления на вход записи-чтения блока 11 памяти, на инфорг мационный вход которого единичный сигнал поступает с выхода 27 блока 16 управления о Запись слова состоит в записи единиц в п ячеек блока 11 памяти, адреса которых однозначно определяются записываемым словом Соответственно, процесс записи дпит- ся п тактов, причем в каждом такте производится сдвиг влево на один разряд содержимого регистра 9 маски (первоначально все разряды регистра 9 сигналом с выхода 31 блока 16 управления устанавливаются в единицу) . Сдвиг влево осуществляется под действием единичного сигнала с выхода 29 блока 16 управления. При сдвиге освободившиеся разряды реме п-го, в который -записывается единица, устанавливаются в нуль с, Процесс стирания слова состоит в записи нулей в ячейки, единицы в которых отра25 жали факт хранения только данного числа. Как .следует из описания процесса записи, единица, записанная в ячейках, адреса которых начинаются с нуля, свидетельствует о хранении

40 в устройстве числа, совпадающего с кодом, следующим в адресе после первого нуля. Соответственно, каждай указанная ячейка соответствует только одному информационному слову. В

45 то же время ячейки, номера которых начинаются с комбинации 10, соответствуют двум числам, отличающимся в младшем разряде. Ячейки, номера которых начинаются с комбинации 110, соответствуют четырем числам, отлича- кядимся в двух, младших разрядах, и ТоД. При стирании числа обнуление ячеек производится только тогда, когда единица в данной ячейке обусловлена наличием в памяти только данного числа. В первом такте операции стирания по адресу, определяемому модифицированным кодом опроса, при установленных в единицу всех разрядах ре50

55

гистра 9 маски заполняются нулями о Например, при код маски в цикле записи меняется, образуя последовательность кодов: 11111111, 11111110, 11111100,00., 10000000, ООООООООо С изменением маски п раз меняется модифицированный код опроса на выходах 10, образуя последовательность адресов блока 11 памяти, по которым осуществляется запись единицы.

В режиме стирания слова из запо- минанщего устройства единичный сигнал подается на вход 33 устройства,

под действием этого сигнала блок 16 управления формирует последовательность сигналов, реализующих процесс стирания слова, подаваемого на информационные входы 2 устройства (фиГо5)о Указанная последовательность начинается вьщачей блоком 16 управления единичного сигнала с выхода 26, по которому стираемое слово с входов 2 через коммутатор 1 записывается в

регистр 3. Единичным сигналом с выхода 31 блока 16 управления все разряды регистра 9 маски устанавливаются в единицу, а единичным сигналом с выхода 21 блока 16 управления все

ме п-го, в который -записывается единица, устанавливаются в нуль с, Процесс стирания слова состоит в записи нулей в ячейки, единицы в которых отра5 жали факт хранения только данного числа. Как .следует из описания процесса записи, единица, записанная в ячейках, адреса которых начинаются с нуля, свидетельствует о хранении

0 в устройстве числа, совпадающего с кодом, следующим в адресе после первого нуля. Соответственно, каждай указанная ячейка соответствует только одному информационному слову. В

5 то же время ячейки, номера которых начинаются с комбинации 10, соответствуют двум числам, отличающимся в младшем разряде. Ячейки, номера которых начинаются с комбинации 110, соответствуют четырем числам, отлича- кядимся в двух, младших разрядах, и ТоД. При стирании числа обнуление ячеек производится только тогда, когда единица в данной ячейке обусловлена наличием в памяти только данного числа. В первом такте операции стирания по адресу, определяемому модифицированным кодом опроса, при установленных в единицу всех разрядах ре0

5

5,

гистра 9 маски в блоке 11 памяти записывается нуль, В следующем такте нулевым сигналом с выхода 26 блока 16 управления в регистр 3 записывается исключаемое слово, п-й разряд которого инвертирован поразрядным сложением по модулю два в элементах НЕРАВНОЗНАЧНОСТЬ 6 содержимого регистра 3 и индексного регистра 13, все разряды которого, кроме п-го,. обнулены Формируемым в этом случае модифицированным кодом опроса производится опрос соответствующей ячейки блока 11 памяти; если в этой ячейке записана единица, то процесс сти рання на этом завершается, а если - нуль, то сигналами с выходов 29 и 23 блока 16 управления производится сдвиг влево соответсвенно регистра 9 маски и индексного регистра 13 с заполнением нулями освободившихся разрядов о По адресу, определяемому модифицированным кодом опросаj в блоке 11 памяти записывается нуль, затем по способу, описанному вьппе, нвертируется (п-1)-й разряд регистра 3, и соответствующим модифицированным кодом опроса, выбираемым в качестве адреса блока П памяти, производится опрос соответствующей ячейки блока 11 памяти Если в упомя нутой ячейке записана единица, то процесс стирания заканчивается, а если нуль - то производится сдвиг влево регистра 9 маски и индексного регистра 13, и процесс исключения продолжается по способу, описанному вьше о

При поиске слова в предлагаемом стройстве по совпадению (смофиг.б) единичный сигнал подается на вход 37 устройства, который инициирует вьщачу блоком 16 управления единичного сигнала с выхода 26 на коммутатор 1, под действием которого слово с входов 2 устройства записывается на егистр 3 единичными сигналами с выодов 17 и 31 устанавливаются в едиицу все разряды регистра 9 маски и нициируется считывание из блока 11 памяти содержимого ячейки, адрес которой задается модифицированным кодом опроса, состоящим в указанном ежиме поиска из нуля в старшем разяде и кода слова в разрядах с втоого по (п+О -й, Если в соответствуюей ячейке блока 11 памяти записана единица, то единичный сигнал фррми633076

руется на выходе 24 устройства, в противном случае единичный сигнал формируется на выходе 25 устройства. J. В режиме поискя максимального (миьшмального) числа из хранящихся в ассоциативном оперативном запоминающем устройстве подается единичный сигнал на вход 34 и единичный (нуле- JO вой) сигнал - на вход 36, причем сиг- .нал, подаваемый на последний вход, определяет направление поиска; при единичном потенциале на входе 36 осуществляется поиск максимально15 го, а при нулевом потенциале на

входе 36 - поиск минимального среди записанных в устройстве чисел.

Под действием упомянутых внешних управляющих сигналов блок 16 управ- 20 ления формирует последовательность управляющих сигналов, обеспечивакяцих выполнение процедуры поиска экстремума (смофиг.7)о Сигналами с выходов 20 и 19 (18) блока 16 управления ус- 25 танавливаются в единицу первые разряды индексного регистра 13 и регистра 9 маски, все остальные разряды регистров 13 и 9 устанавливаются в нуль; все разряды регистра 3

30 устанавливаются в единицу (нуль)

Производится считывание информации из блока II памяти по адресу, опреде-. ляемому модифицированным кодом опроса; если по данному адресу в блоке

35 1I памяти записан нуль (соответствует отсутствию чисел с единицей (нулем) в старшем разряде), то сигналом с выхода 26 блока 16 управления на регистр 3 с выходов элементов НЕРАВ- - 40 НОЗНАЧНОСТЬ 6 через коммутатор 1 записывается код, ранее хранившийся на регистре 3, но с инвертированным старшим разрядомJ если по упомянутому выше адресу в блоке 11 памяти запи45 сана единица (соответствует наличию хотя бы одного числа среди хранящихся в устройстве с единицей в старшем разряде), то цикл инвертирования отдельного разряда регистра 3 опуска- .

50 ется о Затем по сигналам с выходов 28 22 блока 16 управления производится сдвиг вправо содержимого регистра 9 маски (с заполнением освободившегося разряда единицей) и индексного реfjg гистра 13 (с заполнением освободившегося разряда Нулем)с Описанный вьш1е процесс повторяется п раз, после чего в регистре 3 фиксируется максимальное (минимальное) из чисел.

которое может быть считано с выходов 4 устройства при появлении единичного сигнала на выходе 24 устройства

В режиме поиска ближайшего большего (меньшего) к заданному из чисел, храня1цихся в устройстве, единичный сигнал подается на вход 35 и соответствующий потенциал (при поиска ближайшего большего - единичный, а при поиске ближайшего меньшего - нулевой) подается на вход 36, эти сигналы инициируют выдачу блоком 16 управления последовательности управляющих сигналов, обеспечивающих поиск ближайшего к заданному (фиг,8) которое подается на входы 2 устройства о В соответствии с упомянутым алгоритмом блок 16 управления формирует единичные сигналы на выходах 21,26,31, которыми заданное слово с входов 2 через коммутатор 1 записывается в регистр 3, п-й разряд

индексного регистра 13 устанавливает- 25; ния) и производится опрос соответся в единицу, а все остальные его разряды - в нуль , все разряды регистра 9 маски устанавливаются в единицу. Одновременно нулевым сигналом с выхода 17 блока 16 управления производится считывание из блока 11 памяти информации на вход 40 блока 16 управления (на адресные входы 10 блока 11 памяти подается код, состоящий из нуля в старшем разраде и кода заданного слова в разрядах с второго по (п+1)-й) Если с выхода блока 11 памяти снимается сигнал единичного потенциала, то блок 16 управления формирует единичный сигнал на выходе 24 устройства. Указанная ситуация имеет место, если в устройстве хранится число, совпадакщеа с заданными, В противном случае, т.е, если с блока 11 памяти считывается нуль, блоком 16 управления анализируются сигналы на входах 38 и 39, предсталяюпще прямое и инверсное значения младшего разряда заданного слова. Если младший разряд заданного слова равен нулю (единице), то с выхода 26 на коммутатор 1 подается сигнал, открывающий коммутатор 1J так что в регистр 3 перезаписывается заданное слово с инвертированным младшим разрядом, после чего опять производится опрос блока 11 памяти. Если в соответствую- щей ячейке блока 11 памяти записана единица, то микропрограмма продолжа633078

ется с метки 1 (см.). Иначе, как и в случае, когда младший разряд заданного слова равен единице (нулю),

g производится сдвиг (сигналами с выходов 29 и 23 блока 16 управления) влево содержимого регистров 9 и 13J описанная процедура продолжается до тех пор, пока не будет осуществлен .

10 переход по метке 1, либо не будет сформирован сигнал с выхода 25 (этот сигнал формируется в том случае, если в режиме поиска ближайшего большего (меньшего) к заданному в запоми15 нающем устройстве тсранятся числа, каждое из которых меньше (больше) заданного). Микропрограмма, начинаю-- щаяся с метки 1, реализует поиск минимального (максимального) из множест20 ва чисел, найденных на описанном выше этапе поиска о На каждом шаге этой процедуры сдвигается вправо содержимое регистров 9 и 13 (сигналами с выходов 22 и 28 блока 16 управле

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

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

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

регистра числа, о тличающее- с-Я тем, что, с целью повышения быстродействия устройства, в него введены коммутатор, элементы И, элементы НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ

у

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

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

6330710

выходы блока управления являются соответственно выходом Положительный результате поиска и выходом Отри- ц цательный результат поиска устройства, одиннадцатый выход блока управления подключен к информационному входу блока памяти, с двенадцатого по пятнадцатый выходы блока управле- 10 ния подключены соответственно к входу управления сдвигом вправо регистра маски, к входу управления сдви

гом влево регистра маски, к входу установки старшего разряда в 1 и в О

всех остальных разрядов регистра

ti III

маски, к входу установки в 1 регистра маски, с первого по шестой входы блока управления являются соответственно входами Запись, Стирание, Экстремум, Ближайшее к признаку поиска, Максимум-минимум и Равенство устройства, выходы 3Jie- мента ИЛИ и элемента НЕ подключены соответственно к входу анализа прямого значения младшего разряда признака поиска и входу анализа инверсного значения младшего разряда признака поиска блока управления, выход блока памяти соединен с входом результата поиска блока управления.

V,

Wn.(

32

33 3V 35 37

СРа6енст6сГ

С(28, Cdll O

стремум)

) ф

(лшнаише 3

С Иоиец j

Фиг. 8

Редактор Л.Веселовская

Составитель В.Рудаков Техред Л. Олийнык

Заказ 6369/45Тираж 588Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д.4/5

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

Корректор И,Myска

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации цифровых вычислительных систем с возможностью параллельной обработки информации. Цель изобретения - повьшение быстродействия устройства при выпол-: нении процедур поиска экстремумов или ближайшего большего (меньшего) к заданному в ассоциативной памяти, построенной на основе модулей памяти с произвольным доступом. Ассоциазг 33 з« 35 36 37 с 5S .