Computer Organisation I

Exercise 4 (23-26.11.2004)

• Question 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. So that the data containing the error is 010 0100. These 7 bits contain both the data and parity bits.
  2. What happens if some of the parity bits will change.
  3. How many parity bits are needed if there are 8, 16, 32, 64, 128, 256, 512, or 1024 data bits. How much is the increase in procents.
  4. Why is Hamming code not a good approach to secure LAN data transfers?
     
  
  
  
• Question 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. Is it possible for a process to know if the data was found in cache or not? Why?
  4. Does the application user (person) need to know if the data was found in cache or not? Why
  5. How can a user (programmer) influence the effectiveness of the cache memory?

   

• Question 3: Process
  1. What happens if the Ready-to-Run queue is empty? When can this be?
  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?

   

• Question 4: Process switch

  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?

   

• Question 5: [2 hwp] 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?

   

Use standard method for building and taking apart activation records, when implementing subroutines and functions. Take care, that all work registers (R0-R5) have the same value at the time of subroutine or function return as they were when the subroutine or function call was made.

---

Paivi.Kuuppelomaki@cs.helsinki.fi