Оптимизация для процессоров семейства Pentium: 7. Кэш — Архив WASM.RU

У PPlain и PPro 8 килобайт кэша первого уровня для кода и 8 килобайт для данных. У PMMX, PII и PIII по 16 килобайт для кода и данных. Данные в кэше первого уровня можно читать или перезаписывать всего лишь за один такт, в то время как выход за границы кэша может стоить множества тактов. Поэтому важно, понимать, как работает кэш, чтобы использовать его более эффективно.

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

Если размер массива кратен 32 байтам, вам следует и выравнивать его по границе 32 байта.

Кэш set-ассоциативен. Это означает, что кэш-ряд нельзя ассоциировать с произвольным адресом памяти. У каждого кэш-ряда есть 7-ми битное значение, которое задает биты 5-11 адреса в физической памяти (биты 0-4 определяются положением элемента данных в кэш-ряде). У PPlain и PPro два кэш-ряда для каждого из возможных 128 set-значений, поэтому с определенным адресом в памяти можно ассоциировать только два жестко заданных кэш-ряда. В PMMX, PII и PIII - четыре.

Следствием этого является то, что кэш может содержать не более двух или четырех различных блока данных, у которых совпадают биты 5-11 их адресов. Вы можете определить, совпадают ли эти биты у двух адресов следующим образом: удалите нижние пять битов каждого адреса, чтобы получить значение, кратное 32. Если разница между этими обрезанными значениями кратна 4096 (=1000h), значит у этих адресов одно и то же set-значение.

Давайте я проиллюстрирую вышеизложенное с помощью следующего кода, где ESI содержит адрес, кратный 32:

Код (Text):

1.  
2. AGAIN:  MOV  EAX, [ESI]
3.         MOV  EBX, [ESI + 13*4096 +  4]
4.         MOV  ECX, [ESI + 20*4096 + 28]
5.         DEC  EDX
6.         JNZ  AGAIN

У всех трех адресов, использованных здесь, совпадают set-значения, потому что разница между обрезанными адресами будет кратна 4096. Этот цикл будет очень плохо выполняться на PPlain и PPro. Во время записи в ECX нет ни одного свободного кэш-ряда, поэтому тот, который был использован для значения, помещенного в EAX, заполняется данными с [ESI+20*4096] до [ESI+20*4096+31] и записывает значение в ECX. Затем во время чтения EAX оказывается, что кэш-ряд, содержавший значение для EAX, уже изменен, поэтому то же самое происходит с кэш-рядом, содержащим значение для EBX, и так далее. Это пример нерационального использования кэша: цикл занимает около 60 тактов. Если третью линию изменить на:

Код (Text):

1.  
2.         MOV  ECX, [ESI + 20*4096 + 32]

мы пересечем границу в 32 байта, поэтому у нас будет другое set-значение, и не возникнет никаких проблем с ассоциирование кэш-рядов к этим трем адресам. Цикл теперь занимает 3 такта (не считая первого раза) - весьма значительное улучшение! Стоит упомянуть, что у PMMX, PII и PIII для каждого set-значения есть четыре кэш-ряда. (Некоторые интеловские документы ошибочно утверждают, что у PII по два кэш-ряда на каждое set-значение).

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

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

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

При считывании больших блоков данных из памяти, скорость ограничена временем, уходящим на заполнение кэш-рядов. Иногда вы можете увеличить скорость, считывая данные в непоследовательном порядке: еще не считав данные из одного кэш-ряда, начать читать первый элемент из следующего кэш-ряда. Этот метода можете повысить скорость на 20-40% при считывании данных из основной памяти или кэша второго уровня на PPlain и PMMX, или из кэша второго уровня на PPro, PII и PIII. Недостаток этого метода заключается в том, что код программы становится очень запутанным и сложным. Другую информацию об этом методе вы можете получить на www.intelligentfirm.com.

Когда вы пишите в адрес, которого нет в кэше первого уровня, тогда значение пойдет прямо в кэш второго уровня или в память (в зависимости от того, как настроен кэш второго уровня) на PPlain и PMMX. Это займет примерно 100 ns. Если вы пишите восемь или более раз в тот же 32-байтный блок памяти, ничего не читая из него, и блок не находится в кэше первого уровня, возможно стоит сделать фальшивое чтение из него, чтобы он был загружен в кэш-ряд. Все последующие чтения будут производиться в кэш, что занимает всего лишь один такт. На PPlain и PMMX иногда происходит небольшая потеря в производительности при повторяющемся чтении по одному и тому же адресу без чтения из него между этим.

На PPro, PII и PIII запись обычно ведет к загрузке памяти в кэш-ряд, но возможно указать область памяти, с которой следуюет поступать иначе (смотри Pentium Pro Family Developer's Manual, vol. 3: Operating System Writer's Guide").

Другие пути увеличения скорости чтения и записи в память обсуждаются в главе 27.8.

У PPlain и PPro есть два буфера записи, у PMMX, PII и PIII - четыре. На PMMX, PII и PIII у вас может быть до четырех незаконченных записей в некэшированную память без задержки последующих инструкций. Каждый буфер записи может обрабатывать операнды до 64 бит длиной.

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

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

Хранение временных данных в регистрах, разумеется, более эффективно. Так как регистров мало, вы, возможно, захотите использовать [ESP] вместо [EBP] для адресации данных к стеку, чтобы освободить EBP для других целей. Только не забудьте, что значение ESP меняется каждый раз, когда вы делаете PUSH или POP. (Вы не можете использовать ESP под 16-ти битным Windows, потому что прерывание таймера будет менять верхнее слово ESP тогда, когда это невозможно предугадать.)

Есть отдельных кэш для кода, которых схож с кэшем данных. Размер кэша кода равен 8 килобайтам на PPlain и PPro и 16 килобайтам на PMMX, PII и PIII. Важно, чтобы критические части вашего кода (внутренние циклы) умещались в кэш кода. Часто используемые процедуры следует помещать рядом друг с другом. Редко используемые ветви или процедуры нужно деражть в самом низу вашего кода или где-нибудь еще. © Агнер Фог, пер. Aquila