• 1. 向量化算法总结
  • 2. 最常用的向量化算法传统的基于循环的向量化:针对基本块的SLP向量化: 发掘迭代间的向量并行性,即将每条语句不同的迭代间的实例压缩在一起并行运行。它是用于不存在迭代内并行的普通循环。 SLP针对基本块做向量化, 给定一个循环,若在迭代内已经存在向量并行性,并且并行宽度是硬件向量宽度的整数倍(倍数〉=1),那么不需要循环展开,直接使用SLP方法对loop的循环体进行发掘。 又称pure SLP(展开因子=1)for(){ a[i]=b[i]*c[i]; d[i]=b[i]+c[i]; }for (i = 0; i < n; i++) { c[4i] = a[4i] + b[4i+1]; c[4i+1] = a[4i+2] + b[4i+3]; c[4i+2] = a[4i+3] + b[4i]; c[4i+3] = a[4i+1] + b[4i+2]; }
  • 3. 最常用的向量化算法改进的SLP——循环展开后进行SLP:特点:将迭代间的并行转化为迭代内的并行Stmt1(i) ii+1Stmt1(i+1) i+2Stmt1(i+2) i+3Stmt1(i+3) SLP
  • 4. 最常用的向量化算法改进的SLP——循环展开后进行SLP:发掘迭代间向量并行for(i=0;i
  • 5. 最常用的向量化算法改进的SLP——循环展开后进行SLP:发掘迭代内和迭代间的并行:for(i=0;i
  • 6. 适合用SLP的程序1、已经展开过的循环
  • 7. 适合用SLP的程序2、存在结构不同成员的同构操作
  • 8. 适合用SLP的程序3、非单指令多数据方式
  • 9. 适合用SLP的程序4、需要复杂数据重组
  • 10. 适合用SLP的程序程序特征总结:唯一特征:存在迭代内并行性!!!
  • 11. GCC中的向量化算法Gcc中向量化算法分类:1、针对循环的向量化 pass pass_vectorize2、针对基本块的向量化 pass pass_slp_vectorizeA、loop-based vectorize(传统向量化)B、pure SLPC、hybrid SLP(混合向量化)A、SLP
  • 12. GCC中的向量化算法Gcc中向量化实现顺序:最初实现: loop-based vectorize(传统向量化) 2004 可向量化循环的描述: 1最内存循环只含有一个基本块(没有if-then-else) 2循环的迭代次数在循环执行前就可以确定。 3循环边界已知,可以被向量化因子(每条向量指令可以并行执行的数据宽度) 4循环索引变量从0到N,并且步长为1,循环条件是i
  • 13. GCC中的向量化算法Gcc中向量化实现顺序:功能加强:加入pure-SLP和hybrid SLP 2007 针对基本块的向量化 pass pass_slp_vectorize
  • 14. GCC中的向量化算法调度GCC中的几种向量化算法是怎样调度的?1、对循环的向量化与对基本块的向量化是独立的两个pass2、对循环的向量化采用了混合的SLP向量化方法。A、首先进行传统向量化分析,目的是分析迭代间的向量并行。 B、若传统向量化分析通过,进入SLP分析过程入口。 C、真正进行SLP分析的启动条件是循环中存在非连续访存: 即array[coeff * i],其中coeff!=0。
  • 15. GCC中的向量化算法特点真正的混合向量化,体现在:1、同一个循环体内,某些语句传统向量化,某些语句SLP向量化。2、SLP向量化的实例外,有对实例内数据的引用,那么将之设置为hybrid SLP,这时可能需要将此语句拆成两个版本。供实例内和实例外的引用能够涵盖大多数存在迭代内并行的情况。非连续访存驱动的SLP:自底向上的SLP发掘 算法:从store开始发掘,根据使用定义关系一步步往上发掘。没发现循环展开的部分,取而代之的是在每条语句里记录需要的循环展开因子。在SLP分析之前不进行真正的循环展开:
  • 16. 建议的传统向量化与SLP结合方式Step1 传统向量化分析。若通过,进入step2 Step2 检查循环是否存在迭代内的并行,若存在那么进入step3 Step3 保存原有的信息(若SLP不成功,可回溯到当前状态 )计算展开因子, 循环展开并用SLP方法发掘迭代内并行。若不成功,那么返回到传统向量化状态。 Note : 检查循环存在迭代内并行的程序特征方法。
  • 17. 谢谢