| 并行双调排序算法的有效实现及性能分析 |
| |
| 引用本文： | 顾乃杰,王旭,陈国良,蒋凡. 并行双调排序算法的有效实现及性能分析[J]. 计算机研究与发展, 2002, 39(10): 1343-1348 |
| |
| 作者姓名： | 顾乃杰 王旭 陈国良 蒋凡 |
| |
| 作者单位： | 中国科学技术大学计算机科学技术系,合肥,230027 |
| |
| 摘 要： | 排序是计算机中最常见的操作之一，双调排序是一个非常著名的排离算法，也是最早的并行排序算法，又调排离对排序算法的研究具有非常深远的影响，基于双调排序算法的基本思想，介绍了双调排序在分布存储的并行计算机环境下的一种有效实现方式，采用局部多对多通信替换全局通信，很好地解决了双调排序中的通信问题，算法的计算复杂度为⊙n/p(logn log^2p)，其中n为待排序的关键字个数,p为处理器数，算法在二维网孔结构上通信时间复杂度达到了O（2.12132√p.n/p）其量级达到了理论上的下限，分析结果表明，双调排序算法也具有很好的通信性能和可扩展性。
|
| 关 键 词： | 并行双调排序算法 性能分析 并行算法 计算复杂度 计算机 |
AN EFFICIENT IMPLEMENTATION AND PERFORMANCE ANALYSIS OF PARALLEL BITONIC SORTING |
| |
| GU Nai-Jie,WANG Xu,CHEN Guo-Liang,and JIANG Fan. AN EFFICIENT IMPLEMENTATION AND PERFORMANCE ANALYSIS OF PARALLEL BITONIC SORTING[J]. Journal of Computer Research and Development, 2002, 39(10): 1343-1348 |
| |
| Authors: | GU Nai-Jie WANG Xu CHEN Guo-Liang and JIANG Fan |
| |
| Abstract: | |
| |
| Keywords: | parallel sorting sorting all-to-all communication |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
