基于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高性能計算。