（计算机软件与理论专业论文）并行程序设计模型若干问题研究.pdf

中国科学技术大学博士学位论文 中文摘要 摘要 长期以来，并行计算机的计算能力持续遵循m o o r e 定律快速增长，新的体系 结构不断出现，但并行计算却一直未能真正成为计算的主流。人们逐渐认识到仅 仅设计和建造并行硬件是不够的，并行计算的真正挑战在于支持并行程序设计的 软件。现有并行程序设计系统普遍存在抽象层次较低、程序开发困难的问题。并 行程序与相应并行算法描述相比往往要复杂得多，导致并行程序的可读性和可扩 展性较差。同时，并行体系结构的多样性也造成了并行程序设计模型和软件系统 的多样性，限制了并行应用程序的通用性和灵活性。因此，如何提高并行程序设 计模型和相应并行程序设计系统的抽象层次，支持通用并行数据结构和算法的开 发，并最终提高并行程序开发的效率，成为并行计算中需要解决的关键问题。本 文针对上述问题开展了以下研究工作： ( 1 ) 消息传递并行程序设计模型研究 针对现有消息传递系统抽象层次过低的问题，提出新的泛型面向对象消息传 递接口一g 0 0 m p i ，创建了完整的数据划分、序列化和传输框架，有效地解决了 任意用户自定义、复杂、动态数据结构和抽象数据类型的消息传递问题；设计和 实现了基于策略的多功能通信端口，提供流式接口和消息类型检查机制，支持基 于消息传递的并行算法到相应并行程序的快速和直观地映射；利用g o o m p i 实现 了若干典型的基于消息传递的并行算法，并与相应的m p i 实现进行了对比。 ( 2 ) 共享存储并行程序设计模型研究 针对现有多线程程序设计系统的不足之处，提出新的并行多线程接口一 p m t ，在不依赖于语言扩展和专用编译器的前提下，实现直接面向多线程并行程 序设计的支持，包括并行任务的管理和线程池机制、各种并行执行区域、并行循 环的静态和动态调度、各种支持并行访问的共享数据结构等；利用p m t 对c + + 标 准模板库中的若干数据结构和算法进行了并行化。 ( 3 ) 锁无关的投机并行多线程研究 讨论了未来的多核体系结构上基于事务性执行的投机并行多线程技术一 s p t t x 。由于目前尚没有支持投机并行多线程的硬件产品，因此提出基于软件 拘s p t t x 功能性模拟算法和正确性验证算法，并在此基础上，提出利用二进制 代码动态插桩技术，设计并实现了基于软件的s p t t x 功能性模拟器和正确性验 证器，有效支持了对s p t t x 技术的进一步研究。 ( 4 ) 统一架构并行程序设计模型研究 中文摘要 中国科学技术大学博士学位论文 针对新型混合式并行体系结构，提出融合了消息传递和共享存储模型的 新的统一架构并行程序设计模型：基于g o o m p i 和p m t ，实现了原型系统一 p a r a d e ，支持统一架构的分布式共享数据，并使用作用域行为对程序的数据共 享进化优化。 ( 5 ) 面向方面并行程序设计研究 研究了新的面向方面程序设计技术在并行程序设计领域的应用。提出泛型面 向方面程序设计框架一a o p 十+ ，并在此基础上尝试对数据结构添加并行访问支 持和对串行算法进行面向方面的并行化改造。 本文的主要贡献与创新点有： ( 1 ) 应用新的程序设计技术提高并行程序的抽象层次 针对传统并行程序抽象层次过低的问题，本文将现代面向对象、泛型和面向 方面程序设计技术综合应用于并行程序设计领域，在不引入任何抽象开销的前提 下，显著改善了并行程序的可读性、可维护性和通用性，提高了其模块化程度。 f 2 ) 针对不同的并行体系结构，分别提出高抽象层次的并行程序设计模型 提出新的泛型面向对象消息传递接口一g o o m p i ，成功解决了复杂动态数据 结构的划分、序列化和传输问题；提出了基于策略的多功能通信端口，支持一致 的流式接口；提出新的并行多线程接口一p m t ，在程序库一级实现了并行任务的 管理、各种并行区域、循环的静态和动态调度和各种共享数据结构。 ( 3 ) 提出统一架构的并行程序设计模型 提出统一架构的并行程序设计模型，融合了消息传递模型和共享存储模型； 实现了统一架构的分布式共享数据，利用作用域行为支持对特定对象和特定作用 域的数据共享优化，有效简化了混合式体系结构上并行程序的开发。 关键词：并行计算，并行程序设计模型， 构并行程序设计模型，事务性内存， 泛型程序设计，面向方面程序设计 l l 消息传递模型，共享存储模型，统一架 投机并行多线程，面向对象程序设计， 中国科学技术大学博士学位论文英文摘要 a b s t r a c t t h ec o m p u t a t i o np o w e ro fp a r a l l e lc o m p u t e r sh a sb e e ni n c r e a s e de x p o n e n t i a l l ya c c o r d i n gt om o o r e sl a w ，a n dn e wp a r a l l e la r c h i t e c t u r e sc o n t i g o u s l ye m e r g e h o w e v e r ，p a r a l l e l c o m p u t i n gh a sn e v e rb e e na b l et ob e c o m et h er e a lm a i n s t r e a m p e o p l eg r a d u a l l yr e c o g n i z e d t h a to n l yb e i n ga b l et od e s i g na n db u i l dp a r a l l e lh a r d w a r ew a sn o te n o u g h t h er e a lc h a l 1 e n g et u r n e do u tt ob es o f t w a r et h a ts u p p o r t sp a r a l l e lp r o g r a m m i n g m o s te x i s t i n gp a r a l l e l p r o g r a m m i n gs y s t e m ss u f f e ral o wa b s t r a c t i o nl e v e l ，a n dp a r a l l e lp r o g r a m m i n gw i t h i nt h e m i sd i 伍c u l t p a r a l l e ip r o g r a m sa r ea l w a y sm u c hm o r ec o m p l e xt h a nt h e i rc o r r e s p o n d i n gp a r a l l e la l g o r i t h m s ，a n dh e n c es u f f e rf r o mp o o rr e a d i b i l i t ya n de x t e n s i b i l i t y w h i l eo nt h eo t h e r h a n d ，t h ed i v e r s i t yo fp a r a l l e la r c h i t e c t u r e sl e a d st ot h ed i v e r s i t yo fp a r a l l e lp r o g r a m m i n g m o d e l sa n ds o f t w a r es y s t e m s ，t h u sl i m i t st h eg e n e r i c i t ya n df l e x i b i l i t yo fp a r a l l e lp r o g r a m s t h ek e yp r o b l e mt h a tw ew o u l d1 i k et os o l v ei sh o wt op r o m o t et h ea b s t r a c t i o nl e v e lo fp a r a l l e lp r o g r a m m i n gm o d e l sa n dt h e i rc o r r e s p o n d i n gp a r a l l e lp r o g r a m m i n gs y s t e m s ，s u p p o r t t h ed e v e l o p m e n to fg e n e r i cp a r a l l e ld a t as t r u c t u r e sa n da l g o r i t h m s ，a n df i n a l l yp r o m o t et h e p r o d u c t i v i t yo fp a r a l l e lp r o g r a m m i n g i no r d e rt os o v l et h ea b o v ep r o b l e m s ，t h er e s e a r c h w o r k si nt h i sd i s s e r t a t i o na r e ： ( 1 ) s t u d yo nm e s s a g e p a s s i n gp a r a l l e lp r o g r a m m i n gm o d e l m o t i v a t e db yt h el o wa b s t r a c t i o no fe x i s t i n gm e s s a g e p a s s i n gs y s t e m s ，w ep r o p o s e d an e wg e n e r i co bj e c t o r i e n t e dm e s s a g e - p a s s i n gi n t e r f a c e g o o m p i w ec r e a t e dac o m - p l e t ef r a m e w o r kf o rd a t ap a r t i t i o n ，s e r i a l i z a t i o na n dt r a n s m i s s i o n ，a n de f f e c t i v e l ys o i v e d t h ep r o b l e mo ft r a n s f e r r i n ga r b i t r a r yu s e r d e f i n e d ，c o m p l e x id y n a m i cd a t as t r u c t u r e sa s w e l la sa b s t r a c td a t at y p e s w ed e s i g n e da n di m p l e m e n t e dt h ep o l i c y b a s e dv e r s a t i l e c o m m u n i c a t i o np o r tt os u p p o r ts t r e a m - s t y l em e s s a g e 。p a s s i n ga n dm e s s a g et y p ec h e c k i n g m e c h a n i s m s g o o m p is u p p o r t sr a p i da n di n t u i t i v em a p p i n gf r o mm e s s a g e - p a s s i n gb a s e d p a r a t l e la l g o r i t h m st oc o r r e s p o n d i n gp a r a l l e lp r o g r a m s w ea l s oi m p l e m e n t e ds e v e r a lt y p i c a lm e s s a g e 。p a s s i n gb a s e dp a r a l l e la l g o r i t h m si ng o o m p i ，a n dc o m p a r e dt h e mw i t ht h e i r m p ic o u n t e r p a r t s ( 2 ) s t u d yo ns h a r e dm e m r o yp a r a l l e lp r o g r a m m i n gm o d e l m o t i v a t e db yt h ed i s a d v a n t a g e so fe x i s t i n gm u l t i t h r e a dp r o g r a m m i n gs y s t e m s ，w ep r o p o s e dan e wp a r a l l e lm u l t i t h r e a d i n gi n t e r f a c e p m t ，w h i c hr e q u i r e sn ol a n g u a g ee x t e n s i o n so rp r o p r i e t a r yc o m p i l e r s i tp r o v i d e sd i r e c ts u p p o r tf o rm u l t i t h r e a d e dp a r a l l e l p r o g r a m m i n g ，i n c l u d i n gp a r a l l e lt a s km a n a g e m e n t ，t h r e a dp o o l ，v a r i o u sp a r a l l e lr e g i o n s ， s t a t i ca n dd y n a m i cs c h e d u l i n go fp a r a l l e ll o o p s ，a n dv a r i o u ss h a r e dd a t as t r u c t u r e sw h i c h s u p p o r tp a r a l l e la c c e s s w ea l s op a r a l l e l i z e ds e v e r a ld a t as t r u c t u r e sa n da l g o r i t h m sf r o m t h ec + + s t a n d a r dt e m p l a t el i b r a r yu s i n gp m t ( 3 ) s t u d yo i ll o c k - f r e es p e c u l a t i v ep a r a l l e lt h r e a d i n g w ed i s c u s s e dt h et e c h n i q u eo fs p e c u l a t i v ep a r a l l e lt h r e a d i n gu s i n gt r a n s a c t i o n a le x e c u t i o n ( s p t t x ) ，w h i c hi sb a s e do nt h e f u t u r em u l t i c o r ea r c h i t e c t u r e b e c a u s et h a t 1 1 1 英文摘要 中国科学技术大学博士学位论文 t h e r ea r ec u r r e n t l yn oh a r d w a r ep r o d u c t sw h i c hs u p p o r ts p t t x ，w ed e s i g n e da n di m p l e m e n t e das o f t w a r e b a s e ds p t t xf u n c t i o n a ls i m u l a t o ra n dc o r r e c t n e s sv e r i f i c a t o rb y , , s i n gb i n a r y l e v e ld y n a m i ci n s t r u m e n t a t i o n ，w h i c hc a ne f f e c t i v e l ys u p p o r tf u r t h e rs t u d yo d s p t t x ( 4 ) s t u d yo nu n i f i e dp a r a l l e lp r o g r a m m i n gm o d e l w ep r o p o s e dan e wu n i f i e dp a r a l l e lp r o g r a m m i n gm o d e lf o rh y b r i dp a r a l l e la r c h i t e c t u r e s 、w h i c hi n c o r p o r a t e st h em e s s a g e p a s s i n ga n ds h a r e dm e m o r ym o d e l s w ei l n p l e m e n t e dap r o t o t y p es y s t e mn a m e dp a r a d eb a s e do ng 0 0 m p ia n dp m t w h i c hs u p p o r t s u n i f i e dd i s t r i b u t e ds h a r e dd a t a ，a n du t i l i z e ss c o p e db e h a v i o u rt oo p t i m i z et h ed a t as h a r i n g i np a r a l l e lp r o g r a m s ( 5 ) s t u d yo na s p e c t - o r i e n t e dp a r a l l e lp r o g r a m m i n g w es t u d i e dt h ea p p l i c a t i o no ft h en e wa s p e c t o r i e n t e dp r o g r a m m i n gt e c h n i q u e w e p r o p o s e dag e n e r i ca s p e c t o r i e n t e dp r o g r a m m i n gf r a m e w o r k a o p + + ，a n dt r i e dt oa d d p a r a l l e la c c e s ss u p p o r tf o rd a t as t r u c t u r e sa sw e l la sp a r a l l e l i z es e q u e n t i a la l g o r i t h m si na n a s p e c t o r i e n t e dm a n n e r t h em a i nc o n t r i b u t i o na n di n n o v a t i o no ft h i sd i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) p r o m o t e dt h ea b s t r a c t i o nl e v e lo fp a r a l l e lp r o g r a m sb ya p p l y i n gm o d e r np r o g r a m m i n gt e c h n i q u e s m o t i v a t e db yt h e l o wa b s t r a c t i o nl e v e lo ft r a d i t i o n a lp a r a l l e lp r o g r a m s ，w ea p p l i e d m o d e r no b j e c t o r i e n t e d ，g e n e r i ca sw e l la sa s p e c t o r i e n t e dp r o g r a m m i n gt e c h n i q u e st ot h e r e a l mo fp a r a l l e lp r o g r a m m i n g ，a n dd r a m a t i c a l l yp r o m o t e dt h er e a d i b i l i t y ，m a i n t a i n a b i l i t y ，g e n e r i c i t ya sw e l la sm o d u l a r i t yo fp a r a l l e lp r o g r a m sw h i l ei n t r o d u c e dn oa b s t r a c t i o n p e n a l t y ( 2 ) p r o p o s e dv a r i o u sh i g h l e v e lp 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 nd i f - f e r e n tp a r a l l e la r c h i t e c t u r e s w ep r o p o s e dt h en e w g e n e r i co b j e c t o r i e n t e dm e s s a g e - p a s s i n gi n t e r f a c e g o o m p i ， w h i c hs u c c e s s f u l l ys u p p o r t sp a r t i t i o n ，s e r i a l i z a t i o na n dt r a n s m i s s i o no fc o m p l e xa n dd y n a m i cd a t as t r u c t u r e s w ep r o p o s e dt h ep o l i c y b a s e dv e r s a t i l ec o m m u n i c a t i o np o r t 。w h i c h e f f e c t i v e l ys u p p o r t su n i f o r ms t ：r e a m s t y l em e s s a g e p a s s i n g w ea l s op r o p o s e dan e wp a r a l 一 1 e lm u l t i t h r e a d i n gi n t e r f a c e p m t ，w h i c hi sap u r e1 i b r a r yl e v e ls o l u t i o n i ti m p l e m e n t s p a r a l l e lt a s km a n a g e m e n t ，v a r i o u sp a r a l l e lr e g i o n s ，s t a t i ca n dd y n a m i cs c h e d u l i n go fl o o p s ， a sw e l la sv a r i o u ss h a r e dd a t as t r u c t u r e s ( 3 ) p r o p s e du n i f i e dp a r a l l e lp r o g r a m m i n gm o d e l w ep r o p o s e dt h eu n i f i e dp a r a l l e lp r o g r a m m i n gm o d e l ，w h i c hu n i f i e dt h em e s s a g e p a s s i n ga n ds h a r e d - m e m o r ym o d e l s i ti m p l e m e n t su n i f i e dd i s t r i b u t e ds h a r e dd a t a ，a n d u t i l i z e ss c o p e db e h a v i o u rt os u p p o r td a t as h a r i n go p t i m i z a t i o n sf o rs p e c i f i cd a t ao b j e c t si n s p e c i f i cs c o p e s ，t h u se f f e c t i v e l ys i m p i f i e dt h ed e v e l o p m e n to fp a r a l l e lp r o g r a m so nh y b r i d a r c h j t e c t l l r e s k e yw o r d s ：p a r a l l e lc o m p u t i n g ，p a r a l l e lp r o g r a m m i n gm o d e l ，m e s s a g ep a s s i n gm o d e l ， s h a r e dm e m o r ym o d e l ，u n i f i e dp a r a l l e lp r o g r a m m i n gm o d e l ，t r a n s a c t i o n a lm e m - o r y is p e c u l a t i v ep a r a l l e lt h r e a d i n g ，o b j e c to r i e n t e dp r o g r a m m i n g ，g e n e r i cp r o g r a m m i n g ，a s p e c to r i e n t e dp r o g r a m m i n g l v 中国科学技术大学博士学位论文插图目录 插图目录 图1 1m p p 并 i 机群体系结构示意图 图1 2p v p 和s m p 体系结构示意图 图l 一3d s m 体系结构示意图 图2 1 消息传递模型示意图 图2 2g o o m p i 的层次化结构 图2 3i o s t r e a m s 结构示意图 图2 4m p i 流在i o s t r e a m s 类层次中的位置 图2 5 用g o o m p i 实现的s u m m a 算法 图2 6c a n n o n 算法的g o o m p i 与m p i 实现对比 图2 7g o o m p i 与m p i 程序代码量比较 图2 8l a mm p i 和g o o m p i 程序通信性能对比 图3 1 共享存储程序设计模型 图3 2 一组线程集合及线程间的关系， 图3 3p m t 程序的任务结构 图3 - 4s e g m e n t e d v e c t o r 内部结构示意图 图3 5s e g m e n t e d m a p 内部结构示意图 图3 6 并行f f t 算法中蝶形变换的任务划分 图3 7 基于共享存储的并行矩阵乘法示意图 图3 8 串行和并行泛型矩阵乘法 图3 9 使用p m t 实现的并行f f t 算法的运行时间 图4 1 软件平台整体架构7 0 图4 2 串行程序及相应s p t t x 并行程序结构 7 2 图4 3s p t t x 程序的执行过程7 2 图4 4 事务回退和恢复路径7 8 图4 5s p t t x 程序中的循环在正确性验证器中的执行次序示意图 8 2 图4 6s p t t x 程序中的循环在正确性验证器中的执行次序示意图( 按时 间轴展开) 8 2 v 3 3 4 5 7 8 2 4 5 5 8 3 3 4 坫掩毖弘弘踮勰 铊必蛆雅盯 插图目录 中国科学技术大学博士学位论文 v i 图4 7s p t t x 程序示例 图4 8s p t t x 模拟器运行示例 图4 9s p t t x 程序的投机成功率 图5 1p a r a d e 系统组成结构示意图 图5 2p a r a d e 系统中的并行任务 图5 3 用p a r a d e 实现并行矩阵乘法 图5 4 并行矩阵分块乘法的数据共享示意图 图5 5 用p a r a d e 实现并行j a c o b i 迭代算法 图6 1a o p + + 框架的组织结构 图6 2 计算v e c t o r 实例个数的方面 图6 3f i g u r e e l e m e n t 及其派生类的定义 图6 4 观察者模式的泛型组件 图6 5f i g u r e e l e m e n t 的移动事件 图6 6 实现观察者模式的方面 图6 7a o p + + 生成的类c 的继承结构 图6 8 调用a ? j m ，f ，j 的顺序图 图6 9 红一黑分解 图6 1 0a s p e c t 编织器的编译时性能 踮跖跖 虬眩g；叭 挖m m m m 加船 l 1 l 1 l 1 1 l 1 1 1 1 1 1 j 中国科学技术大学博士学位论文表格 目 录 表格目录 表2 1g o o m p i 各抽象层次的主要组件及功能概述 表2 2m p i 通信模式和g o o m p i 通信策略 表2 3 各种消息传递库的特性 表3 1p m t 的基本任务和任务组相关功能 表3 2p m t 中的线程和线程池 表3 3p m t 中的路障机制 表3 4p m t 中两任务间的同步机制 表3 5p m t 中的并行区域。 表3 6s e g m e n t e d v e c t o r ( 部分) 接口及功能 表4 1 事务性内存指令和s p t t x 应用程序接口 表4 2s p t t x 软件模拟器分析例程 表4 3 正确性验证器中各分析例程的功能 表4 4 预定义的调试级别 v i i 加 n n 娩阻的 订似s 8 s 3 中国科学技术大学博士学位论文 1 1概述 第一章绪论 本章首先介绍了本文研究工作的背景和研究现状，包括并行计算的发展、典型 的并行硬件体系结构、典型的并行程序设计模型及相应软件系统，并进一步介绍了 几种现代程序设计技术：随后总结了并行计算所面l 临的关键问题，并在此基础上， 提出本文研究工作的主要研究内容和思路；随后列出常用的文献资源并给出本文的 组织结构。 1 2研究背景及现状 1 2 1并行计算概述 随着计算机技术的飞速发展，几乎所有学科都走向定量化和精确化的道路， 从而产生了一系列诸如计算物理、计算化学、计算生物学和计算气象学等计算性 的学科分支，并逐渐形成了一门计算性的学科分支，称为计算科学( c o m p u t a t i o n a l s c i e n c e ) ，与传统的理论科学和实验科学并列，成为第三门学科。 由于应用的进一步推动，产生了对大规模和高性能计算的强大需求，因此出现 了并行计算机系统和并行计算技术，即同时使用多个处理器更快地求解问题。 计算机硬件的性能和集成度以m o o r e 定律所预言的指数级的速度持续高速发 展，并行计算机体系结构也经历了并行向量处理机、大规模并行多处理机等多个发 展阶段，直到近年来s m p 和机群体系结构逐渐得到推广，并出现了新型多核体系 结构，预示着未来并行计算即将经历新的高速发展阶段。 并行计算本身是一个复杂的系统问题，涉及并行计算机硬件体系结构、并行程 序设计模型、支持并行程序设计的软件系统等诸多方面的问题。 1 2 2 并行硬件体系结构 对并行计算机硬件体系结构的分类方式可以有多种。例如f l y n n 分类法 5 1 按 照指令流和数据流的多倍性概念对计算机系统进行了分类。其中指令流指机器所执 行的指令序列，数据流指指令流所操作的数据序列，而多倍性指机器的瓶颈部件 上所可能并行执行的最大指令或数据的个数。根据f l y n n 分类法，计算机系统可分 第一章绪论中国科学技术大学博士学位论文 为：单指令流单数据流s i s d ( s i n g 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 r e a m l 、单指 令流多数据流s i m d ( 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 r e a m ) 、多指令流 单数据流m i s d ( 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 r e a m ) 以及多指令流多 数据流m i m d ( 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 r e a m l 。 在本节中，我们以并行计算机系统中存储器的组织方式为标准对并行计算机硬 件体系结构进行分类。 1 2 2 1 分布式存储体系结构 分布式存储的并行计算机通常被称为多计算机( m u l t i c o m p u t e r ) ，是由多个具 有局部存储模块的相互独立的处理结点通过互联网络连接而成。其分布式存储所具 有的可扩放性质使这类系统有可能获得非常高的计算性能。然而，不同结点上的进 程之间需要使用消息传递模型来进行通信，因而程序设计比共享存储体系结构稍为 困难一些。 属于分布式存储体系结构的系统有： 大规模并行处理机m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 其结构特点为：在处 理结点中使用商用微处理器；在处理器结点内部使用物理上分布的存储器： 使用具有高通信带宽和低通信延迟的互联网络结构，各结点间紧密耦合；可 能扩展至成百上千个处理器：属于m i m d 计算机，进程间采用消息传递方式 进行同步；程序由多个进程组成，每个进程拥有独立的地址空间，通过显式 消息传递实现进程间通信，用户必须显式处理数据分布。 机群( c l u s t e r ) 是一组独立计算机的集合，其结构特点为：各结点均为完整的计 算机系统，结点可以是工作站、也可以是普通的p c 机；互联网络通常采用商 用网络，如以太网、f d d 和a t m 等：网络接口与结点彭j i o 总线松散耦合； 各结点有本地磁盘；各结点有自己独立的操作系统。 m p p g l 机群系统的组织结构分别如图l l ( a ) 和( b ) 所示。 51 2 22 共享存储体系结构 共享存储的并行计算机通常称为多处理机( m u l t i p r o c e s s o r ) ，它具有一个所有 处理器都可以访问的全局物理内存，并且可以通过对共享数据的读写来提供简单的 共享存储程序设计模型。 属于共享存储体系结构的系统有： 并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r l 通常包含了少量专门设计 定制的高性能向量处理器( v e c t o rp r o c e s s o r l ，每个处理器往往至少具 2 中国科学技术大学博士学位论文1 2 研究背景及现状 ( a ) m p p( b ) 机群 图1 1 ：m p p 干1 1 机群体系结构示意图 s w i t c hn e t w o r k 8 u s s w i l c hn e t w 。r k ( a ) p v p( b ) s m p 图1 2 ：p v p , i s m p 体系结构示意图 有1 g f l o p s 的处理能力。系统使用专门设计的高带宽交叉开关网络将向量 处理器连接到共享存储模块，存储器能够以兆字节每秒的速度向向量处理器 提供数据。p v p 通常不使用高速缓存，而是使用大量的向量寄存器和指令缓 存。 对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 通常由若干商用微处理器组 成，它们之间经由高速总线f 或交叉开关) 连接到共享的存储器。系统的结构 是对称的，每个处理器都可以等平等地访问共享存储器、i 0 设务和操作系 统服务。 p v p , i i s m p 系统的组织结构分别如图1 2 ( a ) 和( b ) 所示。 此外，需要特别提出一类新型的共享存储体系结构的系统，称为多核( m u l t i c o r e ) ，即在一个单独的芯片上封装多个处理器内核，因引多核又称为片上多处理 机( c mp ) c h i pm u l t i p r o c e s s o r ) 。多核体系结构严格地说是一种微体系结构( m i c r o 一 3 第一章绪论 中国科学技术大学博士学位论文 图1 3 ：d s m 体系结构示意图 a r c h i t e c t u r e ) ，其多个处理器核心之间往往共享二级以下的c a c h e ，因此处理器间的 交互具有非常小的延迟，是一种极端紧耦合的体系结构。在多核体系结构上的并行 计算通常更易于获得更高的性能和加速比。 多核体系结构可以近似看作一个更紧密耦合的s m p ，但多核系统中可以设置 新的对事务性内存f 4 3 1 和投机并行多线程 3 0 1 f 6 5 】的硬件支持，从而支持锁无关的 投机并行多线程程序设计( 详见第4 章) 。 1 2 2 3 分布式共享存储体系结构 分布式共享存储d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 体系结构【5 6 1 【4 5 】是在物理 上分布存储的系统中逻辑地实现共享存储模型，其结构示意图如图1 3 所示。 d s m 的分布式共享功能既可以由硬件实现，也可以由软件实现。使用硬 件实现的d s m 系统，从用户的角度来看，可以等同于共享存储体系结构。 用软件实现的d s m 又称为共享虚拟存储( s v m ，s h a r e dv i r t u a lm e m o r y ) ( 在本文 第5 章中对d s m 系统和分布式共享数据( d s d ) 系统进行了比较) 。典型的d s m 系统 有c v m 5 5 】、b r a z o s 【8 6 、r t h r e a d s 【2 9 】、m i l l i p e d e 【4 8 】 4 9 、s c i o s 6 0 、s m i l e f 5 4 1 、p r o t e u sf 9 3 1 、s h a s t af 7 7 1 以及s i r o c c of r s 等等。 51 2 2 4 混合式体系结构 这里所说的混合式体系结构( h y b r i da r c h i t e c t u r e ) ，指的是并行系统中同时具 有分布式存储和共享存储的性质。典型的实例是s m p 机群( s m pc l u s t e r ) 。 在s m p 机群中，s m p 结点之间为分布式存储体系结构，而同一个s m p 结点内 部的各处理器之间组成共享存储体系结构。s m p 机群比单个s m p 结点有更好的可 扩放性，而比普通的机群有更高的集成度和计算能力。s m p 机群体系结构又称为 4 中国科学技术大学博士学位论文1 2 研究背景及现状 层次式体系结构( h i e r a r c h i c a la r c h i t e c t u r e ) 。 在多核体系结构出现之后，在不久的将来，必然出现多核s m p 机群( m u l t i c o r es m pc l u s t e r ) 这样具有更多层次的混合式体系结构。 混合式体系结构无疑拥有更强大的计算能力，但在该体系结构上的并行程序设 计模型也随之变得极为复杂。本文第5 章中讨论了混合式体系结构上的并行程序设 计模型。 1 2 3并行程序设计模型 对于并行计算的用户而言，任何并行计算机硬件体系结构最终需要为用户提 供一个程序员视图( p