Как найти количество пропусков конфликтов в симуляторе кеша

Я пытаюсь разработать симулятор кеша. Чтобы найти попадание / промах в кеше для блока, я сравниваю его индекс и смещение с блоками, уже присутствующими в кеше. В случае n-ассоциативного кеша я проверяю только те записи кеша, в которые может попасть этот блок.

В таком случае легко определить количество попаданий и промахов. Если кеш заполнен (или все записи, в которых может находиться блок, заняты), то у нас отсутствует емкость.

Подскажите, пожалуйста, как я могу узнать количество пропущенных конфликтов? Определение конфликта мисс говорит:

Conflict misses are those misses that could have been avoided, 
had the cache not evicted an entry earlier

Как я могу определить, нужно ли удалять ранее удаленную из кеша запись?


caching memory cpu-architecture cpu-cache computer-architecture
person nish    schedule 18.08.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете хранить все исторические адреса в хэш-карте и выполнять поиск всякий раз, когда вы промахиваетесь - если вы не попали в кеш, но попали в хэш - вы в какой-то момент удалили эту строку.

Однако он может довольно быстро увеличиваться в размерах. Однако в большинстве случаев интереснее спросить: «Мог бы я сохранить строку в кэше еще немного и избежать этого промаха?». Для этого вы можете расширить симуляцию кэша, чтобы иметь больше способов (вплоть до глубины истории, которую вы определяете, по-прежнему реалистично сохранять строки). Вы просматриваете свой кеш, как и раньше, и поддерживаете тот же метод LRU, который вы использовали бы, но если путь попадания выходит за пределы «реального» счетчика с точки зрения возраста LRU - это ошибка конфликта (то есть - линия была там, но отодвинул цепочку LRU за пределы точки, которую следовало исключить). Убедитесь, что ваш механизм LRU может работать таким образом - истинный LRU должен быть в порядке, поскольку он поддерживает строгий порядок, основанные на возрастном значении также подойдут, но другие типы, такие как псевдо-деревья LRU, могут оказаться сложными.

person Leeor    schedule 19.08.2013
comment
Другое подобное решение - просто запустить симуляцию дважды: один раз с вашей нормальной конфигурацией, а другой - с очень сильно ассоциативной конфигурацией (говорят тысячи способов). Промахи пропускной способности - это разница между промахами в двух конфигурациях. - person Danny; 20.08.2013

arrow_upward
4
arrow_downward

Концептуально вот как вы можете измерить типы промахов:

измерить количество промахов (M) для одного и того же кода для следующих кешей:

  1. Бесконечная емкость, полностью ассоциативный кеш
  2. Полностью ассоциативный кеш конечной емкости
  3. N-сторонний ассоциативный кеш конечной емкости

тогда

  • количество обязательных промахов = M1
  • количество пропусков емкости = M2-M1
  • количество конфликтных пропусков = M3- количество пропусков пропускной способности - количество обязательных пропусков = M3 - M2

При фактическом выполнении этих измерений в вашем симуляторе вам не нужно запускать три разных симуляции. Промахи в хэш-карте, описанные Лиором, дают вам M1. Теперь, если вы реализуете свою хеш-карту в виде списка (или какой-либо более эффективной структуры данных), так что вы никогда не удаляете запись, но всякий раз, когда делается доступ к адресу «x», помещайте «x» в начало списка. Всякий раз, когда делается ссылка, и она попадает в первые места 'S' в вашем списке (где S - размер вашего кеша), это может быть засчитано как HIT для кеша номер 1 и 2. Фактическое моделирование кеша (моделирование N -way cache) дает вам M3. Таким образом, фактическая модель кеша плюс эта структура данных списка дает вам M1, M2, M3 за один прогон моделирования.

person Neha Karanjkar    schedule 25.02.2014