并行双调排序算法的有效实现及性能分析  

AN EFFICIENT IMPLEMENTATION AND PERFORMANCE ANALYSIS OF PARALLEL BITONIC SORTING

作　　者：顾乃杰[1] 王旭[1] 陈国良[1] 蒋凡[1] 

机构地区：[1]中国科学技术大学计算机科学技术系,合肥230027

出　　处：《计算机研究与发展》2002年第10期1343-1348,共6页Journal of Computer Research and Development

摘　　要：排序是计算机中最常见的操作之一 .双调排序是一个非常著名的排序算法 ,也是最早的并行排序算法 ,双调排序对排序算法的研究具有非常深远的影响 .基于双调排序算法的基本思想 ,介绍了双调排序在分布存储的并行计算机环境下的一种有效实现方式 ,采用局部多对多通信替换全局通信 ,很好地解决了双调排序中的通信问题 .算法的计算复杂度为 Θ( n/p( logn+ log2 p) ) ,其中 n为待排序的关键字个数 ,p为处理器数 .算法在二维网孔结构上通信时间复杂度达到了 O( 2 .12 13 2 p· n/p ) ,其量级达到了理论上的下限 .分析结果表明 。Sorting is one of the most common operations performed by a computer. The very famous bitonic sorting is one of the earliest parallel sorting algorithms. Bitonic sorting has a very important impact on the research of parallel sorting algorithms. Many parallel sorting algorithms are based on bitonic sorting. Following the basic strategy of bitonic sorting, here given is an efficient implementation scheme of bitonic sorting on a distributed memory parallel machine. To solve the communication problem in bitonic sorting, local all-to-all communication patterns are used instead of total exchanges. The computational complexity of the algorithm isΘ(n/p(logn+log2p)), wheren is the number of keys to be sorted, andp is the number of processors. The communication complexity of the algorithm on a 2-D mesh isO(2 12132p·n/p). The order of this communication complexity reaches the theoretical lower bound.The analytical result shows that the communication performance and the scalability of bitonic sorting are excellent.

关 键 词：并行双调排序算法 性能分析 并行算法 计算复杂度 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]