Computer Organisation I

Exercise 4, week 17, Tuesday 20.4.

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. Alternatively to bringing the diskette, you can store your programs to the fs file server.

• Question 1: Hamming code
  Return the answer to this question day before your meeting! This answer will grant you one point equal to the points of the course exam.

  Hamming code is the simplest of the error-correcting codes.

  1. Create the Hamming coded bit sequence to store 4 data bits 1001. How many check bits do you need (How long syndrome do you need)? How can you check that the bits have not changed?
  2. Does the Hamming coded bit sequence 100 1101 (4 data bits and 3 check bits, bits are numbered from the right) contain any errors? If so, where and what is the error and how can you fix it?
  3. What about the coded bit sequence 100 1100? As you may notice there is one inverted bit when combared with the sequence in b). How does the Hamming code correct this one?

  Write your answer to a plain text file, which you must then send to the course assistant using the web-page http://db.cs.helsinki.fi/~tuohinie/tito/ .

  The web-page asks first you to choose your small group. Then you have to write your name and upload the text file containing your report.

  You have to return the answer at the latest 24 hours before the small group session's starting time. A late delivery is not possible.

  ---

   

• Question 2: Hamming code for longer bit sequences
  1. Please create the Hamming coded bit sequence for the 16 data bits 01010011 01010101? (The 16 data bits do not contain the check bit) Please explain your solution.
  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?

   

• Question 3: 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

   

• Question 4: 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 5: 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 6: Table as a parameter to a subroutine.

  Define a table Taulu[0..5] that contains six items in the main program. Implement the following functionality in ttk-91 symbolic assembler language and execute your program in koksi emulator.

  1. Write a subroutine Init(Arr, Dim, Val). It initializes the parameter Arr by storing to each item Arr[i] the sum Val+i+1000. Parameter Arr is the table to be initialized, Dim is the number of the items in the table and Val is an integer value. Arr is a reference parameter. Dim and Val are value parameters.
     Please notice that the usage of a table reference parameter is a bit more complex, since you cannot use in the subroutine the reference format @Arr(R1), but need to calculate the address yourself. The table has to be passed as a reference parameter, because we need to change the content of the table in the subroutine.
  2. In the main program, initialize the table Taulu using the subroutine Init (Val = 100).
  3. Also in the main program, print the value and address of item Taulu[4].
  Please implement the subroutine call systematically following the guidelines presented in the Finnish material (slides 14-18 of lecture 4).

  ---

  Tiina.Niklander@cs.helsinki.fi