581365-8 Computer Organization II, course exam 1.11.2002         [ Kääntöpuolella suomeksi]

Write in each sheet of paper: your name and signature, student id, course name, and page number.

1.  [12 p] Booth's Algorithm for integer multiplication.
   1. [6 p] What is the basic idea in Booth's algorithm?
   2. [2 p] Give as an example how Booth's algorithm works with multiplication 27*27.
   3. [2 p] When is Booth's algorithm faster than the conventional approach? Give an example.
   4. [2 p] When is Booth's algorithm slower than the conventional approach? Give an example.
       
2. [12 p] Cache and TLB
   1. [2 p] What is there common with cache and TLB? What are the biggest differences?
   2. [2 p] How does principle of locality affect to the implementation of cache and TLB? Are there any differences?
   3. [2 p] What advantage is there in having long cache blocks (lines)? 
   4. [2 p] What advantage is there in having large sets in set-associative TLB's? 
   5. [2 p] What advantage is there in having multiple levels of caches?
   6. [2 p] What does the concept "split cache" mean? How is that related to TLB?
      
      
      
3.  [12 p] Hardwired and microprogrammed control
   1. [3 p] What problem is solved by control?
   2. [3 p] What is common with hardwired and microprogrammed control?
   3. [2 p] What disadvantages are there in hardwired control as compared to microprogrammed control?
   4. [2 p] What advantages are there in hardwired control as compared to microprogrammed control?
   5. [2 p] There are the concepts of horizontal and vertical microdode in microprogrammed control. Do similar concepts also apply the hardwired control? If they do, what do they mean? If they do not, why?
        
      
4. [12 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.
   
   Observe the following set of instructions generated by the compiler:

   	Load	R2, VarX   ; Regs(R2) <- Mem(VarX)
   	Add	R5, R5, R2 ; Regs(R5) <- Regs (R5) + Regs(R2)  
   	Move	R2, R6     ; Regs(R2) <- Regs (R6)
   	Add	R3, R3, R2
   	Mul	R3, R2, R5 
   	Jnzer	R2, Loop
   	Add	R3, R2, R5

   Many aspects in the preceding code segment may reduce the execution speed from the maximum possible for that architecture.
   1. [6 p] Describe precisely the problem types defined below and mark in a clear way all occurrences of each problem type in the preceding code segment:
      • data dependencies
      • structural dependencies
      • control dependencies
      How can one avoid or reduce the performance problems caused by each problem type?  
       
   2. [3 p] Assume now, that the architecture is implemented as superscalar. Describe precisely new problem types given below and mark in a clear way all occurrences for each problem type in the preceding code segment.
      • output dependencies
      • antidependencies
      How can one avoid or reduce the performance problems caused by each new problem type?
       
   3. [3 p] Assume now, that a functionally correct emulator has been implemented for this architecture. The emulator is implemented according to normal von Neumann architecture and it executes given machine language code one instruction at a time. Which dependencies described in parts (a) and (b) must be considered in the emulation and how? Why?

       Make all needed assumptions and write them down.