Abstract:
The so-called(m,n)selection problem is the problem of selecting the msmallest(or largest)numbers from n numbers(n≥m).Parallel solution of this problem has been implemented successfully on the networks,but it is seldom studied on the multiprocessor systems.This paper,first,based on Batcher's principle of bitonic merging,proposes the bitonic selection network in which the number of comparators is O(nlog
2m)and the delay time is O(logn logm);then,we find the varing rule of the pivots in all successive ranks of the network throughobserving the data transfer property in the network.According to this rule,the parallel selection algorithm executed in time O(logn logm)on n processors is given.