向量化算法总结

1、向量化算法总结最常用的向量化算法传统的基于循环的传统的基于循环的向量化向量化：针对基本块的针对基本块的SLP向量化向量化： 发掘迭代间的向量并行性，即将每条语句不同的迭代间的实例压缩在一起并行运行。它是用于不存在迭代内并行的普通循环。 SLP针对基本块做向量化， 给定一个循环，若在迭代内已经存在向量并行性，并且并行宽度是硬件向量宽度的整数倍（倍数=1），那么不需要循环展开，直接使用SLP方法对loop的循环体进行发掘。 又称pure SLPpure SLP（展开因子=1）for（）ai=bi*ci;di=bi+ci;for (i = 0; i n; i+) c4i = a4i + b4i+1;

2、c4i+1 = a4i+2 + b4i+3;c4i+2 = a4i+3 + b4i;c4i+3 = a4i+1 + b4i+2;最常用的向量化算法改进的改进的SLP循环展开后进行循环展开后进行SLP：特点：特点：将迭代间的并行转化为迭代内的并行Stmt1(i)ii+1Stmt1(i+1)i+2Stmt1(i+2)i+3Stmt1(i+3)SLP最常用的向量化算法改进的改进的SLP循环展开后进行循环展开后进行SLP：发掘迭代间向量并行for（i=0；iN；i+=1）ai=bi*ci;for（i=0；iN；i+=4）Ai:i+3 = bi:i+3 * ci:i+3;for（i=0；iN；i+=4）

3、ai=bi*ci;ai+1=bi+1*ci+1;ai+2=bi+2*ci+2;ai+3=bi+3*ci+3;应用1：最常用的向量化算法改进的改进的SLP循环展开后进行循环展开后进行SLP：发掘迭代内和迭代间的并行：for（i=0；iN/2；i+=1）a2i=b2i*c2i;a2i+1=b2i+1*c2i+1;for（i=0；iN/4；i+=1）a4i=b4i*c4i;a4i+1=b4i+1*c4i+1;a4i+2=b4i+2*c4i+2;a4i+3=b4i+3*c4i+3;for（i=0；iN/4；i+=1）A4i:4i+3 = b4i:4i+3 * c4i:4i+3;应用2：适合用SLP的程

4、序1、已经展开过的循环、已经展开过的循环适合用SLP的程序2、存在结构不同成员的同构操作、存在结构不同成员的同构操作适合用SLP的程序3、非单指令多数据方式、非单指令多数据方式适合用SLP的程序4、需要复杂数据重组、需要复杂数据重组适合用SLP的程序程序特征总结：程序特征总结：唯一特征：存在迭代内并行性！唯一特征：存在迭代内并行性！GCC中的向量化算法Gcc中向量化算法分类：中向量化算法分类：1、针对循环的向量化、针对循环的向量化 pass pass_vectorize2、针对基本块的向量化、针对基本块的向量化 pass pass_slp_vectorizeA、loop-based vecto

5、rize（传统向量化）（传统向量化）B、pure SLPC、hybrid SLP（混合向量化）（混合向量化）A、SLPGCC中的向量化算法Gcc中向量化实现顺序：中向量化实现顺序：最初实现：最初实现： loop-based vectorize（传统向量化（传统向量化） 2004可向量化循环的描述：1最内存循环只含有一个基本块（没有if-then-else）2循环的迭代次数在循环执行前就可以确定。3循环边界已知，可以被向量化因子（每条向量指令可以并行执行的数据宽度）4循环索引变量从0到N，并且步长为1，循环条件是iN的形式。5所有内存存取的都是一维数组。6所有的数组存取都是连续的（跨度都是1），

6、并且是对齐的。7根据目标平台的向量化支持情况，支持的操作包括加减乘。8所有的操作都必须针对相同长度的数据类型。9不允许有规约（如sum += ai）和归纳(如 ai = i)。10循环中不允许有常数和不变量（如 ai = 5）GCC中的向量化算法Gcc中向量化实现顺序：中向量化实现顺序：功能加强：加入功能加强：加入pure-SLP和和hybrid SLP 2007针对基本块的向量化针对基本块的向量化 pass pass_slp_vectorizeGCC中的向量化算法调度GCC中的几种向量化算法是怎样调度的？中的几种向量化算法是怎样调度的？1、对循环的向量化与对基本块的向量化是独立的两个、对循环

7、的向量化与对基本块的向量化是独立的两个pass2、对循环的向量化采用了混合的、对循环的向量化采用了混合的SLP向量化方法。向量化方法。A、首先进行传统向量化分析，目的是分析迭代间的向量并行。B、若传统向量化分析通过，进入SLP分析过程入口。C、真正进行SLP分析的启动条件是循环中存在非连续访存：存在非连续访存： 即arraycoeff * i，其中coeff！=0。GCC中的向量化算法特点真正的混合向量化，体现在：真正的混合向量化，体现在：1、同一个循环体内，某些语句传统向量化，某些语句SLP向量化。2、SLP向量化的实例外，有对实例内数据的引用，那么将之设置为hybrid SLP，这时可能需要将此语句拆成两个版本。供实例内和实例外的引用能够涵盖大多数存在迭代内并行的情况。非连续访存驱动的非连续访存驱动的SLP：自底向上的自底向上的SLP发掘发掘 算法：算法：从store开始发掘，根据使用定义关系一步步往上发掘。没发现循环展开的部分，取而代之的是在每条语句里记录需要的循环展开因子。在在SLP分析之前不进行真正的循环展开：分析之前不进行真正的循环展开：建议的传统向量化与SLP结合方式Step1 传统向量化分析。若通过，进入step2Step2 检查循环是否存在迭代内