摘要
对于共享存储的多处理器系统,给出一种易于实现的从任意给定的n个数据中既选取前m个最小者又选取前m个最大者的并行算法(m<n),算法所用的处理器数为[n/(2m)]+1,时间复杂度为O(log_2(n/m)·log_2m·m)。
A parallel selection algorithm is presented to solve both the first m smallest elements and the first m largest elements from n given numbers, where m<n. It is easily implemented on Shared-memory multiprocessor systems using In/ (2m)]+1 processors, and its time complexity is O(log_2n/m·log_2m·m).
出处
《广西大学学报（自然科学版）》
CAS
CSCD
1993年第1期14-18,共5页
Journal of Guangxi University（Natural Science Edition）
关键词
共享存储
多处理器系统
并行算法
partition
selection
shared-memory
multiprocessor systems
parallel algorithms
