Вопрос 20: Типы отображения адресов в кэш
1. С прямым отображением адресов
Для размещения в кэш-памяти данных блока b в место m используется часть разрядов адреса блока i. Т.к. мы не можем осуществлять полностью ассоциативное сравнение, то часть разрядов адреса блока разбивают на 2 части, где первая часть будет ячейка ассоциативной памяти, где хранится место требуемого блока (i – индекс) и вторая часть t – тег, определяющий отличие одного блока от другого при его хранении в одном и том же месте. d – смещение внутри блока. Преобразование адреса блока в место М сводится к выборке разрядов i из адреса.Индекс и смещение внутри блока суммируются и являются адресом блока в памяти данных. Разряды адреса фактически являются номером ячейки, где хранится тег того блока, который находится в кэш-памяти. Из памяти тегов, которая имеет обычную линейную организацию, выбирается значение, называемое тегом, хранящимся в кэш-памяти. Этот тег поступает в устройство сравнения, которое проверяет, равен ли этот тег тегу, хранящемуся в этом блоке. Если они совпадают, то кэш-попадание, иначе кэш-промах.
Недостаток: При частом обращении в разные области основной памяти, отображающиеся в одном и том же месте, эффективность кэш-памяти ухудшается.
2. С множественно-ассоциативным отображением адресов
Реализован компромисс между полностью ассоциативной кэш-памятью и кэш-памятью с прямым отображением: ОП разбивается на блоки, объединенные в области (как при прямом отображении), КП разбивается на группы мест по числу блоков в области, т.е. для каждого индекса имеется несколько мест, но в разных группах. Тэги в этом случае для определения кэш-попадания подвергаются ассоциативному сравнению (как при полностью ассоциативной памяти).
Как и в памяти с прямым отображением имеется ЗУ с линейной организацией памяти, которое называется статическое ЗУ тегов. Индекс определяет группу тегов, то есть произошло как бы расслоение кэш-памяти. Эти теги подвергаются ассоциативному сравнению с тегом находящимся в адресе. Теги поступают на цифровые компараторы сравнения тегов. После сравнения теги поступают в шифратор, который говорит о том, в каком месте группы находится требуемый блок или что этого блока нет. Если блок имеется, выдается номер места в этой группе. С шифратора снимаются 2 сигнала, т.е. решаются две задачи:
1.) Выбор свободного места в кэш-памяти, если оно есть.
2.) Если все места заняты, выбирается замещаемое место путем анализа тегов, содержащее бит обращения (модификации) и формирует номер места, которое можно использовать для размещения нового блока, предварительно сохранив хранящийся, если установлен бит модификации в теге.
Допустим контроллер обнаружил кэш-промах, т.е. сработала эта схема и обнаружила, что нет требуемого блока в кэш-памяти, но вся кэш-память свободна или занята, и имеются некие свободные места в той группе, которая предназначена для хранения этого блока. Для выбора свободных мест шифратор должен выдавать не только сигнал о том, что блока нет, но и сигнал, определяющий свободно место или занято. Если свободных мест нет, то в этом случае можно использовать в памяти тегов дополнительные теги, т.е. хранить там не только теги мест, но еще и специальные флаги: W – в это место произведена запись, F – частота обращения к блоку (контроллер должен с некой периодичностью сбрасывать этот флаг в 0), B.
Шифратор дополнительно решает выбор свободного места в кэш-памяти. Для этого может использоваться специальный бит в теговой памяти В – место занято. Если все места заняты и установлен бит записи W, шифратор реализует стратегию замещения. Для этого используются такие биты, как W — место модифицировано и F – к месту было обращение процессора. Биты F контроллером периодически сбрасываются в 0.
Недостатки:
1.) Эта организация самая сложная, но она реально используется.
2.) Требуется большой объем памяти тегов.
3.) Усложнена реализация стратегий обновления, замещения и выбора, т.е. необходимы специальные схемы для определения свободных мест в кэш-памяти, для выбора места подлежащего замещению (обновлению), а также схем, сохраняющих изменённый блок кэш-памяти в основной памяти.
3. С полностью ассоциативным отображением адресов
При полностью ассоциативном размещении блоков в кэш-памяти допускается размещение каждого блока b из ОП в любом месте m кэш-памяти. Механизм преобразования адресов должен быстро дать ответ, существует ли копия блока b в кэш-памяти, и, если существует, то в каком месте m она находится. Исходя из этого рассмотрим структуру полностью ассоциативной кэш-памяти.
При полностью ассоциативном размещении блоков в кэш-памяти допускается размещение каждого блока b из ОП в любом месте m кэш-памяти.
Механизм преобразования адресов должен быстро дать ответ, существует ли копия блока b в кэш-памяти, и, если существует, то в каком месте m она находится.
Исходя из этого рассмотрим структуру полностью ассоциативной кэш-памяти.
А – это адрес, состоящий из двух частей: номера блока и смещения, требуемых данных внутри этого блока. Часть адреса b передается в ассоциативную память тегов. Блок поступает и на выходе этой памяти имеется схема опознавания действительного или недействительного номера места. Число ячеек в памяти тегов равно числу мест в кэш-памяти с линейной организации, но эта кэш-память возвращает номер места, где хранится нужный блок.
Недостаток: необходимо использовать ассоциативную память, реализующую большое число сравнений для определения кэш-попаданий и место блока в кэш-памяти.
В ассоциативной памяти тегов фактически существует две части: первая часть, которая подвергается ассоциативному сравнению, то есть предъявили входные данные b, а она отвечает путем одновременного сравнивания всех тегов ячеек, есть ли ячейка, которая ассоциирована с этим номером блоком или нет. Для последовательного сравнивания нет времени (10нс). Получается, сколько ячеек, столько компараторов адреса. Вся ассоциативная память строится по принципу распараллеливания в пространстве.