（计算机系统结构专业论文）基于数据流水和资源分配的二维simd优化方法.pdf

论文独创性声明 本论文是我个人在导帅指导下进行的研究工作及取得的研究成果。沦文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声| ! l j 并表示了谢意。 作者签名 论文使用授权声明 同期奠1 2 ：! ：! 兰 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公柿论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名 忆，一 斗 蝉峤 摘要 摘要 二维s i m d 结构是在嵌入式系统中提高多媒体处理能力的有效系统结构。该结 构是指nxn 个处理单元按一定的拓扑结构连接而成的阵列结构，同行列的处理单 元以s i m d 的方式工作，不同行列相当于并行执行的s i m d 功能部件。基于这种结 构数据和计算的并行性，它通常被作为多媒体加速部件与通用处理器核集成在一个 s o c 上，并由通用处理器完成应用程序中串行部分的计算。目前，二维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 结构的编译优化技术，使得编译器能够 使用二维s m m 结构的指令集优化高级语言编写的应用程序。 目前，现有的针对二维s 蹦d 结构的编译技术也仅是通过匹配应用程序中固定 模式来生成特定格式的汇编代码，并且对应用程序的并行性进行了一些假设，因此 具有很大的局限性。本文在针对二维s i m d 结构编译优化方法上，在以下几个方面 给出了创新性的研究。 1 对目前出现的二维s i m d 结构的结构特征进行了分析，总结了目前该类型结 构的典型特征和缺陷。 2 针对二维s i m d 结构共享数据总线这一限制，提出了一种高效的流水优化方 法。 3 针对二维s i m d 结构中各p e 间的互连方式，提出了一种新的资源分配方法。 关键词：二维s i m d 结构，共享数据总线，编译优化，资源分配 4 a b s t r a c t a b s t r a c t t w o - d i m e n s i o n a ls 岫a r c h i t e c t u r ei sw i d e l yu s e di nt h ef i e l do fe m b e d d e ds y s t e m t ob o o s tt h ep e r f o r m a n c eo fm u l t i m e d i ap r o c e s s i n g t i l i sa r c h i t e c t u r ei sc o n s i s t e do fa t w o d i m e n s i o n a la r r a yo fp e s ( p r o e e s s i n ge l e m e n t s ) ，a n dt h ep e si nt h es a m el o wo r c o l u m nw o r ka sas 帅u n i t , a n dd i f f e r e n ts i m du n i t sc a nw o r kp a r a l l e l l y d u et ot h e p a r a l l e l i s mo fd a t aa n dc o m p u t a t i o n , t w o d i m e n s i o n a la r c h i t e c t u r ei so f t e ne m p l o y e d i na s o cw i t hag e n e r a lp r o c e s s o rw h i c hi su s e dt od e a lw i t ht h es e q u e n t i a lp a r to ft h e p r o g r a m c u r r e n t l y , t w o d i m e n s i o n a la r c h i t e c t u r eh a sa l r e a d yb e e nw e l lc o n c e r n e di n b o t ha c a d e n l ea n di n d u s t r y d u r i n gal o n gp e r i o d ，t h ef u l lu t i l i z a t i o no 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 ei s d i f f i c u l tb e c a u s ea p p l i c a t i o nw r i t e r st i t l el a r g e l yr e s t r i c t e dt ou s i n ge m b e d d e da s s e m b l y , w h i c hi sat e d i o u sa n dt o u g ht a s k w i mt h ec o n s i d e r a t i o no f p o w e rc o n s u m p t i o na n dd i e s i z e m o s to ft h et w o d i m e n s i o n a ls 咖a r c h i t e c t u r e su s es h a r e dd a t ab u sa n df e w r e g i s t e r s ，t h i si sa n o t h e rd i f f i c u l t yf o ra p p l i c a t i o nw r i t e r st op r o g r a mf o rt w o - d i m e n s i o n a l s i m da r c h i t e c t u r ed i r e c t l y ap r o m i s i n gs o l u t i o nt ot h i sp r o b l e mi st oo n p l o yt h e c o m p i l e rt e c h n i q u e st oh e l pt h ea u t o m a t i cc o d eg e n e r a t i o nf o rt w o - d i m e n s i o n a ls i m d a r c h i t e c t u r e u n t i ln o w , t oo u rb e s tk n o w l e d g e ，t h e r ei sv e r yl i t t l er e s e a r c ho nt h eo p t i m i z i n g t e c h n i q u e sf o rt 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 b a s e do nt h ed e e ps t u d yo fb o t ht h e m u l t i m e d i aa p p l i c a t i o n sa n dt 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 ， w ep r o p o s e da c o m p i l e rs c h e m et oo p t i m i z et h em u l t i m e d i aa p p l i c a t i o n sf o rt w o d i m e n s i o n a ls i m d a r c h i t e c t t t r e t h ew o r ko f t h ed i s s e r t a t i o ni n c l u d e s ： 1 a n a l y s i s a n ds u m m a r i z a t i o nt h ec h a r a c t e r i s t i c sa n dl i m i t a t i o n so f t w o - d i m e n s i o n a ls 岫a r c h i t e c t u r e 2 ah i g hp e r f o r m a n c ep i p e l i n e do p t i m i z a t i o nm e t h o dt os o l v et h el i m i t a t i o nc a u s e d b ys h a r e dd a t ab u s 3 an e wr e s o u r c ea l l o e a t i o nm e t h o du s i n gt h ei n t e r - c o n n e c t i o no fp e st od e a lw i t h l a c ko f r e g i s t e t s 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 ，s h a r e dd a t ab u s ，c o m p i l e ro p t i m i z a t i o n , r e s o u r c ea l l o c a t i o n 5 第一章引言 1 1 多媒体应用 第一章引言 上世纪九十年代以来，计算机世界发生了革命性的变化，这一变化主要体现在： 计算机与其使用者之间的交互方式发生了巨大的改变，人与计算机之间的交流不再 仅仅局限于简单的键盘字符输入和屏幕字符输出。扫描仪、摄像头、声卡、麦克风、 音响设备、3 d 输出设备、游戏操纵杆等多媒体输入输出设备的出现使得人机之间的 交流手段变得越来越丰富多彩。随着这些设备在计算机系统中被广泛而深入的使用， 以通用处理器为核心的多媒体应用逐渐占据了个人电脑应用中的统治地位。与此同 时，手机、p d a 、数码相机等数字设备的普及也加速了这一趋势。 在这些多媒体应用中，作为计算核心的处理器往往承担了编码、解码、压缩、 解压、解释、增强与渲染等高强度的计算任务 1 ，而这些计算又往往具备以下的主 要特征 2 ： 极大的数据量 较小的数据类型( 8 位或者1 6 位) 大量存在的数据并行性 计算密集，分支跳转可预测性很强 较强的实时性要求多个并发的媒体流( 例如视频流和音频流) 巨大的i 0 带宽需求 另一方面，得益于互联网络的发展，多媒体应用与网络应用相互结合，使得多 媒体应用技术有了更进一步的发展。然而，随着多媒体技术的普及与发展，多媒体 应用对计算机系统的核心计算能力提出了越来越高的要求。以网络视频应用为例： 网络视频应用将来自互联网的视频数据解码后再根据视频输出设备的要求重新编 码，并将编码后的数据输出到视频设备。网络视频的使用者总是希望能够获得清晰 而连贯的收视效果，这就要求我们提高视频分辨率使图像变得更清晰，并提高单位 时间内输出图像的帧数来保证视觉的连贯性。但是，分辨率每提高一倍，所需要处 理的数据量将增加四倍，计算机系统处理每一帧图像数据所需要的时间也相应延长 为原先的四倍，同时单位时间内能够输出图像的帧数则降为原先的四分之一。这样， 提高图像分辨率与提高单位时间内输出图像的帧数便成为了一对矛盾。所幸的是， 6 第一章引言 由于视觉存在暂留现象，因此在视频播放的过程中，我们只要保证每秒有二十四帧 以上的图像被输出就可以保证收视者能看到足够连贯的图像。所以为了提供优质的 视频服务，我们需要提高应用中编解码的效率。而提高编解码效率的方法有两种， 其一为提高处理器的计算能力，其二为降低编解码方法的复杂度。但是，由于网络 视频应用的数据来自于互联网络，因而网络传输的效率便成为了应用的另一个瓶颈。 因为，如果互联网络无法在单位时间内提供足够的数据量，则收视者一样无法获得 连贯的收视效果。因此，为了提高网络传输的效率，我们往往将数据进行高密度压 缩，而高密度压缩的代价则是降低编解码的效率。由于种种牵制，使得提高计算机 系统的核心计算能力成为了提高多媒体应用效果的唯一选择。 1 2 多s i m d 结构 1 2 1s i m d 操作 尽管通用处理器的性能已经有了长足的发展，但是由于多媒体应用本身的特殊 性，多媒体计算还是对通用处理器的计算能力提出了重大挑战。在多媒体应用刚兴 起的时候，一种典型的解决方案是增加专用芯片( 媒体处理器) 。但随着多媒体应 用的日益广泛，低成本的解决方案就变得十分迫切了。所以在通用处理器内增加支 持就变得很流行，这种支持就是通过s i m d ( 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 1 所示。 o 区叵王五习 图1 1s i m d 操作示例 各大处理器厂商都先后为自己的处理器增加了多媒体扩展( m u l t i m e d i a e x t e n s i o n ) ，如i n t e l 的删x s s e s s e 2 s s e 3 ，a h i d 的3 d n o w ! ，i b m 的v 姒，s u n 的v i s 等。同时，嵌入式处理器厂商也积极将多媒体扩展加入到自己的产品中，例如a n a l o g 的a d s p 一2 11 6 1 、e q u a t o r 的m a p c ab r o a d b a n ds i g n a l p r o c e s s o r ( b s p ) 、3 d s p 的 u n i p h y 、t e n s i l i c a 的x t e n s av e c t r ae x t e n s i o n 以及p h i l i p s 的t r i m e d i ac p u 6 4 3 7 嚣 第一章引言 等。 1 2 2 多s i m d 结构 虽然设计专用a s i c 芯片或在通用处理器核的基础上增j j d s l m d 功能单元作为 多媒体加速部件可以在一定程度上增强多媒体的处理能力，但是这两种解决方法都 存在一些不足，使它们无法有效解决多媒体应用对计算的要求。设计专用a s i c 芯片 虽然可以满足部分嵌入式多媒体应用实时处理的需求，但是因为它的结构针对某种 # i n g l e1 0 n gs i m du n i t ”4 “一“1 “w “ 。叵e 正工丁习 ，区巨e 圈，m u l t i p l e 磐渊x n u n i l s - e 巨e 圈j 图1 2 单长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 指令格式时，广播指令至) j s i m d 功能单元的各个处理单元需要更长的时间， 这样不利于处理器时钟频率的提高。其次，长的s i m d 功能单元需要编译器发掘更多 的相同标量操作来组成一条s i m d 指令，而多个短的s i m i 功能单元则只需进一步发掘 s i m d 指令的并行性。因此，多个短的s i m d 功能单元更有利于编译器的优化。基于这 样的考虑，多s i m d 结构逐渐成为各种处理器芯片中主要的多媒体加速手段，如图1 2 第一章引言 所示。 翻m d u h 孵 s l m n u n h s i m n u 口h 图1 3 分布式主存多s i m d 结构 图1 4 共享主存多s i m d 结构 近2 0 年来v l s i 技术的飞速发展使得芯片设计的成本大大降低，因此许多大学和 研究机构设计了基于多s i i v i d 结构的多媒体处理芯片。目前多s i m d 按其片上c a c h e 的组织形式可以分为分布式主存多s i m d 结构和共享主存多s m i d 结构。 分布式主存多s i i v i d 结构其结构如图1 3 所示。每个s i m d 功能单元有各自的本 地c a c h e 。比较典型的系统如i b m 的c e l l l 4 。 共享主存多s i m d 结构其结构如图1 4 所示。各个s i m d 功能单元共享片上 c a c h e 。由于共享主存s i i v i d 结构有比较小的芯片面积和能量消耗，目前主要应用在 嵌入式领域。表1 1 给出了比较具代表性的使用共享主存多s i m d 结构作为多媒体 加速部件的s o c 。 l 产品名称 研究机构 i m a t r i x 5 l m i t 9 第一章引言 m o r p h o s y s 6 - 9 u n i v e r s i t yo fc a li f o r n i a ，i r v i n e r e m a r c 1 0 s t a n f o r d i m a g i n e 1 1 s t a n f o r d v i r a m 1 2 u cb e r k e l e y v i s i o nc h i p s 1 3 1 4 u n i v e r s it yo ft o k y o m o t o r o l a6 0 1 1 1 5 m o t o r o l ai n c f a s t m a t h 1 6 i n t r i n s i t yi n c m r d s p 1 7 m o r p h ot e c hi n c m g a p 一2e 1 8 f o l s o mi n c h e r a 1 9 n e wj e r s e yi n s t i t u t eo ft e c h n o l o g y 表1 1 采用共享主存多s i m d 结构作为多媒体加速部件的s o c 1 3 二维s i m d 结构及其面临的问题 1 3 1 二维s i m d 结构 目前，在多s i m d 结构中，最具代表力的就是二维s i m d 结构，所谓二维s i m d 结构 就是指使用一组并行执行的一维s i m d 部件来加速程序执行，如图1 5 所示。二维s i m d 结构目前已经得到了广泛的应用，表1 1 中列出的共享主存多s i m d 结构中大部分都是 采用的二维s i m d 结构。 图1 5 二维s i m d 结构图解 l o 第一章引言 图1 6 描述了一种典型的二维s i m d 结构，是指一个8 8 的处理单元p e 组成的阵列 结构，各p e 按一定的拓扑结构连接，同行列的p e 以s i m d 方式工作，不同的行列相 当于单独的s i m d 功能部件。 图1 6 一种典型的二维s i m d 结构 1 3 2 二维s i 胁结构与一维s i m d 结构在并行性上的区别 二维s i m d 结构虽然只是运用了一维s i m d 部件问的并行性，但却导致了一些 与一维s i m d 部件在并行性上的本质差别： l 单个s i m d 部件之内的数据并行性，该层并行性与一维s i m d 部件的并行 性相同。 2 s i m d 部件之间的并行性，该层并行性为二维s i m d 结构所特有，包括时间 域和空间域的并行性。 时间域上的并行性，这一层的并行性是指多个s i i v l d 部件在时问上复用 前面s i i v l d 部件的计算结果而形成的流水化并行。 空间域上的并行性，这一层的并行性是指多个s i m d 部件同时执行各自 的s i m d 指令形成的并行。 第一章引言 1 3 3 二维s i i d d 结构在硬件和软件上面临的问题 虽然二维s i m d 结构已经得到了广泛的应用，但是该结构在硬件和软件支持上 还面临着一些问题： 1 在硬件上，由于目前采用二维s i m d 结构的s o c ，其主要应用领域是手持 设备的多媒体处理，因此出于节能和芯片面积的考虑，在这些s o c 的设计 中，都对二维s i m d 结构加入了一些限制。目前，二维s i m d 结构普遍采 用的一个限制是多个s i m d 行n 复用一条数据通路。复用数据通路的限制 使每次通过数据通路加载的操作数只能满足多个行列中一个s i m d 部件的 数据需求，二维s i i v i d 结构目前普遍的采用的另一个限制是p e 结构比较简 单，每个p e 上只有很少数目的寄存器。这个限制使二维s i m d 结构在运行 时通过各p e 的寄存器只能保存十分有限的数据和中间结果，这就使共享一 条数据通路的各行列在运行时对数据通路加载数据的依赖更加明显。 2 在软件上，针对二维s i i v l d 结构编译技术的研究还比较滞后。一些研究机 构也对二维s i m d 结构的编译技术进行了研究，但是采用的主要方法是匹 配程序中的固定模式生成特定格式的汇编代码的方式来进行编译优化，这种 优化方式要求程序员在进行二维s i m d 结构应用程序开发的过程中，要对 底层结构和多媒体程序的并行特性都有一定的了解，并按编译器能够处理的 方式编写代码，由此导致采用这种方法实现的编译器具有很大的局限性。二 维s i m d 结构编译技术研究滞后造成的直接后果是各种采用二维s i m d 结 构的系统还处于手动编写汇编代码的编程模式，不仅不利于缩短产品的开发 周期，也给二维s i m d 结构应用程序的开发增加了难度。 1 4 本文的安排 结合二维s i m 结构的体系结构特点和目前针对该结构的编译技术发展状况，我们 对针对二维s l m d 结构的编译优化技术的关键点作了如下总结： 1 妥善处理二维s i m d 结构的三点并行性( 如1 3 2 中所述) ，特别是s i m d 部件 之间的并行性，这在传统的并行编译理论框架下并不能完全解决。 2 妥善处理二维s i m d 结构在硬件上受到的限制( 如1 3 3 中所述) ，其中， 数据通路的限制给编译器有效探索多媒体程序在二维s i m d 结构上空间域和 1 2 第一章引言 时间域的并行性造成了极大的障碍；p e 内寄存器数目的限制使得二维s i m d 结构执行时刻对数据加载的依赖更加突出，因此，如果编译器无法解决好结 构受限的二维s i m d 结构中多行列s i m d 部件对数据通路加载数据的竞争， 那么复用一条数据通路的多个s i m d 部件将退化成单s i e ) 功能部件，系统的 利用率和处理能力都会受到很大的影响。 我们的研究工作就是在深入剖析了当前共享主存多s i m d 结构的体系结构特点 和对多媒体应用程序代码进行深入分析的基础上，针对共享主存多s i m d 结构编译 技术研究的不足，结合共享主存多s i m d 结构中普遍采用的共享数据总线和寄存器 少的限制和应用程序的特点，提出了一系列针对二维s i m d 结构的优化方法。 本文一共分为八章，第一章的内容至此结束。第二章和第三章分别介绍了底层 结构和传统并行理论在二维s i m d 结构中遇到的障碍。第四章讨论了针对二维s i e ) 结 构编译优化的基本功能。第五章和第六章分别具体阐述了两种优化方法：针对二维 s i m d 结构的流水优化方法和资源分配方法。第七章介绍了实验方法和结果，并对结 果进行了分析，最后第八章对全文进行了总结和展望。 第二章底层结构及编程摸式 第二章底层结构及其编程模式 2 1 底层结构m o r p h o s y s 2 1 1m o r p h o s y s 概述 m o r p h o s y s 6 - 9 是一种采用二维s i m d 结构作为多媒体加速部件的粗力度可重 配置系统。做为二维s i m d 结构比较有代表性的系统，m o r p h o s y s 是科研中少数参与 产业化的结构。由于主要应用领域为移动设备的多媒体处理，因此在它的设计中也 采用了共享主存多s i m d 结构中普遍采用的限制一一共享数据总线和每个s i m d 功能 单元只有较少的寄存器。许多公司的s o c 也采用了类似m o r p h s y s 结构的共享主存多 s i m d 结构。因此我们的研究选用m o r p h o s y s 作为底层结构。 图2 1m o r p h o s y s 结构 m o r p h o s y s 的结构如图2 1 所示，它由五部分组成： 1 t i n y r i s cc o r e 控制核心，负责对整个芯片的控制和执行程序中的串行 部分。 2 二维s i m d 结构一个8 x 8 的处理单元阵列，作为多媒体加速部件，负责加 速应用程序中的海量数据处理。 3 指令缓冲t i n y r i s c 从指令缓冲中为二维s i m d 结构选择需要执行的操作， 相当于二维s i m d 结构的指令c a c h e 。 1 4 第二章底层结构及编程模式 4 数据缓冲为二维s i m d 结构提供操作数，相当于数据c a c h e ：为了提高数 据的传输效率。共享主存的物理结构分成两块一f b o f b l 。当其中一块为多s i m d 功 能单元提供数据读写时，另一块可以通过d m a 与片外主存进行数据交互。 5 d m a 控制器在t i n y r i s c 的控制下，负责控制数据缓冲和指令缓冲与外部 存储之间的数据传输。 2 1 2 t i n y r i s cc o r e t i n y r i s cc o r e 2 0 是一块通用处理芯片核，它负责执行应用程序中的所有串行 代码，以及负责控制m e m o r y 到各组件之间的数据流，所以也称为总控芯片。 t i n y r i s cc o r e 采用3 2 位处理器，4 - s t a g e 的流水线，1 6 个3 2 位寄存器和3 个功能 部件：1 个a l u ，1 个3 2 位移位部件，和1 个内存部件，如图2 2 所示。t i n y r i s c 除了一 些常规的指令外，在原有的i s a 中添加一些特殊的指令，以用来控制二维s i m d 结构的 执行、共享内存与片外内存之间以及指令缓冲与片外内存之间的数据交换。实际上， 二维s i m d 结构相当于t i n y r i s c 的一个功能部件。 f e t c h s t a g o d e c o d e s t a g e e x e c u t e s t a g e w r i t e b a c k s t a g e 2 1 3 二维s i m d 结构 图2 2t i n y r i s c 体系结构 m o r p h o s y s 采用了一个8 8 的p e 阵列，行列的8 个p e 以s i m d 方式工作，是 第二章 底层结构及编程模式 m o r p h o s y s 的多媒体加速部件，具体结构如图i 6 所示。 p e 的结构如图2 3 所示，每个p e 由一个定点操作的a l u ，一个乘法器和一个寄存 器堆组成，p e 执行的操作通过c o n t e x t 寄存器中的一个3 2 位的指令字进行配置。a l u 除了提供一般的逻辑和数学运算外，它还提供诸如绝对值计算和乘加运算等在多媒 体领域经常用到的运算。两个多路选择器分别用来选择a l u 的操作数，这些输入包括 四个相邻的p e 的输出，同行( 列) p e 的输出，共享主存中的数据，p e 寄存器文件中 的数据等等。此外p e 的寄存器文件是由4 个1 6 位寄存器组成的，而输出寄存器是2 8 位以适合a l u 的输入精度。p e 中的c o n t e x tw o r d 是一个3 2 位的指令寄存器，它包含着 用来配置该p e 执行的指令字。 掰蝴 图2 3 二维s i m d 结构的节点p e 的结构 6 4 个p e 之间的互连方式主要分为3 个层次，如图2 4 所示 1 第一层为最近邻居相连：将每个p e 与其上、下、左、右的4 个相邻p e 连接。 2 第二层将整个阵列分成4 个子块，每个子块为4 + 4 规模，然后将子块中每行 ( 列) 中在第一层连接中未被相连的p e 两两连接。 3 第三层使4 个子块之间能够快速的传输数据。这些1 a i l e 能将某行( 列) 上p e ( 上4 或下4 中一个) 中的数据传到相邻子块同行( 列) 上的p e 中，如此3 层设计大大 加快了p e 内数据传输。 1 6 亡e赛谣砖甍童声-罾；嚣、謇一v 第二章底层结构及编程模式 一一 慰 纛瓣蒸 书鑫睁薪燕 ；毒一 一孛= 槲= ：# ：铽 强受g 隍5 能 奄f 酡 世譬r 亭 砸鸯麟冀镘矗毛牌r 哥 一 g 匕缈? q 扔缈s 图2 4p e 的互连方式 显然，如此连接而成的二维s i m d 结构有两种s i m o 执行模式： 行s i m d 模式( 图2 5 ) ：同行的8 个p e 组成一个s i m d 执行单元 列s i m d 模式( 图2 6 ) ：同列的8 个p e 组成一个s i m d 执行单元 数据总线的复用方式：同行的p e 复用一条数据总线，如图2 7 所示。因此，行s i m d 模式时，同行各p e 从数据总线获得的3 2 b i m 数据完全相同。列s i m d 模式时，各列 s i m d 执行单元获得的2 5 6 b i m 操作数完全相同。 d m 瓤 i 让b 咻 图2 5 行s i m d 模式 图2 6 列s i i d d 模式 1 7 第二章底层结构及编程模式 窑 兽 誊 i 盂 蚕 嚣 鼍 2 兽 盂 篓 星 嶂蹿獬睡麓蹲蜀隧一 博一陌潲陌俦舄陌障 - 矿蹲两陶峰随隧蹲 虿离离梅碡诲离一梧接瞪晒垮隐睁晒卜审 f 薅掉悼睡婚隧滔 陌礴两”两障一跨“蜀一蹲 f 蒋障障一两一两蒋障卜蕈障障障陲障障 草 哼“诲弯。奄一龟晦”培磷 2 1 4 指令缓冲 图2 7 数据总线及控制字广播方式 指令缓冲用来存储控制各p e 的3 2 - b i t s 指令组成的v l i w 指令字，相当于二维 s i m d 结构中各行列s i m d 操作的指令c a c h e 。指令缓冲器分为两部分，分别为二维s i m d 结构的两秘执行模式提供指令缓存，指令的广播方式如图2 。7 所示。每部分1 6 个 2 5 6 b i t s 的指令槽，每个指令槽由8 个3 2 b i t s 的指令字组成，如图2 8 所示。每个指令 字对应二维s i m d 结构的一行或一列。控制逻辑从指令缓冲中选取一个指令来确定二 维s i m d 结构各行列的操作。 2 1 5 数据缓冲 数据缓冲作为二维s i m d 结构的数据c a c h e ，在m o r p h o s y s 系统中共享主存的存在 对于数据传输是非常重要的。其结构如图2 9 所示。 共享主存被分成2 块，s e t0 ( f b o ) 和s e t1 ( f b l ) 。s e to 和s e t l 可以同时工 作，也就是说s e t0 读( 写) 时，s e t1 还能同时写( 读) 。例如，当二维s i m d 结构 从一个s e t 读取数据迸行运算时，d m a 可以继续从片外内存中向另一个s e t 中传输数据， 并且对于同一个s e t ，数据总线可以同时从它的两个b a n k 读数，并将两个b a n k 中的向 量数据交错组织在一起向二维s i m d 结构提供数据，这一点在图2 9 右边的柱体中得到 了说明，这样的设计大大地提高了i o 速度。 刀ooq番cl器cn b l i 孽 苎三雯 塞星丝塑墨塑堡堡茎 s t z 职o s e t o 糙 臣亟巫互叵曼匝习 厂弋 、弋， 医亘巫燕三圊 图2 8 指令缓冲的组织形式 8 n k 6 4 x 8b 外 2 。1 6 d m a 控制器 c o i u m n c o n 协m - b u s t o r c 山晌瞪 c o l u m n s r o w c o n 协船 卜b u s t o 敝a r r a y m s 8 鲫e a b b a b b 。 8 b b b 1 r o ，f r o m r c 脚 l s b y t e d m a 作为一种用来提升芯片与外围设备数据传输的设备，m o r p h o s y s 中d m a 控制器 园圉 第二章底层结构及编程模式 是一个通用d m a 控制器，用来协助t i n y r i s c 处理主存与数据缓冲，主存与指令缓冲之 间的数据传输。 2 2m o r p h o s y s 的编程模式 为了便于控制二维s i m d 结构以及指令缓冲，数据缓冲等结构，m o r p h o s y s 为 t i n y r i s c 的指令集添加了几条指令，如表2 1 所示，这些指令从功能上可分为三类： 主存和数据缓冲之间的数据传输 主存和指令缓冲之间的数据传输 控制p e s 的执行 指令描述 l d c t x t l o a dc o n t e x tp r o g r a mi n t ot h ei n s t r u c t i o nb u f f e r l d f b ，s t f bd a t at r a n s f e rb e t w e e nm a i nm e m o r ya n dd a t ab u f f e r e x e c u t ec o n t e x t ( f r o mi n s t r u c t i o nb u f f e r ) i nt h er ca r r a y ( r o wo rc o l u m n c b c a s t m o d e ) e x e c u t er ca r r a yw i t hs p e c i f i cc o n t e x t ( r o w c o l u m n ) ，l o a do n eo p e r a n d s b c b f r o md a mb u f f e ri n t or c a r r a yc o l u m n e x e c u t er ca r r a yw i t hs p e c i f i cc o n t e x t ( c o l u m nm o d e ) ，l o a dt w o d b c b c o p e r a n d sf r o mb o t hb a n ko f d a t ab u f f e ri n t or ca r r a y e x e c u t er ca r r a yw i t hs p e c i f i cc o n t e x t ( r o wm o d e ) ，l o a dt w oo p e r a n d s d b c b r f r o mb o mb a n ko f d a t ab u f f e ri n t or ca r r a y w f b w r i t ed a t af r o mr ca r r a yc o l u m nt os p e c i f i e da d d r e s si nt h ed a t ab u f f e r 、f b iw r i t ed a t af r o mr ca r m yc o l u m nt od a t ab u f f e r ( i m m e d i a t ea d d r e s s ) w r i t ed a t af r o ma l lr ci nt h ef i r s tr o wo ft h er c a r r a yt ot h et i n y r i s c r c r i s c r e g i s t e rf i l e 表2 1t i n y r j s c 附加的控制指令 第三章 传统并行理论在二维s i m d 结构中遇到的障碍 第三章传统并行理论在二维s i m d 结构中遇到的障碍 虽然，传统并行理论已经相对成熟，但是将其应用于针对二维s i m d 结构的优 化中，却得不到预期的结果。原因有二：首先，我们所使用的b e n c h m a r k 的代码编 写风格对获得理想优化效果设置了障碍，换句话说，程序员在b e n c h m a r k 中对代码 进行了不少深层次的串行优化；其次，二维s i m d 结构本身在结构上的限制和特殊 性是对获得理想加速比的极大挑战。 在本章中，我们将从b e n c h m a r k 代码和二维s i m d 结构两方面分析入手，具体 说明传统并行理论在二维s i m d 结构中遇到的障碍。 3 1b e n c h m a r k 简介 对于编译优化技术的研究来说，b e n c h m a r k ( 基准程序) 的选择是非常重要的， 要在二维s i m d 结构上获得性能提升，那么b e n c h m a r k 需要具备如下特征： 程序需要具有非常明显的h o t s p o t ( 热点) 特征，即程序的大部分执行时间 消耗在某些核心的代码上。 程序需要具有良好的空间局部性，即程序运行时访问数据的跨度在较小的范 围内，这是缘于二维s i m d 结构本身提供的数据缓冲比较小，且总线使用 规则限制了该结构的数据传输能力。 程序中的h o t s p o t 需要具有良好的数据级并行性，这是能否运用s i m d 优化 技术的关键所在，更是二维s m d 优化的前提。 程序中的h o t s p o t 在数据级并行性之上，还需要存在一定的循环级并行性， 这是发挥二维s i m d 结构并行优势的关键，也是二维s i m d 结构在体系结 构上与单纯的多媒体扩展的最大区别。 基于上述特点，我们选择多媒体包b e r k e l e ym u l t i m e d i aw o r k l o a d 和加解密程序 i d e a 、3 w a y 作为代码分析的对象。在本节我们将分别介绍我们选择的b e n c h m a r k ， 下一小节将从代码的角度来分析b e n c h m a r k 的特征。 3 1 1 b e r k e l e yh u l t i m e d i aw o r k l o a d b m w ( b e r k e l e ym u l t i m e d i aw o r k l o a d ) 2 1 2 4 】是美国加州大学伯克利分校提出的 2 l 第三章传统并行理论在二维s i m d 结构中遇到的障碍 一套多媒体程序集。它是一个用标准c c + + 语言实现的多媒体应用程序测试包。这个 测试包采用了完整的多媒体应用作为测试程序，使得这个测试包更能反映多媒体应 用的真实需求。另一方面，这个测试包对数据也进行了仔细地筛选，使得测试结果 更具有代表性。 b 唧包括了1 2 个应用程序，其中8 个为定点应用、4 个为浮点应用。表3 1 给出了 这1 2 个应用程序的基本描述，包括了具体的程序名称，应用领域，代码行数等。 3 i 2 i d e a 与3 - w a y 表3 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 在现代密码学中，主要有两种文本加密方法：序列密码法( s t r e a mc i p h e r ) 和分 组密码法( b l o c kc i p h e r ) 。序列密码法在数据流的各个二进制数字中应用加密密钥 以及算法，每次处理一个比特，现代密码学不太常用这种方法，其主要替代方法为 分组密码法，其为数据流中的数据块而不是单个比特应用密钥和算法。 大多数分组密码法具有很好的数据并行性，因此这些算法很适合在二维s i m d 结 构上执行，在本文的研究中我们选取了两个典型