ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.12.2021
Просмотров: 5254
Скачиваний: 8
2 4 6 Глава 5. Память
• схемы совпадения, используемые для параллельного сравнения каждого бита
всех хранимых слов с соответствующим битом признака поиска и выработки
сигналов совпадения;
• регистр совпадений, где каждой ячейке запоминающего массива соответствует
один разряд, в который заносится единица, если все разряды соответствующей
ячейки совпали с одноименными разрядами признака поиска;
• регистр маски, позволяющий запретить сравнение определенных битов;
• комбинационную схему, которая на основании анализа содержимого регистра
совпадений формирует сигналы, характеризующие результаты поиска инфор-
мации.
При обращении к АЗУ сначала в регистре маски обнуляются разряды, которые
не должны учитываться при поиске информации. Все разряды регистра совпаде-
ний устанавливаются в единичное состояние. После этого в регистр ассоциатив-
ного признака заносится код искомой информации (признак поиска) и начинает-
ся ее поиск, в процессе которого схемы совпадения одновременно сравнивают
первый бит всех ячеек запоминающего массива с первым битом признака поиска.
Те схемы, которые зафиксировали несовпадение, формируют сигнал, переводя-
щий соответствующий бит регистра совпадений в нулевое состояние. Так же про-
исходит процесс поиска и для остальных незамаскированных битов признака по-
иска. В итоге единицы сохраняются лишь в тех разрядах регистра совпадений,
которые соответствуют ячейкам, где находится искомая информация. Конфигура-
ция единиц в регистре совпадений используется в качестве адресов, по которым
производится считывание из запоминающего массива.
Из-за того что результаты поиска могут оказаться неоднозначными, содержи-
мое регистра совпадений подается на комбинационную схему, где формируются
сигналы, извещающие о том, что искомая информация:
•
аО — не
найдена;
•
а 1
— содержится в одной ячейке;
•
а2 —
содержится более чем в одной ячейке.
Формирование содержимого регистра совпадений и сигналов
аО, а1, а2
носит
название
операции контроля ассоциации.
Она является составной частью опера-
ций считывания и записи, хотя может иметь и самостоятельное значение.
При считывании сначала производится контроль ассоциации по аргументу по-
иска. Затем, при
аО=1
считывание отменяется из-за отсутствия искомой инфор-
мации, при
а1
= 1 считывается слово, на которое указывает единица в регистре
совпадений, а при
а2=
1 сбрасывается самая старшая единица в регистре совпаде-
ний и извлекается соответствующее ей слово. Повторяя эту операцию, можно по-
следовательно считать все слова.
Запись в АП производится без указания конкретного адреса, в первую свобод-
ную ячейку. Для отыскания свободной ячейки выполняется операция считыва-
ния, в которой не замаскированы только служебные разряды, показывающие, как
производилось обращение к данной ячейке, и свободной считается либо пу-
стая ячейка, либо та, которая дольше всего не использовалась.
Ассоциативная память 2 4 7
Главное преимущество ассоциативных ЗУ определяется тем, что время поиска
информации зависит только от числа разрядов в признаке поиска и скорости оп-
роса разрядов и не зависит от числа ячеек в запоминающем массиве.
Общность идеи ассоциативного поиска информации отнюдь не исключает раз-
нообразия архитектур АЗУ. Конкретная архитектура определяется сочетанием
четырех факторов: вида поиска информации; техники сравнения признаков; спо-
соба считывания информации при множественных совпадениях и способа записи
информации.
В каждом конкретном применении АЗУ задача поиска информации может фор-
мулироваться по-разному (рис. 5.20.).
Рис. 5.20. Классификация АЗУ по виду поиска информации в запоминающем массиве
При простом поиске требуется полное совпадение всех разрядов признака по-
иска с одноименными разрядами слов, хранящихся в запоминающем массиве.
При соответствующей организации АЗУ способно к более сложным вариантам
поиска, с частичным совпадением. Можно, например, ставить задачу поиска слов
с максимальным или минимальным значением ассоциативного признака. Много-
кратное выборка из АЗУ слова с максимальным или минимальным значением ас-
социативного признака (с исключением его из дальнейшего поиска), по существу,
представляет собой упорядоченную выборку информации. Упорядоченную выбор-
ку можно обеспечить и другим способом, если вести поиск слов, ассоциативный
признак которых по отношению к признаку опроса является ближайшим боль-
шим или меньшим значением.
Еще одним вариантом сложного поиска может быть нахождение слов, числен-
ное значение признака в которых больше или меньше заданной величины. Подоб-
ный подход позволяет вести поиск слов с признаками, лежащими внутри или вне
заданных пределов.
Очевидно, что реализация сложных методов поиска связана с соответствую-
щими изменениями в архитектуре АЗУ, в частности с усложнением схемы ЗУ
и введением в нее дополнительной логики.
2 4 8 Глава 5. Память
При построении АЗУ выбирают из четырех вариантов организации опроса со-
держимого памяти (рис. 5.21). Варианты эти могут комбинироваться параллельно
по группе разрядов и последовательно по группам. В плане времени поиска наибо-
лее эффективным можно считать параллельный опрос как по словам, так и по раз-
рядам, но не все виды запоминающих элементов допускают такую возможность.
Рис. 5.21. Классификация АЗУ по способу опроса содержимого запоминающего массива
Важным моментом является организация считывания из АЗУ информации,
когда с признаком поиска совпадают ассоциативные признаки нескольких слов.
В этом случае применяется один из двух подходов (рис. 5.22).
Рис. 5.22. Классификация АЗУ по способу выборки совпавших слов
при множественных совпадениях
Цепь очередности реализуется с помощью достаточно сложного устройства, где
фиксируются слова, образующие многозначный ответ. Цепь очередности позво-
ляет производить считывание слов в порядке возрастания номера ячейки АЗУ
независимо от величины ассоциативных признаков.
При алгоритмическом способе извлечения многозначного ответа выборка про-
изводится в результате серии опросов. Серия опросов может формироваться пу-
Кэш-память 2 4 9
тем упорядочивания тех разрядов, которые были замаскированы и не участвовали
в признаке поиска. В другом варианте для этих целей выделяются специальные
разряды. Существует целый ряд алгоритмов, позволяющих организовать упоря-
доченную выборку из АЗУ. Подробное их описание и сравнительный анализ мож-
но найти в [14].
Существенные отличия в архитектурах АЗУ могут быть связаны с выбранным
принципом записи информации. Ранее был описан вариант с записью в незаня-
тую ячейку с наименьшим номером. На практике применяются и иные способы
(рис. 5.23), из которых наиболее сложный — запись с сортировкой информации на
входе АЗУ по величине ассоциативного признака. Здесь местоположение ячейки,
куда будет помещено новое слово, зависит от соотношения ассоциативных при-
знаков вновь записываемого слова и уже хранящихся в АЗУ слов.
Рис. 5.23. Классификация АЗУ по способу записи информации
Из-за относительно высокой стоимости АЗУ редко используется как самосто-
ятельный вид памяти.
Кэш-память
Как уже отмечалось, в качестве элементной базы основной памяти в большинстве
ВМ служат микросхемы динамических ОЗУ, на порядок уступающие по быстро-
действию центральному процессору. В результате процессор вынужден простаи-
вать несколько тактовых периодов, пока информация из ИМС памяти установит-
ся
шине данных ВМ. Если ОП выполнить на быстрых микросхемах статической
памяти, стоимость ВМ возрастет весьма существенно. Экономически приемлемое
решение этой проблемы было предложено М. Уилксом в 1965 году в процессе раз-
работки ВМ Atlas и заключается оно в использовании двухуровневой памяти, ког-
да между ОП и процессором размещается небольшая, но быстродействующая бу-
ферная память. В процессе работы такой системы в буферную память копируются
те участки ОП, к которым производится обращение со стороны процессора. В обще-
принятой терминологии — производится
отображение
участков ОП на буферную
память. Выигрыш достигается за счет ранее рассмотренного свойства локальнос-
ти — если отобразить участок ОП в более быстродействующую буферную память
2 5 0 Глава 5. Память
и переадресовать на нее все обращения в пределах скопированного участка, мож-
но добиться существенного повышения производительности ВМ.
Уилкс называл рассматриваемую буферную память подчиненной (slave me-
mory). Позже распространение получил термин
кэш-память
(от английского сло-
ва
cache
— убежище, тайник), поскольку такая память обычно скрыта от програм-
миста в том смысле, что он не может ее адресовать и может даже вообще не знать о
ее существовании. Впервые кэш-системы появились в машинах модели 85 семей-
ства IBM 360.
В общем виде использование кэш-памяти поясним следующим образом. Когда
ЦП пытается прочитать слово из основной памяти, сначала осуществляется поиск
копии этого слова в кэше. Если такая копия существует, обращение к ОП не про-
изводится, а в ЦП передается слово, извлеченное из кэш-памяти. Данную ситуа-
цию принято называть успешным обращением или
попаданием
(hit). При отсут-
ствии слова в кэше, то есть при неуспешном обращении —
промахе
(miss),—
требуемое слово передается в ЦП из основной памяти, но одновременно из ОП
в кэш-память пересылается блок данных, содержащий это слово.
Рис. 5.24. Структура системы с основной и кэш-памятью
На рис. 5.24 приведена структура системы с основной и кэш-памятью. ОП со-
стоит из 2
n
адресуемых слов, где каждое слово имеет уникальный
n
-разрядный ад-
рес. При взаимодействии с кэшем эта память рассматривается как
М
блоков фик-
сированной длины по
К
слов в каждом (М = 2
n
/K).
Кэш-память состоит из С блоков
аналогичного размера (блоки в кэш-памяти принято называть
строками),
причем
их число значительно меньше числа блоков в основной памяти (С «
М).
При счи-
тывании слова из какого-либо блока ОП этот блок копируется в одну из строк
кэша. Поскольку число блоков ОП больше числа строк, отдельная строка не мо-
жет быть выделена постоянно одному и тому же блоку ОП. По этой причине каж-
дой строке кэш-памяти соответствует
тег
(признак), содержащий сведения о том,
копия какого блока ОП в данный момент хранится в данной строке. В качестве
тега обычно используется часть адреса ОП.