В ряде случаев (например, для тонкой оптимизации программы под конкретный компьютер) полезно знать характеристики кэш-подсистемы: количество уровней, время доступа к каждому уровню, их размер и ассоциативность, и т.п.
Для одноразовой оптимизации необходимые значения можно посмотреть в спецификации на компьютер, но когда требуется автоматическая оптимизация (например, во время сборки и установки программы), характеристики приходится определять косвенно, по результатам прогона специального набора тестов.
Удобная тестовая программа для Linux —
Пример графика, который был получен этой программой на реальной системе:
Вспомним, что кэш разбит на блоки (строки): каждый блок хранится как неделимая единица, и читается из следующего уровня памяти целиком. Младшие биты адреса определяют смещение искомого байта в блоке кэша. Блоки обычно организованы двумерно: несколько сетов, из которых нужный выбирается по следующим младшим битам адреса; и несколько вейев, из которых нужный выбирается произвольно — чаще всего, по правилу LRU.
Для каждого блока хранится тэг, содержащий адрес хранимых в блоке данных в основной памяти. При обращении к памяти все теги нужного сета сравниваются с тегом искомого адреса. Например, для кэша из 32 блоков, организованных в 4 вея:
Благодаря тому, что сет выбирается по младшим битам адреса, непрерывный в памяти массив будет располагаться непрерывно и в кэше. Например, если размер блока — 64 байта, и первый блок массива попал в сет 0:
Если массив помещается в кэше целиком, то при обращении к нему не возникает промахов: каждый следующий блок массива попадает в следующий свободный вей. При последующих проходах по массиву он весь будет читаться из кэша, и новых обращений к памяти следующего уровня не потребуется.
Если же размер массива превышает размер кэша, то в соответствии с правилом LRU первые блоки массива будут вытеснены его последними блоками. Например, если массив состоит из 35 блоков, то первые три блока будут вытеснены:
Теперь при втором проходе по массиву первые три сета будут заполняться по-новой из следующего уровня памяти, а остальные пять сетов будут читаться прямо из кэша. В конце второго прохода последние три блока снова вытеснят первые блоки массива:
Таким образом, при каждом следующем проходе 20 блоков будут читаться из кэша, а остальные 15 — из следующего уровня памяти. Когда размер массива превышает размер кэша на целый вей (в нашем примере, на 8 блоков), данные между проходами не будут сохраняться в кэше: каждое обращение будет приводить к промаху и к чтению нового блока из памяти следующего уровня.
Что имеем в сухом остатке?
Далее, по крутизне ступеньки можно судить об ассоциативности кэша. Если кэш неассоциативный (прямое отображение: только один вей), то размер вея равен размеру кэша, и 100% промахов начинаются с двукратного размера кэша. Если кэш двухвейный, то размер вея — половина размера кэша, и правый край ступеньки — полтора размера кэша. И так далее: если кэш полностью ассоциативный (только один сет), то размер вея равен размеру блока, и ступенька вертикальная: превышение размера кэша даже на один блок приводит к 100% промахов.
На нашем графике первая ступенька чётко вертикальная, а вторая довольно размазанная. Можно сделать вывод, что кэш первого уровня разденьный для кода и данных, и поэтому каждый проход по массиву вызывает одни и те же события в кэше; а кэш второго уровня общий, поэтому в нём лежит также и код тестовой программы, и код и данные ОС; поэтому вторая ступенька начинается ещё до того, как размер массива достигнет размера кэша. Размер кэша — это тот размер массива, с которого начинается воспроизводимый линейный рост времени доступа к массиву; на нашем графике это 6МБ, что подтверждается и данными спецификации на процессор.
Зависимость времени доступа от размера массива проанализирована. Что насчёт размера шага? Первый важный факт: для одного и того же размера массива размер шага не влияет на количество промахов. Если шаг больше размера блока, то в кэш будет читаться не весь массив, а отдельные блоки; часть сетов останутся свободными. В любом случае, получаем 0% промахов до тех пор, пока массив меньше кэша, и 100% промахов, если массив больше на один вей. Например, для массива размером 36 блоков, и шага в 128 байт (2 блока):
На каждом проходе возникает промах в сетах 0 и 2, и 10 блоков читаются из памяти по-новой. Содержимое сетов 4 и 6 (8 блоков) сохраняется между проходами, и читается напрямую из кэша. Имеем 10/18=56% промахов. Если же шаг равен 256 байт (4 блока):
На каждом проходе возникает промах в сете 0, и 5 блоков читаются из памяти по-новой. Содержимое сета 4 (4 блока) сохраняется между проходами, и читается напрямую из кэша. Имеем 5/9=56% промахов.
Ситуация несколько меняется, если размер шага превышает размер вея: в этом случае «пропущенные» веи остаются свободными, и в кэш помещаются все прочитанные блоки массива, даже если сам массив больше размера кэша. Например, для массива размером 64 блока, и шага в килобайт (16 блоков), читаются всего четыре блока, и все они попадают в один и тот же сет:
Аналогичная ситуация всегда имеет место с полностью ассоциативным кэшем, у которого размер вея совпадает с размером блока. Отличительная черта такого прохода — левый край ступеньки сдвигается в зависимости от размера шага: вдвое большему шагу соответствует вдвое больший «кажущийся» размер кэша, потому что каждый второй вей «пропускается» при чтении.
На графике, приведённом в начале, левые края ступенек совпадают для всех размеров шага — значит, размер вея каждого кэша больше максимального из испробованных размеров шага, и составляет как минимум 4КБ. Для кэша L1 видим вертикальную ступеньку: 0% промахов для массива размером 32КБ, и 100% промахов для массива в 36КБ. Как мы видели выше, это означает, что добавка 4КБ наполняет вей целиком; стало быть, размер вея — в точности 4КБ, т.е. кэш L1 восьмивейный.
Для кэша L2 видим линейный рост примерно до 12МБ, т.е. до удвоенного размера кэша, что соответствует неассоциативному кэшу. Тем не менее, в спецификации на процессор указано, что кэш L2 24-вейный, т.е. с размером вея 256КБ. Можно сделать вывод, что либо реализация кэша не соответствует спецификации (разве кто-то обратил бы на это внимание?), либо алгоритм выбора вея отличается от LRU. В любом случае стоит отметить, что фактическое время доступа к кэшу при циклическом проходе по большому массиву оказывается лучше (более пологая ступенька), чем если бы кэш был на самом деле 24-вейным LRU.
И ещё пара интересных явлений, которые можно наблюдать на графике. Начиная с массива размером 1МБ, время доступа к памяти зависит от величины шага — как мы видели выше, это невозможно объяснить возникновением промахов в кэше. Похожая картина наблюдалась бы, будь размер шага меньше размера блока: тогда после переполнения кэша число промахов достигает не 100%, а меньшего уровня, зависящего от размера шага. Для шага в полблока получаем 50% промахов (после каждого чтения блока из памяти следующего уровня, читаем следующий элемент массива уже из кэша); для шага в четверть блока получаем 25% промахов (после каждого чтения блока из памяти — три чтения из кэша), и т.д. Как же могут быть в кэше блоки размером в несколько килобайт?
Дело, как можно догадаться, в страничной организации памяти, и в переполнении DTLB. 1МБ — это 256 четырёхкилобайтных страниц; значит, ёмкость нашёго DTLB — 256 записей. Когда массив превышает 1МБ, то при каждом чтении элемента, кроме чтения собственно данных массива, требуется прочитать из памяти ещё и запись таблицы страниц (PTE). Для шага в 512 байт после каждого чтения PTE следуют семь попаданий в DTLB, и 12% промахов едва заметно повышают время доступа к массиву. С другой стороны, для шага в 4КБ каждое чтение PTE выполняется из памяти (100% промахов в DTLB), и время доступа растёт существенно. Видим, что 100% промахов в DTLB достигаются не немедленно, а на массиве размером 1280КБ, т.е. превышающем ёмкость DTLB на четверть. Заключаем из этого, что DTLB четырёхвейный.
Другое интересное явление — что время доступа к массиву, превышающему размер кэша L2 (т.е. каждое обращение выполняется к памяти последнего уровня, RAM) также зависит от размера шага, причём разница больше, чем можно было бы объяснить промахами в DTLB. Дополнительную разницу объясняет протокол SDRAM, в котором разделены операции «открытия строчки памяти» и «чтения из открытой строчки». Аналогично с промахами в DTLB, меньший шаг позволяет прочитать следующий элемент массива из уже открытой строчки, тогда как при большем шаге требуется открывать новую строчку при каждом обращении. Численную проверку соответствия наблюдаемой задержки задержке открытия строчки я не выполнил, т.к. не смог найти спецификацию на использованные модули памяти.
Для одноразовой оптимизации необходимые значения можно посмотреть в спецификации на компьютер, но когда требуется автоматическая оптимизация (например, во время сборки и установки программы), характеристики приходится определять косвенно, по результатам прогона специального набора тестов.
Удобная тестовая программа для Linux —
lat_mem_rd из пакета тестов lmbench. Её работа заключается в том, что она выделяет в памяти массив и читает его элементы с заданным шагом, циклически проходя по массиву снова и снова. Затем выделяется массив большего размера, и т.д. Для каждого значения шага и размера массива подсчитывается среднее время доступа.Пример графика, который был получен этой программой на реальной системе:
Вспомним, что кэш разбит на блоки (строки): каждый блок хранится как неделимая единица, и читается из следующего уровня памяти целиком. Младшие биты адреса определяют смещение искомого байта в блоке кэша. Блоки обычно организованы двумерно: несколько сетов, из которых нужный выбирается по следующим младшим битам адреса; и несколько вейев, из которых нужный выбирается произвольно — чаще всего, по правилу LRU.
Для каждого блока хранится тэг, содержащий адрес хранимых в блоке данных в основной памяти. При обращении к памяти все теги нужного сета сравниваются с тегом искомого адреса. Например, для кэша из 32 блоков, организованных в 4 вея:
Благодаря тому, что сет выбирается по младшим битам адреса, непрерывный в памяти массив будет располагаться непрерывно и в кэше. Например, если размер блока — 64 байта, и первый блок массива попал в сет 0:
Если массив помещается в кэше целиком, то при обращении к нему не возникает промахов: каждый следующий блок массива попадает в следующий свободный вей. При последующих проходах по массиву он весь будет читаться из кэша, и новых обращений к памяти следующего уровня не потребуется.
Если же размер массива превышает размер кэша, то в соответствии с правилом LRU первые блоки массива будут вытеснены его последними блоками. Например, если массив состоит из 35 блоков, то первые три блока будут вытеснены:
Теперь при втором проходе по массиву первые три сета будут заполняться по-новой из следующего уровня памяти, а остальные пять сетов будут читаться прямо из кэша. В конце второго прохода последние три блока снова вытеснят первые блоки массива:
Таким образом, при каждом следующем проходе 20 блоков будут читаться из кэша, а остальные 15 — из следующего уровня памяти. Когда размер массива превышает размер кэша на целый вей (в нашем примере, на 8 блоков), данные между проходами не будут сохраняться в кэше: каждое обращение будет приводить к промаху и к чтению нового блока из памяти следующего уровня.
Что имеем в сухом остатке?
- пока массив меньше кэша, время доступа к нему будет постоянным (0% промахов)
- когда массив больше кэша менее чем на один вей, время доступа к нему будет зависеть от размера «излишка»
- когда массив больше кэша на один вей или более, время доступа к нему будет постоянным (100% промахов)
Далее, по крутизне ступеньки можно судить об ассоциативности кэша. Если кэш неассоциативный (прямое отображение: только один вей), то размер вея равен размеру кэша, и 100% промахов начинаются с двукратного размера кэша. Если кэш двухвейный, то размер вея — половина размера кэша, и правый край ступеньки — полтора размера кэша. И так далее: если кэш полностью ассоциативный (только один сет), то размер вея равен размеру блока, и ступенька вертикальная: превышение размера кэша даже на один блок приводит к 100% промахов.
На нашем графике первая ступенька чётко вертикальная, а вторая довольно размазанная. Можно сделать вывод, что кэш первого уровня разденьный для кода и данных, и поэтому каждый проход по массиву вызывает одни и те же события в кэше; а кэш второго уровня общий, поэтому в нём лежит также и код тестовой программы, и код и данные ОС; поэтому вторая ступенька начинается ещё до того, как размер массива достигнет размера кэша. Размер кэша — это тот размер массива, с которого начинается воспроизводимый линейный рост времени доступа к массиву; на нашем графике это 6МБ, что подтверждается и данными спецификации на процессор.
Зависимость времени доступа от размера массива проанализирована. Что насчёт размера шага? Первый важный факт: для одного и того же размера массива размер шага не влияет на количество промахов. Если шаг больше размера блока, то в кэш будет читаться не весь массив, а отдельные блоки; часть сетов останутся свободными. В любом случае, получаем 0% промахов до тех пор, пока массив меньше кэша, и 100% промахов, если массив больше на один вей. Например, для массива размером 36 блоков, и шага в 128 байт (2 блока):
На каждом проходе возникает промах в сетах 0 и 2, и 10 блоков читаются из памяти по-новой. Содержимое сетов 4 и 6 (8 блоков) сохраняется между проходами, и читается напрямую из кэша. Имеем 10/18=56% промахов. Если же шаг равен 256 байт (4 блока):
На каждом проходе возникает промах в сете 0, и 5 блоков читаются из памяти по-новой. Содержимое сета 4 (4 блока) сохраняется между проходами, и читается напрямую из кэша. Имеем 5/9=56% промахов.
Ситуация несколько меняется, если размер шага превышает размер вея: в этом случае «пропущенные» веи остаются свободными, и в кэш помещаются все прочитанные блоки массива, даже если сам массив больше размера кэша. Например, для массива размером 64 блока, и шага в килобайт (16 блоков), читаются всего четыре блока, и все они попадают в один и тот же сет:
Аналогичная ситуация всегда имеет место с полностью ассоциативным кэшем, у которого размер вея совпадает с размером блока. Отличительная черта такого прохода — левый край ступеньки сдвигается в зависимости от размера шага: вдвое большему шагу соответствует вдвое больший «кажущийся» размер кэша, потому что каждый второй вей «пропускается» при чтении.
На графике, приведённом в начале, левые края ступенек совпадают для всех размеров шага — значит, размер вея каждого кэша больше максимального из испробованных размеров шага, и составляет как минимум 4КБ. Для кэша L1 видим вертикальную ступеньку: 0% промахов для массива размером 32КБ, и 100% промахов для массива в 36КБ. Как мы видели выше, это означает, что добавка 4КБ наполняет вей целиком; стало быть, размер вея — в точности 4КБ, т.е. кэш L1 восьмивейный.
Для кэша L2 видим линейный рост примерно до 12МБ, т.е. до удвоенного размера кэша, что соответствует неассоциативному кэшу. Тем не менее, в спецификации на процессор указано, что кэш L2 24-вейный, т.е. с размером вея 256КБ. Можно сделать вывод, что либо реализация кэша не соответствует спецификации (разве кто-то обратил бы на это внимание?), либо алгоритм выбора вея отличается от LRU. В любом случае стоит отметить, что фактическое время доступа к кэшу при циклическом проходе по большому массиву оказывается лучше (более пологая ступенька), чем если бы кэш был на самом деле 24-вейным LRU.
И ещё пара интересных явлений, которые можно наблюдать на графике. Начиная с массива размером 1МБ, время доступа к памяти зависит от величины шага — как мы видели выше, это невозможно объяснить возникновением промахов в кэше. Похожая картина наблюдалась бы, будь размер шага меньше размера блока: тогда после переполнения кэша число промахов достигает не 100%, а меньшего уровня, зависящего от размера шага. Для шага в полблока получаем 50% промахов (после каждого чтения блока из памяти следующего уровня, читаем следующий элемент массива уже из кэша); для шага в четверть блока получаем 25% промахов (после каждого чтения блока из памяти — три чтения из кэша), и т.д. Как же могут быть в кэше блоки размером в несколько килобайт?
Дело, как можно догадаться, в страничной организации памяти, и в переполнении DTLB. 1МБ — это 256 четырёхкилобайтных страниц; значит, ёмкость нашёго DTLB — 256 записей. Когда массив превышает 1МБ, то при каждом чтении элемента, кроме чтения собственно данных массива, требуется прочитать из памяти ещё и запись таблицы страниц (PTE). Для шага в 512 байт после каждого чтения PTE следуют семь попаданий в DTLB, и 12% промахов едва заметно повышают время доступа к массиву. С другой стороны, для шага в 4КБ каждое чтение PTE выполняется из памяти (100% промахов в DTLB), и время доступа растёт существенно. Видим, что 100% промахов в DTLB достигаются не немедленно, а на массиве размером 1280КБ, т.е. превышающем ёмкость DTLB на четверть. Заключаем из этого, что DTLB четырёхвейный.
Другое интересное явление — что время доступа к массиву, превышающему размер кэша L2 (т.е. каждое обращение выполняется к памяти последнего уровня, RAM) также зависит от размера шага, причём разница больше, чем можно было бы объяснить промахами в DTLB. Дополнительную разницу объясняет протокол SDRAM, в котором разделены операции «открытия строчки памяти» и «чтения из открытой строчки». Аналогично с промахами в DTLB, меньший шаг позволяет прочитать следующий элемент массива из уже открытой строчки, тогда как при большем шаге требуется открывать новую строчку при каждом обращении. Численную проверку соответствия наблюдаемой задержки задержке открытия строчки я не выполнил, т.к. не смог найти спецификацию на использованные модули памяти.
