循环优化与多面体模型

忘是亡心i 2023-10-11 10:22 14阅读 0赞

循环通常是数据并行应用的最密集计算段，因此**循环优化**直接影响性能。当面对嵌套循环时，分配给线程的计算粒度将直接影响性能。循环转换如Fission（循环裂变）与Fusion（循环融合）的嵌套式循环可促使并行化，并提高工作效率。

本文就几种循环优化的方法与多面体模型的调度进行简要阐述（因为LZ已经被这些循环优化搞得痛不欲生了）。

--------------------

### Loop fusion ###

顾名思义，该变换令循环进行了融合。如图所示，原始代码是两个for循环，变化之后，对两个循环中 i、j 相同的范围进行了融合。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70]  
我们为了把该变换映射或者说调度到**多面体模型**中去，需要产生调度树。

举例如下：  
![在这里插入图片描述][20190922215034454.png]  
有这样一段用TC写的代码，语句S、T分别为循环语句。其融合操作表述如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70 1]  
Band 操作将S、T所对应的迭代向量进行了融合。

--------------------

### Loop tiling ###

Loop tiling/blocking 的意思是分块，可以将循环的迭代空间**划分为更小的块**，以帮助确保循环中使用的数据在重用之前**一直保存在缓存中**。循环迭代空间的划分导致将大数组划分为更小的块，从而将被访问的数组元素匹配到缓存大小中，增强缓存重用，消除缓存大小需求。

平常的循环：

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

变换后的循环，拥有一个全新的 block 大小B：

for(j=0; j<N; j+=B){ 
      for(i=j; i<min(N, j+B); ++i){ 
        ....
      }
    }

更具体的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70 2]  
下面是一个矩阵向量乘法的例子。有三个数组，每个数组有100个元素。代码没有将数组划分为更小的大小。

int i, j, a[100][100], b[100], c[100];
      int n = 100;
      for (i = 0; i < n; i++) { 
        c[i] = 0;
        for (j = 0; j < n; j++) { 
          c[i] = c[i] + a[i][j] * b[j];
        }
      }

当我们应用循环分块，使用2 \* 2块，代码变为：

int i, j, x, y, a[100][100], b[100], c[100];
      int n = 100;
      for (i = 0; i < n; i += 2) { 
        c[i] = 0;
        c[i + 1] = 0;
        for (j = 0; j < n; j += 2) { 
          for (x = i; x < min(i + 2, n); x++) { 
            for (y = j; y < min(j + 2, n); y++) { 
              c[x] = c[x] + a[x][y] * b[y];
            }
          }
        }
      }

原来的循环迭代空间n×n。数组的访问块(i, j)也是n×n。当n过大和机器的缓存容量太小,访问数组元素的循环迭代(例如,i = 1, j = 1到n)可能交叉的高速缓存线路,导致缓存丢失。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190922213004775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz,size_16,color_FFFFFF,t_70
[20190922215034454.png]: https://img-blog.csdnimg.cn/20190922215034454.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190922215136834.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190922213606291.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdib3dqMTIz,size_16,color_FFFFFF,t_70