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

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

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

К сожалению, нисходящее перемещение кода зачастую применяется к операциям записи, которые обладают побочным действием — перезаписыванием старого значения. Обойти эту неприятность можно, создав дубликаты базовых блоков на пути от згс к сйг и разместив операции только в новых копиях сЫ Другой подход состоит в использовании предикатных команд (конечно, если таковые доступны). Перемещенная операция защищена тем же предикатом, что и блок згс. Заметим, что предикатная команда может размещаться только в блоке, над которым доминирует вычисление предиката, поскольку иначе предикат будет недоступен. Если ~Ы не ностдоминирует над «гс Как и ранее, следует использовать компенсирующий код, чтобы перемещаемая операция выполнялась на всех путях, не проходящих через сЬк Такая трансформация аналогична устранению частичной избыточности, но копии размещаются ниже блока згс, в разрезе, который отделяет базовый блок згс от выхода.

869 !0.4. Глобальное планирование кода Резюме по восходящему и нисходящему перемещениям кода Из вышесказанного ясно, что существует область возможных глобальных перемешений кода, в которой оказываются различными стоимость, сложность реализации и повышение эффективности программы. На рис. 10.13 сведены различные варианты перемещения кода. Строки таблицы соответствуют следующим четырем случаям.

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

Такое перемещение кода выгодно в том случае, когда дополнительные операции могут быть выполнены бесплатно, т.е. с использованием только тех ресурсов, которые иначе простаивали бы, и когда выполняется путь, проходящий через исходный блок. 3. Если целевой блок не доминирует (постдоминнрует) над исходным базовым блоком при восходящем (нисходящем) перемещении, требуется компенсируюший код. Пути с компенсирующим кодом могут оказаться замедленнымн, поэтому важно, чтобы оптимизированные пути выполнялись чаще, чем неоптимизированные. 4. Последний случай объединяет недостатки второго и третьего случаев: требуется компенсирующий код и может потребоваться выполнение дополнительных операций. 870 Глава 1О. Параллелизм на уровне команд 10.4.4 Обновление зависимостей данных Как показано в приведенном ниже примере 10.10, перемещение кода может изменить отношения зависимости данных между операциями.

Таким образом, после каждого перемещения кода следует выполнять обновление зависимостей данных. Пример 10.10. В случае графа потока на рис. 10.14 в верхний блок может быть перенесено любое присваивание х, поскольку при таком преобразовании сохраняются все зависимости исходной программы. Однако после того, как одно из присваиваний будет перенесено вверх, второе переносить будет нельзя. Точнее говоря, переменная х на выходе из верхнего блока до перемешения не активна, но становится таковой после перемещения.

Если в некоторой точке программы переменная активна, то упреждаюшее определение этой переменной не может быть перемещено выше данной точки. а Рис. 10.14. Пример, иллюстрирующий изменение зависимости данных из-за пе- ремешения кода 10.4.5 Алгоритм глобального планирования В последнем разделе мы видели, что перемещение кода может привести к повышению эффективности некоторых из путей выполнения и снижению эффективности прочих. Хорошая же новость состоит в том, что не все команды равны— одни из них более равны, чем другие. Не секрет, что в действительности 90% времени работы программы тратится на выполнение ! 0% кода.

Таким образом, наша цель должна состоять в том, чтобы сделать часто выполнимые пути как можно более быстрыми, возможно, за счет того, что более редкие пути станут более медленными. Имеется множество методов, которые компилятор может использовать для оценки частоты выполнения. Достаточно разумно считать, что команды во внутренних циклах выполняются гораздо чаще, чем код внешних циклов, и что при ветвлении чаше выбираются пути, ведущие назад, чем вперед. Кроме того, крайне 871 10.4. Глобальное планирование кода редко должны отрабатываться ветвления, ведущие к выходу из программы или в подпрограммы обработки исключений.

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

1. Восходящее перемещение операций в блоки, эквивалентные с точки зрения управления. 2. Упреждающее восходящее перемещение операций по одной из ветвей в предшествующий доминирующий блок. Вспомним, что в разделе 9.7.! область определялась как подмножество графа потока управления, которое может быть достигнуто через один входной базовый блок. Любая процедура может быть представлена как иерархия областей. Полностью процедура состоит из области верхнего уровня со вложенными в нее подобластями, представляющими естественные циклы в функции.

Граф потока управления мы считаем приводимым. Алгоритм 10.11. Планирование на основе областей ВхОд: граф потока управления и описание машинных ресурсов. Выход: план Я, отображающий каждую команду на базовый блок и интервал времени. Метод: выполняем программу, приведенную на рис. !0.15. Терминология программы должна быть очевидна: СопГго!Е9иГг (В) — множество блоков, эквивалентных с точки зрения управления с базовым блоком В, а функция ВолплагесБисс, примененная к множеству базовых блоков, дает множество базовых блоков, являющихся преемниками как минимум одного блока множества, для которых все блоки множества являются доминирующими. Планирование кода в алгоритме 10.11 идет от наиболее глубоких внутренних областей к наружным. При планировании области каждая вложенная подобласть рассматривается как черный ящик; команды не могут перемещаться в подобласти или из них. Однако они могут перемещаться вокруг подобласти при условии удовлетворения ограничений зависимостей данных и управления.

Все ребра управления и зависимости, идущие назад к заголовку области, игнорируются, так что получающиеся в результате графы потоков управления и зави- 872 Глава 10. Параллелизм на уровне команд 1ог (каждая область В в топологическом порядке, так что внутренние области обрабатываются до внешних) ( Вычисление зависимостей данных; Гог (каждый базовый блок В области А в приоритетном топологическом порядке) ( СапйВ1осЬ = Сои!го!Ег1ши (В) О ВоттшейБисс (Сопгго!Еди!г (В) ); Сапй!тгз = готовые команды в Сапг181осЫ; Гог (1 = О, 1,..., пока не будут спланированы все команды из В) ( 1ог (каждая команда и из СапЛп.багз в приоритетном порядке) Н' (и не имеет конфликтов ресурсов в момент 1) ( Я(п) = (В,1); Обновление имеющихся ресурсов; Обновление зависимостей данных; Обновление Саид!тм; Рис.

!О.! 5. Алгоритм глобального планирования на основе областей симости данных ацикличны. Базовые блоки в каждой области посещаются в топо- логическом порядке. Такое упорядочение гарантирует, что базовый блок не будет планироваться до тех пор, пока не будут спланированы все команды, от которых он зависит. Команды, которые должны быть спланированы в базовом блоке В, выводятся изо всех блоков, эквивалентных с точки зрения управления блоку В (включая сам базовый блок В), а также из непосредственных преемников блока В, над которыми он доминирует.

Алгоритм планирования списка используется для создания плана для каждого базового блока. Этот алгоритм поддерживает список команд-кандидатов СапЮть, который содержит все команды в блоках-кандидатах, все предшественники которых уже спланированы. План создается такт за тактом. Для каждого такга в порядке приоритета проверяется каждая команда из списка Сапй!ть и планируется, если позволяют ресурсы.

Затем алгоритм 10.11 обновляет список Сапгйпзм и повторяет процесс до тех пор, пока не будут спланированы все команды из базового блока В. Приоритетный порядок команд в списке Садизм использует функцию приоритета, подобную рассмотренной в разделе 10.3, в которую внесено одно важное изменение. Командам из блоков, эквивалентных с точки зрения управления блоку В, назначается более высокий приоритет, чем командам из блоков-преемников.

873 10.4. Глобальное планирование кода Причина этого в том, что команды из блоков-преемников в базовом блоке В могут вычисляться только с упреждением. и Развертка циклов При планировании на основе областей граница итерации цикла является барьером для перемегцения кода. Операции из одной итерации не могут перекрываться операциями из другой. Один простой, но эффективный метод смягчения этой проблемы состоит в небольшой развертке цикла перед планированием кода.

Цикл Гог наподобие аког(1 = 0; 1 ( Ыр 1++) ( Я(1); ) можно переписать так, как показано на рис. 10.16, а. Аналогично цикл гереа( гереас Я; цпс11 С; может быть переписан так, как показано на рис. 10.16, б. Развертывание создает большее количество команд в теле цикла, позволяя алгоритму глобального планирования достигать большей степени параллелизма. Уплотнение окрестностей Алгоритм 10.11 поддерживает только два первых вида перемещения кода, описанных в разделе 10.4.1.

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

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