基于OpenMP的并行求和算法的研究与分析

【摘 要】目前几乎所有主流CPU厂商都致力于大力发展多核处理器，增加芯片支持的并行能力，从而提升计算机运算速度。本文主要探讨近来流行的多核计算技术，介绍一种重要的工业标准OpenMP，以及通过一个基于OpenMP的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。

【关键词】多核处理；并行求和算法；多线程；OpenMP

0.引言

多核技术始终是近年来全球计算机技术发展的重要内容。自从英特尔在2006年底了全球第一基于OpenMP的并行遗传算法探讨397款主流服务器四核处理器后，英特尔一直致力于推动多核应用生态系统的成熟与发展。实际上，从2002年推出超线程技术开始，英特尔就开始了向多核技术转型的步伐。最终，英特尔公司将四个计算“大脑”装入一枚处理器中，随着至强5300的诞生，计算机行业宣告正式进入了多核时代。

多核计算将成为一种广泛普及的计算模式，影响企业和消费者用户的使用模式。如目前的服务器应用，要求高的吞吐率和在多处理器上的多线程应用；Internet的应用、P2P和普适计算的应用都促使了计算机性能的不断提升。大型企业的ERP、CRM等复杂应用，科学计算、政府的大型数据库管理系统、数字医疗领域、电信、金融等都需要高性能计算，多核技术可以满足这些应用的需求。

本文主要探讨近来流行的多核计算技术，介绍一种重要的工业标准OpenMP，以及通过一个基于OpenMP的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。

1.OpenMP

OpenMP是一种适用于多种硬件平台的共享存储编程的工业应用标准，提供了一个可用的编程模型，具有简单、可移植性和可扩展性，灵活支持多线程和负载平衡的潜在能力，目前支持Fortran语言，c和c++。OpenMP规范中定义的制导指令、运行库和环境变量，能够在保证程序可移植性的前提下，按照标准将已有的串行程序逐步并行化。

OpenMP程序开始于一个单独的主线程。主线程会一直串行地执行，直到遇见第一个并行域才开始并行执行。并行域表示该部分程序计算量大，需要多个处理器共同来处理以提高效率和运行速度；并行区间以外的部分表示该部分的程序不适宜或者不能并行执行，只能由一个处理器来执行。主线程创建一队并行线程，然后，并行域中的代码在不同的线程队中并行执行，当主线程在并行域中执行完后，它们或被同步或被中断，最后只有主线程在执行。实际上，所有的OpenMP的并行化，都是通过使用嵌入到C/C++或Foaran源代码中的编译制导语句来达到的。在具体实现时，在并行域开始处添加OpenMP制导指令#Pragma，另外，OpenMP是独立于平台的，如果编译器不支持OpenMP，将会自动忽略预处理指令#Pragma，程序依然可以按照串行程序代码顺利编译执行。

2.传统求和算法

2.1算法设计

传统的求和算法思路相当简单，先定义一个数组，然后随机生成一系列数据放入数组中，再使用循环将各个数据累加存入最后结果变量中即可。

本文先约定定义的是一个long型的数组a，存入的数据为long型整数，考虑到数组元素的最多个数与测试机器的字长有关，而笔者所使用的测试环境是字长为32位的win7系统，且此算法要与下面的并行求和算法进行比较，因此本着尽可能选取多数据且不超过long型数据范围（2^31- 1）的原则，本文将存入数组的数据个数N定为65536。然后使用rand（）函数只随机生成1-100的整数，这样保证最后求和的结果也不会超过long型数据的范围，防止了计算过程中数据溢出情况的发生。

2.2具体实现

（1）随机生成数组数据代码实现：

3.基于OpenMP的并行求和算法

3.1实验前准备

由于现在电脑CPU一般都有两个核，4核与8核的CPU也逐渐走入了寻常百姓家，传统的单线程编程方式难以发挥多核CPU的强大功能，于是多核编程应运而生。多核编程可以认为是对多线程编程做了一定程度的抽象，提供一些简单的API，使得用户不必花费太多精力来了解多线程的底层知识，从而提高编程效率。OpenMP支持的编程语言包括C语言、C++和Fortran，支持OpenMP的编译器包括Sun Studio，Intel Compiler，Microsoft Visual Studio，GCC。实验使用的是Microsoft Visual Studio 2008，C++语言，CPU为Intel i3 2350 双核四线程。在Microsoft Visual Studio 2008上openMP的配置非常简单，总共分2步：

（1） 新建一个工程。

（2） 建立工程后，点击 菜单栏->Project->Properties，弹出菜单里，点击 Configuration Properties->C/C++->Language->OpenMP Support，在下拉菜单里选择Yes。

3.2算法设计

OpenMP简单易用，在设计算法时我们不需要添加额外的include头文件和link库文件，只须在合适的地方添加OpenMP语句即可，例如在for循环前加一句“#pragma omp parallel for”。而且这些语句运行在单核机器上，或者编译器没有将OpenMP设为可用的机器上编译也不会报错，将自动忽略#pragma这行代码，然后按照传统单核串行的方式编译运行。使用OpenMP来实现并行求和的算法思路也是非常简单的，即把数组分成多块，每个 CPU 核心负责一块的求和，最后把每块的和加起来即可。但考虑到当多个线程并行执行时，有可能多个线程同时对某变量进行了读写操作，从而导致不可预知的结果，即和的计算不准确的问题，实验使用了OpenMP提供的一个工具，归约（reduction），也就是在#pragma omp parallel for 后面加上了 reduction（+：sum），它可以告诉编译器：下面的for循环你要分成多个线程跑，但每个线程都要保存变量sum的拷贝，循环结束后，所有线程把自己的sum累加起来作为最后的输出。

3.3具体实现

并行求和计算代码实现：

4.算法效率的比较与分析

4.1比较实现

首先，为了保证测试比较的准确性，每一次比较我们都是使用同一个数组，同一组随机生成的数据测。使用OpenMP函数库里面的omp_get_wtime（）函数来获取当前时间，通过运行前后两个时间值之差来计算算法运行时间。考虑到单次执行时间远远小于1秒，时间太短，不利于分析，所以在两个求和的算法的代码前加上一个次数为5000的循环。最后输出求和结果和运行时间。代码如下：

4.2比较结果与分析

表4.1为两个算法运行5000次的时间累积的时间值。

由表格中的测试结果数据看，平均起来并行求和相对于串行只用了 其57% 的时间，效率是有所提高。但是，由于本实验使用的CPU为双核四线程处理器，即伪四核。想来如果四核并行求和的话，耗时应是串行的 25% 左右，而这个结果与期望值相差太大。于是，笔者又将该程序放置安装有货真价实的四核处理器i5 2450上，进行实验，测试结果如表4.2。

测试结果数据表明：并行求和算法用时约为串行的29%。29% 与最初预期的 25% 相当接近，考虑到CPU被其他程序共享占用的情况，该结果已经符合之前的期望值，但也从一定程度上说明了使用OpenMP的归约工具进行并行求和其算法的效率确实要比串行的要高，但是在双核四线程处理器下的效率却不能达到真正四线程的效果。至此，实验的结束。

5.结束语

本文使用基于OpenMP工具实现了并行求和算法，并将之与传统的串行求和算法进行了对比和分析，计算效率优势明显。在这个以多核处理器为主流的时代，OpenMP将成为程序员必不可少的工具。

随着应用需求的扩大和技术的不断进步，多核技术必将展示出其强大的性能优势。多核处理器是处理器发展的必然趋势，无论是移动与嵌入式应用、桌面应用还是服务器应用，都将采用多核的架构，因此多核技术应用前景广阔。

参考文献：

[1] 张引琼，戴小鹏. 独立学院Java语言教学改革与实践研究[J]. 电脑知识与技术， Vol.8，No.8，March 2012：1886～1887.

[2] 骆挺，徐婷婷，孙霞. Java课程在民办院校实践教学的思考[J]. 福建电脑， 2012年第3期：43～44.