Кэш-линия

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

Назначение и принцип работы

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

Размер кэш-линии является компромиссом между эффективностью использования пространственной локальности и объёмом передаваемых данных. Типичный размер для современных процессоров (x86, ARM) составляет 64 байта, хотя в некоторых архитектурах (например, PowerPC) встречаются линии по 128 байт.

Структура кэш-линии

Каждая кэш-линия в кэше содержит три основных поля:

• Тег (tag) — часть адреса памяти, которая идентифицирует, какой именно блок данных из ОЗУ хранится в данной линии. Обычно это старшие биты адреса, за вычетом битов смещения внутри линии и индекса набора.
• Данные (data) — собственно содержимое блока памяти размером, равным размеру кэш-линии (например, 64 байта).
• Флаги состояния (status flags) — служебные биты, указывающие на состояние линии (валидность, модифицированность, эксклюзивность и т.д.). В многопроцессорных системах используются протоколы когерентности кэша (MESI, MOESI и др.), где каждый флаг определяет, можно ли читать или писать в линию.

В некоторых реализациях также может присутствовать бит «грязности» (dirty bit), указывающий, что данные в линии были изменены и должны быть записаны обратно в основную память.

Ассоциативность и размещение

Кэш-линии распределяются по кэшу в зависимости от его организации:

• Кэш с прямым отображением (direct-mapped cache) — каждая кэш-линия из ОЗУ может быть помещена только в одну конкретную позицию (набор) в кэше. Адрес памяти разбивается на тег, индекс набора и смещение внутри линии. Индекс определяет номер набора, а тег проверяется на совпадение.
• Полностью ассоциативный кэш (fully associative cache) — любая кэш-линия может быть помещена в любую свободную позицию. Поиск ведётся по всем тегам одновременно, что дорого в реализации, но даёт наименьшее количество конфликтов.
• Наборно-ассоциативный кэш (set-associative cache) — компромиссный вариант: кэш разбит на наборы (sets), каждый из которых содержит несколько путей (ways). Кэш-линия может быть помещена в любой из путей в пределах набора, определяемого индексом. Например, 4-канальный наборно-ассоциативный кэш означает, что в каждом наборе есть 4 возможных позиции для линии.

В современных процессорах кэш L1 обычно является наборно-ассоциативным (например, 8-канальным), а кэш L2 и L3 — также наборно-ассоциативными, но с большим числом путей (16–32).

Размер кэш-линии и его влияние

Размер кэш-линии существенно влияет на производительность:

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

Типичный размер 64 байта был выбран как оптимальный для большинства рабочих нагрузок. В некоторых специализированных системах (например, в графических процессорах или DSP) размер может быть другим (32, 128 или 256 байт).

Когерентность кэша

В многопроцессорных системах несколько ядер или процессоров имеют собственные кэши, и кэш-линии могут дублироваться. Для согласования данных между кэшами используются протоколы когерентности, такие как MESI (Modified, Exclusive, Shared, Invalid) или его расширения. Каждая кэш-линия помечается одним из состояний:

• Modified — линия изменена и присутствует только в данном кэше.
• Exclusive — линия не изменена и присутствует только в данном кэше.
• Shared — линия не изменена и может присутствовать в нескольких кэшах.
• Invalid — линия недействительна.

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

Примеры и применение

В архитектуре x86-64 (Intel, AMD) кэш-линия имеет размер 64 байта. В процессорах ARM Cortex-A серии также используется 64 байта. В старых архитектурах (например, Intel 80486) размер составлял 16 байт, а в некоторых RISC-процессорах (MIPS, SPARC) — 32 байта.

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

Интересные факты

• В некоторых суперкомпьютерах (например, Earth Simulator) использовались кэш-линии размером 256 байт для работы с большими массивами данных.
• В процессорах Intel с поддержкой AVX-512 кэш-линия может быть загружена или выгружена с помощью специальных инструкций, работающих с 64-байтовыми регистрами.
• Ложное разделение (false sharing) — одна из распространённых проблем производительности в многопоточных программах, когда два потока пишут в разные переменные, но они оказываются в одной кэш-линии, что приводит к постоянным промахам кэша.

Источники

• Hennessy, J. L., Patterson, D. A. Computer Architecture: A Quantitative Approach. 6th ed., Morgan Kaufmann, 2017.
• Intel 64 and IA-32 Architectures Software Developer’s Manual. Volume 3A: System Programming Guide, Part 1.
• ARM Architecture Reference Manual ARMv8, for ARMv8-A architecture profile.
• Tanenbaum, A. S., Austin, T. Structured Computer Organization. 6th ed., Pearson, 2012.