关键词:
并行编程(精选五篇)
并行编程 篇1
1 数据流语言
由于汇编语言中都是直接操作处理器的寄存器,随着处理器硬件的发展,嵌入式工程师和相关编程人员通常都是直接根据硬件结构进行编程,嵌入式编程基本保持着按顺序逐行方式进行编程,因此大多数都停留在微处理器上单线程顺序。数据流编程语言是为了适应多核CPU进行并行处理时编程所适用的语言,它不仅能简化多内核处理器开发过程,而且还能够充分地发挥多内核CPU的优势。现代编程语言已经提升了其抽象层次,除了人工线程操作外,还提供基于任务的API和并行结构。
2 编程过程
由于大家习惯于单线程的编写程序,都是按照顺序语句编写,以流程图为依据然后分别进行编写对应的判断语句或不同的分支语句。但是数据流程序的编写却是以程序执行图进行检测并对应地址进行编译,所以编写的过程和应用范围都存在很大的区别。
2.1 流程图
流程图的处理过程是许多工程师针对某项应用展开研究的过程方法,然而普通流程图并不能按照CPU架构进行处理的顺序,当编程人员需要直接解决想要解决的问题时,都是集中精力于操作数据需要的算法上,以及这些算法之间的从属关系,而不是用直观可视方式表达并行过程。如果编程人员将所有流程图部分都转换为顺序语句让CPU去执行,将会极大地浪费CPU的运行时间,并且运行并行任务时相当困难。
2.2 编程应用
编写数据流的应用程序不但可以用文本方式编写(如VHDL语言),同时还可以用图形方式来表达,能够以最清晰的方式向编程人员表达数据之间的关系和并行机制。比如一个基本算术操作的源代码为:
结果=((B*C)+A)/(D-E),它可以用LabView数据流语言编写的程序如图1所示。从图形化数据流表达方式发现并行操作的直观性能够让编程人员快速判断程序元素之间的相互间的关系。智能编译器可以将源代码示意图中的各个部分划分成独立的小部分,然后分配给不同线程进而在多内核处理器上执行。
2.3 智能编译
解决数据流的方案是使用智能编译器检测并行机制(图2)。数据流编译器可以自动识别代码中的并行部分,然后选择最佳调度顺序型CPU指令,它能让开发人员集中精力解决手头的问题,而不再去考虑如何处理硬件问题。
此外,数据流源代码还可以包含信号处理算法、库调用以及大多数编程语言中常见的其它结构和操作。如今越来越多的编程语言都在增加数据流扩展功能,为数据流并行编程带来相当大的益处。现在不管是否只有两条并行路径的小程序,还是具有上百条并行路径的大程序,都可以利用数据流编程语言的固有并行机制,以便充分发挥多内核CPU硬件的优势。
即使编译器能够自动将数据流代码映射到并行处理器,但是并不能排除开发人员的责任。基本的并行编程技术,如任务并行机制、数据并行机制和管线,可以用数据流代码来实现,而优化过程取决于具体的数据流编程工具,但是也需要依赖人工线程和同步化的支持。
3 适应性
当前被广泛使用的并行硬件设备如:现场可编程门阵列,它可以使用像VDHL和Verilog等硬件描述语言通常用于对FPGA进行编程,它需要开发人员规定逻辑算法和数据依赖性。数据流语言是通过直接访问存储器,把并行代码部分自动映射到多内核CPU,它是通过赋值方式来进行访问。因此可以让编程人员以较小的代价来充分发挥并行硬件的优势,然而同时也会增加应用程序对存储器的占用量,所以数据流编译器会通过尽量减少对存储器的占用量。由于数据流语言与流程图之间存在着众多的相似性使得它们更容易学习和使用。
4 缺陷
数据流语言同样也存在缺点,因为数据流范例与传统顺序语言有很大区别,习惯于顺序语言的编程人员必须克服常规思维方式,而采用曲线顺利过渡到数据流语言。例如,像Lab View等数据流语言可以采用不同的方式输入现有的C代码甚至.m文件脚本,以便充分利用曾经掌握的大量现有代码的复用。
5 结语
随着多内核CPU的快速发展,究竟使用哪种编程语言能够充分发挥CPU的效率呢,机构或独立的编程人员都应认真看待数据流,并把它作为多内核编程的潜在解决方案。全世界对CPU的发展都是日新月异,从双核到多核,因此要想充分发挥CPU中每个核的效率,开发人员不能停留在固有的编程方法,比如利用数据流的编程方法以适应社会的发展,才能在充分利用CPU的同时减轻并行编程所带来的痛苦。
摘要:由于当前硬件的开发逐日增加,为了充分发挥这些硬件的功能,通过介绍数据流编程语言的应用方式,一同介绍了数据流语言所充分利用的类似流程图的用法。利用智能编译器进行检测程序过程,陈述了与硬件地址相结合的编程方法。这种方法极大地简化了开发人员编写多线程程序的难处,同时能够充分发挥多核CPU的效率。
关键词:并行编程,多核处理器,数据流
参考文献
[1]夏妍,郝忠孝.基于聚集块的多用户连续K最近邻多线程查询[J].齐齐哈尔大学学报(自然科学版),2010(06):16-20.
[2]刘玉,胡晖,仇宾.基于Java多线程的聊天室程序[J].电脑编程技巧与维护,2010(21):20-21.
并行编程 篇2
关键词:混合同步,事务内存,同步优化,OpenTM
多核架构是实现计算处理速率高速增长的必然趋势,当程序被多个处理器并行执行时,需要必须的同步机制保证程序在数据竞争时能够得出正确的结果,并且在适当的时候控制线程的执行顺序。在共享内存并行编程中,目前使用广泛的同步机制主要是互斥锁与事件组成的混合同步和事务内存两种同步机制。
针对锁和事件同步暴露出的一些缺点,比如主副线程切换、非必要线程等待等浪费大量的系统资源和时间,有学者提出一种基于数据相关性的同步优化算法[1],可以消除基本块当中的冗余同步。面对传统并行程序设计中锁机制的缺点,文献[2]扩展Open MP,提出一种面向事务存储的Open TM应用编程接口,避免锁机制可能会导致阻塞式等待和死锁等问题,文献[3]提出面向Open TM应用的并行数据重用理论,体现事务内存保证数据的准确性能优越。文献[4,5]通过研究互斥锁和事务内存的语义和逻辑架构,并算法验证并行程序的软件事务内存同步机制。
基于以上理论研究,首先对混合同步进行优化, 调整程序同步方法结构,提高并行程序运行效率。 其次,优化事务同步框架,消除不可回退行为造成系统的安全威胁。最后,将对这两种同步机制优化进行分析,并提出共享内存并行编程最优同步方法。
1同步机制
1.1混合同步
Open MP标准支持两种不同类型的线程同步, 一种是互斥锁,另外一种是事件通知。互斥锁的操作针对需要保护的数据而言,在产生了数据竞争的内存区域加入互斥,包括critical、atomic等语句以及mutex函数,即对某一块代码操作进行保护,以保证同时只能有一个线程执行该段代码。而事件机制则是通过同步屏障( barrier) 、定序区段( ordered sections) 和主程序执行 ( master) 等预处理器指示符声明来控制规定线程的执行顺序,调度多线程完成指定任务。
混合同步给并行编程带来极大的方便,拥有锁和事件同步的优点。例如,锁同步方式被编程人员所熟悉,并行编程效率高,而且锁保护的操作类型比事务内存多[4]。事件同步方法语义简明,线程调度明确,逻辑结构清晰。
然而,无论是互斥锁同步还是事件同步,它们都需要开发人员在源代码中加入专用的指导语句,使得多核并行编程复杂度提高。同时,在锁同步进行复杂并行编程的过程中也暴露了许多缺陷,比如当多个线程因相互争夺对方资源,而导致阻塞,可能导致死锁。事件同步一些同步操作会使得空闲线程处于等待状态,导致系统总体运行效率不高。
1.2事务内存同步
事务内存是数据的集合,程序开发者只需要将事务内存的操作封装为事务,无需考虑复杂的同步问题,事务内存系统负责正确执行事务。Open TM是在Open MP标准上,引入事务内存语义,从而提出了一种面向事务存储的应用编程接口[3]。当程序检测到数据不匹配或者程序冲突时,通过abort( ) 废除当前事务并由retry( ) 回滚到事务开始处重新执行。实现构件transaction可以在Open MP并行区内使用[2],语法如图1所示。
与混合同步相比,事务内存同步方法性能更优。首先,事务内存同步具有事务的原子性和隔离性,即一组内存访问操作要么提交要么夭折,而且不同组操作之间没有影响,因此可以避免死锁。其次, 事务内存同步能为并发编程提供细粒度的并发,而使用锁同步方法则需要设计更为复杂的细粒度算法[6]。最后,事务内存同步的实现可以是非阻塞的,所以线程在执行时如果发生延迟或者异常终止时,不会导致其他线程的阻塞。
尽管事务内存具有原子性和隔离性,但是事务的概念决定事务内存并不完美,尚存在一些问题有待解决,例如事务中不能支持类似系统调用等行为, 一旦执行则可能难以取回已经释放的资源。
2同步优化
2.1混合同步优化
针对混合同步机制中可能存在的锁竞争和系统多线程利用率不高等问题,现采取一种将并行区域整合和扩展的方法对程序结构进行改进,主要对锁和事件通知分别进行优化。
首先,锁保护的代码只允许一个线程执行,这导致其他线程处于空闲状态,而且在一些应用比如科学计算中代码可能会被执行千万次,创建、销毁锁都耗费大量的系统资源,因此可以选择使用临界区和事件同步指导语句master/single取代锁同步。然而,不是所有的锁都能被替代,临界区虽然比较节约线程上下文切换带来的系统开销,却只适用于同一个进程内。master语句要求代码只由主线程来进行,single表示只有一个线程执行一次,因此它们只能在特定的场合取代锁同步[7,8]。
其次,事件同步给并行编程带来极大的便利,各种编译指导语句可以组合使用,如果使用得当可以大大提高程序执行的效率。而且,在每一个并行结构( omp parallel) 和工作共享结构( omp for) 的结束都隐含着一个barrier同步点,要求所有线程必须执行完成调度任务,才能继续向下执行。这种非必要的线程等待既浪费系统多线程资源,又影响程序执行效率,因此采用基于数据相关性的优化方法来消除barrier同步。
图2是并行编译生成的一个Open MP程序片段,包含三个并行区域,而且区域之间存在关联。然而,并行区域中d的循环计算与前一区域无数据相关,故可以将d的计算模块合并到第一并行块中。 同理可推广将第二、三并行块合并。并行区域合并后,程序结构逻辑更加严密,同步次数减少。
图3是并行程序中常见的并行与串行过渡的程序片段。串行区域嵌套在并行区域之间,而且区域之间相互独立,因此扩展并行区,整合成一个大的并行区域,同时采用#pragma omp master语句替换锁保护操作,调度主线程完成串行计算,并消除冗余的同步,调度其他线程执行其他任务。然而,当串行计算与并行区之间存在数据相关时,相应的barrier用于保证所有线程完成任务后才执行后续代码,从而保障数据安全。
综上所述,程序结构能够调整有两个必要条件: 第一,并行区域至少存在两个数据不相关的并行计算代码块; 第二,至少存在一个与串行计算数据独立的并行计算代码块。因此,得到并行区域合并和整合的总体框架,如图4所示。该结构中存在多个并行区域和串行区域,采用并行区合并和扩展的方法,将程序整合为一个#pragma omp parallel并行计算结构,同时对数据相关的计算模块进行同步保护, 保证数据的准确性。
2.2事务同步优化
事务内存同步机制的优点是事务程序执行过程中如果出现异常,则返回事务最开始处重新执行,直到事务完全正确被执行。然后,当程序中包含一些比如I/O操作和释放系统资源等行为时,事务的回退行为无法消除这些行为产生的影响,最终导致同步失败[9]。目前对含有这种不可恢复操作的事务一般有两种处理策略,一是使用缓冲技术[10],二是使所有的事务转为顺序执行[11]。
根据之前对锁的理论分析,锁同步能够保护事务不可恢复的行为,因此考虑对不可恢复的代码块操作采取加锁同步保护。虽然引入的锁机制可能会带来存在死锁的威胁,但是事务内存同步的原子性和隔离性保证程序正确执行,很好地解决了这种潜在问题。其次,一个事务代码可以拆分为多个小的事务,这样虽然使得程序结构更加复杂,但是在某种意义上却可以提高事物的安全性。
基于以上研究,事务结构优化伪代码如图5所示,事务程序运行时,线程进行数据计算,当遇到I/ O端口数据读或者存储以及释放内存等资源的行为时,采取锁同步方法,同时通过冲突检测结果来判定是否需要回滚。检测通过时,线程继续执行代码,并且越过不可回退代码重设事务回滚操作起点。
提出一种保护不可回退行为,并且规划子事务结构的方法,完善事务内存同步机制,可以避免事务同步因不可恢复行为对系统造成的影响,保证程序执行结果的准确性。
3最优同步方法及实验论证
Open TM并行编程接口规定不允许在事务中使用Open MP同步构造,比如critical,atomic,mutex和barrier等,同时在Open MP同步构造中使用事务同步会违背强隔离性[2],但此前提是事务之间存在关联联系,即一个事务内处理的是另一事务相关的程序数据,这种情况的事务不符合并行处理要求,应依次执行。因此,考虑多核多线程并行运算的优势,结合混合同步中并行区域合并和扩展的方法和事务特性的优点,设计出基于共享内存的最优同步方法,如图6所示。
首先,无论是数据并行还是任务并行,都可以将需要处理的程序归于一类事务,即利用#pragma omp transaction指导语句进行事务的定义与处理,结合2. 2节中提出的事务内存优化方法完善同步机制,优化回滚操作对系统的影响。其次,结合2. 1节中提出的并行区域合并和扩展的优化方法,根据事务之间数据关联关系,对事务结构进行并行区域合并和扩展,节省线程调度时间,加快程序的执行效率。
在结构上,此同步方法的保障数据准确的性能比混合同步更优,同时比事务内存同步的线程利用率要高,还解决了事务机制中回滚操作可能存在重大威胁。在功能上,兼具混合同步机制高效的特点和事务同步编程简单、程序出错概率小的特点,是一种高效又方便的并行编程同步方式。
为了验证此同步优化方法的可行性,本文采用包括多个并行和串行代码块的程序集作为实验的测试程序,部分循环计算代码块之间存在数据关联,程序并行数据包括循环结构和主线程任务。实验平台为双核处理 器,主频2. 1 GHz,实验结果 如表1所示。
实验结果表明: 优化后各个程序段执行速率得到优化,整个程序集的运行效率较优化前有改善。 本文讨论并设计了一种结合混合同步和事务内存的优化方法,采用并行区合并与扩展的方法改进程序结构,同时结合事务特性,旨在提高程序的执行效率和完善事务内存机制,实验结果证明程序集运行效率有提高,论证此同步方法的可行性。
4结论
研究混合同步和事务内存两种基于共享内存并行编程的同步机制,通过研究发现两种同步方式存在一定的互补性,因此本文在Open TM同步机制中分别对事务结构内、外两方面进行分析与优化,优化后的Open TM同步机制兼容两者的优点,同时避免了两者的缺点。实验结果表明,在并行编程中,优化后的Open TM同步机制对程序的执行效率有改善作用,性能比混合同步等同步机制优越,是目前基于共享内存并行编程的最优同步方法。
参考文献
[1] 张平,赵荣彩,李清宝.基于相关性的同步优化算法.计算机工程,2006;31(17):68—70Zhang Ping,Zhao Rongcai,Li Qingbao.Synchronous optimization algorithm based on correlation.Computer Engineering,2006;31(17):68—70
[2] Baek W,Minh C C,Trautmann M,et al.The Open TM transactional application programming interface.Parallel Architecture and Compilation Techniques,16th International Conference on,IEEE,2007:376 —387
[3] 吴俊杰,杨学军,刘光辉,等.面向Open MP和Open TM应用的并行数据重用理论.软件学报,2010;21(12):3011—3028Wu,Junjie,Yang Xuejun,Liu Guanghui,et al.Parallel data reuse theories for Open MP and Open TM applications.Journal of Software,2010;21(12):3011—3028
[4] 付明.低级并行代码中几种同步机制的验证.合肥:中国科学技术大学,2009Fu Ming.Validation of Several synchronization mechanism of low-level parallel code.Hefei:University of Science and Technology of China,2009
[5] 李勇.基于软件事务内存的并行程序验证.合肥:中国科学技术大学,2011Li Yong.Validation of parallel program based on the software transactional memory.Hefei:University of Science and Technology of China,2011
[6] 贾建斌,黄春,赵克佳.事务存储并行程序编程接口研究.计算机工程与科学,2010;32(11):136—140Jia Jianbin,Huang Chun,Zhao Kejia.The research of transaction memory store parallel programming interface.Computer engineering and science,2010;32(11):136—140
[7] 戴晨,陈鹏,杨冬蕾,等.面向多核的并行编程和优化研究.计算机应用与软件,2013;30(12):198—202,279Dai Chen,Chen Peng,Yang Donglei,et al.Research of parallel programming and optimization for multicore.Computer Applications and Software,2013;30(12):198—202,279
[8] 王堃.基于多核的并行程序设计及优化.南京:南京大学,2012Wang Kun.Design and optimization of parallel programming based on multi-core.Nanjing:Nanjing University,2012
[9] Mc Kenney P E,Michael M M,Triplett J,et al.Why the grass may not be greener on the other side:A comparison of locking vs.transactional memory.ACM SIGOPS Operating Systems Review,2010;44(3):93—101
[10] Nakano J,Montesinos P,Gharachorloo K,et al.Re Vive I/O:efficient handling of I/O in highly-available rollback-recovery servers.High-Performance Computer Architecture.The Twelfth International Symposium on,2006:200—211
并行编程 篇3
SMP集群是目前国内外流行的并行计算机体系结构之一,它具备节点间分布存储和节点内共享存储的两级内存层次结构,提供了节点间和节点内的两级并行。在设计并行程序时如果同时考虑两种结构的特点,充分利用结构所提供的两级并行性,采用分布内存和共享内存相结合的编程技术,可获得更好的加速比和运行效率。分布内存并行程序设计主要采用消息传递机制,编程模型有消息传递接口(MPI)和并行虚拟机(PVM)等;共享内存并行编程可采用多线程机制(如POSIX)和编译制导(如OpenMP)[1]。混合编程模型是专门针对SMP集群提出的,它将这两种并行程序设计技术结合在一起,充分利用了SMP集群的两级内存层次结构特点,节点间采用分布式存储的消息传递进行通信,节点内利用共享存储进行通信,实现消息传递和共享变量编程的混合。
近年来,三维网格模型在几何建模、计算机图形学等领域得到广泛应用,寻找任意两个顶点间最短路径问题是三维网格模型的基本计算问题。而随着三维网格模型规模的不断扩大,对最短路径问题的计算量和复杂度也急剧上升,时间开销不断增大。将最短路径问题的并行求解在SMP集群平台下实现,可以通过利用SMP集群的两级并行特性来提高并行算法的效率。因此,本文对SMP集群上的粗粒度MPI并行算法进行改进,采用了节点间粗粒度MPI并行和节点内细粒度OpenMP并行的多粒度混合编程方法求解三维网格模型上的最短路径问题。实际性能测试表明,该三维网格多粒度混合并行算法在运行时间方面明显优于原来的粗粒度MPI并行算法,具有更好的加速比和执行效率。
1 SMP集群
1.1 SMP体系结构
SMP集群体系结构如图1所示。图1中显示了具有N个节点(每个节点为2个CPU) 的SMP集群体系结构,图中P/C指的是SMP节点中的处理器(Processor,即CPU)和该处理器的局部高速缓存(Cache)。在SMP中,多个处理器通过总线或交叉开关连接起来,并通过它们访问共享的内存区域和I/O设备,因而SMP具备均匀存储访问UMA结构,并有单一物理地址空间和处理器间低通信延迟的特性。SMP集群通过通信网络(例如Myrinet、以太网或高性能开关)把多个SMP节点连接起来,并且节点间可以通过消息传递进行通信[2]。
1.2 SMP集群的特点
1) 每个节点是一个SMP ,都可以作为独立的一个计算机系统来使用;
2) 每个节点上有一份独立完整的操作系统;
3) SMP集群具有两级存储机制:节点内共享存储和节点间分布式存储;
4) 两级的存储机制决定了SMP集群有两级并行机制:节点内为单地址空间的共享变量编程模型,而节点间为分布式存储的消息传递编程模型。
2 SMP集群混合编程模型
分布式存储体系结构下的并行编程模型主要有消息传递编程模型,它的特点是多地址空间、编程困难、可移植性好,其实现标准有MPI、PVM等。共享存储体系结构下的并行编程模型主要是共享变量编程模型,它具有单地址空间、编程容易、可移植性差等特点,其实现标准有OpenMP和Pthreads等。SMP集群因为同时兼顾了计算性能和可扩展性的两方面,已经成为并行计算机体系结构的主要发展趋势。由于SMP集群同时具备共享存储体系结构和分布式存储体系结构的特点,传统的共享存储体系结构和分布式存储体系结构下的编程模型已经不再完全适用于它,需要给出一种新的编程模型来综合利用这两种模式的优点。
2.1 混合编程模型的实现机制
SMP集群混合编程模型的实现机制有很多种。SMP集群的节点间是分布存储,无疑消息传递模型MPI是分布存储编程的最佳选择。节点内的共享存储编程机制分别有Thread和OpenMP两类,Thread代表所有直接利用线程来实现节点内的并行化计算的模型,例如Linux Threads或POSIX Threads;OpenMP是基于编译制导的共享存储编程模型。因此,有两类混合编程机制:Thread(节点内)+MPI(节点间)和OpenMP(节点内)+MPI(节点间)两类。
2.2 两种混合编程模型比较
编程模型的选择主要取决于易用性与否和计算性能的好坏,从这两个角度分析OpenMP+ MPI优于Thread+MPI[2] 。主要原因是OpenMP和Thread都是由操作系统支持的线程实现,OpenMP直接提供了大量的并行操作语句,封装了线程的同步和互斥操作,而使用Thread模型时却还要考虑繁杂的线程间的同步和互斥,易用性远远不及OpenMP;另外Thread模型是一种低级的方法,它一般使用库方法,而不是编译制导法,这种方法会妨碍编译优化。综合权衡各种因素对程序性能的影响,OpenMP+MPI是更适合于SMP集群的混合编程模型。
3 MPI+OpenMP混合编程模型
MPI和OpenMP具有很大的互补性,为充分利用硬件分布/共享内存层次系统结构可以将这两种编程模型相结合,实现MPI +OpenMP混合并行程序设计。
3.1 分布式存储编程模型MPI
MPI是由学术界、政府和工业协会共同开发的消息传递编程模型的实现标准,具有可移植性好、功能强大、效率高等优点,特别适用于粗粒度的并行。MPI的优点是实现进程级并行,允许静态任务调度,提供明确的并行机制,通常可获得较高的性能;提供了多种点对点和组通信库函数,可根据实际问题的需要选择最优的通信模式。 MPI的缺点是程序设计中需要程序员完成任务和数据的划分及分布,应用的开发和调试难度较大;消息传递的开销非常大,需考虑尽量减少通信延迟;串行程序到并行程序的转化难度大,需做大量的代码修改;动态负载平衡困难等。
3.2 共享存储编程模型OpenMP
OpenMP是共享存储系统编程的工业标准,它具有简单、移植性好和可扩展等优点。OpenMP定义了一个由编译制导、运行时库函数和环境变量构成的集合,用来描述共享内存的并行机制。OpenMP的优点是实现线程级并行,线程间通信通过读/写共享变量实现,编程相对简单,充分利用了共享存储体系结构的特点,避免了消息传递的开销;将串行程序转换为并行程序时无须对代码作大的改动;更好地利用了共享内存体系结构,允许运行时调度,并提供了细粒度和粗粒度并行机制。其不足之处是只能在共享存储结构的机器上运行;数据的放置策略不当可能会引发其他问题;并行化的循环粒度过小会增加系统开销等[3]。
3.3 MPI+OpenMP混合编程模型的实现
混合编程模型通常采用层次结构,上层的MPI表示节点间的并行,下层的OpenMP表示节点内的多线程并行。这种模型的实现首先对问题进行MPI分解,将任务划分成通信不密集的几个部分,每个部分分配到一个SMP节点上,节点间通过MPI消息传递进行通信;然后在每个进程内采用OpenMP编译制导语句再次分解,并分配到SMP的不同处理器上由多个线程并行执行,节点内通过共享存储进行通信。图2描述了SMP集群上MPI+OpenMP混合编程模型的实现机制。
从图2中可知,在每个节点上只有一个MPI进程,首先对该进程初始化,然后每个节点上的MPI进程可以独立作一些局部计算,需要时也可以进行节点间的通信。MPI进程内的主要计算部分(通常是循环部分)采用OpenMP多线程并行求解;在OpenMP求解部分结束后,MPI进程也可以做局部计算、通信或同步;当全部计算工作结束后MPI进程结束。虽然程序中混合了两种模式,但调试时对MPI和OpenMP分别跟踪调试。OpenMP的线程级并行具有较小的延迟,可缓解纯MPI实现带来的网络延迟,同时混合编程还可以优化I/O等资源的使用。
4 三维网格多粒度混合并行算法
4.1 并行化粒度
MPI适合在多节点之间的粗粒度通信,本文采用SPMD的编程模式。而节点内的OpenMP多线程并行具有粗粒度并行化和细粒度并行化两种方法。粗粒度并行化是指OpenMP编译制导指令使用在程序的最外层,首先在主程序中生成多个线程,每个线程类似于SPMD编程模式中的一个进程,使用这些线程就类似于使用SPMD编程模式中的进程,它们均执行相同的代码段,操作在各自不同的数据上。细粒度并行化是指利用OpenMP只并行求解循环部分的计算,又称为循环级并行化。细粒度并行化的方法是在需要用多线程求解的原串行代码中的循环代码段外插入OpenMP的编译制导指令,例如PARALLEL DO等,对串行代码中的其它代码则不并行化。
粗粒度并行使用的编译制导指令较少,并行化通信与调度开销小。但这种方法除了省去数据分配的操作外,程序员使用多线程等同于使用MPI的多进程,编程的复杂度和难度大大增加,而且当混合模型的两级并行机制一同使用时,这种编程复杂性将更大。细粒度并行化比粗粒度并行化的工作量大大降低,只要在循环计算外使用OpenMP编译制导指令并行化即可,而且可以容易地对已有MPI程序的循环做OpenMP多线程并行化。基于这些因素,节点内OpenMP编程采用细粒度并行。因此多粒度混合是指节点间采用MPI粗粒度并行,节点内采用OpenMP细粒度并行。
4.2 三维网格多粒度混合并行算法的实现
求解最短路径问题是三维网格计算中的基本计算问题,有多种三维网格模型上的最短路径算法[4,5],而本文此处采用类矩阵相乘的数值并行算法实现[6]。该算法的实现包括如下四个基本过程:(1)读取初始数据;(2)根据一定划分原则分配数据到各处理器;(3)各处理器并行更新最短路径;(4)汇总数据。上述算法的实现过程包括节点间通信和各节点并行计算两部分,对于需要在各计算节点间传递数据的通信过程采用节点间MPI消息传递编程模型。而对于算法中占大部分计算时间的路径更新过程采用节点内OpenMP细粒度并行编程,这是因为该路径更新过程是通过循环实现的,OpenMP细粒度并行化就是针对这类计算量大的循环进行,OpenMP多线程并行执行会大大提高整个算法的运行效率。此外,算法过程中也有其他循环,但是考虑到循环并行化会带来调度的开销,对于计算量小的循环,我们放弃对它的并行化。下面给出三维网格多粒度混合并行算法的主要伪代码:
#include <mpi.h>
#include <omp.h>
……
int main (int argc, char *argv [])
{
……
MP_Init (&argc, &argv); /*MPI初始化*/
MPI_Comm_size ( MPI_COMM_WORLD,&numprocess);
MPI_Comm_rank (MPI_COMM_WORLD,&myid);
mpi_read_data(); /*读取数据过程(1),MPI消息传递*/
mpi_send_data(); /*发送数据过程(2),MPI消息传递*/
omp_set_num_threads (n); /*设置OpenMP线程数目n*/
#pragma omp parallel for private(i,j,k)
/*路径更新过程(3),OpenMP多线程并行*/
……
mpi_collect_data(); /*汇总数据过程(4),MPI消息传递*/
MPI_Finalize (); /*MPI进程结束*/
}
在上述伪代码中,OpenMP线程数目n的设置与每个节点内的处理器个数相同,我们的实验环境中每个SMP节点有两个处理器,因此OpenMP创建的线程个数为2。这样选择的原因是当节点内的线程数小于这个数值时,SMP的优越性没有发挥到最大,即加速求解的效果没有达到最大;而当线程数大于物理处理器数时,将会因为线程竞争总线带宽而导致性能下降。因此,当SMP节点内每个处理器上只启动一个线程时,效率最高[2]。
5 实验测试
这里采用的SMP集群为Dell PowerEdge 2850系统,每个节点机都有两个主频为2.8GHz的Intel Xeon CPU,内存为ECC DDR-2 SDRAM 2GB,每台节点机上均运行Linux RH9操作系统。本文在8节点SMP集群上建立了LAM-MPI+OpenMP混合并行编程环境。采用本文提出的节点间MPI粗粒度并行和节点内OpenMP细粒度并行的多粒度混合并行算法对三维网格求解最短路径问题进行实验,该程序在SMP集群环境上通过了测试。测试程序分别为粗粒度MPI程序single_mpi和MPI+OpenMP多粒度混合程序mix_mpi_omp,测试数据为891个顶点、1681个面片的蝴蝶三维网格模型,如图3所示。
表1表示粗粒度MPI程序single_mpi和MPI+OpenMP多粒度混合程序mix_mpi_omp的执行时间比较,图4给出这两种并行算法在节点个数分别为1、2、3、4、6、8时的加速比(每个节点为2个CPU)。加速比的求解使用Liu等定义[7]的适合SMP集群的加速比公式:S=Tparallel(1_node)/ Tparallel(N_node),表示一个节点并行执行时间和N个结点并行执行时间的比值。
从表1可以看出,采用MPI+OpenMP多粒度混合并行算法的执行时间要少于粗粒度MPI并行算法,一方面是因为混合编程更充分地利用了CPU的处理能力,并且有着更小的通信开销;另一方面是因为多粒度的程序设计方式提高了并行的加速比。图4表明MPI+OpenMPI多粒度混合并行算法的加速比明显好于粗粒度MPI并行算法的加速比,并且随着节点个数的增加,二者加速比的差距也加大,这表明MPI+OpenMP多粒度混合并行算法有着更好的执行效率和可扩展性。
6 结 论
目前,SMP集群的多层次并行体系结构计算机已成为主流的高性能计算平台,MPI+OpenMP这种混合编程模型相比于单纯的MPI消息传递编程模型更能充分发挥SMP集群节点的性能。本文给出的MPI+OpenMP三维网格多粒度混合并行算法就是利用了这种多层次体系结构的优点,同时解决了大规模三维网格并行计算时间开销过大的问题。实验表明,这种混合编程模式的并行程序性能要超过单一MPI编程模式的程序,并且具有良好的执行效率和可移植性。
参考文献
[1]李清宝,张平.基于分布/共享内存层次结构的并行程序设计[J].计算机应用,2004(6).
[2]陈勇,陈国良,等.SMP机群混合编程模型研究[J].小型微型计算机系统,2004(10).
[3]单莹,等.基于SMP集群的多层次并行编程模型与并行优化技术[J].计算机应用研究,2006(10).
[4]孙晓鹏,李华.基于CSR存储的三维网格最短路径算法[J].计算机工程与应用,2005(10):5-7.
[5]张丽艳,吴熹.三角网格模型上任意两点间的近似最短路径算法研究[J].计算机辅助设计与图形学学报,2003(5):592-597.
[6]武亮亮,郑晓薇.基于三维网格的最短路径并行算法研究[J].计算机工程与设计,2008(5).
并行编程 篇4
传统串行编程模型已经无法实现多核处理器资源利用最大化[1]。OpenMP作为并行编程模型的解决方案,逐渐成为工业标准[2]。如何将OpenMP更好地应用到编程中解决多核处理器资源利用最大化问题,成为一个重要的研究课题。
1 串行编程模型与并行编程模型-OpenMP
传统串行编程模型下,程序线路自始至终是唯一的。即使使用多核处理器,程序依然只能利用单个核进行运算,这样势必造成其它处理器闲置,无法发挥多核处理器的性能。OpenMP的提出为解决这一问题提供了方案,其作为最早提出的并行编程模型,逐渐成为并行编程的规范[3]。OpenMP是面向共享内存以及分布式共享内存的多处理器多线程并行编程语言[4],是一种编译指导语句,能够显式地指导多线程、共享内存并行的应用程序编程接口(API),具有良好的可移植性,支持多种编程语言,如Fortran、C、C++。
OpenMP以线程为基础,通过编译指导语句显式执行并行化,提供并行化的完整控制。众所周知,Java语言也内置了对多线程的支持,然而Java中的多线程并不能完成计算机多个处理器同时处理。因为Java虚拟机采用时间片轮转的方式,根据计算机给定的时间段执行线程,该时间片结束后,Java虚拟机会迅速切换到另一个线程继续运行,整个过程中,Java多线程交叉串行运行。与Java多线程不同,当线程数量小于或等于处理器数量时,OpenMP每一个线程都拥有自己的处理器并进行运算,大大提高了处理器的利用率。OpenMP采用Fork-Join执行模式,如图1所示。
(1)开始执行时,只有主线程运行。
(2)在主线程运行过程中,需要进行并行计算时,派生出(Fork,创建新线程或者唤醒已有线程)线程来执行并行任务。
(3)执行并行时,主线程和派生线程同时工作。
(4)并行代码执行结束后,派生线程退出或者挂起,不再工作,控制流程回到单独的主线程中(Join,即多线程的汇合)。
2 大型稀疏矩阵转置
在微分方程数值解法中,线性代数方程组系数矩阵系数往往很高,但其非零元素所占的比重很小,将这种矩阵称为大型稀疏矩阵。大型稀疏矩阵转置数据运算量大,可以用一个三元组确定一个唯一矩阵元素,这个三元组分别表示非零元素的行号、列号和值。所有三元组构成一个三元组表,该三元组表是一个线性表[5]。
传统的串行编程算法中,假设存在待转置的稀疏矩阵M,首先找出矩阵M第i列所有元素,并转置,将结果存放到转置后矩阵N的第i行;再找出矩阵M的第i+1列的所有元素,并转置,将结果存放到矩阵N的第i+1行;依次执行,直到所有元素转置完毕。
3 并行优化
上述算法每一列转置运算都是独立的,假设运算程序的计算机为X(X>1)核处理器,若使用上述算法运算,将浪费X-1个处理器资源。本文设计优化思想为将每一列的矩阵转置运算分离出来,每一次使用X个处理器进行处理,实现计算机处理器利用率最大化[6]。
在实际设计与实现过程中,使用三元组实现大型矩阵存储,对三元组存储进行了压缩,使得在对三元组存储的矩阵进行转置时,需要使用第三变量作为连接进行转置。当使用OpenMP进行并行编程时,这个第三变量在转置运算中与其它三元组有数据相关性的。需要对该变量进行特殊的加锁操作,保证变量的唯一性,使程序正确运行,但该操作将对程序并行效率产生一定影响。
本文以多个数量级稀疏矩阵为对象(包括100K、1M、10M),横向研究同数量级的稀疏矩阵中,串行编程及基于OpenMP并行编程的计算机运算效率;纵向研究不同数量级运算量在基于OpenMP并行编程的计算机中的运算效率,进行纵向对比。研究基于OpenMP并行模型优化且进行加锁后,程序核心算法流程如图2所示。
理论情况下,双线程算法耗费时间应为普通算法的50%,而四线程算法耗时应为普通算法的25%,是双线程算法耗时的50%。实际操作中,100K数据量下,普通算法平均耗时为427.6ms;基于OpenMP优化后,双线程算法耗时为230.8ms,四线程算法为165.4ms,如图3所示。双线程算法耗时为普通算法的53.98%,接近理论值,而4线程耗时为普通算法的38.68%,是双线程算法的71.66%,与理论值相差较大。当数据量较小时,线程创建及销毁需要一定时间开销,四线程时间开销相对较大,导致计算机运行效率提高相对较低。
在1M数据下,普通算法平均耗时为10730.2ms;基于OpenMP优化后,双线程算法为6910.6ms,四线程算法为3856.2ms,如图4所示。双线程算法耗时为普通算法的64.40%,双线程算法运行效率降低;而四线耗时为普通算法的35.93%,是双线程算法的55.80%。可以看出,当数据量达到一定大小时,线程创建等时间开销相对于运算处理时间微乎其微,线程数量越接近处理器核心数量,计算机运行效率越高。
在10M数据下,普通算法平均耗时为1785476.4ms;基于OpenMP优化后,双线程算法为1027152.6ms,四线程算法为633355.8ms,如图5 所示。双线程算法号时为普通算法的57.52%,双线程算法在更大数据量中运行效率在降低;而四线程耗时普通算法的35.47%,是双线程算法的61.66%,当数据量达到一定大小时,线程开销可忽略不计。然而,由于数据相关性、一致性及同步性等原则,代码优化中对部分代码进行了加锁,当有线程在加锁部分运行时,其它线程不可进入,直到加锁部分执行结束,需要计算其它线程等待的时间,因此四线程并不能达到理论值或接近理论值。
4 结语
基于Open的并行编程模型并非简单地将线程最大化,需要考虑代码上下变量间以及函数间是否具有数据相关性、同步性及内存一致性等[7]。OpenMP在大数据运算中可以提高计算机的运行效率,然而并非线程越多越好,因为线程创建及启动需要一定时间开销;当创建线程等开销时间大于运算时间时,反而使得计算机运行效率降低;数据量越大,OpenMP越能提高计算机的运行效率,并且越稳定,此时若线程数分配至与计算机核心数一致,可实现计算机运行效率最大化[8]。OpenMP在大数据并行编程中有明显优势,然而OpenMP并不能很好地满足普通编程的需要,如果将来普及为常用并行编程模型,需要对小数据量并行编程进行优化,对线程创建等开销进行优化。
参考文献
[1]周伟明.多核计算与程序设计[M].武汉:华中科技大学出版社,2009.
[2]罗秋明.OpenMP编译原理及实现技术[M].北京:清华大学出版社,2012.
[3]赵辉,王振夺.基于OpenMP的多核系统中并行优化研究[J].北华航天工业学院学报,2014(12):16-19.
[4]高瑛,严正国.OpenMP多核并行程序的设计与实现[J].电子测试,2014(5):30-35.
[5]张乃孝.算法与数据结构[M].北京:高等教育出版社,2009.
[6]孙洪迪,高柱.基于OpenMP技术的多核处理器程序的开发实现[J].北京工业职业技术学院学报,2010(1):10-15.
[7]ROHIT CHANDRA.Parallel programming in OpenMP[M].Morgan Kaufmann,2012.
并行编程 篇5
1 支持多种访存技术的CBEA并行编程模型结构
1.1 支持多种访存技术的CBEA并行编程模型
在计算机编程技术中, MPI是一种比较应用比较广泛的并行编程模型, 也是目前计算机编程模型技术中应用最广泛的编程模型技术。应用MPI并行编程模型进行计算机的编程应用, 不仅具有比较良好计算机并行编程平台能够对于编程实现进行支持, 而且该并行编程模型还具有比较高的可扩展性以及可移植性。应用CBEA进行并行编程模型的设计实现, 不仅CBEA中同一节点内的每个SPE可以被当作是MPI计算中的分立节点, 并且CBEA中每个SPE能够实现通过DMA进行统一编址主存的访问实现, 具有比较高效的MPI通信。
总之, 应用MPI进行异构多核技术平台并行编程模型的设计建立, 不仅在进行并行编程模型的设计实现过程中, 可以充分的进行MPI本身所具有的的可移植性以及可扩展性的应用实现, 而且同时还具有对于MPI较大用户群体以及丰富应用软件资源的应用实现, 以及在少量MPI函数实现基础上进行模型可行性的验证实现等功能优势, 具有很大的便利性和积极性。
1.2 支持多种访存技术的CBEA并行编程模型结构
通常情况下, 异构多核技术在实际应用过程中, 多被编译成为SPE以及PPE两种映像形式, 并且通常在SPE和PPE两侧进行运行实现。本文所要论述的一种支持多种访存技术的CBEA片上多核MPI并行编程模型, 它则主要包括四个结构层次部分。即MPI运行时环境部分、PPE侧用户逻辑部分、SPE侧用户逻辑部分以及支持多种访存技术的访存库结构部分。其中, MPI运行时环境结构部分, 主要是由控制主进程mpirun进行创建的, 创建时主要根据运行时参数完成对MPI通信缓冲区、信号量及公共数据结构的初始化及应用任务进程组的创建和管理, 其中应用任务进程组中的进程数量由mpirun运行时的-np参数指定;而PPE侧用户逻辑结构部分主要是由任务进程组创建的一组用户线程组成, 主要完成用户逻辑中的控制部分。
2 基于CBEA的MPI并行通信分析
Cell提供片上高速互连总线, 用于片上核之问的低延迟、高带宽通信, 但对于MPI模型中任务间的通信本文并未使用SPE间的直接通信, 而是使用PPE侧基于共享主存的通信。针对这一情况, 选用基于PPE侧共享主存通信模式也便于计算任务在PPE与SPE间的分解, 传统应用及编程方法中将计算与通信相分离的原则为方便地将通信分解在PPE侧创造了条件。类似于流处理将访存与计算分离的原则, 在并行计算中将通信与计算相分离可以提高计算与通信效率, 在设计良好的应用中存在明显的计算与通信区域的划分。SPE专门设计用于计算, 对控制逻辑执行效率不高, 且只有很小的存储空间, 将通信与控制置于PPE侧, 而将计算密集部分置于SPE侧不仅便于计算任务在PPE与SPE侧的分解也可充分发挥各个核的特长。
3 基于统一访存接口的多种访存技术分析
在计算机设备运行应用中, 存储屏障一直是计算性能产生制约的重要因素, 它通过对于计算机片上多核处理器中每个核计算性能的影响, 实现对于整个多核系统的性能的影响和制约。Cell处理器存储架构非常适合流处理模式的计算, 基于统一访存接口的多种访存技术分析, 主要是通过对CBEA显式软件管理访存技术进行细分优化, 同时在兼顾支持流处理类应用的基础上, 扩展编程模型支持的应用范围, 为MPI编程模型提供高效的多种访存支持。为了同时支持多种访存技术和方便进一步访存性能优化, 还需要在对于“批量访存”、单缓冲区、组相联软件管理Cache和四路缓冲区数据预取访存库研究应用的基础上, 实现统一访存接口提供以及访存运行时剖分机制的增加。通过对四种仿存技术的定义以及五个标准仿存原语, 如表1所示。通过统一标准仿存原语对计算程序源码进行计算, 程序员选择仿存技术及配置文件, 有效的降低了编程的难度。
对任务运行时收集的信息进行计算, 能帮助程序员进一步对应用进行优化, 能够对仿存接口合理的进行选择, 或者配置合理的参数。
结束语
本文主要针对CBEA架构进行分析, 并在此基础上对一个MPI并行编程模型进行研究, 在统一仿存接口环境下, 实现同时支持“批量仿存”与非规则仿存的应用, 在PPE上对通信进行分解, 使模型的适用范围大幅拓宽。总之, 支持多种访存技术的CBEA片上多核MPI并行编程模型是在针对传统计算机编程模型应用局限性与问题的情况, 进行改进设计与提高完善实现的, 对于该种并行编程模型的分析, 有利于提高并行编程模型的设计技术水平, 促进多核并行编程模型在实际计算机编程中的应用, 具有积极的作用和意义。
参考文献
[1]冯国富, 董小社, 丁彦飞, 王旭昊.面向Cell宽带引擎架构的异构多核访存技术[J].西安交通大学学报, 2009 (2) .