Parallel Sorting with Serial Momories

Robert Michael Owens, Joseph F. JáJá

Abstract

This correspondence examines the problem of sorting on a network of processors, where each processor consists of a single storage register and a small control unit capable of comparing two numbers and has a single serial memory attached to it. We show how to sort optimally on one- or two-dimensional arrays of p processors in time θ(n + (n2/p2)) and θ((n/√p) + (n2/p2)), respectively. Because of the implementational advantages of serial memories, we feel that our architecture will be attractive for several applications.
BibTeX
@article{owens1985parallel,
  author = {Robert Michael Owens and Joseph F. JáJá},
  title = {{Parallel Sorting with Serial Momories}},
  journal = {IEEE Transactions on Computers},
  year = {1985},
  doi = {10.1109/tc.1985.5009391},
}

Loading related content...

Figure