Sorting in Sync:
How We Teach Computers to Agree on Order
Embedded Files
::: Home > Instruction > CMSC 180: Introduction to Parallel Computing > Topic 11: Sorting in Sync
Sorting is one of the most familiar problems in computer science—but in parallel computing, it becomes a battlefield of communication and coordination. This week, we explore how distributed processors sort shared data efficiently. We learn how data partitioning, communication cost, and load balancing make sorting both a classic benchmark and a deep lesson in performance design.
Learning Objectives
Learning Objectives
Explain the challenges of sorting when data is distributed across processors.
Compare the logic and performance of key-exchange and merge-based sorting methods.
Analyze how data partitioning, communication, and load balance affect scalability.
Guide Questions
Guide Questions
Why is sorting often used as a benchmark for parallel systems?
How does data distribution influence communication cost?
What trade-offs exist between computation and communication during sorting?
Topic Outline
Topic Outline
Why Sorting Is Hard in Parallel Systems
The Challenge of Global Order
How We Measure a Good Sort
Sorting Models and Approaches
Partitioning and Redistribution
Key-Exchange vs. Merge-Based Methods
Classic Examples
Parallel Odd-Even Transposition Sort
Parallel Quicksort
Current Lecture Handout
Sorting in Sync: How We Teach Computers to Agree on Order, rev 2023*
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
The semester at a glance:
Readings
Readings
Batcher, K. E. (1968). Sorting networks and their applications. Proceedings of the AFIPS Spring Joint Computer Conference, 32, 307–314. https://doi.org/10.1145/1468075.1468121
Blelloch, G. E., Fineman, J. T., Gibbons, P. B., & Shun, J. (2012). Internally deterministic parallel algorithms can be fast. Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 181–192. https://doi.org/10.1145/2312005.2312037
Hammond, S. D., et al. (2020). Scaling sorting and sampling on exascale architectures. Concurrency and Computation: Practice and Experience, 32(12), e5662. https://doi.org/10.1002/cpe.5662
Pacheco, P. S. (2011). An introduction to parallel programming. Morgan Kaufmann.
Shi, H., & Schaeffer, J. (1992). Parallel sorting by regular sampling. Journal of Parallel and Distributed Computing, 14(4), 361–372. https://doi.org/10.1016/0743-7315(92)90047-M
Zaharia, M., Chowdhury, M., Franklin, M. J., Shenker, S., & Stoica, I. (2010). Spark: Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, 1–7.
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 180: Introduction to Parallel Computing > Topic 11: Sorting in Sync
Page updated
Report abuse