Multisets排序的最优并行算法  

An Optimal Parallel Sorting Algorithm for Multisets

作　　者：钟诚[1] 陈国良[2] 

机构地区：[1]中国科学技术大学计算机科学与技术系,合肥230027 [2]国家高性能计算中心,合肥230027

出　　处：《计算机研究与发展》2003年第2期336-341,共6页Journal of Computer Research and Development

基　　金：国家重点基础研究发展规划基金 (G19980 3 0 40 3 ) ;国家"十五""八六三"高技术研究发展计划基金 (2 0 0 1AA1110 41)

摘　　要：排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 <k <n 基于“中值的中值”思想和“筛选”原理 ,通过在递归过程中不断地“筛选”掉某些具有相同关键字值的数据 ,以及自适应地动态分配处理器以平衡计算负载的方法 ,设计一种确定的稳定的Multisets排序并行算法 在具有 p =n1-ε(0 <ε<1)个处理器的共享存储并行机器上 ,对于CREWPRAM模型 ,算法的时间复杂度为O((n/ p +pε)logk) ,获得最优执行代价O(nlogk) ;对于EREWPRAM模型 ,算法所需时间为O((n/ p+pε+logp)logk) ,当 plogp≤n时 ,其执行代价也是最优的Sorting is a very interesting problem that has the important theoretical significance and widely applied value Sorting for multisets is to sort n numbers (records) that contain only k distinct key values, where 0<k<n In this paper, based on the idea of 'median of medians' and principle of 'filtering', a deterministic and stable parallel sorting algorithm for multisets is presented When the algorithm is executed recursively, some data with the same key values are filtered logically and the processors are assigned to the subtasks adaptively and dynamically in order to balance their computing loads For the shared memory parallel systems with p=n 1-ε processors, where 0< ε <1, the algorithm requires O((n/p+p ε) log k ) time and gets optimal O(n log k ) cost on CREW PRAM; its time complexity is O((n/p+p ε +log p )log k ), and its corresponding cost is also optimal when plogp≤n on EREW PRAM The main contribution of the paper is to present a new parallel sorting approach by applying selection technique

关 键 词：Multisets排序 最优并行算法 PRAM 计算机科学 

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