Локальная оптимизация.

Большинство оптимизирующих компиляторов применяют т.н. “локальную” оптимизацию. При таком подходе, сначала генерируется достаточно простой (с точки зрения генерации) машинный код, затем по коду перемещается некое “окно” которое рассматривает лишь локальную окрестность текущей команды, и к коду внутри этого “окна” применяются локальные трансформации.

Примеры локальных оптимизаций:

• Устранение “лишних” инструкций
  • В частности, лишних загрузок и сохранений из/в оперативную память
  • Недостижимого кода (скажем, используемого для отладки)
• Оптимизация потока управления
  • Устранение цепочек переходов (т.е. устранение лишних безусловных переходов)
• Алгебраические упрощения
• Использование машинных идиом

Параллелизм уровня команд. Конвейеризация

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

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

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

1. Чтение команды из памяти
2. Декодирование команды
3. Исполнение команды
4. Обращение к памяти
5. Сохранение результата

Эти действия выполняются, как правило, различными исполнительными блоками внутри процессора, и поэтому могут, в целом, работать одновременно. Таким образом, в тот момент, когда для, скажем i-той команды всё ещё выполняется действие 5, для i+1-й может выполняться действие 4, для i+2-й действие 3 и т.д.

Определённую сложность представляют собой команды ветвления, поскольку заранее неизвестно, по какой ветви пойдёт дальнейшее выполнение кода. Это, соответственно приводит к “заиканию” конвейера, когда он опустошается, и затем вновь заполняется после ветвления. Многие современные процессоры использовали т.н. модель спекулятивного исполнения, когда процессор пытался “предугадать” по какой ветви пойдёт исполнение кода, и опустошал конвейер только если догадка оказалась неверной. Однако некоторая неаккуратность в реализации в итоге привела к недавно нашумевшим уязвимостям Meltdown и Spectre.

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

Ещё один источник ускорения – использование векторных команд, т.е. команд, производящих операцию сразу над несколькими адресами. Эта оптимизация может быть реализована как в компиляторе (тогда используются специальные инструкции, называемые в общем VLIW – very long instruction word), так и непосредственно в железе, тогда такой процессор называется суперскалярным.

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

Оптимизация локальности

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

• Временная локальность означает использование некоторых данных несколько раз за короткий промежуток времени
• Пространственная локальность означает использование в течение короткого промежутка времени некоторых находящихся рядом друг с другом данных

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

Например:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
  Z[i] = Z[i] * Z[i];
}

тот же код можно написать иначе:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
}
for(i = 0; i < n; ++i) {
  Z[i] = Z[i] * Z[i];
}

Технически, оба варианта подразумевают одинаковое количество операций присваивания, однако первый вариант будет значительно быстрее за счёт лучшей локальности данных. К тому же, в первом варианте результаты вычисления X[i] - Y[i] могут вообще не быть записаны в физическую память (поскольку далее не используются), в то время как во втором варианте, если массив Z достаточно велик, чтобы не умещаться в кэш процессора, X[i] - Y[i] должны быть записаны в память.

Другой пример, обнуление “двумерного” массива:

for (j = 0; j < n; ++j)
  for (i = 0; i < m; ++i)
    Z[i+m*j] = 0;

против

for (i = 0; i < m; ++i)
  for (j = 0; j < n; ++j)
    Z[i+m*j] = 0;

И тот и другой код делают одно и то же, но в разном порядке. Первый вариант проходит по массиву Z линейно из начала в конец, в то время как второй вариант “прыгает” по массиву, что может весьма ощутимо негативно сказаться на производительности в силу худшей локальности данных.

Задача оптимизации локальности значительно усложняется, если в рамках рассмотрения к тому же оказывается и параллелизм. В частности, если предполагается параллельное исполнение кода на нескольких процессорах/ядрах, то разные данные могут быть “локальными” для разных процессоров.