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

 

О Г(и С.A; ;Н III e

ИЗОБРЕТЕН ИЯ

Союз Советских

Социалистических

Республик (11} 525161

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено11.03.74 (21) 2004001/24 с присоединением заявки №(23) Приоритет (51) M. Кл.е

G 11 С 15/00

Государственный квинтет

Совета Министров СССР оо делам иэооретений и открытий (43) Опубликовано15.08.76ЯБюллетень ¹30 (53) уДК 681 327.6 (088.8) (4S) Дата опубликования описания 07.04 77 (72) Авторы изобретения

С. И. Хмельник и В. П. Хорошутин

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

Энергосетьпроект (71) Заявитель (54) ACCOUHATHBHOE ЗАПОМИНАЮШЕЕ УСТРОЙСТВО

Изобретение относится к области запоминающих устройств.

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

У известного устройства невысокая скорость работы и дорогостоящая аппаратура.

С целью повьппения быстродействия и эффективной емкости предложенное устройство содержит блок декодирования и арифметический беток, входы которого подключены соответственно к выходам запоминающего блока, адресного блока, блока декодирования и первых четырех регистров, а выходы — ко входам адресного блока, блока декодирования первого и второго регистров, один из входов блока декодирования соединен с выходом первого регистра, а выход— со входом пятого регистра, выходы первого и второго регистров подключены к соответcTH llIIM входам GgPecHQI o 6JIDKG

На фиг. 1 показана блок-схема предложенного устройства; на фиг. 2 представлено дерево" геометрических кодов, на фиг. 3 изображен частный случай геометрического хода; на фиг. 4 дан пример кодирования и поиска на дереве геометрических кодов, 5 Устройство содержит (см. фиг. 1) запоминающий блок 1, пять регистров 2-6, адресный блок 7, арифметический блок 8 и блок декодирования 9. Входы блока 8 подключены соответственно х выходам блоков

10 1, 7, 9 и первых четырех регистров 2-5, а выходы — ко входам блоков 7, 8 первого

2 и второго 3 регистров, один из входов блока 9 соединен с выходом регистра 2, а выход - со входом пятого регистра 6, вы15 ходы регистров 2 и 3 подключены к соответствующим входам блока 7.

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

525161

Устройство в целом решает две задачи:

1) кодирование массива двоичных кодов в линейный геометрический код (ГКЛ), хранящийся в блоке 1 в виде последовательности двоичных разрядов, каждый из которых определяется своим номером в этой последовательности, т.е. адресом в блоке 1;

2) ассоциативный поиск кодов, удовлетворяющих некоторому условию поиска, которое определяется двумя двоичными кодами, ® ключевым и базисным, при этом предполагается что массив кодов, в котором производится поиск, уже закодирован в виде ГКЛ и хранится в блоке 1.

Арифметический блок 8 реализует некоторую рекурентную формулу, связывающую ключевой и базисный коды с предыдущим и последующим значениями чисел j u ККроме того, он считает количество циклов поиска и тем самым определяет момент З окончания поиска.

Адресный блок 7 вычисляет адрес разряда ГКЛ в блоке 1 по известным значениям чисел k и, а затем обращается по этому адресу в блок 1.

Блок декодирования результата 9 по известному значению числа определяет искомый код.

Рассмотрим функционирование устройства в целом.

Адресный блок 7 на основе анализа содержимого регистров 2 (число j ) и 3 (число k ) определяет адрес одного бита и посылает этот адрес в запоминающий блок 1 по адресному выходу. Дальнейшие действия различаются в зависимости от решаемой задачи (поиск или кодирование).

При поиске значение бита по вычисленному в блоке 7 адресу выдается в блок 8, который по этому значению и содержимому регистров 2,4,5, (в последних двух регистрах хранятся коды, определяющие условия поиска) определяет новые значения регистров 2 и 3.

Кроме того, блок 8 проверяет, завершен ли поиск очередного кода, и передает управление блоку 7, если поиск не завершен, или блоку 9, если поиск завершен. Последний по д> содержимому регистра 2 определяет искомый код и записывает его в регистр 6.

Затем управление вновь передается блоку7 для поиска следующих кодов, удовлетворяющих условиям поиска, определяемым кода-,р ми, находящимися в регистрах 4 и 5.

При кодировании адресный блок 7 по вычисленному адресу бита записывает 1" в блок 1 (для этого блок 7 связан с запоминающим блоком 1 адресной и информа4 ционной шинами) . Затем арифметический блок 8 по значениям регистров 2, 4 вычисляет новые значения регистров 2 и 3 и передает управление блоку 7. цикл повторяется до завершения кодирования.

Рассмотрим теперь процессы кодирования и поиска подробнее.

1. Кодирование.

Предварительно рассмотрим дерево изображенное на фиг. 2, и присвоим враждой его вершине двузначный номер (4 k ), где — номер яруса, а — номер вершинь-. в K -м ярусе. При этом будем считать, что нумерация ярусов идет справа налево, а нумерации вершин - сверху вниз. Пусть

0 и и — номера крайнего правого и левого ярусов соответственно.

Тогда k = и;П-1,...,2,1 0; Ь= 1,2, К-4 ...,2

Число ярусов Г = П+1; число узлов деfl рева 0=2-1.

Число вершин в ярусе Р N = 2

Обозначим через * 1 вершину с чеьным номером 4 и через Я вЂ” вершину с нечетным номером 1, !! )!

Путь в дереве, соединяющий вершины ф,, и J5>>, назовем Р-путем. Очевидно, Ф каждый Р-путь можно изобразить последовательностью символов 4 и P . Например, на фиг. 2 выделен путь, которому соответствует последовательность Ь рл"

° ° ° !!(o(t

4Л 2,2 !>1

Каждый символ * х (или P „) последовательности, изображающей некоторый

P-путь на "дереве, назовем К -разрядом

Р-пути. Если каждому разряду Р-пути поставить в соответствие "1 (для * ) и "0" (для р ), то P-путь может быть изображен двоичным кодом Кр . В частности, для рассмотренного случая Кр =0...0...01100.

Номер пути-Р, очевидно, равен номеру того разряда в д -м ярусе, на котором заканчивается этот путь.

Условимся теперь, что < и «двоичные величины (< =0,1 и P = 0,1). Назс вем P-путь открытым, если величина всех его разрядов равна 1, и закрытым, если величина хотя бы одного его разряда равна О.

На фиг. 3 для иллюстрации изображено

"дерево двоичных разрядов, в котором открыты пути: Ьlffg ..., *4О ...., ф......; аС.

Р. !

4У"" И,4""

Вершина О находится за разрядной сеткой и не участвует в вычислениях, приведенных ниже.

Каждому из этих путей соответствует двоичный код: Ку- 0110, "so= 1001, 525 161

Таким образом, если

Ки — — 0101, К 2= 1101, К вЂ” 0011, К„= 1О11.

Таким образом, дерево", изображенное на фиг. 3, представляет шесть двоичных кодов. Следует обратить внимание на то, что открытому пути, изображаемому в дереве только единичными разрядами, соответствует двоичный код, содержащий в общем случае и нулевые разряды.

Из сказанного следует, что "дерево", в котором все пути открыты, изображает все

Т -разрядные двоичные коды. Если же только Ol путей "дерева" открыты, то оно изображает группу из Otal -разрядных двоичных кодов

l5

"Дерево" двоичных разрядов, изображающее множество двоичных кодов, назовем геометрическим кодом, а составляющие двоичные коды — линейными кодами. Номер разряда в старшем ярусе геометрического кода назовем адресом соответствующего линейного кода.

Операции с геометрическими кодами эквивалентны некоторой логической или арифметической операции между известным дво« ичным (базисным) кодом К = Бп „... 8K

8 и каждым из линейных кодов, входящих в множество представленное геометрическим кодом. Кроме того, эти операции, как правило, связаны с распространением переносов из правых (младших) ярусов в левые (старшие) ярусы (переносом назовем сигнал, возникающий в данном разряде и поступающий в соседний разряд).

Введем обозначения:

P — (< q k ) — разряд исходного геометрического кода;

d — (1 + 1, k, ) — разряд исходного геометрического кода; Я вЂ” перенос (общий) в разряды :С и Р

1ly>TI@- соответственно переносы из разряда и А

8 — К -й разряд базисного кода.

Обратимся вновь к геометрическому коду, изображенному на фиг, 2, и расположим все 45 его разряды в виде линейного кода так, чтобы за разрядами К -го яруса следовали разряды (K + 1)-го яруса. Образованный таким образом код обозначим символом ГКЛ.

Имеем: 50

=фа ). то = 2

i,K

2j

2j-4

Перенос из старшего разряда, вообще говоря, может возникнуть в нескольких разрядах, что будет свидетельствовать о наличии нескольких кодов, удовлетворяющих данному условию.

На фиг. 4 жирными линиями изображены пути распространения переносов при ассоциативном поиске базисного кода 1001 и ключевом коде 0101.

При ассоциативном поиске может быть найдено несколько линейных кодов, обладающих данными признаками. Эти коды, есГКЛ=б ..б ... б у, 0 4>4 2 3 1 2 1yk K

2 К У4,К+1 2 п

Обозначим все разряды этого кода симво55 лами 6 и пронумеруем их подряд индексами j = 1... И . Тогда получим: и и n+3

В частности, u,= 2 + 2 — 1 = 2

Выделим в ГКЛ три связанных между собой разряда. Очевидно, что выделенная триада, при обозначении разрядов через 6

3 имеет вид:

Например, после переобозначения разрядов р и * символами 6, геометрический код, изображенный на фиг. 3, принимает вид, представленный на фиг. 4.

Рассмотрим операцию Кодирование".

Запись базисного кода, т.е. формирование в дереве" геометрического кода такого открытого пути, который соответствует базисному коду, описывается уравнением

oc, = 118, Р=7(Б, 7! = )7 = Г. о4

Сигнал переноса записывает "1" в те разряды, через которые прохсщит.

На фиг. 4 пунктирной линией изображен путь распространения переносов при записи кода 0110. Из фиг. 4 следует, что перенос направляется в два старших разряда, но записывает 1" только в один иэ них, определяемый содержимым соответствующего разряда базисного кода.

2. Ассоциативный поиск.

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

"= EIn к 1о r причем « < = 1, если обязательно должно быть совпадение k -х разрядов искомого и и базисного кодов, и = О, если совпадение не обязательно. Тогда

П =(jv$)ga у =(тч д)ГР °

525161 тественно, невозможно выбрать из ГКЛ одновременно.

В связи с этим предлагается следующая схема поиска:

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

2) при прекращении распространения переноса на каком-либо промежуточном или последнем ярусе, перенос "отражается и распространяется в противоположную сторону до ближайшего разряда, в который

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

3) выбирается разряд с номером g +1, т.е. разряд (, данной пары;

4) перенос из выбранного разряда распространяется справа налево, как в п.1 и т.д.

Время выполнения ассоциативного поиска по этому алгоритму пропорционально разрядности искомых кодов и количеству кодов, удовлетворяющих условию поиска, но нв зависит от общего объема массива кодов.

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

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

Я5 регистров подключены к соответствующим входам адресного блэка.

525161

4 иг.Ф

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

Редактор Москаленко Техред М. Ликович Корректор Н. Золотовская

Заказ 5088/581 Тираж 723 Подписное

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

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

Филиал ППП " Патент", r. Ужгород, ул. Проектная, 4