Иерархия памяти в компьютере

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

Разрешить эту дилемму можно, использовав в подсистеме памяти разные технология хранения информации, реализовав некую иерархию подсистемы памяти. Типичная иерархия подсистемы памяти схематически представлена на рис. 5.1.

Рис. 5.1. Иерархия подсистемы памяти компьютера

Принцип иерархии подразумевает выполнение следующих условий:

количество уровней иерархии может быть произвольным;

каждый уровень иерархии выполняет строго определенный набор функций;

обращение извне всегда происходит к верхнему уровню иерархии;

если i-й уровень иерархии может выполнить полученный запрос, то он его выполняет и передает результат источнику запроса – (i-1)-му уровню иерархии;

если i-й уровень иерархии не может выполнить полученный запрос, то он формирует запрос к (i+1)-му уровню иерархии;

по мере перехода от верхних уровней иерархии подсистемы памяти к нижним уровням:

снижается относительная стоимость хранения информации;

повышается емкость;

увеличиваетсявремя доступа;

снижается частота обращений с предыдущего уровня иерархии;

на некотором уровне иерархии обеспечивается энергонезависимость.

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

Ключевыми вопросами, решение которых обеспечивает успех иерархического проекта подсистемы памяти, являются:

организация потоков информации в компьютере, обеспечивающая по мере переходе от устройств памяти верхних уровней иерархии к устройствам памяти нижних уровней снижение интенсивности обращений;

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

Предположим, что процессор в системе может обращаться к памяти двух уровней. Память 1-го уровня содержит N слов и имеет время доступа 1 нс, а память 2-го уровня — 1000 N слов и время доступа 10 нс. Предположим, что если нужное слово находится в памяти 1-го уровня, то процессор извлекает его непосредственно, а если в памяти 2-го уровня, то затребованное слово сначала записывается в память 1-го уровня, а уже оттуда его извлекает процессор. Для простоты анализа не будем учитывать время, необходимое процессору для того, чтобы выяснить, где именно находится искомое слово, — в памяти 1-го или 2-го уровня.

Пусть параметр Н характеризует долю запросов к памяти первого уровня во всем потоке запросов, параметр Т₁ — время доступа к памяти первого уровня, а Т₂ — время доступа к памяти второго уровня. Нет ничего неожиданного в том, что чем выше значение Н, т.е. чем большая часть всех обращений процессора за данными приходится в самый быстрый уровень, тем меньше среднее время обращения к иерархической подсистеме памяти, и тем ближе оно к значению Т₁.

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

Предположим, что 95% всех обращений приходится в память первого уровня (т.е., H=0.95). Тогда среднее время извлечения одного слова из иерархической подсистемы памяти будет равно:

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

Среди существующих на сегодняшний день технологий памяти, не так уж сложно подобрать ряд, обладающий следующими свойствами:

необходимое быстродействие памяти верхнего уровня;

снижение относительной стоимости хранения информации;

повышение емкости;

увеличениевремени доступа;

на некотором уровне иерархии обеспечивается энергонезависимость;

реализация требования о вложенности.

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

Выводы

1. Если быстродействие процессора и быстродействие энергонезависимой полупроводниковой памяти близки, то подсистема оперативной памяти может быть реализована с одним уровнем иерархии.

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

3. Количество и параметры памятей уровней иерархии зависят от области применения компьютера.

4. В высокопроизводительных современных компьютерах существует до 6 уровней иерархии подсистемы памяти.

5. Количество уровней иерархии может быть произвольным.

6. Каждый уровень иерархии выполняет строго определенный набор функций.

7. Обращение к иерархической подсистеме памяти извне всегда происходит к верхнему уровню иерархии.

8. Если i-й уровень иерархии может выполнить полученный запрос, то он его выполняет и передает результат источнику запроса – (i-1)-му уровню иерархии.

9. Если i-й уровень иерархии не может выполнить полученный запрос, то он формирует запрос к (i+1)-му уровню иерархии.

10. По мере перехода от верхних уровней иерархии подсистемы памяти к нижним уровням:

снижается относительная стоимость хранения информации;

повышается емкость;

увеличиваетсявремя доступа;

снижается частота обращений с предыдущего уровня иерархии;

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

на некотором уровне иерархии обеспечивается энергонезависимость.

Локальность ссылок

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

Интуитивно предположение о локализации ссылок кажется вполне резон­ным. Рассмотрим следующие доводы в пользу этого предположения.

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

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

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

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

Эти интуитивные соображения были подтверждены множеством исследова­ний. В ряде работ изучался характер типичных приложений разного назначения, разработанных с применением языков программирования высокого уровня. Некоторые результаты этих исследований приведены в таблице 5.1. В ней представлена относительная частота использования операторов разного типа в программах различного назначения.

Как видно из приведенной таблицы, результаты исследований программ разного назначе­ния дали достаточно близкие результаты — из них следует, что команды перехода и вызова процедур составляют весьма незначительную часть всех выполняемых во время работы программы команд. Таким образом, скрупулезные исследования подтвердили первое из интуитивных предположений.

Таблица 5.1. Относительная частота выполнения операторов разного типа в программах на языках высокого уровня

	Динамическая частота появления	Взвешенная оценка количества машинных команд	Взвешенная оценка количества обращений в память
	Pascal	C	Pascal	C	Pascal	C
Присваивание (ASSING)
Возврат на начало цикла (LOOP)
Вызов процедур (CALL)
Условный переход (IF)
Безусловный переход (GO TO)	-			-	-	-
Другие

На рис. 5.1 представлен график, показывающий харак­тер работы с процедурами в процессе выполнения типовой программы.

Рис. 5.1. Характер обращения к процедурам в процессе выполнения программы

По оси ординат графика отсчитывается текущая глубина вложенности выполняемой процедуры, а по оси абсцисс — время в относительных единицах (циклах выполнения команд "вызов/возврат"). Каждый вызов процедуры представ­лен на графике наклонной линией, идущей вниз-вправо (погружающей програм­му "в глубину"), а команда возврата — линией вверх-вправо (поднимающей про­грамму "на поверхность"). На графике выделены прямоугольниками участки, в которых относительная глубина вложенности не превышает 5. Такой прямо­угольник (окно заданной вложенности) смещается только в том случае, когда глубина вложенности с момента, зафиксированного его левой кромкой, превысит 5. Как видно на графике, программа остается в указанном диапазоне вложенности достаточно продолжительное время, а это означает, что все это время ядро процессора обращается только к командам из пяти текущих вложенных процедур. Исследование ряда программ, написанных на языках высокого уровня, показало, что только в 1% всех команд вызова процедур глубина вложенно­сти превосходит значение 8.

Свойство локализации ссылок подтверждается и более поздними исследова­ниями приложений, характерных для настоящего времени. Например, на рис. 5.2 показаны результаты статистического исследования доступа к страни­цам отдельного Web-сервера.

Рис. 5.2. Локализация ссылок на Web-страницы

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

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

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

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

Этот же принцип можно применить и в системе, имеющей не два, а три или больше запоминающих устройств разных уровней иерархии.

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

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

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

Запоминающие устройства, выполняющие в компьютере роль памяти первых уровней иерархии, как правило, по своей конструкции являются статическими полупроводниковыми энергозависимыми устройствами. Но каждое из них обычно изготавливается по технологии, которая обеспечивает оптимальное соотношение между емкостью, скоростью и стоимостью для памяти данного уровня. Для длительного хранения информации используются внешние устройства памяти большой емкости (по отношению к таким устройствам очень часто используется термин массовая память). Очень часто это жесткие магнитные диски или твердотельные устройства, которые дополняются устройствами со съемными носителями — магнитными, оптическими и магнитооптическими дисками и магнитной лентой. Во внешних запоминающих устройствах хранятся файлы выполняемых программ и обрабатываемых данных, и, как правило, программист обращается к этой информации в терминах файлов или отдельных записей, а не в терминах отдельных байтов или слов.

Иерархические уровни могут быть организованы не только посредством включения в состав технических средств компьютера тех или иных устройств, но и программно. Часть оперативной памяти может быть использована операционной системой в качестве буфера при обмене данными между полупроводниковой оперативной и внешней дисковой памятью. Такая методика, для которой был изобретен специальный термин "дисковый кэш", способствует некоторому повышению производительности системы по двум причинам:

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

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

Контрольные вопросы

1. Какие функции подсистемы памяти в компьютере?

2. Перечислите требования к подсистеме памяти?

3. Как соотносятся между собой основные требования к подсистеме памяти?

4. Что такое энергонезависимость памяти?

5. Назовите основные особенности статической полупроводниковой памяти.

6. Назовите основные особенности динамической полупроводниковой памяти.

7. Назовите основные особенности магнитной памяти.

8. Почему нельзя реализовать в быстродействующем универсальном компьютере подсистему памяти при использовании одной технологии?

9. Каковы принципы организации иерархической подсистемы памяти?

10. Может ли подсистема оперативной памяти иметь один уровень иерархии?

11. Что такое локализация ссылок?

12. Что такое временная локализация?

13. Что такое пространственная локализация?