Только недавно узнал, что на 486-м процессоре для удаления строк из кэша использовался не настоящий алгоритм LRU, а т.н. псевдо-LRU. Т.е. для каждой строки счетчик обращений состоял всего из 3 бит, таким образом, после 8 обращений к строке счетсик сбрасывался в 0, т.е. самая нужная строка помечалась как самая ненужная. Возник вопрос: так ли это на современных процессорах (т.е. сам-то алгоритм такой же, вопрос сколько бит выделяется на счетчик). Нигде не нашел, только на форуме ixbt нашел утверждение что у Conroe этих бит не меньше 4 (но это понятние растяжимое). В общем, интересует разрядность счетчика LRU на C2D и K8/K10.
Member
Статус: Не в сети Регистрация: 07.10.2003 Откуда: Russia, Moscow
ты не путаешь счетчик обращений и список-порядок строк в кеше?
Там вроде бы если последний - 11 (ака 1011) то пишется что последний 10 (101 - на три бита)
на К7 вроде бы 2 последних бит не хватало, дальше зависит от параметров кеша (объема и ассоциативности).
Последние не всегда нужны, т.к. данные выровнены и загружаются не по одному значению.
Домашнее задание: посчитать сколько какому процессору надо для полного счастья бит.
_________________ В поиске включайте "Искать все слова". Избегайте многоточий.
Зачем нужен разгон? http://tsc.overclockers.ru
armadillo Насколько я понял, речь именно о счетчике обращений:
Цитата:
В 486-м процессоре появился внутренний кэш объемом 8 Кб, единый для данных и инструкций. Кэш имел 4-канальную наборно-ассоциативную архитектуру и работал на уровне физических адресов памяти. Он содержал 128 наборов по 4 строки размером по 16 байт. Кэш умел работать только со строками, и если процессор требовал какой-нибудь байт, отсутствующий в кэше, то кэш-контроллер загружал из ОЗУ всю 16-байтную строку, содержащую необходимый байт. Выбор строки для замещения производился по алгоритму "псевдо-LRU", для этого каждому набору строк отводилось по 3 бита статистики использования. Алгоритм LRU (Least Recently Used) основан на поиске элемента, к которому дольше всего не было обращений. При каждом обращении к строке кэш-контроллер увеличивал на 1 соответствующий счетчик LRU. Приставка "псевдо" означает лишь несовершенство механизма работы, ведь под счетчик отводилось всего 3 бита, что дает нам 8 положений счетчика (23). После 8-го обращения к строке счетчик обнулится и соответствующая строка из самой "необходимой" станет самой "не необходимой" и будет прямым кандидатом на замещение.
Сколько нужно бит я уже прикинул Вот мои расуждения:
Для чего вообще нужен кэш? Что бы снизить латентность памяти. Если кэш-промахи, вызванные переполнением счетчика обращений, будут происходить с периодом, намного большим (на 2-3 порядка) чем латентность шины, то никакими тестами падение производительности обнаружить не удастся, и алгоритм LRU может считаться честным. Т.е. должно выполняться условие: Tп << 2^n * T, где n - разрядность счетчика, ТП - латентность памяти, Т - продолжительность такта процессора.
Латентность памяти, насколько я помню (ссылку лень искать), составляет порядка 50 нс для процессоров АМД и 200 для Интел, частота современных процессоров достигает 3 ггц, т.е. латентность памяти составляет 150-600 тактов процессора. Т.е. при разрядности счетчика 16 бит алгоритм LRU уже может считатся настоящим, а не псевдо, т.к. 2^16=65536, что в 100-300 раз больше чем латентность памяти, выраженная в тактах.
Цитата:
Там вроде бы если последний - 11 (ака 1011) то пишется что последний 10 (101 - на три бита) на К7 вроде бы 2 последних бит не хватало, дальше зависит от параметров кеша (объема и ассоциативности). Последние не всегда нужны, т.к. данные выровнены и загружаются не по одному значению.
Честно говоря, не очень понял, можно поподробнее, о чем вы?
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 20
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения