Усовершенствования базового алгоритма - часть 3

Это отсекает переименования, которые никогда не дадут выигрыша. Другим улучшением является запрет на применение преобразования переименования регистров (и спекулятивного выполнения команд по управлению) в тех случаях, когда результирующая инструкция будет запланирована на последнем такте цикла, и можно показать, что такое преобразование будет невыгодным. Далее, перепланирование конвейеризованного кода для достижения более плотного расписания в тех местах кода, из которых были перемещены инструкции, позволило нам улучшить ряд тестов SPEC на 0.5-1%. Этот дополнительный проход особенно полезен для маленьких циклов, в которых создаваемые конвейеризацией «дырки» имеют значение.

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

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

По результатам тестирования усовершенствованного алгоритма планирования на платформе Intel Itanium было получено среднее ускорение в 3-4% на пакете тестов SPEC CPU FP 2000 (для разного набора базовых опций получено разное ускорение), а на отдельных тестах – до 10%. Часть результатов представлена в таблице 1. Мелким шрифтом выделен тест, который работает некорректно с текущей реализацией поддержки условного выполнения.

	База	Сел	Сел +Усл	Сел +Зав	Сел+Зав +Усл
168.wupwise	553	-2,35%	-2,35%	1,27%	1,45%
171.swim	754	1,46%	4,91%	0,93%	5,04%
172.mgrid	574	3,66%	3,83%	7,49%	8,01%
173.applu	531	3,95%	3,95%	3,77%	4,33%
177.mesa	774	1,42%	1,42%	2,58%	1,42%
178.galgel	856	2,45%	2,22%	3,50%	3,50%
179.art	2025	1,14%	6,17%	1,23%	6,22%
183.equake	509	8,64%	8,64%	6,88%	7,07%
187.facerec	959	-0,31%	0,52%	0,00%	0,42%
188.ammp	739	3,79%	4,19%	3,79%	4,19%
189.lucas	898	0,33%	-0,33%	-0,11%	0,00%
191.fma3d	549	-1,28%	-1,28%	0,55%	0,00%
200.sixtrack	325	0,00%	1,23%	8,92%	8,92%
301.apsi	538	1,30%	2,04%	4,65%	5,02%
SPEC FP Geo Mean	687,7963	1,70%	2,47%	3,21%	3,93%

Таблица 1. Результаты тестов SPEC FP для планировщика команд.

Исходные коды реализованного алгоритма планирования команд и конвейеризации циклов был включен в специальную ветвь компилятора GCC, доступную с официального сайта разработчиков. Кроме того, по результатам настройки алгоритм планирования был включен в основную ветвь разработки компилятора GCC, как планировщик по умолчанию для платформы Itanium, и будет доступен в следующем релизе компилятора версии 4.4.0.

Мы продолжаем работы над улучшением алгоритма, в первую очередь – над добавлением поддержки полного графа зависимостей по данным, что позволит как ускорить сам алгоритм, так и реализовать более эффективные эвристики для этапа выбора наилучшей команды. Также будут вестись работы над настройкой реализованного алгоритма на другие архитектуры, в частности, IBM Power6.

Содержание Назад Вперед