- •Глава 1 Обзор компьютерных систем
- •1.1. Основные элементы
- •1.2. Регистры процессора
- •Управляющие регистры и регистры состояния
- •1.3. Исполнение команд
- •Выборка и исполнение команды
- •Функции ввода-вывода
- •Множественные прерывания
- •Многозадачность
- •1.5. Иерархия запоминающих устройств
- •1.6. Кэш
- •Обоснование
- •Принципы работы кэша
- •Внутреннее устройство кэша
- •1.7. Технологии ввода-вывода
- •Программируемый ввод-вывод
- •Ввод-вывод с использованием прерываний
- •Прямой доступ к памяти
- •1.8. Рекомендуемая литература
- •1.9. Задачи
- •Приложение а. Характеристики производительности двухуровневой памяти
- •Функционирование двухуровневой памяти
- •Производительность
- •Приложение б. Управление процедурами
- •Реализация стека
- •Вызов процедуры и возврат из нее
- •Реентерабельные процедуры
Функционирование двухуровневой памяти
Принцип локализации может быть использован для разработки схемы двухуровневой памяти. Память верхнего уровня (Ml) имеет меньшую емкость, она быстрее, и каждый ее бит дороже по сравнению с памятью нижнего уровня (М2). Ml используется для временного хранения определенной части содержимого более емкого уровня М2. При каждом обращении к памяти сначала делается попытка найти нужные данные в Ml. Если она завершается успехом, происходит быстрый доступ. В противном случае, из М2 в Ml копируется нужный блок ячеек памяти, а затем снова осуществляется доступ к Ml. В соответствии с принципами локализации к ячейкам памяти вновь перенесенного блока произойдет еще ряд обращений, что приведет к общему ускорению работы программы.
Чтобы выразить среднее время доступа, нужно учитывать не только скорость работы обоих уровней памяти, но и вероятность обнаружения требуемых данных в Ml. В результате получим:
(1.1.)
где
TS — среднее (системное) время доступа,
T1 — время доступа к Ml (например, кэшу, дисковому кэшу),
T2 — время доступа к М2 (например, основной памяти, диску),
Н — результативность поиска (доля ссылок на данные в Ml).
На рис. 1.15 показано среднее время доступа как функция результативности поиска. При высокой результативности среднее время доступа намного ближе ко времени доступа к Ml, чем ко времени доступа к М2.
Производительность
Рассмотрим некоторые параметры, характеризующие механизм двухуровневой Памяти. Сначала рассмотрим стоимость, которая выражается следующим образом:
(1.2.)
где
СS — средняя стоимость одного бита двухуровневой памяти,
C1 — средняя стоимость одного бита памяти верхнего уровня Ml,
С2 – средняя стоимость одного бита памяти нижнего уровня М2,
S1 — емкость Ml,
S2 — емкость М2.
Желательно добиться соотношения CS=C2. При условии С1>>С для этого требуется, чтобы выполнялось условие S1=S2. Получающаяся зависимость представлена на рис. 1.22.
Теперь рассмотрим время доступа. Для высокой производительности двухуровневой памяти необходимо, чтобы TS=T1. Поскольку обычно T1<<T2, нужно, чтобы результативность поиска была близка к 1.
Таким образом, мы хотим, чтобы уровень Ml обладал малой емкостью (что позволило бы снизить стоимость), но был достаточно большим для того, чтобы повысить результативность поиска и, как следствие, производительность. Можно ли так подобрать размер Ml. чтобы в определенной степени он удовлетворял обоим требованиям? Этот вопрос можно разбить на несколько подвопросов.
Какая результативность поиска удовлетворяет требованиям производительности?
Какая емкость Ml даст гарантию достижения требуемой результативности поиска?
Будет ли эта емкость иметь приемлемую стоимость?
Чтобы ответить на эти вопросы, рассмотрим, величину T1/TS, которая называется эффективностью доступа. Она является мерой того, насколько среднее время доступа TS отличается от времени доступа T1 к Ml. Из уравнения (1.1) находим
(1.3)
На рис. 1.23 представлен график зависимости T1/TS от результативности поиска Н при разных значениях параметра T2/T1. Обычно время доступа к кэшу в пять-десять раз меньше, чем время доступа к основной памяти (т.е. отношение T2/T1 лежит в пределах от 5 до 10), а время доступа к основной памяти приблизительно в 1000 раз меньше, чем время доступа к диску (T2/T1->1000). Таким образом, чтобы удовлетворить требованиям эффективности, величина результативности поиска должна находится в пределах от 0.8 до 0.9.
Теперь вопрос об относительной емкости памяти можно сформулировать более точно. Можно ли при условии S1=S2 добиться, чтобы результативность поиска достигала значения 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 обеспечивает высокую результативность поиска.
Теперь можно перейти к последнему из перечисленных ранее вопросов: удовлетворяет ли относительный размер двух уровней памяти требованиям стоимости? Ответ очевиден: да. Если для повышения производительности достаточно добавить верхний уровень сравнительно небольшой емкости, то средняя стоимость обоих уровней в расчете на один бит будет лишь немного превосходить стоимость бита более дешевой памяти второго уровня.