Алгоритм поиска данных в кэше и алгоритм замещения данных во многом зависят от того, каким образом основная память отображается на кэш, то есть как данные из основной памяти размещаются в кэш-памяти. Если в качестве основной памяти выступает ОП, то при кэшировании данных из нее используются два основных способа отображения:
1. Случайное отображение;
2. Детерминированное отображение.
В первом способе элемент ОП размещается в любом месте кэш-памяти. Чтобы в дальнейшем можно было бы найти требуемые данные в кэше, они записываются туда с адресом, который имели в ОП, то есть структура кэш-памяти в этом случае имеет вид:
| Адрес в ОП | Данные | Управляющая информация |
| … | … | … |
При каждом запросе к ОП осуществляется ассоциативный поиск в кэш-памяти, адрес ОП из запроса параллельно сопоставляется со всеми записями кэш-памяти. Признак, по которому выполняется параллельное сравнение, называется тегом. В качестве тега выступает адрес данных в ОП, присутствующий в запросе. В кэш-памяти со случайным отображением вытеснение прежних данных выполняется только в том случае, когда вся кэш-память заполнена, и в ней нет свободного места, при этом выбор записей на выгрузку осуществляется среди всех данных кэша. Используется алгоритм замещения, которое строится на тех же принципах, что и алгоритмы замещения страниц в системах с ВП. Например, выгружаются данные, к которым дольше всего не было обращений, или данные, количество обращений к которым было наименьшим.
Во втором случае, любой элемент ОП всегда отображается в одно и то же место кэш-памяти, при этом кэш-память делится на строки, каждая из которых предназначена для хранения по крайней мере одной записи об одном элементе данных. На практике, таких элементов может быть несколько. Все строки нумеруются подряд, и между номерами строк кэш-памяти и адресами ячеек ОП устанавливается соответствие типа «один ко многим», то есть одному номеру строки в кэш-памяти соответствует несколько адресов ОП. В качестве средства отображения в данном случае может использоваться простое выделение нескольких младших разрядов из адреса ОП, которые интерпретируются как номер строки в кэш-памяти. Такой способ отображения называется прямым отображением адреса ОП на кэш. Например, если объем кэш-памяти составляет 210=1024 записи (строки), то все они могут быть пронумерованы числами от 0 до 1023, и следовательно, любой адрес ОП может быть отображен на соответствующую строку кэш-памяти выделением 10 младших разрядов из адреса ОП, который присутствует в запросе.
При поиске информации в кэше используется прямой доступ к записи кэш-памяти по её номеру, который выделяется из адреса ОП. В найденной ячейке кэш-памяти могут размещаться данные из нескольких ячеек ОП, младшие разряды адреса которых совпадают с номером строки кэш-памяти. Поэтому для обеспечения достоверного обращения к кэш-памяти должна выполняться дополнительная проверка. С этой целью каждая строка, то есть запись кэш-памяти, дополняется специальным полем, в котором хранится тег. Он представляет собой код старшей части адреса ОП.
Значения всех тегов записывается в дополнительную часть кэш-памяти, которая называется памятью тегов, а значение данных ячеек кэш-памяти записывается в другой части, которая называется памятью данных.
При совпадении значения тега из памяти тегов с содержимым поля тегов в адресе ОП фиксируется кэш-попадание. Если произошел кэш-промах, то данные по соответствующему адресу считываются из ОП и копируются в кэш. Копирование выполняется путем прямой записи данных в ячейку кэш-памяти по её номеру, который представлен младшими разрядами адреса ОП. При этом, если ячейка кэш-памяти, в которую должны быть скопированы данные, содержит другие данные, то они теряются, то есть вытесняются из кэша. В этом случае, процесс замещения данных в кэш-памяти отличается от процесса замещения в кэше со случайным отображением. Отличие состоит в том, что во-первых, вытеснение данных может происходить не только в случае отсутствия свободного места в кэше. Во-вторых, выбор данных на замещение не выполняется.
Данный способ отображения характеризуется простотой реализации и сравнительно небольшой стоимостью.
В современных процессорах кэш-память строится на основе сочетания способов случайного и прямого отображения, что позволяет найти компромисс между относительно невысокой стоимостью кэш-памяти в прямом отображением и эффективностью алгоритма замещения в кэш-памяти со случайным отображением. При подобном смешанном подходе построения кэш-памяти любой адрес ОП отображается не точно на один адрес кэш-памяти, а на группу адресов.
В кэш-памяти создаются группы запоминающих ячеек, в каждую из которых объединяется несколько записей. Число записей в группах одинаково, они нумеруются подряд. Поиск в кэше осуществляется вначале по номеру группы, который читается из младших разрядов адреса ОП. Далее, поиск продолжается в пределах записей найденной группы путем ассоциативного, то есть параллельного просмотра всех записей с целью обнаружения совпадения старших разрядов адреса ОП с содержимым группы ячеек, хранящих значения тегов. В случае кэш-промаха данные копируются по любому свободному адресу данной группы. Если свободных записей в группе нет, то осуществляется замещение данных на основе одного из алгоритмов замещения.
