создание кеш-эффективной версии цикла

Question

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

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

#define N     65536
#define BLOCK 4096

int min(int a, int b);

int main() {

  double a[N];
  double d_a;
  int i,j;
  int bbegin; 
  int bend;

  for(bbegin = 0;bbegin < N;bbegin += BLOCK) {

    bend = min(bbegin + BLOCK, N);

    for(i=bbegin;i<bend;i++){
      for(j=0;j<i;j++){

        /* array a has been filled up elsewhere */
        d_a = a[i] - a[j];
        /* do some stuff with d_a */

      }
    }
  }

}

inline int min(int a, int b) { return (a < b) ? a : b; }

Answer 1

Изменение:

for (i = bbegin; i < bend; i++)
    for (j = 0; j < i; j++)

до:

for (j = 0; j < bend-1; j++)
    for (i = max(bbegin, j+1); i < bend; i++)

Это обрабатывает те же элементы, но в другом порядке, с последующим что каждый a[i] в блоке будет использоваться недавно, когда следующий a[j] загружены, поэтому элементы в этом блоке останутся в кэше.

(max, конечно, имеет очевидное определение, аналогичное min шоу.)