Выражение «Там нет глупых вопросов» подходит так хорошо.Это был такой хороший вопрос, что мне пришлось создать учетную запись, опубликовать в ней и поделиться своими взглядами как человека, который смоделировал кэш на нескольких процессорах.
Вы определяете архитектуру 68000, которая является ЦП, а неGPU или контроллер USB, или другое оборудование, которое может получить доступ к кешу, однако ...
Поэтому код, который вы запускаете на 68000, будет иметь огромное значение для части вопроса "наименьший возможный кеш в будущем"miss '/ page faults ".
В этом случае вы различаете ошибки кэша и ошибки страниц. Я не уверен, к какой именно архитектуре Coldfire вы обращаетесь, но я предполагаю, что аппаратного TLB нет.для замены используется программный механизм (таким образом, кеш будет использоваться совместно с данными приложений).
В политике замены наиболее важным фактором является количество ассоциаций (или путей).
Прямой кэш карты (1 способ), напрямую коррелирует (все чаще всего) с младшими битами адреса (числобитов указывает размер кеша), поэтому кеш 32 Кбайт будет младшим 15 бит.В этом случае замена алгоритмов LRU, FIFO или Random будет бесполезна, поскольку возможен только один выбор.
Однако выбор кэша с обратной записью или записью будет иметь больший эффект.Только для записи в память Запись - означает, что строка кэша не выделена, как в случае кэша обратной записи, где строка, находящаяся в настоящее время в кэше, имеющем те же самые младшие 15 бит, выбрасывается из кэша и считывается, а затем модифицируется для использования IF.код, работающий на CPU, использует эти данные).
Для операций, которые записывают и не выполняют несколько операций над данными, тогда запись обычно выполняется намного лучше, также на современных процессорах (и я не знаю, если этоархитектура поддерживает это), но Writethrough или Writeback могут быть выбраны на основе TLB / Page.Это может иметь гораздо больший эффект на кеш, чем политика, вы можете запрограммировать систему для соответствия типу данных на каждой странице, особенно в кеше прямой карты; -)
Таким образом, кеш прямой картыдовольно легко понять, это также легко понять основание наихудшего случая, лучшего и среднего случая кеша.
Представьте себе подпрограмму 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>
Каквы можете видеть огромную разницу, которую мы сейчас не трогаем, фактически мы лучше всего в этом примере.
Хорошо, так что это простой случай сквозной записи против обратной записи.
DirectКэши карт, однако, в настоящее время не очень распространены, большинство людей используют 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 и другие algorthims, чтобы сделать хорошую работу.Рандом ошибся половину времени.4 способа, и когда я переключаюсь между другими задачами, я не могу повредить кеш настолько, чтобы их данные оставались локальными.Рандом ошибся четверть времени.8 способов, с помощью которых статистика может вступить в силу: 7/8% -ный коэффициент попадания в memcpy не так хорош, как 1023/1024% (полностью ассоциативный или оптимизированный код), но для неоптимизированного кода это имеет значение.
Так почему же люди не создают полностью ассоциативный кеш с политиками случайной замены!
Ну, это не потому, что они не могут генерировать хорошие случайные числа, на самом деле генератор псевдослучайных чисел так же хорош, и да, я могунаписать программу, чтобы получить 100% промахов, но это не главное, я не мог написать полезную программу, которая имела бы 100% промахов, что я мог бы с алгоритмом LRU или FIFO.
A32k 32-байтовая строка Полностью ассоциированный кэш требует, чтобы вы сравнили 1024 значения, в аппаратном плане это делается через CAM, но это дорогостоящее аппаратное обеспечение, и также просто невозможно сравнить это много значений во время обработки «FAST».Интересно, сможет ли квантовый компьютер ....
В любом случае, чтобы ответить на ваш вопрос, какой из них лучше:
- Подумайте, если написаноЭто может быть лучше, чем обратная запись.
- СЛУЧАЙ большого пути лучше
- Неизвестный код СЛУЧАЙ лучше для 4 пути или выше.
- Если это одна функция или вы хотите наиболеескорость от чего-то, что вы готовы оптимизировать, или если вас не волнует наихудший случай, тогда LRU, вероятно, то, что вы хотите.
- Если у вас очень мало LRU, скорее всего, то, что вы хотите, если у вас нет оченьконкретный сценарий, то FIFO может быть в порядке.
Ссылки: