Секреты кэш-памяти, или как потратить 1000 тактов на 10 команд

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

В качестве примера я возьму простенькую систему на кристалле, основанную на 32-битном гарвардском RISC-процессоре с одноуровневой кэш-памятью и без MMU (что-то типа ARM Cortex-R). Процессор подключен к контроллеру внешней памяти через 32-битную шину AMBA AHB, работающую на частоте процессора.



Кэши команд и данных раздельные, прямого отображения, размером по 16 килобайт каждый. Длина строки кэша — 32 байта, то есть каждый кэш содержит по 512 строк. Напомню, что смещение определяет порядковый номер байта внутри строки кэша, а индекс — номер строки кэша в кэш-памяти. Так как кэш прямого отображения, то в нем не могут одновременно находиться несколько строк с одинаковым индексом, даже если тэги у них разные.



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

        # таблица векторов прерываний расположена с адреса 0х0
        _reset_vector:
0x0000: jump   _start
        _interrupt1:
0x0004: jump   _handler1
        _interrupt2:
0x0008: jump   _handler2
...

        # основной код программы расположен с адреса 0x1234
        _start:

        # загружаем первый операнд из памяти в регистр R10
0x1234: moveh   R0, 0x1000 # загружаем 0х1000 в R0[31:16]
0x1238: load    R10, [R0]  # загружаем в R10 значение из 0x10000000

        # загружаем второй операнд из памяти в регистр R11
0x123C: moveh   R1, 0x1001 # загружаем 0х1001 в R1[31:16]
0x1240: load    R11, [R1]  # загружаем в R11 значение из 0x10010000

        # складываем операнды и записываем результат в память
0x1244: add     R2, R0, R1
0x1248: moveh   R3, 0x2000 # загружаем 0х2000 в R3[31:16]
0x124C: store   R2, [R3]   # сохраняем R2 по адресу из R3

        # останавливаем процессор
0x1250: halt


После включения процессор начинает выполнять команды с адреса, соответствующего адресу таблицы векторов прерываний. Этот адрес обычно жестко зашит в процессоре. В общем случае он может быть равен чему угодно, но для простоты предположим, что он равен нулю.
Таким образом первая команда нашей программы — «jump _start» — расположена по адресу 0х0, и процессор априори знает ее адрес.

Этап 1. Процессор ищет в кэше команд строку, содержащую команду с адресом 0х0. Поскольку кэш пуст, контроллер кэша внутри процессора сигнализирует о промахе и тут же приостанавливает процессор, одновременно инициируя так называемый «read burst», то есть запрос на чтение пакета данных из внешней памяти. Данные никогда не загружаются в кэш пословно — только пакетами, иначе смысла в кэше вообще нет! Размер пакета данных равен длине строки кэша. Таким образом, запрос занимает 8 тактов, потому что в нашей системе шина AHB может передавать не более 32 битов данных за такт. В идеальном случае запросу понадобится один такт, чтобы дойти до контроллера памяти (если шина будет занята обработкой другого запроса, то тактов понадобится больше). В зависимости от типа внешней памяти контроллер может начать передавать прочитанные данные либо сразу после прихода запроса (если память SSRAM), либо через несколько десятков тактов (в случае SDRAM) — это время называется латентностью памяти. Еще один такт потребуется прочитанным данным, чтобы пройти обратный путь от контроллера памяти до процессора. Ниже приведены временные диаграммы чтения строки кэша из внешней памяти с латентностью в четыре такта.



Этап 2. Контроллер кэша записывает слова, приходящие из памяти, в буфер строки («line buffer»), размер которого равен длине строки кэша. Когда буфер строки будет заполнен, его содержимое будет сохранено в нулевой строке кэша команд (т.к. индекс у адреса 0х0 — это 0). Однако процессор может выполнять команды из буфера напрямую, поэтому как только в буфер будет записана команда, вызвавшая промах, контроллер кэша тут же разблокирует процессор. Поскольку процессор конвейеризирован, он должен будет выбрать из памяти вторую команду еще до того, как первая будет декодирована. Чтобы добится этого, адрес второй команды будет предсказан, и, скорее всего, будет предсказан неверно, в результате чего процессор продолжит выбирать команды с адреса 0х4. Поскольку вторая команда («jump _handler1») к этому моменту также будет находится в буфере, промаха не произойдет, а процессор начнет выбирать третью команду («jump _handler2»). Так будет продолжаться, пока процессор не поймет, что он ошибся с предсказанием и вторая команда должна была быть выбрана по адресу 0х1234.

Этап 3. Как только процессор прозреет (а в процессоре со, скажем, семистадийным конвейером команд это займет около семи тактов), он тут же выдаст очередной промах кэша, на этот раз вызванный отсутсвием в кэше строки, содержащей команду по адресу 0х1234 («move R0, 0x10000000»), и пошлет новый «read burst», который по возвращении будет сохранен в 145-ой строке кэша (т.к. индекс у адреса 0х1220 — это 0х91=145). В зависимости от реализации процессор может начать загружать данные в кэш либо с начала строки (т.е. сначала слово по адресу 0х1220, потом 0х1224, 0х1228 и так далее вплоть до 0х123С), либо с того слова, которое вызвало промах (так называемый режим «critical word first» — сначала читается слово по адресу 0х1234, потом 0х1238, 0х123С, 0х1220, 0х1224 и т.д.) В обоих вариантах строка в любом случае загружается полностью, но в первом случае процессор потратит пять лишних тактов на ожидание. Нужно заметить, что многие микроконтроллеры до сих пор не поддерживают «critical word first», поэтому при должном везении программист может добиться значительного падения производительности.



Этап 4. Вне зависимости от того, поддерживается «critical word first» или нет, в кэш будут загружены сразу три корректных команды (до «move R1, 0x10010000» включительно). Когда очередь дойдет до команды «load R10, [R0]», процессор обнаружит промах кэша данных (ведь кэш данных-то пуст — все предыдущие манипуляции происходили с кэшем команд) и пошлет еще один «read burst», который будет записан в нулевую строку (т.к. индекс у адреса 0х10000000 — это 0). Если процессор достаточно умен и сообразителен (а большинство процессоров, чуть более сложных, чем студенческие поделки, достаточно умны для этого), он поймет, что следующая за «load R10, [R0]» команда не зависит от нее и может быть выполнена одновременно с копированием данных в кэш. После этого процессор захочет выбрать команду по адресу 0х1240 и мы получим еще один «read burst», который «зависнет», так как шина все еще будет занята предыдущим запросом от кэша данных. Конечно, рано или поздно команда «load R11, [R1]» попадет таки в кэш команд, и процессор тут же обнаружит новый промах кэша данных, который вдобавок вытеснит из кэша загруженную ранее строку с тэгом 0x04000 (так как адреса 0х10000000 и 0х10010000 отличаются только тэгами — 0x04000 и 0x04800 соответственно, а индекс у обоих равен нулю).

Этап 5. В конце концов процессор выполнит команду «store R2, [R3]», которая вызовет еще один промах кэша данных и, как следствие, еще один «read burst», и вдобавок вытеснит из кэша строку с тэгом 0x04800, заменив ее на строку с тэгом 0x08000. Кроме того, нужно помнить, что эта команда ничего не запишет во внешнюю память, потому что запись будет произведена только в кэш! Никакого «write burst» не будет до тех пор, пока программист явно не позабоится о том, чтобы «слить» обновленную строку кэша обратно в память (то есть сделать cache line flush), либо пока строка не будет вытеснена из кэша другой строкой. Например, если бы вместо команды «halt» была команда «load r4, [0x8000]», то процесс чтения выглядел бы так:



Напоследок хотелось бы сказать вот что: ошибки, связанные с неправильным использованием кэшей, можно искать месяцами. Компиляторы, кэширующие volatile-ы, и память, которая вопреки заветам товарища фон Неймана изменяет сама себя, тому свидетели. «Прозрачность» кэшей — это миф, который годится разве что для сферических программистов на вакуумном PHP. Поэтому если в вашем процессоре есть кэш — выключите его от греха подальше!
Поделиться публикацией

Комментарии 15

  • НЛО прилетело и опубликовало эту надпись здесь
      +2
      не знаю, я хардварщик :)
      +4
      Отключать кэши хорошо, когда используется память с латентностью один такт (и если это не противоречит архитектуре процессора в целом). А для динамической памяти совсем не здорово…
        0
        С тем же успехом можно под полным программным контролем заливать нужные области памяти по DMA в on-chip SRAM, у которой латентность как раз один такт (такая память называется Scratchpad Memory, Closely Coupled Memory или Tightly Coupled Memory, как кличет ее ARM). На этот счет есть любопытные исследования, могу дать ссылок. В общем, варианты есть, и кэш не должен рассматриваться как панацея.
          0
          Так давайте ссылок
          Личный опыт показывает, что загрузка кода в SRAM не только бесполезна, но и вредна. На stm32f103 (без кеша) и stm32f407 (с кешем) это вызывало падение производительности.
          TCM тоже совсем не панацея, по банальной причине, в тех мк с которыми мне довелось работать он сидел на D-bus, т.е. из него нельзя было выполнять код

          PS копировать код по мере надобности — хороший способ достичь заявленной в названии поста цифры 1000 тактов на 10 команд
            +1
            Разумеется, речь не идет про SRAM, висящий на внешней шине вместе с периферийными устройствами. С точки зрения процессора это такая же внешняя память, как какой-нибудь DDR, даже если физически она находится на том же кристалле. Даже если память сама по себе обеспечивает доступ за один такт, все равно будет дополнительная задержка в бридже между процессором и шиной, а также накладные расходы на арбитраж.

            CCM/TCM — совсем другое дело. Этот тип памяти фактически встроен в конвейер. Если в процессоре есть кэши, то CCM/TCM расположены бок о бок с ними, а не за ними, как SRAM на внешней шине. В процессоре с гарвардской архитектурой CCM/TCM для команд и данных раздельные, как и кэши. Кроме того, такая память может быть двухпортовой, и тогда процессор может читать из нее, скажем, команды, а DMA-контроллер одновременно может копировать в нее блок из внешней памяти.

            Вот несколько ссылок, которые были под рукой:
            Predictable Programming on a Precision Timed Architecture
            Software-based Instruction Caching for Embedded Processors
            An Optimal Memory Allocation Scheme for Scratch-Pad-Based Embedded Systems
        +9
        Какая-то странная заметка, честно говоря.
        Поэтому если в вашем процессоре есть кэш — выключите его от греха подальше!

        КЭШ нужен для того, чтобы смягчить издержки при повторном обращении к данным, в этом вся его соль. Исследования и практика показывают, что доступ к уже имеющимся данным действительно происходит очень часто. Именно поэтому КЭШ это лучшее из того, что мы имеем сейчас. И именно благодаря ему сейчас увеличивается производительность(ну не только благодаря ему, но его вклад очень велик). Поэтому эта ваша фраза мягко говоря не имеет ничего общего с реальностью.
        Никакого «write burst» не будет до тех пор, пока программист явно не позабоится о том, чтобы «слить» обновленную строку кэша обратно в память (то есть сделать cache line flush), либо пока строка не будет вытеснена из кэша другой строкой.

        Я не знаю понятия «write burst», зато знаю «write through» и «write back». И эти обе стратегии не требуют от программистов никаких усилий. Кроме того, первая обновляет память сразу же, без ожидания «вытеснения».

        Исходя из вышесказанного и размера статьи(написать про КЭШ три экрана это просто смех), я бы поставил 3- этой статье. Да и то с натягом.

        P.S. не сочтите за наезд, просто заметка действительно сырая и противоречивая.
          +1
          Статья про конкретный кусок кода и его испонение процессором с кэшами. Про то, как реально происходят запросы в память и чего можно от них ожидать. Цели объяснять азы работы кэша я не ставил (благо ссылка на неплохую статью имеется в начале).

          «Write burst» показан на последнем рисунке слева — он происходит, пока сигнал «Писать» выставлен в единицу. «Write-back» — это как раз то, как работает мой абстрактный процессор (который работает так же, как один широко известный в узких кругах реальный процессор). Очевидно, что он может потребовать некоторых усилий от программиста, особенно если тот пишет драйвер или программу для многоядерной системы.
            0
            Т.е. write burst это запись из КЭШ в ОЗУ?
            Очевидно, что он может потребовать некоторых усилий от программиста, особенно если тот пишет драйвер или программу для многоядерной системы.

            А разве можно заставить КЭШ записать в ОЗУ при write back стратегии? Покажите пример, если можно, желательно в терминах x86.

            По поводу «виртуального контроллера»: пока читал статью забыл об этом отступлении в начале статьи, так что приношу свои извинения. Я решил, что статья общая.
              +1
              «Write burst» — это не просто запись в ОЗУ, это пакетная запись в ОЗУ строки кэша для минимизации задержек на внешней шине процессора. Это настолько критично с точки зрения производительности, что все современные протоколы системных шин (те же AHB, AXI и т.д.) поддерживают специальные команды для записи/чтения строк кэша (так называемые «wrap bursts»), специально заточенные под режим «critical word first».

              Совершенно точно можно заставить кэш данных записать свое содержимое в ОЗУ при «write-back» стратегии, причем в некоторых случаях это можно сделать как для всего кэша целиком, так и для конкретной строки. Для этого в процессоре предусмотрены команды или управляющие регистры. Запись измененных данных из кэша в ОЗУ называется «cache flushing». Для х86 это делается так: stackoverflow.com/questions/1756825/cpu-cache-flush
                0
                Можете посоветовать чтиво по протоколам шин и прочим около-того темам? Желательно книги.
                  +1
                  С тех пор, как прикрыли Гигапедию, с книгами тяжко :) Я бы рекомендовал начать вот с этого: AMBA 2 Specification. Это не книга, а спецификация, но написана очень понятно, много картинок, к тому же бесплатная (надо только зарегистрироваться). Если есть какой-никакой бэкграунд, хотя бы на уровне институтского курса по цифровой схемотехнике — разобраться не составит труда. Читать можно только про AHB и APB — они до сих пор актуальны, в отличие от ASB.

                  Если есть возможность, можно полистать вот эти книжки: On-Chip Communication Architectures: System on Chip Interconnect или Networks on Chips: Technology and Tools
                0
                Команда сброса кэша? Сброса линейки кэша (это уже смотря как контроллер).
                +1
                Статья про конкретный кусок кода и его испонение процессором с кэшами.

                Поэтому если в вашем процессоре есть кэш — выключите его от греха подальше!

                А не слишком ли категорические выводы вы тогда делаете?
                  0
                  Это всего лишь мое мнение, я его никому не навязываю. В комментах привел несколько ссылок на интересные статьи. Читайте, думайте.

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

            Самое читаемое