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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

Я1 (19) (11) (б1) 4 G 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTGPCHGM / СВИДЕТЕЛЬСТВУ

m а з»зкиas

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4089513/24-24 (22) 11.07.86 (46) 30.12.87. Бюл, ¹ 48 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, А.П.Марковский (SU) и Марта Зеебауэр (HU) (53) 681.327 (088,8) (56) Авторское свидетельство СССР № 493165, кл. G 11 С 15/00, 1975.

Авторское свидетельство СССР № 978197, кл, G 11 С 15/00, 1981. (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ 3AII0 МИНАМЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации цифровых вычислительных систем с возможностью параллельной обработки информации. Цель изобретения — повышение быстродействия устройства при выпол-, нении процедур поиска экстремумов или ближайшего большего (меньшего) к заданному в ассоциативной памяти, построенной на основе модулей памяти с произвольным доступом. Ассоциа1363307

20

30 тивное оперативное запоминающее устройство содержит коммутатор 1, блок

11 памяти, регистр 3 числа, регистр

9 маски, индексный регистр 13, блок

7 модификации признака поиска, блок

16 управления, элементы И 5, элемент

ИЛИ 14, элемент НЕ 15, элементы НЕРАВНОЗНАЧНОСТЬ 6. Сущность работы устройства состоит в том, что в блок лч оперативной памяти объемом 2 (n разрядность чисел) записывается инИзобретение относится к вычислительной технике, в частности к устройствам хранения информации,и может, быть использовано в цифровых системах параллельной обработки информации.

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

Ассоциативное оперативное запоминающее устройство (фиг. 11 содержит коммутатор 1, входами первой группы которого являются информационные входы 2<-2д устройства, регистр 3 числа, выходы которого являются информационными выходами 4, -4,„устройства, элементы И 5, элементы НЕРАВНОЗНАЧНОСТЬ 6, блок 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 соответственно. "Запись", "Стирание" "Экстремум", "Ближайший K признаку поиска", "Максимум-минимум", "Равенство". Блок 16 управления содержит входы 38 и 39 анализа соответственно прямого и инверсного значений младшего разряда поиска и вход 40 результата поиска.

Блок 7 (фиг.2) содержит группы элементов И 41, элементы И 42, элементы НЕ 43, элементы ИЛИ 44.

Блок 16 управления может быть выполнен, например, в виде микропрограммного устройства управления (см.фиг.3) и содержит блок 45 постоянной памяти начальных адресов микропрограмм, блок 46 элементов

ИЛИ, счетчик 47 адреса мнкрокоманд, блок 48 постоянной памяти микропрограмм, регистр 49 микрокоманд, муль-. типлексор 50 условий ветвления мик ропрограмм, элемент И 51, элемент

HJIH 52, вход 53.

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

При записи слова в блок 11 памяти оно подается на входы 2 устройства, а на вход 32 "Запись" подается единичный потенциал, под действием которого блок 16 управления форжругистра 9 маски заполняются нулями.

Например, при n=8 код маски в цикле записи меняется, образуя последовательность кодов: 11111111, 11111110

11111100,..., 10000000, 00000000, С изменением маски и раэ меняется модифицированный код опроса на выходах

10, образуя последовательность адресов блока 11 памяти, по которым осуществляется запись единицы, В режиме стирания слова из запоминающего устройства единичный сигнал подается на вход 33 устройства, 15 под действием этого сигнала блок 16 управления формирует последовательность сигналов, реализующих процесс стирания слова, подаваемого на информационные входы 2 устройства

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

2 через коммутатор 1 записывается в

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

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

4р в устройстве числа, совпадающего с кодом, следующим в адресе после первого нуля, Соответственно, каждай

yKasaHHaa ячейка соответствует только одному информационному слову. В

45 то же время ячейки, номера которых начинаются с комбинации 10, соответствуют двум числам, Отличающимся в младшем разряде. Ячейки, номера которых начинаются с комбинации 110, 5р соответствуют четырем числам, отличающимся в двух, младших разрядах, и т.д..При стирании числа обнуление ячеек производится только тогда, когда единица в данной ячейке обусловлена наличием В памяти тОлько данного числа, В первом такте операции стира" ния по адресу, определяемому модифицированным кодом опроса, при установленных в единицу всех разрядах ре3 13 ет последовательность управляющих сиг налов (фиг.4). В частности блок 16 управления формирует единичный сигнал на выходе 31, который устанавливает все разряды регистра 9 маски в единицу а нулевой сигнал на выходе 26 управляет прохождением информационного слова с выходов 2 через коммутатор 1 на регистр 3 числа. С прямых выходов регистра 3 записываемое слово поступает на один из входов 4 блока 7, на другие входы которого поступает и-разрядный код с регистра 9 маски, а на выходе 10 которого формируется (п+1)-разрядный модифицированный код опроса, причем последний формируется следующим образом . код маски состоит из группы единиц, заиииаююих t стариих разрядов (СЕ fO,ï)) модифицированный код опроса имеет в своем r-м разряде нуль (r=t+1), в разрядах с номерами, меньшими r т.е, в разрядах с 1-ro по (r-1)-й, единицы, в разрядах с(г+1)-го.по (n+1)-й — t старших разрядов немодифицированного кода опроса (кода, подаваемого на входы блока 7) . Например, если код маски имеет внд

11110000 (n=8, =4), а код на регистэ6 3 — 11001010, то r=5, модифицированный код опроса имеет вид

111101100; если код маски имеет вид

00000000, то модифицированный код опро са будет иметь вид 011001010 (r =

1, t = О). Модифицированный код опроса с выхода блока 7 поступает на адресные входы блока 11 памяти.

Сигнал управления записью поступает в виде единичного сигнала с выхода

17 блока 16 управления на вход записи-чтения блока 11 памяти, на инфор".. мационный вход которого единичный сигнал поступает с выхода 27 блока

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

9 сигналом с выхода 31 блока 16 управления устанавливаются в единицу) . Сдвиг влево осуществляется под действием единичного сигнала с выхода 29 блока 16 управления, При сдвиге освободившиеся разряды ре63307 4

5 13 ! гистра 9 маски в блоке 11 памяти записывается нуль. В следующем такте нулевым сигналом с выхода 26 блока

16 управления в регистр 3 записывается исключаемае слово, п-й разряд которого инвертирован поразрядным сложением по модулю два в элементах

НЕРАВНОЗНАЧНОСТЬ б содержимого регистра 3 и индексного регистра 13 все разряды которого, кроме п-га, обнулены, Формируемым в этом случае модифицированным кодам опроса производится опрос соответствующей ячейки блока 11 памяти: если в этой ячейке записана единица, то процесс стирания на этом завершается, а если— нуль, то сигналами с выходов 29 и

23 блока 16 управления производится сдвиг влево соатветсвенно регистра

9 маски и индексного регистра 13 с заполнением кулями освободившихся разрядов, Па адресу, определяемому модифицированным кадом опроса, в блоке 11 памяти записывается нуль, затем по способу, описанному вьппе, инвертируется (и-1)-й разряд регистра 3, и соответствующим модифицированным кодом опроса, выбираемым в качестве адреса блока 11 памяти, производится опрос соответствующей ячейки блока 11 памяти. Если в упомянутой ячейке записана единица, то процесс стирания заканчивается, а если нуль — то производится сдвиг о влево регистра 9 маски и индексного регистра 13, и процесс исключения продолжается по способу, описанному вьппе, При поиске слова в предлагаемом устройстве по совпадению (см.фиг.б) единичный сигнал подается на вход

37 устройства, который инициирует выдачу блоком 16 управления единичного сигнала с выхода 26 на коммутатор под действием которого слово с входов 2 устройства записывается на регистр 3 единичными сигналами с выходов 17 и 31 устанавливаются в единицу все разряды регистра 9 маски и инициируется считывание иэ блока

11 памяти содержимого ячейки, адрес которой задается модифицированным . кодам опроса, состоящим в укаэанном режиме поиска иэ нуля в старшем разряде и кода слава в разрядах с второго по (n+1)-й, Если в соответствующей ячейке блока 11 памяти записана единица, то единичный сигнал форми63307

6 руется на выходе 24 устройства, в противном случае единичный сигнал формируется на выходе 25 устройства.

В режиме поиска максимального (минимального) числа иэ хранящихся в ассоциативном оперативном запоминающем устройстве подается единичный сигнал на вход 34 и единичный (нулевой) сигнал, — на вход 36, причем сиг.нал, подаваемый на последний вход, определяет направление поиска; при единичном потенциале на входе 36 осуществляется поиск максимального, а при нулевом потенциале на входе 36 — поиск минимального среди записанных в устройстве чисел .

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

20 и 19 (18) блока 16 управления ус25 танавливаются в единицу первые разряды индексного регистра 13 и регистра 9 маски, все остальные разряды регистров 13 и 9 устанавливаю гся в нуль; все разряды регистра 3

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

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

35 11 памяти записан нуль (соответствует отсутствию чисел с единицей (нулем) в старшем разряде), то сигналом с выхода 26 блока 16 управления на регистр 3 с выходов элементов HEPAB40 НОЗНАЧНОСТЬ 6 через коммутатор 1 записывается код, ранее хранившийся на регистре 3, но с инвертированным старшим разрядом, если по упомянутому выше адресу в блоке 11 памяти запи45 сана единица (соответствует наличию хотя бы одного числа среди хранящихся в устройстве с единицей в старшем разряде), то цикл инвертирования отдельного разряда регистра 3 опуска50 ется, Затем по сигналам с выходов 28, 22 блока 16 управления производится сдвиг вправо содержимого регистра 9 маски (с заполнением освободившегося разряда единицей) и индексного ре5 гистра 13 (с заполнением освободив55 шегося разряда нулем), Описанный вьппе процесс повторяется п раз, после чего в регистре 3 фиксируется максимальное (минимальное) иэ чисел, 7

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

В режиме поиска ближайшего больше-. го (меньшего) к заданному из чисел, хранящихся в устройстве, единичный сигнал подается на вход 35 и соответствующий потенциал (при поиске ближайшего большего — Единичный, а при поиске ближайшего меньшего— нулевой) подается на вход 36, эти сигналы инициируют выдачу блоком

16 управления последовательности управляющих сигналов, обеспечивающих поиск ближайшего к заданному (фиг.8) которое подается на входы 2 устройства. В соответствии с упомянутым алгоритмом блок 16 управления формирует единичные сигналы на выходах

21,26,31, которыми заданное слово с входов 2 через коммутатор 1 записывается в регистр 3, и-й разряд индексного регистра 13 устанавливается в единицу, а все остальные его разряды — в нуль, все разряды регистра 9 маски устанавливаются в единицу.

Одновременно нулевым сигналом с выхода 17 блока 16 управления производится считывание из блока 11 памяти информации на вход 40 блока 16 управления (на адресные входы 10 блока 11 памяти подается код, состоящий из нуля в старшем разряде и кода заданного слова в разрядах с второго по (п+1)-й). Если с выхода блока ll памяти снимается сигнал единичного потенциала, то блок 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 (этот сигнал формируется в том случае, если в режиме поиска ближайшего большего (меньшего) к заданному в запоми15 нающем устройстве хранятся числа, каждое из которых меньше (больше) заданного). Микропрîrpамма, начинающаяся с метки 1, реализует поиск минимального(максимального) из множест20 ва чисел, найденных на описанном выше этапе поиска, На каждом шаге этой процедуры сдвигается вправо содержимое регистров 9 и 13 (сигналами с выходов 22 и 28 блока 16 управле25 ния) и производится опрос соответствующей ячейки блока 11 памяти.

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

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

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

„- записи-чтения которого соединен с первым выходом блока управления, второй и третий выходы которого подключены соответственно к входу установки в "1" и входу установки в "0"

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

1363307

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

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

ЗО поиска блока управления.

1363307

26

18

2f

22

23

2Ч

f7

27

28

t8

Л

Фиг 4

1363307

1363307

Составитель В,Рудаков

Редактор Л.Be селовская Техред Л. Олийнык

Корректор И,Муска

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

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