Question 5 of 6: Memory-Hierarchy Access Time, RPN-to-Infix, and Control-Unit Styles

Question 5: Memory-Hierarchy Access Time, RPN-to-Infix, and Control-Unit Styles (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A two-level hierarchy with overall average access time 12 ns, top-level hit rate 90%, top-level access time 5 ns. (b) Two postfix (RPN) expressions over operands $A$–$H$. (c) The two families of control-unit implementation. (d) The general concept of microprogramming.

Find. (a) The lower level's access time. (b) The equivalent infix expression for each RPN string. (c) Pros/cons of hardwired vs. micro-programmed control. (d) Three applications of microprogramming.

Approach. (a) apply the average-memory-access-time (AMAT) model, $\text{AMAT}=T_{hit}+(1-H)\times T_{\text{lower}}$, and solve for the unknown; (b) evaluate each postfix string with a stack, popping the two most-recently-pushed values as (left, right) operands for each operator encountered; (c)–(d) contrast the two control-unit design philosophies and their use cases.

1. Part (a) — lower-level access time. The standard two-level AMAT model charges the top-level access time on every reference, plus the lower level's access time only on the fraction of references that miss the top level: $$\text{AMAT}=T_{\text{top}}+(1-H)\times T_{\text{lower}}$$ Substituting $\text{AMAT}=12$ ns, $T_{\text{top}}=5$ ns, $H=0.90$: $$12=5+(1-0.90)\times T_{\text{lower}}\ \Rightarrow\ 7=0.10\times T_{\text{lower}}\ \Rightarrow\ T_{\text{lower}}=\boxed{70\ \text{ns}}$$
2. Part (b) — reverse Polish to infix. Reading each postfix string left to right with a stack, each operator pops its two most-recent operands (the more recently pushed value is the RIGHT operand) and pushes the resulting sub-expression back onto the stack.

   (1) $A\ B\ C\ D\ E\ {+}\ {*}\ {*}\ {/}$: push $A,B,C,D,E$; "+" combines $D,E\to(D{+}E)$; "*" combines $C,(D{+}E)\to C(D{+}E)$; "*" combines $B,\,C(D{+}E)\to B\,C\,(D{+}E)$; "/" combines $A,\,B\,C\,(D{+}E)\to A/[B\,C\,(D{+}E)]$: $$\boxed{A \div \big(B\times C\times(D+E)\big)}$$

   (2) $A\ B\ C\ D\ E\ {+}\ F\ {/}\ {+}\ G\ {-}\ H\ {/}\ {*}\ {+}$: push $A,B,C,D,E$; "+" combines $D,E\to(D{+}E)$; push $F$; "/" combines $(D{+}E),F\to(D{+}E)/F$; "+" combines $C,(D{+}E)/F\to C+(D{+}E)/F$; push $G$; "−" combines $[C+(D{+}E)/F],G\to[C+(D{+}E)/F]-G$; push $H$; "/" combines the previous result, $H\to\{[C+(D{+}E)/F]-G\}/H$; "*" combines $B$ with that $\to B\{[C+(D{+}E)/F]-G\}/H$; "+" combines $A$ with that: $$\boxed{A+B\times\frac{\left(C+\dfrac{D+E}{F}\right)-G}{H}}$$

3. Part (c) — hardwired vs. micro-programmed control unit. Hardwired control implements the control-signal sequencing directly in combinational/sequential logic (state machines, PLAs). Advantages: very fast (no memory-fetch step to retrieve each control word) and no extra control-store hardware. Disadvantages: the logic is fixed at fabrication time — adding, changing, or fixing an instruction's control sequence requires a hardware redesign, and the design/verification effort grows quickly with instruction-set complexity. Micro-programmed control stores each instruction's control-signal sequence as a series of micro-instructions in a control store (ROM/writable control store), fetched and stepped through by a micro-sequencer. Advantages: far easier to design, debug, and modify (changing behaviour is a control-store rewrite, not a re-fabrication) and naturally supports a large, complex, or even user-extensible instruction set. Disadvantages: slower, since every control word must first be fetched from the control store before it can drive the datapath, and the control store itself adds cost/area. Hardwired trades design flexibility for raw speed; micro-programmed trades some speed for flexibility, easier design, and support for complex ISAs.
4. Part (d) — three applications of microprogramming.
   • Emulation: microprogramming lets one hardware platform implement the instruction set of a DIFFERENT machine, by writing microcode that interprets the target ISA's instructions in terms of the host's native micro-operations — used historically to let new machines run software written for an older, discontinued line.
   • Instruction-set extension / customization: new or specialized instructions (e.g. complex string, decimal-arithmetic, or application-specific operations) can be added by writing new microcode routines rather than redesigning hardware, letting a single hardware base support several ISA variants or be patched after fabrication.
   • Bug fixes and errata correction (microcode patching): a design flaw or incorrect control sequence discovered after a CPU ships can often be corrected by loading a revised microcode image (e.g. via a writable/reloadable control store or firmware update) instead of a costly silicon respin — the mechanism behind many modern CPU "microcode updates."
   All three exploit the same property: because micro-programmed control is DATA (a stored sequence of micro-instructions) rather than fixed logic, it can be authored, extended, or corrected in software long after the hardware is built.