Homework 11

22C:122, Fall 1998

Due Monday Nov 16, 1998, in class

Douglas W. Jones
  1. Consider the following interface specification for an MMU:
    	MMU Device Interface Registers
                      _____________
            Control: |___________|_|
                                  |
                                 on/off
                      _____________
            Ptr:     |______o______| Page Table Register
                            |              _____________
                             ------------>|_____________|
    	                              |_____________|
                      _____________       |_______
            Status:  |______|xx|_|_|      |
                       page     | |
                       number   |  -- invalid address
                                 ---- illegal operation
    
            Page Table Entry Format:
                      _____________
                     |______|xx|_|_|
                       frame    | |
                       number   |  -- valid
                                 ---- write permission
    
    The official documentation given to the programmer says that virtual addresses are translated to physical addresses as follows:
    	physical_address( va, op )
    	    break va into
                  p -- the page number
                  b -- the byte in page
                break Ptr[p] into
                  f -- frame number
                  w -- write permission bit
                  v -- valid bit
                if (not v) or ((op = write) and (not w))
                    load Status register with
                      p -- the page number
                      (op = write) and (not w) -- illegal op
                      not v -- invalid address
                    trap request = true
                    return undefined value
                else
                    return physical address composed from
                      f -- frame number
                      b -- the byte in page
                endif
    
    The programmer's manual also notes that the implementation of the MMU is far more efficient than the above code suggests. Specifically, the MMU contains a translation lookaside buffer (TLB), an associative memory used to remember recently translated virtual addresses, so that the MMU only needs to go to physical memory (accessing the array pointed to by the Ptr register) when the required page table entry is not in the TLB.

    Assume that the TLB is built based on an associative memory with the following structure:

                          valid
                      write |  Frame
                  Page   _|_|___||_ in
                 ___||___ ___||___
       Line  ___|        |        |
       Number---|                 |
                |                 |
       Write ---|>                |
       strobe   |                 |
                |________|___  ___|
                    |    ____||____ out
             miss -       | |   ||
            write --------  |  Frame
            valid ----------   
    
    Also assume that there is a memory port available to the MMU. MMU transactions on this port preempt CPU initiated memory cycles.

    Part A: Propose, at the register transfer level, the logic of this MMU.

    Part B: Assuming that the MMU and CPU share a common clock, propose a control unit design for the MMU. This should normally idle in a "translating from TLB state" until the miss line goes high, and then it should go through whatever motions are required to deal with the miss.

  2. One problem with the above MMU design is that the page table required for a typical modern machine can be immense. A typical 32 bit machine will have a 20 bit page number and 12 bits giving the byte in the page (or 10 bits for word in page). A flat page table, such as that suggested above, would therefore require 1 million entries and it would typically occupy about 4 megabytes of memory.

    Part A: One solution to this problem is to note that few processes require more than a few hundred pages, so we add a register to the MMU specification called Max. This contains the size of the page table. Legal page numbers run from 0 to Max-1. Outline how you would use this idea; an informal description of the parts or data paths added to your solution to problem 1-A is a sufficient answer to this question.

    Part B: Another solution to this problem is to break the page table into segments, so the virtual address contains 3 fields, 10 bits to specify segment number, 10 bits to specify page in segment, and 12 bits to specify word in page. The Ptr register now points to the segment table, an array of 1024 entries. Each segment table entry contains a valid bit and the physical address of a segment of the page table. Page table entries are as before. For a typical application, most entries in the segment table will be marked as invalid. Outline how you would use this idea; an informal description of the parts or data paths added to your solution to problem 1-A and the changes to the control unit would be a sufficient answer to this question.