（计算机系统结构专业论文）simd编译优化方法研究.pdf

s i m d 编译优化方法研究 插图目录 8 位整数运算在3 2 位处理器上的实现 i n t e ls i m d 多媒体扩展 s i m i ) 多媒体扩展中的乘加指令 s i m d 多媒体扩展中的饱和加法指令 数据依赖关系图一a 数据依赖关系图一b 数据依赖关系图一c 迭代问语句执行次序 迭代问语句执行次序 含有环的数据依赖图 代码- 2 - 1 8 的数据依赖关系图 代码一2 一1 9 的数据依赖关系图 饱和加法的语法树 饱和加法的语法树 饱和算术的原始语法树模版一 饱和算术的目标语法树模版 饱和算术的语法树模版二 代码- 5 - i 中各变量数据位分类 有效位区间的双向传播， g c c 3 5 - v 的编译流程 g c c 3 5 - v 的s i m d 编译优化效果 a g a s s i z i c c 8 0 的s i m d 编译优化效果 s i m d 编译技术对测试程序a d p c m 的优化效果 s i m d 编译技术对测试程序9 7 2 1 7 2 3 的优化效果 1 2 1 3 1 3 1 5 2 0 2 2 2 2 2 3 2 7 2 8 3 0 3 0 4 6 4 6 4 7 4 7 4 7 5 4 5 7 8 3 9 0 9 1 9 4 9 6 ，2 3 4 1 2 3 4 5 6 7召乞q11卜卜卜 h h h h h拢掷拟撕娜纠黜州们蚪州蜗州妣州毒三廿廿廿 十十十十寸寸寸廿口廿寸吨m h h h h h 1 =即阱阱酐酐酐爵酐爵爵爵肾爵目卧爵图图图图图图图图 s i m d 编译优化方法研究 表目录 表一卜lb 唧中的测试程序及核心代码的计算精度要求1 1 表一3 1b e r k e l e ym u l t i m e d i aw o r k l o a d 3 4 表一3 2b e r k e l e ym u l t i m e d i aw o r k l o a d ( 续) 3 5 表一4 一l 表达式( c o n d i t i o n a ) i ( c o n d i t i o n b ) 的取值表4 8 表一5 2 数据类型与有效位区间初值对照表5 5 表一5 3 有效位区间前向传播法则5 5 表一5 4 有效位区间逆向传播法则一5 6 表一6 一l 表达式e 2 i 与( e 2 1 ) + ( e 2 & i ) 的取值范围6 5 表一9 一l 测试程序及其应用领域8 9 表一9 2g e e 3 5 - v 的s i 帅优化效果9 0 表一9 3 整体优化性能的综合分析一9 2 表一9 4s i m d 编译优化技术在实际应用中的利用状况9 3 表一9 5 各项s i m d 编译优化技术在a d p c m 编译优化中的效果9 5 s i m d 编译优化方法研究 摘要 随着多媒体应用在计算领域中的重要性日趋显著，为了在多媒体应用中获得 更为出色的性能表现，几乎所有的通用处理器生产厂商都为他们的处理器集成了 一个或多个多媒体扩展部件。由于多媒体应用的核心代码往往具有高度的可并行 性，并且对计算精度的要求远低于通用处理器所提供的计算能力，因此这些多媒 体扩展部件往往以通用处理器已有的计算资源为基础，通过一系列整合后，以向 量部件的形式出现。而相应的扩展指令集则以单指令多数据( s i n g l e i n s t r u c t i o nm u l t id a t a ) 的向量指令为主，我们将这些指令称作“s i m d 多媒 体扩展指令”，简称“s i m d 指令”，同时，我们称这些多媒体扩展部件为s i m d 部 件。 目前，程序员只能通过编译器有限的支持来使用各种s i m d 指令，例如通过 嵌入汇编代码，或者使用编译器提供的内部函数( i n t r i n s i cf u n c t i o n ) 等手段在 代码中显式地使用s i m d 部件的指定计算功能。这些手段的使用要求程序员深入 了解s i m d 部件的体系结构，并且具备基本的向量化程序开发能力，大大提高了 多媒体程序开发的难度。一方面，由于各种处理器中集成的s i m d 部件及相关的 s i m d 指令各不相同，针对不同s i m d 部件开发的代码也不完全相同，从而导致了 代码的可重用程度较低。为了降低开发的难度，提高代码的可重用程度，我们必 须加强编译器对s i m d 扩展指令集的支持，使之能够利用s i m d 指令自动优化高级 语言编写的多媒体代码，编译器的这功能被称作s i m d 编译优化。 虽然，s i m d 编译优化技术隶属于向量化技术，然而，由于通用处理器中集成 的多媒体部件与传统的向量处理器之间存在着显著的差异，致使传统的向量化技 术无法被简单地移植于s i m d 编译优化中。迄今为止，只有少数商业编译器( 如 i c c 8 0 ) 能够对个别多媒体程序实施有效地s i m d 优化。而在学术界，针对s i m d 编译的研究往往过于理想化，而无法提高真实多媒体应用的性能。 本文阐述了将传统的向量化方法运用于s i m d 编译优化中的可能性与潜在的 障碍。并以此为基础，展开了s i m d 编译优化技术的研究，提出了多项能够显著 提高代码性能的编译优化技术。并以开放源代码( o p e ns o u r c e ) 编译器g c c 3 5 ， 以及并行编译平台a g g a s s i z 为基础实现了s i m d 优化编译的原型系统。其中，主 要的工作与创新包括： 1 详细研究了当前常见的多媒体应用的核心代码以及流行的s i m d 部件的 体系结构，指出了s i m d 多媒体编译优化技术与传统向量化方法的共同点 s i m d 编译优化方法研究 与重要区别。 2 针对向量化技术中常用的位宽分析无法适应s i m d 编译的需求，提出了基 于双向数据流分析的有效位分析方法，为s i m d 编译优化控制数据宽度、 提高并行度提供了必要的分析基础。 3 由于s i m d 微处理器体系结构的多媒体扩展与高级语言中的整数扩展规则 有不协调之处，严重影响了程序的执行效率。为此，我们提出溢出控制 方法，分别在饱和计算模式和封闭计算模式上解决了这一问题。 4 我们针对s i m d 扩展，解决了一阶线性递归饱和计算的向量化问题，避免 了在向量部件与串行部件之间交换数组，提高了计算效率。此外我们还 提出了周期常量的识别以及变化周期的求解方法，对存在周期常量的多 媒体应用程序扩大了可向量化范围。 5 以6 c c 3 5 与h g g a s s i z 编译系统为基础实现了两个编译原型系统，并利 用这两个原型系统对本文提出的分析与优化技术进行了正确性验证与优 化效果分析。 综合来说，本文以提高s i m d 多媒体编译优化能力为出发点，对其中若干 关键技术进行深入研究，着重讨论了如何提高分析精度以适应s i m d 编译需 求，以及如何在饱和模式下开发潜在并行性的方法等问题。并通过实验验证 了研究成果的正确性与有效性。 关键词：多媒体应用，单指令多数据指令集，s i m d 编译优化 中图分类号：t p 3 1 4 s i m d 编译优化方法研究 a b s t r a c t s i n c em u l t i m e d i ah a sb e c o m ead o m i n a t i n gc o m p u t i n gf i e l d ，t om e e ts u c hat r e n d ， a l m o s ta l lg e n e r a lp u r p o s e dp r o c e s s o rv e n d e r sh a v ei n t e g r a t e dm u l t i m e d i ae x t e n s i o n s ( m m 勘t ot h e i rp r o c e s s o r s d u et ot h ep o t e n t i a lp a r a l l e l i s ma n dt h el o wc a c u l a t i v e p r e c i s i o nr e q u i r e m e n to fm u l t i m e d i aa p p l i c a t i o n sm o s tm m ea r ei m p l e m e n t e dw i t h s i n g l ei n s t r u c t i o nm u l t id a t ai n s t r u c t i o ns e t s c u r r e n t l y , p r o g r a m m e r sa r em a i n l yr e s t r i c t e dt ou s i n ga s s e m b e rt ou t i l i z et h e s e m m e sw i t hi n l i n i n ga s s e m b l yc o d e so ri n t r i n s i cf u n c t i o n s w i t ht h e s em e t h o d s t h e d e v e l o p m e n tb e c o m ee x t r e m e l yi n e f f i c i e n ta n dt h ec o d ew o u l db eh a r dt ob e t r a n s p l a n t e db e t w e e nd i f f e r e n tp l a t f o r m s a na l t e r n a t i v ew a yi st om a k ec o m p i l e r a u t o m a t i c a l l yg e n e r a t es i m di n s t r u c t i o n sf r o mt h ec o d eo fs t a n d a r dh i g hl e v e l p r o g r a m m i n gl a n g u a g e s a l t h o u g hs i m do p t i m i z a t i o ni sap a r to fv e c t o r i z a t i o n ，t h et r a d i t i o n a l v e c t o r i z a t i o nt e c h n i q u ec o u l dn o tb es i m p l yt r a n s p l a n t e dt os i m do p t i m i z a t i o nd u et o t h ed i f f e r e n c e sb e t w e e nv e c t o rp r o c e s s o ra n ds i m da r c h i t e c t u r e c u r r e n t l y , t h e r ei s o n l yf e wc o m p i l e r sc o u l ds p e e d u ps o m ei n d i v i d u a lm u l t i m e d i aa p p l i c a t i o n s b a s e do nt h ed e e ps t u d yt ot h es i m da r c h i t e c t u r ea n dw i d e l ya n a l y s i st ot h e m u l t i m e d i aw o r k l o a d w ec a r r i e do nas e r i e sr e s e a r c ht od e v e l o pe f f i c i e n ts i m d o p t i m i z a t i o nt e c h n i q u e s ，a n dt o f i n do u ts o m eu s e f u lt e c h n i q u e si n t h i sa r e a m e a n w h i l e ，w ei m p l e m e n t e dt h e s et e c h n i q u e sw i t ho p e ns o u r c ec o m p i l e rg e e 3 5a n d p a r a l l e l i z a t i o nr e s e a r c hp l a t f o r ma g g a s s i za sw e l l 力j ew o r ko ft h i sd i s s e r t a t i o n i n c l u d e s ： 1 t h i sd i s s e r t a t i o n t h o m u g h l yi n v e s t i g a t e st h ep r e s e n tr e s e a r c h o ns i m d a r c h i t e c t u r e ，m u l t i m e d i aw o r k l o a d a n ds i m dc o m p i l a t i o nt e c h n i q u e s o n e c o n c l u s i o ni st h a tt h e r ea r eo b v i o u s g a p sb e t w e e ns i m dc o m p i l a t i o n t e c h n i q u ea n dt r a d i t i o n a lv e c t o r i z a t i o nt e c h n i q u e s 2 t om e e tt h er e q u i r e m e n to fs i m dc o m p i l e lw ei n t r o d u c e d v a l i db i t s a n a l y s i s ”，ad u a ld i r e c td a t af l o wa n a l y s i s ，a st h eb a s i ca n a l y s i sf o rf u r t h e r o p t i m i z a t i o n s ，t oc o n t r o lt h eb a n d w i d t ha n de n h a n c et h ep a r a l l e l i s m 8 ! ! 坚里塑堡垡些互堡堕塑 3 s i n c et h e r ea r es t r o n gc o n f l i c t sb e t w e e nt h ep a c ka r i t h m e t i c o fs i m d a r c h i t e c t u r ea n di n t e g e rp r o m o t i o nr u l eo fp r o g r a m m i n gl a n g u a g es t a n d a r d ， w ei n t r o d u c e dt h eo v e r f l o wc o n t r o l l e ds i m da r i t h m e t i ct oo p t i m i z et h e r e l a t e dc o d e 4 w es u c c e s s f u l l yv e c t o r i z et h el i n e a rr e c u r s i v ea r i t h m e t i ci ns a t u r a t e dm o d et o a v o i de x c h a n g i n gt h ed a t ab e t w e e ns e r i a lc o m p o n e n t sa n ds i m dc o m p o n e n t s s ot h a tw ec a ne n h a n c et h ep e r f o r m a n c eo fr e l a t e dc o d e m e a n w h i l e ，w e p r o p o s e dt h em e t h o dh o w t od i s c o v e rc y c - c o n s t a n t ，w i t ht h i sm e t h o dm o r e p o t e n t i a lp a r a l l e l i s ma r cd e v e l o p e d 5 ，w ea l s oi m p l e m e n t e dt w op r o t o t y p es y s t e mw i t ho p e ns o u r c ec o m p i l e r g e e 3 5a n dp a r a l l e l i z a t i o nr e s e a r c hp l a t f o r ma g g a s s i z ，a n dv e r i f i e dt h e c o l t e c t n e s sf o rt h es i m do p t i m i z a t i o nt e c h n i q u e sa n dm e a s u r e t h e p e r f o r m a n c ei m p r o v e m e n ta s w e l l c o n c l u s i v e l y , t oe n h a n c et h ec a p a c i t yo fs i m do p t i m i z a t i o nw ed i s c u s s e d s e v e r a lc r i t i c a lt e c h n i q u e s s u c ha sh o wt op e r f o r m eh i g h l ya c c u r a t e l yd a t ab i t w i d t ha n a l y s i sa n dh o wt od e v e l o pp o t e n t i a lp a r a l l e l i s mi ns a t u r a t i o na r i t h m e t i c m o d e o nt h eo t h e rh a n d ，w ev e r i f i e dt h ec o r r e c t n e s s a n da n a l y z e dt h e p e r f o r m a n c ei m p r o v e m e n tf o rt h et e c h n i q u e s k e yw o r d ：m u k i m e d i aa p p l i c a t i o n ，s i n g l e i n s t r u c t i o nm u l t id a t a i n s t r u c t i o ns e t ，s i m do p t i m i z a t i o n 9 s i m d 编译优化方法研究 1 1 多媒体应用 第一章引言 上世纪九十年代以来，计算机世界发生了革命性的变化，这一变化主要体现 在：计算机与其使用者之间的交互方式发生了巨大的改变，人与计算机之间的交 流不再仅仅局限于简单的键盘字符输入和屏幕字符输出。扫描仪、摄像头、声卡、 麦克风、音响设备、3 d 输出设备、游戏操纵杆等多媒体输入输出设备的出现使 得人机之间的交流手段变得越来越丰富多彩。随着这些设备在计算机系统中被广 泛而深入的使用，以通用处理器为核心的多媒体应用逐渐占据了个人电脑应用中 的统治地位。在这些多媒体应用中，作为计算核心的处理器往往承担了编码、解 码、压缩、解压、解释、增强与渲染等高强度的计算任务 6 0 ，而这些计算又往 往具备以下主要特征 2 1 ： 数据量极大 对计算的实时性要求较高 计算存在高度可并行性 计算密集度高 对计算精度要求较低( 以8 位或1 6 位整数计算为主) 对输入输出的带宽需求较高 多项计算任务同步进行( 如音频与视频计算的同步进行) 另一方面，得益于互联网络的发展，多媒体应用与网络应用相互结合，使得 多媒体应用技术有了更迸步的发展。然而，随着多媒体技术的普及与发展，多 媒体应用对计算机系统的核心计算能力提出了越来越高的要求 5 3 ，5 4 。以网络 视频应用为例：网络视频应用将来自互联网的视频数据解码后再根据视频输出设 备的要求重新编码，并将编码后的数据输出到视频设备。网络视频的使用者总是 希望能够获得清晰而连贯的收视效果，这就要求我们提高视频分辨率使图像变得 更清晰，并提高单位时间内输出图像的帧数来保证视觉的连贯性。但是，分辨率 每提高一倍，所需要处理的数据量将增加四倍，计算机系统处理每一帧图像数据 所需要的时间也相应延长为原先的四倍，同时单位时间内能够输出图像的帧数则 降为原先的四分之一。这样，提高图像分辨率与提高单位时间内输出图像的帧数 便成为了一对矛盾。所幸的是，由于视觉存在暂留现象，因此在视频播放的过程 s i m d 编译优化方法研究 中，我们只要保证每秒有二十四帧以上的图像被输出就可以保证收视者能看到足 够连贯的图像。所以为了提供优质的视频服务，我们需要提高应用中编解码的效 率。而提高编解码效率的方法有两种，其一为提高处理器的计算能力，其二为降 低编解码方法的复杂度。但是，由于网络视频应用的数据来自于互联网络，因而 网络传输的效率便成为了应用的另一个瓶颈。因为，如果互联网络无法在单位时 间内提供足够的数据量，则收视者一样无法获得连贯的收视效果。因此，为了提 高网络传输的效率，我们往往将数据进行高密度压缩，而高密度压缩的代价则是 降低编解码的效率。由于种种牵制，使得提高计算机系统的核心计算能力成为了 提高多媒体应用的效果唯一选择。 表一1 一lb m w 中的测试程序及核心代码的计算精度要求 测试程序应用领域 核心代码计算精度要求 视频压缩解压缩 电子游戏 三维渲染 音频压缩解压缩 语音压缩解压缩 图像压缩解压缩 视线连续追踪 图像压缩解压缩 音乐渲染 音频解码 语音合成 音频编码 早期的计算机系统中往往采用专用的d s p 芯片来提高系统在多媒体应用中的 性能 3 5 ，然而随着多媒体应用的普及，寻求低成本的解决方案就变得异常迫切。 另一方面，作为系统计算核心，通用处理器的计算能力越来越强大，但是，在实 际应用中，多媒体程序却并没有充分利用通用处理器所提供的计算能力。这是因 为，多数多媒体应用程序的核心代码由8 位或者1 6 位的整数计算所构成，而通 用处理器所提供的却是3 2 位甚至6 4 位计算能力。表- 1 - 1 给出了伯克利大学研 究开发的多媒体应用测试包b e r k e l e ym u l t i m e d i aw o r k l o a d ( 简称b m w ) 中所有 测试程序的应用领域以及计算精度需求 8 2 。在全部十二个测试程序中，有三个 测试程序的核心代码为8 位整数计算，五个测试程序的核心代码为1 6 位整数计 嘶嘶一一一嗍麟一哪一脚一一一| s i m d 编译优化方法研究 算，而在其余四个测试程序中，有两个测试程序的核心代码为单精度浮点计算， 两个测试程序的核心代码为双精度浮点计算。 ?整数扩展7 妙 整数扩展。；妙 | | | | = = = ”渊麟 上土上 3 2 雠粘辩 上 lj h l l l l , i i川黼 结果 图- 1 - 18 位整数运算在3 2 位处理器上的实现 如图- 1 - 1 所示，目前常见的3 2 位通用处理器在实现8 位整数计算时，8 位 操作数首先被扩展至3 2 位，然后进行3 2 位计算，最后保留3 2 位计算结果的低 8 位最终的计算结果。在计算过程中处理器的高位计算能力完全被浪费，处理器 的利用率只有四分之一。而多媒体程序的计算核心部分恰恰以8 位或者1 6 位计 算为主，在这种情况下通用处理器的低利用率与多媒体计算的高密度形成了鲜明 的反差。为了提高其性能，通用处理器有必要提高多媒体应用中的利用率。 1 2 s i m d 多媒体扩展基于寄存器的向量化计算 在1 1 中我们提到：目前，通用处理器的计算能力已经能够满足了3 2 位甚 至6 4 位精度要求，然而，多媒体应用往往只有8 位或1 6 位的计算精度需求，通 用处理器的计算能力在多媒体应用中的利用率很低。为了提高在多媒体应用中的 性能表现，通用处理器必须提高其计算能力的利用率。 另一方面，多媒体应用的核心代码往往有着高度的可并行性 5 4 。通过并行 计算充分利用处理器现有的计算能力可以帮助多媒体应用提高其核心代码的计 算效率，并进一步提高多媒体应用的性能。因此，多数通用处理器都引入了s i m d 多媒体扩展指令集。这扩展指令集中的指令将寄存器按8 位或1 6 位划分成若 s i m d 编译优化方法研究 干个单元，对于这些指令来说，参与计算的寄存器所存放的不再是标量操作数， 而是向量操作数，指令所实现的也是向量计算而非标量计算。由于s i m d 扩展对 多媒体应用核心代码的性能提高有着显著的帮助，因此部分通用处理器还为这一 扩展提供了专用的寄存器，同时还引入了向量化的浮点计算。如i n t e l 的s i m d 多媒体扩展s s e s s e 2 s s e 3 就使用了专用的1 2 8 位x 姗寄存器。这一s i m d 扩展 能够同时实现十六个8 位整数，八个1 6 位整数，四个3 2 位整数，四个单精度浮 点数或者两个双精度浮点数计算 3 6 ，3 7 ，3 8 。 图一i 一2i n t e ls i m d 多媒体扩展 除了基本的向量计算外，s i m d 扩展往往还根据多媒体应用的特征增加一些如 乘加，饱和计算这样的复合指令。这些指令能够次实现需要通过多条基本运算 指令组合才能实现的功能。例如，十六位的乘加指令就实现了图一卜3 所示的计 算功能： 源寄存器x源寄存器y 图一1 3s i m d 多媒体扩展中的乘加指令 十六位的乘加指令将3 2 位的源寄存器x ，y 分别用于存放一组由两个1 6 位 s i m d 编译优化方法研究 整数组成的向量操作数，我们将位于x 寄存器低位的向量元素记为x 。，位于x 寄 存器高位的向量元素记作x 。，将位于y 寄存器低位的向量元素记为y 。，位于y 寄 存器高位的向量元素记作y ，。乘加指令的计算结果为x 。y o 十x ，y ，的3 2 位计算 结果。这类运算常常出现在视频，以及图像数据的编解码函数中，乘加指令通过 加法与乘法的复合，能够进一步提高相关代码的效率，进而提高视频和图像多媒 体应用的性能。 除了乘加指令外，饱和计算指令也是s i m d 多媒体扩展中重要的复合指令。 代码一卜l u n s i g n e dq h a r a ，b ，c j i f ( a + b ) 2 5 5 c = 2 5 5 ； e l s e i f a + b ) s ，来表示。 代码- 2 3 ： s ，：a ；b + c s ，：d = a + 2 s 3 ：a 。e + f 除了上述三种数据依赖以外，在构造数据依赖图时，我们还需要考虑控制流 对数据依赖图的影响。在代码- 2 - 4 中，语句s 。，s ：，s 。之间存在着依赖关系： s l - - s 2 s 1 - 9 s 3 2 0 s i m d 编译优化方法研究 代码一2 4 ： s，：a；b+c i fix=o)then s 2 ：a=0 s ，：d = a e n d i f 虽然，s ：对变量a 进行了赋值，而s 。对变量a 进行了引用。但是由于s ：与s 。 分别属于同一个条件结构中的两个不同分支，因此这两条语句的执行有着互斥 性，从而使得语句s 。中所引用的变量a 的值不可能来自于语句s ：。所以语句s ： 与语句s 。之间并不存在数据依赖关系。 然而由于代码的最终流程要在执行时才能最后确定，因此静态分析得到的数 据流只是保守地提供了数据间可能的依赖关系。 代码- 2 6 ： s ，：a = b + c c l ：i f ( x = 0 ) t h e n s 2 ： a = a + 2 e l l d i f s 3 ：d = a + 2 1 在代码一2 6 中，s 。与s 。分别对变量a 进行赋值，而在s ：与s 。中又分别引用 了变量a 。而语句s ：是否执行取决于变量x 的取值，当x 大于等于0 时s 。将被执 行，而当x 小于0 时s z 将不被执行。因此，根据x 的取值不同，我们得到以下两 种不同的依赖关系图。当x 大于等于0 时，由于s 。对变量a 重新赋值，因此s 。 与s a 之间的依赖关系被s ：与s 。之间的依赖关系所取代。而当x 小于0 时，因为， s z 不再被执行，因此所有与s ：有关的依赖关系也随之消失。 s i m d 编译优化方法研究 x 兰0 x 0 图一2 2 数据依赖关系图一b 然而x 的取值往往要等到程序执行时才能确定，因此虽然在s 。中变量a 的取 值只可能来自s 。和s ：中的某一句语句，但是编译器只能保守地计算所有可能的 依赖关系，从而构成如下依赖关系图。 图一2 3 数据依赖关系图一c 2 1 1 循环中的数据依赖关系 在循环中数据的依赖性分析不仅仅关注不同语句间数据依赖性，也关心同一 语句在不同迭代间，或不同语句在不同迭代间的数据依赖关系。为此我们用上标 来区分循环的不同迭代。以代码一2 7 为例，在这段循环代码中，s ，被执行了3 次，我们将它们分别记作s 1 ，s 。2 和s 3 ，而语句s ：则被执行了6 次，我们将它们 分别记作s 。“1 ，s 。1 2 ，s ：。，s ：2 一，s 。3 。，s 。3 2 ( 用于标识外层循环不同迭代的上标在 前，用于标识内层循环不同迭代的上标在后) 。这样，我们就可以将循环迭代看 成是笛卡儿坐标系上不同的点，从而得到不同语句在不同迭代间执行次序关系图 ( 图一2 4 ) ： s i m d 编译优化方法研究 代码一2 7 ： d oi = 1 ，3 s l ： a ( i ) = b ( i ) d oj = 1 ，2 s 2 ：c i ，j ) = a ( i ) 4 - b ( j e n d d o 图一2 4 描绘了循环的迭代空间，而虚线箭头则指明了循环各迭代中各条语句 执行的先后次序。在循环的迭代空间上分析各条语句关于数组变量的数据依赖性 则需要对数组的下标表达式进行分析。 s 1 1 2 1 ”，s 2 -、 ，j ； f 、s 1 2 s 1 2 ，_ s 1 2 - ， 一 j ； i 、声1 3，s 1 3 ，s 1 3 2 图一2 4 迭代问语句执行次序 以代码一2 8 中的循环为例，在这段循环代码中，语句s 。对数组元素a ( i ) 进行 了赋值，而在同一个循环迭代中语句s ：又引用了该数组元素，因此语句s ：依赖 于语句s 。而又因为这样的依赖关系发生在同一个循环迭代内，所以我们将这种 依赖关系称作迭代内的真相关，用s 专：s 。来表示。 代码- 2 - 8 ： d oi = 2 ，n s l ：a ( i ) = b ( i ) + c ( i s 2 ：d ( i ) = a ( i ) e n d d o 我们进一步考察代码一2 9 中的循环 s i m d 编译优化方法研究 代码一2 9 ： d oi 每2 n s l ：a ( i ) = b ( i ) + c ( i s 2 ：d ( i ) 一a ( i i ) e n d d o 在这段循环代码中，s 。与s ：之间仍然存在着数据依赖性。在第i 次循环迭代 中语句s 。1 对数组元素a ( i ) 赋值，而在后一循环迭代中语句s ：”1 引用了该数组元 素。因此s 。”1 倚赖于s 。1 ，而因为这一依赖关系是第i + 1 次循环迭代中的s ：”1 依赖 于第i 次循环迭代中的s 。1 ，所以我们称之为跨迭代的真相关，并用s 。s ：来表 示。 代码- 2 - 1 0 ： d oi = 2 ，n s 1 ：a ( i ) = b ( i ) + c ( i s 2 ：d ( i ) = a ( i + i ) e n dd o 此外在代码一2 1 0 中，第i 次循环迭代中的s ：1 所引用的数组元素a ( i + 1 ) 将在 第i + 1 次循环迭代中被语句s ，”重新赋值。因此在s ”1 与s ：之间存在着反相关， 我们用s o 专。s ：来表示这种跨迭代的反相关。 在这里“= ”和“ ”被用来标示数据依赖在循环的迭代空间中的方向，因此 被称为数据的相关方向。在嵌套循环中，数据依赖关系在每层循环上都有一个相 关方向，这些相关方向组成了一个相关方向向量。例如在代码一2 1 1 中： 代码一2 一1 1 ： d oi = 1 ，n d oj = 2 ，n s 1 ： a ( i ，j ) s 2 ：c ( i ，j ) s3：d(i，j) e n dd o e n dd o j j l i + b + d， h 姐 a a 0 j l = = s i m d 编译优化方法研究 s 。，s 。与s 。之间的依赖关系为 s l sl s l s 2 2 1 2 依赖关系的g c d 分析方法 在实际应用中，大部分数组引用的下标常常以c i + k 的形式出现，其中c 与k 为常数。对于这种形式的数组访问我们可以利用求取最大公因子方法来检查 两个数组引用是否可能指向同一内存空间，从而判断两次引用之间是否存在数据 依赖。以代码一2 一1 2 为例： 代码- 2 - 1 2 d oi = l ，u s 1 ：a ( c + i + j ) = s 2 ： = a ( d + i + k e n d d o 在这段代码中，c ，d ，j ，k 为常数，为了判断s 。与s ：是否会因为数组a 的 引用产生相关性。我们首先计算常数c 与d 的最大公因子，如果c 与d 的最大公 因子不能整除j - k ，则无论循环变量i 的取值如何，下标表达式c i + j 与d * i + k 的 取值永远不会相等。从而在语句s 。与语句s ：不会引用数组a 中同一个数组元素， 即s 与s ：之间不存在依赖关系。反之，如果c 与d 的最大公因子能够整除j - k 则语句s 与语句s ：之间可能存在依赖关系。我们将这一方法应用于代码一2 一1 3 中 的循环： 代码一2 1 3 d oi = l ，u s 1 ：a ( 2 + i ) = s 2 ： = a ( 2 + i + 1 e n dd o 首先，2 与2 的最大公因子为2 ，又因为2 无法整除l ，所以a ( 2 i ) 与a ( 2 i + i ) s i m d 编译优化方法研究 不会引用同一个数组元素，因此s 。与s 。之间不存在依赖关系。实际上s 。所赋值 的是数组a 中的偶数元素，而s 。所引用的则是数组a 中的奇数元素，s 。中所引 用的数组元素并不是在s ；中被赋值的数组元素，因此s 。与s ：之间不存在数据依 赖关系。 代码一2 1 4 ： d oi = 1 ，1 0 s 1 s 2 a ( 19 + i + 3 ) = = a f 2 + i + 2 1 g c d 方法在整数范围内检测两个数组引用的下标是否可能取相等的值，从而 判断相关语句是否存在数据依赖。此外数组引用的下标的取值范围还会受到循环 变量上下界的限制。例如在代码一2 1 4 中，根据g c d 测试方法1 9 与2 的最大公 因子为1 ，它能够整除1 8 ，因此在整数范围内这a ( 1 9 i + 3 ) 与a ( 2 i + 2 1 ) 可能是 同一个数组元素。然而由于循环变量i 的下限为1 、上限为1 0 ，在进行依赖性分 析的时候只需要考虑在这一范围内a ( 1 9 i + 3 ) 与a ( 2 i + 2 1 ) 是否可能为同一数组 元素。经过计算1 9 i + 3 的取值范围为 2 1 ，1 9 3 而2 i + 2 1 的取值范围为 2 3 ，4 1 ， 他们的交集是 2 3 ，4 1 。因此只有在这一范围内，这两处对数组a 的引用可能指 向同一个数组元素。而当i 等于2 时，下标1 9 i + 3 等于4 1 是符合这一条件的。 另一方面当i 等于1 0 时，下标2 i + 2 1 的值为4 1 。这两次数组引用所引用的是 数组a 的同一个元素，因而s 。2 专s ：”。然而当我们将上面的循环代码做如下改动： 代码一2 一1 5 ： d oi = 2 ，9 s 1 s 2 a ( 1 9 + i + 3 ) = = a f 2 + i + 2 1 在这段代码中我们将循环变量的上下界修改为2 和9 ，此时下标1 9 i + 3 的取 值范围为 4 1 ，1 7 4 而2 i + 2 1 的取值范围为 2 5 ，3 9 。这两个取值范围的交集为 空，因此这两个对数组a 的引用不会指向同一个数组元素，s 。与s ：之间不存在 数据依赖性。依据这一算法设计的依赖关系分析方法称为b e n e r j e e 测试 8 。 s i m d 编译优化方法研究 2 2 向量化代码生成 代码一2 1 6 ： d oi = 1 ，n sl ： a ( i ) = b ( i ) s2 ： c ( i ) = a ( i ) + b ( 1 s3 ： e ( i ) = c ( i + 1 ) e n dd o 9 害 图一2 5 迭代间语句执行次序 在这个数据依赖图中没有环，从而只需要交换s ：与s 。的位置就可以保证反相 关s 。o 专s ：的执行次序，由此得到如下向量代码： 代码一2 1 7 ： s ，： s1 ： s2 ： 而代码一2 一1 8 的数据依赖关系则构成了环： nlb u + 町 叶 m 1 2 1 b c a = j | = n n n1 1 1 a e c s i m d 编译优化方法研究 代码一2 1 8 ： d oi = 2 ，n s1 ： a ( i ) = b ( i ) s2 ： c ( i ) = a ( 1 1 + b i 一1 s3 ： e ( i ) = c ( i + 1 ) s4 ： b ( i ) = c ( i ) + 2 e n dd o 在代码一2 一1 8 中存在着如下数据依赖关系： s l 。s 2 s 2 专，s _ s s 2 s 10 9 。s4 s3o ( s 2 图一2 6 是这些数据依赖关系构成的数据依赖图 图一2 6 含有环的数据依赖图 在这张图中s 。中所引用的c ( i ) 在同一循环迭代的s 。中被赋值，而s 。又引用 了前一迭代中由s 。所赋值的b ( i ) ，使得依赖关系s 。专s 。和依赖关系s 。专s ：构成了 环。如果在循环的数据依赖关系图中存在环，在生成向量化代码时必须找到图中 所有的环，在环中的所有语句都不能生成相应的向量代码。如果不能通过代码的 等价变形来消除数据依赖关系图中的环，则这些代码必须被串行执行。虽然在环 内的语句必须被串行执行，但环外的语句依然可以生成相应的向量代码。因而上 面这段循环代码依然可以生成如下向量化代码： s i m d 编译优化方法研究 代码一2 1 9 ： s1 ：a ( 2 ：n ) = b 2 ：n ) s3 ：e ( 2 ：n ) = c ( 3 ：n + i ) d oi = 2 ，n s2 ： c ( i ) = a ( i ) + b ( i 一1 s4 ：b ( i ) = c ( i ) + 2 e n d d o 2 3 反相关与输出相关的消除 形成输出相关和反相关的原因并不是在语句间有真正的数据传递关系，而只 是因为数据间使用了相同的存储空间。因此，通过变量换名或者数据复制即可消 除这些数据依赖关系。 通过引入新变量名，取代旧变量名我们可以消除输出相关和反相关，这一方 法被称作变量换名。例如在代码一2 2 0 中： 代码一2 2 0 ： s ，：a = b + c s 2 ：d = a + l s ，：a = d + e s ：f = a 一1 变量a 被两次赋值，从而形成了语句s 与s 。之间的输出相关，以及s ：与s 。之 间的反相关。只需要将s ，