Когда возникает ошибка страницы или промах кеша, мы можем использовать либо алгоритмы «наименее недавно использовавшиеся» (LRU), либо алгоритмы «первым в списке» (FIFO), либо алгоритмы случайной замены. Мне было интересно, какой из них обеспечивает наилучшую производительность, а также наименьшие возможные будущие ошибки промаха/страницы кеша?
Архитектура: процессор Coldfire
Идеальной политики кэширования не существует, потому что она требует знания будущего (как программа будет обращаться к памяти).
Но некоторые из них заметно лучше, чем другие, в случаях общего доступа к памяти. Это в случае с LRU. LRU исторически давал очень хорошие характеристики при общем использовании.
Но для того, что вы пытаетесь сделать, другая политика может быть лучше. Всегда существует какой-то шаблон доступа к памяти, из-за которого политика кэширования работает плохо.
Вы можете найти эту ветку полезной (и более сложной!) Почему LRU лучше, чем FIFO?< /а>
Выражение "Глупых вопросов не бывает" как нельзя лучше подходит к этому. Это был такой хороший вопрос, что мне пришлось создать учетную запись, опубликовать в ней и поделиться своим мнением как человека, который смоделировал кэши на паре процессоров.
Вы указываете архитектуру 68000, которая представляет собой ЦП, а не контроллер графического процессора или USB, или другое оборудование, которое может получить доступ к кешу, однако...
Поэтому код, который вы запускаете на 68000, будет иметь огромное значение для части вопроса «наименее возможный будущий промах кеша/ошибки страницы».
В этом вы различаете промахи кеша и ошибки страницы, я не уверен, какую именно архитектуру coldfire вы имеете в виду, но я предполагаю, что это не имеет аппаратной замены TLB, он использует программный механизм (поэтому кеш будет совместно с данными приложений).
В политике замещения наиболее важным фактором является количество ассоциаций (или путей).
Кэш прямой карты (1 способ) напрямую коррелирует (в большинстве случаев) с младшими битами адреса (количество бит определяет размер кеша), поэтому кеш 32 КБ будет младшими 15 битами. В этом случае замена алгоритмов LRU, FIFO или Random будет бесполезна, так как есть только один возможный выбор.
Однако выбор кэша с обратной или сквозной записью будет иметь больший эффект. Только для записи в память Сквозная запись означает, что строка кеша не выделяется, в отличие от кеша с обратной записью, где строка, которая в настоящее время находится в кеше, которая использует те же младшие 15 бит, извлекается из кеша и считывается обратно, а затем модифицируется для использования IF код, работающий на ЦП, использует эти данные).
Для операций, которые записывают и не выполняют несколько операций над данными, сквозная запись обычно намного лучше, в том числе на современных процессорах (и я не знаю, поддерживает ли ее эта архитектура), но сквозная запись или обратная запись могут быть выбраны на TLB/странице. основа. Это может иметь гораздо большее влияние на кеш, чем политика, вы можете запрограммировать систему так, чтобы она соответствовала типу данных на каждой странице, особенно в кеше прямой карты ;-)
Таким образом, прямой кеш карты довольно легко понять, также легко понять основу кеша в худшем случае, лучшем случае и среднем случае.
Представьте процедуру memcpy, которая копирует данные, соответствующие размеру кеша. Например, кэш прямого отображения 32 КБ с двумя буферами 32 КБ, выровненными по границе 32 КБ ....
0x0000 -> read
0x8000 -> write
0x8004 -> read
0x8004 -> write
...
0x8ffc -> read
0x8ffc -> write
Здесь вы видите чтение и запись, поскольку они копируют каждое слово данных, обратите внимание, что младшие 15 бит одинаковы для каждой операции чтения и записи.
Кэш с прямым отображением, использующий обратную запись (помните, что обратная запись выделяет строки, делает следующее)
0x0000 -> read
cache performs: (miss)
0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)
0x8000 -> write
cache performs: (miss)
invalidate 0x0000:0x001f (line 0)
0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
0x8000 (modify this location in the cache with the read source data)
<loop>
0x0004 -> read
cache performs: (miss)
writeback 0x8000:0x801f -> WRITE to main memory (ie. write 32 bytes to the desitnation)
0x0000:0x001f -> READ from main memory (ie. read 32 bytes of source (the same as we did just before)
0x8004 -> write
cache performs: (miss)
invalidate 0x0000:0x001f (line 0)
0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
0x8004 (modify this location in the cache with the read source data)
</loop> <--- (side note XML is not a language but we use it as such)
Как вы видите, происходит много операций с памятью, это на самом деле называется «перебором» и является лучшим примером сценария наихудшего случая.
Теперь представьте, что мы используем кеш со сквозной записью, это операции:
<loop>
0x0000 -> read
cache performs: (miss)
0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)
0x8000 -> write
cache performs: (not a miss)
(not a lot, the write is "posted" to main memory) (posted is like a letter you just place it in the mailbox and you don't care if it takes a week to get there).
<loop>
0x0004 -> read
cache performs: (hit)
(not a lot, it just pulls the data it fetched last time which it has in it's memory so it goes very quickly to the CPU)
0x8004 -> write
cache performs: (not a miss)
(not a lot, the write is "posted" to main memory)
</loop until next 32 bytes>
</loop until end of buffer>
Как вы можете видеть огромную разницу, мы теперь не трэш, на самом деле мы в лучшем случае в этом примере.
Итак, это простой случай сквозной записи и обратной записи.
Прямые кеши карт, однако, сейчас не очень распространены, большинство людей используют 2, 4 или 8-канальные кеши, то есть есть 2, 4 или 8 различных возможных распределений в строке. Таким образом, мы можем хранить 0x0000, 0x8000, 0x1000, 0x1800 в кеше одновременно в 4- или 8-канальном кеше (очевидно, что 8-канальный кеш также может хранить 0x2000, 0x2800, 0x3000, 0x3800).
Это позволит избежать этой проблемы с пробуксовкой.
Просто чтобы уточнить номер строки в 32-килобайтном кэше с прямым отображением, это нижние 15 бит адреса. В случае 32k 2 это нижние 14 бит. В случае 32k 4 это нижние 13 бит. В формате 32k 8 это нижние 12 бит.
А в полноассоциативном кеше это размер строки (или нижние 5 бит при 32-байтовой строке). У вас не может быть меньше строки. 32 байта, как правило, являются наиболее оптимальной операцией в системе памяти DDR (есть и другие причины, иногда 16 или иногда 64 байта могут быть лучше, а 1 байт будет оптимальным в алгоритмическом случае, давайте использовать 32, так как это очень распространено)
Чтобы помочь понять LRU, FIFO и Random, рассмотрим, что кеш является полностью ассоциативным, в 32-байтном 32-байтовом линейном кеше это 1024 строки.
Политика случайной замены будет случайным образом вызывать в худшем случае каждые 1024 замены (т. е. 99,9% попаданий), либо в LRU, либо в FIFO я всегда мог написать программу, которая бы «перебрасывала», т.е. всегда вызывают наихудшее поведение (т.е. 0% попаданий).
Очевидно, что если бы у вас был полностью ассоциативный кеш, вы бы выбрали LRU или FIFO только в том случае, если программа была известна и было известно точное поведение программы.
Для ЛЮБОГО, что не было предсказуемым на 99,9%, вы бы выбрали СЛУЧАЙНЫЙ, это просто лучший из-за того, что он не худший, и один из лучших из-за того, что он средний, но как насчет лучшего случая (где я получаю лучшую производительность)...
Ну, это зависит в основном от количества способов...
2 способа, и я могу оптимизировать такие вещи, как memcpy и другие алгоритмы, чтобы они хорошо справлялись. Рэндом ошибался в половине случаев. 4 способа, и когда я переключаюсь между другими задачами, я могу не повредить кеш настолько, что их данные все еще локальны. Рэндом ошибался в четверти случаев. 8 способов, с помощью которых теперь статистика может работать. 7/8% попаданий в memcpy не так хорошо, как 1023/1024% (полностью ассоциативный или оптимизированный код), но для неоптимизированного кода это имеет значение.
Так почему бы людям не сделать полностью ассоциативный кэш со случайной политикой замены!
Ну, это не потому, что они не могут генерировать хорошие случайные числа, на самом деле генератор псевдослучайных чисел так же хорош, и да, я могу написать программу, чтобы получить 100% процент промахов, но это не главное, я не мог написать полезную программу, которая будет иметь 100% промах, что я мог бы сделать с алгоритмом LRU или FIFO.
Строка 32 КБ по 32 байта. Полностью ассоциированный кэш требует сравнения 1024 значений, аппаратно это делается через CAM, но это дорогое аппаратное обеспечение, а также просто невозможно сравнить такое количество значений в «БЫСТРОЙ» обработке. раз, интересно, сможет ли квантовый компьютер...
В любом случае, чтобы ответить на ваш вопрос, какой из них лучше:
Использованная литература:
Многие из изученных мной архитектур используют LRU, так как он обычно обеспечивает не только эффективность реализации, но и в среднем довольно хорошо предотвращает промахи. Однако в последних архитектурах x86, я думаю, происходят более сложные вещи. LRU — это своего рода базовая модель.
Это действительно зависит от того, какие операции вы выполняете на своем устройстве. В зависимости от типов операций лучше работают разные политики эвакуации. Например, FIFO хорошо работает с последовательным обходом памяти.
Надеюсь, это поможет, я на самом деле не архитектурный парень.
Из трех я бы порекомендовал LRU. Во-первых, это хорошее приближение к оптимальному планированию, когда предполагается локальность (это оказывается хорошим предположением). Случайное планирование не может выиграть от локальности. Во-вторых, он не страдает аномалией Белади (как FIFO); то есть кэши большего размера означают лучшую производительность, что не обязательно верно для FIFO.
Только если ваша конкретная проблемная область настоятельно рекомендует использовать что-то другое, в общем случае LRU будет сложно превзойти.
Из этих трех, LRU, как правило, лучший, в то время как FIFO — худший, а случайный выбор находится где-то посередине. Вы можете создать шаблоны доступа, в которых любой из трех вариантов превосходит любой другой, но это несколько сложно. Интересно, что этот порядок также приблизительно определяет, насколько дорого они будут реализовываться: LRU — самый дорогой, а FIFO — самый дешевый. Просто идет шоу, бесплатного обеда не бывает
Если вы хотите получить лучшее из обоих миров, подумайте об адаптивном подходе, который меняет стратегию на основе реальных моделей использования. Например, взгляните на алгоритм IBM адаптивного кэша замены: http://code.activestate.com/recipes/576532-adaptive-replacement-cache-in-python/
