EREW PRAM模型上指数级分割待处理数据集的并行多选算法  

A Parallel Multi-Selection Algorithm with Exponential Partition on EREW PRAM Model

作　　者：崔泽鹏[1] 李伟生[1] 

机构地区：[1]北方交通大学计算机与信息技术学院,北京100044

出　　处：《北方交通大学学报》2003年第2期46-49,共4页Journal of Northern Jiaotong University

摘　　要：提出EREWPRAM模型上指数级分割待处理数据集的并行多选算法,通过分割待处理数据集合的方式来缩小待处理问题规模,待处理元素的规模在指数级上快速达到收敛状态,算法优于线性分割的并行多选算法,算法不会由于待处理数据集合的不均匀性而导致性能的恶化,在时间复杂度上是最优的.This paper presents a new parallel multi_selection algorithm on EREW PRAM model employing a method of exponential partition that divides sets of the elements into smaller ones to reduce the size of the problem to be resolved. The size of the problem approaches to convergence rapidly at exponential rate. The algorithm is more effective than other linear algorithms. The efficiency cannot be undermined in the case that the sets of elements are not uniform, and the time complexity of the algorithm is optimal.

关 键 词：算法分析 并行 多选算法 均匀 分割 

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