Локализация ссылок при обращении к памяти

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

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

К счастью, программы обращаются к коду и данным в своем адресном пространстве неравномерно. На практике наблюдается явная тенденция к локализации обращений к определенным небольшим участкам памяти – локализация (или локальность) ссылок.

Можно выделить пространственную и временную локализацию. Сущность явления пространственной локализации состоит в том, что после обращения по некоторому адресу в памяти, сохраняется высокая вероятность того, что следующие обращения будут направлены по близлежащим адресам. Сущность явления временной локализации состоит в том, что после обращения по некоторому адресу в памяти, сохраняется высокая вероятность того, что в ближайшее время последуют новые обращения по тому же адресу.

Локализация ссылок при обращениях к памяти – это объективное свойство, присущее практически всем данным в памяти компьютера. Локализация ссылок объясняется особенностями архитектуры программ, структур данных и самого процессора.

В частности, пространственная локализация объясняется следующими причинами:

• последовательное выполнение кода программы – в большинстве случаев, процессор, выполнив очередную инструкцию программы, принимает на выполнение следующую инструкцию, расположенную в памяти непосредственно за только что выполненной;

• группировка данных в структуры – разрабатывая программу, программисты обычно группируют логически связанные данные в структуры и широко используют массивы для работы с векторами однотипных данных, обработка всех логически связанных данных обычно выполняется в одном и том же месте программы, и после обращения к одному элементу массива, последует обращение к следующему элементу, и т.д.

В свою очередь, временная локализация объясняется следующим:

• наличие циклов – выполнение тела цикла неизбежно повлечет многократные обращения к одним и тем же данным;

• наличие счетчиков и флагов – в программах широко используются различные счетчики и флаги, обращения к которым регулярно происходят на протяжении всего времени выполнения программы.

• наличие подпрограмм – в программах часто вызываются одни и те же функции и процедуры для выполнения некоторых стандартных действий, в результате многократно используется один и тот же фрагмент кода.

Благодаря локализации ссылок, даже небольшой фрагмент кода и данных программы, размещенный на верхнем уровне в иерархии памяти, обеспечивает высокий процент попаданий при обращениях к памяти, и, как следствие, высокое быстродействие всей памяти, соизмеримое с быстродействием верхнего уровня.

Именно на свойствах локальности при обращениях к данным основана работа виртуальной памяти и кэшей всех уровней, от процессорного до дискового.