Parallel Algorithms (cont.)

• Parallel Sorting

  • Want to parallelize sorting to reduce cost
  • Classified by:
    • Number of parallel inputs
    • Number of parallel outputs
  • Algorithms consist of a local sort and a data exchange step

Previous slide

Next slide

Back to first slide

View graphic version

Algorithms: the order of the steps determines problems. If data step is 1st, have to worry about load balance in the sort step. If sort 1st, have to worry about merging in the data step.