Зависимость времени доступа от размера массива проанализирована. Что насчёт размера шага? Первый важный факт: для одного и того же размера массива размер шага не влияет на количество промахов. Если шаг больше размера блока, то в кэш будет читаться не весь массив, а отдельные блоки; часть сетов останутся свободными. В любом случае, получаем 0% промахов до тех пор, пока массив меньше кэша, и 100% промахов, если массив больше на один вей. Например, для массива размером 36 блоков, и шага в 128 байт (2 блока):
На нашем графике первая ступенька чётко вертикальная, а вторая довольно размазанная. Можно сделать вывод, что кэш первого уровня разденьный для кода и данных, и поэтому каждый проход по массиву вызывает одни и те же события в кэше; а кэш второго уровня общий, поэтому в нём лежит также и код тестовой программы, и код и данные ОС; поэтому вторая ступенька начинается ещё до того, как размер массива достигнет размера кэша. Размер кэша это тот размер массива, с которого начинается воспроизводимый линейный рост времени доступа к массиву; на нашем графике это 6МБ, что подтверждается и данными спецификации на процессор.
Далее, по крутизне ступеньки можно судить об ассоциативности кэша. Если кэш неассоциативный (прямое отображение: только один вей), то размер вея равен размеру кэша, и 100% промахов начинаются с двукратного размера кэша. Если кэш двухвейный, то размер вея половина размера кэша, и правый край ступеньки полтора размера кэша. И так далее: если кэш полностью ассоциативный (только один сет), то размер вея равен размеру блока, и ступенька вертикальная: превышение размера кэша даже на один блок приводит к 100% промахов.
Поэтому каждому уровню кэша соответствует одна «ступенька» на графике, и размер кэша левый край ступеньки. На графике, приведённом в начале, ступеньки две 32КБ и около 4МБ, значит, кэш двухуровневый.
когда массив больше кэша на один вей или более, время доступа к нему будет постоянным (100% промахов)
когда массив больше кэша менее чем на один вей, время доступа к нему будет зависеть от размера «излишка»
пока массив меньше кэша, время доступа к нему будет постоянным (0% промахов)
Что имеем в сухом остатке?
Таким образом, при каждом следующем проходе 20 блоков будут читаться из кэша, а остальные 15 из следующего уровня памяти. Когда размер массива превышает размер кэша на целый вей (в нашем примере, на 8 блоков), данные между проходами не будут сохраняться в кэше: каждое обращение будет приводить к промаху и к чтению нового блока из памяти следующего уровня.
Теперь при втором проходе по массиву первые три сета будут заполняться по-новой из следующего уровня памяти, а остальные пять сетов будут читаться прямо из кэша. В конце второго прохода последние три блока снова вытеснят первые блоки массива:
Если же размер массива превышает размер кэша, то в соответствии с правилом LRU первые блоки массива будут вытеснены его последними блоками. Например, если массив состоит из 35 блоков, то первые три блока будут вытеснены:
Если массив помещается в кэше целиком, то при обращении к нему не возникает промахов: каждый следующий блок массива попадает в следующий свободный вей. При последующих проходах по массиву он весь будет читаться из кэша, и новых обращений к памяти следующего уровня не потребуется.
Благодаря тому, что сет выбирается по младшим битам адреса, непрерывный в памяти массив будет располагаться непрерывно и в кэше. Например, если размер блока 64 байта, и первый блок массива попал в сет 0:
Для каждого блока хранится тэг, содержащий адрес хранимых в блоке данных в основной памяти. При обращении к памяти все теги нужного сета сравниваются с тегом искомого адреса. Например, для кэша из 32 блоков, организованных в 4 вея:
Вспомним, что кэш разбит на блоки (строки): каждый блок хранится как неделимая единица, и читается из следующего уровня памяти целиком. Младшие биты адреса определяют смещение искомого байта в блоке кэша. Блоки обычно организованы двумерно: несколько сетов, из которых нужный выбирается по следующим младшим битам адреса; и несколько вейев, из которых нужный выбирается произвольно чаще всего, по правилу LRU.
Пример графика, который был получен этой программой на реальной системе:
Удобная тестовая программа для Linux lat_mem_rd из пакета тестов . Её работа заключается в том, что она выделяет в памяти массив и читает его элементы с заданным шагом, циклически проходя по массиву снова и снова. Затем выделяется массив большего размера, и т.д. Для каждого значения шага и размера массива подсчитывается среднее время доступа.
Для одноразовой оптимизации необходимые значения можно посмотреть в спецификации на компьютер, но когда требуется автоматическая оптимизация (например, во время сборки и установки программы), характеристики приходится определять косвенно, по результатам прогона специального набора тестов.
В ряде случаев (например, для тонкой оптимизации программы под конкретный компьютер) полезно знать характеристики кэш-подсистемы: количество уровней, время доступа к каждому уровню, их размер и ассоциативность, и т.п.
Железо / Экспериментальное определение характеристик кэш-памяти | Gliffer
Комментариев нет:
Отправить комментарий