基于OpenCL的雙調(diào)排序算法的優(yōu)化

楊朋霖 周志陽(yáng)

西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院

基于OpenCL的雙調(diào)排序算法的優(yōu)化

楊朋霖 周志陽(yáng)

西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院

雙調(diào)排序算法是一種排序網(wǎng)絡(luò)算法。隨著數(shù)據(jù)量的增大，雙調(diào)排序執(zhí)行時(shí)間急劇上升。為了提高雙調(diào)排序執(zhí)行效率降低計(jì)算時(shí)間，本文提出了一種改進(jìn)的并行雙調(diào)排序算法，對(duì)算法進(jìn)行并行化改進(jìn)，使用本地內(nèi)存以及優(yōu)化線程模型。分別使用E8400和GTS450運(yùn)行雙調(diào)排序算法進(jìn)行測(cè)試，改進(jìn)的雙調(diào)排序算法的計(jì)算速度比原版提高了5.24倍。

OpenCL GPU 雙調(diào)排序 KNN

1 引言

近年來(lái)，異構(gòu)計(jì)算系統(tǒng)表現(xiàn)出了良好的并行計(jì)算性能，成為國(guó)內(nèi)外高性能計(jì)算領(lǐng)域的熱點(diǎn)研究方向。OpenCL（Open Computing Language，開(kāi)放計(jì)算語(yǔ)言）作為一種開(kāi)放計(jì)算標(biāo)準(zhǔn)，為很多并行應(yīng)用提供了支持。

排序是科學(xué)計(jì)算或者工程應(yīng)用中經(jīng)常使用，Garcia提出并行插入排序算法，文獻(xiàn)[1]提出了一種并行基數(shù)排序的算法，Garcia提出了基于CUDA并行排序算法，Nolan使用了基于CUDA的冒泡排序，Thanakulwarapas等人提出了一種改進(jìn)通信時(shí)間的雙調(diào)排序，Thouti提出一種基于OpenCL版雙調(diào)排序算法，雙調(diào)排序有很好的表現(xiàn)。

2 相關(guān)概念簡(jiǎn)介

2.1 OpenCL

OpenCL是為異構(gòu)平臺(tái)編寫程序的開(kāi)放式、免費(fèi)標(biāo)準(zhǔn)，也是一個(gè)通用的編程框架。現(xiàn)在由Khronos Group管理，異構(gòu)平臺(tái)可由CPU、GPU、DSP、FPGA或者其他類型的處理器與硬件加速器組成。OpenCL是第一個(gè)以通用為目的的異構(gòu)計(jì)算平臺(tái)，支持市面上絕大多數(shù)的處理器，可以在Windows、Linux、Mac OS大多數(shù)的操作系統(tǒng)上運(yùn)行。OpenCL的核函數(shù)基于C99，相對(duì)編程難度較低。

2.2 雙調(diào)排序

雙調(diào)排序是一種排序網(wǎng)絡(luò)算法，由Batcher提出，Batcher定理是指將任意長(zhǎng)為2n的雙調(diào)序列B劃分為相等的兩半，ai與an+i比較，較小者放入Min集合，較大者放入Max集合。得到的Min和Max仍然是雙調(diào)序列。Min集合中的元素都不大于Max集合中的元素?？梢詫⑤斎氲?n元素雙調(diào)序列首先通過(guò)洗牌比較操作得到一個(gè)MAX序列和一個(gè)MIN序列，然后通過(guò)兩個(gè)n階雙調(diào)歸并器處理就可以得到一個(gè)有序序列。

3 并行雙調(diào)排序算法

3.1 概述

3.1.1 線程模型

OpenCL將GPU的多個(gè)PE（Processing Element）封裝為一個(gè)CU（Compute Unit），多個(gè)workgroup可以并發(fā)運(yùn)行在一個(gè)CU上，不同CU可以并行運(yùn)行。每個(gè)workgroup中包含許多workitem，同一個(gè)workgroup中的workitem可以通信?？梢栽诔绦蛑性O(shè)置workgroup的數(shù)量以及每個(gè)workgroup包含的workitem的數(shù)量，不同設(shè)置對(duì)程序效率有很大的影響。

3.1.2 內(nèi)存模型

在Thouti的論文中雙調(diào)排序算法只使用了全局內(nèi)存。在OpenCL程序中訪問(wèn)全局內(nèi)存的延時(shí)很長(zhǎng)，可以使用本地內(nèi)存提高效率。

3.2 實(shí)驗(yàn)結(jié)果分析

本文使用英特爾E8400+英偉達(dá)GTS450為OpenCL計(jì)算設(shè)備，使用隨機(jī)生成數(shù)據(jù)為測(cè)試數(shù)據(jù)。本次實(shí)驗(yàn)通過(guò)統(tǒng)一的timer.h記錄實(shí)驗(yàn)的運(yùn)行時(shí)間。

優(yōu)化后雙調(diào)排序算法運(yùn)行100次，計(jì)算平均運(yùn)行時(shí)間，然后用數(shù)據(jù)數(shù)量除以平均時(shí)間算出每秒可以處理的任務(wù)量，經(jīng)過(guò)試驗(yàn)可以看出使用本地內(nèi)存后處理速度有了很大提升，速度提升到4.29倍，經(jīng)當(dāng)每個(gè)workgroup包含256個(gè)workitem時(shí)，速度提升到5.24倍。

4 結(jié)束語(yǔ)

本文對(duì)并行雙調(diào)排序優(yōu)化。首先介紹了OpenCL現(xiàn)狀以及排序算法發(fā)展過(guò)程，闡述了雙調(diào)排序的原理以及瓶頸，進(jìn)而提出優(yōu)化的雙調(diào)排序算法，通過(guò)在線程模型、內(nèi)存模型兩個(gè)方面對(duì)KNN算法優(yōu)化。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證對(duì)比，比原版本提高了5.24倍。

[1]Raymond T. OpenCL異構(gòu)并行編程實(shí)戰(zhàn)[M],第1版, 張立浩,譯. 北京:機(jī)械工業(yè)出版社,2015

楊朋霖 ，1990—，男，山西翼城縣人，漢族，西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院在讀碩士研究生，研究方向：GPU高性能計(jì)算。