Report: Processing Power
Computer Scientists commonly treat functions that differ asymptotically by only a constant factor as roughly equivalent. This is because as processors get faster, programs often run faster by a constant factor.
For this assignment, you will write a report showing how hardware’s processing power has increased over time. Then, you will estimate how algorithm runtime changes as processing power increases.
Instructions
You may work with a group of up to three students. If you work as a group, you should only submit once on Gradescope.
Choose a type of computing device which has been around for at least ten years, and for which you can find data about its processing power. For example, iPhones, MacBooks, Nintendo consoles, etc. Floating point operations per second (FLOPS) are commonly used to measure processor performance, but other metrics are also useful (e.g., performance on benchmarks).
First, create a table of model release dates and processing power. For full credit, include at least five data points, and link to your sources.
Next, graph the data to show the increase in processing power over time.
Finally, use your data to answer the following questions:
- How many times faster is the latest model than the earliest model?
- Suppose the earliest model requires 10 seconds to complete a task of size 20 using Algorithm A. Assume Algorithm A has a linear growth rate, where lower-order terms can be ignored, that is: \( \text{runtime} = a_1 \cdot n \), where \( n \) is the task size.
- Estimate how much time the latest model would take to complete a task of size 20.
- Estimate how much time the earliest model would take to complete a task of size 40.
- Estimate how much time the latest model would take to complete a task of size 40.
- Suppose the earliest model requires 10 seconds to complete a task of size 20 using Algorithm B. Assume Algorithm B has a quadratic growth rate, where lower-order terms can be ignored, that is: \( \text{runtime} = a_2 \cdot n^2 \), where \( n \) is the task size.
- Estimate how much time the latest model would take to complete a task of size 20.
- Estimate how much time the earliest model would take to complete a task of size 40.
- Estimate how much time the latest model would take to complete a task of size 40.
- Suppose the earliest model requires 10 seconds to complete a task of size 20 using Algorithm C. Assume Algorithm C has an exponential growth rate, where lower-order terms can be ignored, that is: \( \text{runtime} = a_e \cdot 2^n \), where \( n \) is the task size.
- Estimate how much time the latest model would take to complete a task of size 20.
- Estimate how much time the earliest model would take to complete a task of size 40.
- Estimate how much time the latest model would take to complete a task of size 40.
Note: Estimating the runtime of real-world programs is a bit more complicated. For example, program performance is often constrained by factors other than processor speed, such as memory and storage speed.
Example: PlayStation Processing Power
| Model | Release Date | Processing Power (GPU GFLOPS) |
|---|---|---|
| PlayStation 2 | March 2000 | 6.2 |
| PlayStation 3 | November 2006 | 230.4 |
| PlayStation 4 | November 2013 | 1843 |
| PlayStation 4 Pro | November 2016 | 4198 |
| PlayStation 5 | November 2020 | 9200 |
| PlayStation 5 Pro | November 2024 | 16700 |
- How many times faster is the latest model than the earliest model?
Answer: \( 16700/6.2 \approx 2694 \text{ times faster} \) - Suppose the earliest model requires 10 seconds to complete a task of size 20 using Algorithm A. Assume Algorithm A has a linear growth rate, where lower-order terms can be ignored, that is: \( \text{runtime} = a_1 \cdot n \), where \( n \) is the task size.
- Estimate how much time the latest model would take to complete a task of size 20.
Answer: \( 10/2694 \approx 0.00371 \text{ seconds} \) - Estimate how much time the earliest model would take to complete a task of size 40.
Answer: \( a_1 = 0.5 \) for the earliest model, so \( a_1 \cdot 40 = 20 \text{ seconds} \) - Estimate how much time the latest model would take to complete a task of size 40.
Answer: \( a_1 = 0.0001855 \) for the latest model, so \( a_1 \cdot 40 = 0.00742 \text{ seconds} \)
- Estimate how much time the latest model would take to complete a task of size 20.
- Suppose…
- Suppose…
Sources:
Submit
Submit your report as a PDF on Gradescope. If you worked as a group, you should add your group members to a single submission. Ensure your submission includes:
- A table of model release dates and processing power
- A graph showing processing power increasing over time
- Links to your sources
- Answers to the runtime estimate questions
Learning Goals
- Understand common runtime growth rates
- Visualize how processing power has increased over time
- Estimate algorithm runtime as task size increases
- Estimate algorithm runtime as processing power increases