A taxonomy of parallel sorting

Download
Author
Bitton, Dina
DeWitt, David J.
Hsiao, David K.
Menon, Jaishankar
Date
1984-04Metadata
Show full item recordAbstract
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.
Description
TR 84-601
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Top-down synthesis of simple divide and conquer algorithms
Smith, Douglas R. (Monterey, California. Naval Postgraduate School, 1982-11-12); NPS-52-82-011A new method is presented for the deductive synthesis of computer programs. The method takes as given a formal specification of a user's problem. The specification is allowed to be incomplete in that some or all of the ... -
Recursive algorithms for distributed forests of octrees
Isaac, Tobin; Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar (2014-11-18);The forest-of-octrees approach to parallel adaptive mesh re nement and coarsening (AMR) has recently been demonstrated in the context of a number of large-scale PDE-based applications. E cient reference software has been ... -
CHASING THE UNKNOWN: A PREDICTIVE MODEL TO DEMYSTIFY BGP COMMUNITY SEMANTICS
Werner, Joshua (Monterey, CA; Naval Postgraduate School, 2020-09);The Border Gateway Protocol (BGP) specifies an optional communities attribute for traffic engineering, route manipulation, remotely-triggered blackholing, and other services. However, communities have neither unifying ...