OpenMP多核并行程序的设计与实现

高 瑛，严正国

（1，西安石油大学电子工程学院，陕西西安,710065;2，延安大学物电学院，陕西延安,716000；3，西安石油大学电子工程学院，陕西西安,710065）

0 引言

目前多核计算机可以实现系统中多个进程与线程的并行运算。并行算法的实现主要基于三种并行标准：PVM标准；MPI标准；OpenMP标准。对于大部分串行程序而言，直接在多核处理器上运行依然不能够获得加速。因此，为提高系统的性能，提出将单一任务分解成若干个子任务，分别在不同的节点上运行。在多核处理机上，研究并行算法的实现技术与并行后系统的性能，具有非常重要的理论与现实意义。

1 并行计算性能分析

并行算法的性能通常以加速比和效率作为衡量的标准，下面给出二者的定义。

系统对加速比的定义：加速比为系统执行串行程序所用时间与在同一台计算机上使用多个并行部件执行所花费时间之比。

系统对效率的定义：效率为加速比与所有参与并行执行部件的个数之比。比值越大，则效率越高。

2 OpenMP

OpenMP是共享存储体系结构编程的工业标准，采用标准的Fork/Join式并行执行模型，如图1所示，使用由运行库提供的编译指导语句来实现并行化。在程序开始执行时，只存在一个主线程，在执行过程中，如果遇到并行编译指令要求并行执行时，这时候，主线程会派生出子线程或者启用系统原有线程来并行执行任务。在执行的过程中，主线程协同子线程共同工作，等待并行代码执行完毕后，子线程退出或者挂起，不再参与任务的执行，程序回到原来的主线程上继续执行，直到整个程序运行结束。

3 性能测试

本文采用对求解QAP的粒子群优化算法用OpenMP技术进行并行来验证OpenMP的性能。

3.1 PSO算法的并行化

二次分配问题（QAP）是一种经典的组合优化问题，易于描述而难于求解，已经归入NP-hard问题。QAP不仅以各种不同的形式存在于实际生活领域中，而且问题本身又包含着组合优化的要求，在诸多领域广泛应用。因此，研究QAP具有重要的理论与现实意义。然而，当问题的规模足够大时，QAP的解空间呈现爆炸特征,致使无法在多项式时间内求解最优解。因此，人们通常采用元启发式算法来有效地解决这一问题。

粒子群优化算法（PSO）是一种基于群体的新型随机元启发式搜索算法，起源于鸟类群体智能,可以被纳入多主体优化系统 (MAOS)，已在函数优化、神经网络设计、分类、模式识别、信号处理、机器人技术等许多领域取得了成功的应用。因此，粒子群优化算法具有很好的并行性。

3.2 实验结果

实 验 环 境 为 Intel（R）Core(TM) 2 Duo CPU T5670@1.8GHZ,内存为2GB，WinXP SP3操作系统，以Intel Fortran 10.1.014 with vs2005作为开发软件。实验选取QAPLIB（http://www.seas.upenn.edu/qaplib）中典型实例进行了测试。结果如表1所示。

4 结论

本文从分析OpenMP本身的特点及编程模型入手，通过实验证明了基于OpenMP的并行算法的有效性，而且并行PSO算法在所选的测试实例上都获得了超线性的加速比。充分利用了OpenMP共享存储体系结构的特点，避免了消息传递带来的开销，但是它的不足之处在于可扩展性差。因此，今后的工作将放在对基于SMP集群的MPI与OpenMP混合编程模型的研究，从而克服系统扩展性差的缺点，进而提高系统的易用性和可移植性。

图1 Fork/Join并行模型

表1 并行算法的加速比、效率

[1]OpenMP C application program interface version 2.0[EB/OL].(2000-11).http://www.openmp.org.

[2]周洪斌，吕强.利用混合粒子群优化算法求解二次分配问题[J].计算机应用与软件，2009,26（11）.259-260.

[3]S.Sahniand T.Gonzalez.Pcomplete approximation problems[J].Journal of the ACM,1976,23(3).555-565.

[4]张慧珍，马良，（西）罗佑.二次分配问题及其线性化技术[M].上海人民出版社，2013,01（10）.40-55.

[5]Eberhart R.C,Kennedy J.A New Optimizer Using Partical Swarm Theory.Proc.on 6th International Symposium on Microma chine and Human Science[C].Piscataway:IEEE Service Center,1995.39-43.