Информатика · объяснение и практика
Локальность памяти: почему порядок обхода меняет обращения к строкам кэша
Временная и пространственная локальность памяти: собственные трассы обращений, размер блока и пределы предсказания.

В теме Операционные системы и память: углубление · Учебная карта
В маршруте Цифровая схема и работа вычислителя · 10 тем
Главная мысль
Временная локальность — склонность снова обращаться к недавно использованным данным. Пространственная — обращаться к соседним адресам. Это свойства наблюдаемой нагрузки, а не обещание, что любой кэш ускорит любую программу.
Повтор адреса и соседство — разные признаки
Сравним трассы 100, 101, 102, 103 и 100, 900, 100, 900. В первой виден последовательный проход по соседним адресам, во второй — возврат к двум местам. Один и тот же алгоритм может проявлять оба свойства на разных временных масштабах, поэтому эти названия не делят программы на два несовместимых класса.
Чтобы рассуждать о кэше, нужно знать единицу переноса. Если один блок содержит четыре соседние ячейки, загрузка адреса 100 может подготовить данные для 101, 102 и 103. Если каждая ячейка переносится отдельно, тот же порядок адресов ещё не даёт этого конкретного выигрыша. Само слово «рядом» требует масштаба.
Проверим маленький последовательный проход
Возьмём холодный кэш, блоки по четыре адреса и достаточно места, чтобы не вытеснять загруженное. Адреса 20–23 относятся к одному блоку, 24–27 — к следующему. При чтении 20, 21, 22, 23, 24, 25 случатся две загрузки блока: на 20 и на 24. Остальные четыре обращения найдут нужный блок.
Если затем прочитать 20 снова, уже проявится временное повторное использование. Если между проходами кэш заняли другие данные и вытеснили первый блок, попадания не будет. Поэтому трасса без вместимости и правила вытеснения недостаточна для точного числа промахов; условие об отсутствии вытеснения здесь принципиально.
Пример
Блоки [20–23] и [24–27], трасса 20,21,22,23,24,25: 2 промаха и 4 попадания.
Подсчитываем первые обращения к блокам, а не объявляем каждое новое числовое значение обязательным промахом.
Не превращаем наблюдение в универсальный закон
Один проход по большому массиву может использовать соседство, но почти не возвращаться к прежним значениям. Непредсказуемые указатели могут ослаблять соседство. А небольшой повторяющийся набор обычно полезен только пока помещается в соответствующий уровень памяти; размер задачи способен изменить картину.
При сравнении двух реализаций отдельно фиксируют алгоритм, расположение данных и измерения на конкретной машине. Снижение числа операций не всегда означает такое же снижение времени, а удачная локальность не исправляет неправильный результат. Сначала проверяют смысл вычисления, затем объясняют возможную причину измеренного ускорения.
От чтения к действию
А теперь — вы
Частые вопросы
Локальность означает, что данные физически лежат рядом?
Пространственная локальность относится к адресам на выбранном уровне модели. Для реального оборудования важны перевод адресов и организация блоков.
Можно по двум обращениям гарантировать скорость?
Нет. Они могут показать повтор или соседство, но не определяют задержки всей программы.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
LRU: как последнее обращение меняет следующего кандидата на удаление
LRU на трассе запросов: порядок последнего использования, попадание и вытеснение, различие с FIFO и сроком годности.
Открыть темуСтраница памяти: отделяем номер страницы от смещения
Виртуальный адрес: номер страницы, смещение и перевод в физический кадр на собственном числовом примере.
Открыть тему