Оценка среднего времени доступа к данным при использовании многоуровневой модели памяти

Рассмотрим следующую формальную модель многоуровневой памяти. Пусть память представлена уровнем, пронумерованными от до . Пусть нулевой уровень – это верхний, наиболее быстрый уровень памяти, -ый уровень – нижний, наиболее медленный. Пусть при обращении к некоторому -му уровню памяти требуемые данные будут получены с вероятностью . Вероятность называется вероятностью промаха при обращении к памяти. Пусть среднее время доступа к памяти на -ом уровне иерархии.

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

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

( 0 )

Среднее время может быть в свою очередь вычислено по аналогичной формуле, и т.д., пока не дойдем до самого нижнего уровня:

( 0 )

Учитывая, что , выражение (0) можно записать в окончательном виде (0).

( 0 )

Проанализируем полученное выражение. Очевидно, что при низкой вероятности промаха, среднее время доступа определяется в основном верхними, наиболее быстрыми уровнями, так как вероятность обращения к медленным нижним уровням быстро падает. Рассмотрим следующий пример.

Пусть в компьютере представлена трехуровневая иерархия памяти, как показано на рис. 21. Пусть среднее время доступа к кэш-памяти равно 1 нс. Очевидно, что среднее время доступа существенно зависит от вероятности промаха при обращении к каждому из уровней памяти. Для современных процессоров типичной является вероятность промаха кэша около 10%.

Штрафное время для кэш-памяти в современных процессорах можно положить равным нулю, т.к. современные процессоры обычно начинают процедуру обращения к кэш-памяти и к ОЗУ одновременно. Если данные будут найдены в кэше, то процедура обращения к ОЗУ прерывается. Если же происходит кэш-промах, то выборка данных из ОЗУ выполняется без штрафного времени, т.к. была начата заблаговременно.

Среднее время доступа к ОЗУ положим равным 20 нс. Вероятность промаха при обращении к ОЗУ можно грубо оценить на основании вероятности промаха кэша, сопоставив их объемы. Положим, что объем ОЗУ в 1000 раз больше объема кэша, тогда вероятность промаха . Штрафное время для ОЗУ положим равным 1 нс, т.к. современным процессорам не требуется выполнять полный цикл доступа к памяти для выявления промаха – необходимые структуры данных, описывающие размещение данных в ОЗУ, доступны внутри процессора.

Для жесткого диска среднюю скорость доступа примем равной 10 мс. Тогда среднее время доступа к памяти, рассчитанное по формуле (0), составит примерно 3 нс, что существенно меньше, чем среднее время доступа к ОЗУ, и вплотную приближается к характеристикам кэша.