（计算机应用技术专业论文）基于多核平台优化的ogre+3d渲染引擎.pdf

浙江大学硕士学位论文 摘要 摘要 随着计算机体系结构的发展，多核平台得到了越来越广泛的应用。多核平台 与并行计算理论相结合，以多线程并行的方式使应用程序性能大为提高。 然而在图形领域，多核平台的应用尚未展开。因此，本文对该领域中广为使 用的o g r e3 d 图形渲染引擎进行多线程并行优化，并在多核平台上进行验证， 从而得到一个性能提高的引擎，并证明多核平台和并行计算理论的优越性。 本文首先分析了o g r e 系统，从并行性角度整理了其整体框架，从中提炼出 3 d 渲染系统模块进行详细分析，继而总结出o g r e3 d 渲染系统并行化的三个方 向：多帧渲染并行化、循环迭代并行化、函数调用并行化。 本文还设计了o p e n m p 并行化时的数据保护控制、线程数量设置、线程调度 策略，使用o p e n m p 中的p r i v a t e 、b a r r i e r 、c r i t i c a l 等子句对数掘进行保护、同步， 避免多个线程访问时冲突，同时设置合适的线程数量以及采用最佳调度策略，使 性能提升最大化。 本文使用w i n 3 2 线程库对多帧渲染实现了并行化，使用o p e n m p 对循环迭代 和函数调用实现了并行化，使用o g r e 标准测试程序对优化后的引擎性能进行测 试，并且和优化前的引擎性能进行对比。实验表明并行化后性能提升比例从 2 7 7 0 到3 4 0 ，平：均在1 2 1 6 。 综上所述，本文在多核平台下结合并行计算理论，成功地对o g r e3 d 渲染 引擎进行了多线程并行优化，有效地提升了引擎的性能，验证了多核平台和并行 计算理论的优越性，达到了研究目的。 关键词多核，优化，0 g r e 渲染系统，0 p e n m p ，多线程，并行计算理论 浙江大学硕士学位论文a b s t r a c t a b s t r a c t w i t hc o m p u t e ra r c h i t e c t u r ed e v e l o p m e n t ，t h em u l t i - e o r ep l a t f o r mh a sb e e nw i d e l y u t i l i z e d c o m b i n e dw i t ht h ep a r a l l e lc o m p u t i n gt h e o r y , m u l t i - c o r ep l a t f o r mg r e a t l y i m p r o v e st h ea p p l i c a t i o n sp e r f o r m a n c eb yt h em u l t i - t h r e a dp a r a l l e l i z a t i o n h o w e v e r , m u l t i - e o r ep l a t f o r mh a sn o tb e e ne x p a n d e dt ot h eg r a p h i cf i e l d s ot h i s p a p e rt h r e a d st h eo g r e3 dr e n d e re n g i n ew h i c hi sw i d e l yu s e di nt h eg r a p h i cf i e l d , a n dv e r i f i e st h ee n g i n ei nt h em u l t i c o r ep l a t f o r m w h e nw eg e tao p t i m i z e de n g i n e ， w ep r o o ft h em u l t i - c o r ep l a t f o r ma n dt h ep a r a l l e lc o m p u t i n gt h e o r y sa d v a n t a g e t h i sp a p e rf i r s ta n a l y s e st h eo g r e s y s t e m so v e r a l lf r a m e w o r kf r o mt h ep o i n to f v i e wo fp a r a l l e l i s m t h e ni ta b s t r a c t sa n da n a l y s e st h e3 dr e n d e rs y s t e mm o d u l e si n d e t a i l ，a n ds u m m a r i z et h e3w a y so fp a r a l l e l i z i n gt h eo g r e3 dr e n d e rs y s t e m ，w h i c h a r em u l t i f r a m e sr e n d e r i n gp a r a l l e l i z a t i o n , l o o pi t e r a t i o n sp a r a i l e l i z a t i o n ，c a l lo f f u n c t i o n sp a r a l l e l i z a t i o n i na d d i t i o n ，t h i sp a p e rd e s i g n st h em e t h o d sw h e nu s i n go p e n m pt op a r a l l e l i z e ， w h i c hi n c l u d ed a t ep r o t e c t i o n , t h r e a d sa m o u n ts e t t i n g , t h r e a d ss c h e d u l i n g i no r d e rt o a v o i dt h ec o n f l i c tb e t w e e nt h r e a d sw h e na _ c c e s s i n gt h es a m ed a t ai nt h es a m et i m e ， t h i sp a p e ru s e st h eo p e n m pc l a u s e st op r o t e c ta n ds y n c h r o n i z et h ed a t a , s u c ha st h e p r i v a t ec l a u s e ，b a r r i e rc l a u s e ，c r i t i c a lc l a u s e ，a n ds oo n a n dt h i sp a p e rs e tt h ep r o p e r t h r e a d sa m o u n ta n dt h eb e s tt h r e a d ss c h e d u l i n g s t r a t e g i e s ，w h i c hm a x i m i z e st h e e n g i n e sp e r f o r m a n c e t h i sp a p e re m p l o y st h ew i n 3 2a p it op a r a l l e l i z et h er e n d e rf r a m e s ，a n du s e st h e o p e n m p t op a r a l l e l i z et h el o o pi t e r a t i o n sa n dc a l lo ff u n c t i o n s a tl a s t , t h i sp a p e r e x p l o i t st h eo g r e b e n c h m a r kp r o g r a m st ot e s tt h eo p t i m i z e de n g i n e sp e r f o r m a n c e ， a n dc o m p a r e si tw i t ht h eo r i g i n a le n g i n e t h er e s u l t ss h o wt h a tt h ep r o g r a m su p g r a d e d r a t i of r o m2 7 7 0 t o - 3 4 0 a v e r a g e d1 2 1 6 i ns u m m a r y , t h i sp a p e rs u c c e s s f u l l yo p t i m i z e st h eo g r e3 dr e n d e re n g i n eb y t h r e a d i n gi nt h em u l t i - c o r ep l a t f o r mt h a tc o m b i n e dw i t ht h ep a r a l l e lc o m p u t i n gt h e o r y , a n de f f e c t i v e l yu p g r a d e st h ee n g i n e sp e r f o r m a n c e s ot h i sp a p e ra c c u r a t e l yv e r i f i e st h e m u l t i - c o r ep l a t f o r ma n dt h ep a r a l l e lc o m p u t i n gt h e o r y sa d v a n t a g e ，a n da c h i e v e st h e r e s e a r c hp u r p o s e k e y w o r d sm u l t i c o r e ，o p t i m i z a t i o n ，o g r er e n d e rs y s t e m ，o p e n m p , m u l t i t h r e a d ， p a r a l l e lc o m p u t i n gt h e o r y 缸 浙江大学硕士学位论文图目录 图目录 图2 - 1 英特尔处理器的发展与摩尔定律 图2 2 单核、多处理器、超线程以及多核体系对比7 图2 - 3 并发和并行的区别 图2 4 英特尔酷睿处理器架构。 图2 - 5i b mc e l l 处理器架构。 图2 - 6 并行计算在各种领域的广泛应用 图2 7 指令串行执行示意图。 图2 - 8 指令并行执行示意图 图2 - 9 福林分类法。 图2 1 0 线程状态图 图2 i io p e n m p 的f o r k - j o i n 工作模式 图2 - 1 2o g r e 模块视图 图3 - 1 0 g r e 整体框架 8 1 0 1 1 1 l 图3 - 2r e n d e rs y s t e m 框架图2 3 图3 - 3r e n d e r t a r g e t 框架图。 图3 - 4 用于内部设置的部分_ s e t 函数一2 5 图3 - 5 部分s e t 系列和g e t 系列函数 图3 - 6b u f f e r 类框架视图 图3 7t e x t u r e 类框架视图 图3 - 8 帧的缓冲模式 图3 - 9 完整的帧渲染路径2 8 图3 1 0 多帧并行渲染的同步问题2 9 图3 1 1 双线程并行展开图3 0 图3 1 2 函数调用并行化 图4 1 用b a r r i e r 控制同步 图4 2 线程负载不平衡现象 图5 - 1 l n e 取样分析图 图5 - 2 i h e 调用曲线图 图6 - 1o g r e 项目视图 图6 - 2o p e n m p 编译开关 4 2 图6 - 3b s p c o l l i s i o n 运行结果图 h i 4 2 4 5 4 6 浙江大学硕士学位论文 表目录 表目录 表3 - 1o g r e 模块分类及其功能 表4 1 线程个数与运行时间对照表 表4 2o p e n m p 的调度策略 表4 - 3o p e n m p 结构和子句时间开销列表 表4 - 4 各种调度策略性能对比 表6 - 1 性能优化对照表。 i v 4 7 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题背景 自从上个世纪7 0 年代世界上第一个处理器4 0 0 4 诞生【1 】，处理器的发展进入 了黄金时期。在接下来的3 0 多年时间里，处理器遵循着摩尔定律【2 】即“每1 8 个 月左右的时间里处理器芯片集成的晶体管数量翻番，处理器频率提高一倍”的模 式发展，诞生了8 0 8 6 、8 0 2 8 6 、8 0 3 8 6 、8 0 4 8 6 、p e n t i u m 、p e n t i u m 、p e n t i u mi l l 、 p e n t i u m4 等一系列里程碑式的处理器【3 】，走进了千家万户，极大的促进了工业 的发展、科学的进步、技术的创新，是划时代的科技革命。 但到了2 1 世纪初，处理器的发展遇到了瓶颈。摩尔定律难以保持下去。随 着晶体管的密度不断提高，芯片的发热量越来越大，晶体管的电流泄漏也越来越 严重，集成电路工艺的提升越来越困难；与此同时，超标量、超长指令字和多级 流水线等指令级并行的实现越来越困难，控制逻辑越来越复杂【4 】。芯片制造业在 发展到巅峰之后，遇到了一个非常棘手、现实的难题：即如何解决在增大处理器 外频、提高处理器速度的同时减少发热量及电池能耗。 在这种情况下，多核处理器应运而生。多核处理器将多个处理器内核集成到 一个芯片里，既降低了功耗，又提高了处理器工作效率。多核处理器以其独特的 体系结构，提高了c p u 性能，将摩尔定律延续下去【5 】。英特尔、a m d 、i b m 等 主流c p u 生产厂商都在向多核处理器转变【6 】，从单核平台向多核平台的转变是 必然的，今后多核平台的应用将会越来越广泛，无论是个人计算机、服务器或是 嵌入式等领域，多核平台会全面取代单核平台，成为今后处理器发展的主流方向。 并行计算理论【7 】在上世纪7 0 年代左右提出，它将一个大型的任务拆解成多 个小型的任务共同完成，能大幅度提高计算性能【8 】。并行计算已经广泛应用于工 业设计、科学计算、商业应用等各种领域，并行化的成本优势与应用对性能上的 需求相结合，有力的推动了并行计算的应用【9 】。 并行计算在应用程序中通常表现为相对的微观和宏观两个方面。微观方面即 指令级并行( i n s t r u c t i o nl e v e lp a r a l l e l ) 【1 0 】，例如第2 章中将会提到的单指令多 数据流( s i m d ) 和多指令多数据流( m i m d ) 【1 1 ，许多目前广泛应用的指令集， 例如英特尔的m m x 1 2 、s s e 、s s e 2 、s s e 3 、s s s e 3 、s s e 4 1 3 指令集，i b m 的 p o w e r p c 指令集【1 4 】等等都属于这个范畴；宏观方面即线程级并行( t h r e a dl e v e l p a r a l l e l ) 【1 5 】，它通过任务分配机制，将大规模的计算分解为多个小规模的计算， 浙江大学硕士学位论文第1 章绪论 以线程为基本单位进行分配，多个线程并行完成任务，提高工作效率。多线程编 程用到的方法主要有w i n 3 2 线程库 1 6 1 并1 1o p e n m p 【i t 。本文对并行计算的应用 是线程级并行，即多线程并行化。 o g r e ，即o b j e c t o r i e n t c d g r a p h i c s r e n d e r i n g e n g i n c 的缩写，是一款面向对 象的图形渲染引擎 1 8 1 。o g r e3 d 渲染引擎是一个图形系统，它的类库提供了大 量接口类和函数，并对底层的d i r e 0 3 d 等图形库进行抽象，使得开发者可以非常 轻松的调用o g r e 图形渲染引擎制作出各种各样的图形系统。此外，o g r e3 d 渲染引擎是一款开源的图形引擎，由大量的专业技术人员开发和维护，更新迅速， 功能十分强大，目前已广泛应用于游戏设计、科学模拟、图形学等多个领域。 目前，多核平台推出的时间尚短基于多核平台的研究和应用尚未完全展开， 特别是图形图像领域的计算性能方面 1 9 1 ；而并行计算理论虽然很早就已经被人 提出，并且已经得到了广泛的应用，但以往对并行计算的应用主要集中于集群、 指令集、多处理器等领域，在多核平台上尚缺乏应用与研究 2 0 1 ：此外，o g r e3 d 渲染引擎虽然应用很广泛，但在多线程并行优化方面的研究不多，而且前人的研 究只使用了w i n 3 2 线程库这一较为底层的方法进行优化1 2 1 1 ，性能提升有限。 本文的研究立足于通过线程这一基本单位将多核平台和并行计算联系起来， 对o g r e3 d 渲染引擎进行多线程并行优化，同时引入了o p e n m p 进行优化，进 一步提高了o g r e3 d 渲染引擎的性能，也证明了并行计算和多核平台的优越性。 1 2 本文主要工作 基于上一节的课题背景，本文设计了一个基于多核平台优化的o g r e3 d 渲 染引擎。本文首先对相关背景和技术知识进行了综述，分别介绍了多核概述、体 系结构，并行计算理论、系统结构、编程技术，以及o g r e3 d 渲染引擎体系结 构及其3 d 渲染系统；然后对o g r e3 d 渲染引擎进行了系统分析，从并行性角度 整理其整体框架，筛选出其中的渲染系统模块，并总结出渲染系统模块中适合进 行多线程并行优化的区域，有多帧渲染、循环迭代、函数调用三个方面；同时还 设计了用o p e n m p 进行并行化时的数据保护控制、线程数量设置、线程调度策略； 接着具体实现了上述的设计方法，其中采用w i n 3 2 线程库对多帧渲染进行并行化， 采用o p e n m p 编译制导对循环迭代和函数调用进行并行化。 在完成了o g r e 渲染系统分析、o p e n m p 并行优化设计和具体实现之后，为 验证该优化后的渲染引擎性能改进，在双核平台上用标准测试程序对其进行了测 试。测试结果表明，该优化的o g r e3 d 渲染引擎性能得到了较大提升，证明了 2 浙江大学硕七学位论文第1 章绪论 本文的观点。 1 3 主要研究难点 本文的主要研究难点有以下几个方面： o g r e 3 d 渲染引擎是个相当复杂的系统，功能强大，模块众多，分支广泛， 而且各模块、类、函数之间的联系千丝万缕，相互之间的数据关联很密切。 因此，对o g r e 3 d 渲染引擎进行详细的系统分析，整理其整体框架以及其渲 染系统模块内的类、函数之间的关系，是一个难点。 o g r e 渲染系统非常庞大，归纳其适合多线程并行优化的区域，也是一个难 点本文除了参考前人的研究和自己的分析之外，还引入了专业的性能分析 工具英特尔v t u n e 性能分析器，也可以看为一个创新之处。 为了提高优化效率，本文除w i n 3 2 线程库之外，还使用了o p e n m p 进行并行 化。当使用o p e n m p 进行并行化时，o p e n m p 的各种结构、予句都有一定的 时间开销，对系统性能和优化效率有相当大的影响。因此，在使用o p e n m p 并行化时如何掌握好数据保护控制、线程数量设置、线程调度策略等结构和 子句，使优化效率尽可能高，是一个难点。 此外，在并行化时如何处理并行区域内的各种数据，使用各种原语、临界区、 栅栏等方法来保证线程之间的同步、数据访问的安全，也是一个难点。 1 4 论文组织结构 本文后续章节按照如下结构进行组织： 第2 章为文献综述部分，介绍了一些本文用到的背景知识和技术。 第3 章为系统分析部分，着重于对o g r e 渲染系统进行分析。 第4 章为优化设计部分，设计了用o p e n m p 进行并行优化时的数据保护控制、 线程数量设嚣、线程调度策略。 第5 章为具体实现部分，根掘第3 章和第4 章中的分析和设计进行详细实现。 第6 章为结果分析部分，根据第5 章的具体实现方法对o g r e 渲染引擎进行 修改，然后用标准测试程序测试性能，并且和优化前的性能对比，验证优化效果。 第7 章为总结和展望部分，首先对本文的研究和创新工作进行总结，总结本 文已获得的成果和仍然存在的不足之处，然后对未来的工作进行展望，指出能改 进的方面和今后的努力方向。 3 浙江大学硕七学位论文第2 章相关背景及技术简介 第2 章相关背景及技术简介 2 1 多核概述 2 1 1 处理器的发展 众所周知，处理器是计算机中最重要的部分，包括逻辑单元、运算单元、控 制单元、一级c a c h e 以及二级c a c h e 2 2 等等。处理器在计算机体系中的地位相当 于人的心脏，如果处理器出了任何故障，整台计算机都无法运转。处理器根据其 处理数据的字长可以分为：4 位、8 位、1 6 位、3 2 位以及6 4 位处理器等等。 在计算机领域，无论是个人计算机，还是商用高性能计算机，甚至是超级巨 型计算机，处理器的参数、规格与频率都经常被用来作为判断一台计算机性能高 低的重要指标1 2 3 1 。处理器的发展与计算机的发展相辅相成、互相促进，并且在 一定程度上可以说，处理器的发展水平即代表了计算机的发展水平。 从上个世纪7 0 年代开始，处理器进入了一个突飞猛进的发展年代，许多知 名厂家，如英特尔、a m d 、m m 、摩托罗拉等，都是依靠开发处理器起家，依靠 众多工程师的智慧结晶、先进的生产工艺，层出不穷的推出了一代又一代处理器， 造就了处理器发展史一座又一座的里程碑。随着处理器集成晶体管数量越来越庞 大，主频越来越高，处理器的性能也越来越强大。 1 9 7 1 年，世界上第一个处理器4 0 0 4 诞生，它由英特尔开发，集成了2 3 0 0 个 晶体管，每个晶体管之间的距离为1 0 微米，能处理4 位数据，每秒运算6 万次， 时钟频率为1 0 8 k h z 1 ；1 9 7 8 年，英特尔推出了1 6 位的8 0 8 6 处理器，同时还生 产出与之相配合的数学协处理器8 0 8 7 ，8 0 8 6 集成了2 9 0 0 0 个晶体管，时钟频率 为4 7 7 m h z ；1 9 8 2 年英特尔推出8 0 2 8 6 处理器，它集成了1 4 3 万个晶体管，时 钟频率提高到了2 0 m h z ；1 9 8 5 年英特尔推出8 0 3 8 6 处理器，它集成了2 7 5 万个 晶体管，时钟频率为1 2 5 m h z ，后逐步提高到2 0 m h z 、2 5 m h z 、3 3 m h z ，最高 为4 0 m h z ；1 9 8 9 年，英特尔推出8 0 4 8 6 处理器，它集成了1 2 0 万个晶体管，时 钟频率提高到5 0 m h z ；1 9 9 3 年，英特尔推出8 0 5 8 6 处理器，即大名鼎鼎的p e n t i u m 处理器，它集成了3 1 0 万个晶体管，时钟频率最高为2 0 0 m h z ：1 9 9 5 年，英特尔 推出p e n t i u mp r o 处理器，它集成了5 5 0 万个晶体管，时钟频率最高为2 0 0 m h z ： 1 9 9 7 年，英特尔推出p e n t i u mi i 处理器，它集成了7 5 0 万个晶体管，时钟频率最 高为3 0 0 m h z ；1 9 9 9 年，英特尔推出p e n t i u mi i i 处理器，它集成了9 5 0 万个晶体 管，时钟频率最高为1 4 g h z ；2 0 0 0 年，英特尔推出p e n t i u m4 处理器，它集成了 4 浙江大学硕士学位论文 第2 章相关背景及技术简介 4 2 0 0 万个晶体管，时钟频率最高己经达到将近4 g h z 2 4 。 早在1 9 6 5 年，英特尔c e o 戈登摩尔就已经预见到了处理器迅猛的发展趋 势，当时他通过观察元件复杂度和时间之间的对数线性经验关系 2 5 1 ，根据各项 实验数据，把元件数量每增长一倍的时间修改为一年半左右，并预测从1 9 7 5 年 起按这个降低后的速度增长，这就是著名的摩尔定律【2 卜_ 芯片的晶体管数量每 一年半左右增长一倍。许多年以来，这条经验定律令人惊奇地在处理器发展历程 上反复地得到验i 正1 2 6 ，如图2 - l 所示： l l a n s l s t o r s 图2 - 1 英特尔处理器的发展与犀尔定律 引用自h t t p ：w w w i n t e l c o n 型t e c h n o l o g y m o o r e s l a w i n d e x h t m 2 1 2 从单核到多核 摩尔定律并不仅仅是一个商业性的预测，而是一场革命计算机行业的革 命。摩尔定律从上个世纪7 0 年代起，一直引导着计算机行业以及半导体行业前 进，在过去的3 0 年里，处理器的发展也在不断的验证这条定律。可是到了二十 一世纪，摩尔定律在受到广泛关注的同时，也由于它的局限性遭受了越来越多的 争议。众所周知，促使处理器性能不断提高的动力主要基于这两个：一是半导体 工艺的逐渐进步，二是处理器体系结构的不断发展1 2 7 。它们相辅相成，互相刺 激以促进对方的发展。但是到了二十一世纪，这个规律已经很难保持下去，如同 上文提到的半导体工艺限制，处理器的频率已经很难再有所提高。经过3 0 多年 s 浙江大学硕士学位论文 第2 章相关背景及技术简介 的发展，英特尔公司的p e n t i u m4 处理器最高频率己接近4 g ，集成的晶体管数量 有数亿个，半导体工艺已经达到了物理极限，很难再提高处理器的频率。 此时多核处理器的概念逐渐被人提出，所谓多核，即在一个单芯片上面集成 两个甚至更多个处理器内核，其中每个内核都有自己的逻辑单元、控制单元、中 断控制器、运算单元，一级c a c h e 、二级c a c h e 共享或独有，其部件的完整性和 单核处理器内核相比完全一致 2 8 1 。多核处理器是时代发展、技术进步、社会需 求的必然产物，有以下几个因素 z 7 1 ： 按照目前晶体管的增长规律，预计到2 0 1 0 年，单个芯片上集成的晶体管数量 将达到1 0 亿个【2 9 。如此巨额的晶体管数量，单核很难完全利用，而多核通 过多个处理器内核在单个芯片上分散开，可以有效利用这些晶体管。 随着晶体管集成度越来越高，晶体管体积越来越小，晶体管之间的线路延迟 越来越大。当晶体管做到1 8 0 纳米级甚至更小时，线路延迟会超过晶体管内 部的门电路延迟，而成为整个集成电路的性能瓶颈1 3 0 1 3 1 1 。以往单核处理器 统一采用典型的集中型架构，所有信号都送往中央内核，线路延迟较大；而 多核处理器采用的架构是分布式架构，即在单个芯片上分散集成多个处理器 内核，全局型的信号大大减少，从而减少了线路延迟带来的影响 3 3 1 。 f r e dp o l l a c k 曾提出过著名的p o l l a c k 规贝1 j 3 2 】：对于给定的工艺技术( 如 c m o s ) ，新一代的处理器微体系结构和前一代的微体系结构相比要多占1 - 2 倍的面积，但只能提高4 0 6 0 的性能。如果一个处理器的硬件逻辑提高一倍， 至多能提高性能4 0 ，而如果采用两个简单的处理器构成一个相同硬件规模 的双核处理器，则可以获得7 0 8 0 的性能提升，同时在面积上也同比缩 , 1 , 2 7 1 。 随着芯片晶体管集成度越来越高，芯片的发热量越来越大，功耗也随之增高。 多核处理器通过将任务分散到多个内核，每个内核频率稍微降低，可以有效 减少芯片热量，降低功耗。 设计一款新的处理器体系需要消耗大量的人力和财力成本，而多核处理器可 以重复利用先前的设计，提高内核重复利用率，同时多个核共享c a c h e 、外 部总线等硬件，能降低成本。 目前的主流应用对多线程并行要求非常高，例如网络应用、数据挖掘等方面。 从计算机体系结构的角度看，多核处理器对处理器资源利用率高，模块化设 计更为简洁，而且对共享资源的争夺较少，当应用程序的线程级并行性较高 时，能获得更好的性能。 6 浙江大学硕十学位论文 第2 章相关背景及技术简介 2 1 3 多核体系 多核处理器通过在单个芯片上集成多个处理器内核，每个核都是相互独立的 处理器，都具有自己的逻辑单元、控制单元、执行单元，c a c h e 可能共享也可能 不共享。多核处理器和其它处理器体系结构对比【3 4 】如图2 2 所示： c p u 状态 c p u 状态 中断逻辑中断逻辑 i i 执行单元i h 超线程 c p u 状态 中断逻辑 执行单元 c a c h e 多处理器 图2 - 2 单核、多处理器、超线程以及多核体系对比 早在单核处理器时代，应用程序已经支持多线程技术。单核内的多线程运行 是串行的，即并发性( c o n c u r r e n c y ) ，多个线程交替执行，在同一时刻只能有一 个线程执行；多核内的多线程运行是并行的，即并行性( p a r a l l e l i s m ) ，多个线程 同时执行，同一时刻可以有多个线程执行【3 5 】，图2 - 3 展示了两者的区别。多核 体系通过增加计算机中物理处理器的数量，能够有效利用线程级并行性。多核处 理器系统支持真正意义上的并行执行，多个线程或者进程能够在多个处理器内核 上同时执行。 并行执行 图2 - 3 并发和并行的区别 多核体系很早就已经应用于嵌入式【3 6 1 、服务器等领域，近年来开始应用于个 7 浙江大学硕士学位论文 第2 章相关背景及技术简介 人计算机领域。通常按照单个芯片上集成的多个处理器内核是否相同，可以将多 核处理器分为这两种： 同构多核处理器( h o m o g e n e o u sc m p ) 同一处理器芯片内部采用完全相同结构的处理器内核，多个处理器内核执行 相同或者类似的任务【3 7 】。目前个人计算机和服务器市场上的大多数多核处理器 都是同构多核处理器，英特尔的酷睿处理器架构如图2 - 4 所示： 图2 - 4 英特尔酷謇处理器架构 从图中可以看出，英特尔酷睿处理器集成了两个完全相同，对称的处理器内 核，两者拥有独立的执行单元、运算单元和一级c a c h e ，共享二级c a c h e 。 异构多核处理器( h e t e r o g e n e o u sc m p ) 同一处理器芯片内部采用了不同结构的处理器内核，异构c m p 除含有通用 处理器作为控制、通用计算之外，多集成d s p 、a s i c 、媒体处理器、v l i w 处理 器等针对特定的应用提高计算的性能 3 8 1 。 i b m 的c e l l 处理器架构如图2 5 所示，从图2 5 中可以看出，c e l l 处理器由 一个p o w e r 结构的处理器核心( p p e ，p o w e rp r o c e s s o re 1 e m e m ) 和8 个辅助处理 器( s p e ，s y n e r g i s t i cp r o c e s s o re l e m e n t ) 构成【3 9 1 。 8 浙江大学硕士学位论文 第2 章相关背景及技术简介 s p us p e 网r i i is x u l is x ul s x ui ls x u s x us x ul 瀚窨彝辅 青 芹 e i bl u pt o9 6b y t e s j c y c l e l lf1 6 b c v c t s b c y c l e ，t b 辩 广亩口蔗1 i 磊尉跏， 2 2 并行计算 图2 - 5 m m c e l l 处理器架构 2 2 1 背景介绍 并行计算( p a r a l l e lc o m p u t i n g ) 的定义：由运行在多个部件上的小任务合作 来求解一个规模很大的计算问题的一种方法【9 】。人类对计算及性能的要求是永无 止境的，从系统的角度来说，集成系统资源，能满足不断增长的对性能和功能的 要求；从应用的角度来说，适当分解应用，能实现更大规模或更细致的计算。并 行计算能降低单个问题求解的时间，增加问题求解规模，提高问题求解精度，在 多机同时执行多个串行程序时容错，具有更高的可用性，能够提高吞吐率【4 0 】。 并行计算在科学以及工程应用的计算模拟、商业应用的数据挖掘及事务处理 等许多领域，已经产生了巨大的作用和影响力。在工程设计领域，并行计算已成 功应用于机翼设计、内燃机设计、高速电路设计、结构设计、微电机系统设计等 方面；在科学计算领域，并行计算已成功应用于d n a 测序、生物序列分析、量 子计算、大分子结构、设计新材料、热核反应、天文数据、气象模型、矿物勘探、 天气预报等方面；在商业应用领域，并行计算已成功应用于服务器集群、数据库、 网络、数据挖掘、数据聚集、数据分类等方面；在计算机系统方面，并行计算已 成功应用于计算机安全、密码学、分布式控制等方面【8 】。并行计算在各种领域的 广泛应用如图2 - 6 所示： 9 浙江大学硕士学位论文 第2 章相关背景及技术简介 图2 - 6 并行计算在各种领域的广泛应用 并行化计算的成本优势与各种领域应用对计算性能上的需求相结合，为促进 并行计算的发展提供了坚实的基础。 2 2 2 系统结构 从不同的视角来看，并行计算可以由不同层次的粒度来表示。例如在一个运 行完整的操作系统中，可以将系统里运行的所有程序看成一个并行任务；而在一 个具体的运行中的程序内部，可以将程序里并发的所有线程看成一个并行任务； 再往细分，可以将程序中某行代码执行的具体指令也看成一个并行任务。比如下 面这两行代码： f o r t t = 0 ；i 4 ；i + + ) c i i l = 一 i i + b i l ： 这个例子里循环中的每次迭代彼此之间都相互独立，即c 【0 】= a 【0 】4 - b 【o 】， c 1 】= a 【1 】4 - b 【1 】等等，所以都可以独立执行，即并行执行在以往典型的指令 机制中没有引入并行执行指令，指令的执行形式如图2 - 7 所示： 图2 7 指令串行执行示意图 1 0 浙江大学硕士学位论文 第2 章相关背景及技术简介 而在支持指令并行执行的体系中，指令的执行形式如图2 8 所示： 图2 - 8 指令并行执行示意图 可见有一系列用来指定程序运行模式、控制结构的模型，以及支持这些模型 相应的体系结构。本文研究的并行计算是线程粒度的，即在一个程序的视图里， 研究多个线程之间的并行性。为了实现程序并行执行，硬件必须提供一个支持多 线程同时运行的平台。 一般说来，计算机的体系结构可以按照两个不同的方向归类。第一个方向是 单个时间点内计算机能够处理的指令流( i n s t r u c t i o ns t r e a m s ) 数量；第二个方向 是单个时间点内计算机能够处理的数据流( d a t as t r e a m s ) 数量。 数据流e = = = = 二= 二二二= 爿 图2 9 福林分类法 按照这种方式，任何计算机系统都可以按照它处理指令和数据的方式给予归 类。这种分类方法是m i c h e a l f l y n n 于1 9 7 2 年提出的，简称为福林分类法【4 1 】， 如图2 - 9 所示，将计算平台分为下面四种【2 8 】： 单指令单数据流( s i s d ) 传统的串行模式的计算机，不支持并行，指令都以串行模式执行，在同一时 刻只能执行一条指令( 即只有一个控制流) 、处理一个数据( 即只有一个数据流) 。 很多老式的计算机都属于这种类型，例如i b m 早期的个人计算机，大部分8 位家 用计算机等等。 1 1 习 au指令流 浙江大学硕士学位论文 第2 章相关背景及技术简介 多指令单数据流( m i s d ) 在这种计算机中，各个处理单元组成一个线性阵列，分别执行不同的指令流， 而同一个数据流则顺次通过这个阵列中的各个处理单元。这种系统结构只适用于 某些特定的算法，所以m i s d 更多的是作为一种理论模型来研究【4 2 】，实用价值 j 很小。 单指令多数据流( s i m d ) 曾经在很长一段时间内成为超级并行计算机主流的向量计算机除了标量处 理单元之外，最重要的是具有能进行向量计算的硬件单元。在执行向量操作时， 一条指令可以同时对多个数据( 组成一个向量) 进行运算。向量计算机因为这个 特点而称为s i m d 计算机，它在诸如信号、图像、音频和视频等应用领域非常有 效。如今，几乎所有的计算机都实现7s i m d 形式的指令集。比如英特尔推出的 m m x 、s s e 、s s e 2 以及s s e 3 指令集，都能在一个时钟周期内处理多个数据单元 ( 存储在浮点寄存器中) 。 多指令多数据流( m l m d ) 同时能执行多个指令流，分别对应于相互独立的数据流。m i m d 是现在最常 见的并行计算平台，最新的多核平台比如英特尔的酷睿处理器就属于m i m d 。 本文对并行计算的研究是基于多核平台，即支持s i m d 和m i m d 的平台，利 用它们对并行计算的支持，对程序进行并行优化而提高性能。在多核平台下，处 理器内核数量增多，每个内核都是一个简单的单线程处理器，这样在并行计算的 线程级粒度视角，刚好可以将多个线程按照一定的策略分配到多核处理器上。 如何评价多核平台里单线程程序转化为多线程程序后的性能提升( 即加速比) 的上限，1 9 6 7 年g e n e a m d a h l 提出了著名的阿姆达尔定律h 3 1 ，用来计算并行程 序理论上相对于最优串行算法性能能提升的最大值。阿姆达尔定律将原始的串行 程序分为为可并行与不可并行两部分，程序加速比和两部分有关，一是原始串行 程序中可并行部分占有的比例，二是该可并行部分的并行程度。若用s p e e d u p 代 表加速比，s 代表程序中的不可并行部分所占比例，1 1 代表处理器内核数量( 理 想状态下内核数量和可并行部分的执行时间成反比) ，那么阿姆达尔定律可以用 公式2 1 表示为： 1、 s p e e d u p 2 s + ( 1 - s ) a 【己l j 例如一个程序中可并行比例为5 0 ，将它在一台双核计算机上并行运行时， 理想的加速比为1 m 5 + 0 5 2 ) = 1 3 3 。本文后面的实验结果，即实际并行优化的加 速比，将和用阿姆达尔定律计算出来的理想加速比进行对比，验证优化效果。 浙江大学硕十学位论文第2 章相关背景及技术简介 2 2 3 编程技术 众所周知，在计算机产业，硬件和软件的发展一向是相辅相成、互相促进1 4 4 j 。 多核这场硬件的革命自然也带动了软件的革命，在单核年代，程序员几乎很少考 虑并行编程的问题，因为就算是多线程的程序，在单核平台上也只能并发执行， 不能并行执行，单线程程序和多线程程序在性能上几乎没有任何区别，相反，由 于线程切换带来的开销，多线程程序的性能往往还不如单线程程序。而在多核平 台上，两者性能的差异非常明显，只要设计得当，多线程程序的性能将大大超越 单线程程序。因此，程序员必须从以前的串行思维中解放出来，投入到并行设计 中去。 在并行程序设计中，按照并行层次的不同 4 0 1 ，可以分为以下四种： 1 指令层，非常细的粒度 2 数据层，细粒度 3 控制层，中粒度 4 任务层，大粒度 前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行，在本 文的设计中即线程级的并行。按照并行程序的设计方法 4 0 1 ，又可以分为以下两 种： 1 隐式并行程序设计 在这种情况下，程序员不需要学习并行编程的知识，而只需要用传统的的串 行编程方式即可，编译器、运行时库和操作系统会自动将代码编译为可并行执行 的指令。这种方法的好处是方便程序员，避免并行编程带来的麻烦；源代码仍然 是单线程程序，方便调试、验证和移植；自动优化的部分由第三方底层实现，不 容易出错。但是这种方法的弊端也是显而易见的，编译器能识别的可并行程度很 低，例如只能对一些较为简单的、特定形式的循环做并行优化；细粒度并行，效 率非常低，性能提升很小。 2 显式并行程序设计 这种情况即程序员完全摒弃传统的单线程设计模式，而采用多线程的并行设 计。这种方法对程序员的要求很高，而且写好的程序调试起来也非常有难度，出 错了很不容易发现。但它的好处也是显而易见的，完全的人工并行设计水平比依 赖编译器“人工智能”的水平要高得多，是粗粒度并行，程序如何并发运行可以 完全掌握，大大提高效率，是性能提高的关键手段。 线程作为程序流程中的单一控制流，在并行设计中是并发的基本单元。接下 浙江大学硕士学位论文第2 章相关背景及技术简介 来简单介绍常用的多线程编程技术：w i n 3 2 线程库和o p e n m p 。 1 1w i n 3 2 线程库 w i n 3 2 a p i 为开发人员提供了一个w i n d o w s 应用程序开发的c c + + 接口，利 用w i n 3 2 的多线程a p i 函数可以轻松创建、控制、终结线程，线程之间可以使用 事件来进行通信 1 6 1 。线程同步