（计算机系统结构专业论文）基于多核环境的数据结构设计.pdf

学科、专业： 研究方向： 作者： 指导教师： 题 南京邮电大学 硕士学位论文摘要 计算机系统结构 并行计算及其体系结构 盟级研究生韭夔基 基于多核环境的数据结构设计 英文题目：d e s i g no fd a t as t r u c t u r ei nm u l t i c o r ee n v i r o n m e n t 主题词：多核环境，数据结构，算法，并行计算，多线程 k e y w o r d s ： m u l t i c o r ee n v i r o n m e n t ，d a t as t r u c t u r e ，a l g o r i t h m ，p a r a l l e l c o m p u t a t i o n ，m u l t i t h r e a d 9 1 南京邮电大学硕士研究生学位论文 摘要 摘要 随着多核处理器的普及，在桌面电脑和笔记本电脑上进行并行程序设计已成为可能。 然而，在并行概念尚未普及的今天，传统的串行计算软件只能导致多核的闲置，只有在算 法设计及软件开发时充分考虑并行性，多核处理器的优势才能真正发挥。数据结构是软件 实现的数据类型，传统的数据结构是在串行模型下设计的。因此，研究并设计基于多核环 境下的数据结构具有一定的理论意义和较高的实用价值。 本文主要在以下四个方面进行了研究： ( 1 ) 对多核环境下树形数据结构的设计进行了研究。主要考虑并行区域的选择，并利 用多线程的思想对二又树进行拆分，从而将任务( 如二叉树的搜索操作) 分配到多个核上 实现了并行执行的目的。 ( 2 ) 对图的并行数据结构进行了研究。多核环境下，根据无向图的空间存储特点，利 用多线程的思想将其搜索过程中的循环迭代分配到多个线程上并行的执行。 ( 3 ) 对线性递归的并行进行了研究。结合多处理机中线性递归并行程序的设计，设计 出基于多核环境的一种线性递归实例叫i b o n a c c i 数列多线程并行算法。 ( 4 ) 对排序算法的并行化进行了研究。分析了冒泡排序和归并排序的基本思想，利用 多线程方法对两种排序算法分别进行了并行化。 上述四点都对其算法进行了复杂性和并行性分析。 关键词：多核环境，数据结构，算法，并行计算，多线程 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h ep o p u l a r i t yo ft h em 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 m i n gb e c o m e sp o s s i b l ei n d e s k t o pc o m p u t e r sa n dn o t e b o o kc o m p u t e r s h o w e v e r , p a r a l l e lc o n c e p ti s n o ty e tw i d e l y a v a i l a b l et o d a y t h et r a d i t i o n a ls e r i a lc o m p u t a t i o ns o f t w a r ec a no n l yc a u s et h em u l t i c o r e p r o c e s s o ri d l e ，w h e nt h ea l g o r i t h md e s i g na n d t h es o f t w a r ed e v e l o p m e n tc a nc o n s i d e rp a r a l l e l i s m f u l l y , t h es u p e r i o r i t yo fm u l t i c o r ep r o c e s s o rc a nm a n i f e s tt r u l y d a t as t r u c t u r ei st h ed a t at y p e i m p l e m e n t e db ys o f t w a r e t h et r a d i t i o n a ld a t as t r u c t u r ei sd e s i g n e di nt h es e r i a lp r o g r a mm o d e l i th a ss o m et h e o r ys i g n i f i c a n c ea n da p p l i c a b l ev a l u et os t u d ya n dd e s i g nt h ed a t as t r u c t u r ei nt h e m u l t i c o r ee n v i r o n m e n t i nt h i st h e s i s ，t h em a i nr e s e a r c ho nf o u ra s p e c t s ： ( 1 ) s t u d yt h ed e s i g no ft r e e s h a p ed a t as t r u c t u r ei nm u l t i c o r ee n v i r o n m e n t i tc o n s i d e r st h e c h o i c eo fp a r a l l e lr e g i o ni m p o r t a n t l y , a n du s e st h em u l t i t h r e a dt os p l i tb i n a r yt r e e i nt h i sw a y , t h ep a r a l l e le x e c u t i o np u r p o s ei sa c h i e v e dw i t ht h et a s ka s s i g n e dt om u l t i c o r ep r o c e s s o r s ( 2 ) i ts t u d i e s t h ep a r a l l e ld a t as t r u c t u r eo fg r a p h i c s h a p e i nm u l t i c o r ee n v i r o n m e n t ， a c c o r d i n gt ot h ec h a r a c t e r i s t i co fs p a c es t o r a g ef o ru n d i r e c t e dg r a p h ，t h el o o pi t e r a t i o no fi t s s e a r c hp r o c e s si sp a r a l l e le x e c u t e dw h e ni ti sa s s i g n e dt om u l t i t h r e a dw i t ht h ei d e ao ft h e m u l t i t h r e a d ( 3 ) i tr e s e a r c h e st h ep a r a l l e lo fl i n e a rr e c u r s i o n i nt h ec o m b i n a t i o nw i t ht h ed e s i g no f p a r a l l e lp r o g r a m o fl i n e a rr e c u r s i o nu n d e rm u l t ip r o c e s s o r , i ti s d e s i g n e d i nm u l t i c o r e e n v i r o n m e n tt h a tal i n e a rr e c u r s i o ne x a m p l e - - f i b o n a c c im u l t i t h r e a dp a r a l l e la l g o r i t h m ( 4 ) t h ep a r a l l e lp r o c e s s i n go fs o r ta l g o r i t h m si sr e s e a r c h e d i ti sa n a l y z e dt h a tt h eb a s i c i d e a so ft h eb u b b l es o r ta n dt h em e r g es o r t ，a n dt h ep a r a l l e lo ft h et w os o r ta l g o r i t h m si s p r o g r a m m e dw i t h t h em u l t i t h r e a d i ti sa n a l y z e dt h a tt h ec o m p l e x i t ya n dp a r a l l e l i s mo ft h ea l la l g o r i t h m si nt h ea b o v ef o u r i t e m s k e y w o r d s ：m u l t i c o r ee n v i r o n m e n t ，d a t as t r u c t u r e ，a l g o r i t h m ，p a r a l l e lc o m p u t a t i o n ， m u l t i t h r e a d 南京邮电大学硕士研究生学位论文目录 目录 第一章绪论1 1 1 多核技术l 1 1 1 多核与超线程1 1 1 2 多核技术产生的背景2 1 1 3 多核技术带来的问题4 1 1 4 多核技术的前景5 1 2 研究的目的和意义5 1 - 3 本文的主要工作和文章的组织结构7 1 3 1 本文的主要工作7 1 3 2 文章的组织结构7 第二章w i n d o w s 环境下的并行计算技术8 2 1 并行概念8 2 1 1 并行和并行计算8 2 1 2 并行计算机系统的访存模型8 2 1 3 进程和线程1 0 2 1 4 数据相关与程序并行性l l 2 1 5 并行程序性能评测1 4 2 2w i n d o w s 环境下的并行方法1 8 2 2 1w i n d o w s 多线程l8 2 。2 2o p e n m p 1 9 2 2 3m p i 2 1 2 3i n t e l 多核工具2 l 2 3 1i n t e lc + + c o m p i l e r 2 2 2 3 2i n t e lv t u n e 性能分析器2 2 2 3 3i n t e lp a r a l l e ls t u d i o 2 3 2 4 本章小结2 3 第三章多核环境下树形数据结构的设计及算法实现2 5 3 1 二叉树的基本概念与性质2 5 3 1 1 二叉树的定义2 5 3 1 2 二叉树的性质2 5 3 1 3 二叉树的遍历2 6 3 2 多核环境下树形数据结构的设计2 6 3 2 1 二叉树的抽象数据定义2 6 3 2 2 二叉树的存储方式2 7 3 2 3 二叉树相应操作的并行设计2 8 3 3 实验分析3l 3 4 本章小结3 4 第四章多核环境下图形数据结构的设计及算法实现。：3 5 4 1 图的基本概念与性质3 5 4 1 1 图的定义3 5 4 1 2 图的遍历3 6 第五章多核环境下递归的设计及算法实现4 3 5 1 递归的基本概念，4 3 5 1 1 递归的定义4 3 5 1 2 递归的应用4 3 5 2 多核环境下递归的并行设计4 3 5 2 1 递归程序的并行性4 3 5 2 2 一种递归实例的并行设计4 5 5 2 3 实验分析4 7 5 3 本章小结5 0 第六章排序的并行设计及算法实现。5 2 6 1 冒泡排序5 2 6 1 1 冒泡排序算法的基本思想5 2 6 1 2 多核环境下并行冒泡排序算法5 2 6 1 3 实验分析5 3 6 2 两路归并排序5 5 6 2 1 两路归并排序算法的基本思想5 5 6 2 2 多核环境下并行归并排序5 5 6 2 3 实验分析5 6 6 3 本章小结5 6 第七章结束语5 7 j 【谢；5 8 参考文献5 9 攻读硕士学位期间的研究成果及发表的学术论文6 3 南京邮电大学硕士研究生学位论文第1 章绪论 第一章绪论 1 1 多核技术 1 1 1 多核与超线程 多核是指在一块芯片上集成两个或多个计算核。操作系统利用所有相关的资源，将它 的每个执行内核作为分立的逻辑处理器【1 】【2 】。通过在多个执行内核之间划分任务，多核处 理器可在特定的时钟周期内执行更多任务。多核架构能够使目前的软件更出色地运行，并 创建一个促进未来的软件编写更趋完善的架构。 在多核环境下，程序可以同时运行在多个物理核中。如图1 1 所示的双核环境下，线 程l 和线程2 分别独自占用执行单元1 和执行单元2 ，这在物理意义上实现了并行。 图1 1 多核技术( 共享c a c h e ) 超线程技术就是利用特殊的硬件指令，把两个逻辑内核模拟成两个物理芯片，让单个 处理器都能使用线程级并行计算，进而兼容多线程操作系统和软件，减少了c p u 的闲置时 间，提高的c p u 的运行效率【i 】【2 1 。从原理上来说，超线程技术属于i n t e l 版本的多线程技术。 这种技术可以让单c p u 拥有处理多线程的能力，而物理上只使用一个处理器。因此，这些 线程在运行过程中仍需要共用执行单元、缓存和系统总线接口。如图1 2 所示 图1 2 超线程技术 在超线程环境下，多个线程只是并发地在一个物理核上运行。如图1 2 所示，线程l 和线程2 都是在一个执行核上运行，只是超线程技术采用逻辑核模拟物理核的策略，所以 l 堕塞墅皇奎兰堡圭竺垄竺兰堡丝茎茎! 兰笙丝 会产生分别对应线程1 和线程2 的两个c p u 状态。虽然采用超线程技术能同时执行两个线 程，但它并不象两个真正的c p u 那样，每个c p u 都具有独立的资源。在执行多线程时两 个逻辑处理器均是交替工作，当两个线程都同时需要某一个资源时，其中一个要暂时停止， 并让出资源，直到这些资源闲置后才能继续。因此，超线程技术并不是真正意义上的并行， 它所带来的性能提升远不能等同于两个相同时钟频率处理器带来的性能提升。可以说i n t e l 的超线程技术仅可以看作是对单个处理器运算资源的优化利用。 1 1 2 多核技术产生的背景 信息技术目前已经成为推动人类社会生产力进步的主导力量，其影响深入到社会生产 和人类活动的方方面面，甚至每个人的工作、生活和学习方式也都因此发生了翻天覆地的 变化。作为信息技术的龙头，计算机技术也同样经历了巨大的发展历程。 一直以来，推动计算机技术不断进步的动力主要来自两个方面：一方面是以生产工艺 为代表的实现技术，其一直推动着计算机主频和器件密度不断向纵深发展：另一方面是以 并行技术为代表的计算机体系结构技术，不断推动着计算机性能横向发展。但由于器件物 理极限的存在，计算机主频和器件密度不可能无限提高。正因为这个缘由，目前主流的处 理器厂商都在将发展重心转向采用体系结构技术来提高计算机性能的轨道上，最终导致了 各种多核处理器的面世。多核的出现是技术发展和应用需求的必然产物【3 捌。这主要基于以 下事实： 1 晶体管时代即将到来 根据摩尔定律，微处理器的速度以及单片集成度每1 8 个月就会翻一番。经过多年的 发展，目前通用微处理器的主频已经突破了4 g h z ，数据宽度也达到6 4 位。在制造工艺方 面也同样以惊人的速度在发展，目前最先进的己投入生产的是3 2 纳米的微处理器，低数 值能使c p u 降低能耗。因此，体系结构的研究又遇到新的问题：如何有效地利用数目众多 的晶体管? 国际上针对这个问题的研究方兴未艾。多核通过在一个芯片上集成多个简单的 处理器核充分利用这些晶体管资源，发挥其最大的能效。 2 门延迟逐渐缩短，而全局连线延迟却不断加长 随着超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t e s ，v l s i ) i 艺技术的发展， 晶体管特征尺寸不断缩小，使得晶体管门延迟不断减少，但互连线延迟却不断变大。当芯 片的制造工艺达到0 1 8 微米甚至更小时，线延迟已经超过门延迟，成为限制电路性能提高 的主要因素。在这种情况下，由于单芯片多处理器( c h i pm u l t i p r o c e s s o r s ，c m p ) i 拘分布式结 构中全局信号较少，与集中式结构的超标量处理器结构相比，在克服线延迟影响方面更具 南京邮电大学硕士研究生学位论文 第1 章绪论 优势。 3 符合p o l l a c k 规则 按照p o l l a c k 规则，处理器性能的提升与其复杂性的平方根成正比。如果一个处理器 的硬件逻辑提高一倍，至多能提高性能4 0 ，而如果采用两个简单的处理器构成一个相同 硬件规模的双核处理器，则可以获得7 0 8 0 的性能提升。同时在面积上也同比缩小。 4 盾皂耗不断增长 随着工艺技术的发展和芯片复杂性的增加，芯片的发热现象日益突出。多核处理器里 单个核的速度较慢，处理器消耗较少的能量，产生较少的热量。同时，原来单核处理器里 增加的晶体管可用于增加多核处理器的核。在满足性能要求的基础上，多核处理器通过关 闭( 或降频) 一些处理器等低功耗技术，可以有效地降低能耗。 5 设计成本的考虑 随着处理器结构复杂性的不断提高，和人力成本的不断攀升，设计成本随时间呈线性 甚至超线性的增长。多核处理器通过处理器i p 等的复用，可以极大降低设计的成本。同时 模块的验证成本也显著下降。 6 体系结构发展的必然 超标量( s u p e r s c a l a r ) 结构和超长指令字( v e r yl a r g ei n s t r u c t i o nw o r d ，v l i w ) 结构在目前 的高性能微处理器中被广泛采用。但是它们的发展都遇到了难以逾越的障碍。超标量结构 使用多个功能部件同时执行多条指令，实现指令级的并行( 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 ) 。但其控制逻辑复杂，实现困难，研究表明，超标量结构的i l p 一般不超过8 。v l i w 结构使用多个相同功能部件执行一条超长的指令，但也有两大问题：编译技术支持和二进 制兼容问题。 未来的主流应用需要处理器具备同时执行更多条指令的能力，但是从单一线程中已经 不太可能提取更多的并行性，主要有以下两个方面的原因：一是不断增加的芯片面积提高 了生产成本；二是设计和验证所花费的时间变得更长。在目前的处理器结构上，更复杂化 的设计也只能得到有限的性能提高。 对单一控制线程的依赖限制了多数应用可提取的并行性，而主流商业应用一般都具有 较高的线程级并行性( t h r e a dl e v e lp a r a l l e l i s m ，t l p ) 。为此，研究人员提出了两种新型体 系结构：c m p 与同步多线程处理器r ( s i m u l t a n e o u sm u l t i t h r e a d i n g ，s m t ) ，这两种体系结构 可以充分利用这些应用的指令级并行性和线程级并行性，从而显著提高了这些应用的性 能。 从体系结构的角度看，s m t 比c m p 对处理器资源利用率要高，在克服线延迟影响方 3 塑塞墅皇奎兰堡圭竺窭生兰堡丝茎苎! 皇堕笙 面更具优势。c m p 相对s m t 的最大优势还在于其模块化设计的简洁性。复制简单设计非 常容易，指令调度也更加简单。同时s m t 中多个线程对共享资源的争用也会影向其性能， 而c m p 对共享资源的争用要少得多，因此当应用的线程级并行性较高时，c m p 性能一般 要优于s m t 。此外在设计上，更短的芯片连线使c m p 比长导线集中式设计的s m t 更容易 提高芯片的运行频率，从而在一定程度上起到性能优化的效果。 总之，c m p 通过在一个芯片上集成多个微处理器核心来提高程序的并行性。每个微处 理器核心实质上都是一个相对简单的单线程微处理器或者比较简单的多线程微处理器，这 样多个微处理器核心就可以并行地执行程序代码，因而具有了较高的线程级并行性。由于 c m p 采用了相对简单的微处理器作为处理器核心，使得c m p 具有高主频、设计和验证周 期短、控制逻辑简单、扩展性好、易于实现、功耗低、通信延迟低等优点。目前c m p 已 经成为处理器体系结构发展的一个重要趋势。 1 1 3 多核技术带来的问题 多核技术的问世给计算机工业带来更强大的能力，也给软件产业带来更大的挑战。硬 件的进步凸显了软件的滞后。“软件螺旋体”是指不断提升的处理器能力和越来越强大的软 件之间的相互影响：运算能力更加强大的处理器使得更加复杂的软件设计成为可能，而越 来越复杂的软件反过来促进处理器能力的进一步提升。计算机工业和消费电子产业的发展 需要软硬件的同时支持，软件工程和计算机科学家承认，尽管软件设计在过去几十年里得 到了巨大的发展，但在并行计算能力的开发上，却一直相当落后。 随着多核硬件产品的逐步普及，并行化在显现出其优异性能的同时，也带来了软件并 行化的全新应用模式，这也就意味着，软件开发人员再也不能忽视“并行化”在软件开发中 的重要地位，这就是并行程序设计的问题【3 羽。并行程序设计很早就有人开始研究，而且很 多人一直在进行这方面的研究。为什么并行程序设计那么难呢? 这是因为大多数计算机和 编程语言发明之初就是按照冯诺依曼理论进行设计的。根据冯诺依曼的理论，c p u 是按 照程序指令，一条条取出来并顺序执行的。而在多核或者多c p u 的计算机中，同时会有多 条指令在执行。与在单个顺序处理器中通过交替执行不同任务来造成并行的假象不同，针 对多核和多c p u 平台开发的软件是真正的并行软件，有多个执行内核( 或者多c p u ) 参 与计算，为了充分发挥多核( 多c p u ) 的能力，就要尽可能地让各个执行内核( 或者多 c p u ) 均衡工作。 目前一些桌面应用尚不支持多线程、价格相对偏高和应用开发工具的不成熟，还在一 定程度上限制多核处理器的推广。随着应用需求的扩大和技术的不断进步，多核必将展示 4 南京邮电大学硕士研究生学位论文 第1 章绪论 出其强大的性能优势。 1 1 4 多核技术的前景 多核技术具有如下好处：首先，由于是多个执行内核可以同时进行运算，因此可以显 著提升计算能力，而每个内核的主频可以比以前低，因而总体功耗增加不太大。其次，与 多c p u 相比，多核处理器采用与单c p u 相同的硬件机构，用户在提升计算能力的同时无 需进行任何硬件上的改变，这对用户来说非常方便。正是由于多核的这些优点，所以，多 核很快被用户接受，并得以普及1 1 。 2 0 0 9 年国际数据公司的统计数据表明，当今的计算机系统几乎都采用多核微处理器设 计。任何技术都在不断发展、不断进步，都延续着从概念的产生到研究的兴起，然后再进 一步发展、深化的过程。因此，计算机技术经过多年的发展之后，现在已经进入到多核时 代，即在同一基片上集成多个核。从理论上讲，只要支撑技术能够提供足够的集成度，那 么核的数量就可以无限增加。我们可以预测，随着时间的推移，技术不断进步，集成了更 多核的处理器会不断面世。 在纳米工艺之后，工艺将会完成从晶体管到量子的变革。只要技术持续向前发展，那 么十年内出现具有大量核的处理器就会变成现实。随着可集成的核的数量不断增长，处理 器体系结构能够在单个处理器内支持大量的基于硬件的、线程级的并行能力。采用多核技 术设计c p u 已成为当今主流技术，在不久的将来，多核编程也将取代现有一切单核编程成 为主流。 1 2 研究的目的和意义 多核给人们提供了更经济的计算能力，但是这种能力能否善加利用还要取决于软件。 如果不针对多核进行软件开发，不仅多核提供的强大计算能力得不到利用，相反还有可能 不如单核c p u 好用【1 2 】【1 3 】。 从某种程度上说，对于软件开发者而言，c p u 主频提升就像是免费的午餐，此前所有 的程序很自然地会从主频的提升中受益，而如今多核出现了，这种免费的午餐没有了。所 以必须针对多核重新进行软件设计。 多核对于不同应用领域的软件影响并不相同： 第一类是传统的科学计算机用户，他们的软件大部分是高性能计算专家写的，也多是 并行的，他们对多点接口( m u l t ip o i n ti n t e r f a c e ，m p i ) 、o p e n m p 等并行编程模型也已经 掌握。 第二类是一般意义上提到的服务器，如银行以及搜狐、g o o g l e 这样的互联网公司，它 5 堕塞墅皇奎兰堡圭竺茎生兰堡堡茎墨! 兰竺丝 们主要的业务特征是并发的访问。这些应用具有天然的并行性，如多用户的访问本身就是 并行的。 第三类是移动用户和桌面用户，他们是面临挑战最大的群体。这些用户的原有大部分 程序都是串行的。 因为多线程技术支持多个操作同时执行，所以能够显著提高程序性能。但是，并行程 序设计人员必须认识到：多线程同时也使得应用程序行为变得更加复杂，因此需要更加深 入的思考才能正确使用。多线程技术使程序行为变得更加复杂的根本原因是程序会同时发 生多个动作。对这些同时发生的动作以及它们之间的交互进行管理将面临同步，通信，负 载平衡，可扩展性这四个方面的挑战。要使应用程序性能达到最优，上述四个问题必须仔 细斟酌处理。 面对多核处理器的横空出世，比如目前已经普遍用于台式机的英特尔酷睿2 双核处理 器，软件研发人员必须学会应对新的难题，就是让软件适应多核处理器下的处理进程，来 确保实现软件的最大性能。研发人员要解决软件同步和潜在的性能瓶颈难题。大量企业目 前都在为多核处理器硬件研发多线程应用软件【l 捌。 由于多核处理器的工作原理与单核处理器是不同的。当使用多核时，程序必须能利用 所有这些核心，必须能同步运行这些核心上的指令。由此带来的挑战就是软件得根据多核 的并行处理原理来设计的。 多核环境下并行计算的进行，短期内仍有许多实际问题，如如何对多线程、同步、调 试和错误检测等方面提供更好的支持；长期来看，需要更好地理解人们想利用并行编程做 些什么，并学习如何在各种不同的并行机器上编写代码。软件之所以落后于多核芯片，其 原因是仍不清楚人们想用这些并行机器做些什么，当前许多设备的并行程度并不高。 许多公司都想把一些旧代码转换到多核，但不想重新编写应用程序。这一事实引起了 人们对自动化工具的极大关注，目前众多公司都在开发将串行代码转变为并行代码的编译 器。但这种方法可能行不通。现在需要的是用并行语言编写程序，这一工作必须详细到算 法级，因此真正需要的应该是并行编程语言。针对多核和多线程的软件开发将是未来十年 软件开发的主要挑战【2 1 2 5 1 。 在计算领域中，数据结构是计算机算法设计的基础，在计算科学中占有十分重要的地 位【2 由2 引。由于传统的数据结构设计一直是基于单核环境的，因此当今的数据结构不能很好 的使软件开发在多核环境下有效的利用多核的资源优势，来组织、存储和处理数据。目前 国内外有很多学者从事并行计算的研究【2 9 。3 2 1 ，而关于在多核环境下对数据结构进行设计的 6 堕塞塑皇奎兰堡圭竺垄生兰垡丝茎兰! 兰丝丝 研究论述甚少。i n t e l 的多核编程专家周伟明在2 0 0 7 软件开发2 0 大会上的演讲“多核计算 中的分布式数据结构”中，提出了复合数据结构设计方法，该方法包含节点叠加型复合和节 点链接型复合。他指出分布式数据结构主要用到节点链接型复合方法即通过先拆分后链接 来设计，并同时指出在对其进行操作时会存在着负载平衡、效率下降等问题【33 1 。因此，随 着多核技术的发展和普及，多核环境下的并行计算必将成为一种趋势，如何在多核系统下 有效地实现算法并行，基于多核环境的数据结构设计成为一个需要研究的课题。 1 3 本文的主要工作和文章的组织结构 1 3 1 本文的主要工作 本文在参考已有单核环境下数据结构设计方法的基础上，展开树、图、递归和排序数 据结构在多核计算机中的设计与实现的研究工作。数据结构由逻辑结构和物理结构组成。 逻辑结构是指数据元素之间的逻辑关系；物理结构是数据结构在计算机中的表示，它包括 空间组织及在其上的操作。我们知道研究数据结构的目的是为了在计算机中实现对它的操 作，因此本文着重于数据结构在多核环境中相应操作的实现，设计出基于多核环境的一一 树形数据结构、图数据结构、递归算法和排序算法，并对设计的相应算法进行复杂性分析。 1 3 2 文章的组织结构 第二章：w i n d o w s 环境下的多核并行方法。本章主要介绍并行计算的概念及条件，并 行计算机系统的访存模型，进程和线程的概念，以及并行程序性能的评测；简述目前 w i n d o w s 环境下的多核并行方法；简要介绍目前w i n d o w s 环境下已有的i n t e l 多核工具。 第三章：多核环境下树形数据结构的设计。本章简要介绍树形数据结构的基本概念； 设计出多核环境下的树形数据结构及相应算法；实验分析所设计相应算法的性能。 第四章：多核环境下图形数据结构的设计。本章简要介绍图形数据结构的基本概念： 设计出多核环境下的图形数据结构及相应算法；实验分析所设计相应算法的性能。 第五章：多核环境下递归的设计。本章简要介绍递归的基本概念；设计出多核环境下 的一种常用递归实例算法；实验分析所设计算法的性能。 第六章：多核环境下内排序的并行设计。本章简要介绍冒泡排序算法，设计出冒泡并 行排序算法；简要介绍两路归并排序算法，实验分析所设计相应算法的性能。 第七章：结束语。本章对论文的主要工作进行总结，介绍了进一步的工作并对课题的 前景进行了展望。 7 南京邮电大学硕士研究生学位论文第2 章w i n d o w s 环境下的并行计算技术 第二章w i n d o w s 环境下的并行计算技术 2 1 并行概念 2 1 1 并行和并行计算 所谓并行( p a r a l l e l i s m ) 是一种高速的处理机制，是事物在系统中同时发生的趋势。我们 把解题中具有可以同时进行运算或操作的特性，称为并行。t 生( p a r a l l e l i s m ) 口4 j 。并行计算 ( p a r a l l e lc o m p u t i n g ) 是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处 理器，各个处理器之间相互协同，并行地执行子任务，从而达到加快求解速度，或者提高 求解应用问题规模的目的【3 5 】【3 6 1 。所谓并行计算可分为时间上的并行和空间上的并行。 时 间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并 行计算科学中主要研究的是空间上的并行问题【3 7 1 。从程序和算法设计人员的角度来看，并 行计算又可分为数据并行和任务并行。一般来说，因为数据并行主要是将一个大任务化解 成相同的各个子任务，比任务并行要容易处理。并行计算同时使用多种计算资源解决计算 问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。 2 1 2 并行计算机系统的访存模型 要实现软件并行执行的目标，就必须为多个线程同时执行提供一个硬件平台。一般而 言，可以从两种不同的角度对计算机体系结构进行分类。第一种分类的依据是计算机在单 个时间点能够处理的指令流( 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 j ， 1 单指令流单数据流( s i n g l ei n t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ，s i s d ) 这是一类传统 的串行计算机，其硬件不支持任何形式的并行，所有指令都串行执行。在某个时钟周期内， c p u 只能处理一个数据流。 2 多指令流单数据流( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t e a m ，m i s d ) 这类机器采 用多个指令流同时对一个数据流进行处理的机制。但是在大多数情况下，多个指令流处理 多个数据流才是更加有效的处理方式。因此，m i s d 并行计算机一般只是作为一种理论模 型出现，而并没有投入到实际的应用中，更不用说大规模生产了。 3 单指令流多数据流( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t e a m ，s i m d ) ：它采用一个 指令流同时处理多个数据流。此类机器在数字信号处理、图像处理以及多媒体信息处理等 应用领域非常有效。最初的阵列处理机或者向量处理机等超级计算机都具备进行s i m d 处 妻塞墅皇奎兰堡圭竺壅生兰垡丝奎蔓：兰! 竺! 竺竺兰堡! 竺堑! 王兰墨蔓查 理的能力。而且时至今日，几乎所有的计算机也都以各种各样的指令集形式实现了s i m d 功能。 4 多指令流多数据流( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t e a m ，m i m d ) ：这类机 器能同时执行多个指令流，这些指令流分别对不同的数据流进行操作。m i m d 是目前最流 行的并行计算平台。现在已经普遍应用的多核计算平台就属于m i m d 范畴。 其中s i s d 是就我们常用的串行机。空间上的并行导致了s i m d 和m i m d 这两类并行 机的产生【j 引，常见的m i m d 类机器如图2 一l 所示。 m i m d 类机器 并行向量处理机 对称多处理机 大规模并行处理机 工作站机群 分布式共享存储处理机 图2 1 常见的五种m i m d 类机器 并行计算机的访存模型如图2 2 所示【3 5 。3 8 】。 m l d 均匀访存模型( u n i f o r mm e m o r ya c c e s s ，u m a ) 非均匀访存模型( n o n u n i f o r mm e m o r ya c c e s s ，n u m a ) 全高速缓存访存模型( c a c h e - o n l ym e m o r ya c c e s s ，c o m a ) 一致性高速缓存非均匀访存模型( c a c h ec o h e r e n t - n u m a ，c c j n u m a ) 非远程访存模型( n o - r e m o t em e m o r ya c c e s s ；n o r m a ) 图2 2 并行计算机的访存模型 在图2 2 中所示的各种访存模型特点如下： u m a 模型的特点是：物理存储器被所有节点共享：所有节点访问任意存储单元的时 间相同；发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；各节点的 c p u 可带有局部私有高速缓存：外围i 0 设备也可以共享，且每个节点有平等的访问权利。 n u m a 模型的特点是：物理存储器被所有节点共享，任意节点可以直接访问任意内存 模块；节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存 模块的3 倍以上；发生访存竞争时，仲裁策略对节点可能是不等价的；各节点的c p u 可带 有局部私有高速缓存( c a c h e ) ；外围i o 设备也可以共享，但对各节点是不等价的。 c o m a 模型的特点是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局 地址空间；利用分布的高速缓存目录d 进行远程高速缓存的访问；c o m a 中的高速缓存容 量一般都大于2 级高速缓存容量；使用c o m a 时，数据开始时可以任意分配，因为在运 9 南京邮电大学硕士研究生学位论文第2 章w i n d o w s 环境下的并行计算技术 行时它最终会被迁移到要用到它的地方。 c c n u m a 模型是n u m a 模型的一种类型。其特点是：内存相连接形成单一内存， 内存之间没有页面复制或数据复制，也没有软件消息传送；只有一个内存映象，存储 部件利用铜缆和某些智能硬件进行物理连接；不需要软件来保持多个数据拷贝的一致 性，也不需要软件来实现操作系统与应用系统的数据传输：单一操作系统和多个处理 器完全在硬件级实现管理。 n o r m a 模型的特点是：所有存储器都是私有的；绝大多数n o r m a 都不支持远程存 储器的访问；在d s m 中，n o r m a 就消失了。 2 1 3 进程和线程 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥 有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前 的活动，通过程序计数器的值和处理寄存器的内容来表示【3 9 1 1 4 0 1 。 进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部 出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念，所有多道程序设计 操作系统都建立在进程的基础上。 进程可表示成四元组( p ，c ，d ，s ) ，其中p 是程序代码，c 是进程的控制状态，d 是进 程的数据，s 是进程的执行状态。两个特征：资源特征，包括程序执行所必需的计算资源， 例如程序代码、内存地址空间、文件系统、i o 设备、程序计数器、寄存器、栈空间等执 行特征，包括在进程执行过程中动态改变的特征，例如指令路径( 即进程执行的指令序列) 、 进程的控制与执行状态等。一个进程具有五种状态。非存在状态：进程依赖的程序还没有 投入运行；就绪状态：进程由其父进程( 例如，操作系统的内核进程或s h e l l 进