Введение в технику оптимизации циклов

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

Время исполнения кода в циклах зависит от организации памяти, архитектуры процессора, в том числе, поддерживаемого набора инструкций, конвейеров, кэшей и опыта программиста.
Рассмотрим некоторые методы оптимизаций циклов: развертка циклов (loop unrolling), объединение циклов (loop fusion), разрезание циклов (loop distribution), выравнивание циклов (loop alignment), перестановка циклов (loop interchange), разделение на блоки (loop blocking).
Перед применением какой-либо оптимизации сделайте самое простое: вынесите из цикла все переменные, которые в нем не изменяются.

Какие причины могут привести к уменьшению скорости работы программы в циклах?

1. Итерации цикла зависимы и не могут исполняться параллельно.
2. Тело цикла большое и требуется слишком много регистров.
3. Тело цикла или количество итераций мало и выгоднее совсем отказаться от использования цикла.
4. Цикл содержит вызовы функций и процедур из сторонних библиотек.
5. Цикл интенсивно использует какое-то одно исполняющее устройство процессора.
6. В цикле имеются условные переходы.

Развертка циклов

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

До	После	После №2
for (int i = 0; i < iN; i++){  res *= a[i]; }	for (int i = 0; i < iN; i+=3){  res *= a[i];  res *= a[i+1];  res *= a[i+2]; }	for (int i = 0; i < iN; i+=3){  res1 *= a[i];  res2 *= a[i+1];  res3 *= a[i+2]; } res = res1 * res2 * res3;

В gcc можно применить следующие ключи: -funroll-all-loops -funroll-loops.

Объединение циклов

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

До	После
for(int i = 0; i < iN; i++){  a[i] = b[i] - 5; } for(int i = 0; i < iN-1; i++){  d[i] = e[i] * 3; }	for(int i = 0; i < iN-1; i++){  a[i] = b[i] - 5;  d[i] = e[i] * 3; } a[iN-1] = b[iN-1] - 5;

Разрезание циклов

Данная оптимизация применяется, когда тело цикла большое и переменным не хватает регистров. Поэтому данные сначала вытесняются в кэш, а если совсем все плохо, то и в оперативную память. А доступ к оперативной памяти занимает ~300 тактов процессора, а доступ к L2 всего ~10. Доступ к памяти с большим шагом еще больше замедляет программу. Оптимально «ходить» по памяти с шагом 2ⁿ, где n — достаточно маленькое число (<7).

До	После
for (int j = 0; j < jN; j++){ for (int k = 0; k < kN; k++){ for (int m = 0; m < mN; m++){  i = j * k + m;  a[i] = b[i] * c[i] + f[i]/e[i]+ x[i] - y[i] +   z[i]/r[i] + d[i] * x[i]; } } }	for (int j = 0; j < jN; j++){ for (int k = 0; k < kN; k++){  double tmp;  for (int m = 0; m < mN; m++){   i = j * k + m;   tmp = b[i] * c[i] + f[i]/e[i];   a[i] = tmp - y[i] + z[i]/r[i] +   (d[i] + 1) * x[i];  } } }

Перестановка циклов

Во вложенных циклах важен порядок вложения. Поэтому необходимо помнить как хранятся массивы в памяти. Классический пример: c/c++ хранят матрицы построчно, а fortran — по столбцам.

До	После
for(int i = 0; i < iN; i++){ for(int j = 0; j < jN; j++){ for(int k = 0; k < kN; k++){  c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } }	for(int i = 0; i < iN; i++){ for(int k = 0; k < kN; k++){ for(int j = 0; j < jN; j++){   c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } }

Теперь обращения к массиву a идут последовательно.

Разделение циклов на блоки

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

До	После
for(int i = 0; i < iN; i++){ for(int j = 0; j < jN; j++){  a[i][j] = a[i][j] + b[i][j]; } }	// размер блоков зависит от размера исходных массивов int iBlk, jBlk; for(int k = 0; k < iN/iBlk; k++){ for(int m = 0; m < jN/jBlk; m++){  for(int i = k * iBlk; i < ((k + 1) * iBlk); i++){  for(int j = m * jBlk; j < ((m + 1) * jBlk); j++){   a[i][j] = a[i][j] + b[i][j];  }  } } }

Примерно по такому принципу работает технология MPI: делит большие массивы на блоки и рассылает отдельным процессорам.

Разрешение зависимостей

Лучшее решение — избавиться. Но не со всеми зависимостями это получится.

for (int i = 1; i < N; i++){
 a[i] = a[i-1] + 1;
}

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

Относительно условных переходов

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

Вместо заключения

Если Вы создаете сложную программу, которая будет занимать много процессорного времени, то

1. Ознакомтесь с архитектурой процессора (узнайте сколько и каких исполняющих устройств у него есть, сколько конвейеров, размеры кэшей L1 и L2).
2. Попробуйте компилировать программу разными компиляторами и с различными ключами.
3. Учитывайте влияние операционной системы.

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

Если хотите сами потренироваться в оптимизации, то попробуйте вычислить число Пи:


Ниже приведен «плохой» код.

long N = 10000000;
double dx, sum, x;
sum = 0.0;
x = 0.0;
dx = 1.0 / (double) N;
for (long i = 0; i < N; i++){
 sum += 4.0 / (1.0 + x * x);
 x += dx;
}
double pi = dx * sum;

О чем я не рассказал: о векторизации вычислений (инструкции SSE); о prefetch'ах, облегчающих работу с памятью. Если будут люди «которым интересно», то напишу отдельную статью про векторизацию циклов.

Подсветка исходных кодов Source Code Highlighter.