基于OpenCL的双调排序算法的优化

杨朋霖 周志阳

西北师范大学计算机科学与工程学院

基于OpenCL的双调排序算法的优化

杨朋霖 周志阳

西北师范大学计算机科学与工程学院

双调排序算法是一种排序网络算法。随着数据量的增大，双调排序执行时间急剧上升。为了提高双调排序执行效率降低计算时间，本文提出了一种改进的并行双调排序算法，对算法进行并行化改进，使用本地内存以及优化线程模型。分别使用E8400和GTS450运行双调排序算法进行测试，改进的双调排序算法的计算速度比原版提高了5.24倍。

OpenCL GPU 双调排序 KNN

1 引言

近年来，异构计算系统表现出了良好的并行计算性能，成为国内外高性能计算领域的热点研究方向。OpenCL（Open Computing Language，开放计算语言）作为一种开放计算标准，为很多并行应用提供了支持。

排序是科学计算或者工程应用中经常使用，Garcia提出并行插入排序算法，文献[1]提出了一种并行基数排序的算法，Garcia提出了基于CUDA并行排序算法，Nolan使用了基于CUDA的冒泡排序，Thanakulwarapas等人提出了一种改进通信时间的双调排序，Thouti提出一种基于OpenCL版双调排序算法，双调排序有很好的表现。

2 相关概念简介

2.1 OpenCL

OpenCL是为异构平台编写程序的开放式、免费标准，也是一个通用的编程框架。现在由Khronos Group管理，异构平台可由CPU、GPU、DSP、FPGA或者其他类型的处理器与硬件加速器组成。OpenCL是第一个以通用为目的的异构计算平台，支持市面上绝大多数的处理器，可以在Windows、Linux、Mac OS大多数的操作系统上运行。OpenCL的核函数基于C99，相对编程难度较低。

2.2 双调排序

双调排序是一种排序网络算法，由Batcher提出，Batcher定理是指将任意长为2n的双调序列B划分为相等的两半，ai与an+i比较，较小者放入Min集合，较大者放入Max集合。得到的Min和Max仍然是双调序列。Min集合中的元素都不大于Max集合中的元素。可以将输入的2n元素双调序列首先通过洗牌比较操作得到一个MAX序列和一个MIN序列，然后通过两个n阶双调归并器处理就可以得到一个有序序列。

3 并行双调排序算法

3.1 概述

3.1.1 线程模型

OpenCL将GPU的多个PE（Processing Element）封装为一个CU（Compute Unit），多个workgroup可以并发运行在一个CU上，不同CU可以并行运行。每个workgroup中包含许多workitem，同一个workgroup中的workitem可以通信。可以在程序中设置workgroup的数量以及每个workgroup包含的workitem的数量，不同设置对程序效率有很大的影响。

3.1.2 内存模型

在Thouti的论文中双调排序算法只使用了全局内存。在OpenCL程序中访问全局内存的延时很长，可以使用本地内存提高效率。

3.2 实验结果分析

本文使用英特尔E8400+英伟达GTS450为OpenCL计算设备，使用随机生成数据为测试数据。本次实验通过统一的timer.h记录实验的运行时间。

优化后双调排序算法运行100次，计算平均运行时间，然后用数据数量除以平均时间算出每秒可以处理的任务量，经过试验可以看出使用本地内存后处理速度有了很大提升，速度提升到4.29倍，经当每个workgroup包含256个workitem时，速度提升到5.24倍。

4 结束语

本文对并行双调排序优化。首先介绍了OpenCL现状以及排序算法发展过程，阐述了双调排序的原理以及瓶颈，进而提出优化的双调排序算法，通过在线程模型、内存模型两个方面对KNN算法优化。经过实验验证对比，比原版本提高了5.24倍。

[1]Raymond T. OpenCL异构并行编程实战[M],第1版, 张立浩,译. 北京:机械工业出版社,2015

杨朋霖 ，1990—，男，山西翼城县人，汉族，西北师范大学计算机科学与工程学院在读硕士研究生，研究方向：GPU高性能计算。