Приложение а. Характеристики производительности двухуровневой памяти

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

Механизм кэширования основной памяти является составной частью компьютерной архитектуры. Он встроен в аппаратное обеспечение и обычно невидим операционной системе. В силу этого кэширование не рассматривает­ся в данной книге. Однако есть еще два примера использования двухуровне­вой памяти, в которых также используется локализация и которые, по крайней мере, частично, управляются операционной системой; виртуальная память и дисковый кэш (см. табл. 1.2). Эти темы являются предметом рас­смотрения глав 8, "Виртуальная память", и 11, "Управление вводом-выводом и дисковое планирование", соответственно. Данное приложение поможет чи­тателю познакомиться с некоторыми характеристиками производительности двухуровневой памяти, которые являются общими для всех трех подходов.

Таблица 1.2. Характеристики двухуровневой памяти

Кэш основной памяти		Виртуальная память (страничная организация)	Дисковый кэш
Типичное соотношение времени доступа	5:1	1000:1	1000:1
Система управле­ния памятью	Специальное встро­енное аппаратное обеспечение	Сочетание аппарат­ного и программного обеспечения	Системное про­граммное обеспе­чение
Типичный размер блока	От 4 до 128 байт	От 64 до 4096 байт	От 64 до 4096 байт
Доступ процессора Ко второму уровню	Прямой доступ	Косвенный доступ	Косвенный доступ

Локализация

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

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

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

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

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

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

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

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

Исследование Язык	[HUCK83] Pascal	(KNUT71] FORTRAN	[РАTT82] Pascal	С	[TANE78] SAL
Изучаемый материал	Научное ПО	Студенческие работы	Системное ПО	Системное ПО	Системное ПО
Присвоение	74	67	45	38	42
Цикл	4	3	5	а	4
Вызов	1	3	15	12	12
IF	20	11	29	43	36
GOTO	2	9	-	3	-
Другие	-	7	6	1	6

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

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

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