ARM architecture intro — used in embedded - aerospace: Exercises

Before we start, we build the one formula every exercise reuses — but this time we derive it, not just quote it.

Intuition Why the first instruction costs

$k$ cycles and each later one costs only 1 Picture the pipeline as a line of $k$ workstations, and $τ$ (tau) is how long a workstation holds one instruction — one clock cycle. A single instruction must visit all $k$ stations in order, so the very first instruction to enter an empty pipe only finishes after it has passed through all $k$ of them: that is $k$ cycles of "fill" time. But here is the trick: while instruction 1 moves from station 1 to station 2, instruction 2 walks into station 1 right behind it. So one cycle after the first finishes, the second finishes; one cycle after that, the third — because at every tick one instruction pops out the end of the line. That "one out per tick" is called the initiation rate, and in an ideal (hazard-free) pipe it equals exactly 1 instruction per cycle. So: $k$ cycles to get the first one out, then $(n - 1)$ more cycles for the remaining $(n - 1)$ instructions, one per cycle. Total $= k + (n - 1)$ cycles.

Intuition This ideal ignores three real "hazards"

The clean formula above assumes nothing ever stalls. Real pipelines can stall for three reasons, all of which we will touch in the exercises:

Control hazard — a branch we guessed wrong, forcing a flush (Ex 3.3, 4.1).
Data hazard — an instruction needs a result the previous one hasn't finished producing yet. Hardware usually solves most of these with forwarding (piping a result straight from one stage's output to another's input), but a LDR followed immediately by a use of that value still costs a 1-cycle load-use stall because the loaded data isn't ready in time (Ex 3.4).
Structural hazard — two instructions want the same hardware unit in the same cycle (e.g. one memory port). ARM's separate load/store design and split caches largely dodge this. See Instruction Pipelining and Memory Hierarchy and Cache.

Level 1 — Recognition

Goal: can you identify the correct ARM concept when you see it?

Exercise 1.1

Which of these is legal ARM and which is illegal, and why?

(a) ADD R0, [R1], [R2]
(b) LDR R0, [R1]
(c) ADD R0, R1, R2

Recall Solution 1.1

What we are testing: the load/store rule — the ALU touches registers only.

(a) ILLEGAL. ADD is an arithmetic (ALU) instruction, so both operands must be registers or immediates. [R1] and [R2] are memory operands. ARM forbids arithmetic straight from memory.
(b) LEGAL. LDR (LoaD Register) is exactly the instruction whose job is to bring a memory value into a register. [R1] means "the value at the address stored in R1".
(c) LEGAL. All three operands are registers — that is what the ALU wants.

Answer: only (a) is illegal. See RISC vs CISC for why CISC allows (a) but RISC deliberately does not.

Exercise 1.2

Match each register to its special role: $R_{13}$ , $R_{14}$ , $R_{15}$ .

Recall Solution 1.2

$R_{13} =$ SP (Stack Pointer) — points at the top of the stack.
$R_{14} =$ LR (Link Register) — holds the return address when a subroutine is called.
$R_{15} =$ PC (Program Counter) — holds the address of the instruction being fetched.

See Registers and Register File. The other 13 registers ( $R_{0}$ – $R_{12}$ ) are general-purpose scratch space.

Level 2 — Application

Goal: can you apply the rules to produce or trace code?

Exercise 2.1

Translate d = x - y; into ARM, where the address of x is in R1, the address of y is in R2, and the result d must be written to the address in R3.

Recall Solution 2.1

Follow the load → compute → store shape forced by load/store architecture:

LDR R4, [R1]     ; R4 = x  (bring x from memory to a register)
LDR R5, [R2]     ; R5 = y
SUB R6, R4, R5   ; R6 = R4 - R5 = x - y  (ALU on registers only)
STR R6, [R3]     ; write R6 back to memory at address in R3

4 instructions. Two loads, one ALU op, one store — the canonical RISC pattern.

Exercise 2.2

A MOV R0, #7 puts the immediate value 7 into R0. Trace the register values after:

MOV R0, #7
MOV R1, #3
SUB R2, R0, R1
CMP R2, #4

What are R0, R1, R2 and the Z flag afterward?

Recall Solution 2.2

After MOV R0, #7: $R 0 = 7$ .
After MOV R1, #3: $R 1 = 3$ .
After SUB R2, R0, R1: $R 2 = 7 - 3 = 4$ .
CMP R2, #4 computes $R 2 - 4 = 4 - 4 = 0$ only to set flags (it does not store the result). Result is 0, so the Z (Zero) flag = 1.

Final: $R 0 = 7, R 1 = 3, R 2 = 4, Z = 1$ . CMP is the flag-setting sibling of SUB; see the flags N Z C V in Registers and Register File.

Level 3 — Analysis

Goal: can you reason about behaviour, timing, and trade-offs?

Exercise 3.1

Run $n = 200$ instructions on a $k = 5$ stage pipeline with $τ = 2 ns$ . Compute $T_{serial}$ , $T_{pipe}$ , and the speedup $S$ .

Recall Solution 3.1

Plug into the boxed formulas.

$T_{serial} = n k τ = 200 \times 5 \times 2 = 2000 ns$ .
$T_{pipe} = (k + n - 1) τ = (5 + 199) \times 2 = 204 \times 2 = 408 ns$ .
$S = \frac{2000}{408} \approx 4.90$ .

Reading it: $S \approx 4.90$ is close to $k = 5$ because 200 is large enough that the 5-cycle fill cost is a small fraction. See Instruction Pipelining.

Exercise 3.2

For the same $k = 5$ pipeline, how large must $n$ be before the speedup reaches 90% of the ideal, i.e. $S \geq 0.9 k = 4.5$ ? Solve for the smallest integer $n$ . The figure below plots the whole curve so you can see the answer.

Recall Solution 3.2

Set $S = \frac{nk}{k + n - 1} \geq 4.5$ with $k = 5$ : $\frac{5 n}{n + 4} \geq 4.5$ Multiply both sides by $(n + 4)$ (positive, so inequality direction is safe): $5 n \geq 4.5 (n + 4) = 4.5 n + 18$ $0.5 n \geq 18 \Rightarrow n \geq 36.$ Smallest integer: $n = 36$ . Check: $S = \frac{5 \cdot 36}{36 + 4} = \frac{180}{40} = 4.5$ exactly.

Exercise 3.3

A branch misprediction on this $k = 5$ pipeline flushes the partly-built instructions and refills. Suppose the flush penalty is $(k - 1)$ cycles. If 1 in every 20 instructions is a mispredicted branch, what is the average cycles per instruction (CPI), and how does conditional execution help?

Recall Solution 3.3

Why base CPI is 1: as derived at the top of this page, an ideal hazard-free pipeline pops out exactly one instruction every cycle in steady state (its initiation rate is 1). So if nothing ever stalled, every instruction would cost 1 cycle on average, i.e. $CPI = 1$ . A misprediction adds $(k - 1) = 4$ penalty cycles, and this happens with probability $\frac{1}{20}$ : $CPI = 1 + \frac{1}{20} \times 4 = 1 + 0.2 = 1.2 cycles/instruction .$ Conditional execution helps by turning a small if (a branch that can mispredict) into straight-line predicated code (e.g. ADDEQ). Fewer branches ⇒ fewer flushes ⇒ CPI stays near 1 ⇒ more predictable timing, which is exactly what Real-Time Systems and WCET needs.

Exercise 3.4

Now a data hazard. Consider:

LDR R4, [R1]     ; load a value into R4
ADD R5, R4, R6   ; immediately uses R4

The ADD needs R4 before the LDR has finished bringing it back from memory. Even with forwarding hardware, this costs a 1-cycle load-use stall. If such load-use pairs are 1 in every 10 instructions on the $k = 5$ pipeline (branches ignored here), what is the CPI?

Recall Solution 3.4

Why forwarding can't fully hide a load: forwarding pipes a result from one stage's output directly into a later instruction's input, hiding most ALU-to-ALU dependencies with zero cost. But a load's data isn't available until after the memory stage — one stage too late for the very next instruction — so the pipeline must insert 1 bubble (stall) cycle. This is the famous load-use delay. $CPI = 1 + \frac{1}{10} \times 1 = 1 + 0.1 = 1.1 cycles/instruction .$ Compilers reduce this by scheduling an unrelated instruction between the load and its use. See Instruction Pipelining and Memory Hierarchy and Cache.

Level 4 — Synthesis

Goal: can you combine several ideas into one design decision?

Exercise 4.1

You must implement if (a == b) c = c + 1; two ways and compare cycle cost on the $k = 5$ pipeline (flush penalty $= k - 1 = 4$ ). Assume a,b,c are already in R0, R1, R2.

(A) Branch version:

CMP  R0, R1
BNE  skip
ADD  R2, R2, #1
skip:

(B) Predicated version:

CMP  R0, R1
ADDEQ R2, R2, #1

For the case where a == b (branch not taken but predictor guessed "taken" → mispredict), count cycles for each, ignoring the shared CMP. Assume the predicated instruction issues in a single cycle (the standard case on ARMv7-A, which supports full conditional execution).

Recall Solution 4.1

Count only the instructions after the shared CMP.

(A) Branch, mispredicted: the BNE costs 1 cycle to issue plus a 4-cycle flush penalty when the guess is wrong, then the ADD runs (1 cycle). Total $= 1 + 4 + 1 = 6$ cycles.
(B) Predicated: just ADDEQ, one straight-line instruction, no branch, no flush $= 1$ cycle.

Predication is $6/1 = 6 \times$ cheaper here, and — more importantly for aerospace — it always takes the same number of cycles whether or not the condition holds. That constant cost is gold for Real-Time Systems and WCET.

Corner case (footnote): this clean $1$ -cycle figure assumes the core executes a predicated instruction in a single cycle — true for classic 32-bit ARM (A32), which predicates almost every instruction. On Thumb/Thumb-2 and on some cores, general predication is replaced by an IT (if-then) block that predicates a short run of following instructions, and on machines with no single-cycle predication a predicated op may still consume its slot even when the condition is false. So predication removes the flush risk but is not always literally free — the win over a misprediction, however, still holds.

Exercise 4.2

You are choosing a core for a battery-powered flight sensor. Core X: $k = 12$ stages, clock $2.0 GHz$ (so cycle time $t_{X} = 0.5 ns$ ). Core Y: $k = 5$ stages, clock $1.0 GHz$ (so cycle time $t_{Y} = 1.0 ns$ ). Branches are 15% of instructions with a 30% misprediction rate; flush penalty $= (k - 1)$ . (a) Compute each core's average CPI. (b) Compute the average time per instruction $= CPI \times (cycle time)$ , so the clock rates actually enter. (c) Which core is faster on this branchy code, and which do you pick for a real-time job — and why?

Recall Solution 4.2

(a) Average CPI $= 1 + (branch fraction) \times (mispredict rate) \times (k - 1)$ :

Core X: $CPI_{X} = 1 + 0.15 \times 0.30 \times (12 - 1) = 1 + 0.045 \times 11 = 1 + 0.495 = 1.495$ .
Core Y: $CPI_{Y} = 1 + 0.15 \times 0.30 \times (5 - 1) = 1 + 0.045 \times 4 = 1 + 0.18 = 1.18$ .

So on CPI alone, Y looks better ( $1.18 < 1.495$ ). But CPI ignores clock speed — a cycle on X is half the length of a cycle on Y, so we must convert to real time.

(b) Average time per instruction $= CPI \times (cycle time)$ :

Core X: $t_{X} \cdot CPI_{X} = 0.5 ns \times 1.495 = 0.7475 ns/instr$ .
Core Y: $t_{Y} \cdot CPI_{Y} = 1.0 ns \times 1.18 = 1.18 ns/instr$ .

(c) Verdict on raw speed: despite its worse CPI, Core X is actually faster per instruction ( $0.7475 ns < 1.18 ns$ , about $1.58 \times$ quicker) because its 2× clock more than pays for the extra flush penalty. This is the whole point: lower CPI does not mean faster — you must multiply by cycle time.

Which to pick for the real-time flight job? Still Core Y — but not because it is faster on average. Pick it because (1) its shallow $k = 5$ pipeline has a smaller, more predictable worst-case flush penalty (4 vs 11 cycles), giving tighter WCET bounds you can certify; and (2) a slower-clock, shallow core generally wins on performance-per-watt, which matters on a battery. Core X's raw-speed advantage is the throughput metric — the right choice for a server, the wrong priority for a deadline-bound, power-limited flight sensor.

Level 5 — Mastery

Goal: can you derive a result and defend a subtle claim end-to-end?

Exercise 5.1

Derive the exact $n$ at which pipeline speedup reaches a general fraction $f$ of ideal, i.e. $S = f k$ (with $0 < f < 1$ ), then sanity-check against Exercise 3.2 ( $f = 0.9, k = 5$ ).

Recall Solution 5.1

What we do: set the speedup equal to $f k$ and solve for $n$ . $\frac{nk}{k + n - 1} = f k$ The $k$ on both sides cancels (divide both sides by $k$ , valid since $k > 0$ ): $\frac{n}{k + n - 1} = f$ Why cancel? It reveals that the fraction of ideal does not depend on $k$ directly, only on how $n$ compares to $k - 1$ . Cross-multiply: $n = f (k + n - 1) = f n + f (k - 1)$ $n - f n = f (k - 1) \Rightarrow n (1 - f) = f (k - 1)$ $n = \frac{f ( k - 1 )}{1 - f}$ Check with $f = 0.9, k = 5$ : $n = \frac{0.9 \times 4}{0.1} = \frac{3.6}{0.1} = 36$ . ✓ Matches Exercise 3.2 exactly.

What it looks like: as $f \to 1$ the denominator $1 - f \to 0$ , so $n \to \infty$ — you can never fully reach ideal $k$ with finite work; you only approach it, exactly as the flattening curve in the figure shows.

Exercise 5.2

Defend or refute: "For a hard real-time flight controller, a pipeline that averages CPI 1.18 but can spike to CPI 5 on a rare mispredict-heavy path is preferable to one that is always exactly CPI 1.4."

Recall Solution 5.2

Refute. Real-time correctness is governed by worst-case execution time (WCET), not average. A path that spikes to CPI 5 means the worst case is $5/1.4 \approx 3.6 \times$ slower than the steady one — if the flight-control loop must finish inside a fixed deadline, that spike can blow the deadline and the average is irrelevant. The always-1.4 core has a tight, provable upper bound, which is exactly what you can certify. This is the deep reason ARM's predictable, conditionally-executed, shallow-pipeline design is loved in aerospace: it trades a little average speed for a small, analysable worst case. See Real-Time Systems and WCET and Power and Performance-per-Watt.

Numeric anchor: worst-case ratio $= 5/1.4 \approx 3.571$ ; if the deadline budget is only $2 \times$ the nominal, this core fails certification.

Recall One-paragraph Feynman recap of this whole exercise set

Everything here spins around two truths. First, ARM's ALU only cooks with ingredients on the counter (registers), so real code is always load → compute → store. Second, pipelines make throughput approach $k \times$ , but only when work $n$ is large and hazards behave — control hazards (mispredicted branches) cost $(k - 1)$ cycles, and even loads cost a 1-cycle bubble their following user can't dodge. For phones you chase the average; for spaceships you chase the worst case, which is why ARM stays shallow, predictable, and conditionally-executed.

Active recall

At what value of

n

does a

k

-stage pipeline reach fraction

f

of ideal speedup?

n = \frac{f ( k - 1 )}{1 - f}

Why does the first instruction cost

k

cycles but each later one only 1?

The first must traverse all

k

stages to finish (fill time); after that, one instruction pops out every cycle because the initiation rate of an ideal pipe is 1 per cycle.

Why can't forwarding fully hide a load-use dependency?

A load's data is only ready after the memory stage — one stage too late for the very next instruction — so a 1-cycle stall (bubble) remains.

Why is a lower-CPI core not automatically faster than a higher-CPI one?

Real time per instruction is CPI times cycle time — a faster clock can make a higher-CPI core win, so you must convert CPI to actual time before comparing across different clock rates.

What does CMP A, B actually store?

Nothing — it computes

A - B

only to set the N Z C V flags for a later conditional instruction.