развертывание цикла для вложенных циклов в C

Question

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

double
applyFilter(class Filter *filter, cs1300bmp *input, cs1300bmp *output)
{

  long long cycStart, cycStop;

  cycStart = rdtscll();

  output -> width = input -> width;
  output -> height = input -> height;


  for(int col = 1; col < (input -> width) - 1; col = col + 1) {
    for(int row = 1; row < (input -> height) - 1 ; row = row + 1) {
      for(int plane = 0; plane < 3; plane++) {

    output -> color[plane][row][col] = 0;

    for (int j = 0; j < filter -> getSize(); j++) {
      for (int i = 0; i < filter -> getSize(); i++) {   
        output -> color[plane][row][col]
          = output -> color[plane][row][col]
          + (input -> color[plane][row + i - 1][col + j - 1] 
         * filter -> get(i, j) );
      }
    }
    
    output -> color[plane][row][col] =  
      output -> color[plane][row][col] / filter -> getDivisor();

    if ( output -> color[plane][row][col]  < 0 ) {
      output -> color[plane][row][col] = 0;
    }

    if ( output -> color[plane][row][col]  > 255 ) { 
      output -> color[plane][row][col] = 255;
    }
      }
    }
  }

  cycStop = rdtscll();
  double diff = cycStop - cycStart;
  double diffPerPixel = diff / (output -> width * output -> height);
  fprintf(stderr, "Took %f cycles to process, or %f cycles per pixel\n",
      diff, diff / (output -> width * output -> height));
  return diffPerPixel;
}

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

double applyFilter(class Filter *filter, cs1300bmp *input, cs1300bmp *output){

  long long cycStart, cycStop;

  cycStart = rdtscll();

//start
    
  output -> width = input -> width;
  output -> height = input -> height;
    
//function calls outside loop.
    int filterSize = filter -> getSize();
    int divisor = filter -> getDivisor();
    
//intializaions
    
    int inputHlen = input -> height - 1;
    int inputWlen = input -> width - 1;
    

// loop unrolling row + k - 1 , col + k - 1
for(int plane = 0; plane < 3; plane++){
  for(int row = 1; row + 3 < inputHlen; row += 4){
    for(int col = 1; col +3 < inputWlen; col += 4){ 
      
              
          output -> color[plane][row][col] = 0;
          output -> color[plane][row + 1][col + 1] = 0;
          output -> color[plane][row + 2][col + 2] = 0;
          output -> color[plane][row + 3][col + 3] = 0;
          
          int acc1 = output -> color[plane][row][col];
          int acc2 = output -> color[plane][row + 1][col + 1];
          int acc3 = output -> color[plane][row + 2][col + 2];
          int acc4 = output -> color[plane][row + 3][col + 3];
          
          for (int j = 0; j + 3 < filterSize; j += 4) {
              for (int i = 0; i + 3 < filterSize; i += 4){ 
                acc1 = acc1 + (input -> color[plane][row + i - 1][col + j - 1] * filter -> get(i, j) );
                acc2 = acc2 + (input -> color[plane][row + i][col + j]         * filter -> get(i + 1, j + 1) );
                acc3 = acc3 + (input -> color[plane][row + i + 1][col + j + 1] * filter -> get(i +2, j + 2) );
                acc4 = acc4 + (input -> color[plane][row + i + 2][col + j + 2] * filter -> get(i + 3, j + 3) );
              }
            }
          
          acc1 = acc1 / divisor;
          acc2 = acc2 / divisor;
          acc3 = acc3 / divisor;
          acc4 = acc4 / divisor;

          
          acc1 = (acc1 < 0) ? 0 : acc1;
          acc1 = (acc1 > 255) ? 255 : acc1;

          acc2 = (acc1 < 0) ? 0 : acc1;
          acc2 = (acc1 > 255) ? 255 : acc1;
          
          acc3 = (acc1 < 0) ? 0 : acc1;
          acc3 = (acc1 > 255) ? 255 : acc1;
          
          acc4 = (acc1 < 0) ? 0 : acc1;
          acc4 = (acc1 > 255) ? 255 : acc1;
          
          
          output -> color[plane][row][col] = acc1;
          output -> color[plane][row + 1][col + 1] = acc2;
          output -> color[plane][row + 2][col + 2] = acc3;
          output -> color[plane][row + 3][col + 3] = acc4;
          
      }
    }
  }
  
//end

  cycStop = rdtscll();
  double diff = cycStop - cycStart;
  double diffPerPixel = diff / (output -> width * output -> height);
  fprintf(stderr, "Took %f cycles to process, or %f cycles per pixel\n",
      diff, diff / (output -> width * output -> height));
  return diffPerPixel;
}

Answer 1

Одна из проблем заключается в том, что вы хотите развернуть только самый внутренний цикл (col). Пытаясь развернуть две петли (row а также col) вам не хватает большого расчета. Один из способов убедиться в этом - сократить количество итераций цикла в 16 раз (row а также col оба цикла шаг за шагом 4), в то время как тело цикла выполняет только в 4 раза больше работы.

Это потому, что вы смотрите только на "диагональные" элементы:

color[plane][1][1]
color[plane][2][2]
color[plane][3][3]
color[plane][4][4]

для первой итерации цикла, а не

color[plane][1][1]
color[plane][1][2]
color[plane][1][3]
color[plane][1][4]

Вы никогда не вычислите 12 из этих значений. color[plane][2][1]будет одним из них. Вы должны сохранитьrow увеличивается на 1 каждую итерацию и должен обновляться color[plane][row][...] каждую петлю.