А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 112

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 112)

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

Уделяя внимание размещению объектов в памяти, диспетчер сможет эффективнее использовать доступную память и, следует надеяться, повысить скорость работы программы. ° Низкие никлас)ные расходы. Поскольку во многих программах выделение и освобождение памяти — весьма распространенные операции, очень важно, чтобы они были максимально эффективны и минимизировали накладные расходы — долю времени выполнения, затрачиваемого на операции выделения и освобождения памяти. Заметим, что стоимость выделения памяти доминирует при малых запросах; для больших запросов она ие столь 7.4. Управление кучей существенна, поскольку обычно амортизируется большим количеством вычислений. 7.4.2 Иерархия памяти компьютера Управление памятью и оптимизация должны выполняться с учетом информации о поведении памяти.

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

Большая разница времен доступа к памяти связана с фундаментальными технологическими ограничениями в области электроники. Можно создать небольшую и быструю память; можно — большую и медленную, но получить большую быструю память нереально. Сегодняшняя технология не позволяет получить гигабайтную память с наносекундным временем доступа, соответствуюшим скорости работы современных высокопроизводительных процессоров. Поэтому память практически всех современных компьютеров образует иерархию памяти. Иерархия памяти, как показано на рис.

7.16, состоит из ряда элементов памяти, в котором более быстрая небольшая память оказывается "ближе" к процессору, а большая и более медленная — дальше от него. Обычно у процессора имеется небольшое количество регистров, содержимое которых управляется программно. Также есть один или несколько уровней кэшей, обычно находяшихся вне статической памяти и имеющих размер от килобайтов до нескольких мегабайтов. Следующим уровнем иерархии памяти является физическая (основная) память, состоящая из сотен мегабайтов или гигабайтов динамической оперативной памяти (ВАМ). Физическая память "подпирается" виртуальной памятью, реализованной в виде гигабайтов дисковой памяти.

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

Все остальные уровни иерархии управляются автоматически. Это не только упрощает программирование, но и позволяет одной и той же программе эффективно работать на различных машинах с разными конфигурациями памяти. При каждом обрашении 558 Глава 7. Среды времени выполнения Типичный объем данных Типичное время доступа > 2 ГБейт 3-15 мс 256 МБайт-2 ГБвйт 100-150 но 126 КБайт-4 МБайт 40-60 нс 16-64 КБайт 5-10 нс 32 слова 1 но Рис.

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

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

Кэши управляются исключительно аппаратно, что позволяет обеспечить относи- 559 7.4. Управление кучей тельно быстрый доступ к оперативной памяти. Поскольку диски сравнительно медленны, виртуальная память управляется операционной системой при помощи аппаратной структуры, известной как буфер преобразования адреса 1!ганя!а!!оп 1оо)газ|де Ьийег).

Данные пересылаются блоками непрерывной памяти. Для амортизации стоимости доступа на более медленных уровнях доступа используются блоки большего размера. Между основной памятью и кэшем данные пересылаются блоками, известными под названием строки кэша (сасЬе 1!пел), обычно длиной 32-256 байт. Между виртуальной памятью (диском) и основной памятью данные передаются блоками, известными как страницы (радея), размер которых обычно составляет 4 — 64 Кбайт.

7.4.3 Локальность в программах Большинство программ демонстрирует высокую степень локальности (1оса1- йу), т.е. ббльшую часть времени они затрачивают на выполнение относительно небольших частей кода и обращаются только к небольшой части данных. Мы говорим, что программа обладает временной локальностью ([ет рога!!оса11!У), если обращение к ячейкам памяти означает, что, скорее всего, через небольшой период времени к ним вновь будет выполнено обращение. Программа обладает пространственной локальностью (араба! 1оса1пу), если, скорее всего, через небольшой промежуток времени будет выполнено обращение к ячейкам памяти, находящимся вблизи тех ячеек, к которым только что было выполнено обращение.

Традиционная мудрость гласит, что 90 времени программа затрачивает на выполнение 10% кода. Вот с чем это связано. ° Часто программы содержат команды, которые никогда не выполняются. Программы, собранные с компонентами и библиотеками, используют только малую часть предоставляемой ими функциональности. Кроме того, в процессе развития программ в них часто остается старый, больше не нужный и не выполняющийся код. ° При типичном запуске программы реально выполняется только малая часть кода, который может быть вызван. Например, команды обработки некорректного ввода и исключений хотя и критичны для корректности программы, на деле выполняются очень редко. ° Типичная программа больше всего времени затрачивает на выполнение внутренних циклов и рекурсию.

Локальность позволяет воспользоваться преимуществами иерархии памяти современного компьютера, показанной на рис. 7.16. Помещая чаще всего используемые команды и данные в быструю, хотя и меньшую, память и оставляя остальную 560 Глава 7. Среды времени выполнения Архитектуры кэшей Как узнать, находится ли строка кэша в кэшеу Проверка каждой отдельной линии в кэше может оказаться слишком дорогим удовольствием, так что распространенная практика заключается в ограничении размещения строки кэша в кэше.

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

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

Характеристики

Список файлов книги