Efficient String Sorting on Multi- and Many-Core Architectures
Efficient String Sorting on Multi- and Many-Core Architectures
复制标题
多核和众核架构上的高效字符串排序
DOI：
10.1109/bigdata.congress.2014.97
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Satoshi Matsuoka
中科院分区：
文献类型：
--
作者：
Aleksandr Drozd;Miquel Pericas;Satoshi Matsuoka
本文讨论了在多核和多核处理器上对字符串进行高效排序的问题。我们提出了在CPU和GPU上实现最高有效位基排序算法，在执行的不同阶段采用不同的并行化策略，以实现良好的负载均衡和系统资源的优化利用。我们评估了我们的解决方案在两种体系结构上的性能，并比较了排序算法在不同密钥长度上的效率。对于GPU的实现，我们引入了一种减少通信的策略来克服PCIe总线带宽的限制。这两种实现都实现了高达每秒7000万个关键字的排序吞吐量，并具有良好的可扩展性。
This paper addresses the issue of efficient sorting of strings on multi-and many-core processors. We propose CPU and GPU implementations of the most-significant digit radix sort algorithm using different parallelization strategies on various stages of the execution to achieve good workload balance and optimal use of system resources. We evaluate the performance of our solution on both architectures and compare efficiency of the sorting algorithm on various key lengths. For the GPU implementation we introduce a communication-reducing strategy to overcome the limitations of the PCIe bus bandwidth. Both implementations achieve sorting rates up to 70 million keys per second sorting throughput with good scalability.