（计算机应用技术专业论文）openmp多线程负载均衡分析方法及调度策略研究.pdf

摘要 多核技术作为提高处理器性能的一个有效可行的方法，不仅在科学领域中产 生了推动作用，也给人们的生活带来了方便。纵观当今市场上的p c 机、服务器、 笔记本电脑，多核已逐渐成为趋势。多核在带来巨大处理潜力的同时，对软件方 面提出了巨大的挑战，原有的串行编程模式已不再适应，需要向并行编程模式转 变。其中，o p e n m p 能够为具有统一地址空间的并行系统提供可移植、可扩展的 开发接口。但是，使用并行编程模式编写的并行程序同样具有使用串行编程模式 编写串行程序时所要面临的性能影响问题。负载均衡就是影响并行程序运行性能 的主要因素之一。为了精确分析负载均衡，缓解程序所表现的负载不均衡性，以 提高程序运行性能，本文主要对o p e n m p 线程负载均衡分析方法以及调度策略 展开讨论和研究。 本文首先讨论和分析了多核技术的发展及其对软件业所产生的影响；总结和 归纳了o p e n m p 相关研究，包括并行效率和性能的分析与改进、多线程之间的锁 同步与竞争、多核编程中的负载均衡以及o p e n m p 的模型扩展与改进；同时，对 支持o p e n m p 的o m p i 编译器以及并行化程序的重要对象循环结构进行了介绍。 其次，为了精确分析并行程序所表现的负载均衡问题，优化性能分析流程， 本文确定了负载均衡分析单元，度量了负载不均衡程度以及潜在的并行调整效率， 并提出了一种以负载均衡分析单元为分析对象来监测、分析、调整o p e n m p 多线 程程序负载均衡的方法。通过实验表明该方法是可行的、有效的。 最后，考虑到并行程序中并行任务是依据调度策略来实现负载的分配，为了 在调度开销与负载均衡之间获得更好的权衡，本文提出将t r a p e z o i d 梯式调度策略 在开源的、支持o p e n m p 的o m p i 编译器进行实现，以提高o p e n m p 多线程程序的 运行性能。实验结果表明：梯式调度策略在递减以及某些极不规则的循环结构中， 在适当的线程数下，与指数调度相比，该调度策略能表现出更好的性能。 关键词：多核技术；o p e n m p ；负载均衡；调度策略；o m p i i i a b s t r a c t m u l t i c o r ec a ni m p r o v et h ep e r f o r m a n c e o fp r o c e s s o r sa sae f f e c t i 诣a n d f e a s i b 1 e w a y w i t hp r o m o t i n g t h ed e v e l 。p m e n t 0 fs c i e n c e a n dt e c h n 0 1 0 9 y ，n a o m = t h el i f e 。fp e o p l em o r ec 。n v e n i e n t l 0 0 k i n ga t t h ec u 玎e mm a r k 武1 n 掣1 登f ： s e r v i c e ，n o t e b o o ka n d s oo n ，m u l t i c o r ep r o c e s s o r h a s b e c o m eat r c n d g r a d u a l l y ： h o w e v e r w h i l em u l t i c o r eb r i n g st h ee i l o r m o u sp r o c e s s i n g p o t e n t i a l ，i tm a k e s ag r e a t c h a l l e n g ef o rt h es i d eo f s o f t w a r e i tm e a n st h a tt h e 。r i g i n a ls e r i a lp r o g m m m i n g m o d e s h 。u l d 。b ec h a n g e di n t 。t h ep a r a l l e lp r 。伊a m m i n gm o d e a t t h i sn m e ，o p e n m p ，：竺 n r 。v i d ep 。r t a b l ea n ds c a l a b l ep r o g r a m m i n gi n t e r f a c e s f o rt h ep a r a n e ls y s t e mw h l c h f t h a - st h eu n i f i e da d d r e s s s p a c e ，b u t i ts h o u l df a c em o r ep r o b l e m 8 a b o m p e r f ? a n c e i m p a c tw h e np a r a l l e l i n gt h es e r i a lp r 。g r 锄s w i t ho p e n m p ，f o re x a m p l e 1 0 a 竺b a l a n c t ： i s o n eo ft h em o s ti m p o r t a n t f a c t o r sw h i c hi m p a c tt h ep e r f o 珊a n c e o i p a r a l l ，e l p r o g r a m s i n0 r d e r t oa n a l y z et h el o a db a l a n c ep r o b l 锄a c c u 眦e l y a n d a ! l e v i 甜e ：h e l o a d 。i m b a l a n c er e n e c t e d i nt h ep a r a l l e lp r o g r a m sa n d t h e ni m p r 。v et h e r u n n 1 n 乏 p e r f o 彻a n c eo fp a r a l l e lp r 。g r a m s ，t h i s t h e s i sm a i n l yd i s c u s s e st h e 柚a i y z l n gm e t n 。d a n ds c h e d u l i n gs c h e m eo fo p e n m p m u l t i t h r e a dl o a db a l a n c e f i r s t l y ，t h i st h e s i sa n a l y z e st h ed e v e l o p m e n to f m u l t i _ c o r ea sw e l la s t h ee t t e c t b r 。u g h tb yi tf o rt h es o f t w a r ei n d u s t r y i tg i v e s ad e e pd i s c u s s i 。n 。nr e s e a r c h e so v e r p e r 盂二c ea n a l y s i s ，t h r e a d s y n c h f 。n i z a t i 。n a n dc o m p e t n i o n 1 0 a o b a 1 a n ，c e ，a b o u t 1 m u l t i - c o r ep r o g r 砌m i n ga n dm o d c l e x t e n s i o n f o ro p e n m nn 卸m i w h 掣：，a 。p e n s 。u r c ：c 。m p i l e rw i t hs u p p 。r t i n go p e n m p a p ii sa l s 。i n 2 r 。d u c e da s w 竺1 ：? ：e l o o pw h i c hi so n e 。f t h em o s ti m p 。r t a n ts t r u c t u r e st h a tc a n b ep a r a l l e l i z e de f f e c t l v e i y s ：c o n d l y ，i n0 r d e rt 。a c c u r a t e l ya n a l y z et h e 1 0 a d i m b a l a n c e 代化d 司m 也e p a r a l l e lp r 。g r 锄sa n d 。p t i m i z et h ep e r f o 咖a n c ea n a l y s i s p r 。c e s s ，m i st h e s l sd e f i n e s ：h eu n i t1 0 fl 。o a db a l a n c ea n a l y s i sa n dm e a s u r e s t h ed e 舒e e 。fi o a di m b 8 1 觚a n d t h e a d j u s t e de 伍c i e n c y o fl a t e n c yp a r a l l e l ，t h e np r 。p o s e s am e t h 。df o r m o n i t o r i n g , a 二l y z i n ga n da d j u s t i n go p e n m pm u l t i - t h r e a d l o a d i m b a l a n c e n x p 盯1 m 叽仇1 r e s u l t ss h o wt h a tt h em e t h o di sf e a s i b l ea n de f f e c t i v e f i n a l l v ，i nv i e wo ft h ef a c tt h a tp a r a l l e lt a s k sa c h i e v e t h el o a dd i s t r i b u t l 。n b a s e d 。nt h es c h e d u l i n g s c h e m e ，t h es c h e d u l i n gs c h e m ep l a y s a ni m p o n a n 0 1 “k ，1 8 8 ： 。fl 。a d b a l a n c e i no r d e rt og e tb e t t e r p e r f o r r n a n c ea n dr e a c h 舢烈伧豫曲加誓 b e t w e e ns c h e d u l i n go v e f h e a da n dl o a d b a l a n c e ，t h i s t h e s i si m p l e m e n t st h et r a p e z o i d i l i s c h e d u l i n gs c h e m eu s i n go m p i ，ao p e n - s o u r c ec o m p i l e rt h a ts u p p o r t so p e n m pa p i t h ee v a l u a t i o nr e s u l t ss h o wt h a tt h et r a p e z o i ds e l f - s c h e d u l i n gw i l ly i e l db e t t e r p e r f o r m a n c et h a ng u i d e ds e l f - s c h e d u l i n gi nc a s eo f t h ed e c r e a s i n g - a n di r r e g u l a r l o o p s t r u c t u r ew i t hn o r m a lt h r e a d sn u m b e r k e yw o r d s ：m u l t i - c o r e ；o p e n m p ；l o a db a l a n c e ；s c h e d u l i n gs c h e m e ；o m p i i v 硕一i ：学位论文 插图索引 图2 1对称多处理器架构图7 图2 2i n t e l 和a m d 双核架构8 图2 3 o p e n m p 并行模式1 3 图2 4o m p i 编译器源到源转换后的代码架构1 8 图2 5四种基本循环结构19 图3 1o p e n m p 多线程负载均衡分析方法的逻辑模型2 3 图3 2线程间的负载不均衡被掩盖2 5 图5 1四种循环结构负载不均衡程度4 0 图5 2四种循环结构潜在并行调整效率4 0 图5 3m s 程序负载均衡分析单元各线程负载分布情况4 5 图5 4a c 程序负载均衡分析单元各线程负载分布情况4 6 图5 5 四种循环结构的并行化性能s ( p ) 4 6 v l i 附表索引 表3 1隐含同步显示化2 7 表4 1不同调度策略划分的调度块大小变化情况3 2 表5 1不同调度策略下m s 程序负载均衡分析单元的负载分布情况4 1 表5 2 不同调度策略下c p 程序负载均衡分析单元的负载分布情况4 l 表5 3m a t r i xm u l t i p l i c a t i o n 测试结果4 4 表5 4m a n d e l b r o ts e t 测试结果4 4 表5 5 c o m p u t ep o t s 测试结果4 5 表5 6a d i o i n tc o n v o l u t i o n 测试结果4 5 v i h 硕一l 学位论文 1 1 研究背景及意义 第1 章绪论 处理器性能的提高主要在于两个方面：是半导体工艺的不断进步；二是处 理器体系结构的不断发展。就处理器而言，半导体工艺的进步就意味着主频的提 高。处理器的知名厂商一直来主要是通过提高主频来增力n c p u 的执行效率，但 是考虑到频率的提高所带来的功耗散热问题以及半导体技术发展的极限，采用多 核技术就成为提高执行效率的一个有效可行的方法之一。 2 0 0 5 年上半年，i n t e l 和a m d 相继推出了自己的双核处理器，随后推出了各自 的多核发展计划，宣告了多核时代的来临。多核处理器在带来巨大处理潜力的同 时，也对程序开发人员和开发工具提出了巨大的挑战，这与以往处理器技术的进 步所带来的影响完全不同。在过去几十年中，每次微处理器技术的进步都会自动 提高现有程序的运行速度，而不需要程序员的干预。例如，当处理器工作主频从1 g h z 提高n 2g h z 时，程序无需任何修改就能够更快的被执行，在更短的时间内得 到运行结果。然而，这种规律已经不再适用于多核处理器。在主频、c a c h e 等其它 条件完全相同的条件下，没有针对多核优化的程序在多核c p u 上运行的速度与它 在单核c p u 上运行的速度并不会有什么区别。实际上，该程序仅仅利用了多核处 理器中的一个处理核心，而其它处理核心是处于空闲状态。 为了充分利用多核处理器计算能力，就必须依据多核处理器模型编写能够并 行执行的程序，充分利用多核处理器上的所有硬件资源。因此，对并行编程方法 和模型的研究显得更为重要。在并行编程方法和模型的研究中，并行编程模型对 现有程序设计语言以及操作系统环境改动较小，因而是颇有应用前景的一种方法。 对现有的编程语言进行扩展是并行编程模型实现的种方式，一个著名的例子是 o p e n m p ，它是共享内存并行程序设计的工业标准，可以对c 语言以及f o r t r a n 语言 进行扩展，从而为现有程序设计语言增加多线程的能力。 o p e n m p 具有良好的可移植性，不仅能够支持多种编程语言，而且也能够运 用于多种平台上，但是使用o p e n m p 并行化后的多线程程序同样具有串行程序所 要面临的性能影响问题，如锁同步与竞争操作、负载不均衡、存储访问方式、过 多的使用f o r k j o i n 所带来的线程管理开销等【，其中，负载不均衡是影响多线程程 序运行性能的重要因素【2 1 。如果借助负载均衡分析方法对程序中所表现出的负载 不均衡性进行精确分析，明确程序中发生负载不均衡的具体点以及影响程度，然 后有选择的对并行程序段进行有效调整，同时，灵活的选择需要被监测的程序段， o p e n m p 多线程负载均衡分析方法及调度策略研究 那么在一定程度上能够缓解程序所表现的负载不均衡性，以提高程序运行性能， 优化性能分析流程。同时，考虑到并行程序中并行任务是借助调度策略来实现负 载的分配，如果能通过调度策略将并行程序中的并行任务合理的划分并分配于各 个线程上，尽量减少线程间的负载不均衡性，那么在软件方面就能有效的提高程 序的运行效率，在硬件方面也能发挥多核的优势。所以本文对o p e n m p 多线程负 载均衡分析方法以及调度策略的研究具有重大的理论和实践意义。 1 2 相关研究及其现状 主频的提高反映了处理器运行性能的提升，但是，随着处理器的频率进入“g 时代以后，频率对于提高处理器综合性能的影响似乎不如从前了，同时，频率的 提高所带来的功耗散热、成本控制等问题给厂商带来了众多难题。在这种现状下， 多核概念呼之欲出。多核是指将多个计算内核集成在一个处理器芯片中，以提升 处理器运行性能。多核在带来巨大处理潜力的同时，也使得软件业面临了巨大的 挑战。为了充分利用多核处理器的计算能力，在软件方面就必须依据多核处理器 模型编写能够并行执行的程序。并行处理技术包括了硬件和软件两个部分。硬件 并行技术主要是计算机体系结构上的创新研究，包括：指令级并行( i n s t r u c t i o n l e v e lp a r a l l e l i s m ，i l p ) ，超线程技术以及多核技术。在软件层次，则存在与硬件 并行技术相对应的研究。例如：与指令级并行对应的编译器指令序列调度优化技 术等。在多核处理器层次也有相应的软件研究工作，主要包括并行编程语言开发、 并行信息的编译器自动提取和分解以及基于多线程的并行编程模型。其中，基于 多线程的并行编程模型对现有程序设计语言以及操作系统环境改动最小，因而是 颇有应用前景的一种方法。目前，基于多线程的并行编程模型主要有四种。第一 种是由程序员调用操作系统的a p i 函数，主动构造多线程结构，实现程序的功能。 这一类包括：m p i ，m i c r o s o f t 的w i n 3 2m u l t i t h r e a da p i 以及p o s i xt h r e a da p i 。 第二种方法是采用支持多线程编程的程序设计语言。j a v a 以及c 捍这两种语言都支 持线程级的程序设计。第三种方法是将程序与现有针对多线程运行环境进行过优 化的程序库进行连接和集成。例如，i n t e l 公司推出了一种能够充分利用多核处理 器计算能力的数学程序库( m a t hk e r n e ll i b r a r y , m k l ) 。最后一种方法是对现有的 编程语言进行扩展。一个著名的例子是o p e n m p ，它是共享内存并行程序设计的 工业标准，可以对c 语言以及f o r t r a n 语言进行扩展，从而为现有程序设计语言增 加多线程的能力。由于o p e n m p 具有良好的可移植性，支持多种编程语言，a p i 比 较少，容易被程序设计人员所接受，并且在支持并行代码的同时不需要对串行部 分的代码进行修改，因而成为广大研究人员关注的重点。使用o p e n m p 并行化后 的程序同样具有串行程序所需要面临的性能影响问题。影响o p e n m p 并行程序性 能的因素包括o p e n m p 本身程序运行的开销、程序中串行部分所占的比例、线程 2 硕j j 学位论文 之间的负载不均衡、线程锁竞争以及同步开销等【3j ，其中，负载均衡是影响o p e n m p 并行化程序后所带来的影响程序运行性能的重要因素【2 j 。 使用好的性能分析方法对并行程序所表现的负载不均衡性进行精确分析，有 助于缓解并行程序所表现的负载不均衡性，以提高程序运行性能。在高性能计算 领域里，需要关注的重要问题之一就是并行程序的性能分析。在这种背景下，出 现了并行程序性能分析方法、工具设计与实现方面的研究【4 q 引。其核心基本是首 先通过对程序代码进行分析，然后利用插桩模板对程序代码进行处理，最后对程 序进行性能监控、性能数据收集、分析、性能信息显示。并行程序性能分析的实 现技术一般分为静态和动态两种【l3 1 。通过模拟程序运行环境以及仿真程序的运行 来实现程序的性能分析称之为静态性能分析，此时，程序并未真正运行。在程序 运行时通过有效的方式获取实际的性能参数并进行相应的分析称之为动态性能分 析，性能参数可以包括硬件和软件方面的参数，如硬件方面的访存冲突率、软件 方面的负载不均衡性、调度开销等。获取性能参数信息的方法有统计( p r o f i l i n g ) 和事件跟踪( t r a c i n g ) ，它们都以插桩技术为基础。 目前在对程序进行性能监测时采用的关键技术大多是插桩技术【l4 1 。插桩可以 理解成一种代码修改机制，其目的是借助插桩点来获取程序当前状态的相关信息。 根据插桩方式的不同可以分为对源代码插桩、对运行时库插桩以及对中间表示层 插桩。基于插桩技术对o p e n m p 程序进行负载均衡分析的现有工具已有一些，如 t a u 7 1 、v t u n e 8 1 、o m n i 9 】等。上述已有的o p e n m p 性能工具( 除o m n i # b ) 关注的 重点都是程序负载均衡的监测、性能数据的获取以及显示，并没有依据所获得的 性能数据对程序进行负载均衡的调整，虽然o m n i 在对程序进行性能分析过程中包 含这方面的内容，但是缺乏灵活性。文献【ll 】考虑程序并行效率以及同步段在程 序所有同步段中的比重提出了相应的均衡策略，能够有针对性的对分析单元进行 均衡调整，体现出了好的灵活性。 有效的性能分析方法有助于精确分析并行程序所表现的负载不均衡性，缓解 其负载不均衡程度，同时，考虑到并行程序中的并行任务是依据调度策略来实现 负载的分配，因此调度策略在负载均衡问题上发挥着重要作用。实现一个好的负 载均衡通常有两种方案【l6 1 ，一种是静态调度，另外一种是动态调度。o p e n m p 并行编程模型为载体，静态调度的含义是程序在编译的时候将并行部分进行任务 划分以及分配，而动态调度是程序在执行的时候实现任务的划分以及分配。显然， 动态调度与静态调度相比，更有效，更灵活，也能解决静态调度所不能解决的问 题，如问题规模只有在程序执行时才能确定的情况【1 7 】。动态调度依据任务划分以 及分配的原则衍生出几种典型的动态调度策略，如p u r es e l f _ s c h e d u l i n g ( p s s ) 引、 g u i d e ds e l f - s c h e d u l i n g ( g s s ) 【19 1 、t r a p e z o i ds e l f - s c h e d u l i n g ( t s s ) 【2 0 】等。除了上述调 度策略之外，学者们也已提出了很多其它延伸的调度策略。不同的调度策略适应 3 o p e n m p 多线程负载均衡分析方法及调度策略研究 于不同的系统结构以及问题场景【2 m 5 1 。文献 2 l 】在一种极端的集群系统环境下， 针对无相关的循环结构，考虑c p u 时钟频率，提出了一种启发式的a 调度策略。文 献 2 4 考虑到处理器之间的性能差异，提出了一种结合t r a p e z o i d 及f a c t o r i n g 优势 的t r a p e z o i df a c t o r i n gs e l f - s c h e d u l i n g ( t f s s ) 。通过实验表明，在分布式环境下，与 其它调度策略相比，t f s s 表现出更好的性能。文献 2 5 】基于现有的o p e n m p 编译 器，借鉴文献 2 1 提出的a 调度策略，针对指数调度策略不适合递减型循环结构的 缺点，在o m p i 编译器上实现了一种新的n e w 策略。但是，采用启发式的aguided 调度策略需要面临确定合适仅值的问题。 1 3 论文主要工作 循环结构是o p e n m p 并行化串行程序的重要对象，也是有效发挥并行效率的 程序结构。在并行化过程中，程序中的循环并行任务会依据调度策略被划分及分 配到不同的线程，如果每个线程之间分配的负载不均衡，那么有的线程可能会执 行很长的时间才结束，所承受的负担沉重，而有的线程则会因为没事可做处于空 闲状态。这自然会给程序并行带来问题，也会无法发挥多处理核优势。因此，借 助好的性能分析方法来精确分析并行程序所表现的负载不均衡性，使用好的调度 策略在各线程之间实现负载分配，那么将有效的缓解并行程序所表现的负载不均 衡性，以提高程序的运行性能。本文的主要工作如下： ( 1 ) 研究o p e n m p 多线程技术的研究现状和发展趋势，对多核技术的发展及其 对软件业的影响进行了分析和总结，并指出了与多核技术相关联的并行技术；尤 其对与o p e n m p 相关的研究进行了分析和归纳。 ( 2 ) 针对o p e n m p 多线程程序所表现的负载均衡问题，总结并分析了现有的负 载均衡分析方法及工具的特性，提出了一种能精确分析并行程序所表现的负载不 均衡性、贴切度量其负载不均衡程度、灵活选择需要监测的程序段的o p e n m p 多 线程负载均衡分析方法。该方法以负载均衡分析单元为分析对象来监测、分析、 调整o p e n m p 多线程程序的负载不均衡，并在隐含同步显示化的基础上，使用指 导语句改写的方法对源程序进行插桩并获取性能数据，以供负载均衡度量及分析。 同时，通过实验对该方法进行了验证。 ( 3 ) 针对调度策略在o p e n m p 多线程程序所表现的负载均衡问题中发挥着重 要作用，探究了不同调度策略的优点和缺点。为了在调度开销与负载均衡之间获 得更好的权衡，提出将t r a p e z o i d 梯式调度策略在o m p i 编译器进行实现，并使用 o p e n m p 多线程负载均衡分析方法来辅助性能分析。 4 硕 ：学位论文 1 4 论文组织结构 论文全文共分为5 章，论文的各章节组织安排如下： 第1 章为绪论，介绍了课题研究的背景及意义，阐述了负载均衡分析方法以及 调度策略的相关研究与现状，并对课题研究的主要工作以及论文的组织结构进行 了论述。 第2 章首先介绍了o p e n m p 萎；线程技术的基本术语和相关概念，分析和探讨了 多核技术的发展及其对软件业的影响。然后详细论述了与o p e n m p 相关研究的现 状，最后阐述了开源的、支持o p e n m p 的编译器o m p i 以及o p e n m p 并行化程序中 的重要对象循环结构。 第3 章分析了现有负载均衡分析方法及工具的特性，提出了一种以负载均衡分 析单元为分析对象来监测、分析、调整o p e n m p 多线程程序负载不均衡的方法。 详细阐述了该方法的逻辑模型以及逻辑模型中所涉及到的关键实现，并通过实验 对该方法进行了验证。 第4 章探讨了对o p e n m p 多线程负载均衡问题产生重要作用的调度策略，并分 析了现有不同调度策略的优点和缺点，提出将t r a p e z o i d 梯式调度策略在o m p i 编译 器进行实现。详细阐述了t r a p e z o i d 梯式调度策略在o m p i 编译器上的设计思想及实 现细节。 第5 章依据o p e n m p 多线程负载均衡分析方法的逻辑模型展开实验，通过实验 验证了该方法是可行的、有效的。同时，使用o p e n m p 多线程负载均衡分析方法 来辅助调度策略的性能分析，并在不同线程数、循环结构、调度块大小的情况下 使用不同调度策略对程序运行性能产生的影响进行了分析。依据实验结果可以看 出，梯式调度策略在递减以及某些极不规则的循环结构中，在适当的线程数下， 与指数调度相比，该调度策略能表现出更好的性能。 最后对全文进行了总结，并阐述了进一步研究的方向。 o p e n m p 多线程负载均衡分析方法及调度策略研究 第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 的o m p i 编译器以及o p e n m p 并行化串行程序中的重要对象 循环结构。 2 1 多核技术基础 2 1 1 多核技术背景 处理器性能的提高主要得益于两个方面：一是半导体工艺的逐渐进步；二是 处理器体系结构的不断发展。2 0 世纪7 0 年代许多知名厂家如i n t e l 、a m d 、i b m 等都推出了不同型号的处理器，印证了处理器的快速发展。增加集成电路的集成 度，提高其性能的主要方法是缩小晶体管尺寸，然而尺寸的缩小必将有一个极限。 如果不能在半导体工艺、原材料方面有所突破，那么往后就无法在更大程度上缩 小晶体管尺寸，这对于处理器频率而言，也就很难再有所提高。另一方面，处理 器的频率进入“g 时代以后，频率对于提高处理器综合性能的影响似乎不如从 前了，同时，频率的提高所带来的功耗散热、成本的控制等问题给厂商带来了众 多难题。据统计，随着频率的不断提升，c p u 的发热量也与日剧增，由最初的2 0 w 发展到了今天的1 3 0 w 以上经过多年的发展，i n t e l 公司推出了频率高达3 8 g h z 的处理器，然而对于推出4 g h z 处理器的计划就没有了下文。i n t e l 公司的老竞争 对手a m d 推出的处理器的频率超过了2 g h z ，但是3 g h z 却成了很难跨越的障碍。 摆在眼前的事实是：处理器的时钟频率不可能无限制的提高，硅原子的直径是否 会有革命性的进展还是芯片技术发展中一个未知的问题；单纯的追求时钟频率的 提升，势必会带来功耗散热等相关问题，这是生产厂家和用户所不愿见到的。在 这种现状下，多核概念就呼之欲出了。 由美国斯坦福大学提出的片上多核处理器( c h i pm u l t i p r o c e s s o r , c m p ) 是将多 个计算内核集成在一个处理器芯片中，从而提高计算能力，而多核是其最基本、 最简单、最容易实现的一种类型。其实，在r i s c 处理器领域，双核心甚至多核 心都早已经实现。而且，早在上个世纪末，惠普和i b m 就已经提出了双核处理器 的可行性设计。其中，i b m 在2 0 0 1 年发布了基于双核心的p o w e r 4 处理器，s u n 和h p 公司在2 0 0 4 年2 月和3 月发布了基于双核的分别命名为u l t r a s p a r 和 p a r i s c 的处理器。但是这种架构仅仅局限于高端的r i s c 领域，应用面窄，没 6 硕，卜学位论文 有引起广泛的注意。2 0 0 5 年4 月1 8 曰，这是计算机发展史上的一个重要时刻， i n t e l 全球同步首发基于双核技术桌面产品i n t e lp e n t i u md 处理器，正式宣告x 8 6 处理器多核心时代来临。随后a m d 推出了专用于服务器和工作站的双核处理器 o p t e r o n ，还有专用于台式机的a t h l o n6 4x 2 双核系列产品。多核在当今市场上发 展得如火如荼。 2 1 2 多核技术概述 多核可以理解成在一个处理芯片上包含多个“执行内核”，从而使处理器能完 全并行的执行程序的多线程。从操作系统层面上来看，多核就是多个处理器，每 个处理器拥有独立的全部相关资源的一个处理核心。而从架构方面来看，多处理 器可以分为对称多处理( s y m m e t r i c a lm u l t i p r o c e s s i n g ，s m p ) 和非对称多处理 ( a s y m m e t r i c a lm u l t i p r o c e s s i n g ，a m p ) 。 对称多处理( s m p ) 是在一个计算机上集合了一组处理器( 多c p u ) ，每个c p u 之间共享内存子系统以及总线结构。其结构如图2 1 。 图2 1 对称多处理器架构图 多个处理器运行操作系统的单一复本，共享内存和计算机上的其他资源，对 内存、i o 和外部中断可以进行平等地访问。系统使得任务队列对称地分布于多个 c p u 之上，以提高整个系统的数据处理能力，充分利用多c p u 优势。随着用户对 应用水平要求的不断提高，使用单个处理器已很难满足实际应用的需求，所以各 厂商纷纷都采用s m p 系统架构的解决方案。现在生产多核产品的主要厂商有i n t e l 和a m d 两家，但是两家在内核架构的设计上还是有很大的不同。如图2 2 所示， a m d 从一开始设计时就考虑到了对多核心的支持，将两个内核做在一个d i e ( 内 核) 上，通过直连架构连接起来，核心之间以芯片速度进行通信，消除系统架构 方面的挑战和瓶颈，集成度更高。i n t e l , 贝l j 是采用两个独立的内核封装在一起，多 个核心共享前端总线的方式，所以当a m d 推出首款双核处理器时，加上了“真双 核来区另l j i n t e l 的“双芯”。a m d 的架构更容易实现双核以至多核，i n t e l 的架构 会遇到多个内核争用总线资源的瓶颈问题。 7 o p e n m p 多线程负载均衡分析方法及调度策略研究 i n t dp t i l 瑚双核架构劬仍o b e r o n 双核架构 图2 2i n t e l 和a m d 双核架构 非对称多处理( a m p ) 由主从处理器组成，其中，主处理器是系统的核心，用 来运行操作系统，负责完成与操作系统相关的一系列操作，如系统调用、i o 控制、 任务调度等，从处理器用来完成用户定义的指定功能。因此，在这种a m p 系统架 构中，资源和任务是由不同性质的微处理器进行管理，这使得它们的工作负载也 不一样，就有可能出现一个处理器任务负载很重，而另一个处理器可能会无事可 做处于空闲状态，从而产生负载不均衡现象。同时，a m p 系统的容错性很差，当 一个处理器发生故障时，整个系统都可能无法正常工作。但是，在嵌入式领域里， a m p 硬件构成的系统却具有广泛的应用前景如s o c 、d s p 等。 处理器架构从单核发展到多核架构，在这过程中，与之相关的技术也在发生 着变化，同时也带来了一些影响多核性能的问题，如节点间通信、任务调度策略、 c a c h e - - 致性问题以及系统异构性问题等。 ( 1 ) 节点间通信 处理器上的各个处理核除了能并行处理多任务、多线程外，有时在执行的程 序中还需要数据共享和同步，那么相应的硬件结构就必须支持核间通信。目前比 较盛行的片上通信机制有两种：一种是基于共享内存的结构，一种是基于片上的 互连结构。基于共享内存的结构是指各个处理器通过中间层与共享的存储器联系， 而中间层可以将数据包放在共享内存空间。此结构需要考虑到两个问题：需要考 虑将数据包放在合适的存储器位置以及对共享内存访问时产生的互斥性。基于片 上的互连结构是指各个处理器借助连接介质( 如局域网等) 进行相互通信，中间 层跨过连接通信介质使数据包传送到所要求的目的节点。此结构也需要考虑到两 个问题：如何选择连接介质以及如何通知发送点数据包已到达。 ( 2 ) 任务调度策略 任务调度策略从整体上可以分为静态调度和动态调度。从操作系统级上来看， 8 硕十学位论文 静态调度可以理解成在系统运行前，获取与任务相关联的一系列信息，以为任务 的静态分配提供参考，形成静态分配方案，在运行时，系统根据静态分配方案来 实现任务的分配。但是，在多核架构的系统中，每个处理器上所承载的任务是动 态产生的，很难作出准确的预测，所以，静态调度方式更多的用于理论研究和辅 助工具。动态调度与静态调度不同，它是在程序运行过程中实现任务的调度。在 运行过程中，系统中相关的任务信息会动态产生，某个处理机上所承载的任务可 能出现突发性的增加或减少，如果能够通过分析多处理器系统的实时任务负载信 息，动态地调度任务，并将任务负载均衡的分配在各个处理机上，那么就可以消 除系统中负载分布的不均匀性，充分利用多核优势。但是，每个支持多处理器的 操作系统都有一套自己的任务调度算法，作为应用程序者更多的会去关心编译器 级的调度策略。 ( 3 ) c a c h e - - 致性问题 c a c h e 层可以缓解处理器和存储器速度不匹配的问题，在多处理器架构的系统 中也有很多应用。同时，它也带来了相应的性能影响问题，如不同处理器私有c a c h e 与共享存储器中数据的不一致即c a c h e 不一致性问题等。出现上述数据不一致性问 题的原因可能有：共享了具有写权限的数据、进程发生迁移时对相关数据未作保 护措施以及i o 传输。在不同的节点通信方式中存在解决c a c h e 不一致性问题的不 同方法。如针对共享内存的通信方式，可以使用监听协议来缓解所出现的c a c h e 不一致问题。 ( 4 ) 系统异构性问题 多处理器架构的系统必须要面对的问题之一就是系统的异构性问题。不同的 处理器使用的数据表示方法可能不一样，女1 l i t t l ee n d i a n 处理器在低位地址存放最 低有效字节，而b i ge n d i a n 处理器是在低位地址存放最高有效字节放。如果在一个 多处理器架构中包含了具有不同数据表示方法的处理器，那么处理器间进行数据 通信时就需要特别关注数据表示格式的差别，以保证数据通信的正确性。 2 1 3 多核技术的发展 软件多线程并行执行意味着多个软件线程在多个硬件平台上同时执行。不过， 对于多线程技术而言，还是经历了指令级并行、超线程技术( 也可称为同时多线 程) 以及当前越来越受关注的多核技术的发展过程。 ( 1 ) 指令级并行( i n s t r u c t i o n 1 e v e lp a r a l l e l i s m ，i l p ) 指令级并行可以理解成动态执行或者乱序( o u to f o r d e r ) 执行技术。其目标是 要增加处理器在单个时钟周期内所能够执行的指令条数。通过重定序机制重新安 排流水线中指令的执行顺序，从而增加指令执行的机会。由处理器来对指令进行 动态调度的工作，对软件开发人员来说是透明的。指令级并行只是让多个指令流 9 o p e n m p 多线程负载均衡分析方法及调度策略研究 交错执行，而没有真正将多线程同时执行。 ( 2 ) 超线程技术 为了实现程序的多线程执行能力，在多核技术正式出现之前，i n t e l 于2 0 0 2 年将创新的超线程技术( h y p e r t h r e a d i n g ，h p ) 运用于新款i n t e lp e n t i u m4 处理器。 超线程技术实际是在单核情况下，利用特殊的硬件结构将两个逻辑内核模拟成两 个物理芯片，从而实现单个处理器就能使线程级并行计算，这样就使得新款i n t e l p e n t i u m4 处理器能兼容多线程操作系统和软件。也就是说，处理器在执行一个线 程时所闲置下来的资源可以分给另一个线程以实现并行计算。这样可以减少c p u 的闲置时间，提高c p u 的运行效率。超线程技术在执行的多个线程不争用同一资 源的情况下能很好提高c p u 的运行效率，如当一个线程要等待用户的键盘输入信 息而被暂时挂起时，另一个线程就可以直接使用处理器的所有资源。但是，在相 反的情况之下，处理器的性能可能会受到影响，这是因为程序在执行过程中会有 调用线程的开销，处理此种现象的开销等等。超线程技术的性能发挥受到了多个 执行线程共享资源可用性的限制，所以拥有超线程技术的单核与多核的性能是有 区别的。那么提升单个芯片上的处理性能，处理器就应该拥有两个或多个核心， 这就使得并行执行的每个线程都拥有独立的整套处理资源，相互之间能保持相对 的独立，从而真正实现多线程的并行执行。 ( 3 ) 多核技术 多核技术所依存的结构不是上述所说的逻辑处理器，而是在一个芯片上集成 了多个处理核，是实在的多处理器结构。因为存在多个处理核，所以每个线程都 具有一个完整的硬件执行环境。那么，各线程之间也就实现了真正意义上的并行。 当然，拥有多个核心的处理器的制造工艺比较复杂，成本也相对要高。而且多核 的架构需要考虑数据一致性和核间通信等问题。在多核架构的情况下，每个处理 核都有自己的缓存，在执行多线程时，对于共享数据的更新必须体现在每个拥有 此共享数据的处理核的缓存上才能保证数据的一致性，从而使程序能正确运行。 执行的多个线程有时需要数据交换和同步，核间通信自然也是需要考虑的。超线 程技术的发挥并不要求多处理器体系结构，而是利用空闲的处理资源以便在相同 时间内完成更多的任务。对于多核技术而言，以双核系统为例，其性能提高在理 论上可以达到或者接近两倍。所以，如果能够将超线程技术与多核技术相结合， 那么就能给应用程序带