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

摘要：为了充分利用多核处理器的硬件资源和计算能力，提出了基于多核并行编程技术的图形数据文件加载优化方案。根据图形数据文件加载的特点，由传统的串行程序改为并行程序，利用多核并行编程模型的思想，找出程序的热点和瓶颈，对其进行优化。实验结果表明，当图形符号数量达到一定数量级之后，优化过后的执行时间较原来串行程序有明显缩短，提高了程序的加速性能，取得了良好的效果。

关键词：OpenMP；程序优化；图形数据文件加载；本地计算

中图分类号：TP317.4文献标识码：A文章编号文章编号：16727800（2013）0010015904

作者简介：査盛音（1986-），男，华北计算技术研究所地理信息与图形图像技术研发中心硕士研究生，研究方向为多核计算；王玉玫（1962-），女，华北计算技术研究所地理信息与图形图像技术研发中心研究员、硕士生导师，研究方向为图形图像处理、指挥自动化技术；聂颖（1972-），女，华北计算技术研究所地理信息与图形图像技术研发中心高级工程师、硕士生导师，研究方向为计算机图形处理与应用技术。

0引言

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

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

1OpenMP简介

1.1OpenMP的基本概念

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

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

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

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

1.3内存模型

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

1.4OpenMP编译指导语句

在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数据本地化模式

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

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

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

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

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

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

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.83 GHz四核机器、3.00GB内存的硬件环境下进行。软件包括Microsoft Visual C++ 6.0、图形处理系统。实验结果的运行时间如图7 从测试结果可以看出，在不同线程设置下，当图形符号数量达到一定量级，特别是在计算量大的情况下，多核多线程的优势表现得更为明显。由表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.

[9]白俊峰，邓祖朴.多核系统的软件开发方法[J].计算机工程，2010，36（12）.