Принцип действия кэш-памяти

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

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

Рис. 6.2. Схема функционирования кэш-памяти

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

Вероятность обнаружения данных в кэш-памяти зависит от разных факторов, таких, например, как объем кэш-памяти, объем кэшируемой памяти, алгоритм замещения данных в кэш-памяти, особенности выполняемой программы, время ее работы, уровень мультипрограммирования и других особенностей вычислительного процесса. Тем не менее, в большинстве реализаций кэш-памяти процент кэш-попаданий оказывается весьма высоким — свыше 90 %. Такое высокое значение вероятности нахождения данных в кэш-памяти объясняется наличием у данных объективных свойств: пространственной и временной локальности.

Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью произойдет в ближайшее время.

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

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

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