（计算机应用技术专业论文）基于多核的多线程算法并行优化.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者力毳隽 日期：h 觯f 月日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者冀秀考 日期：加阳年厂月“曰 摘要 摘要 在多核处理器不断普及的今天，并行软件开发技术的加速发展已成为关键。 多核处理器既促进了并行软件开发技术的发展，也依赖于并行软件开发技术。 但是软件并行化的发展需要克服重重困难。当今在使用的很大部分软件还是串 行思想开发的产物，我们需要从根本软件开发理念上改变，进行软件并行化。 目前已经出现了多种并行编程模型，主要有共享存储编程模型、消息传递模型 和分布式存储模型。多线程并行编程就基于共享存储的编程模型。 矩阵相乘算法的重要性不言而喻，在很多科学计算和工程方面应用极广。 因此，对矩阵相乘算法做了实验，分别采用了w i n 3 2 多线程a p i 、o p e n m p 及c # 多线程对其进行实现。在此过程中，归结了这几种多线程编程方法的特性和优 缺点。w i n 3 2 多线程a p i 具有性能优，可以显性操作线程的优点，但是实现相 对复杂，对软件开发人员要求高。o p e n m p 实现简单，适合于优化循环。但是性 能相对w i n 3 2 多线程a p i 稍微逊色。而c # 在语言级提供了对多线程的支持，但 是由于其基于虚拟机的机制导致其性能还不如前两者，实现难度介于两者之间， 也可显性操作线程。本实验结果有助于在开发时对编程方法的选择。 排序算法是常用而且对其本身性能要求很高的算法。在前面实验研究的基 础上，提出了一种排序组合算法，并且对后半部分的归并排序进行了改进。改 进的方法采用了多线程的思想，将原来单线程执行的归并过程进化成可以同时 执行的两个线程。两个线程分别从已经有序的两个序列的最大值端和最小值端 同时进行比较，将相应的结果放在新序列的相应端。两个线程都工作至新序列 的中间为止，也达到了负载平衡的目的。该算法的实验采用前面实验分析结果 中性能最优的w i n 3 2a p i 多线程编程方法进行实现。实验结果对比表明并行改 进后的算法性能提升显著，并且随着数据规模的扩大，提升比例稳定升高。 关键词：多线程，多核，归并排序，并行优化，排序算法，矩阵相乘 a b s t r a c t a b s t r a c t n o w a d a y s ，a s t h eg r o w i n gp o p u l a r i t yo fm u l t i - c o r e p r o c e s s o r s ，t h e d e v e l o p m e n to fp a r a l l e ls o f t w a r et e c h n o l o g yh a sb e c o m et h ec r u x t h em u l t i c o r e t e c h n o l o g yc a na c c e l e r a t et h ed e v e l o p m e n t o fp a r a l l e ls o f t w a r et e c h n o l o g y ，a n da l s o d e p e n do ni t a tt h ep r e s e n tt i m e ，m o s to ft h es o f t w a r eo ra p p l i c a t i o n si nu s e w e r e d e v e l o p e di ns e r i a li d e a s ，s ot h ed e v e l o p m e n to fp a r a l l e ls o f t w a r et e c h n o l o g ym u s t o v e r c o m em u c hd i f f i c u l t y w en e e daf u n d a m e n t a lc h a n g ef r o mt h et r a d i t i o n a ls e r i a l p r o g r a m m i n gi d e a s t o p a r a l l e li d e a s t h e r e a r ev a r i o u sp a r a l l e lp r o g r a m m i n g m o d e l s ，p a r a l l e lp r o g r a m m i n gm o d e l sb a s e do ns h a r e dm e m o r y ，m o d e l sb a s e do n m e s s a g et r a n s m i t t i n ga n dm o d e l sb a s e do nd i s t r i b u t e dm e m o r y t h e m u l t i - t h r e a d e d p a r a l l e lp r o g r a m m i n gi so n e k i n do fs h a r e dm e m o r yp a r a l l e lp r o g r a m m i n gm o d e l i tg o e sw i t h o u ts a y i n gt h ei m p o r t a n c eo fm a t r i xm u l t i p l i c a t i o na l g o r i t h m ；i ti s w i d e s p r e a di nm a n ys c i e n t i f i cc o m p u t i n g a n de n g i n e e r i n ga p p l i c a t i o n s s o ，t h e r ei s ae x p e r i m e n to fm a t r i xm u l t i p l i c a t i o na l g o r i t h m ，i m p l e m e n t e db yw i n 3 2 m u r i t h r e a d e da p i ，o p e n m pa n dc 撑i tt u r n so u tt h a te a c hm e t h o dh a si t s a d v a n t a g e sa n dd i s a d v a n t a g e s u s i n gw i n 3 2m u l t i t h r e a d e da p i ， i th a sag o o d p e r f o r m a n c e ，a n dt h et h r e a d sc a nb eo p e r a t e de x p l i c i t l y ，b u t i ti sh a r d e rt o i m p l e m e n ta st oo t h e r s u s i n go p e n m p ，i ti se a s yt oi m p l e m e n t ，b u tt h ep e r f o r m a n c e i sw o r s et h a nt h a tw h e nu s i n gw i n 3 2m u l t i - t h r e a d e da p i a l t h o u g hc 舞s u p p o r t i n g m u l t i - t h r e a dp r o g r a m m i n gi nl a n g u a g el e v e l ，i ti m p l e m e n t a t i o ni sb a s e do nv i r t u a l m a c h i n e ，s ou s i n gc 撑，i t sp e r f o r m a n c ei st h ew o r s t ，t h ep e r f o r m a n c ei sb e t w e e nt h e f o r m e rt w o t h ee x p e r i m e n tr e s u l ti sh e l p f u lw h e nd o i n gt h ec h o i c eo fd i f f e r e n t m u l t i - t h r e a d e dd e v e l o p i n gm e t h o d s s o r t i n ga l g o r i t h m i s c o m m o n l y u s e da n dh a sa g r e a t d e m a n do f p e r f o r m a n c e o nt h eb a s i so ft h ep r e v i o u se x p e r i m e n t s ，an e w c o m b i n a t i o nm e t h o d o fs o r t i n ga l g o r i t h m sw a ss u p p o s e d ，a n da no p t i m i z a t i o nw a sm a d et ot h em e r g e a l g o r i t h mu s i n gm u l t i t h r e a di d e a s t h eo p t i m i z e dm e r g es o r t i n ga l g o r i t h mc a n m a k et w ot h r e a dw o r ka tt h es a m et i m e ，o n eo fw h i c hw o r kf r o mt h em a x i m a lv a l u e i i a b s t r a c t s i d eo ft h et w od a t as e q u e n c ea n dw r i t et h eb i g g e rv a l u et oan e wd a t as e q u e n c e f r o mt h em a xs i d e ，a n dt h eo t h e ro n ew o r kf r o mt h em i n i m a lv a l u es i d ea n dw r i t et h e l e s sv a l u et ot h en e wd a t as e q u e n c ef r o mt h em i n i m a ls i d e b o t ho ft h e mw o r ku n t i l t h e yw r i t et ot h em i d p o i n to ft h en e wd a t as e q u e n c et ok e e pt h eb a l a n c eo fe a c h t h r e a d sw o r k l o a d 1 n h en e wa l g o r i t h mw a si m p l e m e n t e db yw i n 3 2m u l t i t h r e a d e d a p i ，w h i c hi st h em o s te f f i c i e n tm e t h o da c c o r d i n gt ot h er e s u l to ft h ef o r m e r e x p e r i m e n t n er e s u l to ft h ee x p e r i m e n ts h o w st h en e wa l g o r i t h mh a sam u c hb e t t e r p e r f o r m a n c e k e yw o r d s ：m u l t i - t h r e a d e d ，m u l t i c o r e ，m e r g es o r ta l g o r i t h m ，p a r a l l e lo p t i m i z e ， s o r t i n ga l g o r i t h m ，m a t r i xm u l t i p l i c a t i o n i i i 目录 目录 1 弓l 言1 1 1 研究背景1 1 2 研究内容3 1 3 研究内容的安排3 2 多核与多线程技术4 2 1 多核技术4 2 1 1 多核体系结构4 2 1 2 多核现状及前景5 2 2 多核对软件业的影响7 2 3 多线程技术8 2 4 基于多核的多线程1 0 3 多线程编程方法。1 2 3 1w i n d o w s 多线程库1 2 3 1 1w i n 3 2a p i 多线程1 2 3 1 2m f c 多线程1 7 3 1 3w m 3 2a p i 与m f c 比较2 0 3 2 p t h r e a da p i 多线程库2 0 3 2 1u n i x 模型中的线程2 0 3 2 2 p t h r e a d 多线程a p i 。2 1 3 3 o p e n m p 2 2 3 3 1 编译指导语句。2 3 3 3 2 运行函数库与环境变量2 4 3 4c 撑多线程机制2 5 3 5 本章小结2 6 4 算法实验2 7 4 1 矩阵相乘算法实现矩阵相乘算法实现2 7 4 1 1 使用w i n 3 2 a p i 实现矩阵相乘算法2 7 i v 目录 4 1 2 使用o p e n m p 实现矩阵相乘算法2 8 4 1 3 使用c 挣多线程实现矩阵相乘算法2 8 4 2 排序算法2 9 4 2 1 传统的主要排序算法2 9 4 2 2 基于多核的并行排序算法设计3 0 4 2 3 基于多线程的归并算法的改进。3 1 4 3 本章小结3 2 5 实验结果分析。3 4 5 1 矩阵相乘实验及效率分析。3 4 5 2 排序算法优化实验内容及结果分析3 7 5 2 1 实验平台及内容3 7 5 2 2 实验结果性能分析3 8 5 2 3 时间复杂度分析4 0 5 3 本章小结4 0 6 总结与展望4 1 6 1 全文总结4 1 6 2 后续工作展望4 1 参考文献4 3 个人简历4 9 在学期间发表的学术论文与研究成果5 0 致谢5 1 v 引言 1 引言 1 1 研究背景 在过去的数十年中，大规模集成电路制成工艺得到了飞速发展，单个硅芯 片上可以集成的晶体管数量也在快速增长，如何有效利用这些不断增长的、数 以亿计的晶体管资源，推动微处理器芯片性能的持续提升已成为信息工业界与 学术界高度关注的关键问题之一。 1 9 9 6 年，斯坦福大学研制出了世界是第一款多核处理器( c h i pm u l t i p r o c e s s o r ，c m p ) 的原型系统h y d r a 。此后，多核处理器的相关研究与商业应 用开始蓬勃发展。短短十几年时间，双核处理器芯片已成为通用微处理器市场 上的主流产品。近年，四核处理器芯片也已上市。工业界与学术界继续探讨含 有更多微处理器内核的单芯片系统。微处理器丌始迈入多核时代。 进入多核时代，计算机系统的软件和硬件功能分配以及各自的作用和特性 都发生了质的变化。现代的计算机系统已经从传统的透明性层次结构抽象、先 硬件后软件的设计流程转变为软件和硬件协同的设计方法。与之相对应的编程 语言、库、编译方法和操作系统等基本概念也被赋予了新的含义。我们正面临 着计算机系统结构的一次变革，这场变革将给我们带来了巨大的挑战，同时也 给我们带来了新的发展机遇。 历史上出现的并行计算机，从系统的角度主要有分布式存储器的s i m d 处 理机、向量超级计算机( 共享式存储器s i m d ) 、对称多处理器( s m p ) 、并行 向量处理机( p v p ) 及集群计算机【。都是属于大型处理器设备，所以目前针 对并行处理的产品设计也还主要集中在服务器和高性能网络设备上。关于多核 多线程产品设计并没有太多的经验可以借鉴，如何发挥出多核多线程处理器的 巨大潜能还需要积极探索。在多核多线程处理器环境下，软件系统的设计需要 开发者了解底层硬件的特点，根据具体的应用环境进行软件系统的设计，这无 疑给开发者带来了挑战。 研究开发新型编程模型的工作成为了极其重要的事情。在目前情况下，多 核应用开发工具和平台的研发尤为迫切，主要包括：智能的优化编译器、程序 调试工具、性能检测和协调工具、并行编程环境以及能耗调度等等【1 】【2 1 。但从 目前来看，一些桌面应用尚不支持多线程，编程模型的限制和应用开发工具的 计算模型、系统软件、新型的通信技术、应用开发平台技术以及和谐的人机交 互模式等关键技术具有重要意义。 并行编程模型一直是并行计算研究领域中的重点内容，它和并行计算机体 系结构紧密相关。共享存储体系结构下的并行编程模型主要是共享存储编程模 型，它具有单地址空间、编程容易、可移植性差等特点，其实现有o p e n m p 和 p t h r e a d 等。分布式存储体系结构下的并行编程模型主要有消息传递编程模型和 分布式共享编程模型两种：消息传递编程模型的特点是多地址空间、编程困难、 可移植性好，其实现有m p i 等；分布式共享编程模型是指有硬件或软件的支持， 在分布式体系结构下实现的具有共享变量编程模型特点的编程模型。后者可以 分别按照硬件或软件的实现分为d s m 和s v m ，目前研究热点的分割全局地址 空间( p g a s ) 模型的研究有u p c 等代表，具有很强的发展潜力1 3 j 。 多线程并行程编程模型属于共享存储模型。多线程编程模型具有实现进程 并行计算、节省内存空间、减少系统管理丌销、( 线程) 通信易于实现等优点1 2 j 。 更重要的是多线程编程模型提供了一种新型的模块化编程思想和方法，这种方 法能清晰地表达各种独立事件的相互关系，但是这种多线程编程模型的并发和 异步优点也带来了一定的复杂度：并发和异步机制带来了线程间的资源竞争无 序性。因此需要引入同步机制来消除这种复杂度和实现线程间共享数据，以一 致的顺序执行一组操作。由上可见，如何使用同步机制来消除线程并发、并行 和异步执行而带来的复杂度是多线程编程中最重要的问题，也是多线程编程模 型研究的核心问题。 总之，为了充分利用多核，程序需要同时做很多事情。这种行为通常被称 为并行计算。并行程序如果编译正确，执行指令的速度将比传统的串行程序要 快很多，因为它能将工作负载按照不同需求分配给处理器的不同核心。而传统 的串行程序只能利用一个核心。 多核技术和并行计算的结合必将成为未来通用微处理器的发展方向。它将 会人们带来了巨大的性能提升空间，同时也给软件开发人员带来了巨大的挑战。 尽管多核是一种硬件技术，但硬件和软件是相互依存的，硬件只是一种物质基 础，只有有了软件的支持，才能使硬件拥有用武之地。多核处理器的革命给整 个计算机领域带来了前所未有的挑战和机遇。一方面，多核意味着在同样的空 间内实现更多的计算功效。另一方面，处理器体系架构的根本性变化要想充分 2 引言 利用这些处理器，比起之前的设计就更具挑战性。面临的挑战之一就是软件， 概述如下：多核平台急需软件支撑。多核处理器可以让多条运算指令同时运行， 这对软件提出了更高的要求。现有的软件如果不做改变，就无法利用目前不断 进步的处理器所提供的多核性能。 1 2 研究内容 本文介绍分析了几种典型的多线程编程实现方法：w i n d o w s 多线程库、 p t h r c a da p i 多线程库、o p c n m p 及支持多线程的编程语言。在此基础上分别研 究了排序算法、矩阵相乘和f f f 算法的特点，提出了各自的并行划分和实现方 法。同时也提出了归并排序基于多线程的改进方法，以及各排序算法的组合方 法。 最后，分别采用以上几种多线程编程方法实现了这些算法。实验结果表明 改进后的并行算法比传统算法效率有很大提升。 1 3 研究内容的安排 本文共分为六章，下面对这六章内容做简要的介绍： 第一章：本章介绍了多核处理器和并行编程模型以及各个算法的研究背景 及意义，并介绍了本文研究的内容以及论文内容的安排。 第二章：本章介绍多核和多线程技术，以及基于多核的多线程技术，并说 明了基于多核的几种多线程划分方法。 第三章：本章介绍了具体介绍了w i n d o w s 多线程库、p t h r c a d 多线程库、 o p e n m p 及支持多线程的编程语言这几种多线程编程方法。并分析了它们各自 的优缺点。 第四章：本章介绍了分析了排序算法、矩阵相乘和h 丌算法的特点，并采 用了以上几种并行编程方法设计各个算法。 第五章：并对实验结果进行了分析，评估了性能，也得出了结论。 第六章：本章对所做工作进行了分析，并对后续的工作进行展望。 多核与多线程技术 2 多核与多线程技术 2 1 多核技术 2 1 1多核体系结构 虽然不同厂商所采用的多核技术各不相同，但所谓多核技术就是将两或多 个计算核心集成在一个处理器上。多核处理器就是使用多核技术的单枚芯片( 也 称为“硅核 ) ，能够直接插入到一个处理器插槽中，但操作系统会利用所有相 关的资源，将它的每个执行内核作为独立的逻辑处理单元。通过在两个或多个 执行内核之间分摊任务，多核处理器可在特定的时钟周期内执行更多任务。根 据设计的不同，这些计算内核可能共享也可能不共享片上的c a c h e i 引。例如，图 2 1 是i n t e l 和a m d 的双核c p u 结构图。 e x e c u t i o ne x e c u t i o n c o r ec o r n 2 m bl 22 l 衄l 2 c a c h ec a c h e b u si fb u si i f tt 1 l r m c hf s b c p u0c p ul l 2c a c h el 2c a c h e f o rc p u0f o rc p u1 s y s t e mr e q u e s th l t 盯矗c e c r o s s b a rs 谢t c h 】i m e m o r yh y p e r t r a n s p o r t c o n t r o l l e rt e c l m o l og y a n ) a t h l o n t m6 4 木2 d u a l - c o r ep r o c e s s o rd e s i g n 图2 1i n t e l 和a m d 的双核c p u 结构图 由于不满足单核现状，a m d 率先在x 8 6 领域推出了双核处理器，英特尔 紧接着后来居上，跟着就发布了四核处理器，掀开了多核大战序幕。可以说近 几年来从单核到双核、从双核再到四核以及六核、八核等，显然表明多核之战， 4 多核与多线程技术 已成为处理器市场最炙手可热的焦点。多核在应用中，在传统的科学计算和服 务器软件方面，由于原有的软件的是并行的。多核提供了一种高性能平台，所 需做的只是针对多核的优化，困难并不大。但是在桌面软件方面，原有软件大 部分是串行的，需要采用很好的并行编程模型和开发环境，才能充分利用多核 的性能。多核的进一步普及取决于软件并行化的发展。 多核技术能够使处理器并行处理任务，多核系统可扩展性很好，并且它能 够在纤巧的外形中融入更加强大的处理能力，这种外形所用的功耗比较低、计 算功耗产生的热量也比较少。多核架构可以使目前的软件更加出色地运行，并 创建了一个能够促进未来的软件编写更趋于完善的架构。多核处理器的优点可 以详细罗列如下： 1 、控制逻辑简单。相对超标量及超长指令字微处理器结构而言，多核处理 器结构的控制逻辑要明显简单很多。相应的多核处理器的硬件实现必然要简单 得多。 2 、低通信延迟。由于多个处理器核心集成在一块芯片上，并且采用共享 c a c h e 或者内存的方式，多个线程间的通信延迟会降低很多，但是这样也对存 储系统提出了更高的要求。 3 、高主频，低功耗。由于单芯片多核处理器的控制逻辑相对简单，包含很 少的全局信号，因此线延迟也相应比较小。所以，在同样的工艺条件下，多核 处理器的硬件实现能够获得比超标量和超长指令字微处理器更高的工作频率。 通过动态调节电压频率和负载优化分布等，可有效降低c m p 功耗1 4 j 。 目前的操作系统充分考虑了多个处理器，为充分利用多个处理器而设计， 且无需修改即可正常在不同的多核处理器上运行。为了充分利用多核处理器， 软件开发人员需要在程序设计过程中融入更多思路，但设计流程和目前对称多 处理系统( s m p ) 的设计流程基本相同，并且现有的单线程应用软件也可以继续 运行。由于多线程技术的应用在多核处理器上显示出了卓越的性能可扩展性， 此类应用软件包括多媒体应用( 例如内容创建和编辑，以及本地和数据流回放) 、 工程和其它技术计算应用以及应用服务器和数据库等中间层与后层服务器应 用。 2 1 2多核现状及前景 伴随着操作系统以及应用软件对多核处理器进一步的支持和优化、芯片制 多核j 多线程技术 造工艺的发展、a m d 和i n t e l 为代表的低功耗处理器技术的进步、芯片级虚拟 化技术的成熟等等因素，这些都将推动服务器处理器多核化趋势的进一步普及。 多核技术即将成为服务器技术的重要的核心技术。目前在服务器处理器市场上， 主要包括i n t e l 和安腾、a m d 的4 核o p t e r o n 、i b m 的c e l l b e ) 芯片、和n e g a r a 八核t 1 芯片、s u n 的u l t r as p a r c 和p o w e r 5 多核、h p 的p a - r i s c 多核等。 这使得整个市场充斥着各种多核处理器的气息。此外，国内的龙芯3 也是专门 面向服务器系统领域的c p u ，目前也在进行多核处理器的研发，国内厂商曙光 在其新品中搭载龙芯多核处理器。 不断提高的应用需求是计算机处理器发展的根本动力。例如，在目前的服 务器应用方面，要求高的吞吐率以及在多处理器上的多线程应用，i n t e r a c t 方面 的应用、p 2 p 和普适计算的应用都促使了计算机性能的不断提升，多核技术已 经成为了服务器技术的重要技术支点。政府的大型数据库管理系统、科学计算、 大型企业的e r p 、c r m 等复杂应用，数字医疗领域、电信、金融等都需要高 性能计算，多核技术可以一定程度上满足这些应用的需求。 继发布3 3 款服务器领域的处理器后，i n t e l 发布了功耗仅有5 0 w 的低功耗 x e o n 处理器，以及后来用于嵌入式平台的四核x e o n 处理器。x e o n 系列处理器 不仅在服务器处理器领域有所建树，同时也为通信、医疗、科研等领域的嵌入 式设备发展带来了强劲的数据处理能力。 英特尔多核嵌入式处理器是面向范围广泛的嵌入式应用的，提供了卓越的 性能和可扩充性，实现了低能耗、高效能的优势。这些全新处理器以其较低的 功耗和较高的效能为嵌入式市场带来了极为卓越的性能。同时，相应的芯片技 术还采用了改进的集成显卡组件。开发商将会发现，这些嵌入式处理器和相关 芯片组，堪称是小外形设计的最佳选择。例如，全新c o m ( c o m p u t e r - o n m o d u l e ) e x p r e s s 外形规范可为嵌入式应用带来出色的性能和i o 密度等1 3 j 。 a m d 嵌入式处理器使用了a m d 6 4 长效保修计划，保证了至少五年的处理 器供应时间，并且增加了两款以a m d 畅销行动产品为基础的低功耗处理器。 分别为m o b i l ea m ds e m p r o n3 5 0 0 + 处理器，和a m dt u r i o n 6 4x 2t l - 5 2 双核心 行动计算技术。此两款处理器的发表为设计工程师提供了在系统开发上新的选 择，并且为顾客带来了最佳的性能与较低的持有成本。 a m da t h l o n 6 4 及a m da t h l o n 6 4x 2 双核处理器是a m d 推出的高性能6 4 位器件，他是面向高端嵌入式领域的，具有出色的计算能力、i 0 通信、存储 6 多核与多线程技术 及扩展性能。与此同时，a m d 宣布了将会新增三款低功耗a m d a t h l o n 6 4 处理 器。新款处理器只有8 瓦的散热规格，能令嵌入式系统研发人员使用它在这样 的功耗下发挥a m d 6 4 技术所具备的各项优势。 随着应用需求的不断扩大和多核技术的不断进步，多核处理器必将展示出 其强大的性能优势。多核处理器是处理器发展的必然发展趋势，涉及到各个方 面的应用，如移动与嵌入式应用、桌面应用还是服务器应用，都将会采用多核 处理器的架构，因此，多核技术应用前景广阔。 2 2 多核对软件业的影响 多核技术是一种硬件技术，但硬件技术和软件技术是相互依存的，硬件是 一种物质基础，只有有了软件的支持，才能使硬件拥有用武之地。多核处理器 革命给整个计算机领域带来了前所未有的挑战和机遇。一方面，多核意味着在 同样的空间内实现更多的计算能力。另一方面，处理器体系架构的根本性变化 使得我们要想充分利用这些处理器，比起之前的设计就更具挑战性。面临的挑 战之一就是软件，多核平台急需软件支撑1 4 】。多核处理器可以让多条运算指令 同时在不同的处理器核上运行，这对软件开发提出了更高的要求。现有的软件 如果不做相应改变，就无法充分发挥目前不断进步的处理器技术所提供的多核 性能。 在今天多核处理器已占据了越来越多的市场份额，作为软件开发人员，必 须直面多核革命带来的冲击。多核编程，既是机遇也是挑战，如何在这个行业 大变革中把握方向、与时俱进，成为摆在我们面前的迫切课题。因为从单核到 多核并不像处理器时钟频率的提升那样对程序员而言是透明的，如果我们的编 写的程序没有针对多核的特点来设计，那就不能完全获得多核带来的性能提升。 为了紧跟多核处理器发展的步伐，在软件开发方面已出现了相应的方法， 首先目前最常用的就是公开标准a p i ( 应用编程接口) ，从过往软件开发经验看 a p i 已经在并行程序设计方面取得了成功，具有较好的使用性和方便性来向程 序设计者提供支持。采用a p i 的并行软件开发方法在灵活性和将来的升级支持 方面都是风险度较低的选择。但是，对于个别特定问题处理方面却并不是最佳 的编程方式。 于此同时，还有一类新的编程方法，专门针对并行多核处理器的并行性， 7 多核与多线程技术 在将来也颇具潜力，通常称其为新生力量。此类方法由三种组成：t h r e a d s ( 多 线程技术) ，o p e n m p 和m p i 。t h r e a d s ( 多线程技术) 使用的是均衡共用存储器或 者共享存储，在传统多核处理器系统中已经有多年的使用历史。虽然他们在实 现并行程序方面更为出色，但作为一项新兴的技术要进行推广还有一定风险。 总之，为了充分利用多核，程序需要同时做很多事情。并行程序如果编译 正确，执行指令的速度将比传统的串行程序要快很多，因为它能将工作负载按 照不同需求分配给处理器的不同核心。而传统的串行程序只能利用一个核心。 2 3 多线程技术 线程( t h r e a d ) 是在操作系统调度过程中比进程( p r o c e s s ) 更小的可调度执 行单元。传统的进程只包含一个执行序列，从头到尾都是一个顺序执行的逻辑 路径，所以也可以称为是单线程的。在应用程序中使用多线程技术，每个线程 都执行一个独立的逻辑路径，可以将冗长的或非常耗时的任务分解开来，某些 部分可以放在后台处理。即使在只有单处理器的计算机上，使用多线程也可以 非常显著的提高应用程序的效率和可用性。 为了适应多处理器环境下日益增长的细粒度并行运算的需要，现代操作系 统提供了线程支持。线程有三个层次的表现形式： 1 、用户级线程在软件开发过程中有软件开发人员所创建和操纵的线程。 2 、内核级线程是有操作系统来实现用户级线程的方式。 3 、硬件线程是指在硬件执行资源上的线程。 单个程序线程一般都包括上述三个层次的表现：程序线程被操作系统作为 内核线程实现，进而作为硬件线程来执行 2 1 。图2 2 是直观的线程层次模型。 l用户级线程 l 由可执行应用程序使用，同时由用户级操作系统处理 l 土 l 揪蒯核盎篇黧黜理 i由景燃用 8 多核与多线程技术 图2 2 线程计算模型 目前的操作系统大都支持线程机制，以便节约使用资源来获得更好的性能。 在支持多线程的系统中，进程是资源分配和保护的实体，而线程则是被调度执 行的基本单元。进程所拥有的资源包括进程的内存地址空间，打开的文件及i o 等资源。属于同一个进程的多个线程共享该进程的代码段和数据段，打开的文 件和信号等。除了共享进程资源，每个线程程还包括各自的线程，线程执行 状态，c p u 寄存器状态和榭1 0 j 。 线程间是相互独立而又相互依赖的。使用多线程编程模型编程就是将进程 的任务划分为执行的线程，每一个线程为一个顺序的单控制流，而所有线程都 是并发、并行并且是异步执行的。多线程机制的优点包括以下几个方面。 首先，线程创建代价小。创建一个线程的代价要远远小于创建一个进程。 由于线程共享进程的资源，所以创建线程时不需要再为其分配内存空间等资源， 所需的创建时间也更少。在s o l a r i s 2 操作系统上，创建进程的时间大约是线程 的3 0 倍。 其次，线程之间的切换比进程之间的切换代价小。线程作为基本执行单元， 当从同一个进程的某一个线程切换到另一个线程时，需要载入的信息比进程之 间切换时要少，所以切换速度要快，s o l a r i s 2 操作系统中线程的切换比进程切 换快大约5 倍。 第三，多线程可以充分利用多处理器。同一进程的多个线程可以在多个处 理器上并行运行，该进程的运行速度可以得到显著提高，而单线程却只能在一 个处理器上运行，不能充分地利用多个处理器。 第四，数据共享。对于同一进程的线程来说，它们共享同一块地址空间， 可以访问相同的数据。数据共享使得线程之间的通信比进程之间的通信比进程 问的通信更高效，更容易。 最后，响应速度快。对于交互程序来说，可充分利用多线程的特性，当执 行一些耗时或者可能被阻塞的任务时，可使用特定的线程完成，其他部分仍然 保持运行和响应。比如当多线程浏览器的一个线程正在载入图片时，用户仍然 能够通过界面线程同浏览器进行交互并得到即时响应。 同时，多线程编程模型的并发和异步优点也带来了一定的复杂度：并发和 异步机制带来了线程间资源竞争无序性【8 】。因此需要引入同步机制来消除这种 9 多核与多线程技术 复杂度和实现线程间共享数据，以一致的顺序执行一组操作。如何使用同步机 制来消除线程并发、并行和异步执行而带来的复杂度是多线程编程中最重要的 问题，也是多线程编程模型研究的核心问题。 2 4 基于多核的多线程 在多核或多c p u 计算机系统中，并行处理能力所能达到的加速比并不能随 着c p u ( 或计算核心) 的数量的增加而无限的增加i 引。根据阿姆尔达定律，如果 设程序中串行部分( 即不可并行化的部分) 所占比例为f ，c p u ( 或计算核心) 的数 量为p ，则并行处理时的阿姆达尔定律可表示为如下公式： s ( p ) = p ( 1 + ( p - 1 ) f ) 也就是说，如果程序中的串行化部分占5 ，那么当c p u ( 或核) 的数量从 2 0 个增加到1 0 0 个时，加速系数只能从1 0 2 5 6 增加到1 6 8 左右。换句话说增 加了4 倍的处理器而速度只增加了约6 4 。实际上，在上述情况下，加速系数 的极限值只有2 0 。 同时，要很好地发挥出多核的性能，必须保证分配到各个计算核心上的任 务有一个很好的负载均衡。否则一些计算核心在运行，而另一些计算核心却处 于空闲，而实际的计算效率是以任务较重的计算核心为准，从而可能造成性能 的瓶颈，无法发挥出多核处理器的优势。 要实现一个高效的负载均衡通常有两种方法【9 l ，一种是静态负载平衡，采 用人工干预的方法预先将整个任务分割成多个可并行执行的部分，尽量保证分 割的各个部分可以独立均衡地运行在不同的处理器核上；另外一种方法是动态 负载平衡，在程序的运行过程中进行任务的分配达到负载平衡的目的。事实上， 即便分割后的工作量仍存在差别，但随着处理器核数的增加，总能让执行时间 缩短，从而增加加速系数。负载平衡的主要难点在于需要由软件开发人员来对 执行块进行手动划分，在处理器核比较少的时候，这种划分难度并不大，但随 着处理器核数的增加其划分粒度也越来越小。另外，如果在划分中使用了锁等 同步机制，一些看起来是均衡的负载也可能会由于竞争变得不均衡。 所以，基于多核的多线程程序设计的关键就是挖掘应用程序的并行性，将 一个程序尽量平均地分解成多个可以同时执行的部分，然后由不同的线程在不 同的内核上执行。将应用程序划分成多个独立的任务，并确定这些任务之间的 1 0 多核与多线程技术 相互依赖关系的过程就成为分解( d e c o m p o s i t i o n ) 【2 1 。分解的方法有三种：任 务分解、数据分解和数据流分解。分解的目的是使得各个处理器都能分配到平 衡的工作负载，从而提高运算的并行性。 表2 1 三种分解方法 说明 任务分解不同的程序行为采用不同的线程实现，常用于g u i 应刚程序 数据分解多个线程对不同的数据块执行相同的操作，常用于音频图像处理和科学计算应用 数据流分解一个线程的输出作为另一个线程的输入，尤其注意尽量消除启动和排空延迟 任务分解是一种能够简单实现并行执行的方法。能够对多个独立任务进行 分类。数据分解也称为数据级并行，可采用多线程对不同的数据对象执行相同 的操作。数据流分解根据任务间的数据流动来分解任务的。可根据不同的应用 特点采用不同的分解方法。 总之，多核时代的到来，给我们的编程思维带来了巨大的冲击。为了能够 充分地利用多核性能，我们必须学会以分块的思维设计程序、以多进程或多线 程的形式来进行软件开发和优化。 多线程编程方法 3 多线程编程方法 3 1w i n d o w s 多线程库 w i n d o w s 是支持多任务的操作系统。在w i n d o w s 操作系统下，一个进程 包含一个或多个线程。3 2 位w i n d o w s 环境下的w i n 3 2 a p i 将内核提供的功能 进行函数封装，应用程序通过调用相关的函数来实现多线程。另外，m f c ( m i c r o s o f tf o u n d a t i o nc l a s s e s ) 以类库的方式将w i n 3 2 进行封装，以类的方式 供应用程序使用。由于m f c 是在w i n 3 2a p i 基础之上进行封装的，其基本原 理与w i n 3 2 a p i 的进步实现原理是一样的。m f c 类库也提供了对多线程的支持， m f c 封装了同步对象，使用起来更加方便。以下将详细说明两者。 3 1 1w i n 3 2a p i 多线程 w i n 3 2a p i 是w i n d o w s 操作系统为内核和应用程序之间提