-
题名基于现代硬件的并行内存排序方法综述
被引量：11
- 1
-
-
作者
郭诚欣
陈红
孙辉
李翠平
吴天贞
-
机构
中国人民大学数据工程与知识工程国家教育部重点实验室
中国人民大学信息学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2017年第9期2070-2092,共23页
-
基金
国家自然科学基金(61532021
61272137
+1 种基金
61202114)
华为创新研究计划(HIRP 20140507)资助~~
-
文摘
研究了现代硬件上的并行内存排序方法,对其研究现状与进展进行了综述.首先简要阐述了经典排序算法以及排序网络的优缺点,分析其并行优化的适用性,然后从现代CPU处理器设备(多核、配备大内存)、图形处理器(GPU)、现场可编程逻辑门阵列(FPGA)等新型处理器设备介绍现有排序方法的研究成果.处理器设备的架构不同,对排序算法的优化策略也不同,现代CPU主要利用线程的本地存储层次优化数据在存储单元中的排列,以减少访存次数及减少访存缺失,同时利用单指令多数据流技术(SIMD),以提高算法的数据级并行度;GPU则需要将多个线程组织成线程块,依靠共享内存提高线程块的访存速度,而在线程块内则使用单指令多线程(SIMT)技术提高线程的执行效率;FPGA则更靠近于硬件底层,受到自身的资源限制,FPGA的优化策略主要依靠硬件描述语言或高级综合语言优化电路的设计,提高资源利用率的同时增加FPGA的吞吐量.现有的成果表明,GPU的并行内存排序性能优于CPU端上的并行内存排序性能.作者最后对未来的研究方向进行了展望.
-
关键词
现代硬件处理器
排序算法
存储访问层次
并行优化
图形处理器
现场可编程逻辑门阵列
-
Keywords
modern hardware processors
sorting algorithm
memory access hierarchy
parallelism optimization
graphics processing unit
field-programmable gate array
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
