Модель без явного задания параметров кэша
Определение модели
Система памяти современного компьютера включает несколько иерархических уровней, каждый из которых выступает в качестве кэша для следующего; типичная иерархия может состоять из регистров, кэша 1 уровня, кэша 2 уровня, кэша 3 уровня, основной памяти и дисковой памяти (рис. 1). Одна из характеристик иерархии заключается в том, что уровни памяти становятся больше и медленнее по мере удаления от процессора; разница в скорости доступа оказывается самой масштабной при переходе от оперативной памяти к дисковой. Еще одно свойство заключается в том, что данные перемещаются между уровнями в виде блоков.
Разница в скорости доступа между уровнями приводит к тому, что стоимость обращений к памяти в значительной мере зависит от того, на каким самом внутреннем уровне памяти находится нужный элемент. Таким образом, схема обращений к памяти некоторого алгоритма в значительной мере определяет время его выполнения на практике. К сожалению, RAM-модель (рис. 2), традиционно используемая для разработки и анализа алгоритмов, не отражает этого, поскольку предполагает, что все обращения к памяти занимают одинаковое время.
Рис. 1. Иерархия памяти
Рис. 2. RAM-модель
Рис. 3. Модель ввода-вывода
Рис. 4. Модель без явного задания параметров кэша
Для более адекватного отражения влияния иерархии памяти было разработано несколько вычислительных моделей. Самая простая и успешная из них – двухуровневая модель ввода-вывода, предложенная Аггарвалом и Виттером [2] (рис. 3). В этой модели используется двухуровневая иерархия памяти, состоящей из быстрой памяти размера M и более медленной памяти неограниченного размера, при этом перенос данных между уровнями осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над данными в быстрой памяти. Предполагается, что алгоритмы полностью контролируют перенос блоков между двумя уровнями. Этот процесс будет называться переносом содержимого памяти. Мерой сложности является количество выполненных переносов содержимого памяти. Преимущество модели ввода-вывода заключается в том, что она частично отражает иерархию памяти и при этом достаточно проста, чтобы на ее основе можно было выполнять разработку и анализ алгоритмов. За последние двадцать лет было получено множество результатов применения модели ввода-вывода, охватывающих большинство областей теории алгоритмов. Довольно полное представление можно получить в обзорах [3, 24, 26, 27].
Были также предложены более замысловатые модели многоуровневой памяти (см. обзор в [ ]), однако они оказались менее успешными – главным образом из-за их сложности, затрудняющей анализ алгоритмов. Все эти модели, включая модель ввода-выводы, предполагают, что характеристики иерархии памяти (уровень и размер блоков) заранее известны.
Модель памяти без явного задания параметров кэша была предложена в 1999 году Фриго и др. [ ]. Алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ должен быть действительным при любых значениях размера блока B и размера памяти M. Предполагается, что перенос содержимого памяти выполняется автоматически при помощи оптимальной автономной стратегии замещения кэша.
Главное достоинство модели ввода-вывода заключается в следующем: в силу того, что анализ в рамках модели ввода-вывода действителен при любых значениях размера блока и размера памяти, он оказывается верен для всех уровней иерархии памяти (детальное обоснование этого утверждения см. в [22, 25]). Иначе говоря, если оптимизировать алгоритм на одном, неизвестном, уровне иерархии, он будет одновременно оптимизирован на всех уровнях. Таким образом, модель явного задания параметров кэша изящно обобщает модель ввода-вывода до многоуровневой модели за счет одного простого условия: алгоритму не позволено знать значения B и M. Задача заключается в разработке алгоритмов, демонстрирующих при этих условиях наилучшее значение количество переносов.
Помимо концептуально простого отображения иерархии памяти, модель ввода-вывода также имеет и другие преимущества. Алгоритмы, разработанные на основе этой модели, не полагаются на знание параметров иерархии памяти; это может пригодиться, например, при разработке программ, которые будут работать на различных или неизвестных архитектурах (таких как библиотечные программы или программы для гетерогенных распределенных вычислений – например, сетевых коллективных вычислений и проектов наподобие SETI@home). Даже на единственной и известной архитектуре параметры памяти, доступные вычислительному процессу, могут быть непостоянными, если несколько процессов конкурируют за одни и те же ресурсы памяти. Поскольку алгоритмы без явного задания параметров кэша оптимизированы для всех значений параметров, они потенциально способны лучше адаптироваться к подобным изменениям, а также к различным размерам входных данных, вынуждающих использовать различные уровни памяти. Наконец, алгоритмы без явного задания параметров кэша автоматически оптимизируют использование буферов динамической трансляции (кэша, содержащего недавно посещенные части таблицы страниц, используемого для виртуальной памяти) процессора, что можно рассматривать как вторую иерархию памяти, параллельную упомянутой в начале обзора.
Возможными слабыми местами модели без явного задания параметров кэша являются предположение об оптимальности автономной стратегии замещения кэша и отсутствие моделирования ограниченной ассоциативности многих уровней иерархии. Первое обстоятельство смягчается тем фактом, что обычно имеющийся анализ алгоритма без явного задания параметров кэша так же хорош в случае замещения кэша при помощи политики замещения наиболее давно использовавшегося элемента, что довольно близко к фактически используемым в компьютерах стратегиях. Второе обстоятельство является слабым местом и многих других моделей памяти.