2.3 Two Laws that Provide Insight: Ahmdahl’s Law and Little’s Law
COS2621 - Computer Organisation · 2. Performance Issues
Performance Issues
Two Laws that Provide Insight: Ahmdahl’s Law and Little’s Law
Ahmdahl’s Law is a formula that helps to find the maximum improvement of a system when only part of that system is improved. This law is particularly useful in parallel computing, where multiple processors are used to execute tasks simultaneously. The law states:
S = 1 / (F + (1 - F) / P)
Where:
- S = speedup of the task
- F = fraction of the task that is sequential (cannot be parallelized)
- P = number of processors
For example, if 30% of a task is sequential (F = 0.3) and the remaining 70% can be parallelized, using 5 processors (P = 5), the speedup can be calculated as follows:
S = 1 / (0.3 + (1 - 0.3) / 5) = 1 / (0.3 + 0.7 / 5) = 1 / (0.3 + 0.14) = 1 / 0.44 ≈ 2.27
This means the maximum speedup achievable with 5 processors is approximately 2.27 times faster than using a single processor. Understanding Ahmdahl’s Law is crucial, as it shows the diminishing returns of adding more processors when a part of the task remains sequential.
Watch out: Students often forget to convert fractions into decimals when applying Ahmdahl’s Law, leading to incorrect speedup calculations.
Little’s Law is another important theorem used in queuing theory. It relates the average number of items in a queuing system (L) to the average arrival rate (λ) and the average time an item spends in the system (W). The formula is:
L = λ × W
Where:
- L = average number of items in the system
- λ = average arrival rate (items per unit time)
- W = average time an item spends in the system
For example, if 12 customers arrive at a bank every hour (λ = 12) and the average time a customer spends in the bank is 10 minutes (W = 1/6 hours), then:
L = 12 × (1/6) = 2
This means, on average, there are 2 customers in the bank at any given time. Little’s Law helps in understanding how systems manage queues and can be applied in various scenarios, such as network traffic or customer service.
Watch out: Students sometimes confuse the units of time when calculating L, λ, and W, resulting in incorrect interpretations of the law.
Both laws offer valuable insights into performance and system efficiency. While Ahmdahl’s Law focuses on the limits of parallel processing, Little’s Law aids in understanding queuing dynamics. By grasping these concepts, you can better design and optimise computer systems.
Check your understanding
- What is the formula for Ahmdahl’s Law?
- How does Little’s Law relate to queuing systems?
- In Ahmdahl’s Law, what happens to speedup as the fraction of sequential work increases?
- Provide an example of how Little’s Law can be applied in a real-world scenario.
Test yourself
4 quick questions on this lesson. Pick an answer to see if you're right.
1. As the fraction of sequential work (F) increases in Ahmdahl's Law, what happens to the maximum speedup (S)?
2. What is the formula for calculating speedup in Ahmdahl's Law?
3. In Little's Law, if the average arrival rate (λ) is 5 items per hour and the average time (W) an item spends in the system is 2 hours, what is the average number of items (L) in the system?
4. What does Ahmdahl's Law primarily address?