（电路与系统专业论文）基于SIMD的媒体处理器的数据存储与组织体系结构优化研究[电路与系统专业优秀论文].pdf

浙江大学硕士学位论文 摘要 摘要 基于s i m d 技术的媒体处理器在多媒体处理领域凭借着其良好的可 编程性和高性能而备受关注。但是其性能的进一步提高却受制于一些非 运算的因素，也就是通常所说的数据存储与组织。这主要是由多媒体处 理的数据访问的灵活性和s i m d 技术对算法的规整性的高度依赖性所导 致。为了进一步的开发基于s i m d 技术的媒体处理器的性能，本文分别 从数据组织和存储两个方面来对其进行体系结构的优化。 首先，在数据组织方面，本文提出了一种基于显式数据置换的 e d o s i m d 指令集体系结构。它将数据置换信息显式地声明在了指令字 当中，同时将数据置换操作与数据计算和存储操作结合起来，通过这样 的方法来降低由数据组织指令所带来的非计算开销。本文还给出了在一 个b a s e l i n es 1 m d 媒体处理器的基础上实现e d o s i m d 指令集体系结构 的方法。基于h 2 6 4 a v c 实时解码器的b e n c h m a r k 实验结果表明，在仅 仅只在硬件面积上增加了o 4 9 的情况下，所提出的e d o s 1 m d 可以达 到1 3 4 1 4 0 的性能加速比以及减少1 7 7 的代码长度。 然后，本文分别从两个方向上探讨了s i m d 媒体处理器的片上存储 系统的优化方案。其一是研究如何能将流访问与面向二维逻辑数据空间 的并行存储器结合起来，在这个方面，本文提出了一个基于地址交织的 二维流存储系统。该存储系统完成了二维逻辑空间到物理空间上并行存 储器模块的映射。数据在物理存储器上进行了交织存放以支持行阵列和 列阵列的同时访问。该交织算法在之前的交织算法基础上做了面向流访 问的改进。基于h 2 6 4 a v c 实时解码器的b e n c h m a r k 实验结果表明，所 述的二维流存储系统可以减少平均约3 2 o 的存储器访问率以及2 5 4 的实时处理中所需的时钟周期数。 在另一方面，本文致力于研究如何改进传统的基于线性偏差的地址 浙江大学硕士学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 交织策略来解决其存储器冗余和无法支持模寻址的问题。本文提出了一 种优化的基于线性偏差的交织策略，它采用了2 p q ( p q 表示并行的数据 通路路数) 个存储器模块。为了克服在这种情况下带来的存储器模块冲 突，所提出的交织策略在二维逻辑数据空间的水平方向上采用了线性的 地址偏差，而在垂直方向上采用了非线性的地址偏差。实验结果表明， 与之前的线性偏差交织策略相比，在p q = 4 或8 的情况下，这里所提出 的优化交织策略可以减少平均1 3 6 的片上存储器面积；在运动估计的 b e c h m a r k 的测试下，可以减少平均3 5 5 的片外存储器的带宽。 关键词：s i m d 媒体处理器，显式数据组织，e d o s i m d ，流访问，二 维存储系统，交织策略 浙江大学硕士论文 a b s t r a c t a b s t r a c t s i m dm e d i ap r o c e s s o r sh a v eb e e nw i d e l yk n o w na n du s e di nt h ea r e ao f m u l t i m e d i a p r o c e s s i n g b e c a u s eo ft h e i r g o o dp r o g r a m m a b i l i t y a n d h i g h p e r f o r m a n c e h o w e v e r , t h ef u r t h e re n h a n c e m e n to ft h e i rp e r f o r m a n c ew i l lb e r e s t r i c t e d b yt h e b o t t l e n e c kr e s u l t e di nb yt h e n o n - c o m p u t i n go p e r a t i o n s ， r e e o g a n i z e da st h ed a t as t o r a g ea n do r g a n i z a t i o n t h i si sm a i n l yb e c a u s et h e f l e x i b i l i t yo ft h ed a t aa c c e s si nm u l t i m e d i ap r o c e s s i n ga n dt h eh i g hd e p e n d e n c e o ft h es i m dt e c h n o l o g yu p o nt h ea l g o r i t h mr e g u l a r i t y t of u r t h e re n h a n c et h e p e r f o r m a n c eo ft h es i m dm e d i ap r o c e s s o r , h e r ew ep r o p o s e ds o m ea r c h i t e c t u r a l o p t i m i z a r t i o nf o rt h ed a t ao r g a n i z a t i o na n ds t o r a g er e s p e c t i v e l y f i r s t l y ，f o rt h ed a t ao r g a n a t i o n h e r ea ne x p l i c i td a t ao r g a n i z a t i o ns i m d ( e d o s l m d li n s t r u c t i o ns e ta r c h i t e c t u r ei sp r o p o s e dt or e d u c et h eo v e r h e a d r e s u l t e di nb yt h ed a t ao r g a z a t i o no p e r a t i o n s i te x p l i c i t l yd e s c r i b e dt h ed a t a p e r m u t a t i o ni n f o r m a t i o n i nt h ei n s t r u c t i o nw o r da n dm e r g e dt h ed a t ao r g a n i z a t i o n o p e r a t i o nt ot h ed a t ac o m p u t a t i o na n ds t o r a g eo p e r a t i o n s a ni m p l e m e n m t i o no f e d o s i m di s ab a s e do nab a s e l i n es i m dp r o c e s s o ri sd e s c r i b e d s i m u l a t i o n r e s u l t ss h o wt h a t ，c o m p a r e dt ot h eb a s e l i n es i m da r c h i t e c t u r e ，e d o s i m di s a c a na c h i e v e1 3 4t o1 4 0s p e e d u p sf u rt h eb e n c h m a r ko fr e a lt i m eh 2 6 4 a v c d e c o d e ra n dr e d u c e1 7 。7 o f t h ec o d es i z ew i t ho n l yo 4 9 i n c r e a s ei nh a r d w a r e a f e a s e c o n d l y ，a si tc o m e st ot h eo n - c h i pd a t as t o r a g e ，w eo p t i m i z e di tf r o mt w o a s p e c t s o n ei s t oc o m b i n et h es t r e a ma c c e s sw i t ht h e2 - dp a r a l l e lm e m o r y s y s t e m h e r ew ep r o p o s e da ne f f i c i e n t2 - ds t r e a mm e m o r ys y s t e m i tm a p sa2 - d l o g i cs p a c eo n t op h y s i c a lp a r a l l e lm e m o r ym o d u l e s d a t aa r ei n t e r l e a v e di nt h e m e m o r yi no r d e rt os u p p o r tb o t hh o r i z o n t a la n dv e r t i c a la r r a ya c c e s s t h e 塑垩盔兰堡兰垡堡兰：兰! ! 翌旦塑鉴竺竺墨矍竺墼堡鱼堡皇望堡竺至竺塑垡些里塞 i n t e r l e a v es c h e m ei si m p r o v e df o rs t r e a m i n ga c c e s sb a s e do nt h ep r e v i o u s i n t e r l e a v es c h e m e s e x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h ep r o p o s e ds t r e a mm e m o r y s y s t e m c o u l dr e d u c e3 2 o o ft h em e m o r ya c c e s s r a t ea n d2 5 4 o ft h e e x e c u t i o nc y c l ec a 3 u u t sf o rr e a lt i m eh 2 6 4 a v cd e c o d e rb e n c h m a r k o nt h eo t h e rh a n d ，w ea r ca i m e dt or e m o v et h em e m o r yr e d u n d a n c yo ft h e p r e v i o u sl i n e a rs k e w i n gi n t e r l e a v es c h e m ea n dt r yt os u p p o r tm o d u l oa d d r e s s i n g h e r e ，a l lo p t i m i z e dl i n e a rs k e w i n gi n t e r l e a v es c h e m ei sp r o p o s e d t h ep r o p o s e d s c h e m ec a l ls u p p o r ts i m u l t a n e o u sa c c e s s o fm u l t i p l es u b a r t a yt y p e so fd a t a e l e m e n t si na2 - dd a t as p a c ew i t hm o d u l oa d d r e s s i n g 2 p q ( p qi st h en u m b e ro f p a r a l l e lw a y s ) m e m o r y m o d u l e sa r eu s e dw i t h o u tr e d u n d a n c yt os a v et h eo n - c h i p m e m o r y i tu s e sl i n e a rs k e w i n gi nt h eh o r i z o n t a ld i r e c t i o na n du s e sn o n l i n e a r s k e w i n gi nt h ev e n i c md i r e c t i o n r e s u l t ss h o wt h a tc o m p a r e dt op r e v i o u sl i n e a r s k e w i n gs c h e m e s t h ep r o p o s e ds c h e m ec a nr e d u c e13 6 o f t h eo n c h i pm e m o r y f o rc a s e so f p q = 4o r8a n dr e d u c e3 5 5 o ft h ee x t e r n a lm e m o r yb a n d w i d t hf o r b e n c h m a r ko f m o t i o ne s t i m a t i o nd u et om o d u l oa d d r e s s i n g k e y w o r d s ：s i m dm e d i ap r o c e s s o r , e x p l i c td a t ao r g a n i z a t i o n ，e d o s i m d ， s t r e a ma c c e s s ，2 - dm e m o r ys y s t e m ，i n t e r l e a v es c h e m e 浙江大学硕七学位论文图目录 图1 1 图1 2 图1 3 图1 - 4 图1 5 图1 6 图2 1 图2 2 图2 3 图2 - 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图3 1 图3 2 图3 3 图3 - 4 图3 5 图3 - 6 图3 7 图3 8 图3 - 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图目录 视频应用数据类型和精度的分布4 c 语言表示的f i r 滤波器核心算法6 s i m d 数据类型和1 6 b i tp a c k e d 加指令6 e l i t e 的数据组织方案9 e l i t e 不同指令的的流水线划分9 子字黄换单元( s p u ) 结构框图【1 8 】l o 指令示例：a d d o bv r 0 ，v r l ，v r 2 1 7 指令示例：s t o bb o 【o 】，v r 2 1 7 a d s p 与e d o s i m d 的指令集体系结构的比较1 8 e d o s l m d 指令集体系结构可行的指令编码方案2 0 b a s e l i n es i m d 和e d o s i m d 体系结构框图2 2 f i r 核心的主要数据操作2 4 数据置换网络的微体系结构2 5 采用e d o s 1 m di s a 实现的f i r 核心2 8 一维8 x 8i d c t 的数据流程图2 9 采用e d o s i m d1 s a 实现的一维8 8i d c t 核心2 9 支持流访问的二维逻辑空间3 8 按列排列的数据阵列在不同的粒度下的排列形状4 0 数据在物理空间中的基于流的存放4 0 地址计算式( 3 4 ) 和( 3 6 ) 的数据流程图4 2 存储器模块分配示例4 4 存储器地址偏差示例4 6 存储器地址路由示例5 0 地址发生单元( a d g ) 的微体系结构图5 2 二维流存储存储系统体系结构实现框图5 2 基于4 x 4 块的去块效应的并行化策略5 5 支持模寻址的二维数据空间的各种数据阵列6 1 基于优化的线性偏差地址交织策略的存储系统示例实现框图7 0 基于优化的线性偏差地址交织策略的存储器模块分配示意图7 l 基于优化的线性偏差地址交织策略的存储器地址分配示意图7 l 示例s r a ml 中的内容一7 2 示例s r a m 2 中的内容7 2 1 1 1 浙江大学硕卜学位论文：基于s 1 m d 的媒体处理器的数据存储与组织体系结构优化研究 图4 - 7 模寻址在运动估计中的运用7 7 浙江大学硕士学位论文 表目录 表目录 表1 1传统s i m d 指令集体系结构的时钟分布【4 】3 表2 1 仿真器在模仿的一个时钟周期里执行的步骤3 1 表2 2 多媒体处理核心级的性能加速结果3 4 表2 3 多媒体处理应用级的性能加速结果3 5 表3 1 存储器模块使能信号表4 4 表3 2 基于快速搜索算法的比较结果5 4 表3 3 基于去块效应滤波的时钟周期比较结果5 5 表3 - 4 基于h 2 6 4 ，心r c 解码器的比较结果5 6 表4 1p a r k 2 7 1 中的存储器冗余5 9 表4 2s r a m l 中的各个数据阵列的表项长度6 7 表4 3 片上存储器需求的比较结果7 5 表4 - 4 片外存储器的带宽需求的比较结果7 8 表4 5 地址发生与路由( a g d r ) 电路模块比较结果7 9 表4 6 面积和时延的比较结果8 0 v 第1 章绪论 1 1 媒体处理器与s i m d 近年来，多媒体产业取得了飞速增长。因特网的成功和图像视频压缩技 术的快速发展使得多媒体成为了计算业的主流。多媒体应用的处理要求也伴 随着用户的更新和更好的应用需要而急速增长。许多当前的多媒体应用的处 理要求已经超出了普通微处理器的计算能力上限，而且下一代的多媒体将包 含更大范围的应用也就意味着更高的计算和处理能力要求。为了更好的支持 未来的多媒体处理，需要在当前的处理器技术基础上寻求更高的处理能力和 灵活性。对此，当前学术界和工业界有以下三种解决方案：【1 】 首先是专用集成电路( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) 方案。 这种方案实际上是一种硬件的解决方案。它可以通过对应用中的关键部分进 行硬件优化来获得高度的性能。这种方案是基于对算法的透彻分析以充分利 用算法与硬件结构相关的运算特性，设计的主要目标就是使专用结构最大限 度的与特定算法匹配，利用v l s i 技术高效的实现目的。不同的算法模块将 被映射到不同的硬件结构上。专用结构不需要取指令、指令译码、指令执行 等过程，也不需要额外的配置信息，这使得用于控制的冗余被大大精简。因 此，专用结构具有效率高，额外开销小，面积小和功耗低的优点。但是，由 于硬件的不可更改性，专用结构的缺点是只适用于某个标准或某个标准的某 个档次，不能对其他标准或档次做出扩展，缺乏灵活性。【2 】 然后是基于通用处理器( g e n e r a lp u r p o s ep r o c e s s o r , g p p ) 的多媒体指令 集扩展方案。这种方案的特点就是尽量在现有的通用处理器基础上通过采用 基于子字( s u b w o r d ) 的并行技术来提高多媒体处理性能。它主要利用了多媒 体处理的以下两个特点：其一，多媒体处理的数据单元一般都是8 位或1 6 位。其二，多媒体处理具有很高的运算规则性，也就是说大量的处理时间都 浙江大学硕l 学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 在内层循环( i n n e r l o o p ) 中，在每次迭代中都对不同的数据进行相同的操作。 正因为如此，在具有6 4 位或者更高的数据位宽的通用处理器中，把一个长字 看作若干个子字，然后通过一条指令就可以完成这些子字的并行处理。这种 技术也叫做单指令多数据( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ，s i m d ) 技术。这 种方案的优点是在现有的通用处理器基础上做很少的改动就可以满足当前多 媒体处理的需要，灵活性很强，但其缺点就是功耗和面积都相当可观，而且 通用处理器的体系结构是面向通用应用需要的而不是专门面向多媒体应用设 计的，因此在性能上无法满足未来多媒体应用对处理性能的高要求。 1 】 最后就是本文所侧重的专用指令集处理器( a p p l i c a t i o ns p e c i f i c i n s t r u c t i o ns e tp r o c e s s o r ，a s i p ) 方案。由于本文关注的是多媒体处理应用， 面向这一类应用的a s l p 一般被称为媒体处理器( m e d i ap r o c e s s o r ) 。相比较 前两种方案，媒体处理器是在二者之间，在性能和灵活性方面做了一个折中。 一方面，它具有a s i c 的专用性，内部集成了针对应用的硬件和软件l p 核， 具有很好的性能，提高了整体的面积利用率同时也降低了功耗。另一方面， 它又有通用处理器的可编程功能，提高了设计的灵活性。 由于s i m d 体系结构在前述的基于通用处理器的多媒体指令集扩展方案 上取得了巨大的成功，它成功了利用了多媒体处理的特性，使采用较少的硬 件代价来获取较高的并行处理特性成为可能。因此，在媒体处理器的设计中， s i m d 技术也得到了广泛的使用。典型的s i m d 处理机的结构由一个控制器 和多个处理单元( p r o c e s s i n ge l e m e n t ，p e ) 组成。通过单个控制器的控制以 前后紧接的方式处理多个独立的p e 操作。传统上说，s i m d 处理机提供了一 个有限的p e 问的规则互连。【3 】 1 2 基于s i m d 的媒体处理器的瓶颈 由于设计基于s i m d 的指令集体系结构( i n s t r u c t i o ns e t a r c h i t e c t u r e i s a ) 方法学对于基于通用处理器的扩展指令集设计和基于媒体处理器的设计有着 很大的相似性，因此二者在一些关键性的瓶颈问题上有着共通之处。不同的 是，对于媒体处理器则可以通过体系结构级的优化来消除这些瓶颈问题。 表1 1 给出了当前一些s t a t e o f - a r t 的s i m d 指令集体系结构的时钟分布 信息【4 1 。从中可以看出，s i m d 处理器在处理时有1 2 - - 1 8 的时间是用在了 数据存储上，还有1 0 - 一1 7 的时间是用在了数据组织上。与此同时，只有大 约1 4 - - 2 8 的时间是用在了数据计算上。从这里可以看出，要想提高基于 s i m d 的媒体处理器的性能，根据a m d a h l 定律【5 】，单纯优化数据通路( d a t a p a t h ) 是无法显著提高整体性能的。当数据通路被高度优化后，数据存储和 数据组织就变成了整个体系结构的瓶颈。 表l l 传统s i m d 指令集体系结构的时钟分布【4 】 v l sm m x ，s s ea i t i v e c 数据存储指令 l 】7 2 1 0 1 7 9 数据组织指令 9 7 1 2 6 1 7 o 整型运算指令 1 3 6 1 8 8 1 】8 浮点运算指令 9 3 6 9 是什么原因导致s i m d 处理器要花费这么多时间在数据存储与组织上 呢? 这要从多媒体处理的特性去分析。这里以多媒体处理中最为复杂的视频 信号处理为例，如图1 1 所示，一帧图像中的视频数据具有以下特点： 1 ) 数据存取是建立在一个二维的逻辑空问中，而且多是按块( b l o c k ) 进行操作。 2 ) 数据存取都是矢量的操作，一次同时存取一个包含多个数据单元的数 据阵列，同时该数据阵列要求在二维逻辑空间中能够按行和按列排列，对数 据阵列的访问强调同时性。 3 ) 操作的数据单元的粒度多样化( 8 ，1 6 位共存) ，以及数据单元要可 以按字节寻址。 浙江大学硕仁学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 图i - 1 视频应用数据类裂和精度的分布 对于传统的通用处理器而言，它的片上存储器通常只包含一个存储器模 块，这个存储器模块的一个e n t r y 就是一个字，每个字又被分为若干个子字 从而进行子字的并行。其中地址是按字( w o r d ) 对齐的。假如要访问的数据 也是严格的按照字进行地址对齐的话，那么这种子字并行的体系结构将工作 的非常完美而且数据通路也将被充分利用。可是在多媒体处理中，事实往往 并非如此，从而使得要想一个多媒体处理的应用能够完全利用所谓的子字并 行变的非常复杂。尤其是视频处理中的运动估计，该算法中的大量寻址都依 赖于高效的非对齐的地址访问，也就是说一个数据字可以从内存中的任意一 个位置开始。这种存储器模式被成为按字节对齐的模式。当前，地址按字节 对齐的重要性已经为一些高性能处理器所接受和支持。比如i n t e lp e n t i u m m m x 6 ，t e x a si n s t r u m e n t sc 6 2 x 【7 】，s t a r c o r e 【8 】，和t r i m e d i a 9 这一类处理 器，但是对于没有地址对齐的数据字的访问要比对齐的访问的时钟代价要高 一些，因为这里需要用l e f ts h i f t ，r i g h ts h i f t ，和b i t w i s eo r 指令对数据进行重 绪论 组，也就是需要数据组织指令来进行软件地址对齐。 对于媒体处理器的设计者来说，支持地址按字节对齐是一个非常重要的 设计要素。【l o l 6 e 提出了一种能够按字节寻址的面向视频处理的处理器体系 结构以此来大大缩减运行一个具体应用所需要的时钟周期数。这种在媒体处 理器设计中常用的存储体系设计是建立在这样一种基础上：所述的存储器系 统包含了多个存储器模块，每个存储器模块能提供一个子字的访问，多路并 行的存储器模块可以提供一个数据阵列的同时访问。如何将一个二维的逻辑 空间映射到这样的并行存储器系统中又是一个关键的设计点交织算法。 传统的交织算法【1 1 1 为：将一个数据单元的逻辑地址f 与并行存储器中的 存储模块数进行如下的运算。那就是将这个数据单元放在第t n 个存储模 块中的地址为i n 的地方上去。这种交织算法的最大优点就是算法简单，而 且当所为2 的幂的时候硬件实现上也非常简单。然而这种交织算法所支持的 数据阵列的排列形状很少，这在多媒体处理中将会成为制约性能的瓶颈。比 如对于一个垂直方向上的列的数据阵列按照这种交织算法将会被映射到一个 存储器模块中去从而使得其无法被同时访问，因为一个存储器模块在一次访 问中只能提供一个子字的访问。因此，如何优化地址交织算法使得并行存储 系统能够支持多种数据阵列的访问将成为媒体处理器设计的一个关键因素。 前面已经提到了在通过软件方式对地址进行按字节对齐时需要用到数据 重组指令。但是数据重组指令并不仅仅用在软件方式的地址按字节对齐上 对于基于s i m d 的媒体处理器，在多媒体处理中，一些核心算法还需要对从 存储器l o a d 到寄存器中的数据进行重新组织才能进入数据通路进行并行运算 处理。一个典型的例子为如图1 2 所示的f i r 滤波器的核心c 代码，为了进 行并行处理，必须将滤波器输入工多次移位然后将不同移位的结果与系数a 相乘，得到的结果再进行移位得到相应的滤波器输出y 。这样在软件实现上 就需要加入大量的数据组织指令。 5 浙江人学硕l 学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 f o r ( n = 0 ；n m 4 ；n + + ) f o r ( k 2 0 ；k a l as l o r a g e l k 匡嘲 ， 6 4 4 1 6 f彳4 1 6 ，p - 一 ，f n ，1 6 0 u m t r a i y iv m r - 1p a c k e dt l e m c n l s i 蕊麓白b t l 舯f i 舯幸1 6 0 * 棘岫厂r m 图l - 4e l i t e 的数据组织方案 iz 34s78 m s 亡庠d e cr d 斟w r o l h 盯h 疏t 狮州 i f d e c r dd 【 聒r w r v 岫wd c m e ml fd e cr dv pr dv ee x le v , 21 嘬 i n l r 毗t - m l i h m c i i m l fd e cr da gx f r l r d m x f r 2w r 图1 5e l i t e 不同指令的的流水线划分 隐式的数据组织方案有效地减少数据组织所带来的开销。但是由于数据 组织被隐藏在了地址置换中，这样要求编程人员需要熟悉v p r 的编程方法。 这样增加了应用软件开发的难度。而且，这种体系结构上的软件编程强烈地 依赖具体的硬件结构。换句话说，这样的软件缺乏在不同的采用隐式数据置 换的处理器上的可移植性。另外，从【1 7 仲可以看到，由于访问v e r 要通过 v p r 才可以，因此在具体的流水线划分上来讲，对于矢量的操作指令，其流 水线级数要比其他的标量指令以及控制类指令要多出一级来。如图l 一5 所示， 这里多出的一级即为对v p r 的访问。 为了开发基于子字( s u b w o r d ) 并行的技术，【i s 在针对i n t e lm m x 多 媒体扩展指令的研究基础上提出了在处理器的执行级流水线中加入了一个 9 浙江人学硕士学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 叫作子字置换单元( s u b w o r dp e r m u t a t i o nu n i t ，s p u ) 的装置的方案，如图1 - 6 所示。该s p u 被用来在数据进行运算处理前对其进行预先的重组，以使得 m m x 指令能够专注于计算。它的使用方法是，在对于一个算法中的l o o p 的 多次迭代中的各次数据组织，只需对s p u 进行一次配置即可使起按照预先配 置的方法去对将要参加计算的数据进行重组。加入这样的一个装置对整个硬 件的面积增加仅仅为1 ，但是它却带来了对于一些多媒体处理和信号处理 核心的4 到2 0 的性能增加。 图1 6 子字置换单元( s p u ) 结构框图【l s 】 这种方法的最大好处就是避免了对数据重组的额外指令操作，当l o o p 的 迭代次数越多，这种方案对性能提高的幅度就越大，显然，如果l o o p 的迭代 次数较少的话，对s p u 的在进入l o o p 前的初始配置的开销就无法忽略了。 这也正是这种方案的局限性所在。但是这种将数据组织嵌入在数据运算中， 使其与数据运算操作结合的思路确相当值得借鉴。 1 3 3 数据存储 【1 9 】中提出了一种非耦合的存取执行体系结构，它将整个体系结构从粗 粒度上分成了两个c l u s t e r ：一个c l u s t e r 分管数据运算工作，而由另一个 c l u s t e r 完成对数据存储的管理。这种体系结构通过将数据存储与数据运算进 行粗粒度的并行来减少由数据存储这类非运算操作所带来的开销。但是这种 消除方法仅仅停留在了粗粒度上，对于细粒度的数据访问并行并没有深入。 前面提到对于并行数据存储来讲一个很重要的问题就是地址交织策略的 改进。这里介绍一下学术界对于地址交织策略的一个研究历程。地址交织策 略可以从总体上被分为两大类：非线性偏差地址交织策略 2 0 2 3 1 和线性偏差 地址交织策略 2 4 2 7 1 。 绝大部分非线性偏差地址交织策略都是建立在b i t w i s ex o r 运算的基础 上的，这种思路最早被b a t c h e r 2 0 所提出。之后f r a i l o n g 等人【2 1 】将这种x o r 策略归纳总结如下：计算一个数据单元在一个存储器模块中的物理地址可以 被转化为一个将其逻辑地址与一个转换矩阵的点乘的运算。在x o r 策略中， 当存储器模块的数量为2 的整数次幂的时候，物理地址的计算和路由将变的 非常容易实现。但是，菲线性偏差地址交织策略往往受到如下问题的困扰： 它们要么不能支持足够多的数据阵列类型，比如 2 0 】【2 3 ， 要么需要限制数 据阵列在逻辑空问中的位置，比如【2 1 】，【2 2 】。 线性偏差地址交织策略采取的方法是将一个位于二维逻辑空间中的坐标 为( f ，力映射到第( 口f + b j ) m 个存储器模块中去。这里脚为并行的存储器模块 的数量。口和b 均为常量。这种线性偏差地址交织策略最早由b u d n i k 和k u c k 【2 4 提出。然后经由s h a p i r of 2 5 ，w i j s h o f f 和v a nl e e u w e n 【2 6 ，j o n gw o n p a r k 2 7 】的研究成果证明，只要并行的存储器模块的数量是一个大于并行数 据通路数量的质数，那么，一个并行存储系统可以同时提供对排列成一行， 一列，一个前向对角线，一个后向对角线的数据阵列的同时访问，而且这些 数据阵列的访问可以发生在二维存储空间中的任意一个地方。这种策略的最 大缺点就在于它需要冗余的物理存储单元，而且地址计算相对于非线性偏差 交织算法来说显得过于复杂。 以上这些对地址交织算法的研究基本上是基于某种固定的数据单元粒度 浙江大学硕t 学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 的基础上的。然而正如前面所提到的，基于的流的访问模式在媒体处理器的 设计中正在被广泛采用，而流访问的一个很重要的因素就是数据粒度的可配 置性。因此，如何将这些地址交织算法进行面向流访问的优化是一个很紧迫 的问题。 1 4 本章小结 本章阐述了基于s i m d 技术的媒体处理器在未来多媒体处理应用中的重 要意义；同时指出了这类处理器的体系结构设计的一个日益突出的问题：基 于s i m d 的媒体处理器的处理性能的进一步提高主要受限于非运算类操作的 开销，它们是数据存储与数据组织。这主要是由于多媒体处理应用的数据访 问非常灵活，而s i m d 体系结构却要求算法具有高度的运算规整性而导致的。 从之前的研究工作的调研发现，数据组织与数据存储这两大非计算任务对非 计算开销的降低都具有着重要意义，单纯致力于解决其中一项都无法真正地 解决s i m d 媒体处理器的这一瓶颈问题，必须对这两个方面都做出一定的体 系结构的优化。本文将逐一介绍对这两个方面的优化研究工作。在第2 章中 提出了一种基于显式置换的e d o s i m d 指令集体系结构来减少数据组织开 销；在第3 章中提出了一种将流访问与二维存储相结合的高效二维流存储系 统来降低数据存储开销；在第4 章中介绍了一种优化的基于线性偏差的地址 交织策略以解决传统基于线性偏差的地址交织策略中的存储器冗余问题以及 进一步支持模寻址来更一步的降低数据存储开销。 基于显式数据置换的e d o - s i m d 指令集体系结构 第2 章基于显式数据置换的e d o s i m d 指令集体 系结构 数据组织是组成s i m d 媒体处理器非计算开销的一个很重要的部分，这 主要是因为多媒体处理应用的数据访问非常灵活，而s i m d 体系结构却要求 算法具有高度的运算规整性。当从存储器读取出来的数据无法满足s i m d 对 规整性的要求时，便需要专门的数据组织指令来对其进行数据重组( 也叫数 据置换) ，这类指令在学术界和业界都得到了广泛使用 1 3 ，1 4 。但是在表l l 可以看到数据置换指令已经占到了非常大的开销。第1 3 2 节已经讲到，为 了降低数据组织指令的开销，i b m 的e l i t e 处理器【1 7 】实现了一种将数据置 换隐藏在地址置换中的隐式数据置换方法。它矢量元素寄存器( v e c t o r e l e m e n tr e g i s t e r , v e r ) 的基础上添加了矢量指针寄存器( v e c t o rp o i n t e r r e g i s t e r , v p r ) ，而将数据组织隐藏在了建立在对v p r 的编程基础上的寄存 器地址置换中去。但是如果没有编译器的良好支持，这种方法要求汇编或l i b 库编程人员必须熟悉v p r 的编程配置方法，对具体的硬件实现有很强的依赖 性从而减少了代码的可移植性。与隐式的数据置换不同，【1 8 】提出了一种半 显式的数据置换方案。它增加了一个接受显示数据置换信息的嵌入在数据通 路中的子字置换单元( s u b w o r d p e r m u t a t i o n u n i t ，s p u ) ，在将一个l o o p 中的 数据置换信息提取表达出来后只用对s p u 配置一次就可以。之所以说是半显 式，是因为所提取出来的数据置换信息依然相对依赖于s p u 的实现，而且如 果l o o p 的迭代次数较少的话，对s p u 的在进入l o o p 前的初始配置的开销就 无法忽略。因此在这一章中我们提出了一种基于显式数据置换的指令集体系 结构，出发点在于将数据置换信息归纳的更加完整且独立于具体的硬件实现， 并且将这些数据置换信息完全显式的声明在指令字中，将数据置换与数据运 算和数据存储有效的结合起来。 浙江大学硕士学位论文：基于s i m d 的媒体处理器的数据存储与组织体系结构优化研究 2 1 数据置换信息的提取和归纳 处理器的数据置换指令的关键部分是操作数之间的置换关系。比如说对 于一个m e r g e 指令，它就会将两个源操作数的若干个数据单元按照指定的顺 序整合放到目的操作数中。这种操作数之间的关系就是所谓的数据置换信息。 这里，这条m e r g e 指令在其设计原则上就采用了隐式数据置换的方法，它通 过指令标识符告诉编程人员，这条指令做的是m e r g e 操作。也可以是一种半 隐式的方法，比如说，在某些指令集体系结构中可以采用一个矢量来诠释如 何对所要m e r g e 的数据单元进行排列。那么这个排列顺序是显式的表示出来， 但是m e r g e 的这一信息的表达还是要依靠“m e r g e ”这个指令标识符。它们都表 现出隐式数据置换的一些共同的缺点：无法将数据置换指令与运算以及存取 指令并行。或许说v l i w 可以做这些事情，但是它已经上升到了另外一个技 术层面。换句话说，v l i w 可以让两条指令并行，但是是否可以这两条指令 合并成一条指令昵? 之所以希望采用完全的显式数据置换也就是基于这样一 种考虑：希望通过将数据置换指令与计算或存取指令合并的方法来降低甚至 消除数据置换指令给s i m d 体系结构所带来的影响。 要想试图在运算或存取指令里面加入数据置换操作首先要考虑的问题 是：指令标识符肯定是用来声明这是一个某某运算或者是某某存取指令，而 无法表达数据置换的操作信息( 类似于上一段提到的那个“m e r g e ”) 。或许可 以创建一种新的指令来表明这是一种某某运算加某某数据置换或者是某某存 取加某某数据置换指令。但是这样做会带来什么后果呢? 试想一下，假如有 5 0 条常规指令( 4 0 条运算指令外加1 0 条存取指令) ，这应该是一个很小的指 令集了，另外有8 种数据置换类型，这个也应该是个比较保守的估计，那么 需要创建的新的指令就有5 0 8 = 4 0 0 条指令，这是个让人生畏的数字，这条 路是显然走不通的。 那么就是如何更有效的来提取和归纳这种数据置换信息。为了解决这个 基于显式数据置换的e d o - s i m d 指令集体系结构 问题，首先对操作数的结构进行分析：通常情况下，一个操作数由若干数据 子字构成，所谓的数据子字是在操作数进行并行运算的时候的粒度。它由 s i m d 操作的粒度来决定。这样一个操作数可以表示为m x n 个比特，其中m = z n = 丁，这里m 表示一个数据子字中包含了多少个比特，而n 代表了 这个操作数包含了多少个这样的数据子字。于是这里m 就决定了这个操作数 的操作粒度。 根据操作数的这种结构特点，这里提出了一种数据置换矢量 ( m u l t i p l e x i n gv e c t o r ) 来表示数据置换信息。它可以表示为： 这里，b 口成为数据置换矢量的种类，而x o