CPU execution time CPI and speedup
Learning objectives and scope
Compute CPU execution time from instruction count, cycles per instruction and clock frequency; combine an instruction mix correctly; compare two designs; and bound an optimization using Amdahl's law. Prerequisites: fractions, percentages, unit conversions and the distinction between an instruction and a clock cycle. This is performance arithmetic, not a complete treatment of benchmarking, pipelines, multicore scaling or power.
Unless explicitly changed, comparisons run the same fixed task to the same result. Counts refer to dynamically executed instructions, not the number of lines in a listing. The given average CPI includes the costs stated in the question. We do not silently add or remove stall cycles. All examples are original teaching workloads, not measurements of a commercial processor.
1. Name the quantity before calculating
CPU execution time is time spent executing the task on the CPU in the stated model. Elapsed or wall-clock time can also include waiting for I/O, scheduling and other delays. Improving CPU time alone need not improve every part of elapsed time.
Latency asks how long one task takes. Throughput asks how many tasks finish per unit time. They are related but not interchangeable. Completing more tasks simultaneously can improve throughput without making one task finish earlier.
Clock frequency f is cycles per second. Clock period τ is seconds per cycle, so τ=1/f. At 2 GHz, f=2×10^9 cycles/s and τ=0.5 ns. A clock cycle is not an instruction: an instruction may require several cycles, and an overlapping implementation may complete more than one instruction per cycle on average.
2. Derive the CPU-time equation
Let I be dynamic instruction count and CPI_avg be average cycles per instruction. Then total cycles=I×CPI_avg, and
T_CPU = I × CPI_avg × τ = I × CPI_avg / f.
Units cancel: instructions × cycles/instruction × seconds/cycle = seconds. Use this cancellation to catch a GHz-to-nanosecond mistake. The equation is bookkeeping, not a promise that changing one factor leaves the others unchanged.
Worked example: a program executes 120 million instructions at average CPI=1.5 on a 3 GHz clock. It needs 180 million cycles. T=180×10^6/(3×10^9)=0.060 s=60 ms. Dividing instruction count by frequency alone would incorrectly assume CPI=1.
3. Weighted CPI from an instruction mix
Suppose class i executes n_i instructions, each costing c_i cycles in the model. Total cycles=Σ(n_i c_i), total instructions=Σn_i, and CPI_avg=Σ(n_i c_i)/Σn_i. If p_i=n_i/I is a fraction of instructions, CPI_avg=Σ(p_i c_i), with Σp_i=1.
Worked example: 50% arithmetic instructions at CPI 1, 30% loads at CPI 3 and 20% branches at CPI 2 give CPI_avg=0.50×1+0.30×3+0.20×2=1.8. For 100 million instructions at 2 GHz, time is 0.09 s. The unweighted mean (1+3+2)/3=2 wrongly assumes equal class counts.
Instruction fractions are not execution-time fractions. Loads account for 0.30×3/1.8=1/2 of this program's CPU time, even though they are only 30% of its instructions. This distinction matters when applying an optimization to one class.
4. Compare times rather than clock labels
Define speedup of new over old as S=T_old/T_new. S>1 is faster, S=1 is unchanged, and S<1 is slower. The fractional time reduction is (T_old−T_new)/T_old=1−1/S. A 2× speedup is a 50% time reduction, not a 200% reduction.
Worked comparison: both machines execute 200 million instructions. A has CPI=1.2 at 2 GHz, so T_A=0.12 s. B has CPI=1.8 at 3 GHz, so T_B=0.12 s. B has a higher clock rate but no speedup for this workload.
An optimization might change instruction count too. If I_new=0.8 I_old and CPI_new=1.25 CPI_old at the same clock frequency, their product stays 1.0 times the old product. Execution time is unchanged. Lower CPI alone is also not a sufficient comparison when counts or clocks differ.
5. Amdahl's law from a time budget
Let a fraction p of the original execution time be improved by a factor s, while the remaining fraction 1−p stays unchanged. Assume fixed work, no extra overhead and no other changes. If original time is T, new time is (1−p)T+pT/s. Therefore
S = 1 / [(1−p) + p/s].
Use p as a fraction of original time, not the new time and not automatically an instruction fraction. For s≥1 and 0≤p<1, even an infinitely fast optimized portion cannot exceed S_max=1/(1−p). If p=0 there is no gain; if p=1, S=s and there is no finite unchanged-part bound as s grows.
Worked example: original time is 100 ms. A component consumes 60 ms and becomes three times as fast. It now takes 20 ms; the unchanged component still takes 40 ms. New time is 60 ms, speedup is 100/60=5/3≈1.667, and time reduction is 40%. The infinite-improvement upper bound is 100/40=2.5×.
Return to the instruction mix: loads occupy half the original time. Reducing their class CPI from 3 to 1.5 gives new average CPI=0.5+0.45+0.4=1.35. Speedup is 1.8/1.35=4/3. Amdahl with p=0.5 and s=2 gives 1/(0.5+0.25)=4/3 as an independent check.
Key points and common mistakes
- Start with the task, count, CPI, frequency and units. Compare execution times for the same task.
- Weight CPI by instruction counts, not by an unweighted average or time percentages.
- Use 1 GHz=10^9 cycles/s, 1 ns=10^−9 s and 1 ms=10^−3 s.
- Distinguish speedup, percentage performance increase and percentage time reduction.
- Amdahl's p is the original time fraction. An unoptimized component limits total improvement.
- A simplified model needs its assumptions. It does not establish real-world performance without measurements.
Original practice: six single-correct MCQs
These are original questions, not previous-year questions. Choose exactly one option.
P01. A task executes 150 million instructions at average CPI 1.6 and clock frequency 2.4 GHz. What is its CPU execution time?
A. 62.5 ms B. 100 ms C. 160 ms D. 10 ms
Answer: B
A: This divides the instruction count by frequency but omits CPI.
B: Cycles=150×10^6×1.6=240×10^6; time=0.1 s=100 ms.
C: This does not divide the 240 million cycles by the stated 2.4 billion cycles/s correctly.
D: The correct time is 0.1 s, not 0.01 s; this has a factor-of-ten unit error.
P02. The instruction fractions are 40%, 40% and 20%, with class CPIs 1, 2 and 4, respectively. What is the average CPI?
A. 7/3 B. 1.4 C. 2.0 D. 2.8
Answer: C
A: 7/3 is the unweighted mean, which incorrectly assumes equal class counts.
B: This fails to include the full weighted contribution of the CPI-4 class.
C: 0.4×1+0.4×2+0.2×4=2.0.
D: This would fit different weights, not the stated 40%, 40%, 20% instruction mix.
P03. A and B execute the same number of instructions. A has CPI 1.5 at 3 GHz; B has CPI 1.2 at 2 GHz. Which comparison is correct?
A. A is 1.2× as fast as B B. B is 1.2× as fast as A C. Both take equal time D. A is 1.5× as fast as B
Answer: A
A: Time per instruction is 0.5 ns for A and 0.6 ns for B; T_B/T_A=1.2.
B: This reverses the execution-time ratio; A finishes sooner.
C: The CPI/f ratios are 0.5 and 0.6 ns, not equal.
D: The clock ratio alone is 1.5, but B has lower CPI, so it must also be included.
P04. Exactly 75% of the original execution time is improved by a factor of 3. The rest is unchanged and no overhead is added. What is the overall speedup?
A. 3× B. 4× C. 1.5× D. 2×
Answer: D
A: Only 75% of the work time is accelerated; the entire program is not three times as fast.
B: Four is the infinite-improvement bound 1/0.25, not the result for a finite factor 3.
C: New time is 0.25+0.75/3=0.5 of old, giving 2 rather than 1.5.
D: S=1/(0.25+0.75/3)=1/0.5=2.
P05. An optimization reduces a fixed task from 80 ms to 60 ms. Which speedup and time reduction are correct?
A. 0.75× and 25% B. 4/3× and 25% C. 4/3× and 33⅓% D. 1.25× and 20%
Answer: B
A: 0.75 is new time divided by old; speedup uses the inverse ratio.
B: Speedup=80/60=4/3; time reduction=(80−60)/80=25%.
C: 33⅓% is the increase in inverse-time performance, not the time reduction.
D: Both ratios use the wrong values; the removed 20 ms is one quarter of 80 ms.
P06. 25% of instructions have CPI 4 and the rest have CPI 1. Only the first class is improved to CPI 2; count and clock remain unchanged. What is the speedup?
A. 8/7 B. 2 C. 7/5 D. 5/7
Answer: C
A: 8/7 results from incorrectly using the 25% instruction fraction as Amdahl’s original time fraction.
B: Only one class becomes twice as fast; the remaining time still contributes.
C: Old CPI=0.25×4+0.75×1=1.75; new CPI=0.25×2+0.75=1.25; speedup=1.75/1.25=7/5.
D: This is new time/old time, the inverse of speedup.
Sources and scope
This is an introductory Computer Organization lesson, not full-topic or full-syllabus completion. The official syllabus establishes alignment; technical references check the underlying definitions. Teaching models, worked examples and practice are original. Verified 14 October 2026.
Sign in to keep your progress. Sign in