Bitonic Selection Algorithms on SIMD Machine

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²n）and O(n^1/2).