Оптимизация для pentium процессора
6. КЕШ
======
Чип Pentium имеет 8k кеша (L1) для кода и 8k для данных. Данные на L1 могут
быть прочитаны или записаны за 1 такт, а в случае промаха кеша это может
стоить многих тактов. По этому очень важно, что бы вы поняли как
работает кеш и могли использовать его с максимальной эффективностью. К
сожалению в большинстве других документов кеш описывается либо недостаточно,
либо слишком непонятно. Я надеюсь, что вы сочтете это описание одним их
лучших.
Кеш данных состоит из 256 строк, по 32 байта в каждой. Всякий раз, когда вы
пытаетесь прочесть данные, которых нет в кеше - процессор прочтет из памяти
целую строку. Строки кеша всегда выравнены по физическому адресу, делимому на
32. Значит всякий раз, когда вы прочитали байт по адресу делимому на 32,
следующие 31 байт могут быть прочитаны практически мгновенно. Вы можете
воспользоваться этим преимуществом, размещая часто используемые данные в
блоках, выравненных по 32 байта. К примеру, если у вас есть цикл, который
работает с двумя массивами, тогда вы можете скомбинировать эти два массива в
одну структуру, что бы данные, которые обрабатываются совместно и загружались
совместно.
Если размер массива кратен 32 байтам, то было бы неплохо выровнять его на 32
байта.
Строка кеша не может быть связана с произвольным адресом памяти. У каждой
строки кеша есть 7-битное установочное значение, соответствующее битам с 5-го
по 11-ый физичекого адреса памяти (биты 0..4 соответствуют 32 байтам внутри
строки кеша). Таким образом у нас есть два блока по 128 строк (всего 256
строк), в каждом из которых могут существовать две строки, ссылающиеся на
один и тот-же адрес памяти. Следствием этого является то, что мы не можем
иметь в кеше более двух строк, указывающих на физические адреса памяти,
имеющие одинаковые биты 5-11. Мы можем определить, имеют-ли два адреса
одинаковое установочное значение следующим образом: Сбросить младшие 5 бит,
каждого адреса, что бы получить значение делимое на 32. Если два адреса,
со сброшенными младшими 5 битам кратны 4096 (=1000h), то эти адреса имеют
одинаковое установочное значение.
Позвольте мне проиллюстрировать это следующим кодом, где адрес в ESI делим
на 32:
AGAIN: MOV EAX, [ESI]
MOV EBX, [ESI + 13*4096 + 4]
MOV ECX, [ESI + 20*4096 + 28]
DEC EDX
JNZ AGAIN
Все три адреса имеют одинаковую установочную величину, поскольку в усеченном
виде они кратны 4096. Этот цикл будет исполняться крайне медленно. Как только
мы попытеамся прочесть данные в ECX процессор обнаружит, что нет возможных
строк, для кеширования данных, следовательно он удалит из кеша наиболее давно
используемые данные, т.е. строку кеширующую данные, которые мы читали в EAX
и заполнит ее данными с [ESI + 20*4096] по [ESI +20*4096 + 31], а затем
прочтет данные в ECX. Затем, когда мы попытаемся прочесть данные в EAX,
процессор снова обнаружит, что в кеше нет строки для кеширования EAX и нет
места, что бы ее добавить, значит ему придется снова отвергнуть наиболее
старую строку (для EBX), затем проведет кеширование для EAX и, наконец,
прочтет данные. Теперь тоже самое произойдет с EBX, и т.д... Таким образом
мы имеем постоянные промахи кеша, и на каждый проход по циклу тратиться около
60 тактов. Но если мы заменим третью строку на:
MOV ECX, [ESI + 20*4096 + 32]
Все! Мы пересекли 32 байтную границу, значит третья строка будет иметь другую
установочную величину, все строки будут постоянно находиться в кеше, не будет
промахов. Время затрачиваемое на один проход по циклу сократится до 3 тактов
(за исключением первого прохода, конечно) - очень значительное улучшение!
Конечно, определить это весьма не просто, особенно если данные разбросаны по
разным сегментам. Лучший способ, которым вы можете решить эту проблему -
хранить данные, использующиеся в критической части вашей программы, в пределах
одного блока длиной 8Кб максимум, или двух блоков, по 4Кб максимум (например
один блок для статических переменных, а другой для стека). Это гарантирует,
что все линии кеша будут использованы оптимально.
Если критическая часть вашей программы работает с большими структурами
данных или работает с произвольными адресами, то не плохим решением будет
хранить все часто используемые переменные (счетчики, указатели, контрольные
переменные, и т.д.) в одном непрерывном блоке, до 4Кб длиной, тогда у вас
останется полный набор строк кеша, для доступа к произвольным данным.
Поскольку вам скорее всего потребуется память в стеке, для параметров
подпрограмм или адресов возврата, то лучше будет скопировать все часто
используемые статические данные в динамические переменные, в стеке, а затем,
если необходимо, копировать их обратно, за пределами критической части
программы.
Во время чтения данных, не находящихся в L1, строка кеша сначала заполняется
из L2, скорость доступа которой примерно 200 ns (что требует 20 тактов в
100 MHz системе), но первые байты из запрашиваемой строки обычно доступны
уже через 50-100 ns. Если запрашиваемые данные не в L2, то задержка составит
порядка 200-300 ns. Эта задержка может быть и большей, если вы пересечете
границу страницы DRAM. (Размер страницы DRAM 1Кб, для 4Мб 72 пиновых модулей
и 2Кб для 16Мб модулей).
Когда вы записываете данные, по адресу, не находящемуся в L1, данные будут
помещены в L2. Это займет примерно 100 ns. Значит если вы пишете 8 или более
байт в 32 байтовый блок, не читая ничего от туда, то лучше всего будет просто
прочитать от туда что-нибудь, что бы загрузить блок в L1. Все последующие
записи в тот-же блок будут записываться во внутренний кеш, и каждая запись
займет 1 такт. (Это не нужно на Pentium Pro, где всегда загружается строка
при промахе записи). Иногда возникает замедление при повторяющихся записях,
без промежуточного чтения.
Иногда можно уменьшить количество промахов при записи, записывая по 8 байт,
используя FILD / FISTP с DWORD операндом, вместо использования целочисленных
регистров. Более медленное исполнение инструкций FILD и FISTP компенсируется
тем, что вы должны сделать только половину необходимых циклов чтения-записи.
Тем не менее этот метод эффективен только на Pentium и только если адрес
записи не находиться в кеше. Более подробно этот метод будет рассмотрен в
разделе 19.
Временные данные вы можете помещать в стек, поскольку стек скорее всего
попадет в кеш. Знаете вы или нет, но тем не менее, если вы сохраняете QWORD
данные в DOWRD стеке, или DWORD данные в WORD стеке, то у вас может быть
проблема с выравниванием.
Если рабочее время двух структур не пересекается, то они могут использовать
одну и ту же область памяти, для повышения эффективности кеша. Это
соответствует общим правилам распределения памяти временным переменным в
стеке.
Конечно, хранение данных в регистрах более эффективно, но поскольку регистров
не много, то возможно вы захотите использовать [ESP], а не [EBP] для
адресации данных в стеке, тем самым освобождая EBP для других целей. Просто не
забывайте, что значение ESP изменяется каждый раз, когда вы используете PUSH
или POP. (Вы не сможете использовать ESP под 16 битной Windows поскольку
таймер непредсказуемо изменяет старшее слово в ESP).
Pentium имеет 8Кб кеша кода, имеющих структуру, похожую на кеш данных. Значит
важно, что бы критическая часть вашего кода (внутренние циклы) полностью
помещалась в кеш. Часто используемые части кода или структуры, которые
используются вместе, было бы предпочтительно и хранить вместе. Редко
используемые ветви или подпрограммы должны храниться дальше.
