Удалить условия в программе на C для ускорения

Question

У меня есть программа C для вычисления чисел, которая включает основной цикл с двумя условиями:

for (i = 0; i < N; i++) {
 for (j = 0; j < N; j++) {
  for (k = 0; k < N; k++) {
    if (k == i || k == j) continue;
    ...(calculate a, b, c, d (depending on k)  
    if (a*a + b*b + c*c < d*d) {break;}
  } //k
 } //j
} //i

Аппаратное обеспечение - это SPE процессора Cell, где при использовании ветвления существует большой штраф. Итак, чтобы оптимизировать мою программу для ускорения, мне нужно удалить эти 2 условия, знаете ли вы о хороших стратегиях для этого?

Answer 1

Для первого вы можете разбить его на несколько циклов, например, изменить:

for(int i = 0; i < 1000; i++)
  for(int j = 0; j < 1000; j++) {
    for(int k = 0; k < 1000; k++) {
      if(k==i || k == j) continue;
      // other code
    }
  }

на:

for(int i = 0; i < 1000; i++)
  for(int j = 0; j < 1000; j++) {
    for(int k = 0; k < min(i, j); k++) {
      // other code
    }
    for(int k = min(i, j) + 1; k < max(i, j); k++) {
      // other code
    }
    for(int k = max(i, j) + 1; k < 1000; k++) {
      // other code
    }
  }

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

int left_side = 1, right_side = 0;
for(int i = 0; i < N; i++)
  for(int j = 0; j < N; j++) {
    for(int k = 0; k < min(i, j) && left_side >= right_side; k++) {
      // other code (calculate a, b, c, d)
      left_side = a * a + b * b + c * c;
      right_side = d * d;
    }
    for(int k = min(i, j) + 1; k < max(i, j) && left_side >= right_side; k++) {
      // same as in previous loop
    }
    for(int k = max(i, j) + 1; k < N && left_side >= right_side; k++) {
      // same as in previous loop
    }
  }

Реализация min и max без ветвления также может быть сложной задачей.Может быть, эта версия лучше:

int i, j, k, 
  left_side = 1, right_side = 0;
for(i = 0; i < N; i++) {
  // this loop covers the case where j < i
  for(j = 0; j < i; j++) {
    k = 0;
    for(; k < j && left_side >= right_side; k++) {
      // other code (calculate a, b, c, d)
      left_side = a * a + b * b + c * c;
      right_side = d * d;
    }
    k++; // skip k == j
    for(; k < i && left_side >= right_side; k++) {
      // same as in previous loop
    }
    k++; // skip k == i
    for(; k < N && left_side >= right_side; k++) {
      // same as in previous loop
    }
  }
  j++; // skip j == i
  // and now, j > i
  for(; j < N; j++) {
    k = 0;
    for(; k < i && left_side >= right_side; k++) {
      // other code (calculate a, b, c, d)
      left_side = a * a + b * b + c * c;
      right_side = d * d;
    }
    k++; // skip k == i
    for(; k < j && left_side >= right_side; k++) {
      // same as in previous loop
    }
    k++; // skip k == j
    for(; k < N && left_side >= right_side; k++) {
      // same as in previous loop
    }
  }
}

Answer 2

Я согласен с 'sje397'.

Кроме того, вы предоставляете слишком мало информации о своей проблеме. Вы говорите, что ветвление дорого. Но как часто это происходит на самом деле? Может быть, ваша проблема в том, что сгенерированный компилятором код выполняет ветвление в общем сценарии?

Возможно, вы могли бы перестроить свои if -ы. Реализация if на самом деле зависит от компилятора, но многие компиляторы относятся к ней прямо. То есть: if - обычный - else - редкий (прыжок).

Тогда попробуйте следующее:

for (i = 0; i < N; i++) {
 for (j = 0; j < N; j++) {
  for (k = 0; k < N; k++) {
    if (k != i && k != j)
    {
      ...(calculate a, b, c, d)  
      if (a*a + b*b + c*c >= d*d)
      {
        ...
      } else
        break;
    }
  } //k
 } //j
} //i

EDIT:

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

Answer 3

Вы уверены, что вам действительно нужен первый оператор if?Даже если он перескакивает один расчет, когда k равно i или j, штраф за проверку его на каждой итерации очень дорогой.Кроме того, имейте в виду, что если N не является константой, компилятор, вероятно, не сможет развернуть циклы for.

Хотя, если это процессор с ячейками, компилятор может даже попытаться векторизовать циклы.

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

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

... может стать ...

for (i = N; i != 0; i--) {

Хотя, если "i" используется в качестве индекса или переменной в вычислениях, вы можете получить снижение производительности, так как вы получите ошибки в кеше.

Answer 4

Я бы сначала посмотрел на ваш код calculate, потому что это может затмить все эти проблемы ветвления. Некоторая выборка выяснила бы наверняка.

Однако, похоже, что для каждого i,j вы выполняете линейный поиск первой точки внутри сферы. Могли бы вы иметь 3 массива, по одному для каждой из осей X, Y и Z, и в каждом массиве хранить индексы всех исходных точек в порядке возрастания по этой оси? Это может облегчить поиск ближайшего соседа. Кроме того, вы можете использовать тест в кубе, а не тест в сфере, поскольку вы не ищете ближайшую точку, а только ближайшую точку.