您好、欢迎来到现金彩票网!
当前位置:双彩网 > 向量化率 >

自动SIMD向量化中基于混合并行的循环分段展开技术

发布时间:2019-07-01 05:59 来源:未知 编辑:admin

  摘要:当前含有 SIMD 功能部件的计算机体系结构中,一般其向量部件与标 量部件可并行工作,为了提高系统的硬件资源利用率,文章针对向量化循环,提 出了基于混合并行的分段展开变换方法。文章以处理器的硬件模型为基础,分析 了开发混合并行的限制条件,设计了一种针对此模型的循环分段展开算法,可将 原来完全向量化的循环,变换为向量与标量混合计算的循环。通过此方法,可以 提高系统的资源利用率,经对 SPECCPU2000 浮点测试表明,此向量化方法对一 些向量化较好的例子,加速比有 10%左右的提升。 关键词 自动向量化,SIMD,混合并行,循环分段展开 中图法分类号 TP311 文献标识码 A

  二十世纪末, 家用电脑得到充分的发展,多媒体应用是家用电脑的主要用途 之一。而多媒体程序由于对大量数据采用相同的操作,因此适于进行向量化。自 从 1996 年 Intel 在奔腾处理器上集成了 MMX 后越来越多的通用处理器上集成了 SIMD(Single Instruction Multiple Data,单指令多数据)扩展,很多的厂商在处 理器中都集成了这一多媒体扩展应用。如今数据的处理越来越庞大,如游戏机芯 片、大规模并行处理机等,因此,SIMD 技术不仅用在多媒体处理方面,而且用 在各种有大量数据存取的应用中, 为当前的海量数据存取以及高性能计算提供了

  一种有效方法。使用 SIMD 技术的方法很多,其中的自动向量化技术是一个有效 的方法, 既能获得较好的性能也能为程序员节约较多的时间。但是传统的自动向 量化方法, 只是尽量开发出程序的向量化能力,并没有考虑系统的硬件资源利用 情况。 当前的 SIMD 计算机中,为了较高的性价比,体系结构中一般有标量功能部 件和 SIMD 功能部件[1][2],两种部件之间可以并行执行(类似于多指令多数据的 执行结构 MIMD) 。示意结构如下图所示:

  本文提出采用混合并行的方法提高系统的硬件资源利用率,因此需要对程序 进行一定的变换以开发程序的混合并行能力。通过循环分段展开[3][4]技术改变循 环内语句的执行方式, 形成无依赖的向量语句与标量语句混合的循环,同时利用 向量与标量部件,以提高系统的资源利用率。 一般 SIMD 功能部件和标量功能部件间的比例要根据处理机的用途来确定, 理想的状况是能使这两类计算尽量在大多数应用中保持平衡, 即向量计算用的时 间和标量计算相等,这样才能最大限度的提高资源利用率。 但是,在实际应用中,向量代码与标量代码所占的比例不可能刚好满足硬件 的要求。即使比例相符合,但由于存在依赖和控制因素,向量代码和标量代码也 不一定能同时在向量硬件和标量硬件上执行。为了满足体系结构的这一特点,在 自动向量化编译中提出了针对向量化循环语句的分段展开技术, 通过分段展开变 换后,使循环的每一次迭代中,一部分语句可以向量执行,另一部分语句同时可 以标量执行,而要使这种混合的循环向量化需要用到超字并行[5]的向量化算法, 本文对变换后的循环均使用此向量化算法, 对此算法的研究较多, 不再过多讨论。 利用循环变换开发 SIMD 向量化混合并行的研究相对较少, 与体系结构关系 较密切,Samuel Larsen 提出了一种选择向量化的概念[6][7],从指令的角度来出发 的,将同一条语句的不同部分向量化,对比其效率,从而选择一种最有利的向量

  化方法,但此方法代价分析很困难,在自动向量化中实现也比较困难。本文提出 了基于混合并行的循环变换技术, 较易实现, 且在实际测试中取得了较好的效果。

  模型假设:假设处理器体系结构中,包括一个 SIMD 功能扩展部件,两个标 量执行单元,SIMD 向量寄存器的宽度为 128 位,一次可以存取 4 个 32 位整型 数据。结构图如下:

  假定向量操作是标量操作需要的机器周期数的 2 倍(实际情况可能不是这样 的,不同的硬件结构间也会有差异,这里只是用一种简单的情况来说明),还假 定不同的操作间机器周期数也是一样的(具体的情况要根据硬件结构来确定,只 是一种简单的假设)。 先不考虑指令的发射及数据加载的时延,要想使部件运算平衡,需要向量化 后的指令和标量指令的比例为:1/4,此模型中标量执行能力与向量执行能力相 当, 相同周期内标量部件与向量部件计算的数据量相同。实际机器可能没有模型 的这么简单,但向量部件与标量部件操作的机器周期数的比例一般来说是固定 的, 可以通过实验得到向量操作与标量操作平衡时的语句比例,在本章讨论的模 型中执行一次向量操作, 同时可以执行两次标量操作。当标量部件与向量部件共 同工作时, 可以让向量部件的机器周期数掩盖标量部件的周期数,这也是将向量 语句展开成标量语句的原因。 为了便于说明这个问题,机器硬件的功能如 2 中的模型假设一样,处理器中 有两个标量部件, 一个 SIMD 功能部件,执行一个 SIMD 指令需要的周期数是一 个标量指令周期数的 2 倍。先假设标量指令的机器周期为 1,向量指令的机器周 期为 2,用下面的例子来说明这种语句展开的好处:

  上例所示,若标量执行,需要的机器周期数为:1024 个周期。向量化后程序 如下所示:

  向量化后的机器周期数为:256*2=512 个周期,加速比为标量执行的 2 倍, 若使用功能部件并行的方法,将循环中的向量循环分段展开为如下形式:

  上面的形式,V1 可向量化执行,V1 中使用的数据是 4 个连续的数据,且每 次迭代语句首地址为 8*i, 这种存储的数据符合向量化取数时地址对齐的要求 (下 节讨论),且语句 V1、S1、S2、S3、S4 之间均没有数据依赖性,这几条语句可 并行执行。执行到此循环时,向量部件执行 V1,需 2 个周期,两个标量部件执 行 S1、S2 需一个周期,S1、S2 执行完后,向量部件还在执行 V1,两个标量部 件继续执行 S3、S4,一个周期之后,三个执行部件均执行完毕,这样,循环的 一次迭代就执行完了。可用如下的图表来表示其执行过程:

  通过上面的分析可知,这种功能部件并行后,程序的执行周期数为:128*2 = 256,加速比为向量化之后的 2 倍。原因就是,本模型中向量执行部件与标量执 行部件的运算能力相同,并行操作,使向量的运算总量减少了一半

  实际应用中,功能部件的并行限制条件很多,常规手工编写的代码一般是不 会考虑到硬件的结构特点,并且还有控制依赖和数据依赖的限制,因此是不适合 进行功能部件并行的。向量化循环分段展开虽可以开发混合并行,但是对向量化 的语句展开也不是完全没有限制的。 有时不正确的分段方法可能会导致向量化的 语句地址不对齐, 而混合的语句也不一定能在不同的功能部件上并行,具体情况

  还要看如何分段。 3.1 应用程序混合并行的限制 循环变换针对的是应用程序,使应用程序更加符合目标机体系结构的特点。 下面就主要讨论一下应用程序中对并行操作的约束,约束条件是: (1) 并行操作的语句要在同一个循环体内; (2) 不存在语句间的控制依赖; (3) 不存在语句间的数据依赖。 再对以上三条约束进行解释,首先,并行操作的语句要在同一个循环体内。 当前的商用编译器和科学研究编译器,由于要确保程序运行的正确,只保守的考 虑循环体内部向量语句与标量语句的并行计算。若语句在不同的循环体内,其语 句间的相关性更加复杂,基础编译时,如果要判断这些语句间的关系,以确定其 是否可并行操作的难度很大,从应用的角度来说,实现这种判断是非常困难的。 并且若语句在循环体外,一般计算的数据复杂性不大,可并行的价值也不高,因 此编译器往往会忽略这些语句的并行性。 其次,语句间的控件依赖会阻碍语句的并行操作。控制依赖增加了指令执行 的不确定性,语句是否执行,要看其控制条件是否达到。如下面的例子:

  上例中,通过依赖分析,S1 每一次迭代用到的 a[i]的值均是上一次迭代的结 果,其不可向量化,只能按标量执行,S3 语句可向量执行,S2 语句是一条控件 语句。若无 S2 语句,则 S1 语句可在标量部件上执行,S3 语句在向量部件上执 行,此两条语句使用不同的功能部件,可并行操作,其总的执行时间为 S1、S3 语句中耗时较长的语句。 但是由于 S2 的控制语句的存在, 语句的执行不确定, S3 这也导致了 S3 语句的执行是不连续的,S3 语句也就不可向量化执行了,否则会 导致 c[i]的结果错误。虽然在并行计算中有一些研究处理控制依赖的方法,但是 无针对功能部件并行操作的控制研究,本文也暂不对此作过多的研究,这只是程 序并行操作的一个约束条件,如何解决有待进一步研究。 最后,语句间的数据依赖也会阻碍语句的并行操作。可以先看如下的例子:

  上例中,S1 每一次迭代用到的 a[i]的值均是上一次迭代的结果,因此 S1 不

  可向量化,S2 可向量执行,这两条语句执行时使用的是不同的功能部件。针对 数组 a[i], 与 S2 之间有一个流依赖, 语句每次执行时需要用到的数据 a[i+1], S1 S2 都要从 S1 语句的执行结果中去取到。这样,S2 必须在 S1 执行完之后再执行, S1 与 S2 就不能同时在不同的功能部件上执行, 因此数据依赖阻碍了功能部件的 并行。 上面分析的几个约束条件都是针对应用程序的,而自动向量化的目标就是将 原本非向量执行的应用程序,通过对程序的结构、数据进行分析,再做一些基本 的变换将标量执行的语句变换为向量执行的语句。 在讨论如何从应用的角度来开 发功能部件的并行性时,主要就是从这些方面进行分析,最后,按照体系结构和 应用程序的特点选择有利的循环变换, 以期在特定目标机下针对同一个应用获得 较高的加速比。 3.2 针对向量化对齐的分段限制 针对本章假定的硬件模型,循环中向量语句数与标量语句数的比例为 1:4 时,向量运算与标量运算平衡,按上一节的展开方法,向量化的语句刚好也是对 齐的,这是一种巧合。并不是其它的结构也可以这样分段,下面举例来说明。 若上述结构中硬件只含有一个标量执行部件,则循环中向量与标量的语句数 就应该是 1:2,则例子:

  从上图可知,循环的向量化语句 V1 是不对齐的,V1 的起始地址为 0、6、 12 ? ,向量寄存器每次取四个数据时,只有从 0、4、8、12 ? 作为起始位置来 存取时,才是向量化过程中最高效的存取方式。因此,上面的向量化过程中,向 量化语句 V1 是不对齐的,虽然通过移位等操作,可以使其对齐,但是要增加额 外的开销。因此,不能使用这种分段的方法。 下面来分析一种通用的向量语句展开的分段技术,若一次向量操作可执行四 条语句,功能部件平衡时向量语句与标量语句的比例为 1:m,机器执行一个向 量周期的时间,可计算出 4+m 条语句的结果。假设循环的边界针对向量化是对 齐的,循环的迭代次数为 n。向量化语句展开后,则应向量化的语句应该是

  从上图可知,这样向量化语句 V1 是连续且对齐的,有助于提高向量化的效 率。针对这种分段方法,必须要求向量语句内没有依赖,分段后标量执行的语句 不能依赖前面向量执行的语句, 但是并不是所有的可向量化语句都能满足这个条 件,下面就讨论分段后能否并行的问题。

  3.3 数据依赖对循环分段展开的限制 一般来说,可以向量化的语句,在语句展开后,做为标量语句执行的部分也 可以在两个标量部件间并行工作。SIMD 向量化有依赖距离的限制,若真依赖的 距离超出了向量长度,则语句可以进行向量化(第二章中已讨论)。但是,若按 照上图的分段方法, 分段的距离一般会大于真依赖的距离,这就破坏了原有的依 赖关系。 按上一小节 4.2.1 的模型假设,向量化一次可以处理 4 个数据,计算平衡时 标量与向量语句的比例为 2:1,有时分段后由于依赖,也不能进行并行工作,可 以用下面的例子来进行说明:

  上例子数组 a 的依赖距离不小于向量化因子的长度 4,其可以向量化。若按 照前一节的要求向量对齐的分段方法,则分为如下的循环:

  经 过 上 述 变 换 后 , 第 一 次 迭 代 i=0 , 例 19 中 的 第 二 条 语 句 变 为 : a[44]=a[40]+b[40],此时用到的数据 a[40]是此循环之前赋的值,这个循环还未对 其进行写操作。而实际上,原循环串行执行的过程如下所示:

  显然,串行执行时,语句:a[44]=a[40]+b[40],用到的数据 a[40]在本次循环 执行的过程中被写过一次,a[40]与循环执行前的值已经不同了。因此,上述的 分段展开变换已改变了程序的数据依赖关系。总起来说,对可向量化语句 S,若 S 存在自身真依赖或 S 与其它语句形成了一个流依赖环(第二章已讨论) ,则对 向量化语句 S 不能采用分段展开的方法开发其并行性。

  4.1 向量寄存器的地址对齐分析 在自动向量化的过程中,要想使向量部件与标量部件并行工作,先要开发出 程序中的向量化特性。循环向量化时,首先要有足够的语句打成一个向量包,向 量计算的地址也应该是对齐的,这样才有较高的向量化效果。 所谓数据对齐[3][6],就是内存首地址是数据宽度的倍数。按照上节的多功能 部件计算模型,向量寄存器宽度为 128 位,每次向量操作存取的数据宽度就为 128 位,数据存取的首地址就应是 128 的整数倍。编译器一般可保证数组在内存 中的首地址对齐,以 32 位整型数据计算为例,从数组首地址开始,每隔 4 个连 续的数据(若 64 位浮点型数据,每两个连续数据)就会有一个对齐边界。若从 对齐边界对向量寄存器进行加载,一次从内存中连续取四个数据,就能保证每次 向量操作是对齐的,可用下图进行说明:

  上例 11 中数据是从 a[2]开始计算,如上图所示,需要将两个连续的区域合 并到一个寄存器,开销较大,因此一般将其从向量化循环中剥离。最后一次迭代 中的数据只有一个, 也不能加载到一个向量寄存器中,对此应对这个向量化循环 进行剥离,向量化循环剥离后的形式如下所示:

  例 12 的三个循环,L2 可完全向量化,且数据是对齐和连续的,效果较好。 L1、L3 数据都不够加载到一次向量化中,因此这两个循环标量执行。向量化循 环边界对齐的算法描述如下:

  令 k 是一次向量化操作可处理 l 内数据的个数; //若以本章的模型, 数据为整型 k=4, 为浮点 k=2;

  4.2 向量化循环分段展开算法 在向量化循环无法与其它标量循环并行工作时,可采用对向量化循环分段展 开的思想来开发功能部件的并行性。前两小节讨论了其基本的思想和分段的限 制,本节将根据前面的讨论提出基于功能部件并行的向量化循环分段展开的算 法。算法描述如下:

  // k 是向量化因子,即一次向量操作可运算的标量语句个数 //在下面的过程中,将按照前面的限制来进行分段展开

  上述算法可简单描述为以下四个步骤: (1) 判断可向量化语句是否是自身真依赖,或处于一个流依赖的环中,否则, 继续; (2) 判断可向量化语句是否有足够的长度进行向量与标量混合计算展开; (3) 若循环不能刚好达到向量与标量混合计算平衡,则将多出的部分剥离; (4) 对向量与标量混合段的代码,更改循环上下界,同时更改语句下标,构 造对齐的向量化语句和无依赖可并行执行的标量语句。

  5.1 测试 本文所做试验选取的硬件平台是在国产CPU SW1600上进行试验,此处理器 支持的SIMD处理长度为256位, 2GB的内存。 操作系统是Red Hat Enterprise Linux 5。 实验所采用的编译器有GCC编译器、Intel编译器和本项目基于OPEN64开发的 自动向量化的工具SW-VEC。 此处理器上有一个SIMD部件,两个标量部件,各功能部件可以并行工作, 由指令发送部件向各流水线上发送不同的计算指令,其中向SIMD部件单发射指 令,向标量部件双发射指令。SIMD计算指令需要的周期数一般比标量部件计算 的周期数要多,但SIMD部件计算指令的时延又没有达到标量计算部件的两倍, 考虑到访存的延时等问题,向量部件的延迟又达不到标量部件的两倍。 针对功能部件并行循环合并与循环分段展开技术主要与目标机的体系结构 有关,若目标机不支持这种结构,则不能进行这种变换。本文针对功能部件并行 测试时,目标机的向量寄存器的位数为 256 位,一次可执行 8 条 32 位整型语句 或 4 条 64 位浮点语句,有两个可并行的标量执行部件。从理论上来说,不考虑 其它因素的影响, 对向量化部分有 12.5%-50%的加速比的提高。而程序中可向量 化的循环的数量是有限的, 又只能对程序中向量化的循环进行一定的合并或分段 展开技术。实际中,由于存在指令调度和数据存取方面的影响,计算的速度提高 并不一定会带来同样的加速比的提高。

  图 9 传统自动向量化和应用混合并行的向量化对 spec2000 程序的加速比

  上图是基于open64实现的传统的自动向量化和基于混合并行的自动向量化 在国产处理器上的测试结果, 改进后程序平均加速比有所提高,相对于原来的向 量化方法对几个向量化较好的例子性能提高10%左右。 从测试可以看出使用此文 的方法通过充分分析程序中语句的数据依赖性,再利用循环分段展开技术,生成 向量化代码与标量代码并行执行的循环,可更充分地利用系统的硬件资源。

  5.2 小结 本文针对含有 SIMD 功能部件扩展的计算机体系结构,利用其向量部件与标 量部件可并行工作的特点, 提出了基于混合并行的向量化循环分段展开的变换方 法,这对提高系统的硬件资源利用率很有意义。 功能部件并行时需要向量与标量计算达到平衡,针对完全向量化的循环,本 文提出了将向量化循环分段展开的变换方法, 通过此变换将原来完全向量化的循 环变换为向量与标量混合计算的循环,以此来开发程序的混合并行能力。 要使系统中向量计算与标量计算平衡,就需要使循环中向量语句的执行时间 与标量语句的执行时间相当。而不同的体系结构中,向量部件的计算能力不同, 向量部件与标量部件的计算能力关系还需要实际测试来确定, 达到绝对的计算平 衡也是不可能的事情。因此,本文假设了一个相对简单的机器模型,暂不考虑不 同指令间的差异, 假定向量指令与标量指令为整倍数的关系,也未考虑循环内语 句计算复杂性的问题。这些问题在实际应用中,也不可能精确的考虑,自动向量 化中实现绝对的运算平衡是不可能的,因此只能利用循环变换达到相对的平衡。 致谢 在此, 谨向对本文提出宝贵建议的审稿专家以及参与本文内容讨论的所有 老师和同学表示衷心的感谢!

http://chinoamobi.com/xianglianghualv/213.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有