Assignment 12, due Dec 3

Always write your name legibly as it appears on your University ID and on the class list!

Note, only the top 10 homework scores will be counted toward the final grade, but it would not be wise to cease doing homework just because you have 10 strong scores. All material covered in the homework is liable to be covered in exams, and the best way to study it is to work on the homework.

Homework

1. Background: Suppose the Hawk machine had no undefined instructions, but you still wanted to create a virtual machine. One approach would be to use the memory management unit to trap some range of addresses, for example, addresses in page zero of the memory.

   We could, for example, write a trap handler that decodes a LOADS from memory address 4 as a register-to-register multiply instruction. Address 8 might be used for division, etc. The index register for LOADS holds the address, but we can use the destination register as an operand register. So, for example, the instruction sequence LIS R1,4 followed by LOADS R5,R1 could mean "multiply R5 by R6 and put the 64-bit product in registers R5 and R6."

   You may need to assume that there is a page table in RAM, and you may need to assume that there is a software function, TRANSLATE that, when called with a virtual address in R3, returns the corresponding physical address.

   a) Write a MULU macro that a user could use as if it was a multiply instruction, so that MULU R5 would mean "multiply R5 by R6 and put the 64-bit product in registers R5 and R6. (0.5 points)

   b) Which trap handler would decode this multiply instruction and how would the handler for this trap determine if it should perform a multiply or some other operation. (0.5 points)

   c) Describe how the handler would find the memory locations holding the multiplier and multiplicand. To solve this problem, you will have to understand the Hawk trap mechanisms fairly well, and you may need to make assumptions about virtual address translation. This is not a programming problem -- a concise easy to read description would be a better solution than Hawk code. (0.5 points)

2. Background: There are two possible relationships between a cache memory and a memory management unit. Either (i) the cache works in terms of physical memory addresses (it is between the MMU and main memory) or (ii) it works in terms of virtual addresses (it is between the CPU and the MMU).

   Consider the consequences of the following change to the MMU: Prior to the change, virtual memory address x maps to physical address a. After the change, virtual memory address x maps to physical address b.

   A problem: Which one of the two relationships between cache and MMU given above requires that the cache be cleared before any further use of the cache? Give an example illustrating the problems that would occur if it was not cleared. (0.5 points)

3. Background: Some MMU designs include one bit for each page of memory that indicates if it is legal to cache the corresponding data. Caches attached to such a system always declare a miss if this bit is set for the current memory address.

   A problem: Give an example of a physical address that should not be cached. Give an example and explain what could happen if that address were cached. Recall that not all physical addresses correspond to RAM. You might want to consider the effect of using a cache on ROM or I/O device registers. (0.5 points)

4. Background: Consider the sample solution distributed for machine problems 4 and 5. These use recursion to handle parenthesized sections of the command string. Consider the following rule: (i) If the interpreter was called from the main program, it should return because it encountered a null. (ii) If the interpreter was called recursively, it should return because it encountered an end paren.

   A Problem: Does this rule suffice to detect all possible unbalanced parenthesis strings? Justify your answer by answering the following: If part (i) of the rule fails, what was the nature of the error? If part (ii) of the rule fails, what was the nature of the error? (0.5 points)