（计算机软件与理论专业论文）基于软件内存事务的高性能服务器设计.pdf

摘要摘要本世纪初，摩尔定律的失效加速了多核处理器的问世和不断普及，硬件并行化的发展反过来也推动了工业界对软件并发性的研究。软件内存事务是用软件的方法对内存操作进行封装，以事务的原子性与隔离型来保证并行程序执行逻辑的一种方法。较之于传统上基于互斥锁的多线程编程方法，软件内存事务具有编程接口易用，不产生死锁等优点。软件内存事务主要可分为基于锁的实现和无锁的实现，本文分别详细介绍了两大类中的几个典型实现，并对它们各自的优缺点进行了分析和比较。经过研究我们发现，现实中的程序运行压力并不是恒定不变的，尤其对服务器程序而言，其处理压力往往会在短时内出现剧烈波动。我们还发现，能够使软件内存事务的性能达到最优化的参数往往取决于目标状态的运行时压力，如写入型事务占事务总数的比例，在内存地址上的访问竞争度等。在现有的软件内存事务的实现中普遍缺乏对运行时压力变化做出反应和调整的机制，于是我们提出了一种基于运行时压力检测和动态策略调整的软件内存事务实现：p a t i n y s t m 。p a - t i n y s t m 主要由压力探测前端，动态调整模块，t i n y s t m 主体和反馈信息处理后端四大部分组成。压力探测前端在事务进入执行前对事务执行速率变化进行检测，并相应地计算出当前系统的处理压力。反馈处理模块负责对一些事务执行以后才能获取的信息进行搜集和统计，例如事务执行平均时间，事务撤销率等。前后端的处理结果提供给动态调整模块用作动态调整的依据，动态调整模块又分为t i n y s t m 运行时参数调整子模块和内存分配策略调整子模块。前者根据运行时处理压力变化和访问地址特性对t i n y s t m 中的两个主要参数进行调整：而后者则根据多线程内存分配的压力变化和内存块大小的规律进行分配策略上的优化。这两个模块根据前后端模块得到的统计数据进行动态调整，以使p a t i n y s t m 的参数搭配和分配策略能够及时地适应运行时压力的变化。通过试验数据的对比我们可以看到，p a t i n y s t m 对运行时压力变化可以做出很快的反应，并通过动态调整参数和策略以适应压力的变化，通过这种方法，基于p a t i n y s t m 实现的服务器程序能够使自身的运行时性能达到并保持在最佳水平上。关键词：软件内存事务，并行计算，压力检测，动态调整a b s t r a c ta b s t r a c tw i t hm o o r e sl a wg o i n gi n v a l i de a r l yi n t h i sc e n t u r y , m u l t i - c o r ep r o c e s s o r sb e c a m ev i s i b l et ot h ei n d u s t r ya n dg o tm o r ea n dm o r ep o p u l a r i nr e t u r n ，t h ep a r a l l e l i s mt r e n di nh a r d w a r ei n d u s t r yt r i g g e r sm o r er e s e a r c hp o w e ri ns o f t w a r ep a r a l l e l i s m s o f t w a r et r a n s a c t i o n a lm e m o r y ( s t m ) i san e wm e c h a n i s mu s e dt ot a k et h ep l a c eo ft r a d i t i o n a ll o c k - b a s e ds y n c h r o n i z a t i o nm e t h o d s c o m p a r e dw i t hl o c k b a s es y n c h r o n i z a t i o n , s t mo f f e r sm o r ef l e x i b i l i t ya n ds c a l a b i l i t ya n ds i m p l i f i e sc o d ew r i t i n ga n dm a i n t e n a n c e t h e r ea r eg e n e r a l l yt w ot y p e so fs t mt o d a y ：l o c k - b a s e da n dl o c k - f r e e w e 1 1i n t r o d u c et y p i c a li m p l e m e n t a t i o n so fb o t ht y p e s ，a n dt h e ng i v ea n a l y s i so n l e i ra d v a n t a g e sa n dd i s a d v a n t a g e s w ef o u n dt h a t ，f o rr e a lw o r l da p p l i c a t i o n s ，t h ep r e s s u r ea r eu s u a l l yn o tp e r s i s t e n t e s p e c i a l l yf o rh i g hp e r f o r m a n c es e r v e r s ，t h ep r e s s u r ec o u l db ec h a n g i n gf a s ti nav e r ys h o r tt i m e w ea l s of o u n dt h ep e r f o r m a n c eo fs t mi m p l e m e n t a t i o nd e p e n d sh e a v i l yo l li t sw o r k l o a d ，a n dt h eb e s ts e t so fp a r a m e t e r sa n ds t r a t e g yv a r ya c r o s sd i f f e r e n tw o r k l o a d sa n de n v i r o n m e n t m o s to fc u r r e n t l ys t mi m p l e m e n t a t i o n sl a c kt h ea b i l i t yt oa d j u s tt h e i rp a r a m e t e r sa n ds t r a t e g i e sa c c o r d i n gt op r e s s u r ea n dc h a n g e s b a s e do nt h ea b o v eo b s e r v a t i o n s ，w ep r o p o s ean e wm e c h a n i s mo fs t mi m p l e m e n t a t i o n ：p a - t i n y s t m ，s h o r tf o rp r e s s u r ea w a r et i n y s t m p a t i n y s t mm a i n l yc o n s i s t so ff o u rm o d u l e s ，w h i c ha r ep r e s s u r ed e t e c t i o n( p d ) ，d y n a m i ct u n i n g ( d t ) ，t i n y s t mm a i nb o d y ( m b ) a n df e e d b a c k ( f b ) p di sr e s p o n s i b l ef o rc o l l e c t i n gt r a n s a c t i o nr e l a t e dd a t ab e f o r eat r a n s a c t i o ng e t si n t oe x e c u t i o ns t a t u sa n dc a l c u l a t i n gc o r r e s p o n d i n gr u n t i m ep r e s s u r eo nt h ef l y f bi sr e s p o n s i b l ef o rc o l l e c t i n gi n f o r m a t i o nt h a t so n l ya v a i l a b l ea f t e rat r a n s a c t i o nh a sf i n i s h e de x e c u t i o na n dg i v e ss t a t i s t i c sr e s u l t sa c c o r d i n g l y , s u c h 嬲a v e r a g ee x e c u t i o nt i m ea n dt r a n s a c t i o na b o r tr a t e t h eo u t p u t so fp da n df ba r ep r o v i d e dt od tm o d u l e 弱b a s i sf o rd y n a m i ct u n i n g d tc o n t a i n st w os u bm o d u l e si t s e l f t i n y s t mp a r a m e t e rt u n i n g ( t p t ) a n dm e m o r ya l l o c a t i o ns t r a t e g yt u n i n g ( m a s t ) t p tc o n s i d e r st h ep r e s s u r ec h a n g e sa n dm e m o r ya c c e s sp a t t e ma l t o g e t h e ra n dt u n e st i n y s t mp a r a m e t e r sa c c o r d i n g l y o nt h eo t h e rh a n d ，m a s to p t i m i z e sd y n a m i cm e m o r ya l l o c a t i o ns t r a t e g yi i一垒垒! 塑! ! a c c o r d i n gt om u l t i t h r e a d e dm e m o r yr e q u e s tp a t t e r na n dc o n t e n t i o nc h a n g e su n d e rm u l t i t h r e a d e de n v i r o n m e n t t p ta n dm a s ta r ek e p tu p d a t e db yt h en e w e s to u t p u tf r o mp da n df b ，s oa st ok e e pt h er u n t i m ep a r a m e t e r sa n ds t r a t e g yg e tt u n e dw i t hp r e s s u r ec h a n g e si nat i m e l ym a n n e r t h r o u g ht h ee v a l u a t i o nr e s u l t s ，w ec a l ls e et h a tp a t m y s t mr e s p o n d sv e r yq u i c k l yw i t hp r e s s u r ec h a n g e s a n dw i t ht h ed y n a m i ct u n i n ga b i l i t y , o b rp a t i n y s t mb a s e ds e r v e ra p p l i c a t i o nc a nw o r kv e r ya c r o s sd i f f e r e n tw o r k l o a d s k e y w o r d s ：s o f t w a r et r a n s a c t i o n a lm e m o r y , p a r a l l e lc o m p u t i n g , p r e s s u r ed e t e c t i o n ,d y n a m i ct u n i n gl l i独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。签名：鱼遮日期：二口口7 年6 月1 日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)签名：鱼缝第一章绪论第一章绪论软件内存事务( s o f t w a r et r a n s a c t i o n a lm e m o r y , s t m ) 作为新兴的并行计算研究方向，最近几年正越来越多地得到研究人员和机构的重视，随着摩尔定律的失效，网格计算，云计算等概念的推出，高效的并行处理机制将在未来几年得到越来越快速的发展，本文将从并行计算的发展之路入手，着重介绍软件内存事务在未来所能扮演的角色和地位。1 1并行计算的发展从2 0 世纪4 0 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件( 特别是编译器与操作系统) 、应用软件，最后随着问题求解环境的发展而达到顶峰。1 1 1 微处理器的发展史第一块微处理器芯片i n t d4 0 0 4 于1 9 7 1 年诞生。4 0 0 4 是一个4 位的处理器，大约有2 3 0 0 个晶体管，时钟频率刚刚超过1 0 0 k h z 。4 0 0 4 主要应用于计算机。2 0 0 1年是微处理器诞生3 0 周年纪念。现代高端微处理器包含有上亿只晶体管，时钟频率超过3 g h z ，因此成为超级计算机系统和强劲的客户服务器系统的组成部分。这些系统如今充满了因特网【3 1 。表1 1 微处理器飞速发展的各个l o 年1 9 7 0 1 9 8 01 9 8 0 1 9 9 019 9 6 - - 2 0 0 0晶体管数量2 k ，1 0 0 k1 0 0k ，lmlm 1 0 0m时钟频率0 1m h z 3m h z3m h z 3 0 m h z3 0 m h z lg h z指令数时钟周期o 1i p c0 1i p c 旬9i p c0 9i p c 1 9i p c微处理器3 0 年的发展历程体现了计算机工业中技术发展不寻常的事实。微处理器的发展与著名的摩尔定律十分吻合。在以前的3 0 多年时间罩，微处理器芯片上的晶体管数量增加了4 个数量级。在同一时期，微处理器的性能增加了5 个数电子科技大学硕+ 学位论文量级。在过去的2 0 多年时间里，微处理器性能每1 8 个月就翻一番，或每l o 年就成为原来的一百倍，这样显著的发展速度是其他工业所不能相提并论的。在这3 0年的每一个l o 年中，微处理器在计算机工业最关键的技术中一直起着重要的作用。在第一个十年中，4 位微处理器的问世很快导致8 位微处理器的出现。这些数据宽度较小的微处理器内部都嵌入一个微控制器，并为洗衣机，电梯和喷气式发动机提供大量的嵌入式应用。同时8 位微处理器也成为新型计算机平台，即个人计算机( p e r s o n a lc o m p u t e r ) 的核心部分，同时成为p c 时代的先驱。2 0 世纪8 0 年代的1 0 年是3 2 位微处理器体系结构与微体系结构等技术的发展时期。指令集设计问题成为大学与工业界研究的焦点。人们意识到指令集体系结构与微体系结构有助于硬件的有效实现，并能在编译器的优化过程中起到很好的杠杆作用。指令流水以及快速c a c h e 缓存成为标准的微体系结构技术。于是，基于3 2 位微处理器的科研和工程工作站问世命他们具有强大的计算能力。这些工作站又一次成为研制下一代更高性能微处理器的更强有力的工具。在2 0 世纪9 0 年代，微处理器成为计算机中最强大、最受欢迎的组件。最快的的微处理器时钟主频竟然已经超过了最快的超级计算机的主频。此时，个人计算机和工作站已经十分普遍，成为人们生产和通信必不可少的工具，但人们进一步渴望能够掌握更为强大的微体系结构技术，这些技术能够将微处理器的所有性能完全发挥出来。用于获取极高主频性能的深度流水线技术和单周期多指令执行技术变得大受欢迎。这时，出现了指令的乱序执行和分支预测技术，它们可用来避免及减少流水线的停顿周期数。在微处理器时代的第三个l o 年快要结束的时候，几乎所有形势的计算平台，从个人手持设备、主流桌面系统、服务器到最强大的并行集群计算机都是基于微处理器而构建的。现在我们正处于微处理器时代的第四个1 0 年，许多领域都有大量的创新出现。当前大家关注的焦点技术已经从指令级并行扩展为包括线程级并行和存储级并行在内的技术。随着技术的进步，这些都将在单芯片上完成。1 1 2 摩尔定律计算机第一定律摩尔定律诞生于1 9 6 5 年，当时戈登摩尔( g o r d o nm o o r e )准备一个关于计算机存储器发展趋势的报告。他整理了一份观察资料。在他开始绘制数据时，发现了一个惊人的趋势。每个新芯片大体上包含其前任两倍的容量，每个芯片的产生都是在前一个芯片产生后的1 8 2 4 个月内。如果这个趋势继续的2第一章绪论话，计算能力相对于时间周期将呈指数式的上升。m o o r e 的观察资料，就是现在所谓的m o o r e 定律，所阐述的趋势一直延续至近几年，且仍不同寻常地准确。人们还发现这不光适用于对存储器芯片的描述，也精确地说明了处理机能力和磁盘驱动器存储容量的发展。该定律成为许多工业对于性能预测的基础。如果摩尔定律没有被打破而一直适用至今，那么对并行计算的研究也许并不会像今天这样急迫。早在i n t e l 如日中天的奔腾c p u 时代，人们就已经在思考这样的一些问题：这样c p u 计算能力的高速稳定发展能够一直持续下去吗? 芯片散热问题会不会成为阻挡芯片速度进一步提高的最大障碍? 经过业界的分析与争论，那时候的基本共识是：摩尔定律还能再适用l o 年左右。但是现实告诉人们，这一切将来得更早。2 0 0 4 年，标志性的i n t e lp 44 g h z 芯片的研制计划取消，几乎肯定了“摩尔定律”神话的终结，也预示着一个崭新时代的来临。i n t e l 前总裁安迪格鲁夫有一句名言：“只有偏执狂才能生存。然而，英特尔在2 0 0 4 年的所作所为显然脱离了“偏执的航道，随着一系列芯片计划的推迟或取消，人们对英特尔顶礼膜拜的虔诚变成了些许的狐疑和质问。特别是标志性的p 44 g h z 芯片的研制计划取消，几乎暗示着“摩尔定律”神话的终结，也预示着一个崭新时代的来临。1 1 3 多处理器与多核的出现与发展摩尔定律的失效让微处理器的发展不得不另寻出路。取消p 44 0g h z 芯片研制计划后，英特尔掉头投入多核( m u l t i c o r e ) 处理器的“怀抱”。多核处理器的基本思想是将多个处理器置入单一芯片中，如此一来，多个处理器能以较缓慢的速度运转，既能减少运转消耗的能量，又能减少运转生成的热量。此外，集多个处理器的能力，可提供比单一处理芯片更强大的处理性能。多核技术的开发源于工程师们认识到，仅仅提高单核芯片的速度会产生过多热量且无法带来相应的性能改善，先前的处理器产品就是如此。他们认识到，在先前产品中以那种速率，处理器产生的热量很快会超过太阳表面。即便是没有热量问题，其性价比也令人难以接受，速度稍快的处理器价格要高很多。英特尔工程师们开发了多核芯片，使之满足“横向扩展”( 而非“纵向扩充 ) 方法，从而提高性能。该架构实现了“分治法”战略。通过划分任务，线程应用能够充分利用多个执行内核，并可在特定的时间内执行更多任务。多核处理器是单枚芯片( 也称为“硅核”) ，能够直接插入单一的处理器插槽电子科技大学硕七学位论文中，但操作系统会利用所有相关的资源，将它的每个执行内核作为分立的逻辑处理器。通过在两个执行内核之间划分任务，多核处理器可在特定的时钟周期内执行更多任务。多核架构能够使目前的软件更出色地运行，并创建一个促进未来的软件编写更趋完善的架构。尽管认真的软件厂商还在探索全新的软件并发处理模式，但是，随着向多核处理器的移植，现有软件无需被修改就可支持多核平台。操作系统专为充分利用多个处理器而设计，且无需修改就可运行。为了充分利用多核技术，应用开发人员需要在程序设计中融入更多思路，但设计流程与目前对称多处理( s m p ) 系统的设计流程相同，并且现有的单线程应用也将继续运行。现在，得益于线程技术的应用在多核处理器上运行时将显示出卓越的性能可扩充性。此类软件包括多媒体应用( 内容创建、编辑，以及本地和数据流回放) 、工程和其他技术计算应用以及诸如应用服务器和数据库等中间层与后层服务器应用。多核技术能够使服务器并行处理任务，而在以前，这可能需要使用多个处理器，多核处理器系统更易于扩充，并且能够在更纤巧的外形中融入更强大的处理性能，这种外形所用的功耗更低、计算功耗产生的热量更少。多核技术是处理器发展的必然。近2 0 年来，推动微处理器性能不断提高的因素主要有两个：半导体工艺技术的飞速进步和体系结构的不断发展。半导体工艺技术的每一次进步都为微处理器体系结构的研究提出了新的问题，开辟了新的领域；体系结构的进展又在半导体工艺技术发展的基础上进一步提高了微处理器的性能。这两个因素是相互影响，相互促进的。一般说来，工艺和电路技术的发展使得处理器性能提高约2 0 倍，体系结构的发展使得处理器性能提高约4 倍，编译技术的发展使得处理器性能提高约1 4 倍。但是今天，这种规律性的东西却很难维持。多核的出现是技术发展和应用需求的必然产物。总之，单芯片多处理器通过在一个芯片上集成多个微处理器核心来提高程序的并行性。每个微处理器核心实质上都是一个相对简单的单线程微处理器或者比较简单的多线程微处理器，这样多个微处理器核心就可以并行地执行程序代码，因而具有了较高的线程级并行性。由于c m p 采用了相对简单的微处理器作为处理器核心，使得c m p 具有高主频、设计和验证周期短、控制逻辑简单、扩展性好、易于实现、功耗低、通信延迟低等优点。此外，c m p 还能充分利用不同应用的指令级并行和线程级并行，具有较高线程级并行性的应用如商业应用等可以很好地利用这种结构来提高性能。目前单芯片多处理器已经成为处理器体系结构发展的4第一章绪论一个重要趋势。1 1 4 多核的出现对软件行业的挑战将一个双核甚至是四核处理器装到pc 的主板上，即使不做任何软件改动，也能产生额外的吞吐能力，这是因为操作系统负责为各个核心安排具体的任务，哪个核心有处理能力可用，它就会自动开始新的线程。对于普通用户，更多的处理核心仅仅意味着更好的性能。不过，随着处理核心增加到8 个乃至1 6 个，在常规的程序设计模型下所看到的多核心的好处就开始减少。无论你在什么时候同时运行w i n d o w s 和几个应用程序，总有上百个线程处于活动状态，但其中的大多数并未做什么工作，因此，并行运行多个线程实际上并不能显著提升性能。例如，要想充分发挥8 核或1 6 核处理器的优势，就需要对一个游戏引擎进行相当大的重写，同时还需要一个独立的图形协处理芯片。让未来的多核心处理器充分发挥性能并不像我们过去想的那样简单。伯克利分校的研究报告从这样一个前提开始：多核心芯片的开发不是由技术研究，而是由传统单核心处理器在设计的实用效率和经济上的限制推动的。随着芯片几何尺寸的缩小，以及它们的复杂性和时钟频率的提升，功耗逐渐成为一个大问题，此外，还出现了其他一些难以解决的问题( 比如由宇宙射线造成的软错误，以及由布线造成的信号延迟影响) ，这些都使得芯片的开发和调试缓慢而又困难。这也是为什么在很长一段时间里，处理器的性能都是每1 8 个月提高一倍，而在过去的五年中，处理器的性能收益呈现递减态势的原因。由于单核处理器的开发受阻，如果以目前的开发速度，单核处理器的性能每5 年才能提升一倍。1 1 5 并行计算的软件方法多核的出现并没有马上带来应用程序的性能提高，因为软件编写者并没有立即准备好为多核处理器编写一套结构完全不同的应用程序，而且要编写正确的并行程序相较之传统的单线程串行执行程序要复杂得多，需要掌握的知识和技能也要求更宽泛。在i t 领域，多年以来的发展趋势都是硬件领先于软件，新的硬件出现促进了计算能力要求更高的软件的发展需求，进而反过来刺激高性能硬件的消费需求。但是自摩尔定律失效的那一刻开始，这种趋势便默默地被打破了，c p u频率不再无止境的增长，硬件的速度也遇到了瓶颈，以往硬件带动软件的发展模式终于发生了变化。而随着多核处理器的不断普及，具有并行化处理能力的软件电子科技大学硕+ 学位论文发展需求则变得越来越迫切。传统的单线程串行化处理软件在多核处理器上不再有性能上的提高，相反，在部分场合下性能较之单核处理器时期还有下降，因此软件的并行化处理能力越来越被放在重要位置。多年以来，并行计算的发展集中在处理器的并行处理上，无论是多c p u 结构还是多核芯片的出现，都是围绕提高处理器的并行执行流进行的。而除了硬件方面的发展，并行计算在软件领域的发展也不可忽视。从另一个角度上看，并行计算软件的发展其实早在微处理器发展之初就已经开始，并伴随着微处理器的发展而一同发展到现在。在传统的u n i x 服务器领域，由于多处理器的使用早已深入人心，编程人员也已习惯于使用多线程并行处理方法进行开发。而在x 8 6 领域，由于单芯片处理能力的不断提高，系统上软件的性能随着来自i n t e l 和a m d 处理器速度越来越快而不断提高，开发者只需对现有软件程序作轻微改动就能坐观其性能在随着硬件性能的上升而不断提升，因此多年来x 8 6 应用程序开发者一直停留在单线程世界，生产所谓的“顺序软件 。随着w i n d o w s 服务器不断的普及与多核并行设计理念的出现，软件世界不得不直面并发性( 将单个任务拆分成多个小块以便分别处理之后再重新组合的能力) 问题，也进一步推动了软件行业对并行化应用发展道路的思考。这其中有两种并行方法的研究得到了比较多的重视：1 1 5 10 p e n m po p e n m p 是一种工业标准的a p i 设计规范，是由s u nm i e r o s y s t e m s u p , i b m 和i n t e l 等多家顶级计算机厂商和软件开发商联手推出的。其目的在于为软件开发人员提供一种通用的规范，使其可以很方便地设计新并行应用程序或修改及并行化现有串行应用程序，从而利用配备多处理器计算系统的共享内存。可移植性也是o p e n m p 的主要目标之一。使用o p e n m p 开发的并行应用程序源代码可由支持o p e n m p 的任何编译器编译且编译好的二进制代码可在目标硬件平台上运行以获得出色的并行性。最流行的本地编程语言f o r t r a n 和c c h 都支持o p e n m p 。o p e n m p的结构允许程序员指定并行区域、同步和数据作用域属性。它还支持用于指定运行时配置的运行时环境变量。例如，环境变量o m pn u mt h r e a d s 指定了程序运行时所使用的工作线程数量。由于o p e n m p 编程模型专用于单一进程，因此其可伸缩性最终要受到一台计算机中处理器( 线程) 数的限制。此外，o p e n m p 的可伸缩性还会受编程逻辑复杂程度和编程风格的限制。当前o p e n m p 的语义尚不够灵活，无法处理某些应用程序。例如当前的规范仅允许在并行区域内创建有限的动态线程。o p e n m p 语言委员6第一章绪论会( 其成员包括s u nm i c r o s y s t e m s 及许多其他厂商) 正致力于确定一种动态任务队列结构，以解除这一重要的局限性。编写o p e n m p 应用程序时可能遇到的其他更为普遍的问题包括避免多线程中出现资源竞争( c o n t e n t i o n ) ，在并发的工作线程之间实现更好的负载均衡。1 1 5 ，2m p i ( m e s s a g ep a s s i n gi n t e r f a c e )m p i 是一种工业标准的规范，专为在多处理器计算机和计算机集群上获得高性能计算而设计，该标准是由大计算机供应商和软件开发商共同设计的。有多种来自不同研究机构和厂商的实现，其中最流行的一种就是m p i c h ，m p i c h 常用作为特定平台或互连而优化的实现的编码基础。m p i 为并行应用程序提供了一种分布式的内存编程模型。尽管整个m p i a p i 集相对较大，其中包含超过3 0 0 个例程，但在编写许多m p i 应用程序时，需要使用的基本例程都不会超过十几个。在m p i c h设计中，整个a p i 集都是在一个低层设备互连例程的小型核心集之上实现并构建的。这一设计体系结构带来了更好的跨不同平台可移植性。惟一的需求就是重新处理设备互连例程的小型核心集，以为新平台或互连移植、优化m p i c h 。m p i 实现依然在不断发展。m p i 1 支持一些关键特性，如p 2 p 及与通信设备的集群消息通信。一条消息中可包含基本数据类型或派生( 用户定义的) 数据类型的m p i 数据。消息数据内容可以是压缩格式，也可以是非压缩格式。另外，它还支持互连拓扑。m p i 2 则提供许多高级通信特性，如远程内存访问和单端通信等。它还支持动态进程创建、管理和并行i o 处理能力。，。总体而言，m p i 为计算机集群上的并行应用程序提供了一个出色的解决方案。但对于许多开发人员来说，m p i 也是一种困难的编程模型。因为m p i 的通信延迟时间较长，所以必须合理分割程序的核心逻辑，以使分布成本更为合理。分析及划分应用程序问题并将问题映射到分布式进程集合中绝对不是一项可靠直觉完成的任务。因为许多m p i 进程之间的交互作用都相当复杂，因此即便选用了恰当的工具，调试并调整运行在大量节点上的m p i 应用程序也极具挑战性。m p i 例程实现的质量可能会带来一些额外的软件开发挑战。m p i 的性能取决于底层硬件平台和互连。在某些极端的情况下，m p i 应用程序的性能可能会受到繁重的互连流的影响。另外一个严重的问题就是大规模m p i 应用程序的可靠性。对干许多m p i 实现而言，只要单一计算节点发生故障，无法正确响应，程序就会停止工作。不幸的是，当m p i 应用程序在数千个计算节点上长期运行时，故障率即会变得不容忽视。7电子科技大学硕士学位论文1 1 5 3网格计算( g r i dc o m p u t i n g )网格计算是一个非常重要的技术发展方向，也是并行计算领域的一部分。某些欧洲国家认为网格计算是自i n t c r n e t 之后的又一信息技术改革新浪潮，并在技术研究方面投入了大量资源。无论如何，网格计算依然处于新生阶段，我们不能确定它将走向何处。上世纪年代中期，p c 开始拥有声卡，“多媒体”成为最时髦的词，当时许多人都在讨论未来的多媒体技术。当时几乎不可能有人想像出今天会出现i p o d 这样的先进产品。这里只讨论我们所了解的今日网格计算技术的基本内容。首先给出一条简单的定义，即网格计算是使用实用工具交付机制对计算资源的虚拟化。网格计算将使i n t e m e t 模式从被动地共享信息转变为主动地共享计算资源。计算能力仅仅是计算资源中的一种并且可像货币一样流通。网格计算环境旨在为资源目录和探索、安全、计算与监控提供一种集成的服务环境。网格计算中的一个核心组件就是d r m ( d i s t r i b u t e dr e s o u r c em a n a g e r ) 。d r m 有一个主进程端1 2 1 监督程序，用于排定并分派任务队列中提文的任务。主进程端口监控程序不断监控执行节点的状态，以向最恰当的执行节点分派任务。d r m 还有一个管理模块，可管理系统配置、统计及资源使用策略。前文已经提到，网格计算如今仍然处于新兴阶段，依然没有出现一种健壮g r i d环境的真正引人注目的软件基础结构和工具。g l o b u st o o l k i t 是g l o b u s 初次努力的优秀成果，使用它可为网格计算启用软件。g l o b u st o o l k i t 是一个开源软件，已被人们广泛采用。它包含多种多样的软件组件，从资源监控和探索到安全性一应俱全。然而，这一软件系统对于许多用户来说都过于复杂了。在网络环境上构建及部署工具包软件不是一项简单的任务。此外，其设计规范和软件更改频繁，这也会使现有资本很快过时。网格计算是与s o a 紧密相关的。网格计算的主要目标之一就是提供计算资源的实用服务。确实，目前的趋势是将网格计算并入w e bs e r v i c e 。网格计算可利用许多重要的w e bs e r v i c e 基础结构并进一步以其为基础进行构建。这里有一个重要的问题，即如何从w e bs e r v i c e 和g r i d 的角度排列不同的利害关系，从而发展w e bs e r v i c e 规范。总体来说网格计算的最大挑战就是创建一个统一的工业标准及设计规范集合并且可为绝大多数人们和组织所接受1 1 5 4超长指令字( v e r yl o n gi n s t r u c t i o nw o r d ，v l i w )超长指令字( v e ql o n gi n s t r u c t i o nw o r d ，v l i w ) ：v l i w ( 超长指令字) 体系结构是美国m u l t i f l o w 和c y d r o m e 公司于2 0 世纪8 0 年代设计的体系结构，e p i c 体系结构就是从v l i w 中衍生出来的【4 1 。v l 州的基本思路是：处理器在一个长指令字第一章绪论中赋予编译程序控制所有功能单元的能力，使得编译程序能够精确地调度在何处执行每个操作、每个寄存器存储器读和每个转移操作。实际上，编译程序创立每个程序的执行记录，计算机则反演该记录。在早期的v l 州计算机中，如果编译程序出错，计算机将产生错误的结果，计算机没有逻辑来检验是否以正确的次序来读寄存器、是否重复使用资源。v l i w 类计算机在传统上被设计成没有高速缓存，主要处理反复循环、向量化的代码。这些限制意味着内存延迟是固定的，转移方向是在编译时就能预测的。由于在v l 州体系结构中指令并行性和数据移动完全是在编译时规定的，处理器只需简单执行编译程序所产生的记录，因而大大简化了运行时资源的调度。v l m 设计者希望通过开发出能够充分利用v l i w 特点的编译，大大缩短程序的指令长度，因而也缩短v l i w 目标程序的执行时间。但是v l i w 最大的局限性恰好就在于编译器上，并不是所有的程序都能被很好地被编译器分拆调度到不同的处理元件上平衡执行，或者说一个没有开发出一个比较完美的编译器能够真正将v l i w 的优势应用于普通可执行程序上。此外，v l r w 硬件与编译器高度耦合的特点也使得其发展之路处处受限，二进制兼容的问题得不到很好的解决。1 2内存事务内存事务又称事务性内存( t r a n s a c t i o n a lm e m o r y ) ，是一种可以极大简化并行编程相关工作的方法。在内存事务的应用中，程序员将可能访问共享内存空间的关键逻辑段划分出来，作为一个内存事务，一个典型的内存事务由一系列内存操作组成，根据事务的特点，一次内存事务要么全部执行完成( 提交) ，要么全部无效( 取消) 。事务性内存系统需要为操作的原子性和隔离性提供保证，原子性意味着一次内存事务要么全部执行，要么全部无效。而隔离型则确保在当前事务提交之前，程序的其他部分和代码无法获知其状态，即中间不稳定态。虽然事务的定义提供了串行化的抽象概念，似乎在系统中事务都是排队串行化处理的，但在实际运行中完全可以对其执行顺序进行优化。比如可以在保证事务原子性和隔离型的前提下，对多个事务并行化执行。程序员可以从事务性内存的机制下获益，因为事务性内存机制中保证了内存操作的原子性，程序员不再需要考虑对关键区访问失败与否的问题，另外，内存操作是可组合性的( c o m p o s t a b l e ) ，并且不存在死锁和优先级反转的问题，因此程序员可以在事务性内存之上自由地创建自己的多线程程序库，而不必担心过去那些在多线程程序中臭名昭著的问题。9电子科技大学硕士学位论文以上是事务性内存的概念性描述，从上面我们可以看出，事务性内存的主要优势在于其为程序编写所提供的便捷性，以及可伸缩，可扩展性。事务性内存概念的提出距今已经有几十年的时间，到今天事务性内存的发展主要出现了两大分支：硬件实现的事务性内存与软件实现的事务性内存。1 2 1 硬件事务性内存( h a r d w a r et r a n s a c tio n aim e m o r y ，h t m )由上述所知，一个事务性内存系统必须实现以下这些需求：( 1 ) 事务提交前的逻辑隔离；( 2 ) 并行事务间的冲突检测；( 3 ) 共享内存的原子化提交操作：( 4 ) 在监测到冲突发生时进行回滚。检测冲突需要系统对事务执行时的读写内存区域进行跟踪。在写操作事务与读操作事务的作用内存区域存在交集时，资源竞争冲突就可能发生。h t m 使用硬件方法对这种冲突检测进行支持，相比较于s t m 实现，h t m具有开销更小，对上层软件透明的优点。实现h t m 的硬件系统使用具有推测工作机制的缓冲区，并在缓存中跟踪读写操作，在c i v i ? 系统中，缓存大小足够支持用于存储大部分应用程序所需要的内存事务信息，并且使用简单的虚拟化技术就可以处理缓存溢出所带来的风险，在冲突检测方面，h t m 可以利用缓存一致性协议。当系统因为缓存未命中而在的c p u之间传递消息时，我们可以探测到触发冲突的读写操作来源。多方的仿真研究表明，这种h t m 实现可以允许并行程序在使用粒度很粗的内存事务时，也能得到性能很高的同步互斥操作，并且仅带来很小的额外开销。h t m 与操作系统有着密不可分的关系，我们将简要描述在操作系统实现中使用h t m 来达到避免死锁和提高效率的办法。现代操作系统的一个重要任务是对c p u 进行合理调度，以达到和最大可能地利用硬件的并行资源优势。操作系统将重要任务分派到交替执行的多个内核线程中，这些任务包括网络数据包的收发，建立和断开连接，以及对页面进行换入换出操作等。在一个c p u 核上可能运行着一个或多个内核线程，而内核线程都是直接被操作系统任务调度器调入c p u 执行的。如果我们在操作系统内采取激进的并行策略，那么就可以在不同的内核线程之间，甚至与内核本身共享数据结构，看似无关的任务也可以造成复杂的同步开销，有些甚至是在程序编写初期无法预见或很难发现的。为了能够保持内核运行的j 下确性，我们需要在访问这些数据结构时加入并发控制的代码，隐式地将访问操作串行化，最普遍的做法是加入互斥锁。这样造成的结果就是，即使外设资源允许多通路并行访问，但操作系统为了保持本身数据结构的一致性和j 下确性，还1 0第一章绪论是不得不将对访问串行化，造成性能的下降，外设资源得不到充分的利用。此外，在这种互斥锁的实现方法中，为了保证操作系统内核的高效性，常常要求程序编写者必须要能够将锁的粒度控制得很细，这样造成的后果往往就是死锁和优先级翻转的增多，并且增加了代码维护的难度。在份关于l i n u x 源代码的b u g 统计分析报告中，1 0 2 5 个b u g 中的3 4 6 个是与同步相关的，比例达到3 4 ，另有份研究发现l i n u x2 5 的内核代码中存在着4 个已证实的和8 个未证实的死锁【l5 1 。在l i n u x 的源代码文件中，经常可以看到为了防止死锁而进行的互斥锁的结构阐述，内核的组件必须互相清楚对方内部实现时所使用的锁调用顺序，否则互相调用时就容易产生死锁。使用h t m 的方法可以使操作系统免于这种锁顺序的设计问题，因为在不发生访问冲突时，内存事务的方法可以将多个访问操作并行化起来，并对程序编写者是透明的。互斥锁的实现中，由于锁的层次结构设计一般从功能模块设计时，甚至系统总体设计时就已经确定，如果在代码维护时去修改其结构，增加或减少锁的数量，改变锁的粒度，则带来的连锁反应可能会使代价变得最终不可控。在这点上，使用h t m 的方法可以很好地避免类似问题的出现，从而为程序编写带来了更高的可扩展性和可维护性。用硬件的方法来实现事务性内存，优势在于实现效率更高，与操作系统紧密结合起来，通过操作系统提供的实现和a p i 接口，使其存在对应用程序编写者透明。h t m 的劣势在于：( 1 ) 不仅对硬件设计有较高的要求，也要求软件编写者对h t m 的概念和使用有一定了解，如果要实现高性能的h t m ，需要投入巨大的人力和资源对现有芯片体系结构进行改造；( 2 ) 兼容性，在h t m 基础上实现的操作系统要想利用h t m 提供的便捷与性能优势，必须与硬件提供商紧密协作，否则兼容性问题无法得到解决。1 2 2 软件内存事务( s o f t w a r et r a n s a c tio n aim e m o r y ，s t m )相对于用硬件方法实现的h t m ，软件内存事务的概念可以很容易得出：使用软件的方法实现事务内存，将对内存的读写操作封装成独立的事务，保证其原子性和隔离性【6 】。有关软件内存事务的具体介绍我们将会在下一章中重点讨论。1 2 3 混合型内存事务( h y b ridt r a n s a c tio n aim e m o r y ，h y t m )i n t d 与密歇根大学的研究人员于2