Question 5 of 6: Hit-Rate Sizing, Infix-to-RPN, and Control-Unit Design
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-Comp-A3, Computer Architecture — National Exams, December 2015. Closed-book, 3 hours; six questions of equal value (20 marks each); FIVE constitute a complete exam (all six answered below as a complete study resource).
Reference texts: Patterson & Hennessy, Computer Organization and Design, 6th ed. — memory hierarchy & cache performance (Q1a, Q2a, Q3a, Q5a), instruction encoding & RISC design (Q2c, Q3b, Q4c), IEEE-754 floating point (Q4b), and memory technology (Q4a); Mano & Ciletti, Digital Design, 6th ed. — control-unit design, register-transfer micro-operations, stack/RPN notation, and binary-multiplication hardware (Q1b, Q3c, Q5b–d, Q6a–c).
Question 5: Hit-Rate Sizing, Infix-to-RPN, and Control-Unit Design (20 marks)
Given. (a) $T_{cache}=8$ ns, $T_{main}=60$ ns, target $T_{avg}=10$ ns. (b) Two fully-parenthesized infix expressions over operands $A$–$H$. (c) The two ways of implementing a CPU's control unit. (d) The micro-program word as the object whose length is being sized.
Find. (a) The hit rate $h$ that achieves $T_{avg}=10$ ns. (b) Reverse-Polish (postfix) equivalents of both expressions. (c) Pros/cons of hardwired vs. micro-programmed control. (d) Three factors sizing the micro-program word.
Approach. (a) solve the two-level weighted-average-access-time equation for $h$; (b) apply a stack-based (or innermost-out) infix→postfix conversion, respecting parenthesis nesting and operator precedence; (c)–(d) reason from the same hardwired-vs-stored-control tradeoff used in Q1(b).
Check: part (a) is solved with the simple two-level weighted-average model $T_{avg}=h\,T_{cache}+(1-h)\,T_{main}$ (the question supplies only "access time" for each level, not a separate miss-penalty figure); if a miss instead requires paying $T_{cache}$ AND THEN $T_{main}$ ($T_{miss}=T_{cache}+T_{main}=68$ ns), the required hit rate would instead be $h=(68-10)/(68-8)=58/60\approx96.7\%$ — close to, but not identical with, the answer below.
Part (a) — required hit rate. The two-level weighted average access time is
$$T_{avg}=h\,T_{cache}+(1-h)\,T_{main}.$$
Substituting the given values and solving for $h$:
$$10=8h+60(1-h)=60-52h\ \Longrightarrow\ 52h=50\ \Longrightarrow\ h=\frac{50}{52}=\boxed{0.9615=96.15\%}.$$
Part (b) — infix to reverse Polish. Converting each sub-expression from the innermost parentheses outward (postfix places an operator immediately after its two already-converted operands):
(1) $(A+B)\to AB{+}$; $(C+D)\to CD{+}$; multiplying these two results, then adding $E$:
$$\boxed{A\ B\ {+}\ C\ D\ {+}\ {\times}\ E\ {+}}$$
(2) Working from the innermost product outward: $D\times E\to DE{\times}$; $C-D\times E\to C\,DE{\times}\,{-}$; dividing by $F$: $\ldots F{/}$; dividing again by $G$: $\ldots G{/}$; $(A-B)\to AB{-}$; multiplying that by the big parenthesized quotient, then by $H$:
$$\boxed{A\ B\ {-}\ C\ D\ E\ {\times}\ {-}\ F\ {/}\ G\ {/}\ {\times}\ H\ {\times}}$$
Part (c) — hardwired vs. micro-programmed control.Hardwired control implements the control-signal logic directly as combinational/sequential circuitry (state machine + gates) tailored to the exact instruction set. Advantages: fastest possible control (no extra memory-fetch step to obtain each control word), no control-store area. Disadvantages: the logic is fixed in silicon — adding or changing an instruction requires re-designing (and re-fabricating) the control circuit, and complex instruction sets make the logic very difficult to design, verify, and debug. Micro-programmed control stores each instruction's sequence of control words (micro-instructions) in a control-store ROM/PLA, and a micro-program counter/sequencer steps through them. Advantages: new instructions or bug fixes can be made by rewriting micro-code, which is far simpler and cheaper to design/verify/change than redesigning hardware, and it naturally supports large, complex (CISC-style) instruction sets. Disadvantages: slower — every micro-instruction must first be fetched from the control store before it can drive the datapath, adding at least one extra access in the critical control path. Hardwired: fastest, inflexible. Micro-programmed: flexible/maintainable, slower.
Part (d) — factors influencing micro-program word length.
Number of control signals/micro-operations that must be specifiable — more distinct datapath signals (register loads, ALU function selects, bus enables, etc.) directly widen a horizontally-encoded word (one bit per signal) or the number/width of encoded fields in a vertical encoding.
Encoding scheme (horizontal vs. vertical/encoded fields) — a fully horizontal word needs one bit per control line, while grouping mutually-exclusive signals into encoded fields (vertical micro-programming) trades word width for an added decoder, so the CHOICE of encoding directly sets how many bits the word needs for the same set of controllable signals.
Next-address (sequencing) field width — if each micro-instruction explicitly specifies the address of the next micro-instruction (rather than simply incrementing a micro-program counter), that field must be wide enough to address the entire control store, plus room for any condition-code/branch-test bits used to support conditional micro-branching.
(A fourth commonly cited factor is the width needed to encode any literal/immediate data field carried directly in the micro-instruction, e.g. a constant loaded into a register.)
