Counting the Cost of Speed:
Why Every Second (and Processor) Matters
Embedded Files
::: Home > Instruction > CMSC 180: Introduction to Parallel Computing > Topic 06: Counting the Cost of Speed
In this topic, we explore how to judge the real performance of a parallel algorithm—not just whether it runs, but whether it runs well. We learn how to measure runtime, cost, and efficiency and how these numbers reveal if our algorithm uses resources wisely. We study the link between work, critical path, and scalability, and see why some algorithms soar with more processors while others stumble. We end with simple case studies that show how design decisions shape performance in practice.
Learning Objectives
Learning Objectives
Compute and interpret parallel runtime, cost, and efficiency.
Explain how work and critical-path length limit achievable speedup.
Analyze algorithm scalability through isoefficiency and cost-optimality.
Guide Questions
Guide Questions
How do we know if a parallel algorithm wastes resources?
What is the critical path, and why can it never disappear?
Why do some algorithms become faster when we make the problem larger?
Topic Outline
Topic Outline
Measuring Performance: What Numbers Really Mean
Parallel Runtime, Cost, and Efficiency
Work and Critical-Path Length: The Ceiling of Speed
Scalability: How Big Can We Grow?
Isoefficiency and the Growth of Problem Size
Cost-Optimal and Non-Optimal Designs
Seeing Design Choices in Action
Matrix Addition and Reduction: The Two Extremes
Decomposition Efficiency: The Shape of Division
Current Lecture Handout
Counting the Cost of Speed: Why Every Second (and Processor) Matters, 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
Balaprakash, P., et al. (2021). Energy-efficient parallel algorithms for exascale computing. IEEE Transactions on Parallel and Distributed Systems, 32(12), 2931–2943. https://doi.org/10.1109/TPDS.2021.3085473
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing (2nd ed.). Addison-Wesley.
Narayanan, D., et al. (2021). Efficient large-scale distributed training of language models. Proceedings of Machine Learning and Systems (MLSys 2021).
Owens, J. D., et al. (2008). GPU computing. Proceedings of the IEEE, 96(5), 879–899. https://doi.org/10.1109/JPROC.2008.917757
Palmer, T. N., et al. (2022). High-resolution climate modeling in the exascale era. Nature Climate Change, 12(3), 198–207. https://doi.org/10.1038/s41558-022-01290-2
Quinn, M. J. (2017). Parallel programming in C with MPI and OpenMP. Cambridge University Press.
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 06: Counting the Cost of Speed
Page updated
Report abuse