ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.12.2021
Просмотров: 5252
Скачиваний: 8
2 5 6 Глава 5. Память
производится параллельное сравнение каждого из четырех тегов, хранящихся в
этой ячейке, с полем тега поступившего адреса, то есть поиск нужного тега среди
четырех возможных осуществляется ассоциативно.
В предельных случаях, когда
v=m,k=
1, множественно-ассоциативное отобра-
жение сводится к прямому, а при
v
= 1,
k = m
— к ассоциативному.
Наиболее общий вид организации множественно-ассоциативного отображе-
ния — использование двух строк на модуль (
v=т/2, k
= 2). Четырехвходовая мно-
жественно-ассоциативная кэш-память (
v
=
т/4, k
= 4) дает дополнительное улуч-
шение за сравнительно небольшую дополнительную цену [122,164]. Дальнейшее
увеличения числа строк в модуле существенного эффекта не привносит.
Следует отметить, что именно этот способ отображения наиболее широко рас-
пространен в современных микропроцессорах.
Отображение секторов
Один из первых вариантов частично-ассоциативного отображения, реализован-
ный в модели 85 семейства ВМ IBM 360. Согласно данному методу, основная па-
мять разбивается на секторы, состоящие из фиксированного числа последователь-
ных блоков. Кэш-память также разбивается на секторы, содержащие такое же число
строк. Расположение блоков в секторе ОП и секторе кэш-памяти полностью со-
впадает. Отображение сектора на кэш-память осуществляется ассоциативно, то есть
любой сектор из ОП может быть помещен в любой сектор кэш-памяти. Логику
работы кэша поясняет рис. 5.29.
Рис. 5.29.
Кэш-память с отображением секторов
Здесь сектор состоит из 16 =2
4
блоков по 16 слов, и основная память содержит
1024 = 2
10
сектора. В 14-разрядном адресе блока основной памяти старшие 10 раз-
рядов показывают номер сектора, а младшие 4 — номер блока внутри сектора.
В свою очередь, кэш-память состоит из 8= 2
3
секторов, и 7-разрядный адрес стро-
ки в кэше включает в себя адрес сектора кэша (3 старших разряда) и номер блока
внутри сектора (4 младших разряда). Ввиду того что расположение блоков в сек-
Кэш-память 2 5 7
торах основной и кэш-памяти совпадает, для выбора блока внутри сектора в обоих
случаях можно использовать четыре младших разряда адреса блока ОП. В резуль-
тате задача преобразования адресов сводится к переходу от 10-разрядного номера
сектора основной памяти к трехразрядному номеру сектора в кэш-памяти. Такое
преобразование осуществляется с помощью ассоциативной памяти тегов на 8 слов
(по числу секторов в кэш-памяти). Каждая ячейка памяти тегов содержит 13 раз-
рядов: 10 старших хранят тег — номер сектора ОП, а три младших разряда — но-
мер сектора кэш-памяти, куда отображен данный сектор ОП. Для проверки того,
имеется ли копия сектора в кэш-памяти, производится ассоциативный поиск по
10 старшим разрядам памяти тегов. Если произошло совпадение, то для доступа
к нужному сектору в памяти данных кэш-памяти используются три младших раз-
ряда соответствующей ячейки памяти тегов.
Поскольку размер сектора велик, в рассматриваемой схеме отображения копи-
руется не весь сектор целиком, а только требуемый его блок. Для этого к каждой
строке, хранимой в кэш-памяти, добавляется один бит информации, называемый
битом достоверности,
показывающий, относится ли данный блок к текущему сек-
тору или в нем осталась информация из сектора, хранившегося на этом месте до
смены секторов.
При заполненной кэш-памяти, когда необходимо заменить один из его секто-
ров, в ассоциативной памяти тегов делается запись о новом секторе, как при заме-
не всего сектора полностью. Фактически же в кэш-память пересылается только
тот блок сектора, к которому в данный момент обращается процессор, и в соответ-
ствующей строке памяти данных бит достоверности устанавливается в единицу.
В то же время биты достоверности остальных строк этого сектора сбрасываются
в 0. Далее, по мере копирования других блоков этого сектора, их биты достоверно-
сти устанавливаются в единицу.
При такой процедуре заполнения секторов кэш-памяти, в случае обнаружения
в ней нужного сектора, предварительно требуется проанализировать состояние бита
достоверности соответствующей строки. Если он установлен в 1, значит, обраще-
ние к данной ячейке кэш-памяти возможно. При нулевом значении бита достовер-
ности сначала производится копирование нужного блока в кэш-память, его бит
достоверности устанавливается в единицу, и лишь после этого разрешается дос-
туп к указанному адресу в кэш-памяти.
В том случае, когда при замене сектора в кэш-памяти необходимо сохранить
его старое содержимое в основной памяти, в ОП пересылаются только заменяе-
мые блоки сектора.
Алгоритмы замещения информации
в заполненной кэш-памяти
Когда кэш-память заполнена, занесение в нее нового блока связано с замещением
содержимого одной из строк. При прямом отображении каждому блоку основной
памяти соответствует только одна определенная строка в кэш-памяти, и никакой
иной выбор удаляемой строки здесь невозможен. При полностью и частично ассо-
циативных способах отображения требуется какой-либо алгоритм замещения (вы-
бора удаляемой из кэш-памяти строки).
2 5 8 Глава 5. Память
Основная цель стратегии замещения — удерживать в кэш-памяти строки, к ко-
торым наиболее вероятны обращения в ближайшем будущем, и заменять строки,
доступ к которым произойдет в более отдаленном времени или вообще не случится.
Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обра-
щение к которой в будущем произойдет позже, чем к любой другой строке кэша.
К сожалению, такое предсказание практически нереализуемо, и приходится при-
влекать алгоритмы, уступающие оптимальному. Вне зависимости от используе-
мого алгоритма замещения для достижения высокой скорости он должен быть реа-
лизован аппаратными средствами.
Среди множества возможных алгоритмов замещения наиболее распространен-
ными являются четыре, рассматриваемые в порядке уменьшения их относитель-
ной эффективности.
Наиболее эффективным является алгоритм замещения на основе
наиболее дав-
него использования
(LRU — Least Recently Used), при котором замещается та стро-
ка кэш-памяти, к которой дольше всего не было обращения. Проводившиеся
исследования показали, что алгоритм LRU, который «смотрит» назад, работает до-
статочно хорошо в сравнении с оптимальным алгоритмом, «смотрящим» вперед.
Наиболее известны два способа аппаратурной реализации этого алгоритма.
В первом из них с каждой строкой кэш-памяти ассоциируют счетчик. К содер-
жимому всех счетчиков через определенные интервалы времени добавляется еди-
ница. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее
число будет в счетчике той строки, к которой дольше всего не было обращений,
и эта строка — первый кандидат на замещение.
Второй способ реализуется с помощью очереди, куда в порядке заполнения строк
кэш-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссыл-
ка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз
оказывается ссылка на строку, к которой дольше всего не было обращений. Имен-
но эта строка прежде всего и заменяется.
Другой возможный алгоритм замещения — алгоритм, работающий по принци-
пу «
первый вошел, первый вышел
» (FIFO — First In First Out). Здесь заменяется
строка, дольше всего находившаяся в кэш-памяти. Алгоритм легко реализуется
с помощью рассмотренной ранее очереди, с той лишь разницей, что после обраще-
ния к строке положение соответствующей ссылки в очереди не меняется.
Еще один алгоритм — замена
наименее часто использовавшейся
строки ( LFU —
Least Frequently Used). Заменяется та строка в кэш-памяти, к которой было мень-
ше всего обращений. Принцип можно воплотить на практике, связав каждую стро-
ку со счетчиком обращений, к содержимому которого после каждого обращения
добавляется единица. Главным претендентом на замещение является строка, счет-
чик которой содержит наименьшее число.
Простейший алгоритм —
произвольный выбор
строки для замены. Замещаемая
строка выбирается случайным образом. Реализовано это может быть, например,
с помощью счетчика, содержимое которого увеличивается на единицу с каждым
тактовым импульсом, вне зависимости от того, имело место попадание или про-
мах. Значение в счетчике определяет заменяемую строку в полностью ассоциатив-
ной кэш-памяти или строку в пределах модуля для множественно-ассоциативной
кэш-памяти. Данный алгоритм используется крайне редко. .
Кэш-память 2 5 9
Среди известных в настоящее время систем с кэш-памятью наиболее встречае-
мым является алгоритм LRU.
Алгоритмы согласования содержимого
кэш-памяти и основной памяти
В процессе вычислений ЦП может не только считывать имеющуюся информацию,
но и записывать новую, обновляя тем самым содержимое кэш-памяти. С другой
стороны, многие устройства ввода/вывода умеют напрямую обмениваться инфор-
мацией с основной памятью. В обоих вариантах возникает ситуация, когда содер-
жимое строки кэша и соответствующего блока ОП перестает совпадать. В резуль-
тате на связанное с основной памятью устройство вывода может быть выдана
«устаревшая» информация, поскольку все изменения в ней, сделанные процессо-
ром, фиксируются только в кэш-памяти, а процессор будет использовать старое
содержимое кэш-памяти вместо новых данных, загруженных в ОП из устройства
ввода.
Для разрешения первой из рассмотренных ситуаций (когда процессор выпол-
няет операцию записи) в системах с кэш-памятью предусмотрены методы обнов-
ления основной памяти, которые можно разбить на две большие группы:
метод
сквозной записи
(write through) и
метод обратной записи
(write back).
По методу сквозной записи прежде всего обновляется слово, хранящееся в ос-
новной памяти. Если в кэш-памяти существует копия этого слова, то она также
обновляется. Если же в кэш-памяти отсутствует нужная копия, то либо из основ-
ной памяти в кэш-память пересылается блок, содержащий обновленное слово
(сквозная запись с отображением); либо этого
не делается
(сквозная запись без
отображения).
Главное достоинство метода сквозной записи состоит в том, что когда строка
в кэш-памяти назначается для хранения другрго блока, то удаляемый блок можно
не возвращать в основную память, поскольку его копия там уже имеется. Метод
достаточно прост в реализации. К сожалению, эффект от использования кэш-па-
мяти (сокращение времени доступа) в отношении к операциям записи здесь от-
сутствует. Данный метод применен в микропроцессорах i486 фирмы Intel.
Определенный выигрыш дает егр модификация, известная
как метод буфери-
зированной сквозной запцси.
Информация сначала записывается в кэш-память и в
специальный буфер, работающий по схеме FIFO. Запись в основную память про-
изводится уже из буфера, а процессор, не дожидаясь ее окончания, может сразу же
продолжать свою работу. Конечно, соответствующая логика управления должна
заботиться о том, чтобы своевременно «опустошать» заполненный буфер. При ис-
пользовании буферизации процессор полностью освобождается от работы с ОП.
Согласно методу обратной записи, слово заносится только в кэш-память. Если
соответствующей строки в кэш-памяти нет, то нужный блок сначала пересылается
из ОП, после чего запись все равно выполняется исключительно в кэш-память.
При замещении строки ее необходимо предварительно переслать в соответствую-
щее место основной памяти. Для метода обратной записи, в отличие от алгоритма
сквозной записи, характерно то, что при каждом чтении из основной памяти осу-
ществляются две пересылки между основной и кэш-памятью.
2 6 0 Глава 5. Память
У рассматриваемого метода есть разновидность —
метод флаговой обратной
записи.
Когда в какой-то строке кэша производится изменение, устанавливается
связанный с этой строкой бит изменения (флажок). При замещении строка из кэш-
памяти переписывается в ОП только тогда, когда ее флажок установлен в 1. Ясно,
что эффективность флаговой обратной записи несколько выше. Такой метод ис-
пользуется в микропроцессорах класса i486 и Pentium фирмы Cyrix.
В среднем обратная запись на 10% эффективнее сквозной записи, но для ее реа-
лизации требуются и повышенные аппаратные затраты. С другой стороны, прак-
тика показывает, что операции записи составляют небольшую долю от общего ко-
личества обращений к памяти. Так, в [194] приводится число 16%. Другие авторы
оценивают долю операций записи величинами в диапазоне от 5 до 34%. Таким обра-
зом, различие по быстродействию между рассмотренными методами невелико.
Теперь рассмотрим ситуацию, когда в основную память из устройства ввода,
минуя процессор, заносится новая информация и неверной становится копия, хра-
нящаяся в кэш-памяти. Предотвратить подобную несогласованность позволя-
ют два приема. В первом случае система строится так, чтобы ввод любой информа-
ции в ОП автоматически сопровождался соответствующими изменениями в
кэш-памяти. Для второго подхода «прямой» доступ к основной памяти допускает-
ся только через кэш-память.
Смешанная и разделенная кэш-память
Когда в микропроцессорах впервые стали применять внутреннюю кэш-память, ее
обычно использовали как для команд, так и для данных; Такую кэш-память При-
нято называть
смешанной,
а соответствующую архитектуру —
Принстонской
(Prin-
ceton architecture), по названию университета, где разрабатывались ВМ с единой
памятью для команд и данных, то есть соответствующие классической архитекту-
ре фон-Неймана. Сравнительно недавно стало обычным разделять кэш-память на
две — отдельно для команд и отдельно для данных. Подобная архитектура полу-
чила название
Гарвардской
(Harvard architecture), поскольку именно в Гарвард-
ском университете был создан компьютер «Марк-1» (1950 год), имевший раздель-
ные ЗУ для команд и данных.
Смешанная кэш-память обладает тем преимуществом, что при заданной емкости
ей свойственна более высокая вероятность попаданий по сравнению с разделен-
ной, поскольку в ней оптимальный баланс между командами и данными устанав-
ливается автоматически. Так, если в выполняемом фрагменте программы обраще-
ния к памяти связаны в основном с выборкой команд, а доля обращений к данным
относительно мала, кэш-память имеет тенденцию насыщаться командами, и на-
оборот.
С другой стороны, при раздельной кэш-памяти выборка команд и данных мо-
жет производиться одновременно, при этом исключаются возможные конфликты.
Последнее обстоятельство существенно в системах, использующих конвейериза-
цию команд, где процессор извлекает команды с опережением и заполняет ими
буфер или конвейер.
В табл. 5.7 приведены основные параметры внутренней кэш-памяти для наибо-
лее распространенных типов микропроцессоров.