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

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

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

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

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

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

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

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

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

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

На рис. 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. Что такое пространственная локализация?