Кэш-память 251
На эффективность применения кэш-памяти в иерархической системе памяти влияет целый ряд моментов. К наиболее существенным из них можно отнести:
емкость кэш-памяти;
•    размер строки;
•    способ отображения основной памяти на кэш-память;
•    алгоритм замещения информации в заполненной кэш-памяти;
•    алгоритм согласования содержимого основной и кэш-памяти;
•    число уровней кэш-памяти.
Емкость кэш-памяти
Выбор емкости кэш-памяти — это всегда определенный компромисс. С одной сторо­ны, кэш-память должна быть достаточно мала, чтобы ее стоимостные показатели были близки к величине, характерной для ОП. С другой — она должна быть достаточно большой, чтобы среднее время доступа в системе, состоящей из основной и кэш-па­мяти, определялось временем доступа к кэш-памяти. В пользу уменьшения размера кэш-памяти имеется больше мотивировок. Так, чем вместительнее кэш-память, тем больше логических схем должно участвовать в ее адресации. Как следствие, ИМС кэш-памяти повышенной емкости работают медленнее по сравнению с микросхема­ми меньшей емкости, даже если они выполнены по одной и той же технологии.
Реальная эффективность использования кэш-памяти зависит от характера ре­шаемых задач, и невозможно заранее определить, какая ее емкость будет дей­ствительно оптимальной. Рисунок 5.25, а иллюстрирует зависимость вероятности промахов от емкости кэш-памяти для трех программ А, В и С [195]. Несмотря на очевидные различия, просматривается и общая тенденция: по мере увеличения емкости кэш-памяти вероятность промахов сначала существенно снижается, но при достижении определенного значения эффект сглаживается и становится не­существенным. Установлено, что для большинства задач близкой к оптимальной является кэш-память емкостью от 1 до 512 Кбайт.
Рис. 5.25. Зависимость вероятности промахов от: а —емкости кэш-памяти;
б — размера строки
25 2 Глава 5. Память
Размер строки
Еще одним важным фактором, влияющим на эффективность использования кэш­памяти, служит размер строки. Когда в кэш-память помещается строка, вместе с требуемым словом туда попадают и соседние слова. По мере увеличения размера строки вероятность промахов сначала падает, так как в кэш, согласно принципу локальности, попадает все больше данных, которые понадобятся в ближайшее время. Однако вероятность промахов начинает расти, когда размер строки стано­вится излишне большим (рис. 5.25, б). Объясняется это тем, что:
•   большие размеры строки уменьшают общее количество строк, которые можнс загрузить в кэш-память, а малое число строк приводит к необходимости частой их смены;
•   по мере увеличения размера строки каждое дополнительное слово оказываете дальше от запрошенного, поэтому такое дополнительное слово менее вероятно понадобится в ближайшем будущем.
Зависимость между размером строки и вероятностью промахов во многом оп­ределяется характеристиками конкретной программы, из-за чего трудно рекомен­довать определенное значение величины строки. Исследования [183, 195] пока­зывают, что наиболее близким к оптимальному можно признать размер строки, равный 4-8 адресуемым единицам (словам или байтам). На практике размер стро­ки обьгано выбирают равным ширине шины данных, связывающей кэш-память с основной памятью.
Способы отображения оперативной памяти на кэш-память
Сущность отображения блока основной памяти на кэш-память состоит в копиро­вании этого блока в какую-то строку кэш-памяти, после чего все обращения к бло­ку в ОП должны переадресовываться на соответствующую строку кэш-памяти. Удачным может быть признан лишь такой способ отображения, который одновре­менно отвечает трем требованиям: обеспечивает быструю проверку кэш-памяти на наличие в ней копии блока основной памяти; обеспечивает быстрое преобразо­вание адреса блока ОП в адрес строки кэша; реализует достижение первых двух требований наиболее экономными средствами.
Для облегчения понимания комплекса вопросов, возникающих при выборе способа отображения оперативной памяти на кэш-память, будем рассматривать систему, состоящую из основной памяти емкостью 256 Кслов, и кэш-памяти емко­стью 2 Кслова. Для адресации каждого слова основной памяти необходим 18-разряд­ный адрес (218 =256К). ОП разбивается на блоки по 16 слов в каждом, следовательно, ее удобно рассматривать как линейную последовательность из 16 384 = 214 блоков. При такой организации 18-разрядный адрес можно условно разделить на две час­ти: младшие 4 разряда определяют адрес слова в пределах блока, а старшие 14 — номер одного из 16 384 блоков. Эти старшие 14 разрядов в дальнейшем будем на­зывать адресом блока основной памяти. В свою очередь, для адресации любого слс в кэш-памяти требуется 11 -разрядный адрес (Ϊ1 = 2К). Кэш-память разбита на стро­ки такого же размера, что и в ОП (напомним, что применительно к кэш-памяти
Кэш-память 2 5 3
вместо слова «блок» принято использовать термин «строка»), то есть содержит 128 = 27 строк. 11-разрядный адрес слова в кэш-памяти также можно представить состоящим из двух частей: адреса слова в строке (4 младших разряда) и адреса строки кэш-памяти (7 старших разрядов).
Поскольку ЦП всегда обращается к ОП (кэш-память для ЦП невидима) и фор­мирует для этого 18-разрядный адрес, необходим механизм преобразования тако­го адреса в 11-разрядный адрес слова в кэше. Так как расположение слов в блоке ОП и строке кэш-памяти идентично, для доступа к конкретному слову в блоке ОП или в строке кэш-памяти можно использовать младшие 4 разряда 18-разрядного адреса. Следовательно, остается лишь задача преобразования 14-разрядного адре­са блока основной памяти в 7-разрядный адрес строки кэша.
Известные варианты отображения основной памяти на кэш можно свести к трем видам: прямому, полностью ассоциативному и частично-ассоциативному, причем последний имеет две модификации — множественно-ассоциативное отображение и отображение секторов.
Прямое отображение
При прямом отображении адрес строки / кэш-памяти, на которую может быть ото­бражен блоку из ОП, однозначно определяется выражением: i =j mod т, где т — общее число строк в кэш-памяти. В нашем примере i =j mod 128, где i может при­нимать значения от 0 до 127, а адрес блокау — от 0 до 16 383. Иными словами, на строку кэша с номером i отображается каждый 128-й блок ОП, если отсчет начи­нать с блока, номер которого равен L Это поясняется рис. 5.26, где основная па­мять условно представлена в виде двухмерного массива блоков, в котором количе­ство рядов равно числу строк в кэш-памяти, а в каждом ряду последовательно перечислены блоки, переадресуемые на одну и туже строку кэш-памяти.
Рис. 5.26. Организация кэш-памяти с прямым отображением
При реализации такого отображения 14-разрядный адрес блока основной па­мяти условно разбивается на два поля. Логика кэш-памяти интерпретирует эти 14 бит как 7-разрядный тег и 7-разрядное поле строки. Поле строки указывает на
254 Глава 5. Память
одну из 128 = 27 строк кэш-памяти, а именно на ту, куда может быть отображен блок с заданным адресом. В свою очередь, поле тега определяет, какой именно из списка блоков, закрепленных заданной строкой кэша, будет отображен. Когда блок фактически заносится в память данных кэша, в память тегов кэш-памяти необхо­димо записать тег этого блока, чтобы отличить его от других блоков, которые мо­гут быть загружены в ту же строку кэша. Тегом служат семь старших разрядов адреса блока.
. Прямое отображение — простой и недорогой в реализации способ отображе­ния. Основной его недостаток — жесткое закрепление за определенными блоками ОП одной строки в кэше. Поэтому если программа поочередно обращается к сло­вам из двух различных блоков, отображаемых на одну и тут же строку кэш-памя­ти, постоянно станет происходить обновление данной строки и вероятность попа­дания будет низкой.
Полностью ассоциативное отображение
Полностью ассоциативное отображение позволяет преодолеть недостаток прямог разрешая загрузку любого блока ОП в любую строку кэш-памяти. Логика управ­ления кэш-памяти вьщеляет в адресе ОП два поля: поле тега и поле слова. Поле тега совпадает с адресом блока основной памяти. Для проверки наличия копии блока в кэш-памяти логика управления кэша должна одновременно проверить те­ги всех строк на совпадение сполем тега адреса. Этому требованию наилучшим образом отвечает ассоциативная память, то есть тег должен храниться в ассоциа­тивной памяти тегов кэша. Логика работы такой кэш-памяти иллюстрируется рис. 5.27.
Рис. 5.27. Кэш-память с ассоциативным отображением Ассоциативное отображение обеспечивает гибкость при выборе строки для вновь записываемого блока. Принципиальный недостаток этого способа — необ­ходимость использования дорогостоящей ассоциативной памяти.
Кэш-память 2 5 5
Множественно-ассоциативное отображение
Множественно-ассоциативное отображение относится к группе методов частич­но-ассоциативного отображения. Оно является одним из возможных компромис­сов, сочетающим достоинства прямого и ассоциативного способов отображения и, в известной мере, свободным от их недостатков. Кэш-память (как тегов, так и дан­ных) разбивается на ν подмножеств (в дальнейшем будем называть такие подмно­жества модулями), каждое из которых содержит к строк (принято говорить, что модуль имеет к входов). Зависимость между модулем и блоками ОП такая же, как и при прямом отображении: на строки, входящие в модуль i, могут быть отображе­ны только вполне определенные блоки основной памяти, в соответствии с соотно­шением i =j mod v, где у — адрес блока ОП. В то же время размещение блоков по строкам модуля — произвольное, и для поиска нужной строки в пределах модуля используется ассоциативный принцип.
Рис. 5.28. Кэш-память с множественно-ассоциативным отображением
На рис. 5.28 показан пример четырехвходовой кэш-памяти с множественно-ас­социативным отображением. Память данных кэш-памяти разбита на 32 модуля по 4 строки в каждом. Память тегов содержит 32 ячейки, в каждой из которых может храниться 4 значения тегов (по одному на каждую строку модуля). 14-разрядный адрес блока ОП представляется в виде двух полей: 9-разрядного поля тега и 5-разрядного поля номера модуля. Номер модуля однозначно указывает на один из модулей кэш-памяти. Он также позволяет определить номера тех блоков ОП, которые можно отображать на этот модуль. Такими являются блоки ОП, номера которых при делении на 25 дают в остатке число, совпадающее с номером данного модуля кэш-памяти! Так, блоки 0,32,64,96 и т. д. основной памяти отображаются на модуль с номером 0; блоки 1, 33, 65, 97 и т. д. отображаются на модуль 1 и т. д. Любой из блоков в последовательности может быть загружен в любую из четырех строк соответствующего модуля.
При такой постановке роль тега выполняют 9 старших разрядов адреса блока ОП, в которых содержится порядковый номер блока в последовательности бло­ков, отображаемых на один и тот же модуль кэш-памяти. Например, блок 65 в по­следовательности блоков, отображаемых на модуль 1, имеет порядковый номер 2 (отсчет ведется-от 0).
При обращении к кэш-памяти 5-разрядный номер модуля указывает на конк­ретную ячейку памяти тегов (это соответствует прямому отображению). Далее
256 Глава 5. Память
производится параллельное сравнение каждого из четырех тегов, хранящихся в этой ячейке, с полем тега поступившего адреса, то есть поиск нужного тега среди четырех возможных осуществляется ассоциативно.
В предельных случаях, когда v=m,k= 1, множественно-ассоциативное отобра­жение сводится к прямому, а при v= 1,к = т — к ассоциативному.
Наиболее общий вид организации множественно-ассоциативного отображе­ния — использование двух строк на модуль (v=m/2, к =2). Четырехвходовая мно­жественно-ассоциативная кэш-память (v = т/4, к = 4) дает дополнительное улуч­шение за сравнительно небольшую дополнительную цену [122,164]. Дальнейшее увеличения числа строк в модуле существенного эффекта не привносит.
Следует отметить, что именно этот способ отображения наиболее широко рас­пространен в современных микропроцессорах.
Отображение секторов
Один из первых вариантов частично-ассоциативного отображения, реализован­ный в модели 85 семейства ВМ IBM 360. Согласно данному методу, основная па­мять разбивается на секторы, состоящие из фиксированного числа последователь­ных блоков. Кэш-память также разбивается на секторы, содержащие такое же число строк. Расположение блоков в секторе ОП и секторе кэш-памяти полностью со­впадает. Отображение сектора на кэш-память осуществляется ассоциативно, то есть любой сектор из ОП может быть помещен в любой сектор кэш-памяти. Логику работы кэша поясняет рис. 5.29.
Рис. 5.29. Кэш-память с отображением секторов Здесь сектор состоит из 16 =24 блоков по 16 слов, и основная память содержит 1024 = 210 сектора. В 14-разрядном адресе блока основной памяти старшие 10 раз­рядов показывают номер сектора, а младшие 4 — номер блока внутри сектора В свою очередь, кэш-память состоит из 8= 23 секторов, и 7-разрядный адрес стро­ки в кэше включает в себя адрес сектора кэша (3 старших разряда) и номер блока внутри сектора (4 младших разряда). Ввиду того что расположение блоков в сек-
Кэш-память 2 5 7
торах основной и кэш-памяти совпадает, для выбора блока внутри сектора в обоих случаях можно использовать четыре младших разряда адреса блока ОП. В резуль­тате задача преобразования адресов сводится к переходу от 10-разрядного номера сектора основной памяти к трехразрядному номеру сектора в кэш-памяти. Такое преобразование осуществляется с помощью ассоциативной памяти тегов на 8 слов (по числу секторов в кэш-памяти). Каждая ячейка памяти тегов содержит 13 раз­рядов: 10 старших хранят тег — номер сектора ОП, атри младших разряда — но­мер сектора кэш-памяти, куда отображен данный сектор ОП. Для проверки того, имеется ли копия сектора в кэш-памяти, производится ассоциативный поиск по 10 старшим разрядам памяти тегов. Если произошло совпадение, то для доступа к нужному сектору в памяти данных кэш-памяти используются три младших раз­ряда соответствующей ячейки памяти тегов.
Поскольку размер сектора велик, в рассматриваемой схеме отображения копи­руется не весь сектор целиком, а только требуемый его блок. Для этого к каждой строке, хранимой в кэш-памяти, добавляется один бит информации, называемый битом достоверности, показывающий, относится ли данный блок к текущему сек­тору или в нем осталась информация из сектора, хранившегося на этом месте до смены секторов.
При заполненной кэш-памяти, когда необходимо заменить один из его секто­ров, в ассоциативной памяти тегов делается запись о новом секторе, как при заме­не всего сектора полностью. Фактически же в кэш-память пересылается только тот блок сектора, к которому в данный момент обращается процессор, и в соответ­ствующей строке памяти данных бит достоверности устанавливается в единицу. В то же время биты достоверности остальных строк этого сектора сбрасываются в 0. Далее, по мере копирования других блоков этого сектора, их биты достоверно­сти устанавливаются в единицу.
При такой процедуре заполнения секторов кэш-памяти, в случае обнаружения в ней нужного сектора, предварительно требуется проанализировать состояние бита достоверности соответствующей строки. Если он установлен в 1, значит, обраще­ние к данной ячейке кэш-памяти возможно. При нулевом значении бита достовер­ности сначала производится копирование нужного блока в кэш-память, его бит достоверности устанавливается в единицу, и лишь после этого разрешается дос­туп к указанному адресу в кэш-памяти. ■
В том случае, когда при замене сектора в кэш-памяти необходимо сохранить его старое содержимое в основной памяти, в ОП пересылаются только заменяе­мые блоки сектора.
f Алгоритмы замещения информации в заполненной кэш-памяти
Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямом отображении каждому блоку основной : памяти соответствует только одна определенная строка в кэш-памяти, и никакой ;. иной выбор удаляемой строки здесь невозможен. При полностью и частично ассо-ί: циативных способах отображения требуется какой-либо алгоритм замещения (вы-■·.· бора удаляемой из кэш-памяти строки).
Hosted by uCoz