Локализация

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

Принцип локализации подтверждается на практике. Рассмотрим следую­щую цепочку рассуждений.

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

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

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

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

Приведенные рассуждения подтверждаются многими исследованиями. Для проверки утверждения 1 проводился разносторонний анализ поведения про­грамм, составленных на языках высокого уровня. Результаты измерений часто­ты появления различных команд при выполнении программы, проведенные раз­ными исследователями, представлены в табл. 1.3. Одно из самых ранних исследований поведения языка программирования проводилось Кнутом[KNUT71], рассматривавшим различные программы на языке FORTRAN, написанные студентами при выполнении практических заданий. Таненбаум [TANE78] опубликовал результаты измерений, проведенные более чем на 300 процедурах, которые использовались при разработке операционных систем и были написаны на языке, поддерживающем структурное программирование. Паттерсон и Секвин [РАТТ82] провели анализ ряда измерений, выполненных над компиляторами, текстовыми редакторами, системами автоматизированного проектирования, программами сортировки данных и сравнения содержимого файлов (языки программирования С и Pascal). Хак [HUCK83] проанализировал четыре программы, являющиеся типичными примерами программ для проведения научных вычис­лений. Среди них были, в частности, программы для выполнения быстрого Фу­рье-преобразования и для решения системы дифференциальных уравнений. По­лученные результаты хорошо согласуются с утверждением, что ветвления и ко­мандывызовов представляют собой лишь небольшую часть всех команд, выполняющихся во время работы программы. Таким образом, проведенные ис­следования подтверждают справедливость приведенного выше утверждения 1.

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

Что касается утверждения 2, то его справедливость подтверждается Иссле­дованиями, результаты которых изложены в [РАТТ85]. Это проиллюстрировано на рис. 1.20, где показано поведение программы в разрезе используемых в ней вызовов процедур и возврата из них. Каждый вызов представлен отрезком ли­нии, идущим на одно деление вниз, а каждый возврат — отрезком, идущим на одно деление вверх. Весь график заключен в коридор шириной 5 делений. Этот коридор является подвижным, но сдвигается лишь в результате 6 последова­тельных команд вызова или возврата. Из графика видно, что программа во вре­мя своей работы может оставаться в стационарном коридоре на протяжении дос­таточно длительного периода времени. Изучение программ, написанных на С или Pascal, показало, что при расширении коридора до 8 делений он сдвигается меньше, чем при 1% вызовов или возвратов [TAMI83].

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

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