Abstract:
In this paper, a parallel-optimal-sequential (POS) approach is proposed, which transforms a computation into a series subcomputation. Each subcomputation can be computed in a parallel-optimal-sequential (POS) fashion,i.e. , there arep processors, and on each of them a subcomputation is computed on an optimal sequential algorithm simultaneously. Based on this approach, a parallel-optimal-sequential vector merging algorithm (POSVM) is designed, which merges 2 sorted sequences (or sorts a Bitonic sequence) of totalN number inO(N/p) time, and a POS vector sorting algorithm (POSVS) sortsN arbitrary numbers inO((NlogN)/p) time on a practical general purpose SIMD machine. These are first vector optimal algorithms (speedup=O(p)), which satisfy two conditions as follows: ① which can be implemented in a practical SIMD machine, such as vector pipeline machine with interleaved memory modules or multiprocessors system with a multistage multi-dimensional interconnect network, in a wide range ofp, 1≤p≤N 1-ε, whereε is an arbitrary small positive number, and ②, which unify the three very different kinds of merging and sorting algorithms: Batcher’s Bitonic algorithm (the fast algorithm but not optimal), the optimal parallel algorithm, and the optimal sequential algorithm. The POS approach is a general approach which can also be used in other problems.