Статья: Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

Рис. 9. Конвейеризация цикла

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

Обзор методов конвейеризации циклов можно найти в работах [7], [12].

Разбивка циклов (loop distribution). В некоторых случаях может иметь смысл преобразование, обратное слиянию и называемое разбивкой циклов. Это целесообразно, например, если тело цикла слишком длинное, и имеющееся число регистров недостаточно для размещения всех используемых в теле цикла переменных. В этом случае часть промежуточных значений приходится временно выгружать в память, а перед использованием в вычислениях загружать на регистры (в англоязычной литературе этот процесс обозначают термином register spilling). Благодаря разбивке цикла можно избежать дефицита регистров и выталкивания значений в память.

В примере, показанном на рис. 10, вторая команда не может быть выполнена параллельно с первой в силу зависимости по данным. В результате разбивки создаются циклы с более короткими телами и меньшим числом зависимостей по данным.

for (i=0;i<100;i++){ for (i=0;i<100;i++)

b[i]=b[i-1]+c; ==> b[i]=b[i-1]+c;

a[i]=b[i]+2;} for (i=0;i<100;i++)

a[i]=b[i]+2;

Рис. 10. Разбивка циклов

Встраивание функций

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

Снятие зависимостей по данным

Алгоритмы планирования команд, используемые практически во всех компиляторах (см. разделы 7.1 и 8), работают с тремя видами зависимостей (или связей) по данным между командами (см., например, [58] или [45]). Здесь будут рассмотрены только зависимости по обращениям к регистрам; о зависимостях по обращениям к памяти см. разд. 7.6.

Пусть имеется некоторая последовательность команд c1, ..., cn, подлежащих планированию. Планировщик может изменять порядок выполнения команд, не нарушая их частичной упорядоченности, которая определяется перечисленными далее зависимостями по данным. (При глобальном планировании планировщик также должен учитывать связи по управлению, препятствующие перемещению команд через точки ветвления; подробнее об этом см. разделы 7.3, 7.4).

1. Связи типа "чтение после записи". Команда cj зависит от ci, если ci записывает значение в некоторый регистр r, а cj читает это значение. Будем обозначать это отношение как cicj.

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

2. Связи типа "запись после записи". Команда cj зависит от ci, если

обе команды записывают значения в некоторый регистр r

j > i

имеется хотя бы одна команда сk, которая читает значение r, записанное командой ci.

Будем обозначать это отношение как cicj. Выполнение команды cj должно быть запланировано позже чем ci, если имеет место cicj.

3. Связи типа "запись после чтения". Команда cj зависит от ci, если существует команда ck, такая что имеет место ckci и ckcj. Будем обозначать это отношение cicj. Смысл этой зависимости в том, что ci читает некоторый регистр r, записанный ранее командой ck, а cj (j > i) записывает в r другое значение. Если имеет место cicj, то cj может быть выполнена не раньше ci (т.е. одновременно или позднее ci).

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

Рис. 11. Зависимости по данным (a) до распределения регистров, (b) после распределения регистров. После распределения регистров появляются антизависимости WAR (R3=R1+R2,R1=R4-R5) по R1 и WAW(R3=R1+R2,R3=R0-R7) по R3

На рис. 11 представлены примеры зависимостей всех типов и показано, как образуются антизависимости.

Зависимости по данным препятствуют параллельному исполнению команд и их переупорядочению при планировании. В случае, показанном на рис. 11а), возможно параллельное выполнение команд (1,2,4) или (3,4). После распределения регистров (рис. 11б), антизависимости жестко определят порядок выполнения команд – 1), 2), 3), 4). Поэтому важно по возможности избавляться от них. Большинство из перечисленны