Вложенная Loop Unrolling in C

Question

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

Эти петли переносят матрицу.

Это мой цикл, чтобы применить разворачивая цикл:

void transpose(int dim, int *src, int *dst) { 
    for (i = 0; i < dim; i++) 
     for (j = 0; j < dim; j++) 
      dst[j * dim + i] = src[i * dim + j]; 
} 

Это мой разворачивания цикл:

void transpose(int dim, int *src, int *dst) { 
    int i = 0, j = 0, dimi = 0, dimj = 0, tempi = 0; 

    for (i = 0; i < dim; i += 8) { 
     for (j = 0; j < dim; j++) { 
      dimj = j * dim + i; 
      dimi = i * dim + j; 
      dst[dimj] = src[dimi]; 

      tempi = i + 1; 
      if (tempi < dim) { 
       dimj = j * dim + tempi; 
       dimi = tempi * dim + j; 
       dst[dimj] = src[dimi]; 

       tempi += 1; 
       if (tempi < dim) { 
        dimj = j * dim + tempi; 
        dimi = tempi * dim + j; 
        dst[dimj] = src[dimi]; 

        tempi += 1; 
        if (tempi < dim) { 
         dimj = j * dim + tempi; 
         dimi = tempi * dim + j; 
         dst[dimj] = src[dimi]; 

         tempi += 1; 
         if (tempi < dim) { 
          dimj = j * dim + tempi; 
          dimi = tempi * dim + j; 
          dst[dimj] = src[dimi]; 

          tempi += 1; 
          if (tempi < dim) { 
           dimj = j * dim + tempi; 
           dimi = tempi * dim + j; 
           dst[dimj] = src[dimi]; 

           tempi += 1; 
           if (tempi < dim) { 
            dimj = j * dim + tempi; 
            dimi = tempi * dim + j; 
            dst[dimj] = src[dimi]; 

            tempi += 1; 
            if (tempi < dim) { 
             dimj = j * dim + tempi; 
             dimi = tempi * dim + j; 
             dst[dimj] = src[dimi]; 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Answer 1

Я не уверен, что ошибка в текущем коде, но здесь это другой подход.

void transpose(int dim, int *src, int *dst) { 
    int i, j; 

    for (i = 0; i <= dim-8; i += 8) 
    { 
     for (j = 0; j < dim; j++) 
     { 
       dst[j * dim + (i+0)] = src[(i+0) * dim + j]; 
       dst[j * dim + (i+1)] = src[(i+1) * dim + j]; 
       dst[j * dim + (i+2)] = src[(i+2) * dim + j]; 
       dst[j * dim + (i+3)] = src[(i+3) * dim + j]; 
       dst[j * dim + (i+4)] = src[(i+4) * dim + j]; 
       dst[j * dim + (i+5)] = src[(i+5) * dim + j]; 
       dst[j * dim + (i+6)] = src[(i+6) * dim + j]; 
       dst[j * dim + (i+7)] = src[(i+7) * dim + j]; 
     } 
    } 

    // Use the normal loop for any remaining elements 
    for (; i < dim; i++) 
     for (j = 0; j < dim; j++) 
      dst[j * dim + i] = src[i * dim + j]; 
} 

Примечание: Число умножения может быть уменьшена за счет введения переменной, как:

int jdim = j * dim + i; 
dst[jdim + 0] = ... 
dst[jdim + 1] = ... 
... 
dst[jdim + 7] = ... 

и аналогично для РИТ.

Answer 2

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

Одно можно сказать наверняка: код стал намного сложнее читать и намного проще испортить.

Если вы знаете наиболее распространенные значения для dim, вы можете попробовать и оптимизировать их. Например, если вы знаете, наиболее распространенный случай матриц 3x3, вы могли бы написать это:

void transpose(int dim, const int *src, int *dst) { 
    if (dim == 3) { 
     dst[0 * 3 + 0] = src[0 * 3 + 0]; 
     dst[0 * 3 + 1] = src[1 * 3 + 0]; 
     dst[0 * 3 + 2] = src[2 * 3 + 0]; 
     dst[1 * 3 + 0] = src[0 * 3 + 1]; 
     dst[1 * 3 + 1] = src[1 * 3 + 1]; 
     dst[1 * 3 + 2] = src[2 * 3 + 1]; 
     dst[2 * 3 + 0] = src[0 * 3 + 2]; 
     dst[2 * 3 + 1] = src[1 * 3 + 2]; 
     dst[2 * 3 + 2] = src[2 * 3 + 2]; 
    } else { 
     for (int i = 0; i < dim; i++) { 
      for (int j = 0; j < dim; j++) { 
       dst[j * dim + i] = src[i * dim + j]; 
      } 
     } 
    } 
} 

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

Answer 3

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

void transpose(int dim, int *src, int *dst) { 
    // represent where the data is being read and where it is going 
    int dstIndex = 0; 
    int srcIndex = 0; 

    // precalculate constants used within the loop 
    int total = dim*dim; 
    int unrolled = dim/4; 

    int dimx0 = dim*0; 
    int dimx1 = dim*1; 
    int dimx2 = dim*2; 
    int dimx3 = dim*3; 
    int dimx4 = dim*4; 

    int i = 0; 
    int j = 0; 

    // since the matrix is being transposed i,j order doesn't matter as much 
    // because one of the matrices will be accessed by column and the other 
    // will be accessed by row (more effecient) 
    for (j = 0; j < dim; j++) { 
     for (i = 0; i < unrolled; i++) { 
      // here the loop is being unrolled 
      // notice that each statement does not rely on previous statements 
      // and there is no conditional code 
      dst[dstIndex + 0] = src[srcIndex + dimx0]; 
      dst[dstIndex + 1] = src[srcIndex + dimx1]; 
      dst[dstIndex + 2] = src[srcIndex + dimx2]; 
      dst[dstIndex + 3] = src[srcIndex + dimx3]; 
      dstIndex += 4; 
      srcIndex += dimx4; 
     } 

     // the transpose was previously completed in larger blocks of 4 
     // here whtever indices that were not transposed will be taken care of 
     // e.g. if the matrix was 13x13, the above loop would run 3 times per row 
     // and this loop would run once per row 
     for (i = unrolled; i < dim; i++) { 
      dst[dstIndex] = src[srcIndex]; 
      dstIndex += 1; 
      srcIndex += dim; 
     } 

     // increment the source index 
     srcIndex %= total; 
     srcIndex += 1; 
    } 
}