Средства разработки приложений


Обзор методов оптимизации кода - часть 20


  1. Планирование команд
    1. Алгоритмы планирования

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

В ILP-компиляции в основном применяются различные варианты приоритетного (эвристического) списочного планирования (list scheduling). Процесс планирования состоит из трех шагов:

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

2. Вычисление приоритетов команд. Приоритеты определяют, в каком порядке будут планироваться готовые к исполнению команды на шаге 3. Способ вычисления приоритетов отражает эвристики планирования, от которых может существенно зависеть результат. Как правило, применяется эвристика планирования по критическому пути, когда приоритет команды определяется высотой соответствующего узла в графе зависимостей. Команды с совпадающими приоритетами упорядочивают либо произвольным образом, либо по некоторому вторичному признаку. В [31] приводятся результаты исследований нескольких эвристик глобального планирования в древовидных областях:

  1. по глубине команды в графе зависимостей;
  2. по числу выходов из области по всем путям в дереве управления, исходящим из данной команды (exit count). Согласно этой эвристике, наибольший приоритет получают команды, находящиеся в корне дерева.
  3. по частоте выполнения на основе данных профилирования (global weight). Приоритет отдается наиболее часто исполняемым командам, а при равенстве частот команды упорядочиваются по глубине.
  4. по взвешенной частоте выходов (weighted count).


    - Начало -  - Назад -  - Вперед -