Remainder = Remainder − Divisor
if Remainder < 0: Remainder += Divisor; Q bit = 0 # restore
else: Q bit = 1
shift Divisor right
MIPS: Lo = quotient, Hi = remainder. Signed: negate the quotient if operand signs differ; the remainder takes the dividend's sign. Time O(n) (n+1 steps); Space O(n) (three registers).
2abig(a) Explain pipelining and hazard. Explain the structural hazard with an example, then devise the solutions. [5]
Pipelining overlaps instruction execution across stages that use separate hardware, raising throughput. A hazard is any condition that prevents the next instruction from entering the pipeline in the next cycle. A structural hazard occurs when two instructions need the same resource at once — e.g. a single memory serving both an IF and a MEM in the same cycle. Solutions: duplicate the contended resource — a split cache (separate instruction/data memory); more generally, add hardware or (as a fallback) stall the pipeline for a cycle.
2bbig(b) Divide the stages in MIPS pipelined execution. Diagram the pipelined datapath with the stages identified. [5]
Five stages, each with its own hardware, separated by four pipeline registers (IF/ID, ID/EX, EX/MEM, MEM/WB): Pipelined execution: at steady state (CC5) all five stages are busy on five different instructions.
3abig(a) Explain the memory hierarchy along with a diagram. [3]
A memory hierarchy stacks several memory technologies. Closer to the CPU = smaller, faster, costlier per bit; farther = larger, slower, cheaper. Each level caches the one below, and locality keeps most accesses in the fast levels — giving the illusion of a big, fast, cheap memory. As distance from the CPU grows, both size and access time increase — the essence of a memory hierarchy.
3bsmall(b) Diagram a direct-mapped cache with 64K 1-word blocks, 32-bit address. [3]
Lines = 64K = 216 ⇒ index = 16 bits. 1-word block ⇒ block offset 0, byte offset 2. Tag = 32−16−2=14 bits. 65,536-line direct-mapped cache, one 32-bit word per line.Each line = valid + 14-bit tag + 32-bit data; index selects one of 65,536 lines.
3cbig(c) Total number of memory units (bits) for a direct-mapped cache with 2 MB of data and 8-word block size, 32-bit address. [4]
Block = 8 words = 32 B = 25 ⇒ lines = 2MB/32B=221/25=216=65536. block offset = 3, byte offset = 2, index = 16, tag = 32−16−3−2=11.