基于全局数据重组的循环倾斜优化

Loop Skewing Optimization on Global Data Regrouping

循环倾斜是程序优化中一种循环变换的手段,它改变空间迭代形式,将循环存在的跨迭代的并行用传统的并行标识出来,使得循环可以并行执行。但是循环倾斜后,并行执行的数据在内存中是离散的,而且每次迭代执行的次数是不一致的。为了更有效地利用SIMD,本文提出一种基于全局数据重组的循环倾斜优化方法。首先分析循环倾斜优化,针对数据离散的问题实现全局数据重组,改善数据局部性,循环易于向量化操作;针对迭代执行次数不一致问题,实现非满载向量操作,使尾循环得以向量执行。最后选择wavefront程序进行测试,优化后,程序计算可以获得平均10.73倍的加速效果。

Loop skewing is a method of loop transformation in program optimization. It changes the form of iteration space and marks the across iterations in loops with the traditional parallel. The loop can be calculated in parallel. But after loop skewing, data which is programed in parallel is discrete. Times of every iteration execution are different. To make full use of SIMD exten- sion, this paper presents loop skewing optimization on global data regrouping. We analyze loop skewing optimization and regroup the data in array for the problem of discrete data. This part improves the data locality and it is simple to do the vector operation. Then we realize the non-full vector operation for the problem of different iteration times. This part makes the tail loop can be exe- cuted in veetorization. At last, we choose the wavefront program for testing. After optimization, the program execution speed can be increased by 10.73 times in average.