A scalable parallel sorting algorithm by regular sampling for big data

Ying WANG; Zhiguang CHEN; Yutong LU

doi:10.11959/j.issn.2096-0271.2024021

您当前的位置：

首页 >

文章列表页 >

A scalable parallel sorting algorithm by regular sampling for big data

STUDY | 更新时间：2024-08-07

- A scalable parallel sorting algorithm by regular sampling for big data
- Big data research Vol. 10, Issue 4, Pages: 89-105(2024)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2024021
  CLC： TP399
- Online First：2024-07，
  
  Published：15 July 2024
- 稿件说明：
移动端阅览
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：

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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Gansu smart tourism system based on big data

Big data and computing models

Analysis and research on the strategy and problems of “Channel Computing Resources from the East to the West”

Digital transformation in higher education:a systematic review

Metaverse and big data: data insight and value connection in spatio-temporal intelligence

Related Author

Liang GUO

Yi YANG

Bingfeng QIN

Jianwen CAO

Min LI

Wei YUAN

Caihong LI

Juntao WANG

Related Institution

School of Information Science and Engineering, Lanzhou University

Key Laboratory of Tourism Information Fusion Processing and Data Ownership Protection, Ministry of Culture and Tourism, Lanzhou University

Technology Information Department, Gansu Provincial Department of Culture and Tourism

School of Computer and Artificial Intelligence, Lanzhou Polytechnical College

Key Laboratory of Artificial Intelligence and Computing Power Technology

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273110 Visits Today：16

⁰