Abstract:
The parallel solution of the (m,n) selection problem on multiprocessorsystems is a significant topic for reseach. The SIMD machine being widely used now isa popular parallel-processing system. This paper describes the bitonic selection algorithmsto solve the (m,n) selection problem on three typical SIMD machine models includingcube connecting computer, shuffle-exchange connecting computer and mesh connectingcomputer. The number of data compare-exchange in each algorithm is O(logn logm); thenumber of data transfer in three algorithms are respectively O(logn logm), O(log
2n)and O(n
1/2).