Exercises — Harvard architecture — separate instruction - data memory

Problem: the Von Neumann bottleneck — on a single shared bus the CPU must choose each cycle to either fetch an instruction or move data, never both. How Harvard attacks it: it gives instructions and data physically separate memories and buses, so one instruction fetch and one data access happen in the same cycle (in parallel). One wire carries one signal; two wires carry two.

• (a) fetched opcode → instruction path (every instruction is fetched over the instruction bus).
• (b) value written by store → data path (data bus, which is read and write).
• (c) read-only program image → instruction path (instruction memory, usually read-only).
• (d) variable being incremented → data path.

Cross-check against the figure above: the black $F$ boxes are the instruction-path traffic (a, c); the red $D$ boxes are the data-path traffic (b, d).

What we do: plug into the carried formulas. $T_{\text{vN}}=N(1+f)=2000(1+0.25)=2000\times 1.25=2500\text{ cycles}$ Why: $2000$ fetches on the shared bus, plus $0.25\times 2000=500$ extra data turns that must wait their turn on that same bus. (In the s01 figure: $500$ extra red boxes stacked beside the black ones.) $T_{\text{H}}=N=2000\text{ cycles}$ Why: the $500$ data accesses overlap the fetches on the second bus — they cost $0$ extra cycles. (In the s01 figure: those red boxes slide under the black ones.) $S=\frac{2500}{2000}=1.25=1+f✓$

What we do: Harvard cost is always $T_{\text{H}}=N=2000$ regardless of $f$. Set von Neumann to $3000$: $N(1+f)=3000\Rightarrow 2000(1+f)=3000\Rightarrow 1+f=1.5\Rightarrow f=0.5$ Interpretation: half the instructions touch data. Then $S=1+f=1.5$ — Harvard is $1.5\times$ faster. This is a memory-heavy workload, exactly where the second bus pays off.

$S_A=1+0.1=1.1,S_B=1+0.6=1.6$ Workload B benefits more. $\frac{S_B}{S_A}=\frac{1.6}{1.1}\approx 1.4545$ Why: the speed-up scales with memory pressure $f$. B does $6\times$ more data traffic fraction, so there is far more work for the second bus to hide. Register-bound A (little data traffic) leaves the data bus mostly idle.

$S=1+f$ and $f$ can be at most $1$ (you cannot have more than 100% of instructions touch data). So: $S_{\max }=1+1=2$ reached only when every instruction accesses data ($f=1$). The claim "always doubles" is false in two ways: (1) $2\times$ is a ceiling, not a guarantee; (2) it is reached only in the extreme $f=1$ case. For typical $f\approx 0.3$–$0.4$, $S\approx 1.3$–$1.4$.

What we do: compute $P$ for each.

• Von Neumann: $S=1$, area $=1\Rightarrow P_{\text{vN}}=1/1=1$.
• Harvard: $S=1+0.3=1.3$, area $=1.6\Rightarrow P_{\text{H}}=1.3/1.6=0.8125$. Decision: on performance-per-area, von Neumann wins ($1>0.8125$) at this low $f$. Harvard buys $1.3\times$ speed but pays $1.6\times$ area — the extra hardware isn't "paid back" here. Insight: Harvard's advantage must clear its area cost. It wins on raw speed but can lose on efficiency when $f$ is small.

Problem with pure Harvard: instruction memory is separate and usually read-only, so you cannot easily write a program as data into it — loading firmware, running a compiler's output, or self-modifying code all break. Modified Harvard mechanism: a single unified main memory at the bottom (von Neumann-style, so programs load as ordinary data), but split L1 caches near the CPU — a separate I-cache on the instruction path and a D-cache on the data path. On the hot path the CPU fetches from I-cache and accesses D-cache in parallel (Harvard's win); the flat unified memory keeps flexibility (von Neumann's win). "Best of both."

Von Neumann — one shared bus, everything serializes: $T_{\text{vN}}=\underset{\text{fetches}}{\underbrace{N}}+\underset{\text{data accesses}}{\underbrace{kfN}}=N(1+kf)$ Harvard — the instruction bus needs $N$ cycles for fetches. The data bus needs $kfN$ cycles for data (only one access per cycle). They run in parallel, so total time is the larger of the two (whichever bus is the bottleneck): $T_{\text{H}}=\max (N,kfN)$ Why $\max$ and not sum: the two buses overlap, so the machine waits only for the slower stream to finish. Speed-up: $S=\frac{N(1+kf)}{\max (N,kfN)}=\frac{1+kf}{\max (1,kf)}$ Evaluate $N=1000,f=0.4,k=3$: here $kf=3(0.4)=1.2$.

• $T_{\text{vN}}=1000(1+1.2)=2200$ cycles.
• $kfN=1.2\times 1000=1200>N=1000$, so the data bus is the bottleneck: $T_{\text{H}}=\max (1000,1200)=1200$ cycles.
• $S=2200/1200\approx 1.8333$. Insight: because $kf>1$, the data bus is now busier than the instruction bus — the fetches hide "under" the data accesses instead of the reverse. Harvard still helps, but the ideal $S=1+f$ formula no longer applies once one bus saturates.

(a) $f=0$ (pure register arithmetic): $kf=0$, so $\max (1,0)=1$, giving $S=\frac{1+0}{1}=1.$ No data traffic ⇒ nothing to overlap ⇒ no speed-up. The data bus sits idle. (b) $k=1$: then $kf=f\le 1$, so $\max (1,f)=1$, giving $S=\frac{1+f}{1}=1+f,$ exactly the base-model formula — good, our refined model contains it as a special case. (c) $kf=1$ (both buses equally loaded, perfectly balanced): $\max (1,1)=1$, $S=\frac{1+1}{1}=2.$ The maximum "balanced" speed-up — both buses fully busy, neither waiting. (d) $kf\to \infty$ (data completely dominates): $\max (1,kf)=kf$, so $S=\frac{1+kf}{kf}=\frac{1}{kf}+1\to 1.$ As data traffic grows without bound, both machines are dominated by the same data stream, and Harvard's fixed instruction bus becomes negligible — the advantage shrinks back toward $1$. Peak benefit is at the balance point $kf=1$, not at extreme data load.

The shape of these four cases is exactly the curve below — read it as the answer to "how does the speed-up move as I add data accesses?"

Follow the red curve left-to-right: it climbs from $S=1$ at $kf=0$ (case a), rises linearly along the $1+kf$ branch while the instruction bus is the bottleneck (case b region), hits its peak $S=2$ at the black dot $kf=1$ (case c, balanced buses), then bends over and sinks back toward the dashed $S=1$ line as $kf\to \infty$ (case d, the data bus saturates and dominates both machines).