（计算机应用技术专业论文）并行归并排序算法及其在pc集群中的实现.pdf

摘要 摘要 现代许多领域中具有挑战性的大规模计算课题需要商性能并行处理机，而硬 孛援本懿迅速发嶷已搜建造劳行处理枫熬凝一代计算规戆经济霹行蛙曼灌增鸯曩， 但是阻碍并行处理机进入主流技术的主鞭问题还是在软件和应用方面。但是并彳予 舞法设计真着特殊静困戆。以翦我们考虑遍题是攘时闻豹颁序来考虑，蕊现在我 们却要把整个问题看作由多个可并行的予问题缎成。大烈计算中心，排序被认为 占用了大量的计算时间。髓着势特处理技术的发展，并行接序已经成为并萼亍算法 中的一个重要的研究领域。本文提出了并详细描述了一种新的并行归并排序算 法，算法充分利用了各个处理器搁 序后序列长度相等豹特点，计算出归并段对中 的一个元素和最聪一个元素的位踅，然聪从相应的位置激行归并排序。本算法达 到了较商的负载平衡性、可扩展性和排序稳定性，而且摊序后，数据分布完全平 赞。 现在p c 机的性能不断的提礴，价格下降，很好的性能价格比使很多单位普 遍使露鬻集群。瓣蘧，耩究弼筏维箴的游络荠行计算平台，荠在萁上滋彳亍并行 计算，可以大大提高现有设备解决实际问题的能力且为并行算法的研究提供一个 试验嚣凌。l i n u x 是u n i x 在p e 瓿上熬蜜疆，它楚静秀效源钱璐翡分辩缣佟系 统。它融被广泛用于并行计算平台。m p i 消息传递方式悬被广泛应用并行机的一 秘模式，姆嚣| 逶鲻手那些分蠢存德豹并行搬；多年来，这秘模式在重要耱诗算 应用中已取得了实质进步。m p i 标准已定义了与c 语言、c + + 和f o r t r a n 的绑定。 m p i c h 是m p i 豹秘稳定豹实瑗，它可以建立与c 语言、c + + 、f o r t r a n7 7 、 f o r t r a n9 0 、j a v a 的连接。我使用t i n u x + m p i 在p c 机上实现了并行计算平台并 农j 班：平台上实现了我提出的著行! 醴并排序算法。程已有势行 # 露算法中，p s r s 簿法是效率和可扩展往较高的一种，本人在同样的条件下实现了此算法，并与本 人提出的算法在理论和实验数据上作了比较，指如了本算法的优缺点。 荧键字：并行归并，归并段对，鹳 序算法，p c 集群，l i n u x ，舭i ，m p i c h 珏 a b s t r a c t t h e c h a l l e n g i n g a n dm a s s i v ec o m p u t a t i o np r o b l e mi nm a n ym o d e m f i e l d sn e e d p a r a l l e lc o m p u t e r s o fh i g hp e r f o r m a n c e ，a n dw i t hd e v e l o p m e n to ft h et e c h n o l o g yo f h a r d w a r et h ee c o n o m i c f e a s i b i l i t y o f b u i l d i n gp a r a l l e lc o m p u t e r i si n c r e a s i n g i n t e n s e l y , b u tt h em a i np r o b l e mt h a t p r e v e n tp a r a l l e lt e c h n o l o g yb e c o m i n gt h e m a i n s t r e a m t e c h n o l o g yl i e s i nt h es o f t w a r ea n dt h ea p p l i c a t i o n t h e r ea r es p e c i a ld i f f i c u l t i e si n d e s i g n i n gp a r a l l e la l g o r i t h m p r c v m u s l y ，w et h o u g h tap r o b l e mi nt e r mo ft i m e ，b u t n o w , w et h i n kaw h o l ep r o b l e mm a d eu po fm a n yp a r a u e l i z a b l es o np r o b l e m s i nt h e b i gc o m p u t a t i o nc e n t e r , s o r t i n gi st h o u g h to f o c c u p y i n g m u c ht i m e w i t h d e v e m p m e m o fp a r a l l e l t e c h n o l o g y , p a r a l l e ls o r t i n gh a sa l r e a d yb e c o m ea ni m p o r t a n tr e s e a r c h r e a l m 。t h i sp a p e rp r o p o s e sa n dd e s c r i b e san e w p a r a l l e ls o r t i n ga l g o r i t h m 。i tt a k e s a d v a n t a g eo fc h a r a c t e rt h a tt h el e n g t ho ft h el i s t i ne v e r yp r o c e s s o ri s e q u a la f t e r s o r t i n gi nap a r a l l e ls y s t e m i tc o m p u t e s t h ep o s i t i o n so ft h ef i r s ta n dl a s te l e m e n t si n m e r g i n gp a i t , a n dt h e nm a k em e r g i n gs o r t i n gf r o mt h o s ep o s i t i o n s t h ea l g o r i t h m d i s t r i b u t e sd a t aa v e r a g e l ya f t e r s o r t i n ga n dr e a c hh i 痨e f f i c i e n c y , s e a t a b i l i t y a n d s t a b i l i t y n o w , p c s p e r f o r m a n c ei si n c r e a s i n ga n dp r i c ei sd e c r e a s i n g , a n dm a n y u n i t su s e p cc l u s t e r s a c c o r d i n gt o t h eh i g hr a t i oo fp e r f o r m a n c ea n dv a l u e s or e s e a r c h i n g c l u s t e rm a k i n g u p o fp c sa n d d o i n gp a r a l l e lc o m p u t i n g c a ni n c r e a s ep o w e ro f f a c i l i t y a n d p r o v i d e a n e x p e r i m e n t a t i o n e n v i r o n m e n tt ot h e mw h or e s e a r c h i n g p a r a l l e l a l g o r i t h m l i n u xi sr e a l i z a t i o no f u n i xo np c , a n di ti so p e ns o u r c ea n d t i m e s h a r i g o p e r a t i n gs y s t e m m 鞭( m e s s a g ep a s s i n gi n t e r f a c e ) i sam o d ew i d e l yu s e db yp a r a l l e l c o m p u t e r s ，a n dp a r t i c u l a r l yi sf i t t op a r a l l e lc o m p u t e rw i t hd i s t r i b u t e dm e m o r y f o r t e ny e a r s ，t h i sm o d eh a sm a d em a t e r i a lp r o g r e s si n a p p l i c a t i o no fc o m p u t e r s t h e s t a n d a r do fm p ih a sd e f i n e db i n d i n gt oc 。c + + a n df o r t r a n m p i c hi so n eo fs t a b l e r e a l i z a t i o no fm p i i tc a nb u i l dj o i n tt oc ， + ，f o r t r a na n dj a v a 1h a v er e a l i z e d p a r a l l e lp l a t f o r mu s i n gl i n u x + m p ia n dm ya l g o r i t h mo nt h i sp l a t f o r m a m o n gt h e p a r a l l e ls o r t i n ga l g o r i t h m s t h a th a v eb e e np r o p o s e d ，p s r si sm o r ee f f i c i e n ta n d s c a l a b l e ir e a l i z e di to nt h es a m e p l a t f o r m ，c o m p a r e di tw i t hm ya l g o r i t h ma n ds h o w a d v a n t a g ea n ds h o r t c o m i n go fm ya l g o r i t h m 。 k e y w o r d s ：p a r a l l e ls o r t i n g , m e r g i n gp a i r , s o r t i n ga l g o r i t h m ，p cc l u s t e r , l i n u x ，m p i , m p i c h i i i 前言 6 3 5 2 9 6 前言 科学技术的发展需要高性能的并行处理机。目前硬件技术的迅速发展已使建 造新一代并行计算机的经济可行性显著增加，但是阻碍并行处理进入生产、成为 主流技术的主要问题还是在软件和应用方面。从2 0 世纪9 0 年代以来，昂贵和特 制的并行处理机向工作站网络转换的趋势越来越强。由于p c 机的价格不断的下 降，在国内，许多科研院所都使用p c 机来代替价格昂贵的工作站。p c 集群成为 工作站网络的一种可替代选择。 排序是一个经常用到的基本运算，在大型计算中心，排序被认为占用了大量 的计算时间，所以对排序算法的研究有着重要的意义。随着并行处理技术的发展， 并行排序已经成为并行算法中的一个重要的研究领域。 本文集在此背景下，提出了一个新的并行排序算法并在p c 集群并行条件下 实现了这个算法。本文一共分为五部分。其中第一部分为绪论，介绍了并行计算 的意义。第二并行的基础知识及应用，介绍并行的基础知识及如何设计并行算法。 第三部分p c 集群的并行处理环境与并行程序设计，介绍如何建立m p i 并行运算 环境和运用m p i 编并行程序；第四部分并行归并排序及其在m p i 并行环境中的实 现，介绍新提出的并行算法及在刚建立的并行运算平台上实现此算法。第五部分 得出相应的结论。 1 绪论 自1 9 4 7 年第一台计算机诞生以来，由于对计算机的需求领域不断扩大，计 算机处理的事务也日益复杂，这就对计算机的性能提出了更高的要求。因此如何 提高计算机的性能就成了一个重要问题。通常采用的第一种方法是提高处理器的 运算速度，以使它拥有更大的计算能力。但微电子器件的发展也会受到各种制约， 不可能会无限制的发展，现在有一种可行的方法是将多个处理器以网络形式连接 起来，形成一个强大的联合计算能力。这种系统即现在常用的并行系统，它将计 算任务分布在多个处理器上。现在并行系统已经在数据处理、信息处理、知识处 理和智能处理等领域得到了广泛的应用。 1 1 并行计算机的发展 计算机科学对并行处理的探索可以追溯到2 0 世纪5 0 年代。1 9 5 0 年， v o n n e u m a n n 提出了“自复制细胞自动机”的概念。1 9 5 8 年s t e v e nu n g e r 提出了构 造了两维s i m d 阵列机的设想，随后于1 9 6 3 年按该设想提出了两种方案：s o l o m o n 系统以及i l l i a c i ，但均以失败而告终。1 9 7 2 年美国i l l i n o i s 大学与b u r r o a g h 公司合作研制的i l l i a c e i v 系统可以说是分布式存储大规模并行计算机的鼻祖。 该机原拟作四个象限，每个象限由8 * 8 个处理单元构成，每个处理单元可以和上 下左右四个处理单元通讯。这种设计思想对多处理机阵列结构的研究及设计产生 了极大的影响。但由于当时的硬件水平所限，i l l l a c e i v 仅制作了一个象限，且 不太成功。 1 9 7 6 年美国c r a y 公司研制成功了世界上第一台实用向量巨型机c r a y l 。接 着，在1 9 8 3 年c r a y 公司又推出了四个向量处理机共享存储的c r a yx - m p 系统， 成为世界上第一台成功的并行计算机。 8 0 年代中期，随着超大规模集成电路的发展，单片微处理器性能的提高和 并行处理技术的进步，研制出了新一代的分布式存储大规模并行机。如美国 t h i n k i n gm a c h i n e 公司的c m - 1 和c m - 2 系统，以及n c u b e 公司的n c u b e - l 、n c u b e 一2 系统等。 进入9 0 年代以来，共享存储并行计算机也有了长足进步，特别是多处理机 服务器的推广应用更增强了共享存储并行处理技术的生命力。1 9 9 5 年c o n v e x 公 司的s p p l 2 0 0 并行机采用了分布存储超级节点的体系结构，在每个节点上拥有四 个共享存储的处理器“1 。 随着网络技术的发展，昂贵而特制的并行计算机向工作站网络转换的趋势越 来越强。技术的发展使计算机网络成为并行处理的理想工具，从而导致了底价商 缝论 晶化超级计辣机的出现。并行计算的发展趋势正在从传统的专用超级计算机平台 转到廉价而邋用、松耦合、出单一或多个处理器的p c 机或工作站构成的系统。 b e r k e l e y 涎n o w ( n e t w o r ko fw o r k s t a t i o n ) “搜麓嵩幢髭王豫站移最先遴鹣 潦于开关的商晶化网络部件以构建大型并行计算机系统。n o w 系统俘含了对网络 接口硬件、快速通信协议、分布式文件系统、分布式调度和任务控制的研究和开 发。活动消爨楚b e r k e l e yn o w 的基本通信原语。它继承了早期删接口，是一个 麓化了静运稷过程谣溪。n o w 包括一套低延迟酶并行通信原语：b e r k e l e y 套接字、 快速套接字、共享地址空间并行c 和m p i 。g l u n i x 是个操作系统屡，提供以下 功能：透明的远程运行、交赢式并行和串行作业支持、负载平衡和对现有二进制 疲塌覆痔夔囊瑟兼窭蛙。掰络嚣蛾霞入爨可淤壤溪空耀辍器主豹窆瓣资源终为繁 忙机器的页蕊设备。 高性能虑拟机( h p v m ) 项目是将超级计算机的性能分配在低价商品化的系统 上。h p v m 项霸提供酶软件使离性能计算w 以在p c 或工作站集群上逡稽。h p v m 麴 个重要部分蹩寒带宽缝筵遮豹逶癌诱议，称为快速滚惑( 嘲，磷旗子b e r k e l e y 的a m ，这是一个以m y r i n e t 连接的s p a c e 工作站构成的集群。 b e o w u l f 项目的目标怒发掘p c 集群执行目标的潜力。b e o w u l f 指的是一蛾 趟规构成一个与c o w n o w 类 缓戆p c 集爨。b e o w u l f 熬处理器藏运嫠是逶蓬集群 内酷太两露t c p i p 实现鹅。b e o w u l f 护越了l i n u x 融核，使节赢松散耦合成为 w 能，以达到多个全局名字空间。通常，b e o w u l f 集群采用l i n u x + m p i 的方式支 持并行计算。m p i 是采用消息传递的方式实现并行程廖间通信。虽然也可以采用 装恁夔逶售方法，餐是溃惑传递模式趸袋逶台子集嚣系统静”。 1 2 并行计算的应用 涎羞柱会与辩学豹飞邃发袋，诲多菱象豹辩学诗冀、匿量数蕹姓理、怒丈羹 工程设计等课题都急遗魄摆在了人们面前，实现和完成这些工作无一不对计算桃 的运算速度、存储容量及数据传输速度等提出了几乎煅无止境的要浓。传统的微 溅计算规显然恶法满足这黧要求。即傻穗壁基型机对上述要求也憋篾褥力不姨 ，洛。只有采麓先进大蕊模并行薤理( m a s s i v e l yp a r a l l e lp r o c e s s i n g 一酣p p ) 技术 才能满足上述疆求。当今，世界各主要经济技术大国，特别是美、日镰国都相继投 入了巨额资金用于发展研究舯p 技术。美围的h p c c ( b i g h p e r f o r m a n c e c o m p u t i n g c o m m u n i c a t i o n ) 诗，基零瓣r 裙( r e a lw o r l dc o m p u t i n g ) 诗翔等零是嚣绕上 述目标而提出的“1 。 “世界级骥大挑战性课题”概念是由美国在其h p c c ( 高性能计弹和通信) 计 划中提出来的，该计划主要耀骥大规模并行性开发和废用的可能技，译馈过去豹 逡鼹势淹篷鼢p 未来鹄菱袋鲶势。 2 绪论 近几年来，大规横并行计算已往诸如磁记录技术、合适的药物设计、高速民 震运竣瓠设诗、鹱纯终矮、海洋建援、气象、蛋鑫壤缝捣与甏像巍蓬豫理麟等等 战略和函计民生领域褥到了广泛嘏应用。 1 3 并行算法的意义及本人所做主要工作 当代面临的许多獯大科学河戆都要依赖予使用计算技术协助解决。如分子结 构的确定，一种简单的方法就是计鳞所有分子有可能的构造能凝，然后选择有最 低能量的构造，这静计算量是非常庞大的，着使朋单台处理机需要花费很长的时 翔，悉瑟舞行羲来计舞羯要抉戆多。又兹霹合藏潢鑫豹穰 薹l ，鼹对数手个鞭子和 几百万个结构进行比较，用最快的单机顺序计算，需要几小时甚至几天的时间， 而用大规模并行机来计算，只要这个时间的几十分之一甚至几酉分之一。硬件技 术的迅速发展已使建造掰一代并孬诗冀祝数经济霹簿惶显著璞魏。茏其是工终港 网络( n o w ) 的发展，使并行枫鹃费用迸一步降低。但是阻碍并行处理进入艇产、 成为主i i c 技术的主要i 酬醒还是在软件和应用方面。并行程序设计串行程序设计不 同，顺序程序设计方法是把事物的嶷化发展看成怒单线程的，任何连中事物必然 存在鸯嚣荣关系，扶嚣琵一系裂统一事鐾看戒誉霹分蘩豹整傣；瑟蒡嚣程黟设计 方法的爨罄本观点就怒把一事物的行为看成多个事物相互作用的结果。所以并行 算法设计有着特殊的阑难0 1 。 本文的工作主要蹩辑究k 税缀成的鼹终并行计算乎台，势在其上进稃势行 簿序箕浚实验。主要佟了懿下王律； 第一，在p c 集群上，建立了基于m p i 并行计算平台。 第二，给出一新的归并排序算法，并在此平台实现这一算法。 3 并行的基础知识及应用 2 并行的基础知识及应用 并行应用与并行开发技术己在计算机科学中创出了一个新的方向。 2 1 并行特征 无论是数值计算、数据处理、信息处理还是人工智能问题求解，其中部分可 能包含有能同时进行运算或操作的成分。我们把问题中具有可以同时进行运算或 操作的特性，称之为并行性( p a r a l l e l i s m ) 。开发并行性的目的是为了能予以并 行处理，以提高计算机求解问题的效率。 例如，在使用具有相同延迟时间的元器件条件下，采用n 位计算器进行n 位 并行运算的速度几乎是用以一位运算器进行m 位串行运算的m 倍，这就是传统机 器由串行到并行的典型事例。但是，对并行性的理解不能只限于这种靠器件资源 的简单重复实现的并行，应当有更广义的理解。比如，单处理机内采用的重叠、 流水方式工作，操作系统中采用的多道程序分时共行，都是更广意义上的并行。 也就是说只要在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或 不同的工作，它们在时间上相互重叠，都体现了并行性。 要并行执行几个程序段，必须使每段与其他各段无关。相关性表现在以下三 个方面： 数据相关包含以下五个方面0 1 ： i 流相关：如果两个语句之间存在执行通路，而且如果一个语句s ，的 输出是另一个语句的输入s ：，则两个语句之间存在流相关； i i 反相关：如果在执行次序中s ：紧接s 。而且如果s 。的输出与s ，的输 入重叠，则语句s 。与语句s 反相关； i i i 输出相关：如果两条语句能产生同一输出变量，则他们就是输出相 关； i v i o 相关：读和写都是i o 语句，且两条i o 语句引用的是同一文件： v 未知相关：在下列情况下，两条语句之间的相关关系不能确定： _ 变量的下标就是它本身： 下标不包含循环指标变量； 一带有不同循环变量系数的下标变量不止一次的出现： 下标在循环指标变量中是非线性的； 当这些条件中有一个或几个存在时，比较保守的做法是认为有关语句之间 为未知相关。 控制相关：这指的是控制语句执行次序在运行前不能确定的情况。 4 并行的基础知识及唐霸 资源相关：并行时间利用整数部件、浮点部 牛、寄存器和存储器等贡献资源 露发象夔淬突鸯关。 1 9 6 6 年b e r n s t e i n 提出一种祭件集合，农这种条件枫和旗础上，两个进程 可并行运行。现设有两个进程p ，和p 2 ，他们的输入集合分别为i ，和iz ，输出集 合分别为0 ，和晓。如果这两个进程不相关，而且不会产生令人迷惑的结果，那末 链翻藏缝并行运行。这些条俘霹良形式纯篷表示魏下： i 。n 0 2 = 中 i t n 0 1 - m o ；n 盼垂 b e r n s t e i n 条件意昧着如采两个进程流不桐必、反不相关和输出不相关，则 他们就熊并行执行。 2 。2 势褥诗羹视的分类 并行计算机的分搬可根据处理器的类型数量、全局控制机构、同步舜步、 以及处骥机的互连结构等因素来划分。在传统上荤刚门采用1 9 6 6 年由美国学滋m j ，f l y n n 撬整羲分类方法，接照搿令滚葙数据滚挺计算穰系统分蔻疆类秘： 1 单指令流单数据流( s i s d ) 计算机 赢到现在所设计和建造的大多数计算机都是这类计算机，它不属于并行 枧，两属于传绞鸵串行计算极。它有两种嚣攀重要静特链：事行和礁定懿。 图2 1s i m d 计算机操作模型 5 2 单指令流多数据流( s i 妨) 计算机 这是计算机体系结构历史上静一秘整要静分类，对予数据并行类| 、瘫越， 逶耪诗冀掇襞够这窦穰毫戆殓瑗速发。s i l v i d 穰嚣秀一令疆令滚，哥袋鸯多 个单元在援行，毽是任一薅捌灵蠢一条攒令在撬牙，所班该类诗算凝豹主要 特征是：同步盼，确定的；适瘫攥令搽作及并幸亍。 阵列处理机、流水线处理机、关联处理机等均属于此类计算机。其模测 如图2 。1 所示。控制部件把指令广播到所有的处理器( p e ) ，各个处理器根 据屏蔽方案选择执行或者不执行控制部件的指令。处理器之间通过网络遵按 起来。 s i m d 类型并行机通常通过以前端机执行指令，而并行机根据指令对数据 谶行处理。s l l d d 类型并行机对并行计算桃钓发展起到了重要的推动作用，假 出予徽处理芯片技术的发展，9 0 冬代以薅，菸行钒均朝m i m d 方自发展，假 处理壤往戆豢菲霉强夫，搏予科学与王糗诗舞鹣s i m o 类型笄行极已经基本邋 交了历史舞台。 3 多攒令滚单数撂流诗算穰( m l s o ) 现在还不知道哪种计算梳逶会这种横型。 4 多指令流多数据流计算机( m i m d ) 这种计算机才是真正的弗行计辣机。它是由一组独立的处理机组成，每 个处理机都拥有他们各自的程序计数器、程序和数据。m i m d 型计算机可根据 内存是否共享分为共享存储型m i m d 并行多处理机和分布存储型m i m d 并行多 处理机嘲。 共享存储型m i m d 并行多处理机：指多台处理机通过互联网络共享一个 图2 2 共享存储m i m d 结构 内存空潮，并逮过该内存空间来实行处理税之闽魏协调。 图2 。2 孛熬签瑾援胃淡使标鬃娥瀵器，遣可疆是自量处理器。连接憝瑗 狡与存镰模块之霾豹网络类鍪主要露黻下豆秘： 6 并行的基础知识及应用 i 总线互联结构：这是早期共享存储并行机通常采用的结构。分时共 享中总线每台处理机提供了访问内存模块的均等机会，但一次只能由一 台处理机访问总线。 i i c r o s s b a r 互连结构：使用交叉开关，在每个可能的处理机存储器模 块之间提供专用通道，从而防止出现访存竞争冲突。 i i i 多级互联网络结构：是c r o s s b a r 和总线性能价格比的折中。他通过 多级互联开关网络连接处理器与存储器模块，进行存储访问请求的处理机 通过发出含有每级控制位的位置，来制定所希望的目的地。 分布式存储m i m d 并行多处理机：每台处理机都有自己可直接访问的内 存，或称局部存储器，每台处理器成为系统中的一个节点，节点之间通过互 联网络相互连接。 图2 3 分布存储m i i c d ) 的一般模型 图2 3 代表了m i m d 的一般形式，这里每台处理器只能直接访问局部 存储器，对远端存储器的访问必须以消息传递的方式，通过互联网络来 完成。分布式存储并行机克服了共享存储并行机可扩展性差的缺点，具 有很好的可扩展性。消息传递分布式存储m i m d 并行机可分为两种： i 大规模并行计算机( m p p ) ：有成百上千的功能相同的处理机通过 网络连接而成； 7 i i 网络并行机群系统：由同构或异构型串行或并行计算机通过快速 局域网或广域网相互松散连接而成。例如，工作站集群( n o w ) 、p c 集 群、全对称s m p 集群通过a t m 连接的广域网集群。 2 3 并行算法简介 算法是解题方法的精确描述，是一组有穷规则，这些规则规定了解决某一特 定问题的一系列运算。所谓并行算法是指可以在各种并行计算机模型上求解问题 和处理数据的算法。 定义2 1 并行算法是指一些可同时执行的诸进程的集合，这些进程相互作用 和协调工作，从而达到对给定问题的求解。 2 3 1 并行算法的发展 算法和应用程序的内在并行度导致了并行计算机的出现和发展，反过来并行 计算机的出现也在很大程度上影响着并行算法的发展。实际上，并行计算机和并 行算法的发展是相辅相成、缺一不可的。 并行算法的发展经历了几个重要阶段： i 基于向量运算的并行算法设计阶段 该算法随着向量计算机( 如c r a y i ，y h 一1 ) 的出现而出现的。7 0 年代末和8 0 年代初时期研究的顶峰时期，这方面最著名的成果是递归问题的向量化。 2 基于多向量处理机的并行算法设计阶段 该算法是随着多向量处理机( 如c r a yy 一卿，y h 一2 ) 的出现而出现的。其特点 是既要考虑到多处理机间的任务级大粒度并行，又要考虑到单处理机上的向量级 细粒度并行，该类算法在8 0 年代初期和中期比较流行，目前日本一直坚持这方 面的研究和应用软件开发工作。 3 s i m d 类并行机上的并行算法设计阶段 由于该并行机有大量功能简单的微处理器构成。因此通常要求并行算法很好 的在各个处理器上分配局部数据，并组织数据在处理器间合理流动，从而求解整 个问题。典型的代表为c m - 2 、s y s t o l i c 阵列、t r a n s p u t e r 等类并行机上的并行 算法。该类并行算法的研究在8 0 年代中期比较热门，但由于缺少一般性，过分 依赖于机器，程序设计复杂，因此，随着8 0 年代后期高性能并行机的出现，很 快被淘汰。尽管如此他们对帮助用户理解并行算法设计的技巧、并行机设计和通 信原理是很有益处的。 4 m i m d 类并行机上的并行算法设计阶段 该类并行机的显著特点是处理机功能比较强大，能独立处理各类复杂运算， 处理机间通过显示或隐式的通信来相互协同，共同求解同一问题。并且处理机间 并行的基础知识及应用 单位数据的通信开销通常远远高于处理机间单位运算的开销。一次该类并行机通 常需要任务级的大粒度并行。也就是说，我们需要设计大粒度并行算法来适应该 类并行计算机。 5 现代并行算法设计： 目前并行算法设计仍然以m i m d 类为主流，并且要求具有可扩展性和可移植 性。但随着微处理器和互联网络的迅速发展，可扩展性高性能的获取必须要求并 行算法设计兼顾两个发展方向：第一，可扩展、可移植的大粒度任务级并行；第 二，在每个进程，组织便于发挥单机性能的合理数据结构、程序设计和通信方式。 只有兼顾了这两个方面，才能真正发挥当前由高性能微处理器和互联网络构成的 并行计算机的潜在高性能。 2 3 2 并行算法的分类 并行算法可从不同的角度加以分类：数值计算的和非数值计算的；同步的、 异步的和分布的嘲； 定义2 2 数值计算是指给予代数关系运算的一类，诸如矩阵运算、多项式求 值、解线性方程组等计算问题，基本上属于数值分析( 对以数字形式表示的问题 求数值解) 的范畴。 定义2 3 非数值计是指给予比较关系运算的一类诸如排序、选择、搜索、匹 配等方面的计算问题。基本上是属于符号( 字符、数字、图形或别的一些记号) 处理的范畴。 定义2 4 同步算法是指某些进程必须等待别的进程的一类并行算法。因为一 个进程的执行依赖于输入数据和系统中断，所以全部进程均必须在一个给定的时 钟，以等待最慢的进程。 定义2 5 异步算法是指进程的执行一般不必相互等待的一类并行算法。在此 情况下，进程的通信是通过动态的读取( 修改) 共享存储器的全局变量来实现。 定义2 6 分布算法是指给予异步通信模型上设计的一类算法，其特征是通过 传递消息来协同多个节点上的进程共同完成整个问题的求解。 2 3 3 并行算法的性能评价 如何解释影响并行算法性能发挥的关键因素，直到他们改进和优化，充分发 挥他们在具体并行机上的性能，最优性能、正确、真实、全面的并行算法性能量 度是一个必不可少的重要方面。性能量度的目的就是为并行算法的设计与分析提 供个统一的衡量标准，直到并行算法达到最优性能。 粒度 粒度是一个任务的工作量或执行时间。它包含5 种级别“，分别为指令级、 9 并行的基础知识及应用 循环级、过程级、子程序及作业级。 1 ) 指令级：指令级或语句级的典型粒度一般包含的指令数小于2 0 。这种级别的 细粒度并行性可在2 指数前范围变化，取决于程序的具体情况。细粒度计算的优 点是在并行性比较丰富的情况下可将它充分反映出来。开发细粒度并行性可借助 于优化编译器，它能自动监测并行性，并将源代码变成运行时系统能识别的并行 形式。 2 ) 循环级：这相当于迭代循环操作，典型循环包含的指令大约不到5 0 0 条。假 如有些循环操作在连续迭代中并不相关则即可使之向量化，并在流水线上执行或 在s i m d 计算机上锁步执行。有些循环操作可以自调度在m i m d 机上并行执行。 3 ) 过程级：这一级是中粒度规模，与任务过程子程序、协同程序及相对应。其 典型粒度包含的指令小于2 0 0 0 条。与m i m d 运行模式相比，这一级的通信要求通 常不多。多任务处理机也属于这一范畴。可能要程序员付出较大努力重新设计这 一级别的程序。 通信需求与 调度开锚 5 级 4 级 3 极 ：需卜t 级圈厂。 图2 4 现代计算机程序运行中的并行级别 并行性 程度 4 ) 子程序级：这一级与作业步和子程序级相对应，粒度规模一般有几千条指令。 作业步可重叠跨越各种不同的作业。子程序通常是在消息传递型多计算机上以 s p m d 或m p m d 模式调度给不同的处理机运行。但处理机的多道程序设计是在这一 级进行的。 5 ) 作业级：这一级对应的是在并行计算机上并行执行的独立作业，这一级粒度 在单个程序中可高达数万条指令。对于少量性能较高的处理及构成的超级计算机 来说，开发这种处理度并行是切实可行的。 1 0 爱 度 拉 枉 中 粗1， 、， 器图 势孬静基鹚辩稿爱疰弱 负载平衡 一个并行程序执行的总时间取决于最后一个完成的任务。若总的串行时间为 薯，分为n 令经务，每个逡穗戆魏嚣霹阕为墨n ，爨慈戆势嚣嚣霾凳墨屈，这是受 载平衡时获褥的最短时间。但若有一个进程需要的时间为2 t n 时间，则总的时 间为2 t n ，熊他进程提前完成也无济于事。负载平衡就是使各进程所需的时间 大致相等，或学说是各个炱b 理机的工作鬣大致相等。 莠幸亍开绢 并行开销是为了组织一个程序并行执行，由程序员或系统引入的开销。要力 求使并行开销最小，但不可能完全没有。歼销主要有任务创建，调度和同步通信 孽| 起懿。 加速比 并行是一种优化技术，用来缩短程序运行的墙钟( w a l lc l o c k ) 时间，也称消 逝( e l a p s e ) 时间。设一个穰序串行执行的墙钟时间为t 。，：箨 亍执行螅壤钟时阀为 墨，羽该稷彦势行撬孬豹麓逮魄为： $ p = t j i p 设t 。为个程序中必须串行执行的部分的串行执行时间，t ，为可以并行执杼 部分的串行融间，璺| jt f t k 。叉设处瑷爨数为n ，煲g 在不考虑开镄嚣孛有： 令k + 锄 又设f 为可以并行部分的串行执行时间占整个獠胯串行执行时间的百分比， 即并行化率，有： 暑= 螺： t 产f i ： 妊( 1 - f 风 这样，不计开销，并行程序的理论加速比为： s t = 露孓 = t j ( t s + t p n ) - 1 【( 1 一o t , + ( f r o 1 = t s 瓜 ( 1 - f ) + f n 】 = h o - o + f n 1 这裁是著名魏豳d a h l 定律。它说赘了宅谖臻了纛净孛霹著行部分与整令运 行时间之比对为n 速比的影响。当处理技术足够多时，f n o ，所以此时有： s 产1 ( 1 - 0 即当程序巾的串行成分一定对，即使在增加处理椒瓣数耳，搬逮眈也不会无 黻增燕。 效率 一个并行算法有好的加速比并不能说明处理器的利用率高，特别是处理机数 瓣不圈定时，掰戳弓| 入算法效率懿概念，瞧揍为评癸舞法毽糍魏一个指标。宅量 艘了每个处壤器有效使用部分占总执行时间的百分眈。并行算法的羧率可定义为 1 1 并行的基础知识及应用 算法的加速比同处理机数目之比1 ，即 e ，= s 。p 若一个并行算法的s 。= p ，e p = 1 ，则称这个算法是最优的并行算法。这是理想情 况，但实际上是不可能的，引起加速比减少的原因在于：算法中并行度不高；缺 乏负载平衡；通信访存冲突以及同步的时间开销。 可扩展性 是并行算法在多大程度上能有效利用增减的多处理机的一个量度。随着处理 机的增加，如果效率曲线基本保持不变，或者略有下降，则称该算法在所有的并 行机上拥有良好的可扩展性：如果效率曲线下降很快，则称可扩展性差。 影响一个并行算法的可扩展性的因素很多，如计算方法、粒度、加速比、效 率、并行系统与通信开销等，评判的标准也不禁相同。对于用m p p 与网络分布式 环境作大规模并行计算而言，效率对并行算法的可扩展性至关重要的。 2 4 并行算法模型 在使用并行计算机解决一个实际问题时，并行算法的设计是很重要的，而且 最终他要成为一个由程序实现的结构依赖性的算法。这就需要一个抽象的并行计 算机结构来作为研究高效的结构依赖性算法的基础，以保证所设计的并行算法适 应广泛的并行计算机结构，并能依照抽象的结构来分析并行算法的效率，从而指 导与并行机结构相匹配的并行算法设计。 2 4 1 p r a m ( p a r a l l e l r a n d o ma c c e s s m a c h i n e ) 模型 1 2 j 根据处理器实现同步的不同特点，p r a m 模型又分为s i m d - p r a m 模型和 m i m d p r a m 模型。 s i m d - p r a m 模型由控制部件、p 台功能相同的处理机pe l ，p e 。，p e 。和 一个容量无限的共享存储器m 组成。每台处理器有自己的局部存储器( l m ) 。 s i m d p r a m 的每步计算中，任意处理机均可通过共享存储器的共享单元同其他处 理器交换数据。为解决处理机间读写冲突，人们按照处理机对共享单元存取访问 的不同约束条件进一步将s i m d p r a m 模型分为一下三种。 i e r e wp r a m ( p r a m ，e x c l u s i v er e a de x c l u s i v ew r i t e ) 模型每次只允 许一台处理机读或写某一共享单元内容，简记为s i m d e r e wp r a m 。 i i c r e wp r a m ( p r a m ，c o n c u r r e n tr e a de x c l u s i v ew r i t e ) 模型每次允许多 台处理机同时读同一共享单元里的内容，但只允许一台处理机向某一单元写 内容，简记为s i m d c r e wp r a m 。 i i i c r c wp r a m ( p r a m ，c o n c u r r e n tr e a dc o n c u r r e n tw r i t e ) 模型每次允许 多台处理机同时读、写同一共享单元里的内容。简记为s i m d - c r c wp r a m 。 茎翌垫董整墅篓茎壅墨一一 m i m d p r a m 模型 m i m d p r a m 模型由p 个控制部件、p 台处理机和一个容量无限大的共享存储 嚣麓缝残，镪台楚理掇奏鑫己戆蜀部存德器猿，量务垂完盛叁蠢豹子任务。农 究成整个任务期间，各处溅机之间通过共享存储器中的全局变量窳现同步与通 信。 m i m d - p r a m 模型按照不弼豹互联网缕擒又分为下灏3 静模型： i 。透过总线访闻全弱变量豹m i m d 模爱，篱记& m i m d - b u sp r a m ： i i 通过交叉开关访问念局变量的m i m d 模型，简记为m i m d c bp r a m ； i i i 通过多级互联网络访问全局变擞的m i m i ) 模型，箍记为m i m d b u sp r a m ： p r a m 援黧戆特轰是：备筵理穰共攀一令垒蜀存镶器，囊翅荚攀全是变量避 杼信息交换；每个处理机w 在单位时闯内访问共享存储器的任意存储单元；处理 机的个数有限绒无限；局部存储器容量较小；简单好用。 p r 趣模溅不足之处；馊嗣了全局处理器，且局谨褰量小，不怒以接述分礤 移髓多娃理懿鹣往黥蓬颈；不能反映溪嶷串缀多系统瀚异步瞧；要求处理梳闻逶 倍无延迟、光限带宽和无歼销；对并行任务的增大不加限制。 2 4 2l o g p 横塑n 3 1 该模黧充分说明了互联鼷络的性能特征，涉及掰嘲络结梅。模熬主要有戬下 四个参数加以描述： l ( l a t e n c y ) 原处理枫与目的处理帆进行消息通信所需要的等待或延迟时 润静上羧# o ( o v e r ) 处理机准餐发送或准备接收每个消息的时间开销，柱这段时间里 处理机不能执行其他操作； g ( g a p ) 一台处理飒逐续两次发送蠛连续两次接牧溶塞熬最小辩闼闰隔， 其倒数为鼢理梳的通信带宽。 p ( p r o c e s s o r ) 处理机个数。 l o g p 模型的特点：抓佼了网络与处理机之间的蚀熊瓶颈；处瑷机淘异步工 终，荠逶遂楚壤瓿蓠豹澄惑转送来完成鬻步；对多线稷装本毒一定瓣菠浃；溃惑 娥迟不确定，憾延迟不大于l ，即任何消息经历的等待时间是不可颥禊4 的，但在 没有阻塞的情况下，最大不超过l ；鼓励编程人员采用一些好的策略，如作业分 溅，计算与道绥重叠以及乎筏逶售模式镣；可班颓 砉算法豹实骣运程靖闼。 己。驴穰黧豹不是之憝：对网络中通僚模式盼描述不够深入；奎要是用予消 息传递算法设计，对于共事存储模式，则简单的认为媛地读操作相当于两次消息 传递，未考虑流水线预取技术、c a c h e 引起的数据不一致性以及c a c h e 命中率对 诗簿熬影璃；蘧乏考惑多线程技术弱上下文舞销；缓设爱点蹲点溃患路瞧器遗孬逶 茎堡塑苎堡! ! 垫望墨壁里 信，这增加了编程者考虑路由器上相关通信操作负担。 2 4 3c 3 模型【1 4 1 他是用于粗粒度并行系统，可将算法分为多个超步，在两个超步之间有同步 操作。c 3 模型主要由以下5 个参数加以描述： p 处理机的个数； h 网络延迟； b 网络的对分宽度，即将网络分成2 个字网络是所需断开的处理机连接个数； s 启动时间，即建立一个消息时的开销； l 消息报的长度，即消息报所含字节数。 c 3 模型假定处理机