（计算机系统结构专业论文）基于数据划分的二维simd优化与结构设计.pdf

论文独创性声明 本论文是我个人在导师指导f 进 j ：的研究工作及取得的研究成果。论文巾除 了特别加以标注和致谢的地方外，彳i 包含其他人或其它机构已绎发表或撰写过的 研究成果。其他同志对本研究的肩发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名： 论文使用授权声明 日期：主：2 ：型 本人完全了解复旦人学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 般。名：盟聊魏毯繇作者签名：盟导师签名：鲻日 阳g b ) 。g i i 期：! ! ：竺 摘要 苹果公司在m a c w o r l d2 0 0 7 上发布的智能手机i p h o n e 是多媒体与通信技术 迅速发展带给我们生活美好礼物的一个典型例子，然而与之相对应的是当手持设 备越来越像一个智能娱乐计算机时，多媒体应用给底层设备计算能力提出了更高 的要求。二维s i m d 结构是指一个由n x n 的处理单元按一定的拓扑结构连接组 成的阵列结构，其同行，列的处理单元以s i m d 方式工作。由于多媒体应用程序 的核心代码由8 位或者1 6 位的整数计算所构成，能够充分运用二维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 l m d 结构性能的影响，提出设计建议。我们在s i m p l e s c a l a r 基础上实 现了一个体系结构模拟器，并在这个平台上测试了算法优化的结果，实验数据显 示算法对于多媒体程序有很好的加速比，此外我们还测试配置了不同的参数的结 构性能，验证了设计建议。本文的主要贡献如下所述： 设计实现了基于s i m p l e s c a l a r 的二维s i m d 结构性能模拟器 提出了基于数据划分的二维s i m d 编译优化算法 分析研究了不同设计参数对二维sj m d 结构性能的影响 关键词：二维s i m d ，数据划分，编译优化，多媒体应用，模拟器 a b s t r a c t 5 一 a b s t r a c t a p p l e si p h o n ew h i c hi sr e l e a s e di nm a c w o d d2 0 0 7i sag i f ts e n tt oo u ri i f e b yt h er a p i dd e v e l o p m e n to fm u l t i m e d i aa n dc o m m u n i c a t i o nt e c h n o l o g y a s h a n d h e l de q u i p m e n t sb e c o m em o r ei i k ee n t a i l m e n tc o m p u t e r s 。m u l t i m e d i a a p p l i c a t i o n se x p e c t m u c h s t r o n g e rc o m p u t a t i o np e r f o r m a n c e o ft h e u n d e d y i n ga r c h i t e c t u r e t w o - d i m e n s i o n a ls i m da r c h i t e c t u r ei sc o m p o s e do f n np r o c e s s i n ge l e m e n t st h a ti n t e r c o n n e c t e dt oo t h e r sa c c o r d i n gt os o m e t o p o l o g y t h ep r o c e s s i n ge l e m e n t si nt h es a m er o wo rc o l u m no p e r a t e t o g e t h e ri ns i m dm o d e s i n c em u l t i m e d i aa p p l i c a t i o n su s u a l l yo p e r a t eo n8 b i t so r16b j t sd a t a t h e yc a nf u i l yu t i l i z ee a c hp r o c e s se l e m e n to ft h e u n d e d y i n gt w o d i m e n s i o n a is i m da r c h i t e c t u r e t h e r e t o r et w o - d i m e n s i o n a i s i m da r c h i t e c t u r ec a na c h i e v eh i g hp e r f o r m a n c em u l t i m e d i ac o m p u t a t i o n t h i sf e a t u r em a k e sc o m p i l i n go p t i m i z a t i o nf o rt h i sa r c h i t e c t u r et h ek e yo fh i g h p e r f o r m a n c em u l t i m e d i ap r o c e s s i n g i nt h i sp a p e rw ep r e s e n tac o m p i l i n go p t i m i z a t i o na l g o r i t h mb a s e do nd a t a p a r t i t i o nt om a pt h ec o m p u t a t i o no n t ot h ea r c h i t e c t u r eo nt h eb a s i so fd e e p u n d e r s t a n d i n go ft w o - d i m e n s i o n a ls l m da r c h i t e c t u r ea n dm u l t i m e d i a a p p l i c a t i o n s d a t al o c a l i t yi s e s s e n t i a it oa c h i e v i n gh i g hp e r f o r m a n c eo n t w o - d i m e n s i o n a ls i m da r c h i t e c t u r ew i t hr e s t r i c t i o n st h a ti m p o s eg r e a t d i f f i c u l t yo nc o m p i l i n go p t i m i z a t i o n t h u sd e c o m p o s i t i o no fd a t aa n dm a p p i n g t h e mo n t op r o c e s s o re l e m e n t si sak e yt e c h n i q u ej nt w o - d i m e n s i o n a is i m d c o m p i l i n g t h ea l g o r i t h mf u i l yu t i l i z e sd a t al o c a l i t yt om a x i m i z et h ed e g r e eo f p a r a l l e l i s ma n dm i n i m i z et h ed e g r e eo fc o m m u n i c a t i o na f t e rd e c o m p o s i t i o n f u r t h e r m o r ew ed e l v ei n t ot h ep e r f o r m a n c ei m p a c to fv a r i o u sd e s i g n p a r a m e t e r so ft w o - d i m e n s i o n a ls i m da r c h i t e c t u r et op r o d 0 s ed e s i g n s u g g e s t i o n sb e c a u s ew eg e td e e pi n s i g h ti n t ot h ea r c h i t e c t u r ed e s i g ni nt h e p r o c e s so fd e v e l o p i n gc o m p i l i n go p t i m i z a t i o na l g o r i t h m s t h ee x p e n m e n t r e s u l t st h a ta r ec a r r i e do u to nt h ep e r f o r m a n c es i m u l a t o rb a s e do n s i m p l e s c a l a rs h o wt h a tt h ea l g o r i t h m sc a ns p e e d u pm u l t i m e d i ap r o g r a m so n t w o - d i m e n s i o n a is l m da r c h i t e c t u r eo b v i o u s l ya n do u ra r c h i t e c t u r ed e s i g n s u g g e s t i o n sa r es u s t a i n a b l e t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ei i s t e d b e l o w ： d e s i g na n di m p l e m e n ts i m u l a t o rf o rt w o - d i m e n s i o n a is i m da r c h i t e c t u r e p r e s e n tac o m p i l i n go p t i m i z a t i o na l g o r i t h mb a s e do nd a t ap a r t i t i o nf o r t w o - d i m e n s i o n a is l m da r c h i t e c t u r e a n a l y z et h ep e r f o r m a n c ei m p a c to f v a n o u sd e s i g np a r a m e t e r so f t w o - d i m e n s i o n a is l m da r c h i t e c t u r e k e y w o r d s ：t w o - d i m e n s i o n a ls i m da r c h i t e c t u r e ，d a t ap a r t i t i o n ，c o m p i l i n g o p t i m i z a t i o n ，m u l t i m e d i aa p p l i c a t i o n s a r c h i t e c t u r es i m u l a t o r 第一章引言 第一章引言 1 1 多媒体应用与二维s i m d 体系结构 多媒体与通信技术的迅速发展使手持设备上的应用程序展现了颠覆性的变 化，图1 1 所示的苹果公司在m a c w o r l d2 0 0 7 上发布的智能手机i p h o n e 就是一 个典型的例子，集电话、音乐、视频、摄像、上网等应用于一身。手持设备越来 越像一个智能娱乐计算机，应用不断丰富，各种计算密集型，高吞吐量的多媒体 应用如视频、音频、图像处理等逐渐成为手持设备的主要应用。 图1 1 苹果公司i p h o n e 在这些多媒体应用中，作为计算核心的处理器往往承担了编码、解码、压缩、 解压、解释、增强和渲染等高强度的计算任务1 10 1 ，而这些计算又往往具有以下 的主要特征【11 1 ： 数据量极大 对计算的实时性要求较高 计算存在高度可并行性 计算密集度高 对计算精度要求较低( 以8 位或1 6 位整数计算为主) 对输入输出的带宽要求较高 第一章引言 多项计算任务同步并行( 如音频与视频计算的同步进行) 早期的系统中通常采用专用的d s p 芯片来提高处理多媒体应用的性能【1 2 】， 然而随着多媒体应用的不断丰富和对底层硬件环境的要求越来越高，低成本的解 决方案就变得十分迫切。所以原本应用在并行处理领域的二维s i m d 结构逐渐引 起重视，由于其离性能计算特性使其成为一个很好的解决方案，因此被广泛的作 为多媒体加速部件应用在各种多媒体处理的s o c 中。二维s i m d 结构是一个由 n x n 的处理单元p e ( p r o c e s s i n ge l e m e n t ) 按一定的拓扑结构连接组成的阵列结 构，其同行，列的处理单元能够以s l m d 方式工作，由于多媒体应用程序的核心 代码由8 位或者1 6 位的整数计算所构成( 表1 1 给出了b e r k e l e ym u l t i m e d i a w o r k l o a d 2 0 主要整型多媒体程序的应用领域及计算精度要求) ，能够充分利 用每一个p e 的计算功能，所以结构具有很高的计算并行性从而能够获得高性能 的多媒体计算。 测试程序应用领域核心代码计算精度要求代码行数 m p e g 2 视频压缩解压缩 c h a r1 7 4 3 7 d o o m 电子游戏 c h a r5 7 8 6 8 m e s a三维渲染 c h a r1 2 0 0 3 8 a d p c m 音频压缩，解压缩 s h o r t3 0 0 g s m语音压缩，解压缩 s h o r t5 4 7 3 d j v u 图象压缩7 解压缩 s h o r t2 5 4 1 9 j p e g 图象压缩解压缩 s h o r t3 3 7 1 4 t i m i d i t y 音乐渲染 s h o r t4 0 5 1 4 表1 1 主要多媒体扩展列表 二维s i m d 结构作为多媒体加速部件的应用前景引起了学术界【1 i 【2 1 【3 】【4 】【5 】 广泛关注，许多公司，如m o r t o r a l a 、i n t d n s i t y 、m o r p h o t e c h 和f o l s o m 等公司 也都推出了采用二维s i m d 结构作为多媒体加速部件的s o c 。然而出于能耗和 芯片面积的考虑，绝大多数二维s l m d 结构加入了复用数据通路和p e 之间连接 受限的限制。因此如果希望充分利用计算资源提供的并行特性，使多个s i m d 行 ，列并行执行，必然造成多行，列s i m d 操作对数据通路的竞争。同时p e 之间连 接方式受限也造成了不同s i m d 行，列之间数据通信的竞争。这些数据通信的限 第一章引言 制给二维s l m d 多行，列的并行特性造成了极大的障碍。 1 2 二维s i m d 优化和数据划分的相关研究工作 虽然二维s i m d 体系结构给多媒体应用程序带来了美好的前景，但是如何充 分利用这个结构优化却成了一个难题。二维s i m d 结构编译技术研究滞后主要可 以归结为以下几方面的原因：首先，并行领域应用的二维s i m d 结构由于受当时 硬件水平的限制，不是很成功，同时，当时的并行编译理论发展还不成熟，所以 没有形成针对二维s i m d 结构比较有效的编译技术；其次，虽然目前的并行编译 技术已经发展比较成熟，但是因为传统的并行编译理论主要针对的程序为科学计 算类程序，而目前二维s l m d 结构主要应用在多媒体处理领域，多媒体程序与传 统的科学计算类程序间存在着一定的差别。最后，由于目前各种嵌入式s o c 使 用的二维s l m d 结构基本都是结构受限的二维s l m d 结构，这些结构自身的限制 也给开发有效的编译技术设置了难度。二维s i m d 结构编译技术研究滞后造成的 直接后果是各种采用二维s i m d 结构的很多系统还处于手动编写汇编代码的编 程模式，不仅不利于缩短产品的开发周期，也给二维s i m d 结构应用程序的开发 增加了难度。 目前只有【6 1 【7 l 在s a - c 语言【3 1 】的基础上对二维s i m d 结构的编译优化进行 了研究，但在生成二维s i m d 结构的代码时，采用的优化方法是基于s a c 语言 提供的一些特性匹配应用程序中的固定模式，同时在他们的研究中，对应用程序 的并行特性也进行了一些假设，这些关于程序并行特性的假设与实际应用程序的 并行特性间存在定的差异，因此采用这种方法实现的编译器具有很大的局限 性。 数据划分是指将数据映射到各个处理单元中的过程，能使程序执行时有良好 的数据局部性，由于能够充分利用数据局部性，所以是用来解决数据通信受限的 一项十分重要的技术。传统的数据划分主要适用于分布式存储模型，然而由于二 维s i m d 结构和其具有一定的相似性，可以考虑将数据划分技术运用n - - 维 s i m d 优化过程中。 数据划分由于和计算划分内在相关，需要兼顾获得最大的计算并行性的同时 考虑到数据的局部性，本身就是非常复杂的一个问题，而当运用到二维s i m d 结 第一章引言 构时由于结构的特殊性使划分的问题更加复杂。一种通用的划分方法是通过程序 员指定数据划分的方式，尽管这种方式可以获得较好的性能，但他们要求程序员 参与到复杂的程序内联的计算和数据划分中并且要求熟悉底层的硬 牛系统。尽管 有许多传统的数据划分方法：【9 】【1 8 】【19 】提出了一个可以同时兼顾计算和数据划 分的对确定的数据表示有效的算法，【1 3 1 4 利用传统共享存储模型上的t i l i n g 等方法划分，【1 5 【16 】【17 】使用仿射变换的方法划分程序语句来减少数据通信， 但是它们都只适合于分布式存储模型，不适合二维s i m d 结构优化。 1 3 本文的贡献及结构安排 我们针对二维s i m d 结构编译技术的不足，提出了一种基于数据划分的编译 优化方法。算法在结合数据划分的基础上，对程序计算部分进行划分并映射到不 同的处理单元上，使之具有很好的并行性同时能够兼顾降低数据通信的要求。此 外在进行数据划分的编译优化过程中，我们根据多媒体应用程序的特点和功耗芯 片面积对体系结构限制研究分析了不同设计参数对于二维s i m d 结构性能的影 响，并提出了结构改进的建议。 文章余下部分如下组织，在第二部分我们介绍了二维s i m d 结构，然后在第 三部分中分析了多媒体应用程序的特点并在第四部分中给出了体系结构的性能 模拟器的设计与实现。在第五部分中给出了基于数据划分的二维s i m d 编译优化 的具体过程，之后的第六部分中研究分析了不同设计参数对结构性能的影响。我 们在第七部分中给出了实验数据并在第八部分给出了文章的结论和进一步工作。 第二章= 维s i m d 体系结构分析 第二章二维s i m d 体系结构分析 2 1 单指令多数据流s i m d 单指令多数据流( s i m d ) 就是指s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t a s t r e a m ，它用一个控制器来控制多个处理器，同时对一组数据( 又称“数据向量1 ) 中的每一个分别执行相同的操作以实现空问上的并行性。s i m d 计算利用大量 处理单元对向量所包含的各个分量同时进行运算，这正是它获得很高处理速度 的主要原因。与同样擅长于向量处理的流水线向量处理机相比，s i m d 计算依 靠的并行措施是资源重复，而不是时间重叠。所以，在硬件价格大幅度下降， 加上系统结构的不断改进的情况下，s i m d 计算具有较好的性能价格比。而且 在提高运算速度方面，s i m d 计算主要依靠增多处理单元的个数，其提高速度 的潜力相当大；如果有很好的互连网络相配合，则多处理单元的功能和灵活性 将会更强一些。例如i n f e i 的m m x 、s s e 、s s e 2 、s s e 3 指令和a m d 的3 dn o w ! 技术即是其在微处理器中实现，以一个控制器控制多个行的处理微元。图2 1 为s j m d 执行方式示意图： i n e x t i n s t r i | a ( 1 ) + b ( 1 ) i l p r e yi n s t ri i n e x tn s i r ia ( 2 ) + b ( 2 ) ip r e v i n s t r l n e x t i n s t r i a ( 3 ) + b ( 3 ) ip r e y i n s t r l n e x t i n s t r ia ( 4 ) + 8 ( 4 ) l p r 南i n s t r p r o c e s s o r1 p r o c e s s o r2 p r o c e s s o r3p r o c e s s o r4 图2 1 s i m d 执行方式示意图 2 。2 二维s i m d 体系结构简介 近年来v l s i 技术飞速发展，2 0 年前花费上亿美元开发的并行系统现在能 以较低的成本集成到一个芯片上来实现。原本应用在并行处理领域的二维s l m d 第二章= 维s i m d 体系结构分析 结构逐渐引起学术界重视，许多大学和研究机构设计了基于二维s i m d 结构的 多媒体处理芯片。这些芯片对目前各种主流的多媒体应用都获得了很好的加速 比。随着各个大学和研究机构对二维sj m d 结构研究的深入，采用二维s i m d 结构作为多媒体加速部件在嵌入式领域广阔的应用前景逐渐引起了工业界的关 注。许多公司加入到二维s i m d 结构的研究中，一些公司已经推出基于二维 s i m d 结构的s o c ( s y s t e mo nc h i p ) 。表2 1 给出了比较具代表性的使用二维 s l m d 结构作为多媒体加速部件的s o c 。 产品名称研究机构备注 m a t n x m l t m o r p h o s y su n i v e r s i t yo fc a l i f o r n i a ，i r v i n e r e m a r cs t a n f o r d v i s i o nc h i p s u n i v e r s i t yo ft o k y o m o t o r o l a6 0 11m o t o r o l ai n c f a s t m a t h i n t r i n s i t yi n c m ，d s p m o r p h ol e c hi n c m g a p 2i n t e lc o r p o r a t i o n ，f o l s o m 表2 1采用二维s i m d 结构作为多媒体加速部件的s o c 二维s i m d 结构通常作为多媒体加速部件集成到通用处理器芯片( 一般为类 m i p s 核) 上，通用处理器核完成应用程序中的串行部分的处理和对其它功能单 元的控制，二维s i m d 结构作为多媒体加速部件在通用处理器核的控制下，完 成对各种应用中计算密集，数据并行性比较好的部分的处理。 二维s i m d 结构为由n x n 的处理单元p e ( p r o c e s s i n ge l e m e n t ) 组成的阵 列结构，各p e 按一定的拓扑结构连接，同行，列的p e 能够在通用处理器核的 控制下以s i m d 方式工作，不同的行，列相当于单独的s l m d 功能部件。图2 2 所示为一个8 x 8 的二维s i m d 结构示意图。二维s i m d 结构在任何一个维度上 都可以视作是一个典型的s l m d 结构，各行或各列可以执行不同的运算操作形 成多个s i m d 操作同时进行的结构。 第二章二维s i m d 体系结构分析 图2 28 x 8 二维s i m d 结构示意图 处理单元( p r o c e s s i n ge l e m e n t ) - - 般由定点操作运算器、乘法器和一个寄 存器堆组成，在通用处理器核的指令控制下从相邻的处理单元或者寄存器中 取数进行定点运算并输出结果或者保存在内部寄存器中，相当于一个微型的 处理器。图2 3 为一个典型的p e 结构示意图。处理单元之间的连接方式决定 了数据通信的方式，每一个p e 可以和相邻的p e 交换数据，也可以和同一行 或同一列的p e ，甚至可以和任何一个p e 交换数据，这取决于设计时的连接 方式的设计。 图2 3 处理单元的典型结构示意图 第二章二维s i m d 体系结构分析 二维s i m d 阵列由于在进行运算时需要大量的数据，所以阵列和外部内 存的数据交换需要高速的数据通路来保证运算所需的数据。一般阵列和外部 主存之间存在特殊的数据通路进行数据交换，如图2 4 二维s i m d 结构整体 架构图所示的d a t ai n t e r f a c e 。 f 一一一一一一一一一一一一一一一一一一 图2 4 二维s i m d 结构整体架构图 2 3 二维s i m d 结构所受的限制 1 i i i l l l i i l l l j 出于能耗和芯片面积的考虑，绝大多数二维s i m d 结构加入了复用数据通 路和p e 之间连接受限的限制。复用数据通路指的是在二维s i m d 结构与外部 内存交换数据时，多s i m d 行，列复用一条数据通路，而数据通路宽度只能满足 一行，列s i m d 的数据需求，因此如果希望充分利用计算资源提供的并行特性， 多个s i m d 行，列并行执行，必然造成多行，列s i m d 操作对数据通路的竞争。而 p e 之间的连接方式决定了p e 之间的数据通信方式，由于功耗和面积的限制， 连接方式至多为相邻相连加上同行，列共用一条总线传递数据，这种相连方式造 成了不同s i m d 行，列之间数据通信的竞争。 一 ，1 第二章= 维s i m d 体系结构分析 这些限制给二维s i m d 优化带来了巨大的挑战，优化的方法需要能够尽可 能的缓解应用程序对二维s i m d 结构执行时加载数据的压力，有效的提高二维 s i m d 结构的并行性。同时算法还应该考虑到执行时p e 之间连接所受的限制， 使计算时的数据具有最大的局部性，降低p e 之间的数据通信开销。 第三章模拟器设计与实现 第三章模拟器设计与实现 为了迸一步研究分析二维s i m d 结构和优化方法的实际效果，我们需要一个 可以测试效果的实际平台，使用硬件平台存在着成本高灵活性差的缺点，因此我 们基于s i m p l e s c a l a r 8 设计实现了一个可变参数的二维s i m d 体系结构的性能 模拟器，并在g c c 工具链上实现了编译、汇编和连接工具。 3 1s i m p l e s c a l a r 模拟器简介 s i m p l e s c a l a r 模拟器是一套被广泛使用的体系结构模拟系统软件，通过接收 输入的程序或者系统状态段经过模拟执行后输出结果和执行性能相关的数据( 包 括c y d e 数，c a c h em i s s 等数据) 。s i m p l e s c a l a r 通过采用指令驱动技术( a p 由目 标指令仿真器对每一条指令进行解释，通过解释的结果驱动性能模拟器) 将功能 模拟和性能模拟结合起来协同工作，对于系统调用和i 0 指令s i m p l e s c a l a r 将其 转换成对操作系统的系统调用，并将结果返回给相应指令。图3 1 为s i m p l e s c a l a r 模拟器设计图： 图3 1 为s i m p l e s c a l a r 模拟器设计图 s i m p l e s c a l a r 包含功能模拟和性能模拟的模拟器，其中的s i m - o u t o r d e r 是一 个近似动态调度处理器的性能模拟模拟器，能够提供给我们所需的执行时的统计 信息，为软硬件开发提供测试数据。s i m - o u t o r d e r i 作的模式为乱序执行的流水 第三章模拟器设计与实现 线工作方式，流水线分为以下五个段：f e t c h 、d i s p a t c h 、e x e c m e m 、w d t e b a c k 、 c o m m i t 。 s i m - o u t o f o r d e r 的主函数s i r n _ m a i n 0 主干是一个死循环，它的流程完全模拟 流水线的处理过程，不同的是由于模拟的需要将流水的顺序逆转，以使逻辑上的 流水站不要提前处理要下一拍才能处理的指令。模拟结束通过信号量返回主函数 m a i n ( ) ，退出。5 级流水如下执行，在每个流水周期结束后，c y c l e 需要加。1 ”： r u u _ c o m m i t o - r u u _ w r i t e b a c k o - * r u u _ i s s u e o - - r u ud i s p a t c h 0 - - r u u _ f e t c h ( ) 3 2 二维s i m d 阵列的模拟实现 二维s i m d 部件由n x n 个处理单元( p e ) 按照一定的拓扑结构组成，首先我 们需要实现一个p e 部件，我们采用类似一个简单c p u 核的实现，根据p e 结 构定义其内部各器件的实现，包含寄存器堆，运算器和乘法器等，数据结构如图 3 1 2 所示： t y p e d e fs 恤t 正j t n 】c t ( r 呼jr 昭s r f g s _ n u m , 处理单元p e 的通用寄存器堆 r c g s _ to u 【p 咄 ，处理单元p e 的存放结果的寄存器 a t u 功能部件运算器的指针t * a l u ； , i m u l t it * m u l t i ：功能部件乘法器的指针 w o r d1 6 盘g ，处理单元p e 的标志位 c o n t 耐_ tc o n t e x t ； 处理单元的指令存放寄存器 ) r ot ； 图3 2 处理单元的数据结构 其中a l u 和m u l t i 分别指向一个包含函数指针的运算器和乘法器结构类型，通过 函数指针使得运算器和乘法器的执行功能能够被配置到不同的运算器与乘法器 实现上，具体的功能根据p e 所支持的指令集实现。此外p e 的寄存器个数也可 通过宏配置。 二维s i m d 阵列结构由一个参数配置的二维数组表示，数组的基本类型即为 上述p e 数据结构，而p e 之间的相连方式信息我们保存在一个基本类型1 6 b i t s 整形的二维数组中，一个b n 指代与同行或列的某个p e 相连与否。 第三章模拟器设计与实现 3 3 整合二维s i m d 阵列与通用处理器 二维s i m d 结构作为多媒体加速部件与通用处理器核共同组成s o c 系统， 所以在模拟二维s i m d 执行的时候需要将其和通用处理器结合在一起模拟才能 得到准确的性能数据。我们沿用s i m p l e s c a l a r 提供的通用r i s c 核部分，需要 将二维s i m d 部件的执行结合到r i s c 核的五级流水线执行中，即f e t c h 、 d i s p a t c h 、e x e c m a m 、w r i t e b a c k 和c o m m i t ，并添加控制二维s l m d 阵列的指 令集的实现。 二维s i m d 作为多媒体加速部件，在指令i s s u e 的时候需要判断是否已经被 占用，如果此时二维s i m d 部件空闲则流出指令并置部件忙，否则将指令放入 r u u ( r e g i s t e ru p d a t eu n i t ) 队列中，r u u 队列保存的是指令因为所需功能部件 忙而等待计算。丽在c o m m i t 的时候还需要判断是否从二维s i m d 结构中获得数 据写到内存中，这个时候也需要判断二维s i m d 部件的状态，如果忙则将指令放 入l s q ( l o a ds t o r eq u e u e ) 队列中。l s q 保存的是指令因为访存操作时功能单 元忙而等待。在整合了流水线执行过程后，我们只需加入操作二维s l m d 的指令 集到原有的指令集中就完成了二维s i m d 部件与通用处理器的整合。图3 3 为整 合的流水线执行图： 图3 3 整合二维s l m d 部件后流水线执行图 控制二维s i m d 阵列的指令集包括为阵列存取数据、读取指令、以行或列 s i m d 方式执行指令、直接写回结果等，这些指令直接操作二维s i m d 阵列运行 以获得运算结果。表4 1 为我们实现的典型指令集： 第三章模拟器设计与实现 指令名指令编码指令说明 l d c t ) 汀o x e 0 将控制指令读入二维s l m d 指令缓存 l d f bo x e l将数据读入二维s l m d 数据缓存 s t f b 0 x e 2 将数据写回外部主存空间 s b c b0 x e 3从缓存读取一个数据并进行s i m d 操作 d b c b c0 x e 4 从缓存读取二个数据并进行列s l m d 操作 d b c b r o x e 5 从缓存读取二个数据并进行行s i m d 操作 c b c a s to x e 6直接进行行s l m d 操作 w f 引0 x e 7 将阵列各p e 结果数据写回缓存( 地址用立即数表示) w f b0 x e 8 将阵列各p e 结果数据写回缓存 r c r i s c0 x e 9将一行p e 的结果数据写回缓存 表3 - 1 二维s i m d 控制指令集 上述的每一条指令的实现包括定义指令名称、指令编码、所需资源、执行方 式、操作数和结果类型等。然后我们需要在指令定义文件中编码实现该指令的具 体操作运算数并产生结果的过程。图3 4 例示了一条指令的定义和实现： # d e f i n ew f b i _ i m p l 、 ( 、 缸、 f o r ( i f f i o j 8 + ) 、 ( 、 i n t 囱t 阿c 引可b e tr 酷u l i ( 0 w f b c o l ) ： 、 期嗵丘锄扯b u m r 帆船吼eb l 撕；w f b s e t ， w f b _ b a n k , w f b _ b a n k a d d r + i 2 。瞳目： 、 ) 、 ) d e f i n s t ( w f b i 。0 x e 7 ， w 蹦。“。 r c a r r a y ,f - i ， d n a , d n a , d n a , d n a , d n a ) 图3 4 二维s i m d 控制指令w f b i 的定义和实现 3 4 编译工具链的实现 为了测试所实现的二维s i m d 模拟器，我们需要一套编译的工具链来产生可 第三章模拟器设计与实现 以运行在模拟器上的二进制程序。我们在开源项日g c c - 3 3 和g n ub i n u t i l s 一2 9 5 基础上构建了可生成运行于二维s i m d 模拟器上的二进制代码的c o m p i l e r 、 a s s e m b l e r 以及l i n k e r 。对于编译器的修改是增加了对应于每一条二维s i m d 控 制指令的内嵌函数，这样可以使经过我们优化的源程序能够以内嵌函数的方式运 用二维s i m d 阵列。在汇编器上我们针对每一条指令实现将其汇编为二进制编 码，以使之能够在模拟器上执行。 第四章多媒体程序特性分析 第四章多媒体程序特性分析 4 1 程序包简介 对于多媒体程序分析来说，基准程序( b e n c h m a r k ) 或者程序集( w o r k l o a d ) 是非常重要的。因为多媒体程序非常多，而且版本也非常众多，显然分析人员 无法枚举所有的程序。所以就有各种机构选取了各种具有代表性的程序组成基 准程序包来方便大家的分析工作。其中比较有代表性的是b e r k e l e ym u l t i m e d i a w o r k l o a d 【2 0 】。这是美国加州大学伯克利分校提出的一套多媒体程序集。这套 程序集以m e d i a b e n c h 为基础，在程序的数量、广度上都进行了扩展。同时， 这个程序包还在数据集上进行了比较大的改进，提供了比较大的数据集以保证 程序在现代处理器上也能有比较长的运行时间。 b e r k e l e ym u l t i m e d i aw o r k l o a d 是一个用标准c c + + 语言实现的多媒体应 用程序包，由于采用了完整的多媒体应用作为测试程序，使得这个测试包更能 反映多媒体应用的真实需求，另一方面对数据也进行了仔细的筛选，使得测试 结果更具有代表性 2 1 】【2 2 】f 2 4 】f 2 5 】。此外还有以下两个重要的特点： 1 它是完全开源的。所有源代码和数据都可以免费得到。 2 其作者不光设计了这个程序包，而且还对其进行了大量的分析。 我们从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 ) 中选取了最有代表性的 m p e g 2 、j p e g - e n c o d e r 和i d e a 程序以及在其中经常使用到的核心代码 m e ( m o t i o ne s t i m a t i o n ) 和矩阵乘法构成我们的基准测试程序包。此外还添加了 类似i d e a 的3 - w a y 加解密程序作为测试程序的补充。 4 2 多媒体程序运行时的特点 b m w 的作者对于多媒体程序和科学计算时的运行时特点进行了比较【2 3 】。 他的比较是在d e c a l p h a 平台上进行的，采用的多媒体程序包是b m w ，科学 计算程序包是s p e c 9 5 。对于这些程序来说，比较都是基于标量版本进行的。 他从如下几个方面进行了比较并得出相应结论。 指令比例：虽然这些程序包在指令的总体分布上比较相似，但是科学 第四章多媒体程序特性分析 计算有更多的浮点计算，而多媒体应用程序更加强调移位( s h i f t ) 和逻辑 ( l o g i c a l ) 运算。 数据宽度( d a t aw i d t h ) ：对于s p e c 9 5 面言，其位宽变化比较平缓， 而对于b m w 中的程序，其位宽变化很剧烈。般来说，视频程序使 用1 2 位左右的精度，音频程序使用1 6 位，而其他程序没有明确的精 度特定。 潜在指令并行性：对于多媒体应用程序来说，平均基本块长度达到1 4 条指令，而s p e c 9 5 只有7 条指令，这说明多媒体程序比一般整型运 算程序有更大的并行性。此外，多媒体程序有更高的可预测性，一个 值得注意的特点是条件跳转往往在7 和1 5 次处发生跳转情况变化。这 和多媒体程序中视频和图象处理算法的循环长度有很大关联( 例如 m p e g 2 算法的基本处理单元是8 x 8 的子块和1 6 x 1 6 的宏块) 。 局部性：通过分析b m w 的c a c h em i s s 比率对于c a c h e 大小的变化 关系，并与其他研究成果相对比，b m w 的作者得到的结论是多媒体程 序的数据局部性比一般程序要好。 程序时间分布：通过分析多媒体程序中每一行代码所花时间的多少， 作者得出结论，多媒体程序具有非常明显的h o t s p o t 特征。某些核心代 码片断占据了绝大部分的执行时间。此外，不同程序的h o t s p o t 代码具 有很多相似的地方。 从这些特点我们可以看出，多媒体应用程序的数据宽度都比较小，具有很 好的指令集并行能力，程序的h o t s p o t 特征也非常明显，这些都使得二维s i m d 结构非常适合于处理多媒体程序。 4 3 代码形式特点 在对我们选取的测试包程序分析的过程中，我们发现多媒体程序源代码在 形式上具有以下的一些特点。 4 3 1 广泛使用指针进行计算 我们选取的程序包中所有的程序都是c c + + 代码的，这些代码中指针的运 第四章多媒体程序特性分析 用非常的广泛。对