并行排序的编程方法与应用

黄逸

摘 要：为了发挥多核微型计算机的计算效能，文章在Visual C++和OpenMP环境中探讨了并行排序算法的设计和实现方法。首先，将整体排序任务按处理器上的核数均衡地进行分组；然后，在各个计算核中以选择排序的方式独立完成子序列的排序；最后，以并行归并的方式将各个有序子序列形成一个整体的有序序列。实验表明，并行排序较传统的串行排序而言，其计算效能有了显著的提升。

关键词：并行排序；多核计算；选择排序；归并排序

在不同领域的信息处理过程中，经常需要按照某种线性序（如数的小于关系）对一些对象进行排序，以便高效地完成信息的分析和处理。常见的计算机排序算法有冒泡排序、选择排序、插入排序、歸并排序和基数排序等，通常，可用计算耗时指标来评价这些排序算法的效率和性能。由于现有的排序算法是以串行的工作方式来完成排序的，因此，直接在多核架构的微型计算机上执行，是无法发挥处理器既有的多核并发计算效能的，于是有必要对现有的排序算法进行多核并行运算的改进[1]。

1 并行排序的编程设计与实现

1.1 OpenMP模型的编程原理

OpenMP（Open Multi Processing）模型是一种共享存储体系结构上的编程模型，它包含一套编译指导语句及一个支持函数库，目前已应用到Unix/Linux，Windows等多种操作系统上，支持的编程语言有Fortran，C/C++等。OpenMP模型的设计初衷是为了提供存储共享的体系结构和编程平台，并为编程用户提供可行的串行程序转并行化的设计方案[2]。

OpenMP是基于线程技术的并行编程模型，采用“fork-join”方式执行程序。如图1所示，程序开始时在一个主线程中执行，遇到可并行执行的区域时，便创建一组线程，这些线程可以执行相同的代码块；也可以使用共享存储的方式，并行执行不同的任务[3]。

下面代码是基于C语言的OpenMP编程示例：

int main（）

{

#pragma omp parallel for

for（int j=0；j<100；j++ ）

{

printf（″j=%d＼n″， j）；

}

printf（″The program is close＼n″）；

}

在上面的示例代码中，OpenMP使用“#pragma omp parallel for”编译指导语句把一个没有先后相依关系的for循环语句以并行方式执行。由于for循环语句是以并行的方式执行，为此，循环体中的打印输出语句没有以顺序形式输出；此外，根据上述的“fork-join”工作原理可知，仅当for并行循环语句执行结束后，程序才输出“The program is close”。

1.2 并行排序算法的设计

为了发挥多核微型计算机的并行计算能力，结合OpenMP模型的“fork-join”工作特点，设计了如图2所示的并行排序算法。算法首先提取运行机器其处理器的核数n，然后把整体序列均衡地分为若干个子序列；并以选择排序的方式在各个计算核中并行地完成各个子序列的排序；待各个子序列的排序结束后，继续用归并排序的方式并行地归并出一个整体的有序序列[4]。算法的设计要点如下。

（1）提取处理器的核数：在Windows操作系统中，可以调用API函数GetSystemInfo（ ）来提取运行机器其处理器所拥有的核数，相关代码如下：

int MyModel：：_GetNoOfProcessors（）

{

SYSTEM_INFO kn；

GetSystemInfo（&kn）；

return kn.dwNumberOfProcessors；

}

（2）并行选择排序：在获取处理器的核数后，便可以把待排序任务均衡地分为2m×n（m>1，m∈N）个子任务，对于这些子序列的排序而言，由于它们之间并没有前后的相依关系，所以可在各计算核中并行地完成排序。考虑到排序的主要操作是元素的比较和交换，为了避免元素的频繁交换，这里以选择排序作为各并行排序任务的基本算法。相关代码如下：

#pragma omp parallel sections

{

#pragma omp section /*“fork”域*/

for（i1=0；i1

{

k=i1；

for（j=i1+1；j

{/*存储最小数的位置*/

if（a[j]

k=j；

}

if（i1！=k）

{t=a[i1]；a[i1]=a[k]；a[k]=t；}/*完成a[i1]与a[k]数据交换*/

}

.

.

.

#pragma omp section /*“fork”域*/

for（in=0；i2

{

k=in；

for（j=in+1；j

{

if（a[j]

k=j；

}

if（in！=k）

{t=a[in]；a[in]=a[k]；a[k]=t；}

}

}

（3）并行归并排序：利用上述的并行选择排序可以得到2m×n个有序的子序列，不难发现，可以在微处理器的各个计算核中，用复制的方法把两个不同的有序子序列归并为一个有序序列，从而得到2m-1×n个有序的子序列；继续两两归并，……，如此重复，直至归并出一个整体的有序序列。相关代码如下：

#pragma omp parallel sections{

#pragma omp section/*“fork”域*/

void Merge（float sub1[]，sub2[]，float dest[]）/*按照從小至大的方式进行归并*/

{/*sub1[]和sub2[]为需要归并的有序子序列*/

i=0；j=0；k=0；

if（sub1[i]

{dest[k]=sub1[i]；i++}

else

{dest[k]=sub2[j]；j++}

for（k=1；k

/*按照从小至大的方式进行归并*/

{ Sub1_Len和Sub2_Len分别为sub1[]和sub2[]序列的长度

if（sub1[i]

{dest[k]=sub1[i]；i++；}

else

{dest[k]=sub2[j]；j++；}

k++；

}

.

.

.

}

2 并行排序的实验及分析

实验的硬件环境是：Intel core i5-6600K四核CPU/Intel core i7 6800K六核CPU、DDR4 2133MHZ 16GB RAM、金士顿SUV400S37/240G固态硬盘；软件环境为：Windows 7专业版64位、Microsoft visual studio 2015中文版；实验中需要进行对比的算法有冒泡排序算法、选择排序算法和新设计的并行排序算法。实验过程中，用rand（）函数随机产生一个长度为5 000的实数序列，然后分别用上述3种算法完成序列的排序；实验重复100次，取平均计算耗时作为度量各种算法的效能。实验的具体结果如表1所示。

从表1的实验结果可以发现，冒泡排序算法的计算耗时最多、选择排序算法次之，而新设计的并行排序算法为最小。由于冒泡排序和选择排序均属于串行算法，所以它们在不同计算核的计算耗时并没有明显的差异，与之形成对比的是，新设计的并行排序算法在四核和六核的计算环境中则有了约41%和56%的提升。为此，新设计的并行排序算法是正确和有效的。

3 结语

排序算法在众多领域中有着广泛的应用场合，而优秀的排序算法不仅要求高效而且还要求节省资源。为多核架构的微型计算机设计了一种并行的排序算法，新算法将原序列划分为若干个子序列，然后通过并行的选择、归并排序方式来完成最终的排序任务，由于各个子序列的排序没有前后的相依关系，为此能较好地发挥多核微型计算机的计算效能。

[参考文献]

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

[2]雷洪，胡许冰.多核并行高性能计算OpenMP[M].北京：冶金工业出版社，2016.

[3]梁海英，王凤领，谭晓东.数据结构C语言版[M].北京：清华大学出版社，2017.

[4]严蔚敏，李冬梅，吴伟民.数据结构C语言版[M].北京：清华大学出版社，2015.