Parallel Algorithms (cont.)

• Parallel Sorting (cont.)

  • Major Concern
    • Deadlock
      • Can be avoided by:
        • Using range-partitioning
        • Having a sufficient size data exchange buffer
        • Using a modified sort algorithm

• Parallel Aggregation/Duplicate Removal

  • Uses local and global steps

Previous slide

Next slide

Back to first slide

View graphic version

Modified sort: sort locally only by position in final partition and then exchange data guaranteeing a balanced data flow.

Local/global steps: local step removes duplicates. Then partitions data to find duplicates in different sites (global step).

Note: the functions may differ for aggregation.