（信息与通信工程专业论文）simd编译优化技术研究.pdf

浙江大学硕士学位论文 摘要 多媒体应用是近年来计算机领域的研究热点。多媒体应用的代码往往具有较高的并行 度。为了获得更高的性能，几乎所有的处理器厂商都为其处理器增加了多媒体扩展，以充分 利用处理器的计算能力，并提供了具有单指令多数据特点的指令集，简称为s i m d 指令。 s l 晴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 向量化。 但体系结构和主要应用领域的不同使多媒体扩展和向量处理器之间存在较大差异。两者在向 量长度、指令集特点以及存储操作等方面存在着关键区别。妨碍s i m d 编泽优化的主要有以 下几个问题：多媒体程序中复杂的代码形式影响了向量化效果，各种多媒体典型操作变化较 多不易识别，存储操作功能较弱制约了优化性能的提升。 本文提出了一种面向由c 语言编写的多媒体应用程序、与目标平台无关的s i m d 向量 化方法，是对原有的向量化方法的扩展与改进，解决了现有技术中含有指针形式的c 程序 难以向量化、多媒体典型操作无法有效识别、s i m d 寄存器数据利用率不高等问题，能够有 效生成s i m d 指令。该方法主要在语法树中间表示上进行，不改变编译后端的结构，具有较 好的可移植性和可扩展性。 该方法对传统向量化算法的主要改进之处在于：对多媒体c 代码广泛存在的指针访问 进行了分析处理；采用模式匹配方法有效识别复杂的多媒体典型操作；采用循环分布、循环 交换等方法提高了循环中潜在的并行性；本文还提出了一种s i m d 寄存器分配方法减少冗余 存储操作，降低因体系结构限制而产生的数据存储操作开销。 关键词s i m d ，编译优化，向量化，寄存器 浙江大学硕士学位论文 a bs t r a c t t h ep a s td e c a d eh a sw i t n e s s e dm u l t i m e d i ap r o c e s s i n gb e c o m eo n eo ft h em o s ti m p o r t a n t c o m p u t i n gw o r k l o a d s t or e s p o n dt ot h ee v e r - g r o w i n gp e r f o r m a n c ed e m a n do fm u l t i m e d i a w o r k l o a d s , m u l t i m e d i ae x t e n s i o n s ( m m e ) h a v eb e e na d d e dt om o s te x i s t i n gp r o c e s s o r s t h e m u l t i m e d i ae x t e n s i o n so fm o s tp r o c e s s o r s e x p l o i ts i n g l e i n s t r u c t i o nm u l t i p l ed a t a ( s i m d ) i n s t r u c t i o n , w h i c hp r o v i d e saf o r mo fv e c t o r i z a t i o nw h e r eal a r g em a c h i n ew o r di sv i e w e da sa v e c t o ro fs u b w o r d sa n dt h es a m eo p e r a t i o ni sp e r f o r m e do na l ls u b w o r d si np a r a l l e l s i m di n s t r u c t i o n so f f e rh i g h e rp e r f o r m a n c e ，l o w e re n e r g ya n db e t t e rr e s o u r c eu t i l i z a t i o n s y s t e m a t i cu s a g eo fs i m di n s t r u c t i o n sc a l ls i g n i f i c a n t l yi m p r o v ep r o g r a mp e r f o r m a n c e h o w e v e r , c o m p i l e r ss t i l ld on o th a v e9 0 0 ds u p p o r tf o rs i m di n s t r u c t i o n s ，a n do f t e nt h ec o d eh a st ob e w r i t t e nm a n u a l l yi na s s e m b l yl a n g u a g eo ru s i n gc o m p i l e rk n o w nf u n c t i o n s ( c k f s ) ，w h i c hw i l l l e a dt o p o o rr e a d a b i l i t y , p o r t a b i l i t yp r o b l e ma n dh i g h c o s to fs o f t w a r ed e v e l o p m e n ta n d m a i n t a i n a n c e i no r d e rt ou l t i l i z es i m di n s t r u c t i o nf u l l y , w en e e dc o m p i l e rt ot r a n s l a t et h e h i 曲l e v e ll a n g u a g e st os i m di n s t r u c t i o n so fm e d i ap r o c e s s o r sa u t o m a t i c a l l y t h i si sc a l l e ds i m d c o m p i l a t i o no p t i m i z a t i o n b e c a u s eo ft h es i m i l a r i t yb e t w e e nm u l t i m e d i ae x t e n s i o n sa n dv e c t o rp r o c e s s o r s ，o n em a y n a t u r a l l yc o n s i d e ra p p l y i n gt r a d i t i o n a l v e c t o f i z a t i o nt e c h n i q u e st om u l t i m e d i aa p p l i c a t i o n s h o w e v e r , s a t i s f a c t o r yr e s u l ta r ey e tt ob eo b t a i n e df o rt h ev e c t o r i z a t i o no fr e a l i s t i cm u l t i m e d i a p r o g r a m so nm m e t h eg a pb e t w e e nm m ev e c t o r i z a t i o na n dt r a d i t i o n a lv e c t o r i z a t i o ni st h e n a t u r a lr e s u l to fb o t ht h ea r c h i t e c t u r a ld i f f e r e n c e sm u l t i m e d i ae x t e n s i o n sa n dt r a d i t i o n a lv e c t o r p r o c e s s o r sa n dt h ed i f f e r e n c e sb e t w e e nm u l t i m e d i aa p p l i c a t i o n sa n dn u m e r i c a la p p l i c a t i o n s t h e o b s t a c l e so fs i m do p t i m i z a t i o nl i ei nt h ef o l l o w i n ga s p e c t s ：c o m p l e xc o d ef o r mi ns o u r c ec o d eo f m u l t i m e d i aa p p l i c a t i o n s ，t h em u l t i m e d i at y p i c a lo p e r a t i o n sa n di t sv a r i a t i o n sw h i c hc a nn o tb e r e c o g n i z e de a s i l y , a n dt h ec o n s t r a i n t si nm e m o r yo p e r a t i o n s i nt h i st h e s i s ，t h ea u t h o r c a l t yo nar e s e a r c ht od e v e l o pe f f i c i e n ts i m do p t i m i z a t i o n t e c h n i q u e s ，a n dp r e s e n tas i m dc o m p i l a t i o no p t i m i z a t i o na p p r o a c ht h a ti si n t e g r a t e di n t ol c c c o m p i l e r t h ea p p r o a c hc a ne f f i c i e n t l yg e n e r a t es i m di n s t r u c t i o n s ，a sw e l la st oc o p ew i t ht h eu s e o fp o i n t e ri ncc o d e ，a n di d e n t i f yt h et y p i c a lo p r a t i o n si nt h em u l t i m e d i aa p p l i c a t i o n b e c i d e s ， t h ea u t h o rd e s i g n e da n di m p l e m e n t e da na p p r o a c ho fs i m dr e g i s t e ra l l o c a t i o n , i m p r o v e dt h e p e r f o r m a n c eo fr e g i s t e ra l l o c a t i o ne f f e c t i v e l y k e yw o r d s ：s i m d ；c o m p i l a t i o no p t i m i z a t i o n ；v e c t o r i z a t i o n ；r e g i s t e r 浙江大学硕士学位论文 第一章绪论 随着多媒体应用的日趋广泛，各种媒体处理技术受到越来越多的关注。许多处理器都在 原有的指令集结构上增加了多媒体扩展，并提供了具有单指令多数据特性( s i n g l ei n s t r u c t i o n m u l t i p l ed a t a ，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 编译优化技术的研究意义、国 内外的相关研究现状以及本文工作内容作一介绍。 1 1s i m d 技术的应用背景 1 1 1 多媒体应用的特点 近年来，多媒体应用受到了越米越多的关注。多媒体技术不是各种信息媒体的简单复合， 它是一种把文本、图形、图像、动画和声音等形式的信息结合在一起，并通过计算机进行综 合处理和控制，能支持完成一系列交互式操作的信息技术。多媒体技术的发展改变了计算机 的使用领域，使计算机由办公室、实验室中的专用品变成了信息社会的普通工具，广泛应用 于工业生产管理、学校教育、公共信息咨询、商业广告、军事指挥与训练，甚至家庭生活与 娱乐等领域。 人们对多媒体需求的增长促进了各种各样的媒体处理技术的产生，如语音分析和综合， 字符识别，音视频压缩，图形动画，3 d 渲染，图像增强和恢复，图像视频分析和编辑， 视频传输等等。媒体处理的主要特点1 1 1 有： 。 大量存在的数据并行性； 。 极大的数据量： 。 较小的数据类型，一般媒体数据类型只有8 位( 如图像) 或1 6 位( 如声音) ； 。 较强的实时性要求； 。 多个并发的媒体流； 随着用户对更多更好的多媒体服务的需求，多媒体应用的处理性能要求也迅速提升。当 今很多媒体应用己经超越了传统处理器的处理能力，媒体处理系统需要更大的灵活性和计算 能力以充分支持多媒体应用。 浙江大学硕士学位论文 1 1 2 媒体处理器的特点 尽管个人电脑处理器的性能已经有了长足的进步，但多媒体计算还是给处理器的计算能 力带来了新的挑战。这主要是因为1 2 捌： 。 通用处理器是针对复杂控制执行逻辑优化的，它不关心具体某类应用程序的特征： 而多媒体计算控制逻辑相对简单，分支跳转的可预测性很强。这样使得通用处理器 的复杂控制无用武之地。 现代通用处理器是以字( 一般为3 2 位或者6 4 位) 为单位进行计算的；而多媒体计 算主要的运算宽度是8 位或者1 6 位。这样使得处理器的数据处理宽度无法得到充 分利用。 上述特点使得通用处理器无法有效处理多媒体数据。而多媒体计算的数据量又极为庞 大，所以通用处理器对于多媒体计算就显得力不从心。因此，为了保证高效的多媒体处理能 力，必须在处理器体系结构上进行增强。 传统上提高处理器性能有两条主要途径【l l l ：提高时钟频率和增加处理器并行处理能力。 前者通过提高流水线深度和简化流水线每级的设计逻辑等手段，使得处理器的时钟频率得到 不断的提高。而后者通过添加更多的硬件逻辑，加强处理器的并行处理能力，提高处理器的 吞吐量。然而，随着品体管集成度的提高，由于晶体管的封装，芯片的蚀刻等问题使得传统 的通过硬件工艺水平发展来提高处理器性能变得越来越困难【1 6 1 。另外，媒体处理器是针对 媒体应用领域而设计的，单单依靠提高时钟频率和增加处理器并行处理能力等手段来提高处 理器性能是不够的，还需要从媒体处理的特点进行考虑。 为了适应媒体处理的特点，媒体处理器采用了不同于传统处理器的体系结构来提高处理 器性能。针对满足媒体处理数据量大，计算密集等特点，媒体处理器中往往通过对指令集体 系结构( i n s t r u c t i o ns e ta r c h i t e c t u r e ，i s a ) q b 进行多媒体扩展( m u l t i m e d i ae x t e n s i o n ，m m e ) | 1 2 l 来支持媒体处理。多媒体扩展是利用通用处理器完善的开发环境( 如成熟的编译器和操作系 统) 来实现多媒体应用支持。对通用处理器的指令集结构作些附加的多媒体扩展，可以用很 小的硬件代价获得对媒体处理较高的性能支持。多媒体扩展往往提供很多s i m d 指令来加速 多媒体应用。 1 1 3s i m d 技术 多媒体算法中经常需要对无相关性的多个象素或数据作相同的操作，因此多媒体应用的 核心代码往往有着高度的并行性。同时，目前处理器的数据带宽已经达到3 2 位甚至6 4 位， 而典型的多媒体应用程序往往只有8 位或者1 6 位，利用率很低。为了充分利用这些数据带 宽，硬件设计者引入了s i m d 的概念。 s i m d 是用一个控制器来控制多个处理单元，同时对一组数据( 又称“数据向量”) 中 2 浙江人学硕上学位论文 的每一个元素同时执行相同的操作来实现空间上的并行性。 多数处理器都提供了s i m d 指令集，并增加了专门用于执行s i m d 指令的s i m d 寄存器。 s i m d 寄存器的位宽往往为3 2 位、6 4 位或者1 2 8 位，这个位宽被称为。字( w o r d ) ”。这些s i m d 寄存器可以划分为若干个较小的相互独立的单元，称为“亚字( s u b w o r d ) ”。s i m d 指令对 s i m d 寄存器中的所有亚字同时执行相同的操作。例如，一个6 4 位的s i m d 寄存器可以存 放8 个8 位的数据、或4 个1 6 位的数据、或2 个3 2 位的数据。图1 1 给出了一个典型的 s i m d 指令执行模型：两组数据各包括四个相互独立的单元，每对单元执行相同的操作，可 同时得到四个运算结果。 i x 3x 2x lx o i y 3y 2y ly 0 l l ii r 1r 1r ) 年) ) l ， ， 广一 ( o p 丫 l x 30 p y 3 x 2 0 p y 2 x io p y l x o o p y o 图1 - 1 典型的s i m d 指令执行方式 对于s i m d 指令米说，参与计算的寄存器中存放的不再是标量操作数，而是向量操作数， 指令所实现的也不是标量计算而是向量计算。s i m d 指令利用了媒体应用程序中大量存在的 数据并行性，通过一条指令完成以前若干条指令才能完成的任务，因而提高了媒体处理的能 力。 除了基本的向量计算外，多媒体扩展往往还根据多媒体应用的特点而提供一些特殊的复 合指令，如乘累加、饱和计算、m a x m i n 最值运算、求平均值、差的绝对值求和等等。这 些指令能够一次实现通常需要通过多条普通运算指令组合才能实现的功能。这些复合指令在 各类多媒体程序中的应用能够使代码获得超线性的加速比1 6 】。因此这些针对多媒体应用的复 合操作也是s i m d 指令集中的重要组成部分。 由于s i m d 指令对多媒体应用核心代码的性能提高有着显著的作用，随着硬件技术的发 展，越来越多的s i m d 构架被整合在通用处理器或者d s p 芯片中。例如，i n t e l 在p e n t i u mi i i i v 芯片中实现了基于寄存器的s i m d 构架，在这一构架基础上提供了s s e n 指令集，并不断推 陈出新。 第一代的s s e ( s t r e a m i n gs 1 m de x t e n s i o n s ) 指令集1 7 1 出现在p e n t i u m1 1 1 处理器中，共有 3 浙江大学硕上学位论文 7 0 条指令，包括：提高3 d 图形运算效率的5 0 条s i m d 浮点运算指令、1 2 条m m x 整数运 算增强指令、8 条优化内存中连续数据块传输指令。这些指令对图像处理、浮点运算、3 d 运算、视频处理、音频处理等诸多多媒体应用起到全面强化的作用。 s s e 2 8 j 指令集是i n t e l 公司在s s e 指令集的基础上发展起来的。相比于s s e ，s s e 2 使用 了1 4 4 条新增指令，提高了应用程序的运行性能。随m m x 技术引进的s i m d 整数指令从 6 4 位扩展到了1 2 8 位，使s i m d 整数类型操作的有效执行率成倍提高。双精度浮点s i m d 指令允许以s i m d 格式同时执行两个浮点操作。除s s e 2 指令之外，最初的s s e 指令也得到 增强，通过支持多种数据类型的算术运算来支持灵活并且动态范围更广的计算功能。s s e 2 指令可让软件开发员极其灵活地实施算法，并在运行诸如m p e g 2 、m p 3 、3 d 图形之类的 软件时增强性能。 s s e 3 8 1 指令集规模较小，包含1 3 条指令。它共划分为五个应用层，分别为数据传输命 令、数据处理命令、特殊处理命令、优化命令和超线程性能增强。最新推出的s s e 4 1 9 指令 集被视为i n t e l 自从s s e 2 之后对指令集最大的一次的升级扩展。s s e 4 包括大约5 0 条新指令， 用于增强从媒体应用到高性能计算应用领域的性能，图形图像处理、视频处理、2 d 3 d 创 作、多媒体、游戏、内存敏感负载、高性能计算等应用都会从中受益。 其他典型的s i m d 指令集包括a m d 的3 dn o w 10 0 1 、s u nu l t r a s p a r c 处理器的v i s 指 令集【l l l 以及m o t o r o l a 的a i t i v e c f l 2 1 指令集等等。这些处理器通过充分利用数据通路资源，在 传统处理器的设计基础上进行s i m d 指令扩展来同时处理多个数据，进而提高了媒体处理的 能力。 1 2 编译器设计 1 2 1 编译器的作用 编译器是现代计算机系统中的基本组成部分。从狭义上讲，编译器是把用高级语言编写 的程序翻译成对等的可在某一计算机上执行的目标代码或机器代码的系统软件。从广义上 讲，编译器概念可以进一步延伸，可以是把一种高级语言翻译成另一种高级语言，也可以是 把一种机器语言翻译成另一种机器语言，或是把一种高级语言翻译成中间表示形式等等。图 l - 2 显示了编译器在整个计算机系统中的位置和扮演的角色。从图中可以看出，编译器与目 标机器结合得非常紧密，事实上它允许用户忽略与具体目标机器相关的机器语言细节。无论 是操作系统还是应用程序开发都离不开编译器的支持。 4 浙江大学硕士学位论文 硬件 图l - 2编译器在计算机系统中的位置 问硬件 操作系统是对效率要求很高的系统软件，它的编写往往使用高级语言，这就需要利用优 秀的优化编译器以产生良好、高效的代码。比如著名的开源操作系统l i n u x 就是主要用c 语言编写，并用著名的开源编译器g c c ( g n uc o m p i l e rc o l l e c t i o n ) i 4 s 1 编译的【6 7 1 ，达到了很 高的效率。 应用程序的开发也离不开编译系统的支持。为了达到较好的可读性、可维护性和可移植 性，较快的开发速度，以及较低的成本等优点，应用程序主要用高级语言开发。为了在使用 高级语言开发的同时获得优异的效率，就需要一个好的优化编译器来提供高效的代码。因此， 编译器不仅完成由高级语言到目标机器指令的翻译工作，它同时也是对应用程序进行优化的 主要工具。 1 2 2 编译器的基本结构 编译器的结构通常可以粗略地分为前端( f b n te n d ) 和后端( b a c ke n d ) 两大部分【l l 12 1 ，如图 l - 3 所示。 蔡程序中间表示 前端后端 7 i ”广 编译器 图l - 3编译器结构组成 程序 前端接受高级语言编写的应用程序，并将其转化成机器无关的中间表示( i n t e r m e d i a t e 5 浙江大学硕士学位论文 r e p r e s e n t a t i o n ，i r ) 。中间表示是指编译器翻译源语言程序到目标代码的中间过程中的临时 表示。前端主要致力于理解源语言程序。后端将中间表示转化为目标机器的汇编代码或者机 器代码。 中间表示是前端和后端间进行信息传送的桥梁，使得前端和后端成为相对独立的两大模 块。这样，只要中间表示不变，若干个面向不同目标机器的后端可以共享同一前端；反之， 若干个支持不同高级语言的前端也可以使用同一后端。 1 2 3 编译器的工作流程 一个编译器的工作流程由一系列的阶段组成，这些阶段从待编译的源程序的字符序列开 始，依次对源程序的某个特定形式进行分析，并产生一种新的形式。 ， ，7 圈： 、， l 词法分析器i 上单词串 f 语法分析器i 中间袭 1r 语义分析器i 土中间衷 l 代码生成器l 示，7 图l - 4 编译器基本工作流程 一个完整的编译过程至少包括图1 4 所示的四个阶段，分别是： 1 词法分析( 1 e x i c a la n a l y s i s ) 。这一阶段分析提交的字符串，将其划分为一组符合编 程语言词法规范的单词( t o k e n ) 。如果字符串不能转换为一串合法的单词串，将报 告错误信息。 2 语法分析( s y n t a c t i c a n a l y s i s o r p a r s i n g ) 。这一阶段处理单词串，产生中间表示。如 果单词串中含有语法错误，将报告错误信息。 3 语义检查( s e m a n t i cc h e c k i n g ) 。这一阶段以中间表示为输入，确认程序是否满足源 6 、 一 r 一 ， 、 一 。i 一 ， 、 一目并一 、 一j l 一 一 一 、 一 一 、一， 、 ， ， 、 ， 、，、 ， ， 、 、 ， 、 、 ， 、 、 一眄 ， 、 、 示 ， 浙江大学硕士学位论文 语言要求的语义属性。 4 代码生成( c o d eg e n e r a t i o n ) 。这一阶段将中间表示转换为可运行的目标机器代码。 除了这四个基本的阶段，编译器还包括一张符号表和访问该表的若干例程，以及与操作 系统和用户环境的接口( 用来读写文件、读取用户的输入、向用户输出信息等等) 1 2 4 编译器的构造 编译器作为一种复杂的系统软件，有着开发周期长、结构复杂、调试困难的特点。 由于编译器功能复杂，在编译器开发过程中必须将编译问题划分为一个个的子问题进行 解决，所以编译器的结构一般是一种基于“遍”( p a s s ) 的层次化结构。这种层次上的划分简 化了编译器开发与调试的难度。对于优化编译器，由于产生最优化( o p t i m a l ) 的目标代码是个 n p 完全问题【1 3 l ，而开发一种优化算法往往需要大量的人力物力进行设计与实现，所以人们 往往需要在编译器的优化能力和复杂程度上做出折衷。 编译器中的一些问题可以用统一的方法进行解决，而帮助生成编译器本身的编译器生成 器( c o m p i l e rg e n e r a t o r ) 之类的工具可以帮助进行这方面的自动化或半自动化开发。这些工具 既包括前端扫描工具，如l e x 1 4 t1 卯、y a c c 1 4 ，6 ，1 7 1 ，也包括后端代码生成工具，如i b u r g 1 s - 2 0 、 o l i v e 2 1 】等。但工具的使用也造成了调试上的困难。由于工具产生的代码难以进行人工阅 读，所以调试代码、跟踪代码都是很困难的问题，这增加了编译器调试的难度。另一方面优 化编译器中各个优化器的相互作用也可能会产生冗余代码，而这些代码在产生来源上的分析 和定位都更加困难，这也大大增加了编译器开发和调试的难度。 编译器设计开发过程中，构造一个全新的编译器是一项相当复杂的工程，如果在已有的 系统功能完备、具备良好模块结构的编译器之上进行开发，不仅会缩短开发周期，而且能够 在目标机器做了修改以后迅速对编译器进行调整。如果将与目标机器相关的特性从代码生成 器中抽取出来，在单独一个文件中进行描述，并通过一些构造器将这些特性翻译成代码生成 器需要的数据结构和配置信息，这样能方便地将编译器重定向到新的目标机器。如图1 5 所 示。其中，目标机器描述按一定格式组织为单独的文件，i b u r g 是代码生成器的构造器。 图1 - 5 可重定向编译器的代码生成器结构 7 浙江大学硕士学位论文 1 3s l m d 编译优化 1 3 1s i m d 编译优化研究的意义 s l m d 编译优化是指：为多媒体程序源代码尽可能地生成优化的s i m d 指令序列。在一 些文献中它也被称为s i m d 向量化( s i m d i z a t i o n ) 2 7 1 、寄存器内向量化( s i m d i z a t i o nw i t h i na r e g i s t e r , ，s w a r ) 2 s 】或寄存器内s i m d 优化1 2 9 1 。 已经有大量研究【2 5 。2 9 1 表明，s i m d 指令在提高媒体处理器性能和降低功耗方面有显著的 作用。例如，德国d o r t m u n d 大学的r a i n e rl e u p e r s 等为t e x a si n s t r u m e n tc 6 2 x x 和p h i l i p s t i n m e d i at m l 0 0 0 两种d s p 芯片实现了一种支持s i m d 的指令选择算、法【2 3 1 。他们的实验结 果表明，利用s i m d 指令可以使所需指令的数目平均减少5 0 。同时，m a r k u sl o r e n z 和p e t e r m a r w e d e l 等也首次对s i m d 指令对功耗的影响进行了研究f 2 9 j 。其研究结果表明：虽然一条 s i m d 指令消耗的功率可能是一条普通指令的几倍，但对整个程序而言，充分利用s i m d 指 令仍能使整体功耗平均减少7 2 ，而使执行时间平均减少7 6 。 虽然s i m d 指令的出现给优化多媒体应用带来了美好的前景，但是如何充分利用这些扩 展指令却成为一个难题。因为s i m d 指令不像超标量等技术那样是微体系结构 ( m i c r o - a r c h i t e c t u r e ) 层面的，而是体系结构层面的( 程序员可见的) 1 2 5 1 ，这要求程序员( 或 者编译器) 显式地利用这些新特性来提高程序性能。程序员常常需要通过p r o f i l e 工具找出影 响程序性能的瓶颈部分，将这些部分用汇编代码重写，或者采用在代码中直接嵌入汇编指令 的方法来直接优化程序中的核心代码，或者使用优化库函数。而这些方法都要求程序员对硬 件系统的深入了解。这一方面增火了程序开发的难度，另一方面由于不同处理器厂商的多媒 体扩展指令各不相同，给程序移植带来很大困难。 因此，程序开发人员希望由编译器为多媒体程序源代码尽可能地生成优化的s i m d 指令 序列。这种方法有以下优点：首先，解放了程序设计人员。程序的开发人员只需要用标准的 高级语言来实现应用算法，而将相关的优化交由编译器来实现。他们不再需要去深入学习各 种s i m d 硬件平台，也不需要去学习如何编写向量化的汇编代码。这样就大大减轻了程序员 的负担。其次，更加安全可靠。由编译器来代替程序员进行相关性判断或指令选择等工作可 以有效降低出错的几率。第三，大量现有的应用程序代码都可以被继承下来，从而节约了大 量重写代码的投资，降低了开发成本。 由此不难看出，构造能够支持s i m d 指令的优化编译器具有重要的研究意义和应用价 值。如何根据多媒体程序代码自动生成优化的s i m d 指令也成为编译技术领域的一个研究热 点。 8 浙江大学硕士学位论文 1 3 2s i m d 编译优化的要求 s i m d 编译优化是一种高层的、细粒度并行优化。对于这种优化生成的代码，应有以下 要求l ”l ： 1 保持原程序语义。必须在编译分析时严格遵循语言规范所规定的语义，并保证最后 生成的s l m d 代码也保持这种语义。保义性要求主要有以下几个方面： ( 1 ) 保持数据相关性。数据相关性决定了程序中代码的执行顺序。因为s i m d 编译优 化本质上是一种代码的变换，必然涉及到对代码执行顺序的调整，因此必须保证这些调整不 违反数据相关性。 ( 2 ) 保持操作精度。小数据类型( c h a r 和s h o r t ) 在运算之前往往需要先转换成i n t 类 型，然后执行运算，运算结束后再将结果转换成所需类型，即整型提升( i n t e g e rp r o m o t i o n ) 。 但对于s i m d 指令来说，因为其操作数的每个单元( 即子字) 的长度是固定的，所以它对小 数据类型的运算不进行整型提升。这样，进行s i m d 优化后的代码就有可能因为计算过程中 的数据溢出而引起结果的不一致。这种情况应当避免。 2 产生的s i m d 指令必须高效。尽可能找出那些能在s i m d 编译优化中受益的程序部 分，必须确保生成的s i m d 指令比普通指令更加高效，这也是s i m d 编译优化的价值所在。 1 4相关工作与研究现状 针对s i m d 编译优化的技术研究历史不长，目前这一领域的研究主要可以概括为以下几 个方面： 。 基于向量化的s i m d 编译方法 - 基于s l p 的编译方法 。 其他s i m d 编译优化相关子问题的研究 1 4 1 向量化方法 自动向量化技术是一种基于数据相关性分析的编译优化技术。r a n d ya l l e n 、k e n k e n n e d y 等人对向量机上的自动向量化做了许多开创性的工作【2 6 1 。他们在相关性分析、代码 规范化、循环变换等技术上做了大量研究，并提出了自动向量化编译算法【2 们。该方法在面 向向量处理器处理的科学计算程序上取得了十分满意的结果。 自动向量化技术以相关性分析为基础。相关性的精确概念最早由d a v i dk u c k 提出【z7 1 ， 随后m i c h e a lw r o l f 、k e nk e n n e d y 等人相继完善了这一概念【2 8 1 ，提出了方向向量、相关深度 等一系列概念，并将其运用到自动向量化上。u t p a lb a n e r j e e 等人则提出了相关性的测试方 9 浙江大学硕士学位论文 法 2 9 1 ，包括g c d 测试1 2 9 1 、o m e g a 例测试等。作为面向向量处理器的编译技术，自动向量化 取得了比较大的成功。 s i m d 指令通过单条指令实现对多个数据元素的并行操作。这种数据并行处理方式与向 量处理非常类似，因此，s i m d 指令可以看成是一种向量长度比较短的向量指令。鉴于多媒 体扩展与向量处理器的相似性，因此，大量科研和工程研究致力于将向量化方法引入s i m d 编译优化技术中以支持s i m d 指令。 k r a l l 和l e i a i t 在s u i f 编译器的基础上将自动向量化技术移植到v i s 多媒体扩展指令的 代码生成中t 3 1 1 。开源编译器g c c 从4 1 版本开始以t r e e s s a t 3 2 1 为优化架构逐步移植自动向 量化技术。但是目前为止这些移植工作并未取得令人十分满意的结果，编译器自动生成的向 量化代码与手工优化相比还有较大差距。这是因为s i m d 多媒体扩展与向量处理器的应用领 域与硬件平台都不同。s i m d 指令主要面向的是多媒体应用。与向量处理器相比，s i m d 多 媒体扩展具有存储操作功能弱、多媒体程序代码形式不规范等特点1 3 6 1 ，从而增加了向量化 的难度。针对存储操作功能弱的问题，现有的研究工作中，主要通过数据预取来隐藏访存延 迟，或者通过数据局部性优化来提高c a c h e 命中率【3 7 - 3 9 1 ，从而加快平均访存速度。针对向量 化对代码形式要求较高的问题，有一些关于代码形式规范化的研究成果，包括循环的正规化、 递归变量的归约、全局向前替代、标量扩张等等。 由于s i m d 编译优化和向量化针对的是不同的硬件平台和应用领域，因此尽管前者在一 定程度上可以借鉴后者的方法，但不能完全照搬后者的研究结果，而应首先找出两者的差异。 文献f 3 4 , 3 f l 从硬件角度探讨了s i m d 指令的特点，以及如何改进硬件以更好地支持s i m d 编译 优化。文献1 3 6 l 对多b m w 多媒体程序包中的核心代码进行了手工s i m d 实现，并对这些代 码的运行时特点进行了分析。也有一些研究尝试从不同于传统向量化的角度去看待s i m d 编 译优化，如文献 4 5 1 提出将软件的向量化和硬件的流水线相结合，从而充分利用软硬件的特 点提高性能。 1 4 2 超字并行 在超长指令字( v e r yl o n gi n s t r u c t i o nw o r d ，v l i w ) 思想的启发下，s a m u e ll a r s e n 等人 提出了s i m d 编译优化的超字并行( s u p e r w o r dl e v e lp a r a l l e l i s m ，s l p ) 算法【3 3 】。v l i w 指 令可以将多个不同类型的操作在单个指令周期内同时发送并执行。尽管s i m d 指令与v l i w 指令的并行粒度不尽相同( 前者为数据级并行，后者为指令级并行) ，但s i m d 指令仍可看 作是一种操作类型必须相同的特殊v l i w 指令。 s l p 算法侧重于在一段线性代码空间( 例如基本块) 中而不是在循环中来开发并行性。 其主要思路是：在一个给定的代码空间范围内分析程序代码，找出满足一定条件的几条同构 语句，将它们打包成一条s i m d 指令。其中同构语句是指：两条语句的对应位置具有相同的 操作符和操作数类型。对于程序中的循环，则首先以一定的展开因子展开，使其成为一个基 本块，再在基本块内进行分析。而无需进行循环迭代依赖分析，简化了数据依赖分析的过程。 1 0 浙江大学硕十学位论文 l a r s e n 和a m a r a s i n g h e 以s u i f 为基础，面向a l t i v e e 目标平台，实现了s l p 方法p 3 1 。此 外，还有不少研究工作基于s l p 方法展开。在文献提出了一种基于自由节点调度的s i m d 代码生成算法，并取得了一定的效果。 1 4 3 对s i m d 编译优化相关子问题的研究 还有一些研究围绕与s i m d 编译优化相关的子问题展开。 r a i n e rl e u p e r s 等人提出了基于数据流图的指令选择算法1 2 3 1 ，将传统的树模式匹配和动 态规划的指令选择算法与整数线性规划相结合，最大限度地生成s i m d 指令。 文献【3 9 】对s i m d 编译优化中的相关性问题及其与传统向量化之间的差异进行了详细讨 论。 文献【5 3 】提出使用可嵌套的规则库来进行可向量化操作识别的方法。 此外，还有一些研究提出新的语言和工具来支持s i m d 指令。文献 4 1 ，4 2 提出了一些c 语言的扩展( 宏、语法扩展等) 来方便程序员开发平台无关的s i m d 操作。而文献【4 3 】提出 了一种使用高层数学描述利用s i m d 指令来实现f f t 、d c t 等数字信号处理中的关键算法 的方法。 1 5本文主要内容、创新点与结构安排 本文对媒体处理器编译器中s i m d 指令的自动生成的编译优化技术进行了研究，在l c c 编泽器上实现了一种s i m d 编译优化方法。该方法解决了现有技术中含有指针形式的c 程 序难以向量化、多媒体典型操作无法有效识别、s i m d 寄存器数据利用率不高等问题，能够 有效生成s i m d 指令。 本文的s i m d 编译优化方法可以看作是传统向量化算法的扩展与改进。传统向量化算法 主要面向由f o r t r a n 语言编写的科学计算程序。本文的s i m d 编译优化方法则面向由c 语言 编写的多媒体应用程序。c 语言编写的多媒体程序代码形式变化较多，特别是常常使用指针 来访问内存单元。并且传统向量化算法难以识别s i m d 指令中的一些多媒体典型操作。本文 的方法针对这些问题进行了改进，增加了对于代码中指针形式的分析与处理，并采用了模式 匹配方法识别饱和运算等多媒体典型操作。 现代处理体系结构与指令集系统的多样性要求编译器易于重定向。本文的s i m d 编译优 化方法的主要工作在l c c 的树中间表示级进行，对编译后端改动较小，具有目标平台无关 的特点。 此外，本文还提出了一种s i m d 寄存器分配方法，并在l c c 中实现。和通用寄存器相 比，s i m d 寄存器中存放的数据更多，因此也产生了更多的重复使用的机会。本文的s i m d 1 1 浙江大学硕士学位论文 寄存器分配方法从这一点出发，在寄存器的分配过程中考虑了向量之间的相似性以及数据的 重复利用，提高寄存器的使用效率。 本文的主要贡献有： - 提出了一种与目标平台无关的s i m d 向量化方法。该方法是对传统向量化算法的改 进与扩展。主要改进之处在于：对多媒体c 代码广泛存在的指针访问进行了分析 处理；采用模式匹配方法有效识别复杂的多媒体典型操作；采用循环分布、循环交 换等方法提高了循环中潜在的并行性。 提出了一种s i m d 寄存器的分配方法并在l c c 上实现。由于s i m d 寄存器存放的 是向量数据，因此s i m d 寄存器的分配与普通寄存器有所区别。本文的s i m d 寄存 器分配方法能够有