（计算机系统结构专业论文）多核处理器并行编程模型的设计和实现.pdf

上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 一导师签名： 1 1 日期： 上海大学工学硕士学位论文 多核处理器并行编程模型的 设计和实现 姓名：曹折波 导师：李青 学科专业：计算机系统结构 上海大学计算机工程与科学学院 2 0 0 9 年1 2 月 上海大学硕士学位论文 ad i s s e r t a t i o ns u b m i t t e dt os h a n g h a iu n i v e r s i t yf o rt h e d e g r e eo fm a s t e ri ne n g i n e e r i n g 一一一 t h ed e s i g na n d r e a l i z a t i o no f p a r a l l e lp r o g r a m m i n gm o d e lo n m u l t i c o r e m d c a n d i d a t e ：c a oz h e b o s u p e r v i s o r ：l iq i n g m a j o r ：c o m p u t e rs y s t e m a r c h i t e c t u r e s c h o o lo fc o m p u t e re n g i n e e r i n ga n ds c i e n c e s h a n g h a iu n i v e r s i t y d e c e m b e r , 2 0 0 9 i v 随着现代社会对计算能力和信息处理速度要求的不断提高，如何提高c p u 处理能力成了亟需解决的问题。传统的依靠提高c p u 主频来提高处理能力的方 法由于受到功耗和设计复杂度的制约已接近极限，在这种背景下，多核处理器 开始出现并成为主流。 多核处理器出现的目的是为了提升程序的性能，然而传统的串行程序却无 法充分利用多核资源来提高运算速度，硬件性能的提升与软件功能的滞后之间 的矛盾日趋显著。编写适用于多核平台的并行程序成为了解决软硬件矛盾的有 效途径之一，这需要程序开发人员全面了解多核处理器体系结构和并行编程方 法，开发与维护的难度比较大。 针对这些问题，本文设计并实现了一个多核处理器的并行编程模型，为开 发人员提供了一个方便高效的开发多核并行程序的接口。我们所设计的多核处 理器并行编程模型是基于任务密取调度策略的以任务作为处理对象的并行程序 库。测试表明，使用该并行编程模型开发的并行程序可获得高性能：资源利用 率高、可扩展性好。论文的主要工作有以下几个方面： ( 1 ) 研究了并行程序设计的一般方法和多核处理器的体系结构，分析了多 核处理器环境下可能影响并行程序性能的因素，并且针对这些问题，提出了一 些解决方案。 ( 2 ) 设计并实现了一个基于任务的并行编程模型，它提供了单任务多数据 流并行和多任务并行两种并行处理方式，其中单任务多数据流并行提供c a c h e 块划分技术以减少存储竞争，多任务并行提供任务密取的任务调度策略以实现 负载均衡。另外，并行编程模型还提供了c a c h e 行对齐内存管理、原子操作、 栅栏机制、消息机制这些基本功能特性。 ( 3 ) 在多核处理器环境下通过计算斐波那契数列和图像处理算法的实例测 试分析了并行编程模型的性能。 关键词：多核处理器，并行程序，并行编程模型，c a c h e 块划分技术，任务密 取 v 上海大学硕士学位论文 a bs t r a c t w i t ht h ei n c r e a s i n gd e m a n d s0 1 1c o m p u t a t i o na b i l i t ya n dd a t ap r o c e s s i n g s p e e di nm o d e r ns o c i e t y , h o w t oi m p r o v ec p u p r o c e s s i n gc a p a b i l i t yh a sb e c o m e ap r o b l e mt h a tn e e d st ob es o l v e di m m e d i a t e l y t h et r a d i t i o n a lm e t h o do f i m p r o v i n gp r o c e s s i n gc a p a b i l i t yb yi m p r o v i n gc p uf r e q u e n c yi sn e a r i n gt h e u t m o s tf o rt h ec o n s t r a i n to fp o w e rc o n s u m p t i o na n dd e s i g nc o m p l i c a c y u n d e r t h e s ec i r c u m s t a n c e s ，m u l t i c o r ep r o c e s s o ri sb e c o m i n gt h em a i n s t r e a m m u l t i c o r ep r o c e s s o ri sb o mt oi m p r o v ep r o g r a mp e r f o r m a n c e ，w h i l et h e t r a d i t i o n a ls e r i a lp r o g r a mc a n n o tf u l l yu t i l i z em u l t i - c o r er e s o u r c e st oi m p r o v e c a l c u l a t i o ns p e e d s ot h ec o n f l i c tb e t w e e nh a r d w a r ep e r f o r m a n c ei m p r o v e m e n t a n ds 0 1 a r ef u n c t i o nl a gi sb e c o m i n gm o r ea n dm o r en o t a b l e w r i t i n gp a r a l l e l p r o g r a mw h i c hc a nr u no nm u l t i c o r ep l a t f o r mb e c o m e so n eo ft h ee f f e c t i v e w a y st os o l v et h i sp r o b l e m b u ti tr e q u i r e st h ep r o g r a m m e rt of u l l yu n d e r s t a n d s y s t e ma r c h i t e c t u r eo fm u l t i - c o r ep r o c e s s o ra n dp a r a l l e lp r o g r a m m i n gm e t h o d t h e r e f o r ei ti sd i 伍c u l tt ow r i t ea n dm a i n t a i n a i m i n ga tt h e s ep r o b l e m s ，t h i sa r t i c l ed e s i g n sa n dr e a l i z e sap a r a l l e l p r o g r a m m i n g m o d e lo nm u l t i c o r e i tp r o v i d e st h ep r o g r a m m e rw i t ha c o n v e n i e n ta n de f f i c i e n ti n t e r f a c et ow r i t ep a r a l l e lp r o g r a mo nm u l t i c o r e p r o c e s s o r t h i sp a r a l l e lp r o g r a m m i n gm o d e li sap a r a l l e lp r o g r a m m i n gl i b r a r y w h i c hi sb a s e do nt a s ka n du s e sw o r ks t e a l i n gt a s ks c h e d u l i n gs t r a t e g y t e s t r e s u l t si n d i c a t et h a tp a r a l l e lp r o g r a m sw r i t t e nb yt h i sp a r a l l e lp r o g r a m m i n g m o d e lh a v eh i g hp e r f o r m a n c e s ：c a l lu t i l i z es y s t e mr e s o u r c e sa n dc a nb e e x t e n d e d t h em a i nw o r ko ft h i sa r t i c l ei sc o n s i s t e do fa sf o l l o w s ： ( 1 ) w es t u d yt h ec o m m o nw a y so fd e s i g n i n gp a r a l l e lp r o g r a ma n ds y s t e m a r c h i t e c t u r eo fm u l t i c o r ep r o c e s s o r , t h e nw ea n a l y z et h ef a c t o r st h a tm a y i n f l u e n c et h ep e r f o r m a n c eo fp a r a l l e lp r o g r a m so nm u l t i - c o r ep l a t f o r ma n df i n d v i 上海大学硕士学位论文 s o m es o l u t i o n st ot h e s ep r o b l e m s ( 2 ) w ed e s i g na n dr e a l i z eap a r a l l e lp r o g r a m m i n gm o d e lb a s e do nt a s k t h i sm o d e lp r o v i d e st w op a r a l l e lp r o c e s s i n gm e t h o d s ，s i n g l et a s km u l t i p l ed a t a s t r e a m sp a r a l l e l i z a t i o na n d m u l t i p l et a s k sp a r a l l e l i z a t i o n t h es i n g l et a s k m u l t i p l ed a t as t r e a m sp a r a l l e l i z a t i o np r o v i d e sc a c h eb l o c k i n gt e c h n i q u et o r e d u c em e m o r yc o n f l i c t sa n dt h em u l t i p l et a s k sp a r a l l e l i z a t i o np r o v i d e sw o r k s t e a l i n gt a s ks c h e d u l i n gs t r a t e g yt ok e e pl o a d - b a l a n c e f u r t h e r , t h i sp a r a l l e l p r o g r a m m i n gm o d e lp r o v i d e ss o m eb a s i cf u n c t i o n sl i k ec a c h el i n ea l i g n m e n t m e m o r ym a n a g e m e n t ，a t o m i co p e r a t i o n , b a r r i e rm e c h a n i s ma n d m e s s a g e m e c h a n i s m ( 3 ) w et e s ta n da n a l y z et h ep e r f o r m a n c eo f0 1 1 1 p a r a l l e lp r o g r a m m i n g m o d e lt h r o u g ht h ep r o g r a mo fc a l c u l a t i n gf i b o n a c c ia n di m a g ep r o c e s s i n g a l g o r i t h m k e y w o r d s ：m u l t i c o r ep r o c e s s o r , p a r a l l e lp r o g r a m ，p a r a l l e lp r o g r a m m i n g m o d e l ，c a c h eb l o c k i n gt e c h n i q u e ，w o r ks t e a l i n g v i i 上海大学硕十学位论文 目录 摘要v a b s t r a c t 第一章绪论1 1 1 课题研究背景l 1 1 1 计算机的高速发展1 1 1 2 多核处理器的出现2 1 1 3 多核处理器面临的挑战3 i 2 课题研究的目的及贡献4 1 2 1 课题研究的目的4 1 2 2 课题研究的贡献5 1 3 相关领域研究现状6 1 4 本文工作和论文组织。7 第二章并行处理与并行程序设计方法的研究与分析9 2 1 并行处理的研究9 2 1 1 计算机体系结构的分类9 2 1 2 并行处理技术及其发展1 0 2 2 并行处理的分类。1 3 2 3 并行程序设计方法及比较1 4 2 3 1 新并行编程语言。1 4 2 3 2 并行化编译器1 5 2 3 3 扩展编程语言1 6 2 3 4 并行编程模型1 7 2 3 5 并行程序设计方法的分析比较1 8 第三章影响多核并行程序性能的因素及解决方案1 9 3 1 多核处理器体系结构分析。1 9 3 2 影响多核并行程序性能的因素分析2 0 3 3 提高多核并行程序性能的方法2 2 3 3 1 控制同时运行线程的数量一2 2 3 3 2c a c h e 块技术2 2 3 3 3c a c h e 行对齐内存分配2 4 3 3 4 任务的合理分配。2 6 第四章并行编程模型的设计与实现2 7 4 1 基于任务的并行编程2 7 4 1 1 单任务多数据流并行2 8 4 1 2 多任务并行。3 0 4 2 任务密取的任务调度策略3 l 4 3 并行编程模型的基本功能特性3 4 4 3 1c a c h e 行对齐内存管理3 5 4 3 2 原子操作类3 5 4 3 3 栅栏机制3 6 4 3 4 消息机制3 8 v i i i 上海大学硕士学位论文 4 4 并行编程模型的总体结构4 0 第五章并行编程模型的应用与测试4 2 5 1 斐波那契数列应用与测试4 2 5 2 图像处理算法应用与测试。4 7 第六章总结与展望5 1 6 1 总结5l 6 2 展望5 2 参考文献5 3 作者在攻读硕士学位期间公开发表的论文5 6 致 射5 7 上海大学硕士学位论文 1 1 课题研究背景 1 1 1 计算机的高速发展 第一章绪论 计算机的发展，如果从第一台计算机的问世算起，到现在才6 0 余年，在人 类科技史上还没有一种学科可以与计算机的发展之快相提并论。 2 0 世纪4 0 年代，无线电技术和无线电工业的发展为计算机的研制准备了 物质基础。1 9 4 5 年，数学家约翰冯诺依曼提出了“存储程序的计算模型， 即：冯诺依曼体系结构【1 1 。在这种结构中，程序是按顺序存放在计算机存储 器中的指令序列，程序中的指令以线性和单线程的模式串行执行。1 9 4 6 年2 月 1 4 日，美国宾夕法尼亚大学研制的电子数字积分器和计算机e n i a c 2 ( t h e e l e c t r o n i cn u m e r i c a li n t e g r a t o r a n dc o m p u t e r ) 在费城公诸于世，它是世界上第一 台电子计算机，标志着现代计算机的诞生。 在早期，计算机只是一个配备了单用户操作系统的简单的孤立设备，每次 只能运行一个程序，用户只能通过简单的文本界面与计算机进行交互。此后， 计算机技术不断发展，同时也将冯诺依曼所提出的设想加以延伸和扩展，2 0 世纪6 0 年代出现了分时共享操作系统【3 】，分时共享操作系统首次引入了程序并 发执行的概念，多个用户能够同时访问同一台主机并向其提交各自的作业以等 待处理。 随着大规模集成电路的发展，2 0 世纪7 0 年代世界上第一款微处理器4 0 0 4 【4 1 诞生，在接下来的多年时间内，处理器遵循着摩尔定律【5 】以“每隔1 8 个月处理 器芯片集成的晶体管数量翻一番，频率提高一倍”发展，处理器工业诞生了x 8 6 系n t 6 1 ，p o w e r 系列吲，s p a r c 系列【8 】等多个家族里程碑式的处理器，操作系 统也日趋完善，具备了批量处理、分时处理和实时处理等多种功能。 计算机的每一次更新换代都使得其体积和耗电量大大减小，功能大大增强， 应用领域进一步拓宽。特别是体积小、价格低、功能强的微型计算机的出现， 上海大学硕士学位论文 使得计算机迅速普及，不仅极大地促进了传统工业向信息化发展，还在人们日 常生活中扮演着多方面的重要角色。目前，计算机的应用已扩展到社会的各个 领域并向着以下四个方向发展： ( 1 ) 巨型化 天文、军事、仿真等领域需要进行大量的计算，要求计算机有更高的运算 速度、更大的存储量，一般的大型通用计算机不能满足要求，这就需要研制功 能更强的巨型计算机。 ( 2 ) 微型化 专用微型机已经大量应用于仪器、仪表和家用电器中。通用微型机已经大 量进入办公室和家庭，但人们需要体积更小、更轻便、易于携带的微型机，以 便出门在外或在旅途中均可使用计算机，应运而生的掌上微型机不断涌现并迅 速普及。 ( 3 ) 网络化 将地理位置分散的计算机通过专用的电缆或通信线路互相连接，就组成了 计算机网络。网络可以使分散的各种资源得到共享，使计算机的实际效用大大 提高。计算机联网不再是可有可无的事，而是计算机应用中一个很重要的部分。 因特网就是个通过通信线路联接、覆盖全球的计算机网络，通过因特网，人 们足不出户就可以获取大量信息，与世界各地的亲友快捷通信，进行网上贸易 等等。 ( 4 ) 智能化 目前的计算机已经能够部分地代替人的脑力劳动，但是人们希望计算机具 有更多的类似人的智能，比如：能听懂人的语言，能识别图形，会自行学习， 能以人的方式思考等等。 1 1 2 多核处理器的出现 计算机技术的迅猛发展使得现代社会对计算能力和信息处理速度的要求不 断提高，这使得提高c p u 处理能力来提升系统一蚪i - t 厶匕f j e 成为了解决问题的关键。然 而传统的依靠提高c p u 主频来提高处理能力的方法由于受到功耗和设计复杂 2 上海大学硕士学位论文 度的制约已接近极限，当晶体管数量增加导致功耗增长超过性能增长速度后， 处理器的可靠性就会受到致命性的影响，因此，如何在提升处理器主频的同时 减少发热量并降低制造工艺成为了亟需解决的问题。 在这种情况下，c p u 厂商开始寻找新的方式来突破计算能力的限制。多核 心c p u 解决方案的出现，似乎给人带来了新的希望，一些大型机生产厂商，如 i b m 、s u n ，开始利用计算机理论的并行计算设计出了多核c p u ，这些c p u 在 一块芯片上集成多个计算内核，成倍地提高计算速度的同时又降低了功耗。多 核处理器通过分布多个内核，每个内核频率稍微降低，可以有效减少芯片热量。 多核处理器还可以重复利用先前设计，提高内核复用率，同时多个核共享外部 总线等硬件资源，降低了单位成本。 2 0 0 5 年4 月，英特尔推出简单封装双核的奔腾d 和奔腾四至尊版8 4 0 。a m d 在之后也发布7 x 2 核皓龙( o p t e r o n ) 和速龙( a t h l o n ) 处理器。2 0 0 6 年7 月2 3 日， 英特尔基于酷睿( c o r e ) 架构的处理器正式发布。至此，多核处理器的应用范围从 大型机扩展到了家用机。2 0 0 6 年1 1 月，英特尔又推出面向服务器、工作站和 高端个人电脑的至强( x e o n ) 5 3 0 0 以及酷睿双核和四核至尊版系列处理器。与上 一代台式机处理器相比，酷睿2 双核处理器在性能方面提高了4 0 ，而功耗反 而降低了4 0 。 如今，多核处理器己经广泛地在桌面、工作站、服务器等平台迅速普及， 甚至已经拓展到了移动计算平台等。今后，多核处理器的应用范围将会越来越 广泛，多核并行程序将成为应用程序的主流，多核处理器也必定会全面取代单 核处理器成为新一代处理器的发展方向。 1 1 3 多核处理器面临的挑战 多核处理器在应用上的优势主要有两个方面：为用户带来更强大的计算性 能；更重要的，则是可满足用户同时进行多任务处理和多任务计算环境的要求。 随着处理器核心数的不断增加，要想充分发挥多核处理器的性能优势，还需要 有适用于多核平台的并行程序。 虽然多核处理器在低层的指令级上实现了并行，然而目前的大部分应用程 上海大学硕士学位论文 序还并不能自动分割成可以并行运行的多任务，分别交给多核处理器的多个核 心去执行。传统的串行程序在编译器的编译下只能生成单一的执行程序，运行 在处理器的一个计算核心上，即使其他核心是空闲的，也无法充分利用他们共 同工作。所以，在多核处理器上运行传统的串行程序并不能给用户带来更强大 的计算性能。 为了充分发挥多核处理器的性能，就需要最大可能地利用多核处理器并行 化的架构优势，编写具有良好并行性的、高性能的、资源利用率高的多核并行 程序。尽管在并行计算研究上，人类已经探索了超过4 0 年，但编写、调试以及 优化并行处理程序的能力还非常弱，开发并行应用程序对于程序开发人员来说 难度较大。 多核时代的到来，给传统的串行程序带来了巨大的冲击，也给软件开发人 员带来了严峻的考验。 1 2 课题研究的目的及贡献 1 2 1 课题研究的目的 传统串行程序无法充分利用多核处理器资源来发挥多核处理器的性能优 势，如何开发能在多核处理器上运行的并行程序成为了开发人员面临的最大难 题，主要包括以下几个方面： ( 1 ) 缺乏并行程序的开发经验 传统的串行程序开发人员早已习惯于编写单一的执行程序，缺少并行程序 的编写经验。面对一个全新的运行环境和程序设计模式，程序开发人员往往觉 得无从下手。 ( 2 ) 不了解线程的运行机制 编写多线程并行程序是充分利用多核资源的有效途径之一，然而这需要开 发人员充分了解线程的创建与销毁、线程的运行机制、线程的分配、线程之间 的同步、线程的管理、线程的调度等诸多问题，开发和调试的难度都比较大， 开发效率也比较低。 4 上海大学硕士学位论文 ( 3 ) 如何将任务映射到线程 对于开发人员来说，如何将一个给定的任务合理而有效地映射到多个线程 从而分配到多核处理器多个核心上并行运行具有一定的难度。 ( 4 ) 如何开发出高性能、充分利用多核资源的并行程序 多核处理器在体系结构方面与单核处理器有诸多的不同，比如：高速缓存、 总线设计、核间通信等。开发人员必须全面了解多核体系结构才能开发出高性 能的多核并行程序。 ( 5 ) 如何开发出扩展性高的多核并行程序 多核处理器是处理器发展的必然趋势，将来处理器核心数必将越来越多。 如何开发出随着处理器核心数的增加系统性能也随之提升的可扩展性高的并行 程序成为了开发人员需要解决的问题。 本课题的研究目的就是要在分析研究多核处理器体系结构的基础上，了解 多核并行程序的特性，掌握并行编程的一般方法，开发一个能使开发人员方便 开发多核并行应用程序的、多核资源利用率高的、运行速度快的、扩展性好的 多核并行程序库。 1 2 2 课题研究的贡献 针对开发人员在多核处理器环境下开发多核并行程序面临的这些难题，本 文在分析多核处理器体系结构的基础上，研究实现了一个基于多核处理器的并 行编程模型。 首先，该模型以任务的方式定义具体问题，可以从任务的角度方便地将串 行程序划分成多个子任务映射到多核处理器的多个核心上并行执行，使得程序 开发人员无需了解多核处理器的体系结构以及底层的线程是如何工作、如何管 理的，也无需考虑如何将一个任务划分成多个子任务并行执行就能方便高效地 开发多核并行程序。 其次，在研究分析影响多核并行程序性能因素的基础上，通过优化调整， 减少有限带宽上的存储竞争，提高c a c h e 利用率，达到负载均衡，最大限度地 利用多核资源来提高程序性能。对于应用开发人员来说，完全不需要了解并行 5 上海大学硕士学位论文 程序是怎么进行优化的就能开发出资源利用率高的、运行速度快的多核并行程 序。 最后，使用该模型开发的多核并行程序是可扩展的，即：随着处理器核心 数的增加，程序性能将随之上升，而开发人员无需对代码做任何修改。另外， 该模型还提供了不同的并行处理接口，使得开发人员能够根据具体问题方便地 使用相应接口开发并行程序。 1 3 相关领域研究现状 多核处理器环境下的并行编程研究在多年前就已经展开，例如 s w a r m ( 9 ( s o f t w a r ea n da l g o r i t h m sf o rr u n n i n go nm u l t i c o r e ) 。m c s t l 1 0 】( t h e m u l t i c o r es t a n d a r dt e m p l a t el i b r a r y ) ，s k a n d i u mj a v am u l t i c o r el i b r a r y l l l l ， q u i c k t h r e a d 1 2 1 ，c i l k 1 3 】等。 s w a r m 是一个开源的、方便的、充分利用多核处理器资源的并行程序库， 主要有两大贡献： ( 1 ) 提出了一个新的分析多核处理器系统中算法性能的计算模型。 ( 2 ) 提出了一个开源的、方便的并行编程框架。它提供了多核编程的基本 方法，如：同步、控制、内存管理和集合操作等。 m c s t l 是标准c + + 库的并行实现，s t l ( s t a n d a r dt e m p l a t el i b r a r y ) 的算法 如s o r t , r a n d o m _ s h u f f l e ，p a r t i a l _ s u m ，f o r _ e a c h , p a r t i t i o n , m e r g e ，f i n d ，n t h e l e m e n t 等都将因为并行性而提升性能。在实际应用中程序开发人员无需改变原来代码 而只需使用s t l 的算法就能轻松实现程序的并行。此外，m c s t l 还能很好地 与s t l 库协同处理外存上的大数据集。 s k a n d i u mj a v am u l t i c o r el i b r a r y 是一个基于多核处理器体系结构的并行编 程j a v a 算法框架库，它提供了基本的并行模式，比如：m a s t e r - s l a v e ，p i p e ，f o r , w h i l e ，i f , m a p ，f o r k 和d i v i d ea n dc o n q u e r 。 q u i c k t h r e a d 是一个为n u m a ( n o n u n i f o r mm e m o r ya c c e s s ) 体系结构优化 的c 抖多核编程库。q u i c k t h r e a d 的最大特点是充分利用底层硬件和考虑所有的 c a c h e 层次以及n u m a 结点。q u i c k t h r e a d 提供了基本的并行结构，比如： 6 并行程序，在编写很难用数据并行或消息传递类型实现的并行程序，比如动态 异步并行等程序时尤为高效。c i l k 提供了一个高效编写密集和稀疏数据的算法， 如矩阵因数分解。c i l k 语言设计最主要的概念是，程序设计人员应该负责探索 程序并行运算的可能性，分辨出程序中可以安全地进行并行运算的元素以及决 定程序运行时处理器之间如何分配工作。 以上这些并行编程库虽然为开发多核并行程序提供了一个方便的接口，但 是它们大都针对特定的体系结构或者提供的是底层的控制，对于程序开发人员 来说，还是要考虑如何将具体问题按照何种方式合理有效地分配到各个处理器 核心并行执行，此外对于那些针对特定体系结构的并行编程库，将在一定程度 上限制并行程序的可移植性。 1 4 本文工作和论文组织 本文在分析多核处理器体系结构的基础上，研究并实现了基于多核处理器 的并行编程模型。主要工作有： ( 1 ) 研究了并行程序设计方法和多核处理器体系结构，分析了多核处理器 环境下可能影响并行程序性能的因素，提出了解决这些问题的方法。 ( 2 ) 提出了一个基于任务密取策略的、面向任务的、提供不同并行处理接 口的多核处理器并行编程模型。 ( 3 ) 在多核平台上，通过实验和应用进一步分析验证了我们的多核编程模 型的性能。 本文的具体章节安排如下： 第一章阐述了课题的研究背景，简要介绍了课题的研究目的和贡献以及相 关领域的研究现状，简单描述了本文的工作重点。 第二章研究了并行处理的相关技术，分析了并行处理的方式与并行程序设 计的一般方法，为后文实现并行编程模型奠定基础。 7 上海大学硕士学位论文 第三章研究了多核处理器的体系结构，分析了多核平台上可能影响并行程 序性能的因素并提出了相应的解决方案。 第四章详细介绍了多核处理器并行编程模型的设计和实现以及该模型提供 的基本功能特性。 第五章使用并行编程模型做了一些实验和应用，进一步分析验证了该模型 的性能。 第六章对全文进行总结并对进一步研究方向作出展望。 上海大学硕士学位论文 第二章并行处理与并行程序设计方法的研究与分析 2 1 并行处理的研究 2 1 1 计算机体系结构的分类 一般而言，可以从两种不同的角度对计算机体系结构进行分类。第一种分 类的依据是计算机在单个时间点能够处理的指令( 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 ) 的数 量。因此，任何给定的计算机系统都可以根据其处理指令和数据的方式加以归 类。这种分类方法就是众所周知的f l y n n 于1 9 7 2 年提出的f l y n n 分类法【1 4 】，如 图2 1 所示。 争 秀 髟 “，4 一 缓 萝 l l多指令流单数据流 ， ： ； l c 潲聊 。 l 多指令流多数据流 ；( m i m d )； ； 箩耄 g 褫jj 。? 。j j 。渤j ? 一? ， ， i ? ? j 镌 箩! 爹 。 “驾 ； 单指令流单数据流 ；单指令流多数据流i l( s i s d ：( s i m d )： i j 级， ， 。捌 魏， ，。么 图2 - 1 计算机体系结构分类图 根据f l y r m 分类法，计算机体系结构可以分为以下四类： ( 1 ) 单指令单数据流机器( s i s d ) 是一种传统的串行计算机，其硬件不支持任 何形式的并行，所有指令都串行执行。在某个时钟周期内，c p u 只能处理一个 数据流。很多早期的计算机都是这种体系结构的典型代表，例如最初的i b mp c 9 期非常流行 ( 2 ) 多指令单数据流机器( m i s d ) 采用多个指令流同时对一个数据流进行处 理。但是在大多数情况下，多个指令流处理多个数据流才是更加有效的处理方 式，因此，m i s d 并行计算机一般只是作为一种理论模型出现。 ( 3 ) 单指令多数据流机器( s i m d ) 采用一个指令流同时处理多个数据流。此 类机器在诸如数字信号处理、图像处理以及多媒体信息处理( 例如音频和视频 处理) 等应用领域非常有效。最初的阵列处理机或者向量处理机( 例如c r a y - 1 ) 等巨型计算机都具备进行s i m d 处理的能力。如今，几乎所有的计算机也都以 各种各样的指令集形式实现了s i m d 功能。 ( 4 ) 多指令多数据流机器( m r m d ) 能够同时执行多个指令流，这些指令流分 别对不同的数据流进行操作。m i m d 是目前最流行的并行计算平台。最新的多 核计算平台就属于m i m d 的范畴，例如i n t e l c d u o 双核处理器【15 1 。 因为目前的计算机一般都属于s i m d 或者m i m d 体系结构，而这两种体系 结构都提供了支持并行执行的硬件特性，因此开发人员能够非常方便地利用软 件中存在的数据级和任务级并行性来提高程序性能。 2 1 2 并行处理技术及其发展 并行处理技术是4 0 年来在微电子、印刷电路、高密度封装技术、高性能处 理机、存储系统、外围设备、通信通道、语言开发、编译技术、操作系统、程 序设计环境和应用问题等研究和工业发展的产物，并行计算机具有代表性的应 用领域有：数值天气预报应用、v l s i 电路的计算机辅助设计、大型数据库管理、 人工智能、犯罪控制和国防战略研究等，而且它的应用范围还在不断地扩大。 并行处理技术主要是以算法为核心，并行语言为描述，软硬件作为实现工具的 相互联系而又相互制约的一种结构技术。 所谓并行性是指在同一时刻或同一时间间隔内完成两种或两种以上工作， 只要在时间上互相重叠，都存在并行性。计算机系统中的并行性可从不同的层 次上实现，从低到高大致可分为： 1 0 上海大学硕士学位论文 ( 1 ) 指令内部的并行：是指指令执行中的各个微操作尽可能实现并行操作。 ( 2 ) 指令间的并行：是指两条或多条指令的执行是并行进行的。 ( 3 ) 任务处理的并行：是指将程序分解成可以并行处理的多个任务，并将 分解出来的任务并行处理。 ( 4 ) 作业处理的并行：是指并行处理两个或多个作业。如多道程序设计、 分时系统等。 并行处理技术有以下三种形式： ( 1 ) 时间并行：是指时间重叠，在并行性概念中引入时间因素，让多个处 理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加 快硬件周转而赢得速度。时间并行性概念的实现方式就是采用流水线处理部件。 这是一种非常经济而实用的并行技术，能保证计算机系统具有较高的性能价格 比。目前的高性能微型机几乎无一例外地使用了流水线技术。 ( 2 ) 空间并行：是指资源重复，在并行性概念中引入空间因素，以“数量 取胜 为原则来大幅度提高计算机的处理速度。大规模和超大规模集成电路的 迅速发展为空间并行技术带来了巨大生机，因而成为实现并行处理的一个主要 途径。空间并行技术主要体现在多处理器系统和多计算机系统，但在单处理器 系统中也得到了广泛应用。 ( 3 ) 时间并行+ 空间并行：是指时间重叠和资源重复的综合应用，既采用时 间并行性又采用空间并行性。 在过去的四十年中，摩尔定律一直引导着计算机设计人员的思维和计算机 产业的发展。为了满足信息处理的应用需求，使计算机性能按照摩尔定律进一 步提升，同时减小散热，降低成本，并行处理技术不断发展，可以概括为以下 三个阶段： ( 1 ) 指令级并行技术【1 6 】。为了使处理器资源得到最充分的利用，计算机体 系结构设计师采用了指令级并行技术( 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 ) 来提高处理器 性能。指令级并行技术，即动态执行或乱序( o u to fo r d e r ) 执行技术，使得c p u 能够以更加优化的方式对指令进行重定序，从而达到消除流水线停顿的目的。 这种并行是发生在硬件层次上的，而且对于软件设计开发人员来讲是透明的， 上海大学硕士学位论文 也就是说，软件人员并不能也不需要看到计算机硬件上的这些变化。 ( 2 ) 超线程技术【1 7 1 。超线程技术( h y p * n 鹏a d 洫g ) 实际上只有一个实际的物 理处理器，但是从软件的角度来看，存在多个逻辑处理器。超线程技术支持操 作系统和应用程序将多个线程调度到多个逻辑处理器上，就像多处理器系统一 样。从微体系结构的角度看，逻辑处理器的指令都是固定的，并且在共享的执 行资源上同时执行。也就是说，多个线程能够在多个逻辑处理器间进行调度， 但是由于执行资源是这些逻辑处理器共享的，因此微体系结构必须决定两个线 程如何以及何时切换执行，当一个线程被挂起的时候，另一个线程就会继续执 行。 ( 3 ) 多核处理器。多核处理器采用单芯片多处理器的设计，随着生产工艺 与制造技术上的进步，处理器厂商在设计多核处理器时，不是重用单个处理器 中某些处理器资源，而是在单个处理器芯片内实现两个或者更多的“执行核 。 实际上，这些执行核都是相互独立的处理器，只是位于同一块芯片上而已。这 些执行核都具有自己的执行集合以及体系结构资源。根据设计的不同，这些执 行核可能共享也可能不共享片上高速缓存。此外，这些互相独立的执行核可以 和超线程技术相结合，从而将逻辑处理器的数量增加到执行核数量的两倍。 图2 2 给出了不同处理器的体系结构。 c p u 状态 中断逻辑 执行单元c a c h e 单核结构 c p u 状态 中断逻辑 执行单元c a c h e c p u 状态c p u 状态 中断逻辑中断逻辑 执行单元 c a c h e 超线程技术 c p u 状态 中断逻辑 执行单元 c a c h e 多处理器结构 c p u 状态c p u 状态 中断逻辑中断逻辑 执行单元| c a c h e 执行单元| c a c h e c a c h e 图2 - 2 处理器体系结构图 1 2 多核体系结构 上海大学硕士学位论文 超线程技术与多核体系结构的区别在于：在超线程技术中，单个处理器被 分成许多部分来使用，其中一些部分被各线程共享