基于图形硬件的双调排序算法优化.pdfVIP

维普资讯

第29卷第14期计算机工程与设计2008辱1

VO1．29NO．14ComputerEngineeringandDesign

July2008

基于图形硬件的双调排序算法优化

宾洪斌，何锫，胡明辉

(长沙理工大学计算机与通信工程学院，湖南长沙410076)

摘要：介绍一种新的并行排序算法，该算法以双调归并排序为基础，运用图形硬件的并行体系结构和--y,#序树数据结构

的优点，用部分并行代替所有阶段的顺序执行，对双调排序算法进行优化。对该算法进行分析，在理论上n个序列在P个流

处理器上的排序，最优的时间复杂度为O((nlogn)／p)。实验测试结果表明，优化后的算法比其它基于图形硬件的双调归并排序

算法所用时间短。

关键词：双调归并排序；流计算；图形处理器；归并；算法优化；排序网

中图法分类号：TP301．6文献标识码：A文章编号：1000．7024(2008)14．3660．03

Optimalbitonicsortforgraphicshardware

BINHong-bin，HEPei，HUMing-hui

(SchoolofComputerandCommunicationEngineering，ChangshaUniversityofSciencenadTechnology,

Changsha410076，China)

Abstract：Anovelparallelsortingispresented．Thisalgorithmisbasedbitonicmerge-sortscheme．ThebenefitofusingGPU’Sparallel

rachitectureandabinarytreeimprovetheapproach．Insteadofacompletelysequentialexecutionofallstages，theapproachisexecuted

thempartiallyoverlapped．ForsortingnkeysutilizingPstreamprocessorunits，thisapproachachievestheoptimaltimecomplexityO

((nlogn)p／)．Theapproachperformsverywellinpractice，whichiscausedbyseveraloptimizations．Furthemrore，hteapproach

consumeslesstimehtnaohterapproachesbasedonGPU．

．

Keywords：bitonicmergesort；streamcomputing；graphicsprocessingunit；merge；optimalar／thmet／c；sortingnetwork

前面两种算法。但是他们的算法并没有在时问复杂度上优化。

0引言

1．2算法介绍和改进

计算机图形处理器(graphicsprocessingunit，GPU)用于通1．2