581365-8 Computer Organization II, Exam 19.11.2013   Kääntöpuolella suomeksi

1. [9 p] Cache and TLB
   1. [3 p] What problem will a cache try to solve? What type of locality is cache solution based on and why? What exactly happens when there is a cache miss and what is its performance cost?
   2. [3 p] What problem will a TLB solve? What type of locality is TLB solution based on and why? What exactly happens when there is a TLB miss and what is its performance cost?
   3. Explain the term "set associative cache".
   4. Explain the terms "unified cache" and "split cache".
   5. How do the cache and the TLB relate to each other?
   
   
2. [18 p] Dependencies. Assume that RISC architecture ALU instructions have three register operands and that the result is stored into the first (left-most) register. The architecture is implemented in ordinary (not superscalar) pipelined fashion so that, in best case, one instruction can be completed in each cycle. The pipeline has 5 phases (instruction fetch, instruction decode, register read, ALU, write back).
   
   Observe the following set of instructions generated by the compiler (instruction number on left):

   1         Load  R2, VarX     ; Regs(2) <- Mem(VarX)
   2         Add   R5, R5, R2   ; Regs(5) <- Regs(5) + Regs(2)  
   3 Loop    Move  R2, R6       ; Regs(2) <- Regs(6)
   4         Add   R3, R3, R2
   5         Add   R2, R3, R5 
   6         Jnzer R3, Loop
   7         Move  R1, R2

   Many aspects in the given code segment may reduce the execution speed from the maximum possible.
   1. [6 p] Describe precisely the problem types data dependency (raw), control dependency, and structural dependency. Mark in a clear way one occurrence of each problem type in the given code segment (if it appears there).
      
   2. [6 p] How can one avoid or reduce the performance effects caused by data, control or structural dependencies? Give six solution methods (at least one of each dependency type, and at least two solutions for control dependency) and describe briefly how it works. Solution methods should be such that they would not require stopping the pipeline ("bubble").
      
   3. [4 p] Assume now, that the architecture is implemented as superscalar with fetch policy fetch and decode 3 instructions at a time and issue policy out-of-order issue, out-of-order completion. Describe precisely new dependency types (output dependency (waw), antidependency (war)) and mark in a clear way one occurrence for each problem type in the given code segment (if it appears there).
      
   4. [2 p] How can one avoid or reduce the performance problems caused by these new dependency types given in part (c)? Give one solution to each new dependency type and describe briefly how it works. Solution methods should be such that they would not require stopping the pipeline ("bubble").


3. [9 p] Control
   1. [1 p] What problem is solved by control?
   2. [2 p] How is microprogrammed control implemented?
   3. [2 p] Compare microcode instructions to machine language machine instructions? Differencies? Similarities?
   4. [2 p] What is the difference between horizontal and vertical microcode? Give an example.
   5. [2 p] What advantages/disadvantages are there in microprogrammed control as compared to hardwired control?