Функционирование двухуровневой памяти

Принцип локализации может быть использован для разработки схемы двух­уровневой памяти. Память верхнего уровня (Ml) имеет меньшую емкость, она быст­рее, и каждый ее бит дороже по сравнению с памятью нижнего уровня (М2). Ml ис­пользуется для временного хранения определенной части содержимого более емкого уровня М2. При каждом обращении к памяти сначала делается попытка найти нуж­ные данные в Ml. Если она завершается успехом, происходит быстрый доступ. В противном случае, из М2 в Ml копируется нужный блок ячеек памяти, а затем сно­ва осуществляется доступ к Ml. В соответствии с принципами локализации к ячей­кам памяти вновь перенесенного блока произойдет еще ряд обращений, что приведет к общему ускорению работы программы.

Чтобы выразить среднее время доступа, нужно учитывать не только ско­рость работы обоих уровней памяти, но и вероятность обнаружения требуемых данных в Ml. В результате получим:

(1.1.)

где

T_S — среднее (системное) время доступа,

T₁ — время доступа к Ml (например, кэшу, дисковому кэшу),

T₂ — время доступа к М2 (например, основной памяти, диску),

Н — результативность поиска (доля ссылок на данные в Ml).

На рис. 1.15 показано среднее время доступа как функция результативно­сти поиска. При высокой результативности среднее время доступа намного бли­же ко времени доступа к Ml, чем ко времени доступа к М2.

Производительность

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

(1.2.)

где

С_S — средняя стоимость одного бита двухуровневой памяти,

C₁ — средняя стоимость одного бита памяти верхнего уровня Ml,

С₂ – средняя стоимость одного бита памяти нижнего уровня М2,

S₁ — емкость Ml,

S₂ — емкость М2.

Желательно добиться соотношения C_S=C₂. При условии С₁>>С для этого требуется, чтобы выполнялось условие S₁=S₂. Получающаяся зависимость представлена на рис. 1.22.

Теперь рассмотрим время доступа. Для высокой производительности двух­уровневой памяти необходимо, чтобы T_S=T₁. Поскольку обычно T₁<<T₂, нуж­но, чтобы результативность поиска была близка к 1.

Таким образом, мы хотим, чтобы уровень Ml обладал малой емкостью (что позволило бы снизить стоимость), но был достаточно большим для того, чтобы повысить результативность поиска и, как следствие, производительность. Можно ли так подобрать размер Ml. чтобы в определенной степени он удовлетворял обоим требованиям? Этот вопрос можно разбить на несколько подвопросов.

• Какая результативность поиска удовлетворяет требованиям производитель­ности?

• Какая емкость Ml даст гарантию достижения требуемой результативности поиска?

• Будет ли эта емкость иметь приемлемую стоимость?

Чтобы ответить на эти вопросы, рассмотрим, величину T₁/T_S, которая называ­ется эффективностью доступа. Она является мерой того, насколько среднее время доступа T_S отличается от времени доступа T₁ к Ml. Из уравнения (1.1) находим

(1.3)

На рис. 1.23 представлен график зависимости T₁/T_S от результативности поиска Н при разных значениях параметра T₂/T₁. Обычно время доступа к кэшу в пять-десять раз меньше, чем время доступа к основной памяти (т.е. отношение T₂/T₁ лежит в пределах от 5 до 10), а время доступа к основной памяти приблизительно в 1000 раз меньше, чем время доступа к диску (T₂/T₁->1000). Таким образом, чтобы удовлетворить требованиям эффективности, величина результативности поиска должна находится в пределах от 0.8 до 0.9.

Теперь вопрос об относительной емкости памяти можно сформулировать более точно. Можно ли при условии S₁=S₂ добиться, чтобы результативность поиска достигала значения 0.8 или превышала его? Это зависит от нескольких факторов, в число которых входит вид используемого программного обеспечения и детали устройства двухуровневой памяти. Основное влия­ние, конечно, оказывает степень локализации. На рис. 1.24 показано, какое влияние оказывает локализация на результативность поиска. Очевидно, что если емкость уровня Ml равна емкости уровня М2, то результативность по­иска будет 1.0, поскольку все содержимое М2 находится в Ml. Теперь пред­положим, что нет никакой локализации, т.е. все обращения происходят в случайном порядке. В этом случае результативность поиска линейно зависит от относительного размера памяти. Например, если объем Ml равен половине объема М2, то в любой момент времени на уровне Ml находится ровно поло­вина всех данных уровня М2, и результативность поиска равна 0.5. Однако на практике проявляется эффект локализации обращений. На графике пока­зано влияние локализации средней и сильной степени.

Таким образом, сильная локализация позволяет достичь высокой результативности поиска даже при сравнительно небольших объемах памяти верхнего уровня. Например, многочисленные исследования подтверждают, что при сравнительно небольшом размере кэша результативность поиска превышает 0.75, причем этот показатель не зависит от размера основной памяти (см., например, [AGAR89], [PRZY88], [STRE83] и [SMIT82]). В то время как типичный размер основной памяти в наши дни составляет многие мегабайты, вполне достаточным является кэш, емкость которого лежит в пре­делах от 1 до 128 Кбайт. При рассмотрении виртуальной памяти и дискового кэша можно сослаться на другие исследования, подтверждающие справедливость такого же утверждения, а именно — благодаря локализации относительно малый размер Ml обеспечивает высокую результативность поиска.

Теперь можно перейти к последнему из перечисленных ранее вопросов: удовлетворяет ли относительный размер двух уровней памяти требованиям стоимости? Ответ очевиден: да. Если для повышения производительности достаточно добавить верхний уровень сравнительно небольшой емкости, то средняя стоимость обоих уровней в расчете на один бит будет лишь немного превосходить стоимость бита более дешевой памяти второго уровня.