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

 

 

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

Каждая запись включает в себя адрес данных в основной памяти, сами данные и дополнительную управляющую информацию, которая используется для реализации алгоритма замещения данных в КЭШе (признаки модификации и действительности данных).

Цель – повысить количество кэш-попаданий. Вероятность обнаружения данных зависит от разных факторов: объема КЭШа, объема кэшируемой памяти, алгоритма замещения данных в КЭШе, особенностей выполняемой программы, времени её работы и других особенностей вычислительного процесса. Высокая вероятность нахождения данных объясняется наличием 2 свойств: пространственная и временная локальность.

1. согласно свойству временной локальности данные только что считанные из основной памяти скорей всего скоро снова понадобятся. В начале работы системы, когда кэш пуста, почти каждый запрос к основной памяти выполняется по полной программе, то есть запрос попадает в кэш, обращение к основной памяти. По мере заполнения КЭШа возрастает вероятность обращения к данным, которые уже были использованы на предыдущем этапе работы системы, то есть к данным, которые содержатся в КЭШе и могут быть считаны намного быстрее, чем из ОП.

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

Проблемы:

1. проблема согласования данных. В процессе работы содержимое в КЭШе постоянно обновляются, значит должно выполняться вытеснение. Вытеснение может происходить 2 способами: если данные не были изменены во время нахождения – путем простого объявления некоторой области свободной (сброс бита действительности); если данные были модифицированы – в дополнение к первому пункту происходит копирование в ОП. Наличие в компьютере 2 копий данных порождает проблему согласования данных. Если происходит запись в ОП по некоторому адресу, а содержимое этой ячейки находится в КЭШе, то в результате соответствующая запись в КЭШе становится недостоверной. Поэтому при каждом запросе к ОП в том числе и при записи должен просматриваться кэш. Если данные отсутствуют, то запись выполняется только в ОП, а если данные находятся в КЭШе, то возможны 2 решения:

o Сквозная запись – запись выполняется одновременно и в кэш и в ОП.

o Обратная запись – запись производится только в кэш-память, при этом в описателе данных делается отметка (признак модификации), которая указывает на то, что при вытеснении данных из КЭШа их необходимо переписать в ОП, чтобы актуализировать устаревшее содержимое ОП.

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

Способы отображения ОП на кэш-память.

При кэшировании используется 2 основные схемы: случайная и детерминированная. При случайном отображении элемент ОП может быть размещен в любом месте кэш-памяти. Для того чтобы в дальнейшем можно было найти нужные данные в КЭШе, они помещаются туда вместе со своим адресом. При каждом запросе к ОЗУ в КЭШе должен выполняться поиск адреса. Очевидно, что схема простого перебора для поиска потребует больших затрат времени, поэтому для КЭШей со случайным отображением используют ассоциативный поиск, при котором сравнение выполняется не последовательно, а параллельно со всеми его записями. Признак, по которому выполняется сравнение называется тегом.

 

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

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

 

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

 

Если строка кэш-памяти, в которую должен быть скопирован элемент из ОП, содержит другие данные, то последние вытесняются из КЭШа. Процесс замещения данных в кэш-памяти на основе прямого отображения существенно отличается от процесса случайного отображения. Во-первых, вытеснение данных происходит не только в случае отсутствия свободных ячеек в КЭШе. Во-вторых, никакого выбора данных на замещение не существует. Во многих современных процессорах кэш-память строится на основе сочетания этих двух подходов. При смешанном подходе произвольный адрес ОЗУ отображается не на один адрес КЭШа (при прямом отображении) и не на любой адрес кэш-памяти (при случайном отображении), а на некоторую группу адресов. Все группы пронумерованы, поиск в КЭШе осуществляется вначале по номеру группы, а затем в пределах группы путем ассоциативного просмотра всех записей. При выполнении запросов к ОП во многих ВС используется 2 или 3-уровневое кэширование. При работе необходимо обеспечить непротиворечивость данных на всех уровнях, кэш разных уровней могут согласовываться разными способами, например, при 2-уровневом кэшировании кэш–1 использует сквозную запись, кэш–2 использует обратную. Такая схема согласования применяется в Intel-процессорах при одном из вариантов работы.