面向大数据的可扩展正则采样并行排序算法

王莹; 陈志广; 卢宇彤

doi:10.11959/j.issn.2096-0271.2024021

您当前的位置：

首页 >

文章列表页 >

面向大数据的可扩展正则采样并行排序算法

研究 | 更新时间：2024-08-07

- 面向大数据的可扩展正则采样并行排序算法
- A scalable parallel sorting algorithm by regular sampling for big data
- 大数据 2024年10卷第4期页码：89-105
- 作者机构：
- 作者简介：
  
  [ "王莹（1995- ），女，中山大学计算机学院硕士生，主要研究方向为算法并行。" ]
  [ "陈志广（1984- ），男，博士，中山大学计算机学院副教授，主要研究方向为大数据存储与处理、并行与分布式计算、高性能计算与超级计算机。" ]
  [ "卢宇彤（1969- ），女，博士，中山大学计算机学院教授，主要研究方向为高性能并行系统软件、大数据处理技术、HPC+AI技术。" ]
- 基金信息：
  
  国家重点研发计划项目;The National Key Research and Development Program of China(2021YFB0300103);国家自然科学基金项目;The National Natural Science Foundation of China(62272499);国家自然科学基金项目;The National Natural Science Foundation of China(U1911401)
- DOI：10.11959/j.issn.2096-0271.2024021
  中图分类号： TP399
- 网络首发：2024-07，
  
  纸质出版：2024-07-15
- 稿件说明：
移动端阅览
王莹, 陈志广, 卢宇彤. 面向大数据的可扩展正则采样并行排序算法[J]. 大数据, 2024,10(4):89-105.

Ying WANG, Zhiguang CHEN, Yutong LU. A scalable parallel sorting algorithm by regular sampling for big data[J]. Big data research, 2024, 10(4): 89-105.
王莹, 陈志广, 卢宇彤. 面向大数据的可扩展正则采样并行排序算法[J]. 大数据, 2024,10(4):89-105. DOI： 10.11959/j.issn.2096-0271.2024021.

Ying WANG, Zhiguang CHEN, Yutong LU. A scalable parallel sorting algorithm by regular sampling for big data[J]. Big data research, 2024, 10(4): 89-105. DOI： 10.11959/j.issn.2096-0271.2024021.

摘要

排序算法是计算机科学领域的一个基础算法，是大量应用的算法核心。在大数据时代，随着数据量的极速增长，并行排序算法受到广泛关注。现有的并行排序算法普遍存在通信开销过大、负载不均衡等问题，导致算法难以大规模扩展。针对以上问题，提出一种大规模可扩展的正则采样并行排序（scalable parallel sorting by regular sampling，ScaPSRS）算法，摒弃传统正则采样并行排序（parallel sorting by regular sampling，PSRS）算法中由一个进程负责采样的做法，转而让所有进程参与正则采样，选出p-1个分隔元素，将整个数据集划分成p个不相交的子集，然后实施并行排序，避免了单一进程的采样瓶颈。此外， ScaPSRS采用一种新的迭代更新策略选择p-1个分隔元素，保证划分的p个子集尽可能大小相同，从而确保p个进程对各自的子集进行本地排序时的负载均衡。在天河二号超级计算机上进行的大量实验表明， ScaPSRS算法能够成功地扩展到32 000个内核，性能比PSRS算法和Hofmann等人提出的分区算法分别提升了3.7倍和11.7倍。

Abstract

Sorting is one of the basic algorithms in computer science

and has been extensively used in a variety of applications.In the big data era

as the volumes of data increase rapidly

parallel sorting has attracted much attention.Existing parallel sorting algorithms suffered from excessive communication overhead and load imbalance

making it difficult to scale massively.To solve above problems

a scalable parallel algorithm sorting by regular sampling (ScaPSRS) was proposed

which sampled the p-1 pivot elements to divide the entire data set into p disjoint subsets by all parallel processes

rather than by only one given process as PSRS did.Furthermore

ScaPSRS adopted a novel iterative update strategy of selecting pivots to guarantee that the workloads and data were evenly scheduled among the parallel processes

thus ensuring superior overall performance.A variety of experiments conducted on the Tianhe-Ⅱ supercomputer demonstrated that ScaPSRS succeeded in scaling to 32 000 cores and outperformed state-of-the-art works significantly.

关键词

Keywords

references

FRAZER W D , MCKELLAR A C . Samplesort:a sampling approach to minimal storage tree sorting [J ] . Journal of the ACM , 1970 , 17 ( 3 ): 496 - 507 .

HUANG J S , CHOW Y C . Parallel sorting and data partitioning by sampling [C ] // Parallel sorting and data partitioning by sampling . Chicago:IEEE , 1983 .

SHI H , SCHAEFFER J . Parallel sorting by regular sampling [J ] . Journal of Parallel and Distributed Computing , 1992 , 14 ( 4 ): 361 - 372 .

HELMAN D R , JÁJÁ J , BADER D A . A new deterministic parallel sorting algorithm with an experimental evaluation [J ] . ACM Journal of Experimental Algorithmics , 1998 ,3:4.

HOFMANN M , RUNGER G . A partitioning algorithm for parallel sorting on distributed memory systems [C ] // Proceedings of 2011 IEEE International Conference on High Performance Computing and Communications . Piscataway:IEEE Press , 2011 : 402 - 411 .

JEON M , KIM D . Parallelizing merge sort onto distributed memory parallel computers [C ] // International Symposium on High Performance Computing . Berlin:Springer , 2002 : 25 - 34 .

HERRUZO E , RUIZ G , BENAVIDES J I , et al . A new parallel sorting algorithm based on odd-even mergesort [C ] // Proceedings of 15th EUROMICRO International Conference on Parallel,Distributed and Network-Based Processing (PDP’07) . Piscataway:IEEE Press , 2007 : 18 - 22 .

BATCHER K E . Sorting networks and their applications [C ] // Proceedings of the Spring Joint Computer Conference . New York:ACM , 1968 : 307 - 314 .

SOHN A , KODAMA Y . Load balanced parallel radix sort [C ] // Proceedings of the 12th International Conference on Supercomputing . New York:ACM , 1998 : 305 - 312 .

KHATAMI Z , HONG S , LEE J , et al . A load-balanced parallel and distributed sorting algorithm implemented with PGX.D [C ] // Proceedings of 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) . Piscataway:IEEE Press , 2017 : 1317 - 1324 .

SHAMOTO H , SHIRAHATA K , DROZD A , et al . Large-scale distributed sorting for GPU-based heterogeneous supercomputers [C ] // Proceedings of 2014 IEEE International Conference on Big Data (Big Data) . Piscataway:IEEE Press , 2015 : 510 - 518 .

SUNDAR H , MALHOTRA D , BIROS G . HykSort:a new variant of hypercube quicksort on distributed memory architectures [C ] // Proceedings of the 27th international ACM conference on International conference on supercomputing . New York:ACM , 2013 : 293 - 302 .

WAGAR B . Hyperquicksort:a fast sorting algorithm for hypercubes [J ] . Hypercube Multiprocessors , 1987 , 1987 : 292 - 299 .

HARSH V , KALE L , SOLOMONIK E . Histogram sort with sampling [C ] // The 31st ACM Symposium on Parallelism in Algorithms and Architectures . New York:ACM , 2019 : 201 - 212 .

ZHU R , GUO Y W , XUE J H . Adjusting the imbalance ratio by the dimensionality of imbalanced data [J ] . Pattern Recognition Letters , 2020 , 133 : 217 - 223 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于大数据技术的甘肃智慧旅游系统

大数据与计算模型

“东数西算”战略与问题的分析研究

高等教育数字化转型的现状与发展研究

元宇宙与大数据：时空智能中的数据洞察与价值连接