Лекция 2. Оптимизация работы с кеш-памятью процессора

• Архитектура ЭВМ фон Неймана включает устройство управления, арифметико-логическое устройство, устройство ввода-вывода и системную память.  

• Набор инструкций процессора поддерживает операции чтения, записи и арифметико-логические операции.  

• Пример операции: чтение элемента массива, сложение со скаляром и запись результата.  

• В архитектуре процессора есть регистры для хранения операндов арифметико-логических операций.  

• Регистры общего назначения имеют фиксированный размер и ограниченное количество.  

• Системная память энергозависима и используется для хранения данных и программ.  

• В программах много операций доступа к памяти, что нагружает функциональные модули процессора.  

• Исторически разрыв между производительностью процессоров и памяти увеличивается.  

• Процессоры вынуждены простаивать в ожидании готовности операндов.  

• Внеочередное выполнение инструкций и планирование операций по готовности операндов.  

• Локальность ссылок: пространственная и временная.  

• Пример программы с инициализацией переменной и суммированием элементов массива.  

• Пространственная локальность: обращение к смежным адресам в памяти.  

• Временная локальность: повторное обращение к одному и тому же адресу через короткий промежуток времени.  

• Нон-темпорал дейта: данные, которые не используются длительное время.  

• Кэш-память используется для повышения производительности программ.  

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

• Кэш реализован аппаратно и используется для всех обращений процессора.  

• Время доступа увеличивается с подъемом по иерархии памяти.  

• Регистры процессора, кэш первого уровня, кэш второго уровня и кэш третьего уровня.  

• Внешняя память, такая как HDD или SSD, также используется в иерархии.  

• Регистры имеют самое быстрое время доступа.  

• Кэш первого уровня быстрее, чем кэш второго уровня.  

• Кэш третьего уровня может быть реализован вне ядра и делиться между ядрами.  

• Внеочередное выполнение позволяет выполнять инструкции по готовности данных.  

• Вычислительный конвейер совмещает выполнение инструкций.  

• Многопоточность также относится к внеочередному выполнению.  

• Архитектура процессора описывает систему команд и режимы адресации.  

• Микроархитектура определяет внутреннее устройство процессорного ядра.  

• Пример: процессор Intel с микроархитектурой Golden Cove.  

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

• TLB-кэши и write-combining буферы используются для специальных задач.  

• Пример: процессор Эльбрус с каскадом из трех уровней кэш-памяти.  

• Программы на языке Си оперируют линейными адресами.  

• Виртуальная память и страничная организация памяти создают иллюзию большого адресного пространства.  

• Пример: 16 ГБ памяти на машине, но адресное пространство ограничено 2^64 байтами.  

• Операционная система опрашивает контроллеры памяти для определения физической памяти.  

• Физическая память разбита на страницы фиксированного размера, обычно 4 килобайта.  

• Ядро поддерживает таблицу страниц, где хранится информация о состоянии каждой страницы.  

• При запросе памяти ядро выделяет необходимое количество страниц.  

• Программа работает с линейными адресами, которые преобразуются в физические адреса.  

• Если памяти не хватает, ядро записывает занятые страницы на жесткий диск.  

• Виртуальная память позволяет программам работать с большим адресным пространством.  

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

• В современных системах свопинг используется редко, чтобы избежать снижения производительности.  

• Кэш процессора работает с физическими адресами.  

• Ядро операционной системы поддерживает таблицу страниц для преобразования линейных адресов в физические.  

• Процессор использует TLB кэш для быстрого преобразования часто используемых адресов.  

• Профилировщик perfstat позволяет отслеживать события, такие как менеджер и майнер фолды.  

• Менеджер фолд означает обращение к жесткому диску, что указывает на проблемы с памятью.  

• Майнер фолд происходит, когда страница присутствует в оперативной памяти, но не отображена в адресное пространство процесса.  

• Кэш первого уровня проверяет наличие данных по физическому адресу.  

• Если данные не найдены, кэш обращается к кэшу второго уровня и так далее.  

• Если данные не найдены в кэше, они загружаются из оперативной памяти.  

• Программы имеют свойства пространственной и временной локализации.  

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

• Строка кэш-памяти содержит 64 байта, что позволяет эффективно использовать кэш.  

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

• Кэш должен решать задачи: определение наличия блока с адресом в кэш-памяти, реализация алгоритма сопоставления физического адреса с записью в кэш-памяти.  

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

• Политика записи данных: write-back и write-through.  

• Обеспечение согласованного состояния данных в кэш-памяти ядер процессоров.  

• Аппаратный протокол для поддержания когерентности кэш-памяти.  

• Три подхода: множественно-ассоциативное отображение, полностью ассоциативное отображение, полный перебор.  

• Физический адрес разбивается на три поля: смещение блоков, индекс множества, тэг.  

• Кэш состоит из строк по 64 байта, поиск строки осуществляется по тэгу и смещению.  

• Четырехканальный множественно-ассоциативный кэш размером 32 килобайта.  

• В каждом множестве четыре строки, всего 128 множеств.  

• Физический адрес интерпретируется: смещение, номер множества, тэг.  

• Пример обращения к элементу массива с физическим адресом.  

• Кэш загружает блок из 64 байт, элемент попадает в строку кэш-памяти.  

• Возможность атаки на кэш-память через чтение через границу строки.  

• Кэш-память первого уровня может содержать данные из разных строк.  

• Компилятор и процессор минимизируют кэш-лайн сплит.  

• Кэш-память уровня L2 может быть инклюзивной или эксклюзивной по отношению к L1.  

• Кэш может работать в режимах write-through и write-back.  

• Write-through: данные сразу записываются в оперативную память.  

• Write-back: данные помещаются в кэш и помечаются как модифицированные.  

• При заполнении кэша данные вытесняются в оперативную память.  

• Алгоритм LRU вытесняет наименее востребованные строки.  

• Модифицированные строки записываются в память при их вытеснении.  

• Пространственная и временная локальность данных важны для оптимизации.  

• Оптимизация доступа к данным включает слияние циклов и модификацию структур данных.  

• Пример: перестановка циклов для улучшения пространственной локализации.  

• Слияние циклов улучшает временную локальность и уменьшает кэш-мисы.  

• Объединение двух циклов в один снижает накладные расходы и условные переходы.  

• Инициализация массива и вызов функции могут вытеснить данные из кэша.  

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

• Пример: заполнение массива единицами вытесняет данные из кэша, что замедляет вычисления.  

• Классический пример: умножение матриц.  

• Внутренний цикл по строке и столбцу приводит к кэш-миссу при каждом обращении.  

• Перестановка циклов улучшает пространственную локализацию и уменьшает кэш-мисс.  

• Разбиение матрицы на подматрицы для улучшения кэширования.  

• Выбор размера блока зависит от размера кэш-памяти процессора.  

• Пример: перемножение подматриц улучшает пространственно-временную локализацию.  

• Использование потоковой записи для минимизации загрязнения кэша.  

• Специальные инструкции позволяют записывать данные в write-combiner-buffer.  

• Пример: использование нон-темпорал данных для предотвращения вытеснения полезных данных из кэша.  

• Современные процессоры имеют аппаратный prefetch для предсказания данных.  

• Специальные инструкции позволяют процессору предзагружать данные в кэш.  

• Пример: использование prefetch для чтения элементов массива из кэша.  

• Выравнивание массива структур для улучшения кэширования.  

• Пример: выравнивание массива структур для минимизации кэш-мисса.  

• Важно учитывать размер структуры и массива для оптимального использования кэша.  

• Первый элемент структуры гарантированно попадает в начало строки кэш-памяти.  

• Критический код работает только с полями a и b, что приводит к неэффективному использованию кэш-памяти.  

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

• Утилита по холле показывает размещение структур в памяти и их выравнивание.  

• Выравнивание структуры должно быть кратно размеру самого большого поля.  

• Компилятор добавляет заполнители для выполнения системных требований, что увеличивает размер структуры.  

• Перестановка элементов структуры позволяет плотнее упаковать их в строку кэш-памяти.  

• Пример с массивом частиц показывает, как можно оптимизировать использование кэш-памяти.  

• Структура из массивов обеспечивает лучшую пространственную локализацию и возможность параллелизации кода.  

• Профилировщик perf позволяет анализировать промахи кэш-памяти и эффективность использования кэш-памяти.  

• Утилита perf mem report помогает выявить ошибки и неэффективное использование кэш-памяти.  

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