Parallel Sorting & Performance Metrics
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 01: Parallel Sorting & Performance Metrics
This topic establishes the necessary graduate-level foundation by reviewing fundamental parallel computing concepts, including different architectural models (PRAM, Interconnection Networks) and crucial performance metrics like speedup, efficiency, cost-optimality, and Amdahl's Law. It also serves as a comprehensive recap of key parallel sorting algorithms (like Odd-Even Transposition and Bitonic Sort) to ensure all students, regardless of undergraduate background, begin the course with a unified understanding of basic parallel algorithm design principles.
Learning Outcomes
Learning Outcomes
The fundamental models of parallel computation, including PRAM and communication-cost models such as LogP, are understood and related to practical performance behavior.
The metrics of speedup, efficiency, and isoefficiency are derived and applied to characterize the scalability of representative parallel algorithms.
The structural and communication properties of parallel sorting algorithms, particularly Bitonic Sort and Sample Sort, are analyzed to illustrate the interaction between computation and synchronization.
Topic Outline
Topic Outline
Handout: Review of Parallel Sorting & Performance Metrics*
Setting the Clock of Parallelism
Parallel Programming Models and Metrics
PRAM vs. Realistic Models
Speedup, Efficiency, and Scaling
Parallel Sorting Algorithms
Adaptive vs. Fixed Sorting Networks
Shared vs. Distributed Memory Sorting
Cost Analysis and Scalability
Asymptotic Cost and Isoefficiency
Empirical Validation & Optimal Scaling
From Ordered Data to Ordered Computation
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.
Readings
Readings
Fundamental Models and Scalability Metrics
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.The LogP Model (Realistic Communication Costs)
Culler, D. E., Karp, R. M., Patterson, D. A., Sahay, A., & Yelick, K. (1993). LogP: Towards a realistic model of parallel computation. Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '93), 1–12.Bitonic Sort (Comparison Networks)
Batcher, K. E. (1968). Sorting networks and their applications. Proceedings of the AFIPS Spring Joint Computer Conference, 32, 307–314.Sample Sort (Partitioning and Load Balancing)
Shi, Y., & Schaeffer, J. (1992). Parallel sorting by sampling. Journal of Parallel and Distributed Computing, 14(4), 361–372.
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 280: Parallel Processing > Topic 01: Parallel Sorting & Performance Metrics
Page updated
Report abuse