Организация и политики кэша

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

Definition

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

Scope

Эта тема охватывает внутреннюю структуру одного кэша: прямое отображение, наборно-ассоциативное и полностью ассоциативное размещение; политики замещения, такие как LRU и их аппроксимации; политики записи (сквозная запись (write-through) против обратной записи (write-back)) и выделение при записи (write-allocation); размер блока; и классификацию промахов на принудительные (compulsory), по емкости (capacity) и конфликтные (conflict). Она исключает когерентность мульти-кэша (протоколы когерентности кэша) и трансляцию адресов (виртуальная память и подкачка).

Core questions

• Чем прямое отображение, наборно-ассоциативное и полностью ассоциативное размещение отличаются по стоимости и поведению при конфликтах?
• Какая политика замещения должна вытеснять блок при промахе и как она дешево аппроксимируется?
• Чем политики сквозной записи и обратной записи отличаются по трафику и сложности?
• Как классифицируются промахи и какие изменения в дизайне уменьшают каждый вид?

Key concepts

• кэш с прямым отображением
• наборно-ассоциативный кэш
• полностью ассоциативный кэш
• замещение по принципу наименее недавно использованного (LRU)
• сквозная запись (write-through) против обратной записи (write-back)
• выделение при записи (write-allocate)
• размер блока (строки)
• принудительные, по емкости и конфликтные промахи

Key theories

Модель промахов «трех С»

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

Mechanisms

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

Clinical relevance

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

History

Уилкс предложил подчиненную (кэш) память в 1965 году, и вскоре кэши были коммерчески внедрены. Обзор Алана Джея Смита 1982 года синтезировал обширные измерения политик размещения, замещения и записи, установив терминологию проектирования, используемую до сих пор. Модель «трех С» позже предоставила структурированный способ рассуждения о причинах и способах устранения промахов.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

В чем разница между кэшами со сквозной записью и обратной записью?

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

Почему используются наборно-ассоциативные кэши вместо кэшей с прямым отображением?

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