Assignment 12, Solutions

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)

           MACRO   MULU r
   	  LIS     R1,4
   	  LOADS   r,R1
           ENDMAC
   

   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)

   The MMU trap handler would decode it by examining the TMA register and noting that TMA=4.

   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)

   The trap handler first needs to know what registers were specified. This means it needs to examine the destination register field of the instruction that caused the trap. Given that the register save area includes the saved value of PC, we can get this by

   instr = M[ translate( savedPC ) ]

   now we can check that instr.opcode is LOADS (this could have been done in 1 b), and we can extract the destination register

   rd = instr & 0xF

   Given that the saved registers are addressable as an array, the particular registers we need are

   multiplier = lowresult = savedR[ rd ]
   multiplicand = highresult = savedR[ rd + 1 ]

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)

   When the program (probably the operating system) changes the contents of the MMU, it expects the contents of the corresponding memory locations to change. Thus, for the example given, once the program changes the mapping of address x, it expects a load from x to give a different value than it gave before.

   In arrangement (i), where the cache works with physical addresses, this will happen naturally. In arrangement (ii), where the cache works with virtual addresses, if the cache is not cleared, it will continue to report the old value for x after a change to the MMU. Thus, arrangement ii requires that the cache be cleared after any change to the MMU.

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)

   Do not cache device registers. Consider what would happen if the keyboard input status register was cached.

   while (not keyboardinputstatus.ready) do nothing;

   If the register was cached, the cache would hold the old copy of the value, the polling loop would loop forever, and any change to the ready bit would never be visible to the CPU.

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)

   Part (i) of the rule will fail in scanning the string ()) The inner () causes a recursive call that ends normally, while the final ) causes a return to the main program. It never finds the null beyond the end of the string.

   Part (ii) of the rule will fail in scanning the string (() The inner () causes a recursive call that ends normally, while the initial ( causes a recursive call that returns when it encounters a null where it expected an end paren.

   As a result, if the interpreter is modified to check for conformance to these rules, all strings of unbalanced parentheses will be detected.