Adding more processors cannot make every computation arbitrarily fast. Amdahl’s Law estimates the maximum speedup available from the work that can run in parallel and the work that must remain sequential. section 2.11 section 2.14
Apply the idea by separating a computation into:
- Sequential work, such as dividing inputs or collecting results, which limits the overall speedup. section 2.11
- Independent parallel work, which can be divided among multiple processing resources. section 2.11 section 2.14
- Practical overheads and redesign needs, including decomposition, algorithm changes, and synchronization points. section 2.14
Searching index cards
Searching a mixed pile takes 5 seconds alone: 1 second to divide the cards, 3 seconds to search, and 1 second to collect matching cards. Two friends reduce the search phase to 1 second, so the total becomes 3 seconds—a 40% speedup, not an unlimited one. section 2.11
The law is a decision aid: estimate the benefit before parallelizing, especially when a large sequential fraction remains. Parallelism also requires multiple processing resources and independent tasks. section 2.14
