Search

排序算法是计算机科学领域的一个基础算法，是大量应用的算法核心。在大数据时代，随着数据量的极速增长，并行排序算法受到广泛关注。现有的并行排序算法普遍存在通信开销过大、负载不均衡等问题，导致算法难以大规模扩展。针对以上问题，提出一种大规模可扩展的正则采样并行排序（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倍。

Copyright of Acta Scientiarum Naturalium Universitatis Sunyatseni / Zhongshan Daxue Xuebao is the property of Sun-Yat-Sen University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Big Data Research (2096-0271) is the property of Beijing Xintong Media Co., Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Chinese Mental Health Journal / Zhongguo Xinli Weisheng Zazhi is the property of Chinese Mental Health Journal and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Computer Engineering & Science / Jisuanji Gongcheng yu Kexue is the property of Computer Engineering & Science and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Computer Engineering & Science / Jisuanji Gongcheng yu Kexue is the property of Computer Engineering & Science and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Journal of National University of Defense Technology / Guofang Keji Daxue Xuebao is the property of NUDT Press and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Journal of National University of Defense Technology / Guofang Keji Daxue Xuebao is the property of NUDT Press and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Computer Engineering & Science / Jisuanji Gongcheng yu Kexue is the property of Computer Engineering & Science and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)