Способы отображения основной памяти на кэш.

Алгоритмы поиска и замещения данных в кэше зависят от того, как основная память отображается на кэш.

Используются две схемы отображения:

· случайное отображение;

· детерминированное отображение.

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

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

Электронная реализация такого поиска значительно удорожает кэш-память. Поэтому этот метод используется для обеспечения высокого процента попадания при небольшом объеме кэш-памяти.

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

При детерминированном способе отображения любой элемент основной памяти отображается в одно и то же место кэш-памяти. В этом случае кэш-память разделена на строки, каждая из которых предназначена для хранения одной записи об одном элементе данных и имеет свой номер.

Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (довольно много) адресов оперативной памяти.

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

При поиске данных в кэше используется быстрый прямой доступ к записи по номеру строки, полученному из адреса оперативной памяти из запроса. Кроме того, выполняется дополнительная проверка на совпадение тега с соответствующей частью адреса из запроса.

При совпадении тега с соответствующей частью адреса из запроса констатируется кэш попадание. Если нет констатируется кэш-промах и данные считываются из OI и копируются в кэш.

Во многих современных процессорах кэш-память стоится на основе сочетания этих двух подходов, что позволяет найти компромисс между сравнительно

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

При промахе данные копируются по любому свободному адресу из однозначно заданной группы.

Если свободных адресов в группе нет, то выполняется вытеснение данных. Поскольку кандидатов на выгрузку несколько – все записи из данной группы – алгоритм замещения может учесть интенсивность обращения к данным и тем самым повысить вероятность попаданий в будущем.

Как мы видели, кэш просматривается только с целью согласования содержимого кэша и основной памяти. Если происходит промах, то запросы на запись не вызывают никаких изменений кэша.

В некоторых реализациях кэш-памяти при отсутствии данных в кэше они копируются туда из основной памяти независимо от того, выполняется запрос на чтение или запись.

В соответствии с описанной логикой работы кэш памяти при возникновении запроса сначала просматривается кэш, а затем, если произошел промах, выполняется обращение к основной памяти.

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

В ряде вычислительных систем используется двухуровневое кэширование.

Кэш первого уровня имеет меньший объем и более высокое быстродействие, чем кэш второго уровня. Кэш второго уровня играет роль основной памяти по отношению к кэшу первого уровня.

Сначала делается попытка обнаружить данные в кэше 1-го уровня. Если произошел промах, поиск продолжается в кэше второго уровня. Если нужные данные отсутствуют и здесь, тогда происходит считывание данных из основной памяти.

При считывании данных из ОП происходит их копирование в кэш второго уровня, а если данные считываются из кэша второго уровня, то они копируются в кэш первого уровня.

Кэши разных уровней могут согласовывать данные разными способами. Например, в процессоре Pentium кэш первого уровня использует кэш первого уровня - обратную запись.

Заметим, что мы рассматривали системы, в которых на каждом уровне имеется только один кэш. Однако существует целый ряд систем – распределенных систем обработки информации, в которых на каждом уровне имеется несколько кэшей.