Computer Organization I, Fall 2001, HW 4

1. Hamming code.
   1. Show how error correcting Hamming code recognizes and corrects a mistake when the 3. bit from left has changed in 7-bit data 011 0100.
      (these 7 bits contain both the data and parity bits)
   2. How many wires (bits) does one need to protect a 32-bit data bus with error correcting Hamming code?
      (We want to move 32 bits of data in addition to the parity bits)
   3. Why is Hamming code not a good approach to secure LAN data transfers?
      

    

2. Cache memory. Assume that data access time (1 word) from cache memory is 2 ns, and 10 ns from main memory. Cache block (line) size is four words. Assume that 97% of memory references are found from the cache when cache is used. You may (unrealistically) assume that there is always room for a new block in the cache and that the data transfer time from MBR to cache is zero.
   1. If cache is not used, how long does it take to read the data (1 word) to a register, in average?
   2. If cache is used, how long does it take to read the data (1 word) to a register, in average?
   3. How does a process know if the data was found in cache or not?
   4. How does the application user (person)  know if the data was found in cache or not?
   5. How can a user (programmer) influence the effectiveness of the cache memory? 

    

3. Prosess
   1. What happens if the Ready-to-Run queue is empty?
   2. Can there be many processes for the same program at the same time in Ready-to-Run queue? Why or why not?
   3. Which takes longer, subroutine call or process switch? Why?
   4. Is cache contents part of  processor context (of a process) or not? Why?
   5. Are MAR and MBR part of processor context or not? Why?
      
      
4. Assume that there is an operating system for TTK-91. One part of that OS is the process control.  Assume further that due to a clock interrupt we need to switch the process that runs on the processor.
1. How and where are the data for the process earlier in execution stored? Which data must be stored?
2. How and from where does one find the data for the new process? Where is the first instruction for the new process? How is the processor turn actually given to the new process?
3. What is the processor state (user, priviledged) from the time just before the clock interrupt until the execution of the first instruction of the new process?
   
   
5. [2 htp] Jump table. Long switch statements can slow down program execution. For example, if one is executing some loop many times and each time one must select one case out of 60 possible cases. This will take 30 comparisons in average, and each comparison involves at least 2 machine instructions!

   If the selection values are integer valued, starting from zero and making up more or less contiquous value set, then one can use a jump table instead of many if-then-else type comparisons. With jump table one can reach the right case in a fixed time with just a few machine instructions. Jump table contains many jump instructions (one per case), of which one is selected with indexed addressing mode. For example, if register R3 contains the selection value, and jump table address is JTBL, then the right jump instruction is selected in the jump table with machine instruction "JUMP JTBL(R3)".

    

   1. Give a (Koksi executable) ttk-91 example on jump table use, when there are 10 cases to select from.
   2. How does one implement the switch statement above, if the jump table contains only the case addresses instead of the jump instructions leading to each case? Give the implementation for the same example as in part (a).
   3. When is type (a) implementation better than type (b) implementation? Why?
   4. When is type (b) implementation better than type (a) implementation? Why?
   5. If each case takes 10 instructions and there are 60 cases, then how much (%) does the use of jump table speed up the execution (as compared to multiple comparison approach)? Is there a difference between implementations (a) and (b) in this respect?

    

Be prepared to show all Koksi related and other programming homeworks using a PC at the practice session. Please bring both a listing and on a diskette all the programs you made for this practice session.