Иерархия памяти и кэши

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

Definition

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

Scope

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

Sub-topics

• Cache Coherence Protocols
• Cache Organization and Policies
• Memory Technologies and DRAM
• Virtual Memory and Paging

Core questions

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

Key concepts

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

Key theories

Локальность ссылок

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

Компромиссы в проектировании кэша

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

Mechanisms

Когда процессор запрашивает данные, сначала проверяется кэш; попадание (hit) быстро возвращает данные, в то время как промах (miss) извлекает блок с более низкого уровня и может вытеснить другой блок в соответствии с политикой замещения. Записи распространяются с помощью схем сквозной записи (write-through) или обратной записи (write-back), а протоколы когерентности поддерживают согласованность нескольких кэшей. Виртуальная память добавляет шаг трансляции — через таблицы страниц и буфер ассоциативной трансляции (translation lookaside buffer) — сопоставляя адреса программы с физической DRAM, обеспечивая при этом защиту.

Clinical relevance

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

History

Морис Уилкс предложил концепцию кэша («подчиненной памяти») в 1965 году, и кэши появились в коммерческих машинах, таких как IBM System/360 Model 85. Виртуальная память возникла с компьютером Atlas в начале 1960-х годов, формализованная моделью рабочего набора Деннинга. Обзор Алана Джея Смита 1982 года обобщил знания о проектировании кэшей, а многоуровневые кэши и сложные протоколы когерентности стали стандартом по мере увеличения разрыва в скорости между процессором и памятью.

Debates

Аппаратное против программного управления локальностью

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

Key figures

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

Seminal works

• hennessy2019
• smith1982cache
• patterson2020

Frequently asked questions

Почему кэши эффективны, если они так малы по сравнению с основной памятью?

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

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

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