A taxonomy of parallel sorting
DeWitt, David J.
Hsiao, David K.
MetadataShow full item record
In this paper, we propose a taxonomy of parallel sorting that includes a broad range of array and file sorting algorithms. We analyze the evolution of research on parallel sorting, from the earliest sorting networks to the shared memory algorithms and the VLSI sorters. In the context of sorting networks, we describe two fundamental parallel merging schemes - the odd-even and the bitonic merge. Sorting algorithms have been derived from these merging algorithms for parallel computers where processors communicate through interconnection networks such as the perfect shuffle, the mesh and a number of other sparse networks. After describing the network sorting algorithms, we show that, with a shared memory model of parallel computation, faster algorithms have been derived from parallel enumeration sorting schemes, where keys are first ranked and then rearranged according to their rank.
Showing items related by title, author, creator and subject.
Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers Ekin, Cengiz (Monterey, California. Naval Postgraduate School, 1992-12);This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm ...
McCoy, Earl E.; Carey, Bernard J. (Monterey, California. Naval Postgraduate School, 1980-05); NPS-52-80-007This paper reviews and analyzes the desirable properties of a computer network taxonomy from the point of view of its usefulness in a design procedure. A key factor that must be considered is that the design environment ...
Hartman, Jonathan Edward (Monterey, California. Naval Postgraduate School, 1991-12);As computing machines advance, new fields are explored and old ones are expanded. This thesis considers parallel solutions to several well-known problems from numerical linear algebra, including Gauss Factorization and the ...