（计算机系统结构专业论文）流基准测试程序开发及其流并行性分析.pdf

摘要 摘要 随着多媒体应用对计算机性能要求的同益提高，流处理器体系结构应运而 生。作为一种新兴的体系结构研究领域，实现创新的最大障碍就是目前并不清 楚如何在这种体系结构上最好地表达和执行并行计算，使用现有的多媒体基准 测试程序来进行流并行计算的研究是不合理的，有必要开发一套流基准测试程 序包来满足流体系结构研究的需要。 本文在深入研究典型的流体系结构i m a g i n e 流处理器的基础上，针对一 套完整的多媒体基准测试程序包m e d i a b a n c h ，分析其中各个程序中的流并行 性，对于其中适于流并行化的程序设计并实现了流并行程序版本，作为流体系 结构研究的基准测试程序，并对流基准测试程序的应用进行实验评测。 本文的具体研究内容以及所取得的研究成果包括：( 1 ) 深入研究了i m a g i n e 流体系结构及其软件系统，总结出适于在i m a g i n e 上进行处理的应用特点，以及 如何将并行计算任务映射到i m a g i n e 体系结构上的一般方法。 ( 2 ) 以多媒体基 准测试程序m e d i a b e n c h 为研究对象，详细分析了多媒体应用程序的整体特性以 及不同测试程序各自具有的特点，总结出从多媒体应用中提取流并行性的基本 方法。( 3 ) 针对具有丰富的流并行性的多媒体应用程序j p e g 、m p e g 2 、r a s t a 、 g s m 和e p i c ，分别设计和实现了它们的流并行程序，讨论了流并行程序设计过 程中所涉及的关键技术问题。( 4 ) 用以上5 个流并行程序作为基准测试程序， 对流体系结构进行了有针对性的性能评测，完成了对m e d i a b e n c h 在流体系结构 上并行化适应性的评价，总结出在整个流处理过程中的性能影响因素，从而对 流体系结构、流编译系统以及流程序设计提供了有价值的改进意见。 本文的研究工作丰富了对流体系结构特征的认识，形成了一套丌发流基准 测试程序的方法，为流体系结构的进一步研究工作提供了借鉴。 关键词：流体系结构流编程模型媒体处理流基准测试程序流并行程序设计 a b s t r a c t a b s t r a c t a l o n gw i t ht h ei m p r o v e dr e q u i r e m e n to fm u l t i m e d i aa p p l i c a t i o nt o w a r dt o c o m p u t e rp e r f o r m a n c e ，s t r e a mp r o c e s s o ra r c h i t e c t u r ee m e r g e dn a t u r a l l y a sak i n do f r i s i n ga r c h i t e c t u r er e s e a r c ha r e a ，t h eb i g g e s th i n d r a n c eo fi n n o v a t i o ni sw ed o n 、tk n o w h o wt oe x p r e s sa n dp e r f o r mp a r a l l e lc a l c u l a t eo nt h i sn e wa r c h i t e c t u r e i ti sn o tl o g i c a l t ot a k eu s eo ft h ee x i s t i n gm u l t i m e d i ab e n c h m a r kt or e s e a r c hs t r e a mp a r a l l e lc a l c u l a t e ， s oi ti sn e c e s s a r yt od e v e l o pas t r e a mb e n c h m a r ks u i tt os a t i s f yt h er e q u i r e m e n to f s t r e a ma r c h i t e c t u r er e s e a r c h i nt h i sp a p e r ，b a s e do nd e e p l yr e s e a r c ht h ec l a s s i cs t r e a ma r c h i t e c t u r e i r f i a g i n es t r e a mp r o c e s s o r ，w ea i m a ta l li n t e r g r a t e dm u l t i m e d i ab e n c h m a r ks u i t m e d i a b e n c ht oa n a l y z et h es t r e a mp a r a l l i s m ，a n dr e a l i z eae d i t i o no fs t r e a mp a r a l l e l p r o g r a m st o w a r dt ot h o s ep r o g r a m sw h i c hs u i tt os t r e a ma r c h i t e c t u r e s u c hs t r e a m p r o g r a m sa r et a k e na ss t r e a mb e n c h m a r kf o rs t r e a ma r c h i t e c t u r er e s e a r c ha n dw e e v a l u a t i n gt h e s ea p p l i c a t i o n so ni m a g i n es i m u l a t o r t h er e a l l yr e s e a r c hc o n t e n t sa n dr e s e a r c hr e s u l t so ft h i sp a p e ri n c l u d e ：( 1 ) s t u d y o nt h ei m a g i n es t r e a ma r c h i t e c t u r ea n di t ss o f t w a r es y s t e mt h o r o u g h l y ，a n dt h e n s u m m a r i z et h ea p p l i c a t i o nc h a r a c t e r i s t i c sa p p l y i n gt oi m a g i n ed e a l i n ga n dt h eg e n e r a l w a yo fm a p p i n g ( 2 ) t a k i n gm u l t i m e d i ab e n c h m a r kt e s tp r o g r a ma sab a s i ct o o l ， d i s s e c tt h eo v e r a l lc h a r a c t e r i s t i co f a p p l i c a t i o np r o g r a mi nd e t a i l s ，b e s i d e st h ev a r i o u s f e a t u r e so fd i f f e r e n tt e s tp r o g r a m s t h e nt h eb a s i cm e t h o d so fr e f i n i n gs t r e a m p a r a l l e l i s mw e r es u m m e du p ( 3 ) d e s i g ns t r e a mp a r a l l e l i s mi nd e t a i lf o rm u l t i m e d i a a p p l i c a t i o np r o g r a m ，s u c ha sj p e g ，m p e g 2 ，r a s t a ，g s m ，e p i c ，f o r m i n gs t r e a m b e n c h m a r kt e s tp r o g r a m t h e nd i s c u s st h ek e yt e c h n o l o g yi n v o l v e d ( 4 ) e v a l u a t ei t s f u n c t i o nw i t hac l e a ra i ma n ds o m ei n f l u e n c i n gf a c t o r sa r eo b t a i n e dt h r o u g ha n a l y z i n g s u i t a b i l i t ya b o v e m e n t i o n e d ，t h e r e b yg i v es o m ep e r f o r m a n c ef e e d b a c kf o rs t r e a m a r c h i t e c t u r e ，s t r e a mc o m p i l i n gs y s t e ma n ds t r e a mp r o g r a m m i n g t h ew o r ko ft h i s p a p e re n r i c h e dt h ec o n g r e g a t i o no fs t r e a mb e n c h m a r ka n d d e v e l o p e dav e r yp o w e r f u ls e to fm e t h o d sf o rs t r e a me x p l o i t i n g ，w h i c hm a yo f f e r s o m er e f e r e n c ea n dg i s tf o rr e s e a r c hf o rs i m i l a rr e s e a r c hw o r k a b s t r a c t k e yw o r d s ：s t r e a ma r c h i t e c t u r e ，s t r e a mp r o g r a m m i n gm o d e l ，m e d i ap r o c e s s i n g ， s t r e a mb e n c h m a r k ，s t r e a mp r o g r a m m i n g 图目录 图目录 图2 1i m a g i n e 流处理器硬件结构1o 图2 2i m a g i n e 的运算簇结构l o 图2 3 流编程模型在体系结构上的映射1 3 图2 4 流编程模型：13 图2 5 派生流的种类1 6 图2 6i fe l s e 分支的处理机制1 7 图2 7 数据流图19 图2 8 流编译器过程2 0 图4 1j p e g 编解码过程2 9 图4 2j p e g 编码中数据流的组织3 1 图4 3z i g - z a g 扫描31 图4 4j p e g 编码的流程序模型3 2 图4 5c o l o r 中数据流的组织以及伪代码3 2 图4 68 元素c h e n w a n g 算法流程3 3 图4 7m p e g 2 视频编码原理框图3 6 图4 8 数据分块成流示意图3 8 图4 9 编码的核心操作和流数据3 9 图4 1 0p 帧编码的s t r e a m c 程序的关键代码4 0 图4 1 1i d x g e n 关键代码l o o p 循环4 1 图4 1 2 运动估值的当前块和参照块4 2 图4 1 3 运动估值核心代码4 3 图4 1 4 桢长和桢移4 4 图4 1 5r a s t a 流处理数据流图4 7 图4 1 6 频谱计算4 8 图4 1 7k e r n e l 中的频谱计算4 8 图4 1 8 频谱计算核心级代码4 9 图4 1 9 多个临界带的处理5 0 图4 2 0c b r a n d 核心级程序5 0 图4 2 1i d f t 计算原理示意图5 1 图4 2 2i d f t 流计算示意图5 2 v i l 幽目录 图4 2 3r p e l t p 语音编码算法示意图5 3 图4 2 4g s m 流编程数据流图。5 5 图4 2 5 短时滤波处理5 6 图4 2 60 簇上的计算5 7 图4 2 7 滤波过程5 9 图4 2 8 控制点分布区域图6 0 图4 2 9e p i c 流编程数据流图6 1 图4 3 0d l p 执行模式6 4 图4 3 1t l p 执行模式6 5 图5 1 时间开销统计图7 4 图5 2 流长度对性能的影响7 5 图5 3 循环展开和软件流水带来的性能影响7 5 图5 4 数据带宽层次7 7 v i l l 表图录 表目录 表1 1 典型的并行计算基准测试程序组5 表3 1m e d i a b e n c h 的组成_ 2 3 表3 2 多媒体基准测试程序的流并行性2 7 表5 1 流程序的输入数据集6 9 表5 2 p r o f i l e 得到的程序局部特征7 l 表5 3 性能指标统计值7 2 i x 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 扩k ： a 叼莎年胪月列日 第1 章绪论 1 1 研究背景和意义 第1 章绪论 应用需求在计算机系统的发展过程中一直都起着主导作用，新的应用需求 驱动新的系统设计。随着多媒体应用对计算机性能要求的r 益提高，新型的流 处理器体系结构己成为工业界和学术界的研究热点，带来了许多新的需要探索 和解决的体系结构关键技术问题。对于一个新型的流体系结构研究来说，实现 创新的最大障碍就是目前并不清楚如何在这种体系结构上最好地表达和执行并 行计算，使用现有的多媒体基准测试程序来进行流并行计算的研究是不合理 的，有必要丌发一套流基准测试程序包来满足流体系结构研究的需要。我们在 对流体系结构以及流编程模型进行全面和深入研究的基础上，基于一个学术的 流处理器体系结构研究模拟实验环境( 包括编程模型以及编程语言、编译环境、 时钟精确模拟器和统计工具) ，针对一套完整的多媒体基准测试包m e d i a b a n c h ， 分析其中各个程序中的流并行性，对于其中适于流并行化的程序设计并实现了 流并行程序版本，作为流体系结构研究的基准测试程序，并对流基准测试程序 的应用进行实验评测。 本文介绍了开发流基准测试程序的过程以及涉及到的一些关键技术问题和 方法。 1 1 1 流式应用对体系结构提出的新的要求 在日常应用中，多媒体程序是计算量巨大的应用，现有的计算机系统还不 能做到应付自如。仔细研究这些程序的特点，可以看出计算量主要集中在多媒 体运算，包括视频，声音，图像，文字等的编码解码，分析处理，显示转换 等。多媒体处理本身具有如下的一些特点： ( 1 ) 数据总量巨大。这个特点是很显然的。一部普通的v c d 的数据量在 1 g b 1 2 g b 之间，而一部d v d 的数据量在4g b 5 g b 之间。即使 是m p 3 格式的一首歌的数据量也常常在l o m b 左右。而这些数据还都是 高度压缩的，其压缩比在1 0 1 0 0 之间。媒体在计算机上的绝大部分处理 首先要还原数据，其数据量就更大了。 第1 章绪论 ( 2 ) 活动数据量相对也比较大。所谓活动数据，是指在一段时l 训内需要反复 访问的数据。比如，有人测算后得出，m p e g 2 解码程序的活动数据量约 为2 m b 。其它的应用其活动数据量会有出入，但一般都比较大。 ( 3 ) 绝大多数数据仅访问一次或少数几次。从上面的数据可以看出，活动数 据量仅占数据总量的很小一部分。所以，除了活动数据以外的数据，其 访问频率是很低的，很多情况下只访问一次。 ( 4 ) 所有的数据都要访问。比如，播放v c d 一般要从头到尾全部放一次，所 有数据都用到了。 ( 5 ) 在同一个应用中，绝大多数数据的处理是一致的。即这些数据将带入同 一个公式进行运算。 ( 6 ) 应用有明显的整数浮点分别。某些应用几乎只使用整数运算，而另一些 运算则大量采用浮点运算。采用整数运算的应用一般是编码解码、显示 转换等应用。采用浮点运算的应用一般是分析处理一类，通常称为“智能 算法”，比如语音识别等。 ( 7 ) 核心循环的代码量一般很小。因为数据总量是巨大的，如果核心循环再 复杂，整个程序的执行速度将无法接受。 从上述的特点可以看出，计算机系统必须要有针对性地提供相应的功能支 持才能快速地处理这些程序： ( 1 ) 快速的数据交换速度。多媒体应用的所有数掘都必须处理，所以数据必 须全部从一个部件传递到另一个部件。于是部件间的数据交换速度极大 地影响了整体性能。这些数据交换通道包括硬盘到内存，内存到c p u ， c p u 内部等。这些通道的带宽都必须足够大才能满足多媒体应用的要 求，任何一个地方的瓶颈都将影响整个系统的性能。 ( 2 ) 大的片上存储空间。由于多媒体应用活动数扼量比较大，大的片上存储 空间就对性能提高有很大的帮助。特别是在现有的内存带宽非常有限的 情况下。 ( 3 ) 向量运算指令集。 ( 4 ) 快速的整数a l u 和浮点a l u 。 这些要求是传统的通用处理器所不能满足的，而专用处理器又具有一定的 局限性( s e l l i a hr a t h n a m ，1 9 9 6 ) ，新型的流体系结构( m s c o t tr i x n e r ，2 0 0 1 ) 应运 而生。与此同时也提出了流应用的概念。所谓流，就是不问断的、连续的、移 第1 章绪论 动的数据队列，队列长度可以是定长或不定长的，流元素的组成可以是复杂的 或简单的。流应用具有以下几个主要特征： ( 1 ) 计算密集性：流式应用对每次从内存中耿出的数据都要进行大量的算术 运算，称为计算密集性。计算密集性可用计算访存比( 对每次取进的数据 执行的操作个数) 量化，流应用的计算访存比一般在2 0 以上，意味着对 每次从内存中取进的数据都要进行大量的算术运算。 ( 2 ) 并行性：流应用中的运算可以并行，并且以数据级并行为主，同时存在 指令级和任务级并行。 ( 3 ) 局部性：局部性可以分为数据重用局部性与生产者消费者局部性。数据 重用局部性是指在执行计算核心程序时重复使用的系数和数据，主要是 多媒体运算中的活动数据量。生产者消费者的局部性体现在计算流水线 的不同阶段中，即生产出的数据( 即一个计算核心程序写的数据) 被另一 个计算核心程序所消费( 被读取) ，且不会再被生产数据的计算核心所使 用。 可以看出，流应用的特点是由多媒体应用的某些特点提取后得到的，从多 媒体应用程序中必然能够提取可观的流并行性。 1 1 2 流体系结构与其他处理多媒体应用的体系结构的比较 流体系结构是近年来出现的一种面向高性能媒体处理的体系结构。 与通用处理器体系结构相比，传统的通用微处理器体系结构主要建立在指 令级并行处理的基础上，采用c a c h e 来利用数据重用性，从而减小了数据访问 延迟。复杂的c a c h e 优化机制降低了数据访问带宽。但是在数据并行应用中， 要求的数据供应量大，并且数据重用性极低。采用c a c h e 给运算单元供应数 据，不仅容量有限，无法为大量的计算单元提供数据；而且没有重用性的数据 经过复杂的c a c h e 机制来存取反而会降低数据访问的性能。最根本的问题是， 指令级并行处理器上的运算单元极其匮乏，不能很好地开发数据并行性。 与媒体专用的处理器相比，专用媒体处理器通过硬件的方法把特定的多媒 体处理功能实现在一片或多片超大规模集成电路上，这类媒体处理器具有性能 高、价值便宜、省电、系统设计简单等优点，但缺点是功能固定，不能用于其 它媒体处理。 第1 章绪论 与通用处理器上的多媒体扩展相比，通用处理器只是专门提供了多条专用 指令，从而使得执行多媒体应用所需的指令数量减少，但是由于受到处理器性 能的局限，通用微处理器目前只用于有限的一些媒体处理的应用( 如m p e g 解 压缩等) ，对计算量大的应用( 如m p e g 压缩) 还不能达到实时处理的性能。 流体系结构的主要特点是采用大规模的运算阵列和多级存储层次来满足媒 体处理所需要的密集计算以及频繁访存。它结合了通用微处理器和专用媒体处 理器的优点，既可达到很高的处理性能，又有可编程和可适应不同媒体处理要 求的特点。 1 1 2 流体系结构研究对基准测试程序提出新的要求 现在国际上正积极开展新型体系结构的研究，涌现出i m a g i n e ( b k h a i l a n y ， 2 0 0 1 ) 、r a w ( m b t a y l o r ，2 0 0 2 ) 、v i r a m ( c e k o z y r a k i s ，19 9 9 ) 和s c o r e ( e y l o n c a s p i e t ，2 0 0 1 ) 等多种面向1 0 亿只以上晶体管的新型流体系结构。它们都特别强 调对流应用的支持，在硬件上都拥有大量的本地寄存器，并提供许多简单廉价 快速的计算单元、相对简单的指令发射逻辑、多级存储层次避免全局通讯等 等，如何对这种新型的体系结构做出公正的评价，并为新系统的设计提供有用 的信息，都是基准测试程序所面临的新的挑战。 新的基准测试程序开发必须针对流体系结构的特点，可以反映流式应用的 主要特征，能够客观、公正地评价机器的性能。但真f 做到完全公正并非易 事，要涉及到的因素很多，包括体系结构、编译优化、编程环境、测试条件、 解题算法等。本文所做的研究正是试图在这些方面给出一些方法以及建议。 1 2 并行基准测试程序的研究现状 1 2 1 并行基准测试程序 已经在使用的并行计算基准测试程序有很多，有的用来研究整个系统的总 体性能，有的用来测量计算机系统某一特定方面的性能。下面是几个比较典型 的并行基准程序组的介绍。 从下表中可以看出已有的并行基准测试程序一般都集中在科学计算的领 域，包括各种各样的数值计算，主要开发指令级并行性。而且各个不同的基准 测试程序都有偏向性地针对了不同体系结构的并行机，用来测试该并行机某一 方面或者系统的整体性能。流体系结构与已有的并行机在结构和编程模型卜都 第1 章绪论 有很大的不同，针对的应用领域也不同，所以用这些并行计算基准测试程序来 测试流体系结构的性能是不适当的。 表1 1 典斑的并行计算基准测试程序组 基准测试源代码 应川特征 程序名语言 测试一致性共享地址空间的机器的b e n c h m a r k ，由两个部 s p l a s h 2 c 分组成：4 个k e r n e l 程序和8 个a p p l i c a t i o n 程序两个部分 组成，代表了科学、1 1 j 程计算，图形方面的应用 基于m p i 由5 个核心( e p 、m g 、c g 、f t 、i s ) 和3 个模拟戍用 n p b 组的f o 九r a n ( l u 、s p 、b t ) 程序所绢成。l s 中的人部分计算是整数 算术运算，而其它几个基准稃序均是浮点密集计算。主 源代码 要评估并行超级计算机的性能 重点放在可扩放、分布存储、消息传递的体系结构上， p a r k b e n c f o r t r a n 7 7 测试基本体系结构参数，并行计算机的基本通信性能 h ( c o m m s ) ，计算速度和通信速度的比) 以及同步的能力以 及数据移动平i o 访问 用丁测试不同u n i x 平台上0 s 开销以及处理器、高速缓 l m b e n c hc 存、主存、网络和磁盘之间的数据传输能力，对识别性 能瓶颈和系统殴计很有川 测试可持续的存储带宽( m b s ) 以及相应的计算机速率， s t r e a mc ，f o r t r a n 主要用来测量主存带宽的b e n c h m a r k ，也可以川米测试 c a c h e 的带宽 针对c f d ( 计算流体力学) 方面的计算，模拟大型c f d n a sp a r a l l e i f o r t r a n 中计算和数据的移动特征，主要是为了比较各种并行机 b e n c h m a r k 的性能。测试范同从整数排序到复杂的数值计算 对高性能计算机进行比较全面的评价，除反映处理器的 h p c cc 性能外，更多地考虑内存、网络等全面的特征 1 2 2 多媒体应用领域的基准测试程序 与传统处理器不同，一些适应了指令级并行性编译器需要的，带有v l i w 以 及s i m d 结构的微处理器也相继出现，绝大多数这种处理器以像多媒体和通信这 样的应用为目标，而不是通用程序，流体系结构也具有这样的特征。像s p e c 那 样的通用基准测试程序不能抓住多媒体和通信应用程序的本质特点，一些专用 的基准测试程序因此就被开发出来满足这个需要。其中包括d s p s t o n e ，这个基 准主要集中在汇编语言或者小计算核心的使用上，更侧重于核心编码和底层过 滤器操作。m e d i a b e n c h ( c h u n h ol e e ，1 9 9 7 ) 是第一个反映多媒体和通信系统应用 第1 章绪论 特征的基准测试程序包，也是第一个为了强调编译技术而仅仅使用高层语言的 基准测试程序包。它由完整的应用程序所组成，不是模型程序也不是代码核 心，包括从图象处理，通信和d s p 应用程序中精选出来的1 9 个应用程序，针对 多媒体和通信应用程序的基本特征，采用高级语言来编程，独立于处理器结构 和编译器，。另外还有伯克利大学丌发的b e r k e l e ym u l t i m e d i aw o r k l o a d ，这个 基准测试程序包建立在u c l am e d i a b e n c h 基础上，有一大部分应用是与 m e d i a b e n c h 重叠的，但能覆盖更多的多媒体处理，主要考虑应用的使用人数， 代码质量( 性能，鲁棒性) 和可维护性。 这些多媒体基准测试程序虽然在一定程度上匹配了流体系结构的应用领 域，但是并不能完全抓住流式应用的所有本质特点，而且由于所使用的编程语 言具有差异性，也使得这些基准测试程序不能直接用于流体系结构的性能评 测。 1 2 3 基准程序测试的使用方法 在对现有的并行基准测试程序进行介绍之后，下面进一步讨论对计算机系 统的性能进行预测的方法( 翟季冬，2 0 0 5 ) ，通常采用三种方法来进行测试。 1 基于程序模拟的性能分析。首先需要有一个将分析的某种体系结构的模拟 器，然后在这个模拟器上运行应用程序的每个动态指令。由于每个指令被 模拟，所以模拟器能够产生一个应用程序精确的性能预测，但是需要很长 的时间才能够得到程序的性能。 2 基于剖析( p r o f i l e ) 的性能分析。通过使用插装工具运行应用程序一次，然 后产生这个应用程序的统计信息。这个统计信息包括，程序中基本块的个 数，每个基本块的起始位置，每个基本块执行的次数等信息。然后把这些 统计信息输入一个分析工具，最后得到程序运行时白j 的一个估计。这种方 法的速度会比较快，但是需要考虑指令之间的相互作用。 3 回卷预测性能分析。隔离出每个影响性能预测的因素，最后把这些因素合 成到一起，得到性能的预测。可以分为三个部分：先单独分析机器的特 性，得到机器的一个特征描述，然后静态的分析程序轮廓，通过机器特征 和程序轮廓的某种影射关系而得到程序的性能预测。 这三种方法各有优缺点，第一种方法的模拟时问让人难以接受，改进的方 法是提取有代表性的一部分数据，同时保持原有数据的有效性，从而达到减少 第1 章绪论 模拟时间的效果。由于现在微处理器将乱序发射、超标量等技术引入，导致第 二种方法使用的基本块隔离的技术已经不能精确预测程序的性能，改进的方法 是在调度每个基本块的时候，不单考虑每个基本块的执行时间，也要考虑每个 基本块对它相邻的基本块的时间影响。而第三种方法主要是针对访存密集型应 用会产生很好的预测效果。实际操作时是根据应用程序的特征以及机器的特点 选择其中的几个方法结合来进行预测的。 以上的预测模型主要集中在串行程序的预测，对于并行程序的性能分析研 究工作很少，主要是由于并行应用程序的性能预测是复杂的，它是程序算法、 编译器、操作系统、处理器的体系结构、互联网络等一系列影响因素的函数。 本文是在考虑各种因素的基础上，利用第一种方法与第二种方法结合的方式对 性能进行预测的。 总的说来，进入2 1 世纪以后，微处理器的市场已从以s p e cc p u 2 0 0 0 所代 表的传统的科学技术应用，扩展到多种应用领域，尤其是增长份额最快的嵌入 式应用领域。应用从计算密集型转向数据密集型，并且很少有数据重用的特 点，都使得传统的单线程串行计算模型和采用指令级并行技术的单处理器结构 处理这类应用的能力很差。为了获得更高的微处理器性能，需要丌发更多更半f l 粒度的片上并行性，如数据级并行性和线程级并行性。与此同时，c p u 性能基 准测试不仅要包括指令级并行应用，而且要包括数据并行类应用和线程级并行 类应用，以及混合各种并行性的各类并行计算类应用，用于评测未来可能存在 的各种类型的c p u 性能。 随着国际上对新型流体系结构的日益关注，在对流体系结构模型本质特征 进行研究之后，本文认为开发流基准测试程序将是未来基准测试程序发展的重 要方向之一。多媒体领域是流式应用的最初背景，可以考虑从中丌发流基准测 试程序，但是媒体处理又不能完全概括流式应用的主要特征，所以可供研究的 应用领域也更为广阔。开发流基准测试程序尚处于起步阶段，有许多关键问题 值得研究。 1 3 论文的研究目标和主要工作 在上述研究背景下，本文选择了“流基准测试程序的丌发及其流并行性分 析”作为研究课题，试图开发出一套针对多媒体应用领域的流基准测试程序 第l 章绪论 包。文中主要对多媒体基准测试程序m e d i a b e n c h 进行了详细的分析，并挑选出 几个最符合流式应用基本特点的应用程序进行了流并行程序设计。 论文的研究内容包括： 1 ) 对典型的流体系结构进行系统的分析和研究。研究内容涉及i m a g i n e 的流体 系结构、流处理的特征、流编程模型以及流编译系统等。 2 ) 对多媒体基准测试程序m e d i a b e n c h 做详细的流并行性分析，总结出从应用 中提取流并行性的方法。 3 ) 研究在流处理器上开发流基准测试程序的方法和关键技术。 4 ) 评测对流应用的执行性能造成影响的因素，对硬件结构、编译系统以及流 并行程序设计方法提出改进建议。 本文的研究主要得到国家9 7 3 项目的支持。 1 4 论文的结构 论文共分为6 章。 第一章介绍了课题的选题背景及研究意义。 第二章介绍了典型的具有流体系结构特征的i m a g i n e 流处理器，详细描述了 i m a g i n e 软硬件的各个方面以及流编程模型到流体系结构上的映射原理。 第三章分析了多媒体基准测试程序中的流并行性，提出丌发多媒体程序中 流并行性的基本依据和基本方法。 第四章描述了5 个典型多媒体应用程序的详细流并行程序设计过程，讨论了 程序设计过程中所使用的关键技术以及方法。 第五章提出t n 评流并行程序的分阶段模型，给出了不同角度的性能测评结 果，着重分析了对性能产生影响的因素以及消除这些因素所需要做出的软硬件 方面的改进。 第六章对本文的研究工作进行了全面的总结 第2 章流体系结构和流编程模型 第2 章流体系结构和流编程模型 流体系结构是个新的体系结构概念，是在应用需求的主导下产生的。目 前国际上涌现出了多种流体系结构，每种都有各自的流语言及编译器，已有的 流语言及程序设计模型包括s t r e a m c k e m e l c ( p e t e rm a t t s o n ，2 0 0 1 ) 、s t r e a m l t ( s a m a na m a r a s i n g h ee t a l ，2 0 0 3 ) 、b r o o k ( i b u c k ，2 0 01 ) 、c g ( s a m a n a m a r a s i n g h e ，2 0 0 3 ) 、s e q u o i a ( s a m a na m a r a s i n g h e ，2 0 0 3 ) 等。为了丌发流基准 测试程序，我们必须从现有的流体系结构中挑选出一个具有代表性的流处理器 作为研究平台和实现工具。在对这些不同种类的流体系结构做了比较之后( 王其 刚，2 0 0 7 ) ，我们将i m a g i n e 流处理器( w i l l i a mj d a l l y ，2 0 0 2 ) 选定为基准计 算机。 本章的内容主要是在国内外已有研究工作的基础上，结合我们的研究实 践，全面系统的分析了i m a g i n e 流处理器软硬件的各个方面。本章的工作为从多 媒体基准测试程序中提取流并行性提供了思想和依据，是本文的研究基础。 2 1i m a g i n e 流处理器体系结构 i m a g i n e 是由斯坦福大学在2 0 0 2 年丌发的一款可编程的流处理器，它作为 通用处理器的协处理器，主要处理运算密集型的应用。i m a g i n e 的硬件结构如图 2 1 所示，其核心部件为一个片上的流寄存器文件( s r f ) ，其他的所有部件， 包括8 个运算簇，一个微控制器( m c ) ，一个流存储系统( s m ) ，一个网络接 口( n i ) 以及一个流控制器( s o ) 都通过总线连接到了s r f 上。其中流控制器 可以控制流数据从片外d r a m 加载到s r f 中，或者从片外d r a m 中存储回片 外d r a m ，中间要经过流存储系统；微控制器可以将编译后的微代码从s i 讧中 加载到自己的内部空间从而控制8 个运算簇的具体计算：运算簇从s r f 读出数 据流进行具体的计算；网络接口可以实现多个i m a g i n e 芯片的互连。这样看来 i m a g i n e 的结构明显有别于冯诺依曼结构访存和计算部件是分离的，数据 访问也被分解成了多个存储层次，各自独立地运转。 第2 章流体系结构和流编程模型 2 1 1 运算部件 ， 2 56 g b i s 图2 1i m a g i n e 流处理器便1 ，i 二结构 i m a g i n e 流体系结构的一大特色是集成了大量的运算单元，图2 1 中只画出 了两个运算簇，事实上i m a g i n e 的运算部件是由8 个这样的运算簇组成的，每个 运算簇里面包含3 个加法器、两个乘法器、一个除法丌方器、一个拥有2 5 6 个 入口的便签薄( s c r a c h p a dm e m o r y ) 以及一个簇间通讯部件( c o m m u n i c a t i o n u n i t ) ，结构如图2 2 所示。另外其本地寄存器文件( l r f ) 是分柿式的，消除了传 统的集中式寄存器文件中可能存在的访问冲突。其中的便签薄可以存放一些查 找表或者小数组，使得不同的运算簇可以访问不同的数组元素；簇问通讯部件 是为解决运算簇间的数据依赖而设计的，运算簇可以在微控制器的控制下交换 彼此之间的数据，从而达到数据的重组。这样整个运算部件拥有4 8 个运算单元 的运算能力，每个运算簇内部由于具有多个运算单元可以在v l i w 机制的控制 下实现指令级并行，而8 个运算簇之间由于具有相同的控制逻辑可以实现数据 级并行，同时由于存在簇间通讯部件又具有了一定的灵活性。 l o 图2 2i m a g i n e 的运算簇结构 第2 章流体系结构和流编科模刑 2 1 2 流寄存器文件s r f 由于多媒体应用中绝大多数数据只访问一次，且使用过一次不会再使用， 所以i m a g i n e 摒弃了传统的c a c h e ，采用一种新的可编程片上存储部件s r f 来实 现数据流的传递，这是i m a g i n e 的另外一大特色。i m a g i n e 中的数据以流为单 位，流是记录的有序排列，流在s r f 中的存放是有序的，所以对流数据的访问 必须按序进行，不能随机访问。所有从片外d r a m 来的数据必须经过s r f 的缓 存，所有输入到运算簇上的数据必须从s r f 加载，这样就达到了计算和访存的 分离。这样做的好处有两个：( 1 ) s r f 足够大，可以将一个数据工作集完全存 放，如果这个工作集只需要进行一次处理的话，那么处理完毕后就可以将这个 数据工作集清除，事实上是被处理后产生的中间结果覆盖了，而中间结果又可 以被其他的计算核心所访问，此时所有的数据传递只在s r f 和运算簇的本地寄 存器之间进行，不需要访问内存，节省了宝贵的片外带宽。( 2 ) s r f 类似于一 个大的缓冲，当一个计算核心在进行计算的同时，可以将其他的流从片外 d r a m 加载到s r f 中，这样就使部分计算和访存重叠，相当于利用计算隐藏了 部分的访存延迟，减少了时间开销。 2 1 3 多级存储层次 i m a g i n e 的第三大特色是设置了多级存储层次( n u w a ns j a y a s e n a ， 2 0 0 5 ) ，在不同的存储部件之间形成了不同的带宽来对运算单元提供有效的支 持。越靠近运算部件的地方带宽越高，相应的片外d r a m 带宽就能设计的相对 较低，实现了对有限片外带宽的有效率利用。 i m a g i n e 的存储层次由分块的寄存器文件组织结构组成，包括本地的分布式 寄存器文件( l r f ) 以及分块的全局流寄存器文件( s r f ) 和片外d r a m 共同组 成。其特点如下： 1 ) 采用本地的分布式寄存器文件来支持运算单元。寄存器文件被分割成较小 的寄存器文件直接与各自的输入端相连接，由开关选择在运算单元和寄存 器之间传送数据。再将多个带有小寄存器文件的运算单元组织成若干个运 算簇，可以使面积、功耗以及线延迟都得到一定比例的降低。同时每个运 算簇只能对流寄存器文件s r f 中固定的部分进行访问，从而可以并行地对 并发的数据进行操作。 第2 章流体系结构利流编程模刑 2 ) 采用软件可管理的片上存储( 流寄存器文件) 取代硬件管理的c a c h e 。流寄 存器文件将运算单元从很长的不定的d r a m 访存延迟中有效地隔开，从存 储器中获得的数据只会在存储器和流寄存器文件( s r f ) 中进行传输。流寄 存器文件是软件可管理的，编译对运算单元和存储资源进行静态调度。 3 ) 充分利用d r a m 带宽。一方面对d r a m 的访问方式进行控制，以便能利用 好内部d r a m 的结构来最大化d r a m 带宽：另一方面，有效地组织利用片 内存储和带宽，使得需要和片外存储器进行的传输达到最小，避免浪费宝 贵的片外存储带宽。 通过组织这样的存储层次，运算所需数据被存放在运算簇内部，保证它能 被频繁的快速存取；核心程序之间的中白j 流数掘被存放在片上的流寄存器文件 中，使得它能够在核心程序间循环利用而不会产生存储器访问；最后，初始输 入、最终输出和其他的全局数据存放在外部d