Организация кэш-памяти современных процессоров

Федеральное агентство по образованию

Государственное образовательное  учреждение

высшего профессионального образования

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра прикладной математики

КУРСОВАЯ РАБОТА

По дисциплине: «Архитектура ЭВМ»

На тему: «Организация кэш-памяти современных процессоров»

Выполнил: студент группы ММ-313 Тюкавкина Н.С.

Дата сдачи: ____________________

Работа защищена с оценкой: ____________________

Руководитель: Лепинин Е.Ф. ______________

ЧЕЛЯБИНСК 2008

АННОТАЦИЯ

Память ЭВМ всегда считалась одним из «узких» мест, поэтому проблемы повышения ее производительности никогда не выпадали из внимания разработчиков архитектуры ЭВМ и системного программного обеспечения. Фактически, общим решением, используемым для достижения этой цели, является многоуровневая организация системы памяти, на разных уровнях которой применяются несколько различные механизмы управления.

 

СОДЕРЖАНИЕ

Введение 3

1. Соответствие между строками кэша и блоками оперативной памяти 7
2. Функция прямого отображения 8
3. Ассоциативная функция отображения 10
4. Секционированная ассоциативная функция отображения 12
5. Алгоритм замены строк кэша 14
6. Целостность информации в кэше и оперативной памяти 16
7. Размер блока 19
8. Кэширование в современных процессорах 21
9. Управление кэшированием 26
10. Кэш трасс 35
11. Общая организация и способ хранения трасс в кэше 38
12. Сравнение с альтернативной организацией кэша инструкций 42

Заключение 46

Список литературы 47

 

ВВЕДЕНИЕ

Основная память компьютеров  реализуется на относительно медленной  динамической памяти (DRAM), обращение к ней приводит к простою процессора – появляются такты ожидания (wait states). Статическая память (SRAM), построенная, как и процессор, на триггерных ячейках, по своей природе способна догнать современные процессоры по быстродействию и сделать ненужными такты ожидания (или хотя бы сократить их количество). Разумным компромиссом для построения экономичных и производительных систем явился иерархический способ организации оперативной памяти. Идея заключается в сочетании основной памяти большого объема на DRAM с относительно небольшой кэш-памятью на быстродействующих микросхемах SRAM.

В переводе слово кэш (cache) означает «тайный склад», «тайник». Тайна этого склада заключается  в его «прозрачности» – адресуемой области памяти для программы он не добавляет. Кэш является дополнительным быстродействующим хранилищем копий блоков информации из основной памяти, вероятность обращения к которым в ближайшее время велика. Кэш не может хранить копию всей основной памяти, поскольку его объем во много раз меньше основной памяти. Он хранит лишь ограниченное количество блоков данных и каталог (cache directory) – список их текущего соответствия областям основной памяти. Кроме того, кэшироваться может не вся память, доступная процессору.

При каждом обращении  к памяти контроллер кэш-памяти по каталогу проверяет, есть ли действительная копия затребованных данных в кэше. Если она там есть, то это случай кэш-попадания (cache hit), и данные берутся из кэш-памяти. Если действительной копии там нет, это случай кэш-промаха (cache miss), и данные берутся из основной памяти. В соответствии с алгоритмом кэширования, блок данных, считанный из основной памяти, при определенных условиях заместит один из блоков кэша. От интеллектуальности алгоритма замещения зависит процент попаданий и, следовательно, эффективность кэширования. Поиск блока в списке должен производиться достаточно быстро, чтобы «задумчивостью» в принятии решения не свести на нет выигрыш от применения быстродействующей памяти. Обращение к основной памяти может начинаться одновременно с поиском в каталоге, а в случае попадания – прерываться (архитектура Look aside). Это экономит время, но лишние обращения к основной памяти ведут к увеличению энергопотребления. Другой вариант: обращение к внешней памяти начинается только после фиксации промаха (архитектура Look Through), при этом теряется, по крайней мере, один такт процессора, зато экономится энергия.

В современных компьютерах  кэш обычно строится по двухуровневой схеме. Первичный кэш (L1 Cache) встроен во все процессоры класса 486 и выше; это внутренний кэш. Объем этого кэша невелик (8-32 Кбайт). Чтобы повысить производительность, для данных и команд часто используется раздельный кэш (так называемая Гарвардская архитектура – противоположность Принстонской, использующей общую память для команд и данных). Вторичный кэш (L2 Cache) для процессоров 486 и Pentium является внешним (устанавливается на системной плате), а у Р6 и выше располагается в одной упаковке с ядром и подключается к специальной внутренней шине процессора.

Кэш-контроллер должен обеспечивать когерентность (coherency) – согласованность данных кэш-памяти обоих уровней с данными в основной памяти, при том условии, что обращение к этим данным может производиться не только процессором, но и другими устройствами. Следует также учесть, что процессоров может быть несколько, и у каждого может быть свой внутренний кэш.

Контроллер кэша оперирует  строками (cache line) фиксированной длины. Строка может хранить копию блока  основной памяти, размер которого, естественно, совпадает с длиной строки. С каждой строкой кэша связана информация об адресе скопированного в нее блока основной памяти и ее состоянии. Строка может быть действительной (valid) – это означает, что в текущий момент времени она достоверно отражает соответствующий блок основной памяти, или недействительной. Информация о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы), и о ее состоянии называется тегом (tag) и хранится в связанной с данной строкой ячейке специальной памяти тегов (tag RAM). В операциях обмена с основной памятью обычно строка участвует целиком (несекторированный кэш), для процессоров 486 и выше длина строки совпадает с объемом данных, передаваемых за один пакетный цикл. Возможен и вариант секторированного (sectored) кэша, при котором одна строка содержит несколько смежных ячеек – секторов, размер которых соответствует минимальной порции обмена данных кэша с основной памятью. При этом в записи каталога, соответствующей каждой строке, должны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, поскольку большее количество бит каталога отводится под тег, и выгоднее использовать дополнительные биты действительности, чем увеличивать глубину индекса (количество элементов) каталога.

Основные характеристики кэш-памяти представлены в таблице №1.

 

Таблица №1: функциональные характеристики блоков кэш-памяти

Характеристика	Набор параметров / возможное  значение
Объем кэша
Метод отображения	Прямой Ассоциативный Секционированный ассоциативный
Алгоритм замены	LRU (least recently used) – заменяется строка, к которой дольше всего не обращался процессор FIFO (first in, first out) – заменяется строка, записанная в кэш раньше остальных LFU (least frequently used) – заменяется реже всего используемая строка Случайный – заменяется случайно выбранная строка
Политика поддержания  информационной безопасности
Размер блока (строки кэша)
Структурная организация  блока	Одно или двухуровневый Единый или разделённый

 

1. СООТВЕТСТВИЕ МЕЖДУ СТРОКАМИ КЭША И БЛОКАМИ ОПЕРАТИВНОЙ ПАМЯТИ

Поскольку количество строк  кэша значительно меньше количества блоков оперативной памяти, при разработке кэша необходимо выбрать какой-либо способ, позволяющий установить соответствие между строками кэша и блоками оперативной памяти, т.е. позволяющий как можно проще и быстрее выяснить, какой блок памяти размещен в той или иной строке кэша. Для краткости такой способ называют функцией отображения (mapping function). Выбор того или иного варианта функции отображения существенно влияет на структурную организацию блока кэш-памяти.

На сегодняшний день существуют три варианта решения  этой проблемы: прямой, ассоциативный  и секционированный ассоциативный. Ниже мы рассмотрим каждый из них – сначала проанализируем принцип работы алгоритма, а затем опишем способы его реализации. Будем считать, что блок кэш-памяти имеет следующие параметры:

• объем кэша 64 Кбайт;
• размер блока, которым обмениваются кэш и оперативная память, 4 байт; это означает, что кэш состоит из 16К =214 строк по 4 байт в каждой;
• объем оперативной памяти 16 Мбайт, т.е. длина кода адреса – 24 бит

Таким образом, с точки зрения обмена информацией с кэшем оперативная память состоит из 4М блоков по 4 байт в каждом.

Простейший вариант функции  отображения – прямое отображение (direct mapping). При таком способе за каждым блоком оперативной памяти «закрепляется» фиксированная строка кэша. Схема на рис. 4.17 поясняет общий принцип прямого отображения. Для определения номера строки кэша i используется простое соотношение: i =j mod m, где j – номер блока в оперативной памяти; m – общее количество строк в кэше.

 

2. ФУНКЦИЯ ПРЯМОГО ОТОБРАЖЕНИЯ

Функция прямого отображения, использующая в качестве исходной информации адрес слова, довольно просто реализуется. Схема поиска информации в кэше рассматривает переданный процессором код адреса слова как состоящий из трех полей. Младшие w бит идентифицируют слово (в нашем случае – байт, поскольку длина слова равна 1 байт) внутри блока оперативной памяти. Старшие s бит определяют один из 2^s блоков в оперативной памяти. В схемах управления кэшем эти s бит разбиваются на два поля: старшие s-r бит – поле тэга, а младшие r бит – поле номера строки, которое однозначно задает одну из m=2^r строк кэша. Результат реализации такой функции отображения следующий:

Строка кэша	Блок оперативной памяти
0	0, m, 2m, ..., 2s-m
1	1, m+1, 2m+1, ..., 2s-m+1
…	…
т-1	m-1, 2m+1, 3m+1, ..., 2s-1

Таким образом, использование  части разрядов кода адреса в качестве номера строки кэша устанавливает однозначное (но не взаимно однозначное) соответствие между блоком оперативной памяти и строкой кэша. Каждому блоку памяти назначена своя строка кэша, но каждая строка кэша может принимать информацию из разных блоков. Какой именно блок в текущий момент находится в данной строке, определяет поле тэга – старшие s-r разрядов кода адреса.

На рисунке №2 показано, как будет выглядеть применение прямой функции отображения в той системе, параметры которой мы оговорили в начале этого раздела. В системе, взятой для примера, m=16К=2¹⁴ и i=о mod 2¹⁴. При таких параметрах функция прямого отражения дает следующие результаты:

Строка кэша	Начальный адрес соответственного блока оперативной памяти
0000	000000, 010000 , ..., FF0000
0001	000004, 010004 , ..., FF0004
...
3FFF	00FFFC, 01FFFC , ..., FFFFFC

Важно, что все блоки  оперативной памяти, назначенные  одной и той же строке кэша, имеют  разные значения тэга – значения восьми старших двоичных (двух шестнадцатеричных) разрядов адреса. Например, блоки с адресами 000000, 010000, ..., FF0000 имеют, соответственно, значения тэгов 00, 01, ..., FF.

Рассмотрим, как будет  выполняться операция чтения при  использовании в кэше прямой функции  отображения. От процессора поступает  запрос байта, сопровождаемый 24-разрядным кодом адреса. Из него извлекается 14-разрядное поле номера строки, которое однозначно указывает, в какой строке кэша следует искать затребованный байт. Если значение в поле тэга переданного адреса (старшие 8 разрядов) совпадает со значением в поле тэга этой строки, то младшие 2 разряда кода адреса указывают, какой из четырех байтов этой строки следует передать процессору. В противном случае старшие 22 разряда кода адреса (поле тэга плюс поле номера строки) используются для обращения к оперативной памяти и, дополненные нулями в двух младших разрядах, задают начальный адрес блока размером в 4 байт.

Прямую функцию отображения  довольно просто реализовать в схеме управления блоком кэш-памяти, но у нее есть существенный недостаток (который, как это почти всегда бывает, является продолжением ее достоинств). Фиксированное назначение строк кэша блокам оперативной памяти может привести к тому, что одни строки кэша будут обновляться очень часто, в то время как другие вообще не используются, поскольку к ним процессор не обращается. Так, если в программе имеется несколько повторяющихся обращений к двум разным блокам, отображаемым на одну и ту же строку кэша, эти блоки будут постоянно