Кэш-память 2 5 7
торах основной и кэш-памяти совпадает, для выбора блока внутри сектора в обоих случаях можно использовать четыре младших разряда адреса блока ОП. В резуль­тате задача преобразования адресов сводится к переходу от 10-разрядного номера сектора основной памяти к трехразрядному номеру сектора в кэш-памяти. Такое преобразование осуществляется с помощью ассоциативной памяти тегов на 8 слов (по числу секторов в кэш-памяти). Каждая ячейка памяти тегов содержит 13 раз­рядов: 10 старших хранят тег — номер сектора ОП, атри младших разряда — но­мер сектора кэш-памяти, куда отображен данный сектор ОП. Для проверки того, имеется ли копия сектора в кэш-памяти, производится ассоциативный поиск по 10 старшим разрядам памяти тегов. Если произошло совпадение, то для доступа к нужному сектору в памяти данных кэш-памяти используются три младших раз­ряда соответствующей ячейки памяти тегов.
Поскольку размер сектора велик, в рассматриваемой схеме отображения копи­руется не весь сектор целиком, а только требуемый его блок. Для этого к каждой строке, хранимой в кэш-памяти, добавляется один бит информации, называемый битом достоверности, показывающий, относится ли данный блок к текущему сек­тору или в нем осталась информация из сектора, хранившегося на этом месте до смены секторов.
При заполненной кэш-памяти, когда необходимо заменить один из его секто­ров, в ассоциативной памяти тегов делается запись о новом секторе, как при заме­не всего сектора полностью. Фактически же в кэш-память пересылается только тот блок сектора, к которому в данный момент обращается процессор, и в соответ­ствующей строке памяти данных бит достоверности устанавливается в единицу. В то же время биты достоверности остальных строк этого сектора сбрасываются в 0. Далее, по мере копирования других блоков этого сектора, их биты достоверно­сти устанавливаются в единицу.
При такой процедуре заполнения секторов кэш-памяти, в случае обнаружения в ней нужного сектора, предварительно требуется проанализировать состояние бита достоверности соответствующей строки. Если он установлен в 1, значит, обраще­ние к данной ячейке кэш-памяти возможно. При нулевом значении бита достовер­ности сначала производится копирование нужного блока в кэш-память, его бит достоверности устанавливается в единицу, и лишь после этого разрешается дос­туп к указанному адресу в кэш-памяти. ■
В том случае, когда при замене сектора в кэш-памяти необходимо сохранить его старое содержимое в основной памяти, в ОП пересылаются только заменяе­мые блоки сектора.
f Алгоритмы замещения информации в заполненной кэш-памяти
Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямом отображении каждому блоку основной : памяти соответствует только одна определенная строка в кэш-памяти, и никакой ;. иной выбор удаляемой строки здесь невозможен. При полностью и частично ассо-ί: циативных способах отображения требуется какой-либо алгоритм замещения (вы-■·.· бора удаляемой из кэш-памяти строки).
2 58 Глава 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. Запись в основную память про­изводится уже из буфера, а процессор, не дожидаясь ее окончания, может сразу же продолжать свою работу. Конечно, соответствующая логика управления должна заботиться о том, чтобы своевременно «опустошать» заполненный буфер. При ис­пользовании буферизации процессор полностью освобождается от работы с ОП.
Согласно методу обратной записи, слово заносится только в кэш-память. Если соответствующей строки в кэш-памяти нет, то нужный блок сначала пересылается из ОП, после чего запись все равно выполняется исключительно в кэш-память. При замещении строки ее необходимо предварительно переслать в соответствую­щее место основной памяти. Для метода обратной записи, в отличие от алгоритма сквозной записи, характерно то, что при каждом чтении из основной памяти осу­ществляются две пересылки между основной и кэш-памятью.
Hosted by uCoz