Ассоциативное запоминающее устройство
Иллюстрации
Показать всеРеферат
О Г(и С.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