Assignment 11, due May 3

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: In the final machine problem, the prologue for the trap handler saves all of the registers in a trap save area, and the epilogue restores all of them. Within the handler, the saved registers represent the state of the user's computation. Within the handler, R2 points to the trap save area, so the instruction LOAD R3,R2,svPC, for example, will load the saved program counter into R3.

   a) Write code to fetch the instruction halfword that caused the trap into R4, assuming that the saved program counter has been loaded into R3 using the instruction given above. (0.4 points)

   b) Write code to check to see if the instruction that caused the trap (already in R4) was the LIW instruction. Note that this would be as easy as a simple CMPI instruction except that there is a 4-bit destination register field in the instruction halfword. (0.4 points)

   c) Suppose you wanted to call PUTHEX from within the trap service routine. What is the correct value of ARSIZE to use in the calling sequence? (0.4 points)

   d) Knowing that your trap service routine might call PUTAT, PUTHEX and PUTS, how can you go about figuring out how much extra space to allocate in the register save area beyond the minimum reqsuired to save the registers? (0.4 points)

   e) The built-in trap handler in the Hawk monitor outputs one more register than the assignment requires for your own instruction trap handler. What is this extra register and why don't you need to output it for the instruction trap handler? (Hint: See Chapter 14 of the notes, which you are expected to have read for this week.) (0.4 points)

2. Background: Computer science theory says that sorting an array of n elements takes O(n log n) time. As a result, if you plot the time taken to sort versus the array size on semi-log graph paper (that is, on graph paper with a linear scale for time and an logarithmic scale for the array size), you should get a straight line.

   a) Sketch an appropriate semi-log graph layour for showing the time taken to sort n elements, with time units (of unknown size) on the appropriate axis and memory size in steps from 8 to 1024 kilobytes, with each step being twice the size of the previous step (8, 16, 32, 64, etc). (0.3 point)

   b) Assume your machine has just one level of cache (an oversimplification on most modern machines) with a capacity of 64 kilobytes. Imagine the effect of this on an experimental study of sorting algorithms as you vary the size of the array being sorted from 8 kilobytes to 1024 kilobytes. Draw the approximate curve you would expect to see on the semi-log graph you drew for part a. (0.3 point)

   Note: No matter what the hardware, it will always take longer to sort a larger array. Therefore, in all cases, run-time will always increase monotonically with the size of the set being sorted.

3. A Question: What is the difference between a write-through cache and a write-back cache? (0.4 point)