close

Вход

Забыли?

вход по аккаунту

?

8620.Улучшенный алгоритм оптимизации порядка выполнения команд

код для вставкиСкачать
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№30
КРАТКИЕ СООБЩЕНИЯ
УДК 681.3.07
П.М.Довгалюк
УЛУЧШЕННЫЙ АЛГОРИТМ ОПТИМИЗАЦИИ
ПОРЯДКА ВЫПОЛНЕНИЯ КОМАНД
Методы оптимизаций переходов между базовыми блоками
Алгоритмы конвейерной оптимизации занимаются изменением порядка выполнения
инструкций для того, чтобы ускорить выполнение программы. При этом изменение порядка
инструкций не должно изменять результат выполнения программы. Для достижения этой
цели компилятор может выполнять следующие действия:
— переупорядочивание инструкций в базовых блоках;
— переупорядочивание инструкций, входящих в цикл; развертывание цикла;
— оптимизация инструкций перехода.
Измерение порядка инструкций может давать полезный эффект в тех случаях, когда
между выполнением некоторых инструкций должно пройти определенное время, которое
можно заполнить полезными действиями.
В некоторых RISC-процессорах между выборкой инструкции цикла и непосредственным выполнением перехода (изменением значения регистра Program Counter) происходит выборка нескольких команд, следующих за инструкцией перехода, которые также попадают в конвейер и выполняются как обычно (например, MIPS, PA-RISC и SPARC). Самый простой способ избежать конфликтов в этом случае — включение после инструкции
перехода нескольких «пустых» инструкций (NOP — No OPeration). Существует несколько
способов избежать непроизводительных простоев: например, помещение инструкции перехода не в самый конец базового блока таким образом, что последние полезные инструкции
будут помещены в конвейер после инструкции перехода; или размещение после инструкции
перехода команд из следующего (куда производится переход) базового блока и коррекция
адреса, по которому осуществляется переход.
Однако, размещая после инструкции перехода некоторый полезный код, необходимо
контролировать возможные его конфликты с тем кодом, который выполняется до перехода
и после него (в следующем базовом блоке). Традиционный подход заключается в поиске
таких инструкций среди крайних (в частично упорядоченном множестве инструкций), т.е.
таких, которые должны выполняться первыми (не имеют зависимостей в текущем базовом
блоке) или последними (от результатов которых не зависят никакие инструкции данного
базового блока). Такой подход может давать неоптимальный результат, так как порядок
инструкций в базовом блоке выбирается независимо от перемещенных инструкций.
Кроме алгоритмов локального составления расписаний (list scheduling) существуют
также глобальные алгоритмы, которые действуют в пределах нескольких базовых блоков
(extended basic blocks scheduling), наиболее вероятного пути выполнения программы (trace
scheduling), и некоторые другие алгоритмы, также рассматривающие различные объединения базовых блоков. Таким алгоритмам легче учесть взаимодействие инструкций из разных
базовых блоков, но они имеют следующие особенности.
1. Существенное изменение структуры и объема кода: повторение некоторых инструкций с целью составления более оптимального порядка их выполнения. Чем больше рассматриваемый участок кода, тем больше может увеличиться в объеме результирующая программа.
117
2005
ВЕСТНИК НОВГОРОДСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
№30
2. Код разбивается на независимые участки, поэтому проблема их эффективного
взаимодействия только уменьшает свою значимость, но не исчезает совсем.
3. Очень большое время выполнения алгоритма. Так же, как и у других алгоритмов оптимизации, время работы данной группы алгоритмов зависит от квадрата количества инструкций. Но число рассматриваемых команд существенно больше, чем для алгоритма, работающего в пределах одного базового блока, что и обуславливает большое время выполнения.
Ниже предлагается модификация алгоритма перестановки команд в пределах базового блока, позволяющая учитывать связи между инструкциями из разных базовых блоков и,
таким образом, уменьшать задержки при выполнении команд перехода.
Описание предлагаемого метода
Метод устранения непроизводительных задержек, описанный в [лит.], работает следующим образом: осуществляется оптимизация порядка выполнения команд в пределах
базового блока (basic block scheduling), затем выбираются несколько инструкций, которые
подходят для заполнения задержки команды перехода. При этом может измениться уже
сгенерированное расписание выполнения инструкций, так как во втором шаге могут быть
перемещены инструкции из середины расписания. Поэтому предлагаемые изменения данного алгоритма касаются первого его шага. За основу алгоритма выполнения этого действия
взят известный (см. [лит.]) алгоритм переупорядочивания команд в базовых блоках, который действует следующим образом:
находит граф зависимостей между командами в пределах базового блока,
вычисляет приоритеты инструкций,
создает пустое расписание,
перемещает в расписание по одной команде из оставшегося множества команд в базовом блоке, выбирая каждый раз команду с максимальным приоритетом.
Для того, чтобы достичь поставленной цели, при составлении исходного расписания
учитываются существующие зависимости между командами из текущего базового блока и
командами из базового блока, в который может перейти управление. После составления
этого расписания команды, которые могут быть использованы в качестве заполнения задержки, будут расположены в самом конце расписания (или их не будет вообще).
Чтобы алгоритм составления расписания команд в базовом блоке упорядочивал инструкции именно таким образом, необходимо ввести критерий, который позволял бы при
выборе очередной инструкции из списка кандидатов на помещение в расписание учитывать
связи между смежными базовыми блоками. В качестве дополнительной характеристики
команды предлагается использовать период времени, который должен пройти с момента
начала выполнения инструкции до того момента, как сможет начать выполнение хотя бы
одна из команд, зависящих от данной. При осуществлении выбора из двух инструкций, при
прочих равных условиях, будет выбрана та, которая имеет большее значение этого параметра. Следовательно, в конце расписания окажутся команды, или не имеющие зависимостей вообще, или те, у которых минимален период времени до начала выполнения зависящих от них команд. А именно эти команды могут наиболее эффективно заполнить паузу от
начала выполнения команды перехода до того момента, как изменится регистр PC.
Выводы
Применение улучшенного алгоритма оптимизации порядка выполнения команд в базовых блоках позволяет уменьшить количество непроизводительных простоев конвейера
как при выполнении команд условного и безусловного перехода, так и при выполнении
двух последовательных базовых блоков.
Особенность данного алгоритма по сравнению с оптимизацией различных объединений базовых блоков состоит в том, что он не увеличивает объем кода и требует меньше
времени для выполнения.
Muchnick S. Advanced compiler design and implementation. San Francisco: Academic Press, Morgan Kaufman
Publishers, 1997. 856 p.
118
Документ
Категория
Без категории
Просмотров
1
Размер файла
171 Кб
Теги
алгоритм, оптимизация, улучшенными, выполнения, команды, порядке, 8620
1/--страниц
Пожаловаться на содержимое документа