（计算机软件与理论专业论文）simd自动优化方法.pdf

摘要 摘要 近年来，随着多媒体应用的发展，多媒体加速技术的重要性日益突出。使用 s i m d 技术可以显著地提高多媒体程序的性能。然而由于缺乏编译器的支持，对 于多媒体开发人员来说使用s i m d 指令是相当困难的一件事。他们不得不使用嵌 入式汇编或者是i n t r i n s i c 函数才能利用这些指令。因此，自动化s i m d 编译器 的研究就交得至关重要。 本文提出了两种s i m d 自动优化方法，基于向量化的方法和基于模式匹配的 方法。这两种方法都可以自动生成s i m d 指令，对某些多媒体程序取得比较好的 效果。在本文中，我们还对两种方法进行了评估和比较。 基于向量化的方法原于传统的向量化方法，可以实现对循环中单条语句的 s i m b 优化。但这种优化方法的优化效率不是很高。针对这一点我们又提出了基 于模式匹配的方法。该方法可以依照事先定义好的模式对源程序中的一条或几条 语句进行匹配，进而自动生成s i m d 指令。在n e t b u r s to p t i m i z i n gc o m p i l e r ( n o c ) 项目和a g a s s i z 项目中，我们分别实现了上述两种方法。 关键词s i m d ，自动优化，多媒体应用程序，向量化，模式匹配 a b s t r a c t ab s t r a c t i n c r e a s i n g f o c u so nm u l t i m e d i a a p p l i c a t i o n s h a s p r o m p t e d t h ea d d i t i o no f m u l t i m e d i ae x t e n s i o n st om o s te x i s t i n gg e n e r a l p u r p o s em i c r o p r o c e s s o r s b yt a k i n g a d v a n t a g eo f t h e f u l lw i d t ho f t h e p r o c e s s o r sd a t a p a t h ，t h ei n s t r u c t i o n sa l l o wm u l t i p l e s m a l ld a t ai t e m st ob ep r o c e s s e ds i m u l t a n e o u s l yb yo n ei n s t r u c t i o n t h e s es h o r t s i n g l e i n s t r u c t i o ns t r e a m s ，m u l t i p l e d a t as t r e a m ( s i m d ) s t y l e i n s t r u c t i o n so p e r a t eo d p a c k e d d a t at y p e s ，w i d eo p e r a n d sw h i c ha r ec o m p o s e do fs m a l l e ri n d i v i d u a le l e m e n t s u n f o r t u n a t e l y , t h el a c ko fc o m p i l e rs u p p o r th a sh i n d e r e dt h em u l t i m e d i aa p p l i c a t i o n d e v d o p e r f r o me x p l o i t i n gs i m d t e c h n i q u e s t h i sp a p e ri n v e s t i g a t e st h ep o t e n t i a lf o ra u t o m a t i cs i m d t r a n s f o r m a t i o n f o rt h i s p u r p o s et w om e t h o d s ，v e c t o r i z i n gb a s e da n dp a t t e r nm a t c h i n gb a s e dt r a n s f o r m a t i o n m e t h o d s ，a r eu s e d t h ep u r p o s e o ft h i sa r t i c l e i st os h o wt h e p o s s i b i l i t i e s a n d d e f i c i e n c i e so ft h e s et w om e t h o d s t h ee x p e r i m e n t ss h o w t h a tp a t t e r nm a t c h i n gb a s e d t r a n s f o r m a t i o nm e t h o di se f f i c i e n ta n dp r a c t i c a lf o rt h em u l t i m e d i aa p p l i c a t i o n k e y w o r ds i m d ， a u t o m a t i c t r a n s f o r m a t i o n ， m u l t i m e d i a a p p l i c a t i o n ， v e c t o r i z a t i o n ，p a t t e r nm a t c h i n g 第一章引论 第一章引- v e 对多媒体应用程序的特点 在可预见的将来，多媒体处理将成为计算机领域主要的应用之- 1 1 。多 媒体处理主要是诸如图像，音频，视频和图片等多媒体数字信号的生成，编 码，解码，处理，显示和信息传递。在过去的几年中，多媒体应用得到了很大 的发展，但是这一领域真正的发展潜力在于像电信会议，远程教育和高质量 的多媒体频道这样的日常多媒体应用得到广泛的应用之后。 取得这种潜力的一个障碍是这些应用需要大量的计算。这些是因为多媒 体应用所采用的算法有着内在的计算集中性，具有时实性和需要在同一系统 中同步运行多个应用程序。例如，一个视频远程通讯系统需要同时运行多个 第一章引论 视频处理程序，如编码解码，音频处理和一个软件调制解调器。因此，当 前这种应用在普通处理器上每秒钟只能显示很少的帧数，而图像的大小也很 小。为了达到多媒体应用的这种大计算量的要求，现在的系统使用d s p 处理 器作为普通处理器的协处理器对特定的多媒体应用进行加速。但是，使用普 通处理器可以获得很多好处，例如编程更简易，节约成本和易于升级。这些 好处使得我们更倾向于对多媒体应用使用普通处理器。正是因为这一点，大 多数高性能的普通处理器引入了s i m d 扩展指令集。 现在s i m d 技术主要应用于3 d 图形，语音识别，图像处理，科学计算以 及其他的多媒体应用领域。这些应用程序都拥有如下的特点： 固有的并行性 规则的和连续的内存访问模式 对数据进行递归地操作 无数据相关的控制流 大量的计算集中 一般来说，可以获得比较大加速的程序都包含一些简单的循环。在这些 循环中包含有对连续数组的操作。而这些循环的迭代集中了整个应用程序的 大部分执行时间。具有如上特点的应用程序一旦使用s i i d d 技术进行加速可 以获得比较大的加速比。而现实应用中的多媒体程序恰恰具有以上的特点。 二、s i m d 技术的概述 提高处理器性能的一种方法就是并行地执行多条计算。其中能够使我们 获得并行性的一种方法就是使用单指令流多数据流技术( 即s i m d 技术) 。 第一章引论 图1 1 中阐述了一个典型的s i m d 计算。两组装配的四个数据单元x 1 ， x 2 ，x 3 ，x 4 ，和y 1 ，y 2 ，y 3 ，y 4 被并行地执行。每对数据单元x 1 和y l ，x 2 和y 2 ，x 3 和y 3 ，x 4 和y 4 都执行了相同的操作。得到的结果是装配好的四 个数据单元。 l x 4x 3x 2x l iy 4 y q y ： 丫4 $ e 争 x 4o p y 4x jo o y 3 x 2 y 2x io p v i 图1 - 1 典型的s i m d 操作 如图卜1 中所示s i m d 计算方式已经广泛地为微处理器供应商所采用。例 如，i n t e l 的m m x s s e s s e 2 系列，s u n 的v i s 和m o t o r o l a 的a l t i v e c 等。 下面我们简单介绍一下i n t e l 处理器中的s i m d 指令系列。在i a 3 2 中最初引 入的是m m x 技术。删x 可以使用一组6 4 一b i t 寄存器m m x 对装配的字节( b y t e ) ， 字( w o r d ) 和双字( d o u b l e w o r d ) 整数进行s i m d 操作。 奔腾i i i 处理器引入了s s e 系列扩展了最初的s i m d 计算模型m m x 。s s e 可 以处理4 个装配的单精度浮点数。操作数可以为内存单元或一组1 2 8 一b i t 寄 存器x m m 。s s e 也对m m x 进行了扩展。 奔腾进一步将s i m d 计算模型扩展为s s e 2 系列。s s e 2 指令的操作数同 样为内存单元或x m m 寄存器。s s e 2 可以处理装配的双精度浮点数和1 2 8 一b i t 的整数。 鱼二至! 丝 i a 3 2 中完整的s i m d 扩展指令集( m i x ，s s e 和s s e 2 ) 使得程序员能够设 计算法对经过装配的6 4 b it 、1 2 8 一b i t 整数以及单精度和双精度浮点数进行 操作。 i n t e ls i m d 技术的总结 下面我们将对i a 一3 2 中的三组s i m d 技术j i l m x ，s s e 和s s e 2 进行总结。 m m x 技术 引入6 4 一b i tm m x 寄存器 引入对装配的字节，字和双字的整数的s i m d 操作 s s e 扩展 引入1 2 8 一b i tx m m 寄存器 引入1 2 8 一b i t 装配的四个单精度浮点数类型 引入数据预取指令 引入n o n t e m p o r a l 存储指令和其他c a c h e 及内存指令 加入额外的6 4 一b it s i m d 整数支持 s s e 2 扩展 加入j 2 8 一b i t 装配的2 个双精度浮点数类型 加入对1 2 8 - b i t 的1 6 个字节，8 个字，4 个双字和2 个四字整数的 s i m d 整数操作 加入对6 4 一h i t 整数操作数的s i l d 算术操作 加入新的和已存在的数据类型间的转换指令 扩展对数据s h u f f l e 的支持 扩展对c a c h e 和内存操作的支持 4 第一一章引论 关于s i m d 的详细内容参见参考文献 2 三、自动化s i m d 编译器的意义 尽管s i m d 技术有着广泛的应用前景，但是由于多媒体程序开发人员需要 使用嵌入式汇编或者是特殊的库函数编写程序，s i m d 技术只能被少数专、i p 的 程序员所使用。因此，自动化s i m d 编译器的研究就变得至关重要。 本文中提出了两种自动s i m d 优化的方案：基于向量化方法和基于模式识 别的方法。在下面的两章中，我们将详细阐述这两种方案的实现并对其进行 评价。 笫二章基于向量化的s i m d 自动优化方案 第二章基于向量化的si m d 自动 优化方案 一、向量化方法的可行性 一个c 向量化编译器如图2 1 所示。 一c 源程序 v e c t o r i z i n g s t a g e 图2 1 一个c 向量化编译器 s i m d 优化代码卜 第二章基于向量化的s i m d 自动优化方案 当一个c 源程序作为输入被编译器接受后，向量化编译器就会在向量化阶段， 尽可能地把程序中最内层循环变换为向量操作，然后由代码生成器为这些操作产 生向量化代码。r a n d ya 1 l e n ；阳k e nk e n n e d y 曾对向量计算机环境下的向量化并行 方法进行了大量的研究。他们在论文“a u t o m a t i ct r a n s l a t i o no ff o r t r a n p r o g r a m st ov e c t o rf o r m ” 3 中提出了比较成熟的向量化方法。本文中针对s i m d 优化而提出的向量化方法就是在r a n d ya 1l e n 和k e nk e n n e d y 的方法的基础上进行 了一定程度的改进。 虽然并行的粒度不同( s i m d 的并行粒度较小，属于指令级并行) ，s i _ i d 技术 同向量计算机一样都是在开发程序的并行性。从这一点上来讲，向量化方法是完 全适用于s i m d 技术的。另外，向量化方法主要针对的是内层循环，将其转化为 向量操作。而多媒体应用程序中拥有大量的循环，并且程序的执行时间绝大部分 是花在这些循环上的。图2 2 是对伯克利大学开发的多媒体应用工作集的源程序 行数和f o r 循环个数进行的统计。 第二章基于向量化的s i m d 自动优化方案 s o u r c ef o r n a m ed e s c r i p t i o n 1 1 n e s l o o p s a d p c mi m aa d p c ma u d i oc o m p r e s s i o n3 0 03 d j v u a t & ti w 4 4w a v e l e t i m a g ec o m p r e s s i o n 2 5 4 1 93 4 8 d o o mc l a s s i cf i r s tp e r s o ns h o o t e rv i d e og a m e 5 7 ，8 6 8 4 5 6 g h o s t s c r i p tp o s t s c r i p td o c u m e n tv i e w i n g r e n d e r i n g 2 4 8 ，3 6 3 1 2 2 6 g s m e u r o p e a ng s m0 6 1 0s p e e c hc o m p r e s s i o n5 ，4 7 3 7 6 j p e g d c tb a s e dl o s s y i m a g ec o m p r e s s i o n3 3 ，7 1 4 4 5 4 l a m em p e g 一1 l a y e ri i i ( m p 3 ) a u d i oe n c o d e r1 9 ，7 0 4 4 4 3 m e s ag e a r so p e n g l3 dr e n d e r i n ga p ic l o n e1 1 9 8 3 01 5 7 2 m e s am o r p h 3 d o p e n g l3 dr e n d e r i n ga p ie o n e 1 2 0 ，4 0 l 1 5 7 4 m e s ar e f l e c t o p e n g l3 dr e n d e r i n ga p ic l o n e1 1 9 ，8 8 3 1 5 6 6 m p e g 一2e n cm p e g 一2v i d e oe n c o d i n g 7 ，6 0 5 1 8 5 m p e 6 - 2d e cm p e g 一2v i d e od e c o d i n g 9 ，8 3 2 1 1 4 m p 9 1 2 3 m p e g 一1l a y e ri i i ( m p 3 ) a u d i od e c o d e r 7 ，7 9 0 6 0 p o v r a y p e r s i s t a n c eo fv i s i o nr a yt r a c e r 1 5 1 ，3 4 6 1 1 9 4 r a s t a s p e e c hr e c o g n i t i o n 2 4 ，5 8 9 1 1 4 r s y n t h k l a t ts p e e c hs y n t h e s i z e r 7 ，0 8 9 3 2 t i m i d i t y m i d im u s i cr e n d e r i n gw i t hg u si n s t r u m e n t s4 0 ，5 1 4 1 4 9 图2 2b e r k e l e y 多媒体工作集 从以上的数据统计来看，针对内层循环进行优化的向量化方法可以捕获较多 的循环进行优化，进而取得加速比。 基于上述的考虑，复旦大学并行处理研究所在自动s 埘d 编译器n e t b u r s t o p t i m i z i n g c o m p i l e r ( n o c ) 项目中采用了向量化方法，并且取得了一定的效果。 在下一节中，我们将详细阐述向量化s i m d 优化方法的框架。 第二章基于向量化的s 1 m d 自动优化方案 二、向量化s i m d 优化方法的过程 现在我们来描述一下在理想的情况下，一个普通的程序是如何转化为s i m d 代码的。我们首先讨论这一问题的一些重要的部分。假设我们的s i m d 优化编译 器面临如下的c 程序的输入： 弘r ( i = 0 ；i 1 0 0 ；i + + ) sk i = i ； f o r ( j = k j 3 0 1 ；j + + ) s 2 k = 舡+ l ； s 、“ ，】= “ 力+ 肼】； rv j + 3 】= v 刀+ w 刎； 我们目标是使用s i m d 指令对s ，和s 。进行优化。但是我们必须遵循一个前提 条件，这就是在s i m d 变换前后程序在语义上要一致。只有当s ，和s 。在循环中顺 序地执行和作为s i m d 技术优化后的指令序列来执行时在语义上不存在差别才能 进行优化。这样才能保证程序变换后的正确性。我们考虑一个稍微简单一些的例 子： 加r ( i = 0 ； 1 0 0 ；i + + ) x i 】= h f 】+ y 【f ； ) 第二章基于向量化的s i m d 自动优化方案 如果我们想把上面这条语句变换为如下s i m d 向量操作 扣r ( i = 0 ；i 1 0 0 ；i + = 4 ) ( x v = m m l o a d u p s ( x + i ) y v = 一m m l o a d u p s ( y + f ) ； x v = 一m m a d d p s ( x v ，y v ) ； 一m m s t o r e u p s ( x + i ，删) ； 我们必须保证这种变换不存在语义上的差别。试想一下，如果循环在一个迭 代中计算某个值，然后在以后的三个迭代中某一个使用了它，那么就不能达到语 义上一致了。看下面的例子： f o r ( i = o ；i 1 0 0 ；i + + ) x f + 1 = x i 十y i l ； ) 这段程序就不能被正确地优化为s i m d 指令。这是因为除第一个迭代以外， 每个迭代都使用了上一个迭代所计算的值。显然这种情况属于某种类型的相关。 我们称一个循环中的语句与自己产生相关的这种形式为自相关。为了区别上面的 这两种情况，s i m d 优化编译器必须进行测试来决定一条语句是否有自相关，既 一条语句是否使用了它在前面迭代中计算的值。关于相关性测试的内容我们会在 下一节中进行讨论。下面我们回到本节开始的那个例子上去，来看看整个优化过 程是怎样的。 第二章基于向量化的s i m d 自动优化方案 首先，我们来定义什么是一个标准化的循环。当一个循环的下界为o ，步长 为1 ，而且循环变量在循环体中不被赋值，我们就把它定义成为一个标准化的循 环。如果一个循环不是标准的循环，我们可以通过引入新的循环变量将其进行标 准化。在循环体中，每个对老的循环变量的引用都被替换为新的循环变量的表达 式。本节的例子引入新的循环变量后得到的结果如下： 如r ( i = o ；i 1 0 0 ；i + + ) 舡= i ： f o r ( j 。= o , j 3 0 0 ；j 。+ + ) 幻= 蔚+ 1 ： u u l + 1 】= u j + 1 1 + m 蜘； v 【，。+ 4 】= v j 。+ 1 】+ w 蔚】； ) 瓯j = 3 0 1 ； ) 我们注意到，现在新变量j 。成为内层循环的循环变量。一条新的赋值语句被 引入来定义原来的循环变量，。这种循环标准化的主要目的是尽可能地把数组下 标转化为循环变量的线性函数。为了达到这一目的，我们还要把循环体中的辅助 循环变量替换掉，例如上面程序中的舫。这种变化称为循环变量替换 4 。我们 的例子可以被转化成下面的形式： 第二章基于向量化的s i m d 自动优化方案 如r ( i = o ；i 1 0 0 ；i + + ) k i = f ： f o r ( j = o ；j 3 0 0 ；j 。+ + ) u i j + 1 1 = u j 1 + 1 】+ w 陋+ _ ，。】； v t j + 4 1 = v i i + 1 】+ w k i + j 。】； 肼= 女f + 3 0 0 ； j = 3 0 1 ； 这样我们就把循环体中对于肼的计算移除了，并且对舫的引用我们都用舸的 初值加上由循环迭代所引起的增量( j 。的函数表达式) 来替代。我们所采用的这 种方法是传统优化技术强度消弱的反向操作。 最后为相关性测试而做的变换是表达式合并，即将整数表达式和常数的代入 到数组下标中以达到简化下标的目的。这次所得到的结果是： f o r ( i = o ；i 1 0 0 ；i + + ) f o r ( j = 0 ；j 3 0 0 ；，+ + ) s“l ，+ 1 = “【，+ + 1 4 w 【j + ，】； 咒v _ ，。+ 4 】= v j + 1 + w i + j 肪= i + 3 0 0 ； 瓯j = 3 0 1 ； 第二章基于向量化的s 1 m d 自动优化方案 在这个例子中，移除了对k i 在外层循环的第一次赋值，在语句s ，s 。和s ；中 对k i 的引用为右值所替代。一旦下标表达式转换完毕，我们可以通过建立数据流 图对整个程序进行数据流分析。这张图可以被用作整个程序的常数传播和无用语 句的消除。存上面的程序中，假设船和，在以后的代码段中不再活跃，那么在这 段程序中对k i 和的赋值都可以被删除。 扣r ( i = 0 ；i 1 0 0 ；i + + ) 力r ( j 。= o ；j 。 3 0 0 ；j + + ) s “ ，。十1 】= “【，。+ 1 + w f + 。 ； 只v 【，十4 = v j + + 1 + w i + ，+ 在这一步中，我们所尝试的循环变换都是为了让数组下标变成更规范的形 式，即循环变量的线性函数。这种形式可以使褥我们能够应用更强大和精确的相 关性测试。一旦我们测定了语句间的相关性，我们就可以进行s i m d 代码生成了。 通过相关性信息，编译器可以判断程序中的语句会不会存在自相关。在上面的程 序中，s 不存在自相关，而只存在自相关。因此。s ，可以进行s i m d 优化而墨只 能顺序执行。 第二章基于向量化的s i m d 自动优化方案 如r ( i = 0 ；i 1 0 0 ；i + + ) f o r ( j 1 = o ；j 3 0 0 ；j 。+ = 4 ) “v = 一m m l o a d u p s ( u + j + 1 ) ； w v = 一m m l o a d u p s ( w + i + x “v = 一m m m u l p s ( u v ，w v ) ； 一晰一s t o r e u p s ( u + j + 1 ，“v x f o r ( j = o ；j 。 3 0 0 ；j + + ) rv 【+ 4 = v i i + 1 】+ w i + j + 】； 图2 3 给出了n o c 中s i m i ) 优化的整个过程。我们使用g c c 的p a r s e r 将输入 的c 源程序转化为作为中间表达形式的语法树。经过s i m d 向量化处理后，g c c 的后端可以根据变化后的语法树生成中间表达形式r t l 7 ，最终生成汇编代码。 s i m d 向量化处理包括三个步骤： a ) 循环预处理，即循环标准化及变换。 b ) 相关性测试，即建构语句间的相关图。 c ) s i m d 代码生成。对可能使用s i m d 指令的语句进行s i m d 变换。 第二章基于向量化的s i m d 自动优化方案 圉骘罔嗡阳 爵目 | 循环预处l【：，。l f 理和相关卜叫“掣譬。l | 性分析lj i 1 一一1 ，j 图2 3 在下面的两节中，我们将就( b ) ，( c ) 两项进行详细的讨论。 三、相关性分析 从上面一节的介绍中可以看出，向量变换的最大障碍是程序中存在的自相 关。如果一条语句同自身存在相关性，这条语句就不能直接进行s i m d 优化。因 此，相关性分析的主要任务在于揭示程序中所有的自相关。自相关分为两种：语 句直接同自己产生的直接自相关，和语句通过传递同自己产生的间接自相关。下 面的例子阐述了间接自相关： 第二章基于向量化的s 1 m d 自动优化方案 如r ( i = 0 ；i 1 0 0 ；i + + ) s t i _ n f + 6 【吐 s 2s i 】- s i + f 】； sd 【“1 】= 4 0 + 4 0 ； 虽然s ，s z 和s 并不直接与自己产生相关，但他们仍然通过传递产生了自 相关。为了能进一步揭示自相关产生的原因，我们先来研究一下语句间的相关性。 我们对于三种相关类型，流相关，反相关和输出相关，都要进行考虑。值得 注意的是，本文中所提到的相关性的含义与数据流分析中所遇到的相关性的含义 是不同的。本文中的相关性是指两条语句必须依照某种顺序来执行的这种关系， 而不是数据流分析中所指的为了一条语句能得到正确的值，另一条语句必须先出 现。三种类型的相关性都有一个共同点，即两条语句或者同一条语句的两次不同 的执行访问同一个内存位置。因此，三种类型的相关可以使用同样方法进行测试。 在下文的叙述中，我们只以流相关为例，但所有的概念和方法对其他两种相关同 样适用。 根据同循环的关系不同，语句的相关还可以分为：与循环无关的相关( 1 0 0 p i n d e p e n d e n td e p e n d e n c e ) 和跨循环的相关( 1 0 0 pc a r r i e dd e p e n d e n c e ) 。 与循环无关的相关( 1 0 0 pi n d e p e n d e n td e p e n d e n c e ) 是指一条语句在一 个循环迭代中存储一个内存位置，然后另一条语句在同一个迭代中读取 这个位置。在前面的例子中，& 与s 的相关就是这种类型的相关。 跨循环的相关( 1 0 0 pc a r r i e dd e p e n d e n c e ) 是指”条语句在某个循环迭 代中存储一个内存位置，然后在以后的循环迭代中读取这个位置。在前 面的例子中，s 与s 的相关就是这种类型的相关。 显然，如果只存在与循环无关相关，是绝不可能产生自相关的。只有当跨循 第二章基于向量化的s i m d 自动优化方案 环相关加入到相关传递链中时，才可能产生自相关。由此可见自相关同循环的关 系是非常密切的。假如我们让外层循环的循环变量保持不变，只看内层循环中的 语句，某些跨循环的相关就可能消失，进而由这些跨循环相关引起的自相关也消 失了。因此，对于多层嵌套循环来说，确定哪一层循环产生相关是非常重要的。 这样我们就可以从外层循环开始，一层层地剥离循环，找出更多的可向量化的语 句。下面我们来看看，我们是如何进行相关性测试的。 1 测试每两条语句间的相关性和最大相关深度 我们可以定义符号s l 万k 8 2 如果存在k 层上存在& 与s 的相关。相关深度是 s i m d 优化中关于相关性测试的又一重要概念，下面我们给出它的定义。我们说逆 与s 相关且相关深度为d ，如果存在k d 使得s 瓯。所有相关深度中最大的一 个称为最大相关深度。 经典的相关性测试方法有g c d 测试以及b a n e r j e e 测试。在“b a n e r j e e g c d 与b a n e r j e e b o u n d 联合数组相关性测试” 8 一文中介绍了一种比较高效和精确 的测试方法。根据 8 中所介绍的相关性测试方法，我们可以获得每两条语句问 的相关性和最大相关深度。在这一步我们要获得所有类型的相关，包括流相关， 反相关和输出相关。 第二_ = j 章基于向量化的s i m d 自动优化方案 2 构建相关关系图 有了上面的测试结果，我们就可以构筑相关关系图了。相关关系图中的结点 是语句，用圆圈来表示。如果两条语句问存在相关，那么代表他们的圆圈之间就 存在一条边，用箭头来表示，并且在边上注明最大相关深度。我们还是从一个例 子开始。 如r ( i = 0 ；i 1 0 0 ；i + + ) sx i - y i 】+ 1 0 ； f o r ( j = 0 ；j 1 0 0 ；，+ + ) &b j 】- a j ，】； f o r ( k = o ；k 1 ) ) c o n d i t i o n so o u t p u t d e c l 一m 1 2 8 $ m m ) c o d e ( s m m 。_ m m _ a v g _ e p u 8 ( v l ，v 2 ) 图3 5 墨三兰苎王鳖蔓坚望堕! ! 坚里鱼垫垡些查墨 s u m a b s u c h ar = 0 】 s s c a l a rs is + = $ s c a l a rs iv ： e l s e $ s c a l a rs 1s 一= s s c a l a rs lv p a t t e r nf # s t m t - - y , $ s c a l a r s i v = # v e c u q i a r l - # v e c u q i a r 2 ； i f ( $ s c a l a rs iv 3 2 7 6 7 0 ) $ s c a l a rh 1v = 3 2 7 6 7o ； e l s ei f ( o v e c s f s 1 构成了一个求p l i 和p l i + 1 平均 数的操作。 中的减法和、构成了一个求绝对值后再累加的操作。 第三章基于模式匹配的s i m d 自动优化方案 我们来看看代码匹配与变换引擎是如何使用模式对这段程序进行优化的。以 下是引擎匹配成功的三个模式： 1 # v e c 一1 6 u q i s a r r u q i a o $ s u b b 0 2 # v e c 一1 6 u q ij ( ( u n s i g n e d i n t ) ( $ v e c _ u q i _ v l + $ v e c u q i 啊v 2 + 1 ) 1 ) # s t m tj $ s c a l a r s i v = # v e c j j q la r l 一# v e c q i a t 2 i f ( $ s c a l a rs iv = o ) 3$scalars is + = $ s c a l a rs iv ： e l s e $ s c a l a rs i s - - = $ s c a l a r 。s iv ； 代码匹配与变换引擎将执行3 1 节中所述的五步进行优化。图3 7 中的程序 可经过图3 8 步骤产生图3 - 9 所示的结果。 第_ 兰章基于模式匹配的s i m d 自动优化方案 使用模式l 将p l i t ) 3 约q # v e c 。 使用模式1 将p l 【i + 1 】归约4 # v e c 。 上 使用模式1 将p 2 【i 】归约到w e c 。 、l 使用模式2 将( 群v e c + # v e c + 1 ) 1 归约到群v e c 。 上 使用模式3 将v = # v e c 一# v e c ： i f ( v = 0 ) e l s e 归约到# s t m t 图3 - 8 山 第三章基于模式匹配的s i m d 自动优化方案 r x m m l = 一m mi o a d u _ s i l 2 8 ( l - m 1 2 8 i 。) ( p 1 ) ) ， f i - 恃p l 位地址的1 6 一b y t e 的内存数据取到r x m m l 中 n ( m m 2 = j nm _ l o a d u s i l 2 b ( l _ m 1 2 8 i 士) ( p 1 + 1 ) ) r x m m 3 = m m i o a d u _ s i l 2 8 ( l m l 2 8 i + ) ( p 2 ) ) ； r x m m l = 一m m a v g _ e p u 8 ( r x m m l r x m m 2 ) ； 将r x m m l 和r x m m 2 取平均数放到r x m m l 中 r e s = 一m ms a d _ e p u s ( r x m m l ，r x m m 3 ) ； ，将r x m m l 和r x r n m 3 中的低8 个无符号字节相减 取绝对值后求和放到r e s 的低3 2 位中 ，同时将r x m m l 和r x m m 3 中的高8 个无符号字节相减取 i t 绝对值后求和放到r e s 的6 4 - 7 9 位中 r x m m 3 = 一m m x o r s i l2 8 ( r x m m 3 ，r x m m 3 ) r x m m 3 清0 r x m m 3 = 一m m u n p a c k h i _ e p i 3 2 ( r e s ，r x m m 3 ) 将r e s 的6 4 7 9 位放到r x m m 3 的低3 2 位中 r x m m l = 一m ma d d _ e p i 3 2 ( r e s r x m m 3 ) f i r e s 和r x m m 3 中的低3 2 位相加 s + = 一m mc v t s i l 2 8 _ s i 3 2 ( r x m m l ) ； 取r x m m l 低3 2 位与s 相加再放到s 中去 图3 - 9 我们注意到图2 的程序中，循环中的所有语句都可以被匹配而后归约，因此， 我们不需要进行相关性检查。并且如果系统中只存在上述三个模式，我们就只会 得到一种优化方案，那么也不需要进行优化方案决策。然而，如果程序不能达到 上述要求，n o c 就必须进行相关性检查和优化决策a 第三章基于模式匹配的s i m d 自动优化方案 四、实验数据 我们对伯克利多媒体应用程序集进行基于模式匹配的s i m d 优化，得到的结 果如下： b e n c h m a r k原执行时间优化后执行时间加速比 b l p e g - 2e n c1 6 0 1 1 0 9 81 4 6 l a m e6 1 05 0 2 1 2 2 m d 9 1 2 3 8 + 2 47 6 01 0 8 m p e g 一2d e c1 8 71 7 6 1 0 6 t i m i d i t 7 1 5 61 4 7 1 0 6 八、小结 在以上各节中，我们给出了基于模式匹配的s i m d 自动优化方法。该方法包 括内层循环预处理，模式匹配，相关性检查，优化决策和代码生成。利用这一方 法可以对程序中的一条或多条语句进行匹配。在实际应用中，该方法取得了较好 的加速比。 结束语 结束语 随着s 1 m d 技术在普通处理器上的发展，s i m d 自动编译技术的重要性日益突出。自动 编译技术可以检测出程序中的可优化部分将其转化为s i m d 指令，从而达到加速多媒体程 序的目的。 国际上对s i m d 自动编译技术的研究开始未久，主要是借鉴了向量化的方法。本文首先 介绍了我们对于基于向量化的s i m d 自动优化方法的研究。实验数据表明基于向量化自动优 化方法虽然具有一定的普遍性，但是这一方法对多媒体程序的加速效果不是很明显。针对这 一点，本文又提出了基于模式匹配的方法。这一方法在加速效果，灵活性和可用性等方面都 取得了一定的创新与突破。 今后要完成的工作是将基于模式匹配的s i m d 优化方法在a g a s s i z 中实现。 附录 附录 附录 附录 4 3 附录 附录 本附录中给出了由v t u n e 在i n t e lp e n t i u m4 平台下，对b e r k e l e y 多媒体工作 集中2 0 个测试程序包进行测试所得到的结果。这2 0 个测试程序包分别是 a d p c me n c o d e r ，a d p c md e c o d e r ，d j v ue n c o d e r ，d j v ud e c o d e r ，d o o m ， g h o s t s c r i p t ，g s me n c o d e r ，g s md e c o d e r ，j p e g e n c o d e r ，j p e gd e c o d e r ，l a m e ， m e s ag e a r s ，m e s am o r p h 3 d ，m e s ar e f l e c t ，m p e g - 2e n c o d e r ，m p e g - 2d e c o d e r ， m p g l 2 3 ，p o v r a y ，p a s t a ，t i m i d i t y 。饼状图中显示了不同模块的执行时间占整 个程序的执行时间的百分比。 4 5 致谢 致谢 感谢我的导师朱传琪教授的教诲。感谢臧斌宇老师的指导。本文课题的研究 与写作处处得到了他们热情的指点和无私的帮助。 感谢实验室各位同仁和师兄师姐师弟师妹们，本文的完成离不开他们的协 助。 感谢一