第39卷  计  算  机  学  报  Vol. 39    2016年  论文在线出版号  No.157  CHINESE J OF COMPUTERS  Online Publishing No.157 ——————————————— 本课题得到国家自然科学基金(No.61532021, 61272137,61202114)、华为创新研究计划（HIRP 20140507）资助.郭诚欣,男,1988年生,博士研究生,主要研究领域为数据仓库、并行计算优化.E-mail: guochengxin2014@ruc.edu.cn.陈红(通讯作者),女,1965年生,博士,教授,博士生导师,高级会员,主要研究领域为数据库、数据仓库、无线传感器网络.E-mail:chong@ruc.edu.cn.孙辉,女,1977年生,博士,讲师,主要研究领域为移动数据管理、数据挖掘.李翠平,女,博士,教授,博士生导师,  计算机学会(CCF)高级会员,主要研究领域为社会网络、数据挖掘.吴天贞,女,1992年生,硕士研究生,主要研究领域为数据仓库.  基于现代硬件的并行内存排序方法综述 郭诚欣1),2) 陈红1),2) 孙辉1),2) 李翠平1),2) 吴天贞1),2) 1)(中国人民大学数据工程与知识工程国家教育部重点实验室北京  100872)  2)(中国人民大学信息学院北京  100872)  摘  要  研究了现代硬件上的并行内存排序方法,对其研究现状与进展进行了综述.首先简要阐述了经典排序算法以及排序网络的优缺点,分析其并行优化的适用性,然后从现代CPU处理器设备(多核、配备大内存)、图形处理器(GPU)、现场可编程逻辑门阵列(FPGA)等新型处理器设备介绍现有排序方法的研究成果.处理器设备的架构不同,对排序算法的优化策略也不同,现代CPU主要利用线程的本地存储层次,优化数据在存储单元中的排列,以减少访存次数及减少访存缺失,同时利用单指令多数据流技术(SIMD)技术,以提高算法的数据级并行度;GPU则需要将多个线程组织成线程块,依靠共享内存提高线程块的访存速度,而在线程块内则使用单指令多线程(SIMT)技术提高线程的执行效率;FPGA 则更靠近于硬件底层,受到自身的资源限制,FPGA的优化策略主要依靠硬件描述语言或高级综合语言优化电路的设计,提高资源利用率的同时增加FPGA的吞吐量.现有的成果表明, GPU 的并行内存排序性能优于CPU端上的并行内存排序性能.最后对未来的研究方向进行了展望.  关键词  现代硬件处理器；排序算法；存储访问层次；并行优化；图形处理器；现场可编程逻辑门阵列 中图法分类号  TP393    论文引用格式： 郭诚欣,陈红,孙辉,  李翠平,吴天贞，基于现代硬件的并行内存排序方法综述，2016，Vol.39,在线出版号  No.157 GUO Cheng-Xin,CHENHong,SUN Hui,LI Cui-Ping,WU Tian-Zhen，Parallelism of In-Memory Sorting Algorithm on Modern Hardware，2016，Vol.39,Online Publishing No.157 Parallelism of In-Memory Sorting Algorithm on Modern Hardware GUO Cheng-Xin1),2) CHENHong1),2)SUN Hui1),2)LI Cui-Ping1),2)WU Tian-Zhen1),2) 1)(Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education (Renmin University of China), Beijing100872)  2)(School of Information, Renmin University of China, Beijing 100872)  Abstract  The  research  achievements  of  parallel  in-memory sorting  method  on  modern  hardware  are summarized in  this  paper. Firstly, the  advantages  and  disadvantages  of  classical  sorting  algorithms and  sorting network are briefly reviewed and their applicability of parallel optimization is analyzed. Then the state-of-the-art sorting methods  implemented  on the  modern  CPU  processor  device  (multicore,  equipped  with  large  memory), Graphics Processing Unit(GPU), Field-Programmable  Gate  Array(FPGA) and  other  new  processor  equipments are introduced. Different optimization strategies about sorting algorithm are utilized on different architecture of processors. Modern  CPUs mainly  utilize thread  local  memorylevel  with  aligned data  in  order  to  reduce  the 网络出版时间：2016-10-14 12:39:38网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161014.1239.008.html2  计  算  机  学  报  2016年 frequency of  memory  access and memory  miss. To  improve  data  level  parallelism of sorting  methods, Single Instruction  Multiple  Data (SIMD) technology  is also involved; Threads  of a GPU are organized into thread blocks,  using  Shared Memory  to  improve  the  speed  of  memory  access.  Single  Instruction  Multiple Threads(SIMT) is utilized in thread blocks to improve the execution efficiency of threads; Compared to CPU and GPU,  the  FPGA  is  closer  to  the  underlying hardware,  limited  by  its  own  resources.  Therefore  optimization strategies of  the  FPGA are to optimize the  design  of  circuitusing hardware  description  language  or  high  level synthesis language to make the use of resources more efficient and improve the throught of FPGA. According to recent  achievements,  GPUs have  a  better  performance  than CPUs on  sorting. The research  interests for further study are proposed in the final section. Key words  Modern  Hardware  Processors;  Sorting  Algorithm;  Memory  Access  Hierarchy;  Parallelism Optimization; Graphics Processing Unit; Field-Programmable Gate Array  1  引言 计算机硬件技术的迅速发展使得计算机的计算能力不断提高.一方面,处理器结构不断变化,从传统的单核处理器,到多核处理器(Multi  Cores),再到众核处理器(Many  Cores),处理器内核数量不断增加;另一方面,随着存储技术的不断发展,存储方式的增加,从外存到内存再到缓存(Cache),使得计算机的访存效率不断提高.计算机硬件技术的发展持续缩短着程序的响应时间,而除传统中央处理器(Central Processing  Unit,  CPU)架构外,新型处理器设备的出现则使高性能计算进入到新的时代.由于新型硬件处理器设备大多有自身的存储模块,CPU上并没有相应的大容量存储模块,因此本文将配备大内存的多核CPU处理器称为CPU端,以CPU端和新型硬件处理器设备作为现代硬件的关注点.排序是很多计算机领域中都必不可少的基本数据处理操作[1],在数据挖掘、超级计算、信息系统等领域都存在大量的排序任务,通过排序能使得数据以一定的顺序进行排列,从而减少后续操作的时间,如数据的查找,在有序的数据集上进行数据查找操作.除了数据在内存中能顺序访问,访存效率高于随机访问以外,还能使用二分查找、按位移查找等高效的数据查找方法,使得有序数据集的查找效率远高于无序的数据集上的数据查找效率,因此排序的性能优化一直受到研究者的关注.在排序领域,已经有不少的研究者提出了许多排序方法,这些方法有各自的优缺点,也有各自适合应用的场景,而计算机硬件条件的发展也对排序方法的优化提出了新的要求.根据最新的计算机硬件条件以及排序方法的适用情况,研究者们在CPU端、众核架构的图形处理器(Graphics Processing Unit, GPU)、Xeon Phi和侧重硬件设计的现场可编程逻辑门阵列(Field-Programmable  Gate Array, FPGA)上做了相应的优化工作,使排序操作的性能有了大幅度的提高. 在早期受限于计算机内存的不足,相当长的时间里,研究者对排序操作的研究主要在于外存排序(External  Memory  Sorting)[2],数据存储于外存设备(主要是磁盘)中,程序将需要将数据从外存设备中读取到内存中才能进行排序工作,在排序过程中还会在外存与内存间产生多次中间结果的交换,因此外存排序主要的性能瓶颈在于内存和外存间频繁的I/O.随着内存容量增加,数据得以全部存储在内存并进行排序等操作,外存排序中内外存间的I/O瓶颈也随之消失,取而代之的是排序算法对内存存储访问层次(Memory  Access  Hierarchy)的利用效率.除此之外,单个处理器核心的增加、多线程处理概念的提出以及软件并行技术的成熟,提高着处理器设备的并行处理能力,使得在其上实现的排序方法性能得到了极大的提高.与其他并行计算需要面对的问题相同,并行的排序算法需要避免数据划分的不平等而导致的负载不均衡、多线程的资源争用、内存访问冲突等问题.此外,新型计算处理器设备的出现也为排序方法提供了新的优化方向. 在经典的排序算法[3-7]中,插入排序(Insertion Sort)和快速排序(Quick  Sort)是高效的小序列排序算法,适用于数据划分后各线程的本地排序过程.而归并排序(Merge  Sort)的思想非常适合多线程并发执行,因此在并行排序算法的最后阶段通常都会使用归并排序,将各线程排好序的子序列合并为最终的排序结果.基数排序(Radix  Sort)与桶排序(Bucket Sort)都有将数据进行分桶的过程,当数据划分为多个桶时就能使用多线程处理不同的桶数据,达到并行化的效果.但基数排序和桶排序都无法处理数据偏斜问题,一旦数据严重偏斜,基数排序将退化为按论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  3 位逐位比较的排序算法,而桶排序将与插入排序性能相当,都将降低算法的性能,并行的优势也完全体现不出来.计数排序(Counting  Sort)一定程度上解决了这个问题,在分桶前会先计算整个序列的数据直方图,获得数据的分布情况,根据直方图计数排序将待排序序列平均地分到多个线程进行排序,使得各线程负载均衡.数据直方图的出现一定程度解决了分桶负载不均衡的问题,因此在一些基数排序的实现过程中会引入直方图的计算,以平衡各桶的数据量. 经典的排序算法大多是在串行执行的前提下设计出来的,而以双调排序(Bitonic  Sort)[8]和奇偶排序(Odd-Even  Sort)[9]为代表的排序网络则是专为并行机器设计的排序方法.排序网络由多个比较器按照一定的逻辑连接而成,每一个比较器的位置和比较结果都清楚确定,不会出现程序的分支预测情况,因此非常适合使用现代的并行化技术,如单指令多数据流技术(Single  Instruction  Multiple  Data,SIMD).与此同时,虽然双调排序等排序网络最初是专为并行机器设计的排序方法,但却拥有O(n*log2n)的高时间复杂度.为此研究者提出了许多关于降低时间复杂度的并行排序成果,理论上的时间复杂度能到O(n*log(n)),但由于排序过程中的通信代价较高、理论模型和实际模型间的差异,实际的时间复杂度要达到O(n*log(n))是很难的,这些研究成果在实际的并行机器环境下只有部分的目标得以实现,性能加速效果并不比串行的排序算法明显,需要做相应的改进优化工作[10]. 在现代的CPU端以及新硬件处理器的条件下,排序操作的优化主要从排序方法的优化实现出发.基于设备的硬件特性,考虑方法本身的特点如何与硬件的结构特性相结合,利用设备多核多线程处理的并行特性,提高算法的各级并行度;同时考虑设备的存储访问层次,利用设备上的高速存储单元,减少访存延迟,优化存储中数据的排列方式,提高方法的访存效率. 本文将主要对现代硬件上的并行内存排序方法研究成果进行总结,详细阐述不同硬件设备上排序方法的优化策略,分析其优缺点,同时展望未来研究的方向.第2节介绍CPU端排序方法的优化工作,第3节介绍GPU上实现的排序方法,第4节介绍其他新硬件设备(FPGA 和Xeon  Phi)上实现的排序方法,第5节将对文中介绍的优化进行分析对比,第6节讨论未来的研究方向. 2  CPU端上的排序方法 在外存排序的时代,内外存间存在着大量的数据拷贝过程,而频繁的I/O传输数据会导致计算性能的严重下降,因此排序方法的瓶颈主要在于内外存间的I/O,而当内存容量足以容纳全部待排序的序列甚至整个数据库应用时,排序方法的访存瓶颈从内外存间的I/O转换为不同层次的存储访问[11].工业技术的发展使得CPU的主频变快,但存储的访问速度却发展缓慢,而在CPU和主存之间还有寄存器(Register)、cache、TLB等访存设备,不同的存储层次间的容量和访问速度都存在着差异,存储利用的不足会导致cache 缺失,从而增加算法的执行时间,因此根据存储访问层次进行算法优化能提高算法的性能. 提高算法性能的另外一个途径是算法并行化,计算机硬件的发展给并行化提供了实现的条件,从单处理器多核心、多线程处理,到向量处理器、SIMD处理,硬件并行化发展的同时,软件并行化技术也在不断完善,使得研究者更好地利用计算机硬件上的多级并行特性.综上所述,针对不同的访存要求,结合并行优化技术对经典的排序算法进行相应的改进能让排序算法的性能得到极大的提升.本节将主要介绍现代CPU端基于存储访问层次和SIMD等并行技术的排序算法. 2.1  排序方法概述 在排序方法中,归并排序、基数排序等经典排序算法与以双调排序为代表的排序网络拥有各自的特点,是大多数研究者选择的三种优化对象. 归并排序属于稳定的比较型排序方法,主要利用分而治之(Divide  and  Conquer)的思想,首先将待排序的序列进行划分,直到数据集被划分为单个数据,然后将所有的数据逐步进行排序合并,完成排序过程. 基数排序是一种非比较的排序方法,通过将待排序的数据按数据位从高位到低位(或从低位到高位)进行分桶,从而获得在该数据位上有序的数据,重复整个过程则会得到有序的数据集.基数排序的优点在于不需要在数据集中进行大量的比较,只通过多次桶的划分就可以完成排序,但如果小数据量排序的效率高于继续分桶排序的效率,基数排序的策略反而会影响全局的排序性能.在基数排序的实现过程中还会加入数据直方图,以获得各桶数据量的4  计  算  机  学  报  2016年 均衡. 双调排序网络(简称“双调排序”)是基于Batcher定理构建的一种常用的排序网络.Batcher定理给出,任意长的双调序列划分为等长的两个部分,第一部分与第二部分按照原来的顺序进行比较,将较大的数据放入MAX序列,较小的数据放入MIN序列,这两个序列依然为双调序列,且MAX序列中每一个数据都大于等于MIN中的每一个数据.双调排序网络中每一个比较器的位置都是排序前确定的,因此不存在分支预测情况,符合SIMD指令的实现要求. 2.2 基于存储访问层次的优化 Jimenez-Gonzalez[12]等研究了基数排序与存储访问的关系,提出了cache 敏感的基数排序(Cache Conscious  Sorting  Based  on  Radix  sort,CC-Radix Sort).基数排序的时间复杂度很低,但是一个很重要的缺点就是缺乏数据的局部性,在大数据集上会影响cache和TLB的层次效率,导致出现很多的cache缺失.为减少cache 缺失,提高基数排序过程中所用到的向量的局部性,CC-Radix  Sort首先判断数据的大小是否与cache大小相等,不相等则利用计数排序计算序列的直方图,进行子桶划分,将向量划分为L3 cache块的大小.CC-Radix  Sort利用了多级cache的访问层次,通过对数据块大小的组织调度减少cache缺失,提高了数据块在内存中的读写效率.CC-Radix Sort使得研究者开始关注cache、寄存器这一级别存储结构的优化,但仍无法避免cache因访问冲突造成的缺失. Inoue[13]等将SIMD技术和线程级并行相结合,提出了AA-sort(Aligned-Access sort).AA-sort分为三个阶段:第一个阶段将数据划分为cache或本地内存大小的block,第二个阶段对每个block使用comb排序算法进行排序,但comb排序由于有非对齐的内存访问和循环体依赖性,会降低SIMD 的效率.因此AA-sort 首先对每个向量进行升序排序,然后所有向量组合成颠倒顺序的向量数组,再利用SIMD的转置指令将向量数组重新排列顺序,得到按顺序排列的向量数组,消除非对齐的内存访问和循环体依赖性,如图1所示.在第三阶段中,核外算法使用SIMD化的奇偶归并排序网络,同时利用访存的局部性提高整体排序性能.AA-Sort能达到O(n*log(n))的时间复杂度,但需要使用数量较多的寄存器. 原顺序0 1 2 3 4 5 6 07 8 9 ...转置后顺序0 n 2 n 3n 1 n+1 2n+1 0 3n+1 2 n+2 ...0 n 2n 3n1 n+1 2n+1 3n+12 n+2 2n+2 3n+2n-1 2n-1 3n-1 N-1. . .向量中的元素向量数组转置后的顺序0 1 2 34 5 6 78 9 10 11N-4 N-3 N-2 N-1 . . .原顺序排序后的整理 图1 AA-Sort中的转置操作[13] Hiroshi[14]等研究结构体数组的排序策略.结构体数组的排序分为两种策略,一种是将结构体的关键字和索引进行组合,对组合后的关键字索引对利用SIMD指令进行多路的归并排序,排序完成后将结构体重新排列,但重新排列的过程是随机且分散的内存访问,会导致大量的cache 缺失,且无法使用预取技术进行加速;另一种方法是直接将结构体读入内存进行排序,这种方法没有随机访问的缺点,但却无法利用SIMD的优势.针对两种方法中存在的问题,提出了一种折衷的多级多路归并排序方法.该方法在第一种方法的基础上将归并过程分为多级进行,在每一级的归并结束都重新排列一次结构体,此时需要重排的结构体数量少且体积较小,因此能减少cache的缺失.当需要排序的数据块数量较少存放在cache时,该方法使用向量化的comb排序以消除数据依赖的条件分支,当数据块数量较多存放于寄存器时则使用SIMD化的双调排序进行排序,消除了开销高的排列指令,最后将数据块进行合并. 仅依靠存储访问层次优化的成果虽然不多,但该优化思想却得到了研究者的广泛认可,并在更多的研究成果中获得了应用,同时与其他优化技术(如SIMD)相结合,提高排序操作的性能. 2.3  基于并行技术的优化 Furtak[15]等证明了对长度非常小的数组排序利用SIMD指令是很有好处的,并对插入排序、归并排序和双调排序网络进行了基于SIMD指令的优化.对于插入排序和归并排序,在排序前使用SIMD指令进行序列预处理,将原始序列排序成多个有序的小序列,然后分别使用插入排序和归并排序得到最后的排序结果,而对于双调排序网络,Furtak 则重新排列了双调排序网络中原始比较器的位置,使得双调排序SIMD化,提高排序的性能.该研究成果详细描述了使用SIMD指令的流程,包括数据在内存的对齐、在SIMD 寄存器中的存放方式,尽管现在SIMD向量寄存器的位数增加,SIMD 指令集也发生论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  5 了一定的变化,该研究成果仍具有一定的参考价值. Cell处理器是一种异构的多核处理器,其上有多个通过DMA和主存间交换数据块的纯SIMD协处 理 器(Synergistic  Processing  Elements,SPE). Bugra[16]等使用SIMD改进了双调排序网络,形成了分布式的排序算法CellSort,如图2所示.CellSort 分为三个阶段,第一个阶段是单个SPE里的本地排序(Single-SPE Local Sort),使用SIMD化的双调排序作为核心算法.原始的双调排序中存在着连续元素的比较,但使用SIMD指令时,元素是连续存放在向量中,同一个向量无法进行比较,因此需要对向量中的元素进行重新混洗排列,先通过一次混洗将需要比较的元素存放在不同的两个向量中,使用SIMD指令进行比较后再重新将元素混洗到正确的位置,如图3所示. 排序(m)0排序(m)1排序(m)2排序(m)P-1排序(P*m)本地排序分布式核内排序主存排序(N),N=L*P*mO(L) 内存访问分布式    核外排序图2 CellSort 第二阶段是分布式的核内排序(Distributed In-core Sort),在本地排序完成后,需要将多个SPE的排序结果合并,为了减少SPE间的通信,算法按双调排序的性质将SPE进行了升序和降序的分组,并且每个SPE使用的排序元素一半来自本地,另一半元素来自其他的SPE,如图4所示.第三个阶段为分布式的核外排序(Distributed  Out-of-core  Sort),需要将所有SPE上的数据进行合并,过程与第二阶段相似,只是SPE使用共享主存获取待排序的元素. CellSort的时间复杂度为O(n*log(n)/p),n为待排序数据量,p为处理器数量或工作线程数,本文以下含义相同.相较于3.2GHz  Xeon 处理器上的并行快速排序, CellSort能获得50%的性能提高.CellSort利用SIMD的混洗指令对双调排序网络过程中的数据进行位置的交换,该策略可用于其他类型的排序网络的优化,同时SPE间的数据存取形式也有利于通信效率的提高. a1 a2 a3 a4 b1 b2 b3 b4a1 b1 a3 b3 a2 b2 a4 b4s1 s3 s2 s4 l1 l3 l2 l4s1 l1 s2 l2 s3 l3 s4 l4比较和交换s1=min(a1,a2) s2=min(a3,a4) s3=min(b1,b2) s4=min(b3,b4)l1=max(a1,a2) l2=max(a3,a4) l3=max(b1,b2) l4=max(b3,b4)相同的混洗模式3 2 5 4 7 6 9 83 7 5 9 2 6 4 82 6 4 8 3 7 5 92 3 4 5 6 7 8 9比较和交换a1 a2 a3 a4 b1 b2 b3 b4a1 a2 b1 b2 a3 a4 b3 b4s1 s2 s3 s4 l1 l2 l3 l4s1 s2 l1 l2 l3 l4 s3 s4比较和交换s1=min(a1,a3) s2=min(a2,a4) s3=min(b1,b3) s4=min(b2,b4)l1=max(a1,a3) l2=max(a2,a4) l3=max(b1,b3) l4=max(b2,b4)不同的混洗模式3 4 6 5 2 7 9 83 4 2 7 6 5 9 83 4 2 7 6 5 9 83 4 6 5 9 8 2 7比较和交换 图3 Cell排序中的混洗过程[15] C C C C C C C CSPE0              SPE1             SPE2             SPE3             SPE4            SPE5             SPE6             SPE7SPE0处理SPE2处理SPE4处理SPE6处理SPE3处理SPE1处理SPE7处理SPE5处理 图4 Cell排序中的分布式的核内排序[15] Cagri[17]等分析了sort  merge-join 的过程,其大部分的时间消耗在排序的过程,因此对排序过程进行了划分,分为寄存器、cache、内存上的排序过程.在寄存器阶段.由于寄存器容量有限,需要将数据划分到适合寄存器大小,在寄存器中进行SIMD优化后的排序网络,得到许多有序的小序列.随后在cache中使用双调排序进行小序列的合并,当待合并序列的大小超出cache大小的一半时,合并过程将转移到6  计  算  机  学  报  2016年 内存中进行,此时采用多路归并网络的方式减少计算和带宽的要求.该研究成果同时利用了存储访问层次和SIMD技术进行优化,指出SIMD向量单元位数的增加将会在排序性能的提高占有很大的比重. Hayes[18]等研究SIMD指令对排序性能的影响,认为随着SIMD 指令所能支持的向量宽度的增加,SIMD 技术将成为未来微处理器提高性能的重要方法,而SIMD对于排序算法的提高也是显著的.原有的SIMD基数排序存在每次比较的元素并不相邻,导致内存需求过大,因此提出了向量化的串行基数排序(Vectorised Serial Radix,VSR). VSR每次取相邻的元素,通过基数计算获得数据索引,然后进行局部直方图计算,通过全局直方图得到前缀和,如图5的步骤(i)~(iii)所示.然后通过前缀和与元素基数的对应关系得到元素所在最终序列的位移,如图5 的步骤(iv)~(vi)所示.为实现VSR计算直方图和计算位移的过程,需要对SIMD指令进行了扩展,加入了vector  prior  instances  (VPI)和vector  last  unique (VLU)指令,VPI 指令用于得到标识每个数组元素重复数量的掩码,VLU 则是得到用于标识重复元素在数组中最后出现的位置的掩码,并设计了相应的硬件设备.VSR 通过对原有向量化基数排序步骤的简化以及操作的精简,提高了内存的访问效率,从而提升算法性能. 10 14 19 513 20 9 24 15 1 72 2 3 1  10 14 19 5   值索引X X X X(i) 计算索引2 2 3 10 1 2 1  (ii) 局部直方图  0     1    2     3      直方图桶号索引2 4 3 30 2 6 9(iii) 全局前缀和      前缀和      全局直方图输入数组10 14 19 513 20 9 24 15 1 72 2 3 1  10 14 19 5   值索引X X X X(iv) 计算索引输入数组2 2 3 10 2 6 9  (v) 获得位移索引 前缀和6 7 9 2  位移+110 14 19 56 7 9 2  位移值    5      10 14  19    输出数组(vi) 输出结果图5 非递归的最高有效位基数排序[18] Gueron[19]等认为由于快速排序过程中存在需要将序列分成两个序列的操作,存在着无法预测的分支情况,因此无法直接使用SIMD指令并行化.为此Gueron等利用AVX指令设计了一种特殊的掩码,通过掩码对寄存器的元素进行混洗,混洗后能将需要的元素连续地存放在对应的寄存器中,达到原快速排序中分支条件判断的效果,实现了快速排序的SIMD 化,如图6 所示.该方法能一定程度上提高SIMD化的快速排序性能,但从整体的效果而言,快速排序的分支条件仍是其SIMD化的难点. 8 2 6 3SIMD  寄存器3 3 3 3SIMD 寄存器  存放轴心数据0 0xff 0 0xff比较结果-- -- 2 0第一次混洗掩码-- -- 3 1第二次混洗掩码-- -- 2 3混洗结果-- -- 8 6提取出来的查找索引和群体数量0x5 20xa 2 图6 AVX掩码混洗过程 Matvienko[20]等研究了计算生物学中的分子动力学问题,认 为 相 互 作 用 排 序方法(Interaction Sorting  Method,IS)是能有效地分析分子的运动.传统的IS 采用的是快速排序,而快速排序在利用SIMD优化方面较为欠缺,为提升整个IS 算法的性能,决定以更适合SIMD化的桶排序来替换原有的快速排序.Matvienko等首先以向量坐标投影的形式论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  7 对分子的进行分桶,各桶之间存在一定的阈值顺序,然后通过移位操作以及按位与操作,能计算出桶中分子的位移以及分子在整体中的位置,从而获得分子间的距离关系.该IS 方法中计算分子位移及位置的过程可以通过SIMD进行优化.在同样是同SIMD优化的前提下,与基于快速排序的IS方法相比,基于桶排序的IS方法在12线程下获得了1.45倍的加速比. Ahmet[21]等对归并排序的过程进行了改进.在归并的过程中,一般只由一个线程将两个序列合并,在需要归并的序列数少于线程数时将会有线程空闲,不利于充分利用线程资源.在归并过程中,线程对输入的两个序列只是读取的操作,并不会改变序列的值,因此可以使用两个线程同时进行归并的过程(Double  Merging),一个线程进行最小值部分的归并,另一个线程进行最大值部分的合并,如图7所示.经过优化后的算法时间复杂度并没改变,但是减少了线程的空闲等待.与Java库中的并行归并排序相比,经过优化的归并排序获得了50%的加速效果.该优化思想能提高线程的利用效率,若能在归并过程中加入SIMD等并行技术的支持,相信能进一步提高性能. 3 6 11 17 8 13 16 022有序子集 1 有序子集23 6 8 11 13 16 17 022小值合并 大值合并 图7 双线程的归并过程[22] 向量寄存器位长的增加,使得CPU端能同时处理的数据量增加,在同一时刻完成排序方法中多个数据的比较及交换操作,是一项能提高算法数据级并行度的优化策略,在未来的研究中将继续发挥重要的作用. 2.4 其他优化技术 Liu[22]等基于基数排序设计了一套可扩展的硬件加速器FastRadix,该加速器能作为特殊的功能单元集成到CPU的微型体系结构中.Liu 等认为在基数排序中,前缀和的计算处于一个很重要的位置,决定了整个过程的吞吐量,因此设计了两阶段的流水线前缀和计算模块以加速这部分的性能.流水线的设计会涉及到CPU中内存管理单元(MMU)和数据地址转换单元(DTLB)的使用,在读数据请求发送到MMU和DTLB时,这两个单元是不能进行写操作的,由此带来的流水线停止会降低传统流水线的性能,为解决此问题,Liu等设计了队列式的流水线,当流水线中某个阶段需要停止执行时,流水线的其他阶段仍然继续执行,直到下一阶段已经充满了数据时,为避免计算错误才会停止流水线的执行.但考虑到硬件资源的利用率和内存带宽,FastRadix 只将输入序列划分为每8 个整数一片的子序列进行排序,相对于元素数量更多的子序列,计算次数会增加,数据级的并行加速比较低. Cho[23]等主要研究了原地基数排序(in-place Radix  sort).在桶分配的过程中,原地基数排序存在数据依赖关系,无法做到完全并行,同时在桶分配完成后存在负载不均衡的问题,为此提出了PARADIS算法.PARADIS 使用投机的排列方法进行数据分桶,首先在单个处理器内将序列分成相同大小的条带(Stripe),处理器为每个桶开辟一定的空间,然后按桶将这些条带进行组合排列,但此时会出现处理器中某个桶空间满载的情况,造成某些条带处于错误的桶空间,需要对这些少量的条带进行修复,使用相同的方法对少量的条带进行重新分配,直到所有属于同一桶的条带都聚集在一起,同时加入自适应分布的策略,按照公式(1)计算出每个桶的排序时间百分比(分子为对桶i 排序的估计时间,分母为对所有桶排序的估计时间),按照排序时间的百分比进行处理器的分配,达到负载均衡.负载的均衡使得PARADIS在处理大数据量的排序问题有巨大的优势,与基于缓冲管理的基数排序[41]相比能达到两倍以上的加速.该分桶方法需要在每个处理器内形成多个条带,在将条带进行汇总组合时会产生处理器间的通信,当分桶数及处理器数量增加,处理器间控制信息会增加,需要根据设备特性进行调整. * log* logii ijj jCC PPCCbb b Î=å                  (1) Aydin[24]等对最高有效位(Most Significant Digital,MSD)基数排序的实现方法进行了改进,传统的MSD基数排序使用递归进行实现,而Aydin等实现了非递归的MSD基数排序.算法使用了两组向量进行元素的存储,首先根据最高有效位将序列存储在第一组向量中,然后在每个单独的向量中按照基数排序的步骤使用专用的排序结构依次对数据位进行排序,排序的结果存放在第二组向量,以此反复完成排序,如图8所示. 8  计  算  机  学  报  2016年 输入主向量0 1 2 3 …………… 0  n-4  n-3  n-2 n-1First_bucket[n-1]firstlenFirst_bucket[n-1]bucket[0]bucket[1]bucket[2]bucket[3]bucket[4]bucket[5]bucket[6]bucket[7]bucket[8]bucket[9]second_bucket[n-1]Sec_indexsecond_bucket[n-1]最高有效位开始考察数据中间桶图8 非递归的最高有效位基数排序[24] 在此非递归基数排序和快速排序的基础上将两者相结合形成混合的排序算法,算法在进行了若干步的非递归的基数排序后,分别对各个单独的元素向量并行进行快速排序,得到最后的排序结果.算法使用非递归的方式能有助于并行技术的使用,但是却需要使用更多的辅助空间,且并没有对数据的偏斜情况做特殊的处理,出现数据偏斜时,在快速排序进行前可能会进行较多次的基数排序. Liu[25]等对串行的STL快速排序Qsort进行了细粒度的并行实现.首先将输入序列利用类似快速排序的思想进行block划分,即算法取序列的最后一个值作为轴中心,统计序列中比轴中心小的元素个数作为划分序列的基准,划分完成后在每个block中使用并行的快速排序,最后将所有的block 合并.算法在4线程的CPU端进行了实现,是Qsort的两倍加速,与基于OpenMP实现的快速排序也有5%的速度提升.该算法基于快速排序的思想进行序列的划分,但线程间的负载均衡无法得到很好的保证. Axtmann[26]等则研究在有大量处理器以及处理器线程情况下的排序方法.在处理器数量很多时,处理器之间的通信代价必须要得到控制,才能提高排序算法在处理器数量方面的高扩展性.基于这样的考 虑 提 出 了 适 应 的 多 级 样 本 排 序(Adaptive Multi-Level  Sample  Sort),算法首先对样本进行快速并行排序,样本完成排序后需要对各个处理器上的元素序列重新分配,但此时序列长度不相等,在拥有长度较小的序列时,处理器不会对通信做出回应,因此处理器间会存在许多无用的通信.据此算法按序列长度分为小序列和大序列,分别对小序列和大序列做通信处理,拥有小序列的处理器将不再参与通信,拥有大序列的处理器则维持正常通信,从而减少整体的通信次数,最后将处理器进行分组,将序列分发到处理器上进行排序,获得更好的处理器负载均衡. Shi[27]等从比较器的角度对多路的排序网络进行了改进.原有排序网络中的比较器都采用2 元素的比较器,即每个比较器得到两个元素的有序序列,这样势必会增加排序网络的步骤数,而采用n 元素的比较器来设计排序网络则能有效地减少排序网络中的比较器数量,并在此基础上实现了多路的n元素的归并排序算法.但参数n只能为素数,且n元素比较器的理论方式与2 元素比较器相同,在实际实现过程中的效果以及能否利用更多的并行优化技术(如SIMD)仍有待研究. Aydin[28]等在EPIC  Analyze模块上研究了推特(Twitter)上的排序策略,提出了应对增量的排序算法(Incremental  Sorting  Method,ISM),ISM 能对现有的推特数据从用户要求的角度进行排序,同时能一直关注相关话题所产生的新推特数据并及时将这些数据进行排序.当产生新数据时,由于数据量众多,ISM 并不将所有数据重新排序,而只是将新增的数据进行排序,然后将新排序的数据以索引的形式更新到之前已排序的数据中,提高了排序的效率. 2.5  排序方法的相关工作 不少研究者仍关注对传统排序算法本身的改进,通过改进排序算法的思想以及排序算法的实现方式来提高排序算法的性能. Mansi[29]将输入序列分为正负两个部分,计算序列中每个数据的数量,并用两个数组分别存放正负元素的数量,以元素的绝对值作为数组索引,当每个元素的计数完成后,将两个数组合并,加入相应数量的相同元素得到最终的排序序列,该算法只需要扫描两次序列即可完成排序,但却需要消耗非常多的辅助空间,且当序列元素较稀疏时空间的浪费率太高,是一种空间换时间的方法. 杨帆[30]等提出了缫丝排序算法(ReelingSort),设立若干个一维数组作为“滚轴”,对于待排序序列中的每个元素,若比当前活动滚轴的最小数据小则添加在滚轴的首部,比最大数据大则添加在滚轴的尾部,否则考察下一个滚轴;若当前元素无法添加到所有的滚轴,则新建滚轴进行存放,并且将当前活跃的第1个滚轴设为待合并状态,不再添加数据,所有待合并的滚轴将在最后阶段进行合并.通过往各个滚轴里添加数据,能在合并操作之前增加有序子序列的长度,减少合并操作的次数.但算法中的分支条件较为复杂,会导致大量cache 缺失的出现,且内存中存在大量的数据迁移. 杨绣丞[31]等研究数组密度、数组特征、分布特论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  9 征等因素对排序算法性能的影响,提出一种基于特征值计算的排序算法,算法通过计算目标数据在序列中的特征值,求出目标数据小于序列中某个数据的从而得到元素在最终排序结果中的索引值,时间复杂度达到O(n),但需要大量的辅助空间来进行特征因素的存储,空间复杂度远高于传统排序算法. 2.6  小结 大容量主存的出现使得排序操作的操作从外存操作转变为内存操作,固然减少了内外存间的I/O交换,但内存的层次访问效率也成为新的研究关注点,随着计算机硬件的发展,硬件和软件能支持的算法并行度也越高.本节主要介绍了CPU端在并行化技术和内存访问方面的排序优化成果,其中的一些优化概念和使用的优化技术是现有计算机体系结构通用的优化方法,为排序算法在新的硬件设备和新的并行技术下进行优化提供参考. 3  GPU上的排序方法 CPU是一种较为通用的处理器,在处理一些特殊的应用(如图形渲染)时并不能达到人们预期的效果,而专门于图像处理的GPU的出现很好地解决了这个问题.鉴于GPU拥有强大的计算能力,研究者已经已经不再局限于使用GPU提高图形处理的速度,用 于 通 用 计 算 的 图 形处理器(General  Purpose Graphics Process Unit,GPGPU)同样能提高各种类型算法的性能.相比于CPU,GPU虽然在处理器频率上处于劣势,但凭借着不同于CPU的架构以及远多于CPU的处理器核心数,GPU 的计算能力仍然优于同等档次的CPU[32],被广泛用于数据库、数据挖掘、机器学习、矩阵计算等数据密集型计算领域.本节将主要关注GPU上并行排序算法的最新研究成果. 3.1 GPU上的基数排序 Sun[33]等利用CUDA(Compute  Unified  Device Architecture)进行了GPU平台上计数排序(Counting Sort)的优化.基数排序中,计算数据等级(Rank)和排序过程占的时间比毫无疑问是最高的,这两部分操作主要是对内存的读写操作,因此实现并行化的基数排序需要减少这两部分的内存访问延迟.但多线程的处理方式难免会造成访问内存的冲突,而CUDA 模 型 中 的“ 读改写” 原 子 操 作(Read-Modify-Write)能很好地解决这个问题.对于计算数据等级的操作增加一个原子操作,以减少访存冲突,而在排序的过程中由于需要修改计数数组和修改最终的排序结果数组,因此需要增加两个原子操作.除了计算等级和排序阶段,还采用了并行化的前缀和计算方法,进一步对计数排序进行了性能优化.原子操作的引入确实能减少访存的冲突,但也会造成多线程间的停等. Satish[34]等同样利用CUDA在GPU上实现了基数排序和归并排序,以256 个线程组成一个线程Block,将待排序的数据序列划分为多个子序列,利用芯片上内存(On-Chip Memory)的高带宽进行子序列上的局部排序,在局部排序的过程中计算按数据位的前缀和,最后在全局内存中合并各个子序列的前缀和,从而得到各个Block中数据的最终排序位置,完成高效的基数排序.至于归并排序,依然以Block为单位进行子序列的归并,在子序列的合并排序中采用了更并行化的奇偶排序,所有子序列合并完成后得到最终结果. Satish[35]等分别研究了CPU端上的基数排序和GPU上的归并排序.研究发现,基数排序在排序过程中并不是天然的数据并行,基数排序不规律的内存访问模式将会导致cache和访存页面的冲突,从而造成访存缺失.Satish等为此提出了软件管理缓冲的办法,将输入序列的数据重新分配到各处理器的cache中,当cache 填满时才进行共享内存的写出,同时重复利用cache,减少对内存的读写以及增加内存数据的连续性,同时利用SIMD计算前缀和,以得到数据的排序位移.归并排序是天然的数据并行算法,适合SIMD进行优化,但在标量的实现版本中,会因为有大量的预测分支错误而影响性能,而归并网络的使用能减少分支,从而减少错误预测的影响.因此当数据足够时,多线程进行归并网络排序,当待排序序列数量减少时,会将序列划分为多个chunk 进行排序,提高并行度,最后利用多路归并方法,提高内存带宽的利用. Amirul等[36]提出了两种混和的排序算法,以将CPU端和GPU端的计算资源充分利用.第一种为混合的基数合并排序(HybridRadix  sort  and  Merge sort),首先将输入序列划分为多个小于GPU内存的子序列,利用多个GPU对子序列进行并行独立的基数排序,待所有子序列都排序完毕后,将数据传输到CPU进行归并排序,得到最后的排序结果.如图9所示.该方案需要在CPU端进行两次的内存序列读取,且性能受限于CPU端的归并排序. 10  计  算  机  学  报  2016年 待排序序列第1分区第2分区第3分区第4分区Nvidia Quadro 4000Nvidia Quadro 4000部分有序数据部分有序数据部分有序数据部分有序数据部分有序数据部分有序数据有序序列基数排序 归并排序图9 混合基数归并排序 第二种算法是混合基数和桶排序(HybridRadix sort and Bucket sort).首先在CPU端将待排序的输入序列进行分桶,将桶中的序列拷贝到GPU上进行基数排序,排序的结果直接在内存中合并成为最终的排序结果,如图10所示.显然,该方案的关键在于分桶操作,桶的大小必须在GPU的内存限制之内,若桶的大小超出了GPU的内存大小,该方案则会无效,或进行二次分桶,但该方案减少了CPU的访存次数. 待排序列A   到   FG   到   KM   到   ST   到   ZN v i d i a  Q u a d r o   4 0 0 0N v i d i a  Q u a d r o   4 0 0 0有序列基 数 排 序 桶 排 序 图10 混合基数桶排序 Zhang[37]等研究字符串的排序问题,提出了以用户定义的顺序对字符串进行排序.这其中很重要的问题在于用户定义的顺序与计算机中定义的顺序是不一致的,基数排序这一不依赖于比较的排序算法适用于这一情况.由于基数算法是基于数值的排序算法,因此首先需要将待排序的每个字符串转换为相应的数字序列,在中文字母表中,每一个中文字符都对应着一个数字,对这些数字建立哈希表以加快中文字符与数字间的搜索速度,然后采用基数排序对数字序列进行排序,从而得到有序的数字序列,最后通过查找哈希表得到最终的中文字符串排序结果.如图11所示.该算法将中文字符与数字进行映射替换,以适应基数排序的要求,是字符串排序的常用思想,但却未针对基数排序的缺点进行优化,仍会出现多线程的负载不均衡. 无序字符串字符串转为整型数组无序整型数组基数排序有序整型数组有序字符串整型数组转为字符串 图11 基于基数排序的字符串排序 Deshpande[38]等同样提出了基于基数排序的字符串排序算法,主要思想在于将变长的字符串关键字转化为定长的局部前缀和,在各个字符串对应的前缀和上进行排序操作.在GPU中,Thrust 原语能为定长的基数排序提供高效的执行原语,利用Thrust原语对前缀和进行计算能提高排序的性能. 为了加快字符串的查找速度,算法首先对储存在全局内存中每个字符串首字母的位移位置建立索引,如图12所示.算法然后抽取每个待排序的字符串的前两个字母组成前缀,与索引中每个字符串的位移值形成键值对,对这些前缀和进行基数排序,得到第一次的排序结果,对第一次的排序结果进行分析,可以分为两种情况: 情况1:该前缀和在所有前缀和中没有重复.算法将该前缀和的位置进行固定,并以字符串和键值的形式存放,在之后的排序过程中不会再对该位置的前缀和进行比较修改. 情况2:多个相同重复的前缀和.若出现多个重复的前缀和,则将各个相同的前缀和进行分桶,相同前缀和进入同一个桶中,对桶中的前缀和在原字符串基础上去接下来的两位重新组成前缀和,在各个桶中分别并行地进行基数排序. 重复排序步骤,能得到最终的排序结果.如图13所示.该算法能利用多个分桶的优势,将复杂的变长比较转换成高效的定长比较,减少全局字符串的字符移动,同时能在短时间内重新分桶,解决可能存在的数据偏斜情况.但字符串长度差异较大且字符前缀相同的字符串较多时,会出现负载不均衡的情况. 论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  11 0 6 15 21 30 40 49 55R A D I X \0 C O M P U T E R \0 R A D A R \0 P A R A L L E L \0 P AR T I T I O N \0 P A R T I C L E \0 G R A G H \0 C O M P A C T \0 图12 字符串指针映射[38] GRAPH-49段ID 前缀字符串 无重复前缀 位置固定的键值对RA 0CO 6RA 15PA 21PA 30PA 40GR 49CO 55关键字 指针值排序CO 6CO 55GR 49PA 21PA 30PA 40RA 0RA 150011122去除无重复生成段ID加载后续字符MP 6MP 55RA 21RT 30RT 40DI 0DA 150011122关键字 指针值GRAPH-49排序MP 6MP 55RA 21RT 30RT 40DA 15DI 0001100关键字 指针值GRAPH-49加载后续字符MP 6MP 55IT 30IC 400011PARALLEL-21RADAR-15RADIX-0GRAPH-49…PARALLEL-21RADAR-15RADIX-0 最后输出结果COMPACT-55COMPUTERL-6PARTICLE-40PARTITION-30 图13 基于改进基数排序的字符串排序[38] Kumari[39]等在GPU上结合基数排序和选择排序,提出基于划分和并行的选择排序算法(Split  and Concurrent  Selection,SCS),SCS算法首先按处理器的数量将输入的数据序列划分为等长的子序列,在每个子序列中使用并行基数排序对子序列进行排序,然后用并行的选择算法获得每个元素在最终排序结果中的位置,最后只需要将对应的元素拷贝到相应的位置,完成排序.SCS 能利用基数排序的高排序效率以及选择排序高效的数据定位,但在面对大数据量时,选择排序的效率会降低,需要对选择排序的数据量进行优化. Drozd[40]等在CPU端和GPU上利用MSD基数排序实现了字符串的排序过程.算法首先将待排序字符串序列进行基数分桶,在算法开始阶段,桶的数量较少,桶中的数据量大,算法将桶中数据按照线程数量进行分块计算;而随着每个桶的迭代划分次数的增加,新分出来的桶内数据会变少,桶的数目也会增加,当桶的数目达到一定阈值时,分支情况的增加,会使得GPU的加速效果下降,因此算法会将最后阶段大量的小桶排序换到CPU端进行处理.该算法能利用CPU端和GPU不同的特性提升算法性能,且对CPU端和GPU间的传输过程进行了优化处理,每次迭代时只从CPU端向GPU传输所有字符串的一个字符以及字符串的索引指针,减少每次传输的数据规模,但当字符串较短时,此方法带来的性能提升将不足以抵消每个字符串重新划分单个字符的开销. 3.2 GPU上的排序网络 Ye[41]等认为虽然基数排序在GPU上能获得很好的排序性能,但由于基数排序不是基于比较的排序算法,会缺失一般性,因此研究了GPU上基于比较的排序算法.Ye 等结合了双调排序和归并排序,将排序任务和GPU的体系结构建立映射关系,提出了GPU-Warpsort算法.GPU-Warpsort将32个连续区域的线程聚集成一个warp,一个warp中的所有线程在单 指 令 多 线 程(Single  Instruction  Multiple Threads,SIMT)模式下进行工作.GPU-Warpsort算法首先将输入的数据序列划分为等长的子数据序列,以warp为单位在各个子序列上进行双调排序,利用warp中的线程能同时执行的优势和双调排序网络的特性减小排序过程中的障碍和分支预测错误,然后让每一个warp独立地对已排序的子序列进行合并,同时利用合并全局内存访问(Coalesced  Global Memory  Access)来减少带宽瓶颈.在合并的过程中,随着子序列数量的减少,难免会降低算法的并行度,此时算法会将其中较长的子序列进行二次划分以提高算法的并行度,最后将这些子序列交由不同的warp 进行最后的归并操作, 如图14 所示.GPU-Warpsort算法总的复杂度为O(n*log(n)),与Satish[34]等提出的归并排序相比,GPU-Warpsort算法仍有30%的性能提升.GPU-Warpsort算法在归并的12  计  算  机  学  报  2016年 最后阶段对较长的子序列重新划分以提高线程利用效率,其中涉及到再次划分所带来的负载不均衡问题,要求的划分策略将不再是简单的平均划分,有成为性能瓶颈的可能. 输 入 . . .. . .步骤1 在warp中进行双调排序. . .步骤2Warp归并 Warp归并 Warp归并 Warp归并. . .Warp归并 Warp归并… …划分为独立子序列 步骤3Warp归并 Warp归并 Warp归并 Warp归并 步骤4输 出 . . .. . . 图14 GPU-Warpsort过程[41] Peters[42]等利用CUDA实现了双调排序网络,认为要减少算法的运行时间,就要减少全局内存的访问和核心程序启用的数量.为此需要将双调排序网络中的操作集进行划分,划分后的操作子集能在单个线程或单个线程块中运行,同时利用高性能的共享内存访问,使得每一个待排序的数据序列在全局变量中的读写次数最多为一次,从而减少全局内存的使用.传统的双调排序只能对长度为2n的数据序列进行排序,为了对任意长度的数据序列进行排序,Peters等将对序列长度不规整的序列进行最大值的虚拟填补,以满足2n的要求,如长度为2n+1的序列将填补为2n+1的序列进行排序.对拥有普通数值和最大值的子序列排序时,其中的最大值不需要移动,因此最大值可以不用实际存在于内存中,也就不需要额外的内存空间进行存放.该算法相比于同时代GPU上性能最好的基于比较的排序算法,性能上有50%的提升,但却由于双调排序网络本身的高算法复杂度,性能低于GPU上性能最好的基数排序.该算法中对GPU共享内存的使用能提高访存效率,同时也为不规整的序列提供了使用双调排序网络的方法,但有助于提高线程效率的SIMT技术并没有在算法中获得实用. Peters[43]等中研究众核体系结构上的双调排序,认为自适应双调排序虽然能以双调树的形式重新组织数据,减少了算法的时间复杂度,但是在小序列的排序上效率依然不足,因此利用其他排序算法弥补小序列排序效率的不足.其他排序算法大多是基于数组的形式实现,若使用混合的算法会因双调树的结构而变得耗时,为此提出了基于区间重排的双调排序(Interval  Based  Rearrangement  bitonic  sort, IBR bitonic sort).IBR bitonic sort 依然使用数组来存放输入序列,同时使用序列开始位置和序列长度的方式表示进行双调排序网络的序列区间,达到和双调树同样的优化效果,如图15所示.IBR  bitonic  sort在时间复杂度不变的前提下与其他适合处理小序列排序的算法组成混合算法,在不同型号的GPU上对32位整型数和64位整型数进行排序,IBR bitonic sort的性能都优于Ye[41]等和Peters[42]等的排序方法. Kruliš[44]等研究了相似对象的搜索技术,基于排列的物体索引技术是当前较为流行的技术,对于大规模的高维数据集而言,大量的索引建立过程成为了性能提升的最大障碍.Kruliš等将索引的建立过程迁移到GPU上,以利用GPU的大量线程加速索引的建立,其中包括了排序以及最近k个参考点的选择.每个参考点有许多的距离,将这些距离分为若干个块,每个块有n个距离,每个线程利用双调排序网络对每个块进行排序,由于只需该点的前n个距离,因此可以对双调排序的归并阶段进行裁剪.在每个数据块完成排序后,算法对相邻的奇偶块进行向上的归并操作,使得奇数块中存储的是相邻块的距离最小值集,此时可以将偶数块丢弃,对剩下的奇数块继续进行归并,直到获得最小的n个距离.该算法对双论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  13 调排序的裁减方法能减少每一次需要进行归并的数据规模,有助于Top-k查询的性能提升. 索  引：0  1  2  3  4  5   6   7   8   9   10  11  12  13  14  15关键字 ：2  3  5  7  8  10  13  15  17  14  12  11   9   7   3   1A=23 57 8101315E11714 1211 973123 57 8E21714 1211 9E373110131523315787171412111315910E1 , 0    [ 0 , 8 ] , [ 8 , 8 ]E2 , 0    [ 0 , 5 ] , [ 1 3 , 3 ]E2 , 1    [ 8 , 5 ] , [ 5 , 3 ]E3 , 0    [ 0 , 2 ] , [ 1 4 , 2 ]E3 , 1    [ 4 , 1 ] , [ 1 3 , 1 ] , [ 2 , 2 ]E3 , 2    [ 1 2 , 1 ] , [ 5 , 1 ] , [ 1 0 , 2 ]E3 , 3    [ 8 , 2 ] , [ 6 , 2 ]~~~~~~~ 图15 IBR过程[44] 3.3 GPU上的其他排序方法 Leischner[45]等认为样本排序是分布式内存结构中最高效的基于比较的排序算法之一.在按样本排序选出序列划分值后,对桶中的数据进行计数,以直方图的形式存放在全局内存,然后计算直方图的前缀和以获得各个桶的全局位移,最后各线程计算桶中数据的桶内位移,与全局位移结合得到最终结果.为了获得负载均衡,在所有分桶完成后,算法按桶的大小顺序进行排序,将桶再分成多个适合存放于共享内存的chunk,在共享内存中则使用奇偶排序对chunk 进行排序,减少了高开销的全局内存访问,提高效率. Cederman[46]等研究了GPU上快速排序的实现过程,提出了GPU-Quicksort算法.算法主要分为两个阶段,在第一个数据划分阶段中,由于数据序列的划分尚未完成,数据子序列的数量不足以使所有的线程块单独处理一个序列,因此多个线程块将同时处理同一个子序列的不同部分,此时需加入必要的原语以获得线程块间的同步.在第二阶段,当数据子序列的数量足够多时,每个线程块将在本地共享内存中处理数据子序列,减少了线程块间的同步操作,由于GPU中线程数众多,每个线程块分到的数据子序列相对较小,因此在线程块中使用双调排序对子序列进行排序.GPU-Quicksort的算法复杂度为O(n*log(n)/p),能利用GPU上的局部共享内存,同时快速排序所得到的子序列将存在顺序关系,大大简化最后的子序列归并的过程,但需要对数据偏斜的情况进行特殊处理. Davidson[47]等提出了一种高效的并行归并排序算法,通过使用大量的寄存器通信,减少共享内存之间的通信,加快了访存速度.排序过程总共分为三个部分,第一部分是块排序(Block  Sort),每个线程只对8 个元素一组的序列片进行双调排序,然后对这些序列片进行合并,最终将得到多个大小为1024的子序列.第二部分的简单归并(Simple  Merge  Sort)将使用共享内存将各个寄存器中的子序列进行合并,为了提高共享内存的效率,算法分别在寄存器和共享内存中加入了两个窗口,使得寄存器中的内容和共享内存中的内容相匹配,从而适合任意长度的子序列合并.在从寄存器子序列中计算数据在共享内存中的位置时,算法采用二分查找和线性查找相结合,只用二分查找寻找子序列中第一个元素的位置,余下的位置用顺序查找来完成,高效完成各个块在共享内存上的序列合并.第三部分的多路归并(Multi Merge)会将各个块中的序列划分成多个部分,由多个线程完成最后的合并.在定长字符串排序方面,与Satish[34]等提出的归并排序相比有50%的性能提高.由 于 算 法 可 以 对 任 意 长 度 的 序 列 进 行 排序,Davidson等在此基础上开发出为变长键值对的排序模式,有效地解决了变长字符串的排序问题. Yang[48]等研究了输入序列的分布情况对排序算法的影响,提出了GPU上考虑特殊分布的排序算法(Improved Sorting considering Special Distribution, ISSD).ISSD 首先对样本排序进行了改进,选择了较多的样本元素进行了分桶排序,在排好序的样本元素中再选取一定数量的元素进行原始序列的划分.在子序列排序过程中,当元素数量少于512 个时使用更有效率的奇偶排序网络,元素个数多于512 个时则使用并行的快速排序.在整个算法框架上ISSD考虑了以下三类特殊的输入序列分布. 第一类序列是元素值所在的值域较窄的序列,由于整体序列的至于较窄,序列中会存在大量的重复元素,因此将唯一的元素挑选出来进行排序,再与重复的元素合并即可;第二类序列是大部分的元素都有序的序列,由于是大部分元素有序,因此也只需要将少量的无序元素筛选出来进行排序,再与原始序列进行合并,挑选的过程中可能会需要多次的分支情况处理;第三类序列是阶梯式的数据序列,即序14  计  算  机  学  报  2016年 列的分多个区域,各个区域的顺序按区域元素极值的大小排列,此类序列能方便地将序列按大小划分为多个桶,进行排序后按桶的顺序进行合并,但却会出现负载不均衡的问题.ISSD 考虑输入序列的分布能利用序列的特征,从而简化排序过程中的步骤,提高排序的性能,但若序列的分布特征不明显,无法针对序列特征做出优化,就会多耗费序列特征的分析时间,可以考虑将序列进行抽样,对样本进行特征分析,进而近似地认为序列拥有相同的特征.. Banerjee[49]等研究混合计算平台上的快速、可扩展的并行排序方法,认为在GPU进行排序时,CPU的空闲是一种资源浪费,该排序方法将对样本排序进行了改进,CPU 端的资 源也利用起来,形成CPU+GPU的混合计算平台,如图16所示. CPU混 合时间发送代码发送数据 计算计算数据传输数据传输发送结果GPU 图16 混合CPU-GPU平台计算[49] 混合平台上的样本排序分为四个阶段: (1)  在CPU端从输入序列中选择多个分界点,基于分界点对输入序列进行子序列划分,将划分好子序列的输入序列分为两部分,分别作为CPU和GPU上的排序序列; (2)  分别在CPU和GPU上计算输入子序列的直方图; (3)  分别找到直方图中各数据的位置,将序列中的数据分到相应的桶中; (4)  在CPU和GPU上重复前三个阶段,直到最后所有的桶足够小,能在GPU上进行排序,从而完成序列的排序. 由于CPU和GPU之间存在着计算能力的区别,在相互传输数据的过程中会出现停等的现象,而当待排序的数据量增大时,频繁的数据交换将使得传输速度成为性能瓶颈. 3.4  小结 计算机存储体系、硬件体系以及软件并行技术的发展使得程序算法的性能得到了极大的提高,GPU的出现带来了新的硬件体系结构,也带来了新的并行化技术.针对GPU的架构特性,研究者对排序方法进行优化改进,提高了排序操作的效率.随着硬件技术的不断发展,性能更强大的处理器设备将不断出现,如何继续利用这些处理器设备,不断地提高排序算法的性能将成为新的挑战. 4  其他新硬件设备上的排序方法 作为与GPU类 似 作 用 的 新 硬 件 加 速 设备,FPGA 以及Intel  Xeon  Phi也逐渐受到了研究者的关注. FPGA是以并行运算为主,主要以硬件描述语言来实现,相比于PC或单片机(无论是冯诺依曼结构还是哈佛结构)的顺序操作有很大区别.FPGA 对排序方法的实现更接近硬件的底层实现,通过逻辑元件和门电路的组合完成定制功能,能在一个时钟周期内完成多个功能,以达到并行加速效果. 在2012年因特尔推出了Intel Xeon Phi协处理器[50], 是 基 于 多 集 成 核 心(Many  Integrated Core,MIC)体系结构的多核处理器,技术架构和之前Intel用在服务器、超级电脑的基本技术构建块相同,更专注于提高协处理器的通用计算能力.虽然Phi的核心数量不如GPU,但计算能力同样强大,同样适用于加速数据密集型算法的性能. 本节分为两个部分,第一部分介绍FPGA 上排序方法的研究成果,第二部分则介绍MIC体系结构上以及排序相关的研究成果. 4.1 FPGA上的排序方法 Alquaied[51]等基于输入流和存储介质都是有限的情况下设计了FPGA 上的排序算法.算法为每个输入的数据保存一个类似时间戳的数值,利用插入排序的思想进行排序,为了利用有限的存储介质,算法会在存储介质存满的情况下淘汰存储介质中存在时间最久的数值,只保存最近排序的数值. 吕伟新[52]等以FPGA实现了一种比较矩阵排序器,原理在于将一个元素与序列中所有的元素进行比较,大于被比较元素的结果记为1,否则记为0,当所有元素比较完之后,对比较结果进行累加,则获得该元素的最终索引值.将序列的所有元素分别作为一个矩阵的行值和列值,每个行值和每个列值进行比较,矩阵内部则记录每对行列值的比较情况(除去对角线外),比较完成后,对矩阵的每一行进行相加得到该行值的最终索引值.该排序器在7 元素的输入下仅有27ns的延迟,但随着同时输入元素的增加,需论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  15 要的FPGA 逻辑单元也呈指数增加,无法完成过多输入元素的同时排序. Sogabe[53]等研究FPGA 上基因序列的匹配问题.每个待匹配的基因序列都会被划分为若干个片段(short  read),每个片段再由固定长度的种子(seed)组合而成,Sogabe 等将每个片段放在左移寄存器中,通过逐位左移提取种子.每个种子都分为索引和关键字两部分,分别形成索引表和CAL表,根据种子的索引对种子进行进行分桶排序,每个桶的大小为8的倍数,以提高FPGA上的桶与FPGA外的桶的读写效率.在排序后,相同索引的种子能聚集在一起,从而简化匹配的过程.对种子进行排序后的匹配系统与原始系统相比获得了3倍到14倍的加速. Sklyarov[54]等研究FPGA上的排序网络.分析指出,当前排序网络的研究着重于网络比较器或网络步骤的减少(如奇偶归并网络和双调归并网络),而网络的规整性和连接性则很少受到关注,认为奇偶转换网络拥有良好的规整性,能有效地在FPGA 上进行实现.奇偶转换网络的规整性在于每一个比较步骤都完全一样,因此在电路设计时能够重复利用原有的电路进行多次的迭代,减少电路的元件使用数量以及电路的复杂度.为了减少迭代次数,还对待排序序列的首值和尾值进行预比较,防止最大值在序列首位(最小值同理).基于此种思路,Sklyarov等还提出了以两个比较步骤为核心的流水线排序电路,以获得更高的吞吐量.所提出的电路设计方案在减少FPGA的资源利用、降低FPGA的使用成本上有明显的优势,但在吞吐量方面,奇偶归并网络仍是Sklyarov等设计的电路的两倍以上. Chen[55]等研究了在FPGA 上部署双调排序网络的问题,提出了在能耗和存储方面高效的排序网络映射方法,使用这种方法能提高FPGA 上排序网络的数据并行度,同时支持连续的数据流.该映射方法将“折叠”双调排序和Clos网络相结合,根据数据并行度和I/O带宽构造排序结构,提出了流水线式的流排列网路,以实现双调排序的所有交互模式,解决了当数据集变大时双调排序所产生的高路由复杂度、区域消耗、I/O 带宽的问题.该FPGA排序网络与SPRIAL[56]排序网络相比,能耗将近减少一半,最大的吞吐量能多出一倍以上. 4.2 MIC体系结构上的研究成果 Intel在CPU、GPU和基于MIC体系结构的处理器Knights  Ferry(KNF) 1上分别实现了基数排序.相比于GPU,KNF的L2 cache容量更大,能容纳更多的数据,减少了数据的装载次数,同时MIC体系结构适合SIMD指令的使用,因此KNF处理器上的基数排序性能优于GPU上的基数排序[57]. Tian[58]等在Phi上实现了寄存器级的排序算法(Register  Level  Sort  Algorithm),首先将序列划分为多个寄存器大小的小序列,小序列存放于寄存器中,在寄存器层面使用改进的双调排序网络进行排序.同一个寄存器中是不能进行数据比较的,无法按照双调排序网络原始的数据位置完成排序,针对这个问题,Tian 等提出了两种改进的方法. 第一种方法称为单寄存器方法,使用一个额外的寄存器,将数据完全复制过去,将额外寄存器的数据重新排列,从而实现寄存器内部元素的比较.如图17所示: 12341234  步骤      1          2      3拷贝数据 图17 单寄存器方法[58] 第二种方法称为双寄存器方法,将这两个数据中的一个与另一个寄存器的数据进行位置上的交换,使得元网络中在同一寄存器进行比较的两个数据位置分散在两个寄存器,完成比较步骤.根据双调排序网络的比较过程,这种方法从比较的第一阶段就开始使用,此时的数据位置与原始的位置不同,需要在排序网络的最后阶段多加一步操作将数据按正确位置存放,如图18所示: 1 1 1 1 1 1 1 1 13 4 4 4 4 4 4 4 25 5 5 6 6 6 6 2 37 8 8 7 7 7 7 3 42 2 2 2 2 2 2 6 54 3 3 3 3 3 3 7 66 6 6 5 5 5 5 5 78 7 7 8 8 8 8 8 8 步骤  1       2       3       4       5       6       额外步骤                                                                  1 Skaugen  K.  Petascale  to  exascale:  Extending  intel’s  hpc commitment.International  Supercomputer  Conference.  Available  online  at http://download.intel. com/pressroom/archive/reference/ISC_2010_Skaugen_keynote. pdf. 2010 16  计  算  机  学  报  2016年 图18 双寄存器方法[58] 得到多个有序小序列后,使用多核心级的归并算法进行归并,此时处理器间的通信不可避免.算法在归并过程中采取了merge  path[59]算法中的划分策略以均衡处理器的负载,但该策略的引入也产生额外的时间开销.算法最终的时间复杂度与线程数p、输入序列长度n以及每一个寄存器中同时完成排序的 数 据 个 数 K 有关, 为2log( ) log( ) (log( ) log( ) log ( ))*np p n K KpKæö O + +ç÷ èø. 该算法在Phi处理器上实现,通过重新排列双调排序网络中的数据位置实现了寄存器级的排序网络,同时充分利用512位长的向量处理机制以及SIMD技术,提高数据级并行度. 4.3  排序相关的应用 随着并行排序的发展,排序方法的实现也变得越来越复杂,为缩短排序方法的实现时间,研究者在保持一定排序效率的前提下,开始了排序方法自动求解、代码自动生成的研究. Shi[60]等基于形式化方法(partition-and-recur,   PAR),研究了排序算法的自动生成问题,对非降序的排序问题进行了形式化的算法规约,把一个序列按不同的方式划分成若干个子序列,使得运算更加简明.Shi 等采用了三种划分方式,分别是固定分划求解排序问题的方式(determined  bi-partition,  DBP),函数分划求解排序问题的方式(uncertain  bi-partition, UBP)方式以及H-增量方式.DBP是在某一个固定的位置将序列划分为两个子序列,求解得到的子问题的解各自有序,而互相之间无序,尚需将子解归并成原问题解;UBP 则是引入一个函数来分划出两个子问题进行求解,由子解得到原问题解的方法则取决于分划函数的性;H-增量则是按照某个递减的变量h 分裂成若干小组,各小组的解直接构成原问题的解.根据这三种求解排序问题的方式,分别设计了三个泛型算法构件DBPSort,UBPSort 和  HSort,按照三个构件所使用的基本操作和数据,将他们封装成两个类型的构件SortingList 和  Heap,依赖关系如图19所示.在得到这些构件的描述后,就能使用PAR平台将构件转换为可执行的语言级构件,在实用中组合这些构件,以自动生成排序领域的求解算法. HSort DBPSort UBPSortSortingList Heaplist Btree 图19 构建依赖图[60] Hou[61]等认为,SIMD指令虽然能在多核处理器上利用向量寄存器提高排序算法的性能,但是随着硬件水平的发展,相应的指令集也产生了变化(SSE, AVX, AVX512等),而在不同的硬件设备上使用不同的SIMD指令对排序算法进行实现是一件枯燥且易错的事情,为此提出了并行排序自动SIMD化的框架(Automatic  SIMDization  of  Parallel  Sorting, ASPaS),只需要排序网络和与设备匹配的指令集就能得到SIMD化的排序代码.ASPaS 总共有四个过程,第一个过程会根据输入的排序网络生成一系列的比较器,第二个阶段转置器和第三个阶段合并器则会利用SIMD指令集生成数据在算法中重新排列并合并的过程,最后一个阶段将产生SIMD化的代码. 5  对比分析 CPU端与GPU上的排序方法研究成果相对较多,MIC体系结构的协处理器虽然也是专注于提高设备计算能力,受到了一定的研究关注,但由于成果较少,仍需要进一步探索排序方法在其上的优化效果.FPGA则是依靠对底层逻辑电路的优化提升排序方法的性能,与CPU端、GPU和MIC属于完全不同的优化思想.本文主要关注主要关注并行内存排序方法,因此,本节将只针对CPU端与GPU上的排序方法进行分析. 5.1 CPU端的排序方法分析 存储层次访问优化以及并行技术的利用是CPU端排序算法主要的两个优化策略,基于这两种优化策略,研究者们对经典排序算法进行了多种优化,本节对现有的研究成果进行对比总结,分析其优缺点,如表  1所示. 基于存储访问层次主要在于两个方面,第一个方面是将数据重新排列,以顺序的形式存放于内存层次结构中,尽量减少算法的随机内存访问,使得算论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  17 法能利用快速的顺序内存读取速度;另一方面在于数据序列的划分,将数据序列按照最低级cache的大小进行划分,从而利用cache的高速访问,减少cache缺失,提高读写速度.CC-Radix着重研究cache和排序算法的关系,算法在cache 和TLB上的利用率很高,但访问冲突缺失并没有完全解决,影响了算法性能.AA-sort 同样在内存中将数据重新进行了对齐排列,减少cache的缺失.  Hiroshi[14]等利用了多路多级的归并排序,同时在内存中顺序存放数据,能提高访存效率,提高内存吞吐量,但也增加了访存的次数,需要利用其他技术将多次访存延迟隐藏起来. 提 高 算 法 并 行 度 的优 化 主 要 在 于 利 用OpenMP、pthread、SIMD等技术,此外还需减少线程或是处理器之间的通信代价. OpenMP、pthread技术主要提高算法的线程级并行度,而SIMD技术则主要提高数据级的并行度.由于SIMD技术没有直接的指令处理分支预测的情况,因此需要对分支情况做特殊处理,或选择分支情况确定的排序网络作为主要排序方法;同一SIMD向量寄存器中的元素无法进行直接比较,需要对多个向量中的元素进行位置混洗,达到SIMD比较指令的要求,但也引入了混洗的耗时. CellSort、VSR、AVX-QuickSort中采用了SIMD技术以提高算法的并行度:  CellSort利用SIMD实现了双调排序网络,增加了SIMD的混洗过程;VSR 则扩展了原有的SIMD 指令,新的指令尚待规范化和移植性验证;AVX-QuickSort则是利用AVX512指令实现了快速排序,其中SIMD指令用于处理算法的分支判断情况. 总之,在CPU端,根据设备的内存访问层次以及利用SIMD等并行化技术对排序方法进行优化是常见的优化方法,两者通常会同时使用,提高算法并行度的同时利用高速访存,在此之上则是针对增加线程利用率、减少线程间通信代价的优化策略. 5.2 GPU排序优化分析 GPU作为协处理器进行计算加速的研究成果较为成熟,与CPU不同,GPU 拥有大量的工作线程,其上的工作也以线程为单位,并行化的优化技术也是不同于CPU的SIMT技术,本节总结前文介绍的GPU上排序算法的研究成果,并以表格形式给出优缺点,见表2. 表1 CPU端排序算法的优缺点算法名称  改进的方法  优化技术  主要优点  存在问题  适用环境 CC-Radix[12]  基数排序 划分子序列的大小以适应cache的大小 提高算法的局部性,减少cache缺失 无法避免cache的冲突缺失 根据存储访问层次的优化技术能提高排序方法的访存效率,适用于存储层次较多的设备使用 AA-sort[13]  Comb排序 向量元素在内存进行对齐排列,提高元素的访存效率 消除非对齐的内存访问和循环体依赖 Comb排序最差情况复杂度较高,需要较多的寄存器 Hiroshi et al’s[14] 多路归并 排序 数据块较少时重新在内存中进行对齐排列 内存顺序访问和SIMD化 访存次数较多 CellSort[16]  双调排序 SIMD混洗指令实现双调排序,优化元素在各处理器的分布 数据级并行度提高,减少通信次数 SIMD混洗过程增加算法代价 SIMD技术需要硬件体系结构的支持,以使用不同程度的SIMD指令集,同时SIMD技术适合分支情况确定的排序方法使用 VSR[18]  基数排序 对内存中相邻的元素进行排序 访存效率高  需要特殊的SIMD指令进行实现 AVX- QuickSort[19] 快速排序 使用AVX掩码完成分支判断 减少分支判断情况 未在更多的访存方面进行优化 FastRadix[21]  基数排序  减少流水线的停止 提高流水线的效率 数据级的并行程度较低  作为专用的基数排序构件 DM[22]  归并排序 线程数多于待归并序列时使用双线程归并 减少空闲线程 线程利用率高 两个线程执行的指令不一致,若利用SIMD技术还需将线程分组 均匀划分序列的排序方法,应用于最后阶段的归并过程 PARADIS[23]  基数排序  投机的数据分桶方式 消除数据依赖  投机的方法需要额外的修复方法  该优化方法能均衡线程负载,适合18  计  算  机  学  报  2016年 以及负载均衡计算  均衡线程负载  线程众多、数据量大的排序 non-recursive MSD radix sort[24] 使用辅助空间代替多次基数迭代计算过程 提高算法的并行度 需要额外的辅助空间存放 中间分桶结果 存储层次空间充足的设备 BPQsort[25]  快速排序 以快速排序进行子序列排序块的划分 算法并行粒度变细,归并过程简化 线程负载均衡无法保证 待排序序列分布较为均匀,以减少子序列间的数据量差异 AMS Sort[26]  样本排序 对不同长度的序列做不同的通信处理 提高系统的整体通信效率 未利用SIMD做进一步优化 处理器工作线程数量多、通信频繁的设备 n-SortersSN[27]  排序网络 使用n元素比较器设计排序网络 减少排序网络的深度 需要重新设计并行优化方法  n元素比较器能高效实现的设备 从表2看出,GPU上优化的排序算法主要是基数排序、双调排序和样本排序.GPU 线程数量众多,一般会将若干线程进行线程块的组织,由于线程数多,如何提高线程的利用率以及取得线程的负载均衡是GPU上排序算法的一个优化方面. GPU-Warpsort利用了SIMT技术,使得同一线程块中的线程执行同样的指令,提高了算法并行度和线程的利用率,GPU-Quicksort 根据排序过程中子序列的数量调整了线程的处理策略,提高线程的利用率.另一方面,与CPU端相似,GPU上的排序算法亦需要针对访存进行优化,尽可能利用高速的共享内存,减少全局内存的使用.Satish[35]等和Amiru[36]等利用了本地的高速访存,完成线程的局部排序,Deshpande[38]等则改进了基数排序的过程,将比较字符的移动控制在局部的内存范围,减少数据的读取次数,Peters[42]等和GPU Sample Sort根据GPU的内存大小进行了数据划分,线程能在最短的时间内进行数据读取,同时减少内存缺失的次数.  Davidson[47]等则是以更高速的寄存器为主要的数据存储设备.寄存器能提高访存的速度,要提高运算性能,就需要增加寄存器数量,需要归并的子序列数量也随之增加. 表2 GPU并行排序算法的优缺点 算法名称  实现算法  优化技术  主要优点  存在问题  适用环境 GPU Couting Sort[33]  计数排序 CUDA的原子操作 减少访存冲突 没有针对内存访问层次进行优化,原子操作也会造成线程的等待 线程间访存冲突无法避免的GPU设备 Efficient Sorting on GPU[34] 基数排序归并排序 本地内存完成局部排序、细粒度的线程处理划分 提高访存效率和线程利用率 其中的归并排序,当排序键值对的位数和排序数量增加,算法性能出现下降 所实现的归并排序适用于25bit以下和数量在100万以下的键值对排序 Satish et al's[35] 软件控制cache的数据分布及换出方式,重用cache块 提高cache命中率,减少cache交换的代价 当数据bit位长增加时,排序时间却远超过倍数的增加 32 bit或64bit的数据序列 进行排序 Hybrid Radix and Merge sort[36] 在CPU端划分数据,GPU 基数排序 负载均衡 性能很大程度取决于最后 归并过程 CPU端具备高效的归并过程 Hybrid Radix and Bucket sort[36] 基数排序 桶排序 在CPU端分桶,GPU 基数排序 节省归并的过程消耗 分桶的大小受限于GPU的内存,可能产生二次分桶 使用少量GPU就能将待排序序列全部存在GPU内存中 Zhang et al's[37] 基数排序 建立中文字符数字对应的哈希表 能按自定义的顺须排序中文字符 未对基数排序算法本身进行GPU针对性的优化 字符串排序的一般做法 Deshpande et al's[38] 通过局部字符移动将变长字符变为定长字符排序 减少全局字符移动,增加算法局部性 字符串长度差别较大、有一定偏斜时,会出现线程的负载不均衡 字符串长度差异不大且字符串偏斜程度不大的字符串序列排序 Drozd et al's[40] 根据分桶中数据的数量改变排序有效利用硬件的计算优势 字符串长度较短时,CPU 端和GPU端的传输成为瓶颈 每个字符串长度较长的字符串序列的排序 论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  19 算法 GPU-Warpsort[41] 双调排序 对线程进行了分组以及利用SIMT 线程利用率高  归并过程过多  数据分布较为均匀的序列 Peters et al's[42] 利用高速的共享内存和虚拟的最大值 提高访存效率 输入序列大小增大时算法效率降低 50万规模的整数、整数对和浮点整数对的排序, 基于比较的排序过程 IBR bitonic sort[43] 以数组形式实现双调树及其他小序列排序方法 使双调排序更有效地与其他算法混合使用 未根据内存访问进行优化 小序列排序需求多的序列,或小序列无序,整个序列需要 GPU Sample Sort[45]  样本排序 桶的大小适合共享内存 利用了共享内存且负载均衡 分桶的过程较复杂  序列的划分过程是通过与轴数据的比较完成,适合数据分局较为均匀的序列  GPU-quicksort[46]  快速排序  优化线程的调度 线程并行与性能取得平衡 未对快速排序算法本身进行优化 Davidson et al's[47]  归并排序 以寄存器为主要访存单位 提高访存速度  对寄存器的数量要求较高  寄存器数量较多的GPU ISSD[48] 样本排序 奇偶排序 快速排序 根据输入序列的特征进行排序 利用序列特殊分布简化排序过程 序列的分布特征不明显则会浪费特征的检测开销 存在ISSD所能检测的三类特征序列 Hybrid-ArchitecturesComparison Sort[49] 样本排序 桶排序 利用了CPU和GPU的设备并行 提高CPU 的利用率 CPU与GPU间的通信代价、处理能力差异需考虑 CPU端和GPU间通信量少,或CPU端和GPU间处理能力能掩盖通信代价的异构平台 5.3 GPU与CPU端的排序优化比较 GPU的体系结构与CPU端存在着差异,对排序算法的优化侧重也存在不同, (1) 线程并发优化 GPU端虽然CUDA线程众多,远高于CPU端,但需要将多个线程组织成线程块,并且共享同一块高速的共享内存,这类似于CPU端每个线程拥有自身的独立cache,因此在GPU的每个线程块中使用SIMT技术能提高线程的处理效率,而在CPU端则是每个线程中使用SIMD技术,以提高算法的数据集并行度. (2) 存储访问优化 在GPU中,更高效的访存发生在高速的共享内存中,在没有带宽冲突的前提下,对共享内存的访问速度与寄存器的访问速度相当,因此同一线程块中的线程将通过共享内存进行数据的读写,但多个线程块之间的数据交换依然需要借助全局内存完成;而CPU则是每个线程拥有本地的高速cache,在本地高速cache中进行数据的读写能获得最高效的访存效率,而线程间的数据交换则需要通过内存或线程间的通道来进行,会产生一定的通信代价,因此CPU端更多的是将输入序列划分为最低级的cache大小,针对cache或者寄存器将数据重新排列,在线程本地完成局部排序,然后在内存中进行子序列的合并. (3) 优化算法类型 GPU和CPU上的排序算法优化基本上都集中于基数排序和双调网络排序,GPU 上线程较多,能同时处理的分桶较多,因此基数排序受到的关注较多;而在CPU端基数排序与排序网络受到的关注相当,但随着SIMD技术的发展,排序网络将成为研究的热点. (4) 性能对比 CPU是通用的处理器,善于处理分支判断等复杂的逻辑判断,GPU 则用大量的线程及流处理技术,计算能力较CPU而言要强,从现有的研究成果[35,56]可知,同等条件下,GPU 上的排序方法在性能方面都在不同程度上优于CPU端上的排序方法.因此相比于CPU端,GPU更适合实现排序方法,更有利于排序方法的性能提高. 6  未来研究方向 虽然在过去的几十年,研究者们一直在关注20  计  算  机  学  报  2016年 排序领域,提出了很多的排序方法,根据计算机硬件和软件的发展也做出了相应的改进,提高了排序方法的性能,但仍有许多具有挑战的问题需要进一步研究: (1) 数据的划分策略 对于多线程并行的排序算法,数据的划分处理是必不可少的,现有的数据划分策略大致分为三种,一种为按线程数平均分配数据,第二种则按照一定的策略进行数据分桶,最后一种为计算数据的分布,按分布情况进行划分.第一种划分方式实现起来相对简单,划分效率较高,线程间负载均衡,各个线程将本地的数据排序完成,最后将各线程的数据进行归并即可,但这样的划分方式并没有利用数据的特征,导致最后的归并过程较为繁琐,增加总的排序时间;第二种划分方式常见于基数排序等需要进行分桶操作的排序策略,数据进行分桶后,桶与桶之间成有序关系,最后的归并阶段只需要将各个桶的数据连接起来即可,但分桶的过程不可控,从而导致每个桶的大小不一,可能出现负载不均衡的问题;最后一种划分策略能是先获得数据的分布情况,从而确定各线程需要处理的数据量,获得线程的负载均衡,但也增加了计算数据分布的代价,而计算数据分布的最坏结果是仍按线程数的数据平均分配,浪费了计算的时间.三种划分策略有其优缺点,如何将各种划分策略的最坏情况最大程度地避免,将优势突出,从而提高整体的排序性能将是一个值得研究的问题. (2) 优化归并过程 在排序的过程中,为了利用cache的高速访问,都会将输入序列按照最低级的cache 大小进行划分,在最低级cache较小或者输入序列较大时,就会产生数量众多的子序列,使得最后的子序列合并过程成为瓶颈.归并过程必然会涉及到大量的线程通信以及数据的重新排列,若划分数据时按照一定的大小顺序将数据进行划分则会简化归并的过程,这样的思想若能穿插应用于排序的过程中,能减少最后归并过程的负担.此外,在归并过程中提高线程的利用率,特别是当序列数量比线程数少时,在不影响单个线程效率的前提下减少线程的空闲率也是提高归并效率的方法. (3) 研究输入序列的特征 当输入的序列存在某种特征,如符合特定的分布、数据较为偏斜、序列大部分有序等,利用这些输入序列的特征对简化排序步骤有很大的帮助.比较简单的检测方法是扫描序列,但当序列很大时检测的代价也不容忽视,而且并不保证每一次检测都能得到具有某种特征的序列,将平白浪费检测的时间开销,如何在检测开销和检测效率间进行权衡,使得输入序列特征的利用能真正简化排序过程的步骤,从而提高排序算法的性能. (4) 多比较标准的排序 排序过程会将数据根据计算机自身的数据大小标准进行两两比较,而当比较标准变得复杂或是与计算机自身的比较标准不同时,就需要将比较标准转换为计算机能够识别的标准.当需要的比较标准较为复杂或者需要考虑多方面的比较标准时,若将每对比较数据都进行比较标准转换会是一个很耗时的过程,如何优化这一转换过程,将排序性能的影响降到最小是一个有趣的问题. (5) 新型计算硬件设备上的排序算法研究 GPU和基于MIC体系结构的phi等新型硬件计算设备的出现给各领域的算法优化提供了新的思路,使得算法的优化不再局限于CPU的体系结构,这些新型硬件计算设备虽然在主频上无法与CPU相比,但凭借高于CPU的实际线程数以及专注于计算的体系结构设计还是能让运行在其上的程序得到优秀的加速效果.GPU 上已有的排序算法优化成果较多,phi 由于推出的时间尚短,研究成果不多,但以新型硬件计算设备作为CPU外的协处理器提高程序性能的趋势已经形成,无论是现有的体系结构还是待研究的更适合计算加速的体系结构,未来都将会出现性能更加卓越的协处理器,如何在协处理器上对排序算法进行优化,充分发挥协处理器的性能将是一个持续研究的问题,且当前研究中,并行优化的排序算法都源于经典的排序方法,协处理器上还未出现根据特定体系结构的、专用的排序思想,这将是排序算法在新型硬件计算设备上发展的难点. (6) 外存排序算法的研究 本文虽然主要关注内存中的并行排序算法,但外存排序算法方面的研究仍在继续[62-67],相比于内存,外存在容量上依然有绝对的优势,当内存容量不足以存放程序以及相关数据时,外存操作是必不可少的.随着计算机硬件技术的进步,外存设备也得到了长足的发展,固态硬盘(Solid  State Drives,  SSD)的出现使得外存的读写访问速度有了大幅度提高,速度可达传统硬盘(Hard  Disk Drive,  HDD)的数倍,在新的外存体系结构下,虽然论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  21 解决的重点仍是减少内外存间的I/O 次数,但解决的方法也会发生改变,根据新型外存体系结构优化排序算法的性能将是研究者持续关注的研究点.   致  谢 本文部分工作是在作者访问中国人民大学的萨师煊大数据管理和分析中心时完成的,该中心获国家高等学校学科创新引智计划(111 计划)等资助.   参 考 文 献 [1]   MartinWA.Sorting.  ACM  Computing  Surveys  (CSUR),  1971, 3(4):147–174. [2]   FriendEH. Sorting on electronic computer systems. Journal of the ACM, 1956,3(3):134–168. [3]   KnuthDE.  The  Art  of  Computer  Programming,  Volume 3  :(  2nd Ed.) Sorting and Searching. New York, USA: Pearson Education, 1998. [4]   Hoare CAR. Quicksort.The Computer Journal, 1962, 5(1):10-15. [5]   Katajainen  J,  Träff  JL.A meticulous  analysis  of  mergesort programs. Berlin Heidelberg: Springer, 1997.217-228. [6]   Zagha  M,  Blelloch  GE,  Radix  sort  for  vector multiprocessors.//Proceedings  of  the 1991  ACM/IEEE  conference on Supercomputing. Albuquerque, USA, 1991. 712–721. [7]   Cormen TH, Leiserson CE, Rivest RL.Counting Sort. Introduction to  Algorithms  (2nd  ed.),  Cambridge,  USA:  MIT Press/McGraw-Hill, 1990. [8]   Batcher KE. Sorting networks and their applications. //Proceedings of  theSpring  Joint  Computer  Conference,  New  York,  USA, 1968:307–314. [9]   Haberman  AN. Parallel  Neighbor  Sort  (or  the  Glory  of  the Induction  Principle),  Pittsburgh:  Carnegie-Mellon  University, CMU Computer Science Report: AD-759 248, 1972. [10]   Zagha  M,Guy  EB,Radix  Sort  For  Vector  Multiprocessors. //Proceedings  of  the  1991  ACM/IEEE  conference  on Supercomputing, New York, USA, 1991:712-721. [11]   Jiménez-González D, Larriba-Pey JL, Navarro JJ. Communication conscious  radix  sort.//Proceedings  of  the  13th  international conference on Supercomputing, New York, USA, 1999: 76-82. [12]   Jiménez-González  D,  Navarro  JJ,  Larriba-Pey  JL.  CC-radix:  a cache  conscious  sorting  based  on  radix  sort.//Proceedings  of Parallel, Distributed and Network-Based Processing, Genova, Italy, 2003:101-108. [13]   Inoue H, Moriyama T, Komatsu H, et al. AA-sort: A new parallel sorting algorithm for multi-core SIMD processors.//Proceedings of the  16th  International  Conference  on  Parallel  Architecture  and Compilation Techniques, Washington, USA, 2007: 189-198. [14]   Hiroshi  I,  Kenjiro  T,  SIMD-  and  Cache-Friendly  Algorithm  for Sorting  an  Array  of  Structures,  VLDB Endowment,  2015,  8(11): 1274-1285. [15]   Furtak T, Amaral JN, Niewiadomski R. Using SIMD Registers and Instructions  to  Enable  Instruction  Level  Parallelism  in  Sorting Algorithms. //Proceedings of the ACM Symposium on Parallelism in Algorithmsand Architectures, New York, USA, 2007:348–357. [16]   Bugra  G,  Bordawekar  RR,  Yu  PS,CellSort:  High  Performance Sorting  on  the  Cell  Processor.//Proceedings  of  the  33rd international conference on Very large data bases, Vienna, Austria, 2007: 1286-1297. [17]   Cagri B, Gustavo A, Jens T, et al.Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited. VLDB Endowment, 2013, 7(1): 85-96. [18]   Hayes  T,  Palomar  O, and  Unsal  O,  et  al.  VSR  sort:  A  novel vectorised  sorting  algorithm  &  architecture  extensions  for  future microprocessors.//Proceedings  of  theHigh  Performance  Computer Architecture (HPCA), Burlingame, USA, 2015: 26-38. [19]   Gueron S, Krasnov V. Fast Quicksort Implementation Using AVX Instructions. The Computer Journal, 2016, 59(1): 83-90. [20]   Matvienko  S,  Alemasov  N,  Fomin  E.  Interaction  sorting  method for  molecular  dynamics  on  multi-core  SIMD  CPU architecture.Journal  of  bioinformatics  and  computational  biology, 2015, 13(01): 1540004.  [21]   Ahmet  U, Parallel  merge  sort  with  double  merging.//Proceedings of  theApplication  of  Information  and  Communication Technologies (AICT), Astana, Kazakhstan,2014:1-5. [22]   Liu XY, Deng YD. Fast Radix: A Scalable Hardware Accelerator for  Parallel  Radix  Sort.//Proceedings  of  theFrontiers  of Information  Technology  (FIT),  Islamabad,  Pakistan,  2014: 214-219.  [23]   Cho  M,  Brand  D,  Bordawekar  R,  et  al.  PARADIS:  an  efficient parallel algorithm for in-place radix sort. VLDB Endowment, 2015, 8(12): 1518-1529. [24]   Aydin  AA,  Alaghband G.Sequential  and parallel hybrid  approach for non-recursive most significant digit radix sort.//Proceedings of theInternational  Conference  Applied  Computing,  Fort Worth, Texas, USA, 2013:51-58. [25]   Liu  Y,  Yang  Y.  Quick-merge  sort  algorithm  based  on  Multi-core linux.//Proceedings  of  theMechatronic  Sciences,  Electric Engineering  and  Computer  (MEC),  Shengyang ,China,2013: 1578-1583. 22  计  算  机  学  报  2016年 [26]   Axtmann  M,  Bingmann  T,  Sanders  P,  et  al.  Practical  massively parallel sorting.//Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, New York, NY, USA, 2015: 13-23. [27]   Shi  F,  Yan  Z,  Wagh  M.  An  enhanced  multiway  sorting  network based  on  n-sorters.//Proceedings  of  the  Signal  and  Information Processing (GlobalSIP), Atlanta, USA, 2014: 60-64. [28]   Aydin AA, Anderson KM. Incremental Sorting for Large Dynamic Data  Sets.//Proceedings  of  theBig  Data  Computing  Service  and Applications  (BigDataService), Redwood  City, USA, 2015, 170 - 175. [29]   Mansi  R.  A  New  Algorithm  for  Sorting  Small  Integers.  The International Arab Journal of Information Technology, 2010, 7(2): 186-191. [30]   Yang Fan, Wang Jian, Liu Ya-Nan, Cao Rui, ReelingSort: A New Algorithm in Cluster-Sorting, Chinese Journal of Computer, 2012, 35(4):802-810 (in Chinese). (杨帆, 王箭, 柳亚男, 曹蕊. 缫丝排序算法, 计 算 机 学报,2012,35(4):802-810) [31]   Yang  Xiu-Cheng,  Li  Tong,  Zhao  Na,  Liang  Li-Gang,  Li  Chao. Design  and  analysis  of  calculation  sorting  algorithm,  Application Research of Computers, 2014, 31(3):658-662 (in Chinese). (杨绣丞,李彤,赵娜,梁利刚,李超.计算排序算法设计与分析,计算机应用研究,2014,31(3):658-662) [32]   Owens  JD,  Luebke  D,  Govindaraju  N,  et  al. A  Survey  of General-Purpose  Computation  on  Graphics  Hardware.  Computer graphics forum. Blackwell Publishing Ltd, 2007, 26(1): 80-113. [33]   Sun  W,  Ma  Z.  Count Sort  for  gpu  computing.//Proceedings  of theParallel  and  Distributed  Systems  (ICPADS),  Shenzhen, China, 2009:919-924. [34]   Satish  N,  Harris  M,  Garland  M.  Designing  efficient  sorting algorithms  for  manycore  GPUs.//Proceedings  of  theParallel  & Distributed Processing, Rome, Italy, 2009: 1-10. [35]   Satish N, Kim C, Chhugani J, et al. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort.//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, Indianapolis, Indiana, USA, 2010:351-362. [36]   Amirul M, Omar M A, Aini N, et al. Sorting very large text data in multi  GPUs.//Proceedings  of  theControl  System,  Computing  and Engineering (ICCSCE), Penang, Malaysia, 2012:160-165. [37]   Zhang H, Shi S. An Efficient Algorithm of Chinese String Sort in User-Defined  Sequence.//Proceedings  of  theAsian  Language Processing (IALP), Urumqi, China, 2013:253-256. [38]   Deshpande  A,  Narayanan  P  J.  Can  GPUs  sort  strings efficiently?.//Proceedings  of  theHigh  Performance  Computing (HiPC), Bangalore, India, 2013:305-313. [39]   Kumari  S,  Singh  D  P.  A  parallel  selection  sorting  algorithm  on GPUs  using  binary  search.//Proceedings  of  theAdvances  in Engineering  and  Technology  Research  (ICAETR), Unnao ,India,2014: 1-6. [40]   Drozd  A,  Pericas  M,  Matsuoka  S.  Efficient  String  Sorting  on Multi-and  Many-Core  Architectures.//Proceedings  of  theBig  Data (BigData Congress), Anchorage, Alaska ,2014:637-644. [41]   Ye  X,  Fan  D,  Lin  W,  et  al.  High  performance  comparison-based sorting algorithm on many-core GPUs.//Proceedings of theParallel & Distributed Processing (IPDPS), Atlanta, USA, 2010: 1-10. [42]   Peters H, Schulz‐Hildebrandt O, Luttenberger N. Fast in‐place, comparison‐based sorting with CUDA: a study with bitonic sort. Concurrency  and  Computation:  Practice  and  Experience,  2011, 23(7): 681-693. [43]   Peters  H,  Schulz-Hildebrandt  O,  Luttenberger  N.  A  novel  sorting algorithm  for  many-core  architectures  based  on  adaptive  bitonic sort.  //Proceedings  of  theParallel  &  Distributed  Processing Symposium (IPDPS), Shanghai, China, 2012: 227-237.  [44]   Kruliš M, Osipyan H, Marchand-Maillet  S.  Optimizing  Sorting and  Top-k  Selection  Steps  in  Permutation  Based  Indexing  on GPUs. //Proceedings of East European Conference on Advances in Databases  and  Information  Systems(ADBIS),  Futuroscope, Poitiers, France, 2015: 305-317. [45]   Leischner  N,  Osipov  V,  Sanders  P.  GPU  sample  sort. //Proceedings  of  theParallel  &  Distributed  Processing  (IPDPS), Atlanta, USA, 2010: 1-10. [46]   Cederman  D,  Tsigas  P.  Gpu-quicksort:  A  practical  quicksort algorithm  for  graphics  processors.  Journal  of  Experimental Algorithmics , 2009, 14: 4. [47]   Davidson  A,  Tarjan  D, Garland M, et al.  Efficient  parallel  merge sort  for  fixed  and  variable  length  keys.//Proceedings  of theInnovative  Parallel  Computing  (InPar),  San  Jose, USA,  2012: 1-9. [48]   Yang  Q,  Du  Z,  Zhang  S.  Optimized  gpu  sorting  algorithms  on special  input  distributions.//Proceedings  of  theDistributed Computing  and  Applications  to  Business,  Engineering  &  Science (DCABES), Guilin,China,2012: 57-61. [49]   Banerjee  D  S,  Sakurikar  P,  Kothapalli  K.  Comparison  sorting  on hybridmulticore  architectures  for  fixed  andvariable  length  keys, The  International  Journal  of  High  Performance  Computing Applications, 2014, 28(3) 267–284. [50]   Mathur K, Agrawal S, Desai S, et al. Intel Xeon Phi: Various HPC aspects.//Proceedings  of  High  Performance  Computing  and Simulation (HPCS), Helsinki, Finland, 2013: 688-689. [51]   Alquaied  F,  Almudaifer  A,  AlShaya  M.  A  novel  high-speed parallel  sorting  algorithm  based  on  FPGA.//Proceedings  of  the Electronics, Communications and Photonics Conference (SIECPC), Riyadh, Saudi Arabia, 2011: 1-4. [52]   LV  Weixin,  LI  Qingqing,  LOU  Junling,  A  FPGA  Matrix Comparison  Sort  Algorithm and  Its  Application in  Median  Filter, Chinese Journal of Electron Devices,2012,35(1):34-38 (吕伟新,李清清,娄俊岭,FPGA  比较矩阵排序法及在中值滤波器中的应用,电子器件,2012,35(1):34-38) [53]   Sogabe Y, Maruyama T. FPGA acceleration of short read mapping based  on  sort  and  parallel  comparison.//Proceedings  of  the    24th International  Conference  on  Field  Programmable  Logic  and Applications (FPL), Munich, Germany, 2014: 1-4.  [54]   Sklyarov  V,  Skliarova  I.  High-performance  implementation  of regular  and  easily  scalable  sorting  networks  on  an  FPGA. Microprocessors and Microsystems, 2014, 38(5): 470-484. 论文在线出版号  No.157              郭诚欣等：基于现代硬件的并行内存排序方法综述  23 [55]   Chen  R,  Siriyal  S,  Prasanna  V.  Energy  and  memory  efficient mapping  of  bitonic  sorting  on  fpga.//Proceedings  of  the  2015 ACM/SIGDA  International  Symposium  on  Field-Programmable Gate Arrays, Monterey, California,USA, 2015: 240-249. [56]   Zuluaga  M,  Milder  P,  Püschel  M.  Computer  generation  of streaming  sorting  networks.//Proceedings  of  the  49th  Annual Design  Automation  Conference,  San  Francisco,  USA,  2012: 1245-1253. [57]   Satish  N,  Kim  C,  Chhugani  J,  et  al.  Fast  sort  on  cpus,  gpus  and Intel  mic  architectures.  OR  Hillsboro,  USA:  Intel  Labs,  Intel  Technical Report, 2010. [58]   Tian  XC,  Kamil  R,  Reiji  S,  Register  Level  Sort  Algorithm  on Multi-Core SIMD.//Proceedings of the 3rd Workshop on Irregular Applications:  Architectures  and  Algorithms.  New  York,  USA, 2013: 9. [59]   Saher  O,  et  al.  Merge  Path  -  Parallel  Merging  Made Simple.//Proceedings  of  theParallel  and  Distributed  Processing Symposium  Workshops  &  PhD  Forum  (IPDPSW), Shanghai ,China,2012: 1611 - 1618. [60]   Shi  HH,  Xue  JY.  Research  on  automated  sorting  algorithms generation  based  on  PAR.  Journal  of  Software,  2012, 23(9):2248-2260 (in Chinese). (石海鹤,  薛锦云,基于  PAR 的排序算法自动生成研究,软件学报,2012,23(9):2248-2260) [61]   Hou  K,  Wang  H,  Feng  W.  ASPaS:  A  Framework  for  Automatic SIMDization  of  Parallel  Sorting  on  x86-based  Many-core Processors.//Proceedings  of  the  29th  ACM  on  International Conference on Supercomputing, Austin,   USA, 2015: 383-392. [62]   Islam  M,  Sap  M,  Noor  M,  et  al.  A  Faster  External  Sorting Algorithm  Using  No  Additional  Disk  Space.  Jurnal  Teknologi Maklumat, 2006, 18(2): 47-59. [63]   Graefe  G.  Implementing  sorting  in  database  systems.  ACM Computing Surveys (CSUR), 2006, 38(3): 10.  [64]   Yiannis  J,  Zobel  J.  Compression  techniques for  fast  external sorting. The VLDB Journal, 2007, 16(2): 269-291. [65]   Wu  C  H,  Huang  K  Y.  Data  sorting  in  flash  memory.  ACM Transactions on Storage (TOS), 2015, 11(2): 7. [66]   Sundar  H,  Malhotra  D,  Biros  G.  HykSort:  a  new  variant  of hypercube  quicksort  on  distributed  memory  architectures. //Proceedings  of  the  27th  International  conference  on supercomputing. Eugene, Oregon, USA, 2013: 293-302. [67]   Sundar  H,  Malhotra  D,  Schulz  K  W.  Algorithms  for high-throughput  disk-to-disk  sorting.//Proceedings  of  theHigh Performance Computing, Networking, Storage and Analysis (SC), Denver, USA, 2013: 1-10.   GUO  Cheng-Xin,  born  in  1988, Ph.D.candidate.  His  research  interests include  data  warehouse  and  parallel computation optimization.   CHEN  Hong,  born  in  1965, Ph.D.,  proffessor,  Ph.D. supervisor.  Her  research  interests  include  database, data warehouse and wireless sensor network. SUN Hui, born  in  1977,  Ph.D.,  lecturer.  Her  research interests include mobile data management and data mining.  LI  Cui-Ping,  born  in  1971,  Ph.D.,  proffessor,  Ph.D. supervisor. Her research interests include data warehouse and data  mining,  information  network  analysis  and  flow  data managemant. WU Tian-Zhen,  born  in  1992, master candidate.  Her research interest is data warehouse.      Background The  rapid  development  of  computer  hardware technology improves the computation  ability  of processors constantly.  On  the  one  hand,  the architecture  of processors has changed from the traditional single core processors to the multi-cores  processors,  and  then  to  the  many cores processors.The  number  of  cores  on  processorskeep increasing.  On  the  other  hand,  with  the  continuous development  of memory  technology,  memory  capacityhas also  increased.Memory  units  become  diversity  like  register, cache,  RAM.  The  ultilization  of  memory  access  hierachy makes computation more efficient. Besides, the development of  computer  hardware  technology  continues  to  shorten  the response  time  of  procedures.In  addition  to  the  traditional CPU  architecture,  the  emergence  of  new  processor  devices makes the high performance computing into the new era. Sorting is  a basic  data  processing  operations in many computer  fields  like  the  data  mining,  supercomputing, information  systems,  and  other  fields.Sorting can  make  data 24  计  算  机  学  报  2016年 in a certain order, thereby reduce the time of the subsequent operationa, such  as  data  search.The operation  of data  search on  the  sorted  data,in  addition  to  accessing  the  data sequentially  in  the  memory  which  makes  data access efficiency  higher  than  that  of  random  access,also  can  use some efficient  methods like binary  search, search according to  the  offset  inthe  data  set.These  efficient methods  make sorted data set much more efficient than unsorted data sets on data  search.Therefore,the  attention  has  been  paid  by  the researchers  on  the  performance  optimization  of  sorting algorithms.   In the field of sorting algorithms, a lot of classic sorting algorithms have  been  proposed.These  algorithms  have  their own  advantages  and  disadvantages,  also  have  their  suitable application  conditions.  Acoording  to  these  conditions, researchers  have  optimized  sorting  algorithms  on  modern CPU  and  some  new  processor  devices  such  as  GPUs.This paper mainly surveys the related works and summarizes them in a brief way. This research was supported by the the National Natural Science  Foundation  of  China  (Nos.  61532021,  61272137, 61202114) and  Huawei  Innovation  Research  Program(HIRP 20140507).