OpenMP

OpenMP（精选六篇）

OpenMP 篇1

关键词：OpenMP,Smith-Waterman算法,并行编程

1 引言

目前的基因序列信息增长迅速,高速的序列比对有助于生学家研究DNA结构、功能,促进人类生物医学、生命科学等领域的发展。在寻找基因序列最佳相似比对的算法中有两种算法使用较为广泛:BLAST算法和Smith-Waterman[1]算法。BLAST算法的运行速度要比Smit h-Water man算法快,但是Smi th-Wa ter m an要比BLAST算法更为精确,可以实现最佳的局部比对。可是该算法的时间复杂度和空间复杂度都是(TL×NL),于是人们提出了很多改进方法。Pearson[2]等采用启发式方法,以牺牲结果的质量为代价提高了计算的性能;Adam和Douglas提出了两种Smith-Water man并行算法:RowWavefront算法和Diagonal Wavefront[3]算法,这两种算法Open MP并行化之后线程创建和销毁开销太大;Qiao[4]等人在流水并行的基础上,提出了分块的流水并行算法。本文按照Qiao的分块流水并行的思想,对局部比对算法Smith-Waterman算法进行分块行流水的方式进行Open MP并行化,来提高它的速度,同时也减少了内存的需求量。

2 Open MP

Open MP[5]标准是共享存储体系结构上的一个编程模型。共享式存储的并行化具有编程简单、灵活的特点,开发周期较短,并行效率较高。1997年,计算机软硬件厂商联合定义了共享内存编程应用接口的工业标准协议Open MP,克服了长期以来并行解决方案的可移植性和扩展性差的缺点。Intel和AMD双核、四核处理器的推出意味着计算机体系结构的发展朝着更有利于Open MP的方向发展;同时在应用领域更需要充分利用片上多核来提高大规模问题求解的速度。

Open MP是由一套编译制导语句、一个用来支持它的函数库以及环境变量组成。Open MP是通过与标准的C、C++、Fortran语言结合来工作的。Open MP具有使用简单、支持增量化并行、自然映射到多核体系结构上的特点,并且随着处理器数目的不断增加具有很好的移植性。Open MP主要是在循环级上的并行,指令以单一程序多数据结构、任务共享结构、同步结构以及提供对数据共享或私有的支持扩展了原有程序的顺序结构模型。Open MP编写的程序在运行时采用分叉、合并的方式。本文将使用Open MP一部分编译制导语句来介绍Open MP并行化过程,示例代码采用C语言。

在Open MP中,编译制导指令在每一行以#pragma开头,编译制导指令parallel定义一个并行域,就会生成另外的一些线程来并行执行这些代码。除非有一些其它的制导指令,否则对于每一个线程都会执行并行域中的所有代码。有许多方法可以控制线程的行为,具体可以见http://www.openmp.org。在并行域里面,线程不仅可以执行相同的程序代码,还可以分担繁重的计算任务,尤其是for循环。如果一个循环被制导指令for包含,那么它的迭代将根据不同的分配策略分配到不同的线程中去执行。这两个制导指令可以合并在一起成为parallel for结构。Open MP并行循环示例代码如下:

在共享编程环境下,区分变量是所有线程的共享还是每个线程都有一个私有拷贝很重要。在一个循环中,循环计数器必须为私有,因为每一个线程都计算不同的迭代,而循环计数的界限值因为对每个线程都一样,可以共享。默认的情况下,所有变量(除循环计数器)都为共享,Open MP制导指令可以设置哪些变量共享,哪些变量私有。如上所示的一段循环代码是对数组的计算,该数组元素值依赖于其前一行元素值,通过颠倒行和列改变循环。其中数组默认为共享变量,每个线程都可以访问。循环计数器j默认为私有变量。语句private标明每个线程对变量i都有自己的一份拷贝。

3 Smith-Waterman算法

Smith-Waterman算法由smith和waterman两人写于1981年用于计算局部最优比对。1982年由Gotoh得到改进,可以处理多个大小差距处罚。

得分矩阵i,jH依赖关系如图1所示:

4 Smith-Waterman算法Open MP并行化

对Smith-Waterman算法程序的Open MP并行化,本文通过对串行程序中可以并行化的部分进行数据分割,让多个处理机并行执行来实现的。本文中Smi thW a t e r m a n算法是用C语言实现的,因此以下都是以Open MP+C方式介绍并行化过程的。下面分别介绍程序Open MP并行化过程涉及的问题以及处理办法。

4.1 分块流水并行Smith-Waterman算法

Qiao等人在流水并行的基础上,提出了分块的流水并行算法,将得分矩阵分块,每次处理一个子块。计算完一个子块后,将其它处理器所需要的数据传出;而当所需数据还没有收到时,阻塞自己直到获得该数据。在行流水的情况下,一个子块计算完毕后,只需将最下面的一行数据传出,按反对角线流水时,将最下面的行和最右边的列传出。该方法具有良好的并行效果,且可以减少时间和空间复杂度。

由于Smith-Waterman算法中的得分矩阵存在图1所示的依赖关系,本文借鉴Qiao等人提出的分块的行流水并行算法,将得分矩阵分块,每次处理一个子块。在行流水的情况下,每一个子块计算完毕后,只需将最下面的一行数据传出。分块时,每个子块的大小为(nthread+1)×(NL+1),其中nthread为线程数目,NL为测试序列的长度。在计算每一个子块的得分矩阵时,依照行流水的方式,每个线程处理一行,第一个线程处理完第一行第一个数据后,第二线程就可以处理第二行第一个数据了,以此类推,形成流水线。计算完一个子块后将最后一行的值传出,以备进行下一个子块的运算。

4.2 区分共享与私有变量

Open MP在并行化循环结构中最重要的是区别共享和私有变量。其中共享变量可以被所有线程访问,而一个线程只能使用自己的私有变量,不能去访问其他线程的私有变量。通过分析,该分块循环结构的共享和私有变量如下:

#pragma parallel for private(row,line)

其中循环计数器值默认为私有变量,循环内的其它变量默认为共享变量,因此数组E、F、H为共享变量。

4.3 任务调度

Open MP有三种任务调度策略:静态调度、动态调度、引导调度。静态调度将其中大小一样的任务块以轮询的方式静态的分配给所有的线程,对于负载均衡的任务采用静态分配减少开销;动态调度是只要线程完成任务,需要任务就可以获得下一个迭代块,动态调度系统开销比较大。编译器可以对静态部分进行一定的优化,但是对动态部分没有优化功能。引导调度是一种混合策略,每个线程在第一次获得一个较大的块,以后运行中分配逐渐缩减块的大小,直到缩减至chunk Size制定的限制值,块的大小按需要动态计算,这与块大小逐渐减少的动态调度类似。本文的算法将每一块并行化实现,每个块有nthread行,每个线程处理一行。因此使用静态调度,代码如下所示:

通过上述处理,得到S m i t h-W a t e r m a n算法的Open MP并行程序。

5 性能测试与分析

5.1 测试平台

实验平台为四个双核的Intel Xeon MP E7310处理器(1.6GHz),其内存为4GB,高速缓存2MB,操作系统为Red Hat Enterprise Linux Server release 5.0(Tikanga),编译器选择gcc4.2。由于使用的是共享存储编程模式,因此使用其中的一个SMP节点(4个CPU)进行性能测试。

5.2 测试数据与性能分析

测试的C源程序来源M S M.c,本文对其中的Smith-Water man算法进行修改,矩阵选择的是PAM和BLOSUM矩阵。其中两个比对序列是使用Mc Ca ldon Arogos-distribution随机产生的。其中测试的是长度为500的查询序列与长度为300的数据序列的最佳比对分数。并行化之后,将会有多个线程对每块得分矩阵进行并行计算。

测试过程中针对不同线程数做了性能测试,图2是对测试长度为300的BLOSUM矩阵做的测试结果。

由图2的测试结果可以看出,在4个双核CPU上测试,当线程数为2、4、8时效率比其它的要高,当线程数为2时性能比较好,之后再增加线程,性能改善没有2个线程时明显。主要原因是:Open MP编写的程序在运行时采用分叉、合并方式,增加线程,就会增加相应线程创建、销毁开销;其次算法中采用分块的行流水并行方法,在线程增加时后面的线程要等待前一个线程的数据,增加了时间开销。但是总的性能还是得到了改善,其运算速度提高了40%。

6 结束语

本文通过对smith-waterman算法的分析,利用共享存储的编程对该算法进行并行化。从减少算法的运行时间以及对内存的需求量入手,结合共享存储编程的特点,对原串行算法中可以并行化的部分进行相应的处理,使其实现多线程的并行化。在机群的一个SMP节点(4个C P U,每个C PU为双核)的测试表明,性能比原有程序有了很大的提高。

参考文献

[1]SMITH T F,Waterman M S.Identification of Com-mon Molecular Subseque-nces[J].Journal of MolecularBiology,1981,147(1):195-197.

[2]ALTSCHUL S F,MADDEN T L,SCHAFFER AA,et al.Gapped BLAST and PSI-BLAST:A New Genera-tion of Protein Database Search Programs[J].Nucleic AcidsResearch,1997,25(17):3389-3402.

[3]GALPER A R,BRUTLAG D L.Parallel SimilaritySearch and Alignment with the Dynamic ProgrammingMethod[R].Stanford University,KSL Report:1990,90-74.

[4]QIAO X Z,Li Z,ZHU M F.Parallel Computationfor Dynamic Program-ming[C]//Proc.of the 2nd Int.ICSC Symposium on Computational Intelligence Methods&Applications,Bangor,Wales,UK,2001.

OpenMP 篇2

多核计算机快速普及, 如何正确、有效地使用并行计算机, 充分利用并行计算机的资源, 以发挥并行计算机的计算能力尤为重要。图形处理系统也基本都运行在多核计算机平台上, 然而其内部运行机制仍然是由单核完成串行计算任务, 并没有充分利用多核平台的计算优势, 导致了巨大的资源浪费。因此, 如何充分发掘计算机的计算能力, 有效发现程序的可并行能力, 将串行计算转换为并行计算成为非常有意义的课题。

在图形处理系统中, 对于大容量图形数据文件加载、图形数据重新运算生成、实时目标图形数据处理等对于计算能力的要求非常高。因此, 为了充分发挥多核计算机的高性能处理能力, 利用多核并行编程技术, 将原来串行算法的理念结合多核计算机的架构特点, 把串行算法进行变换后得到有效的执行方案, 成为了研究重点。

1 OpenMP简介

1.1 OpenMP的基本概念

OpenMP由OpenMP Architecture Review Board牵头提出, 是已被广泛接受的用于共享内存并行系统的多线程程序设计的一套指导性的编译处理方案。OpenMP作为共享存储标准出现, 是为共享存储环境编写并行程序而设计的一个应用编程接口, 目前支持OpenMP的语言主要有Fortran、C/C++。OpenMP标准中包括一套编译指导语句和一个支持函数库。

1.2 Fork/Join并行执行模式概念

OpenMP是一个编译指导指令和库函数的集合, 主要为共享式存储计算机上的并行程序设计使用。OpenMP在并行执行程序时, 采用的是“Fork/Join”方式, 其并行执行模式如图1所示。

标准并行模式执行代码的基本思想是:程序开始时只有一个主线程, 程序中的串行部分都是由主线程执行, 并行部分通过派生其它线程来执行;但是, 如果并行部分没有结束, 则不能执行串行部分。从图1中可以看出, OpenMP并行执行的程序要全部结束后才能执行后面的非并行部分的代码。这就是标准的并行模式———Fork/Join并行模式。共享存储式并行程序就是使用Fork/Join并行模式。

1.3 内存模型

OpenMP内存模型属于共享存储模型, 即不同的处理器共享同一内存。OpenMP线程之间的数据交换是通过共享内存来实现的, 这需要把共享变量存放在各线程都能访问到的共享存储区。同时还应允许通过私有化方式来说明, 使各个线程可分别维护自己的私有变量。如图2所示, 多个处理器通过共享内存来进行数据互通和交换。

1.4 OpenMP编译指导语句

在OpenMP中, 最主要的是编译指导语句, 它指示编译器如何将串行程序转化成并行程序。一条编译指导语句由directive (命令, 也叫指令) 和clause list (子句列表) 组成。以C/C++为例, OpenMP编译指导语句的格式为:

#pragma omp[clause[[, ]clause]…]

其中, directive部分包含了具体的编译指导语句, 包括parallel、for、parallel for、section、sections、single、master、critical、flush、ordered、atomic等;clause表示子句, 常用的子句有firstprivate、if、lastprivate、private、reduction等。

2 多核程序计算设计模式

在多核多线程编程中, 存在着多种计算设计模式, 下面是常见的几种计算设计模式。

2.1 线程分组竞争模式

对于有锁计算, 当多个线程竞争同一把锁时, 会出现排队执行现象, 由于同一时刻只能有一个线程在运行, 其它线程会因为等待锁而被挂起。为了解决这个问题, 可以将多个线程分成N组, 每组线程竞争同一把锁, 任意不在同一组内的两个线程不发生锁竞争现象。这种将多个线程分组进行锁竞争的方法为线程分组竞争模式。线程分组竞争模式如图3所示。

图3中显示了两个分组的线程竞争情况, 共有4个线程分成两组竞争, 添加、删除操作线程1之间存在锁竞争情况, 添加、删除操作线程2之间也存在锁竞争情况, 但是添加 (或删除) 操作线程1和添加 (或删除) 操作线程2之间不存在锁竞争。在这种分组锁竞争模式下, 不同分组内的线程不发生锁竞争现象, 因而可以并行运行。任意一组线程中, 至少一个线程处于非阻塞状态。因此如果有N组线程, 至少有N个线程处于非阻塞状态;如果N大于等于CPU的核数, 那么任意一个CPU核上都有线程处于执行状态, 可以保证CPU不会产生饥饿现象。

2.2 线程随机竞争模式

而对于不能采用线程分组竞争模式的情况, 可以采用一种称为随机竞争的模式, 即每个线程随机访问各个子数据结构, 多个线程竞争同一个子数据结构 (或内存区域) 的概率是相等的。一个两线程随机竞争4个子内存区域的竞争模式如图4所示。

在图4中, 共有两个线程, 每个线程可以随机访问4个内存区域中的任何一个。当两个线程在访问不同的内存区域时, 不发生锁竞争;但是在同时访问同一内存区域时, 会发生锁竞争现象。因此在随机锁竞争模式中, 有可能出现多个线程竞争同一把锁的现象, 此时会发生排队执行 (只有一个线程在运行) 的现象。显然, 随机竞争模式中, 加速比性能比分组竞争模式差, 但是仍然要好于多个线程竞争同一把锁的性能。

2.3 条件同步模式

条件同步模式是将每次都需要使用同步改为满足一定条件情况下才使用同步的方法, 大大减少了使用同步的次数, 这样就提高了效率。使用条件同步的基本方法, 通常是使用原子操作, 因为使用原子操作进行操作的变量在读取时和读取线程私有变量是一样的。

2.4 批量私有化处理模式

所谓批量私有化处理模式, 是指在一段有锁计算中, 将处理小批量数据改成处理大批量数据的方法。小批量数据是指一个节点的数据或一小段数据等, 大批量数据是指多个节点的数据或大段的数据等。这样可大大降低锁的使用频度, 从而提高效率。

2.5 数据本地化模式

数据本地化模式, 指将共享资源分解, 使每个线程拥有一个私有的部分, 另外还有一个针对全部线程的共享部分。对于私有部分只有本地线程可以操作, 而共享部分则所有的线程都可以操作, 如图5所示。

图5显示了4个线程的数据本地化模式, 每个线程都有一个私有的本地化数据部分, 还有一个所有线程都操作的共享部分。图中带箭头的粗线表示私有本地计算操作, 带箭头的虚线表示有锁或无锁计算的操作。

为了确保共享部分的计算不出现多个线程竞争同一把锁的现象, 还可以按照前面讲过的分组竞争模式或随机竞争模式对共享部分再进行分解。例如, 对于一个队列, 在单核多线程时代, 通常都是对队列直接进行加锁、解锁来避免出现数据竞争问题。如果采用数据本地化模式, 则可以设计成每个线程带有一个私有队列, 另外还有一个共享队列;出队操作时, 则先从私有队列中进行出队操作, 如果私有队列为空, 则从共享队列中获取数据。这样可以保证很大一部分计算是本地计算, 大大提高了效率。

采用本地化模式后, 很明显的优点是加速比性能可以得到很大的提升, 但同时也有一些小缺点, 体现在以下几个方面:①共享资源需要分解成每个线程一个私有部分, 还要分解成多个子共享部分, 数据分解方面存在一定的难度, 对数据结构设计提出了更高的要求;②需要管理分解后的数据, 增加了内存开销;③数据结构变复杂后, 编程的复杂度也相应增加。虽然存在这些缺点, 但是与加速比性能得到明显提升相比, 这些缺点可以忽略不计, 而且这些缺点都是可以控制和克服的。

3 多核并行程序的性能评价

本文主要采用Amdahl定律来进行程序的性能评价。

假设一个程序中, 不能分解成并发计算的部分所占比例为f, 并假设并发计算时无额外开销 (如通信开销等) 。假设程序在单处理器上的执行时间为ts, 那么程序在n个处理器上执行时, 串行部分所在时间为fts, 并行部分执行时间为 (1-f) ts/n。这样, 可以得到加速比为:

式中, ts表示在单处理器上的串行执行时间;S (n) 表示加速比;n表示处理器的个数;f表示串行部分所占整个程序执行时间的比例。

4 OpenMP在图形数据文件加载中的应用

在图形处理系统中, 存在着大容量图形数据文件加载操作, 当图形数据文件中图形符号数量比较少时, 计算机能够作出比较迅速的响应, 但是随着图形符号数量的增加, 响应会随之变慢, 严重影响了程序性能。针对这一问题, 利用多核并行编程思想, 结合图形数据文件加载特点, 提出了图形数据文件加载的本地化模式, 提高了程序的性能。

4.1 图形数据文件加载程序性能优化

图形数据文件加载程序的性能优化主要体现在以下两个方面:

(1) 线程数量设置。针对计算机硬件的不同, 为了提高程序的兼容性和可扩展性, 可以利用omp_get_num_procs () 函数取得当前计算机的处理器个数。一般情况下线程数量刚好等于CPU核数时可以取得比较好的性能, 当线程数量等于CPU核数时, 每个核执行一个线程, 没有线程切换开销;当设置的线程数量远远大于CPU核数时, 将产生大量的线程切换和调度等开销, 也会降低整个程序的效率。当然, 具体设置多少个线程要视情况而定。

(2) 任务调度策略。在多核平台上实现最大加速比的方法就是使各个线程在每个CPU核上尽可能保持平衡, 每个线程分配的任务大致相等。OpenMP提供了几个调度选项, 通过将schedule (type[, size]) (type参数表示调度类型, size为迭代次数) 添加到OpenMP指令控制调度各个线程的调度方式, 调度类型如表1所示。

由表1的对比可以得出, 为了减少调度开销, 尽量使用默认的static方式, 这就要求在程序开始时将任务分成几个尽量相等的块, 从而得到较高的效率。

4.2 图形数据文件加载的本地化模式

针对多核程序中的线程数量设置和任务调度策略, 为了使程序运行时获得最大的性能, 要求在程序开始时设置线程数量, 并且采用static调度方式, 为了达到这一要求, 在图形数据文件加载中采用数据本地化模式, 如图6所示。图形数据文件中存储的图形符号都是独立的个体, 之间不存在数据竞争, 因此, 在获得计算机的CPU核数之后, 可以将图形数据文件中存储的图形符号信息进行分段处理, 采用默认的static调度方式进行并行计算, 最后将读取的图形符号信息进行综合显示。

5 实验结果与分析

本实验式在Intel (R) Core (TM) 2 Quad CPU 2.83GHz四核机器、3.00GB内存的硬件环境下进行。软件包括Microsoft Visual C++6.0、图形处理系统。实验结果的运行时间如图7所示, 加速比结果如图8所示。

从测试结果可以看出, 在不同线程设置下, 当图形符号数量达到一定量级, 特别是在计算量大的情况下, 多核多线程的优势表现得更为明显。由表2可以看出, 多核多线程在计算量较小的情况下, 所获得的加速比并不理想, 甚至会出现并行比串行运行时间更长的情况, 这主要是线程开辟带来的额外开销大于计算节省的时间所致。而对于计算量较大的计算, 计算节省的时间要大于线程开辟带来的额外开销, 多核多线程的优势表现得比较明显, 在4核4线程的情况下, 可获得2.5倍的加速比。

6 结语

通过多核技术实现图形处理系统中图形数据文件加载操作, 证明了多核技术在计算能力上的性能优势。在未来的工作中, 可以将多核技术应用于图形系统中的图形数据运算生成、实时多目标图形数据处理等程序中, 提高程序性能。

参考文献

[1]周伟明.多核计算与程序设计[M].武汉:华中科技大学出版社, 2008.

[2]Akhter S.多核程序设计技术[M].李宝峰, 译.北京:电子工业出版社, 2008.

[3]董丽丽, 刘明生, 袁香菊.多核并行编程技术在中文分词程序优化中的应用[J].计算机工程与设计, 2010, 31 (24) .

[4]罗秋明.OpenMP编译原理及实现技术[M].北京:清华大学出版社, 2012.

[5]多核系列教材编写组.多核程序设计[M].北京:清华大学出版社, 2007.

[6]赖建新, 胡长军, 赵宇迪, 等.OpenMP任务调度开销及负载均衡分析[J].计算机工程, 2006, 32 (18) .

[7]钱葵东, 蹇成刚.OpenMP在信息系统中的应用[J].指挥信息系统与技术, 2011, 2 (5) .

[8]OpenMP Architecture Review Board.OpenMP application program interface[S].Version 3.1, 2011.

OpenMP 篇3

随着多核及众核处理器的大量涌现和网络性能不断的提升, 大规模多核集群并行计算技术也成为当前高性能计算的主流平台[1]。基于共享存储的并行编程语言Open MP已发展为为此类平台的主要实现技术[2]。Open MP并行编程基本思想是将一个待求解任务分成主线程和一些子线程, 其中主线程负责任务划分、调度分配处理核和收集子任务求解结果, 并获得问题最终解。各子线程接收主线程发来消息, 各自进行计算及向主线程返回计算结果。其基本执行模型是采用如图1所示的ForkJoin模式。Open MP应用程序始于主线程 (Master Thread) , 主线程串行执行, 遇见并行域就并行执行子线程。并行域中各线程执行完后返回主线程串行执行, 再遇到并行域并行执行, 依次循环直至程序执行结束。

矩阵乘是高性能计算中最基本的计算模块, 对气候模拟、地震数据处理、流体力学和分子动力学模拟等经典并行应用程序性能有重要影响[3]。签此, 本文将探讨矩阵分块并行乘方法, 利用Open MP在多核集群计算进行大规模计算实现, 以提高矩阵乘效率。

2 矩阵块乘原理

简单矩阵相乘是如图2所示的矩阵A和矩阵B相乘, 然后将结果储存在矩阵C中。这样需三重循环算法, 大大浪费了内存。采用矩阵分块计算时, 能有效提升数据计算效率, 并且在数据规模较大情况下有明显计算优势。主要基于矩阵分解为若干块, 每次完成块计算, 因而提高Cache命中率及计算效率[4]。

针对此问题, 本文将采用如下矩阵分块算法。矩阵乘法可以表示为Cm*n=Am*k*Bk*n, 如图3-1示。

首先, 在i方向对矩阵进行划分 (for (i=0;i<M;i+=Mc) ) , 如图3-2所示, 其中矩阵A和C划分大小为Mc;在此基础上对k方向进行划分 (for (k=0;k<K;k+=Kc) ) , 如图3-3所示, 其中每分块大小为Kc;最后, 在前两步分块基础上, 在j方向上进行划分 (for (j=0;j<N;j+=Nc) ) , 如图3-4所示, 其中B和C分块被进一步划分为宽度为Nc块。[3]

3 基于OpenM P的并行实现

Open MP是基于共享存储体系结构的并行编程标准, 基于Visual Studio 2010的Open MP并行编程指导语句分为并行域指令、工作共享指令、同步指令和数据环境指令等[5]。本文将矩阵分块以后引入如下Open MP是语句:#pragma ompparallel shared (a, b, c) private (i, j, k) 。使得矩阵乘法计算部分能在多核上运行, 并使用语句omp_set_num_threads (num_thread) 来动态改变核资源数。

4 多核集群并行计算实验

本实验在32核集群系统上展开, 为了验证并行计算分块矩阵乘法的效率影响, 将从两个方面采集数据。

1) 令矩阵规模固定为2000*2000, 通过变化内核数量, 将增加核数时间与单核数据相除得到加速比, 结果如图4所示。随着核数增多, 并行计算效率也随之提高。

2) 固定内核数量为4, 通过变化数据规模, 结果如图5所示。由图可知当数据规模较小时, 因为矩阵划分与并行运算所用时间超过串行计算所用时间, 所以效率较低。随着数据增加, 相对加速比逐渐接近并稳定于4。

5 结论

并行计算理论提出和完善以及核集群系出现为大型复杂数据计算提供了有效率计算途径与方法。本文通过对分块矩阵乘法在多核集群计算机上进行实验表明, 多核集群计算能有效提高大规模数据并行计算效率。

参考文献

[1]Sergio Santander-Jiménez, Miguel A.Vega-Rodríguez.Parallel Multiobjective Metaheuristics for Inferring Phylogenies on Multicore Clusters[J].IEEE Transactions on Parallel and Distributed Systems, 2015, 26 (6) :1678-1692

[2]陈永健.Open MP编译与优化技术研究[D].北京:清华大学

[3]Kiran Matam, Siva Rama Krishna, Bharadwaj Indarapu, Kishore Kothapalli.Sparse matrix-matrix multiplication on modern architectures.The 19th International Conference on High Performance Computing (Hi PC) , 2012, pp.1-10

[4]王恩东.MIC高性能计算编程指南[M].北京:中国水利水电出版社, 2012

OpenMP 篇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.

OpenMP 篇5

暂态稳定紧急控制是维持电力系统安全稳定运行的重要手段。暂态稳定紧急控制问题通常建模为考虑暂态稳定约束和系统经济运行的最优化问题。

目前, 求解暂态稳定紧急控制问题的算法主要有试凑法或启发式算法[1,2,3]、基于暂态能量函数的直接法和基于最优控制理论的优化算法。暂态稳定紧急控制问题的难点之一在于暂态稳定约束的描述, 基于能量函数的方法在暂态稳定预防控制和暂态稳定紧急控制方面已有广泛的研究[4,5,6,7,8,9,10,11]。时域仿真法是解决暂态稳定紧急控制的另一种方法, 基于最优控制理论, 各种紧急决策计算均描述为以控制代价最小为目标、以维持系统安全稳定性为约束条件的最优控制问题, 这类最优控制问题实质上就是最优参数选取问题。文献[12-13]将切负荷问题描述为最优控制问题, 提出了一种系统化地决定最小切负荷量及其在各切负荷点分配的算法。文献[14]基于时域仿真得到的系统受扰轨迹给出暂态稳定紧急控制的非线性模型, 然后采用近似规划法和拟贪婪法求解。

简约空间技术主要用来求解自由度较小的非线性规划问题, 已在化工领域获得了广泛应用[15]。文献[16-17]用简约空间内点算法求解暂态稳定最优潮流问题, 计算效率获得极大的提升。文献[18]应用简约空间二次规划法求解暂态电压稳定紧急控制问题, 显著提高了计算效率。由于暂态稳定紧急控制问题中可切负荷/发电机节点相对于问题规模非常小, 即该类问题自由度很低, 本文运用简约空间内点算法进行求解。此外, 算法采用C++编程实现, 对于算法的关键耗时环节, 充分利用多线程并行技术。多个算例测试结果表明, 本文提出的基于Open MP并行简约空间内点法在求解紧急控制问题中, 计算时间明显缩短, 占用内存减小, 能够求解大规模系统的紧急控制问题。

1 暂态稳定紧急控制数学模型

电力系统最优切机切负荷控制问题是一个大规模动态优化问题, 其一般形式为:

其中, x为优化变量;F为优化问题目标函数;H为含微分方程等式约束;G为含微分方程不等式约束; 分别为不等式约束上、下限。

采用隐式梯形积分方法对上述动态优化问题差分化, 动态优化问题 (1) 可转化为如下非线性规划问题:

1.1 目标函数

暂态稳定紧急控制的目的是切除最少的发电机和负荷来保持系统暂态稳定, 因此, 本文将优化目标函数设为切机和切负荷量加权最小:

其中, u=[uG, uL], 为优化控制变量, uG、uL分别为各可切发电机节点切机比例组成的向量和可切负荷节点切负荷比例组成的向量;cG、cL分别为切机、切负荷控制代价的权值, 用来表征可切发电机和负荷的重要性, 本文中将权值均取为1, 即所有可切发电机、可切负荷重要性相同;PG、PL分别为各可切发电机节点装机容量和各可切负荷节点总负荷。

1.2 等式约束

a.发电机动态方程。

电力系统经典模型对于系统第一摆稳定分析非常有效实用[19]。本文中发电机模型采用经典模型, 负荷采用恒阻抗模型, 因此, 各发电机可由如下两阶微分方程描述:

其中, i=1, 2, …, NG (NG为发电机节点数) ; 为发电机暂态电势, 经典模型下为恒定值, E′i、x′di分别为发电机节点i暂态电势、直轴暂态电抗, 分别为发电机节点i在t时刻的功角、节点电压、节点电压实部、节点电压虚部;TJi、Pm i分别为发电机节点i惯性时间常数和有功出力;ωit为发电机节点i在t时刻的角速度;ωs为同步角速度有名值。

b.电网方程。

将发电机表示成电流源形式, 并将发电机等值导纳和负荷等值导纳并入网络, 电网方程可写成:

其中, I txi、Ityi分别为t时刻发电机节点i的注入电流实部和虚部;Gij、Bij分别为节点i和节点j节点导纳实部和虚部;nB为系统节点数。

对于可切机的发电机节点, 有:

对于不可切机的发电机节点, 有:

对于可切负荷节点, 有:

对于不可切负荷节点, 有:

其中, G′ii、B′ii分别为发电机等值导纳和负荷等值导纳并入网络前节点自导纳实部和虚部;GLi、BLi分别为负荷等值导纳的实部和虚部;uGi、uLi分别为切机点切机比例和切负荷点切负荷比例。

1.3 不等式约束

a.控制变量上下界约束:

b.暂态稳定约束。

暂态稳定判据采用中性惯量形式表示:

其中, Mi为发电机惯性常数; 分别为功角上、下界约束。

2 基于Open MP并行简约空间内点法

2.1 简约空间内点算法

采用预测-校正内点法求解非线性规划问题 (2) , 其一阶最优必需条件 (KKT条件) 求解包括预测和校正2步, 其主要计算量在求解以下对称线性方程组[20]:

其中, 为约束条件和目标函数对应海森矩阵的线性组合; 表示等式约束h (x) 对变量x的雅可比矩阵;L′x和Ly为库恩-塔克系统的右端残差向量, 具体定义参考文献[21]。

简约空间技术适用于自由度较低的非线性规划问题, 用来求解对称线性方程组 (12) 。将变量x分成程空间DY和零空间DZ两部分, DY由m个非独立变量组成, DZ由n-m个独立变量组成。变量x的解可写成:

其中, 分别称为程空间和零空间基矩阵, [Y Z]非奇异。零空间基矩阵Z满足:

分别为m维和n-m维单位对角矩阵, 令

则pY、pZ、Δy分别如下求得:

详细的简约空间内点算法原理及实施细则可参考文献[16]。采用简约空间内点算法求解紧急控制问题时, 方程组 (15) — (17) 的求解通过调用KLU[21]计算, 其对矩阵C的分解可复用, 每次迭代只需做1次LU分解。算例分析表明, 简约空间下紧急控制算法的主要计算时间集中在矩阵B和Zm的计算上, 本文通过多线程技术提高这部分的计算效率。

2.2 Open MP并行算法

2.2.1 Open MP编程模型

为充分利用多核处理器计算平台的计算性能, 针对算法可解耦部分利用多线程技术实现并行计算从而加快计算速度。Open MP[22]提供了一套共享存储体系结构下的多线程编程模型, 从而实现本文算法多线程并行技术。

如图1所示, Open MP采用Fork-Join的并行执行模型:程序首先以单线程 (主线程) 开始, 类似一个串行程序, 当遇到并行结构, 主线程会产生一组线程 (Fork动作) , 每个线程都执行并行动态扩展域中的代码;并行结构执行完后, 只有主线程继续执行, 其他所有的线程结束执行 (Join动作) 。本文程序并行化部分, 系统给每个线程分配一个CPU核心。

2.2.2 并行简约空间内点算法

在简约空间内点算法框架下, 多线程技术可通过下面2种方式实现。

a.矩阵Zm的多线程求解。

矩阵Zm的计算公式为式 (15) 。求解矩阵Zm实质就是求解一稀疏线性方程组, 本文调用KLU解法器计算矩阵Zm。KLU解法器是一性能优良的稀疏线性方程组解法器, 其计算过程主要包含LU分解和回代2个步骤:首先对C进行分解, 然后对N的各列向量逐步回代, 最后得到Zm。算例测试表明, 回代过程占据了主要计算时间。

矩阵N是由n-m个m维列向量构成, 在回代过程, 矩阵N各个列向量回代过程相互独立。将N分解成p (p为线程数) 个m维列向量组成的矩阵, 即N=[N1N2…Np]。可将这p个矩阵分配给各计算线程实现并行回代, 从而加快计算速度, 如图2所示。KLU解法器是一个串行解法器, 不支持并行计算。本文对KLU代码进行了修改, 使其按图2所示支持多线程回代。

b.矩阵B的多线程计算。

本文算法采用C++编程实现, 算法实施过程中涉及到较多矩阵操作, 尤其是B的计算占据较多时间。目前有许多高性能线程代数库可供调用, 很多都支持多处理器平台下的多线程并行。在本文中, 基础线程代数库 (BLAS) 被用来作一些矩阵与矩阵相乘运算和矩阵与向量相乘运算, 在计算矩阵B时主要调用DCSRMM和DGEMM函数进行求解, 这2个函数均支持Open MP下多线程计算, 程序实现时通过调用MKL_NUM_THREADS函数设置线程数, 开启多线程从而加快计算速度。此外, 线性代数解法器 (LAPACK) 被用来求解稠密线性方程组 (18) 。

2.3 算法实施流程

采用本文提出的算法求解暂态稳定紧急控制问题的主要步骤如下:

a.读入算例数据, 包括故障信息;

b.对故障后系统进行暂态稳定仿真计算, 若系统保持稳定, 不需要切机切负荷, 跳到步骤g;

c.按照第1节内容对暂态稳定紧急控制问题数学建模;

d.对系统变量及收敛条件初始化, k=0, 算法优化开始;

e.按照第2节提出的并行简约空间内点算法计算变量x更新步长;

f.判断是否达到收敛条件, 若未收敛, k=k+1, 跳到步骤e;

g.算法退出, 输出结果。

3 算例分析

3.1 测试算例

本文采用基于Open MP并行简约空间预测校正内点法对4个算例进行了计算, 这4个算例是在IEEE标准算例的基础上修改得到, 根据切机量和切负荷量相对功角稳定的灵敏度大小来确定可切发电机和负荷。表1给出4个测试算例的参数, 其中nB、nL、NG、nG、Nload、nload分别表示系统节点数、系统线路数、系统发电机数、系统可切发电机数、系统负荷数、系统可切负荷数。对所有测试系统, 在t=0时刻发生三相短路故障, t=0.2 s切除故障线路, t=0.3 s执行切机切负荷操作。tsim为算法仿真时间, 即为切负荷时刻至末端时刻的时间差。采用隐式梯形积分法进行暂态稳定分析时, 积分步长在本文中取为Δt。程序中各发电机相对于惯性中心的偏差不超过±110°作为暂态稳定判据。

表2给出了4个测试算例采用隐式梯形积分差分化方法离散微分方程和网络方程后问题规模, 其中n表示问题状态变量数, m表示问题等式约束数, δDOF表示问题自由度即为n与m之差, rDIM、NNZ分别表示原对偶系统式 (12) 的维数和非零元数量。可以看出, 差分化后优化问题自由度很小, 即满足 从而该问题非常适合简约空间下求解。

本文算法采用C++编程实现, 测试环境为Intel Xeon 2 quad-core CPU, Open MP被用来实现多线程并行。通过调用英特尔提供的高性能多线程线性代数库 (BLAS和LAPACK) 实现算法中的一些矩阵运算。KLU解法器被用来对算法中稀疏线性方程组进行求解。

3.2 测试结果

本文算法是基于Open MP并行简约空间内点法。为表述简洁, 本文称传统内点算法为全空间内点算法。为了比较本文算法与常规算法的性能优劣, 对上面4个算例用隐式梯形差分化方法离散微分方程和网络方程, 并在全空间、简约空间以及并行简约空间下求解, 测试结果如表3所示。表3中“×”表示因时间或者内存不足导致问题不可解。

从表3中可以看出, 采用隐式梯形积分差分微分方程和网络方程, 简约空间下计算速度明显比全空间下计算速度要快, 并且可以求解更大规模系统紧急控制问题。因简约空间技术只是在求取式 (12) 时采取的策略, 其并不改变迭代过程, 简约空间和全空间下问题迭代进程是完全一样的, 得出的优化结果也一样。因此, 本文将把全空间和简约空间得出问题的迭代次数统一列出。

基于Open MP并行简约空间算法是在简约空间算法的框架下对一些计算步骤利用多线程技术并行求解, 它不改变算法的计算进程, 因而两者有相同的迭代进程和相同的优化结果。从表3可以看出, 在8核处理器计算平台下, 并行简约空间内点算法计算效率进一步提高。

本文选取切机切负荷作为紧急控制措施来保证暂态稳定性。以CASE300为例, 列出优化后切机、切负荷量如表4所示。

3.3 并行性能分析

首先对串行简约空间下算法各部分计算时间进行分析如表5所示。从表5可以看出, 简约空间内点算法下暂态稳定紧急控制问题的计算时间主要集中在B计算时间和Zm回代时间。因而本文对这部分进行多线程并行求解, 提高计算效率。

s

为了分析B计算和Zm回代的并行效率, 线程数p取1到8分别进行测试, 测试结果如图3、图4所示。从图3、图4可以看出, 当线程数较少时, 本文算法几乎可以达到线性加速比, 随着线程数的增加, 加速比增长放缓, 在8核处理器下, 加速比最大可达4.5。一般而言, 测试算例规模越大, 本文算法可获得越好的加速比。因此, 本文算法对大规模系统暂态稳定紧急控制问题的求解有较好的潜力。

3.4 时域仿真验证

通过时域仿真来验证上面4个算例的第一摆稳定性, 图5给出了各个测试算例发电机摇摆曲线, 图中实线为系统发生故障后不执行紧急控制操作的功角曲线;虚线为执行切机切负荷操作的功角曲线。因全空间内点算法、简约空间内点算法和并行简约空间内点算法三者有相同的迭代进程, 因此3种算法得出的优化曲线一致, 本文只给出简约空间下发电机摇摆曲线。由图5可以看出, 电力系统发生故障后不执行切机切负荷操作将失去稳定。采用本文提出的算法执行切机切负荷操作, 系统能够保持暂态稳定。

4 结语

OpenMP 篇6

要解决上述矛盾只有两个有效途径, 一是采用大规模的并行机和专用机进行计算, 二是对计算方法进行改进。采用大规模的并行机和专用机进行计算成本过高, 不利于大面积推广使用, 因此利用现有计算设备, 解决上述问题就成为解决问题的关键。在这一背景下, Kondylis等人提出了有利于提升内存使用效率的时域有限差分法 (R-FDTD) , 闫玉波等也基于不同视角提出MPI网络并行FDTD算法, 但是上述方法仍然不能解决一些更为复杂的计算。为了进一步提升计算机内存利用率, 以解决复杂度更高的计算问题, 本文提出了基于局域网系统以及消息传递 (Massage Parallel Interface, 简称MPI) 和Open MP混合编程平台的三维网络并行FDTD方法。该方法主要以10/100Mbps以太网为基础构建并行微机系统, 实现了处理机的个数的随时增减, 使计算过程对大内存的需求问题得到更为有效的解决。

1 MPI-Open MP混合编程模式

MPI是集群计算中广为流行的编程平台, 但是单独采用MPI并不能在这种多处理器构成的集群上取得理想的性能。MPI-Open MP混合编程模式很好地结合了分布式内存结构和共享式内存结构的优势, 实现了节点内和节点间的两级并行。混合编程模式的结构如图1 所示, 对于单独的MPI进程来看, 其不仅可以Open MP编译制导区产生线程级并行, 同时又保留了线程外的单线程。这种编程模式充分集合和发挥了两种不同编程模式的诸多优点, 其中MPI主要用于处理并行处理器之间的粗粒度通信问题, 而依靠Open MP所提供的轻量级线程又对计算机内部不同处理器之间的信息交互提供了有效手段。

2 网络并行FDTD方法中子域划分

显然, 数据通信量是影响计算时间的主要因素。设计时要想达到充分发挥两台微机的计算性能, 提高运算速度、缩短计算时间的目的, 就必须在计算域划分时尽量减少数据通信量, 而至于计算机需要等待数据通讯。将FDTD计算域设想为一个立方体, 那么可以考虑的分割方式有图2 (a) 和图2 (b) 两种。采用图2 (a) 中的分区方式时, 所有通过分界面传递的数据总量为

其中n为每个方向上的网格划分数 ( 设与z垂直的截面为正方形) ; p为节点机个数 ( 系数2 是由于每一个通信面被看成两个, 每一个子域一个通信面) 。采用图2 (b) 中的分区方式时, 所有通过分界面传递的数据总量为:

当p=8、27 和1000 时, (1) 式计算所得的通信总量分别为14n2、52n2和1998n2;而 (2) 所得的通信总量分别为6n2、12n2和54n2。由计算结果可知, 在节点机数目比较接近的情况下, 图2 (b) 中的分区方法通信数据总量较少。如果将FDTD的计算域设为更一般化的长方体, 那么上述两个公式需要分别进行修正, 并得到如下结果:

其中:nx、ny、nz分别是计算区域沿对应坐标轴方向上的网格划分数。由此可见, 公式 (1) 、 (2) 是公式 (3) 、 (4) 的特殊化, 其前提各个坐标轴方向网格划分数必须相同。我们还应该注意到:通信总量虽然会对计算时间造成直接影响, 但是并不能决定并行加速比的高低。一般来说, 节点机计算量与每个节点机所处理的计算域的体积成正比, 而通信量则和相应的通信面面积成正比。所以在合适的问题尺寸下, 并行加速比可以通过提高节点机计算量和通信量的比。此外, 计算机的内部数据交换速度要远快于数据通信速度, 因此在具体计算中, 本地机具有天然的计算优势, 所以在计算中要注意优先发挥本地计算机的计算优势, 也就是要依据节点机的实际情况进行负载量的具体分配。

3 结束语

相对于单独使用MPI编程模式, 对圆柱单站RCS计算和通信分别采用双线程并行处理方式, 可以实现计算过程中的计算与通信的真正重叠。所以上述混合编程模式在加速比方面具有明显优势。但在具体计算中也应当注意下述问题: 当线程数多于处理器个数时, 会产生线程竞争总线带宽的问题, 并导致整个系统性能的下降;当采用线程通信时, 要尽量使发送与接收操作均通过同一线程处理;当需要处理通信与计算重叠的问题时, 要注意负载的分配均衡。

摘要：以多处理器节点集群计算机为平台, 构建了MPI-Open MP混合并行的层次化结构模型。然后以三维金属圆柱FDTD散射计算为算例, 将单独使用MPI和MPIOpen MP混合编程情况下结果的加速比进行了比较, 并借此做了通信与计算重叠试验, 不仅验证了混合方法的有效性, 而且可以看出在多处理器集群计算系统上运用MPI-Open MP模式能进一步提高加速比和带宽利用率。最后, 通过对附加通信量、负载平衡以及网络通信性能等因素对FDTD并行计算产生的影响进行讨论, 可以进一步得出构建局域网的硬件性能、子区域的不同划分以及通信原语言的软件设计对并行加速比和效率具有明显影响, 而带宽利用率的提高则系于负载平衡问题的改善。

关键词：MPI-OpenMP,FDTD,加速比,带宽利用率

参考文献

[1]陈文光.MPI与Open MP并行程序设计C语言版[M].北京:清华大学出版社, 2004.