ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 25.12.2021

Просмотров: 5254

Скачиваний: 8

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

2 4 6 Глава 5. Память

• схемы совпадения, используемые для параллельного сравнения каждого бита

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

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

один разряд, в который заносится единица, если все разряды соответствующей

ячейки совпали с одноименными разрядами признака поиска;

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

совпадений формирует сигналы, характеризующие результаты поиска инфор-
мации.
При обращении к АЗУ сначала в регистре маски обнуляются разряды, которые

не должны учитываться при поиске информации. Все разряды регистра совпаде-
ний устанавливаются в единичное состояние. После этого в регистр ассоциатив-
ного признака заносится код искомой информации (признак поиска) и начинает-

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

Из-за того что результаты поиска могут оказаться неоднозначными, содержи-

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

 аО — не

 найдена;

 а 1

 — содержится в одной ячейке;

 а2 —

 содержится более чем в одной ячейке.

Формирование содержимого регистра совпадений и сигналов

 аО, а1, а2

 носит

название

 операции контроля ассоциации.

 Она является составной частью опера-

ций считывания и записи, хотя может иметь и самостоятельное значение.

При считывании сначала производится контроль ассоциации по аргументу по-

иска. Затем, при

 аО=1

 считывание отменяется из-за отсутствия искомой инфор-

мации, при

 а1

 = 1 считывается слово, на которое указывает единица в регистре

совпадений, а при

 а2=

 1 сбрасывается самая старшая единица в регистре совпаде-

ний и извлекается соответствующее ей слово. Повторяя эту операцию, можно по-
следовательно считать все слова.

Запись в АП производится без указания конкретного адреса, в первую свобод-

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

 производилось обращение к данной ячейке, и свободной считается либо пу-

стая ячейка, либо та, которая дольше всего не использовалась.


background image

Ассоциативная память  2 4 7

Главное преимущество ассоциативных ЗУ определяется тем, что время поиска

информации зависит только от числа разрядов в признаке поиска и скорости оп-
роса разрядов и не зависит от числа ячеек в запоминающем массиве.

Общность идеи ассоциативного поиска информации отнюдь не исключает раз-

нообразия архитектур АЗУ. Конкретная архитектура определяется сочетанием

четырех факторов: вида поиска информации; техники сравнения признаков; спо-
соба считывания информации при множественных совпадениях и способа записи
информации.

В каждом конкретном применении АЗУ задача поиска информации может фор-

мулироваться по-разному (рис. 5.20.).

Рис. 5.20. Классификация АЗУ по виду поиска информации в запоминающем массиве

При простом поиске требуется полное совпадение всех разрядов признака по-

иска с одноименными разрядами слов, хранящихся в запоминающем массиве.

При соответствующей организации АЗУ способно к более сложным вариантам

поиска, с частичным совпадением. Можно, например, ставить задачу поиска слов

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

Еще одним вариантом сложного поиска может быть нахождение слов, числен-

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

Очевидно, что реализация сложных методов поиска связана с соответствую-

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


background image

2 4 8 Глава 5. Память

При построении АЗУ выбирают из четырех вариантов организации опроса со-

держимого памяти (рис. 5.21). Варианты эти могут комбинироваться параллельно

по группе разрядов и последовательно по группам. В плане времени поиска наибо-

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

Рис. 5.21. Классификация АЗУ по способу опроса содержимого запоминающего массива

Важным моментом является организация считывания из АЗУ информации,

когда с признаком поиска совпадают ассоциативные признаки нескольких слов.
В этом случае применяется один из двух подходов (рис. 5.22).

Рис. 5.22. Классификация АЗУ по способу выборки совпавших слов

при множественных совпадениях

Цепь очередности реализуется с помощью достаточно сложного устройства, где

фиксируются слова, образующие многозначный ответ. Цепь очередности позво-

ляет производить считывание слов в порядке возрастания номера ячейки АЗУ

независимо от величины ассоциативных признаков.

При алгоритмическом способе извлечения многозначного ответа выборка про-

изводится в результате серии опросов. Серия опросов может формироваться пу-


background image

Кэш-память  2 4 9

тем упорядочивания тех разрядов, которые были замаскированы и не участвовали
в признаке поиска. В другом варианте для этих целей выделяются специальные
разряды. Существует целый ряд алгоритмов, позволяющих организовать упоря-
доченную выборку из АЗУ. Подробное их описание и сравнительный анализ мож-
но найти в [14].

Существенные отличия в архитектурах АЗУ могут быть связаны с выбранным

принципом записи информации. Ранее был описан вариант с записью в незаня-
тую ячейку с наименьшим номером. На практике применяются и иные способы

(рис. 5.23), из которых наиболее сложный — запись с сортировкой информации на
входе АЗУ по величине ассоциативного признака. Здесь местоположение ячейки,
куда будет помещено новое слово, зависит от соотношения ассоциативных при-

знаков вновь записываемого слова и уже хранящихся в АЗУ слов.

Рис. 5.23. Классификация АЗУ по способу записи информации

Из-за относительно высокой стоимости АЗУ редко используется как самосто-

ятельный вид памяти.

Кэш-память

Как уже отмечалось, в качестве элементной базы основной памяти в большинстве
ВМ служат микросхемы динамических ОЗУ, на порядок уступающие по быстро-

действию центральному процессору. В результате процессор вынужден простаи-
вать несколько тактовых периодов, пока информация из ИМС памяти установит-
ся

 шине данных ВМ. Если ОП выполнить на быстрых микросхемах статической

памяти, стоимость ВМ возрастет весьма существенно. Экономически приемлемое
решение этой проблемы было предложено М. Уилксом в 1965 году в процессе раз-
работки ВМ Atlas и заключается оно в использовании двухуровневой памяти, ког-

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

 отображение

 участков ОП на буферную

память. Выигрыш достигается за счет ранее рассмотренного свойства локальнос-
ти — если отобразить участок ОП в более быстродействующую буферную память


background image

2 5 0 Глава 5. Память

и переадресовать на нее все обращения в пределах скопированного участка, мож-
но добиться существенного повышения производительности ВМ.

Уилкс называл рассматриваемую буферную память подчиненной (slave me-

mory). Позже распространение получил термин

 кэш-память

 (от английского сло-

ва

 cache

 — убежище, тайник), поскольку такая память обычно скрыта от програм-

миста в том смысле, что он не может ее адресовать и может даже вообще не знать о
ее существовании. Впервые кэш-системы появились в машинах модели 85 семей-
ства IBM 360.

В общем виде использование кэш-памяти поясним следующим образом. Когда

ЦП пытается прочитать слово из основной памяти, сначала осуществляется поиск
копии этого слова в кэше. Если такая копия существует, обращение к ОП не про-
изводится, а в ЦП передается слово, извлеченное из кэш-памяти. Данную ситуа-

цию принято называть успешным обращением или

 попаданием

 (hit). При отсут-

ствии слова в кэше, то есть при неуспешном обращении —

 промахе

 (miss),—

требуемое слово передается в ЦП из основной памяти, но одновременно из ОП
в кэш-память пересылается блок данных, содержащий это слово.

Рис. 5.24. Структура системы с основной и кэш-памятью

На рис. 5.24 приведена структура системы с основной и кэш-памятью. ОП со-

стоит из 2

n

 адресуемых слов, где каждое слово имеет уникальный

 n

-разрядный ад-

рес. При взаимодействии с кэшем эта память рассматривается как

 М

 блоков фик-

сированной длины по

 К

 слов в каждом (М = 2

n

/K).

 Кэш-память состоит из С блоков

аналогичного размера (блоки в кэш-памяти принято называть

 строками),

 причем

их число значительно меньше числа блоков в основной памяти (С «

 М).

 При счи-

тывании слова из какого-либо блока ОП этот блок копируется в одну из строк
кэша. Поскольку число блоков ОП больше числа строк, отдельная строка не мо-

жет быть выделена постоянно одному и тому же блоку ОП. По этой причине каж-
дой строке кэш-памяти соответствует

 тег

 (признак), содержащий сведения о том,

копия какого блока ОП в данный момент хранится в данной строке. В качестве

тега обычно используется часть адреса ОП.


Смотрите также файлы