Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 360N, Fall 2003
Problem Set 3
Due: 1 October 2003, before class
Yale N. Patt, Instructor
Santhosh Srinath, Danny Lynch, TAs

Instructions:
You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set returned to you.

  1. If the latency of a DRAM memory bank is 37 cycles, into how many banks would you interleave this memory in order to fully hide this latency when making sequential memory accesses?
  2. An ISA supports an 8-bit, byte-addressable virtual address space. The corresponding physical memory has only 128 bytes. Each page contains 16 bytes. A simple, one-level translation scheme is used and the page table resides in physical memory. The initial contents of the frames of physical memory are shown below.


    Frame 0 empty
    Frame 1 Page 13
    Frame 2 Page 5
    Frame 3 Page 10
    Frame 4 empty
    Frame 5 Page 1
    Frame 6 empty
    Frame 7 Page Table

    A three-entry Translation Lookaside Buffer that uses LRU replacement is added to this system. Initially, this TLB contains the entries for pages 0, 2, and 13. For the following sequence of references, put a circle around those that generate a TLB hit and put a rectangle around those that generate a page fault. What is the hit rate of the TLB for this sequence of references? (Note: LRU policy is used to select pages for replacement in physical memory.)

    Updated 29 October
    References (to pages): 13, 2, 14, 14, 13, 14, 6, 6, 13, 14, 15, 14, 15, 13, 4, 3.

    At the end of this sequence, what three entries are contained in the TLB?

  3. We have been referring to the LC-3b memory as 2^16 bytes of memory, byte-addressable. This is the memory that the user sees, and may bear no relationship to the actual physical memory. Suppose that the actual physical address space is 8K bytes, and our page size is 512 bytes. What is  the size of the PFN? Suppose we have a virtual memory system similar to the VAX in which virtual memory is divided into User Space (P0) and System Space and System Page Table remains resident in physical memory. System space includes trap vector table, interrupt vector table, operating system and supervisor stack as shown in Figure A.1 in Appendix A. If each PTE contained, in addition to the PFN, a Valid bit, a modified bit, and two bits of access control, how many bits of physical memory would be required to store the System Page Table?
  4. Let's say we added a virtual memory system to the LC-3b. Which instructions can possibly generate a page fault? What is the maximum number of page faults an instruction can possibly generate while it is being processed? Which instructions can possibly generate that maximum number of page faults?

    Assume that the virtual memory system added uses a one-level translation scheme and the page table is always resident in physical memory.

    An instruction is said to generate a page fault if a page fault occurs at any time during the processing of that instruction.

  5. (Hamacher, pg.255, question 5.20) 1024x1024 array of 32-bit numbers is to be "normalized" as follows. For each column the largest element is found and all elements of the column are divided by this maximum value.Assume that each page in the virtual memory consists of 4Kbytes and that 1Mbytes of the main memory are allocated for storing data during this computation. Suppose that it takes 40 ms to load a page from the disk to the main memory when a page fault occurs (assume that when we start, the main memory is empty ).
    a. How many page faults would occur if the elements of the array are stored in column order in the virtual memory?

    b. How many page faults would occur if the elements are stored in row order?

    c. Estimate the total time needed to perform this normalization for both arrangements a & b. Assume that it takes 2 ns to do a comparison, 20 ns to do a divide and 100 ns to do a load/store to memory.
     

  6. Suppose the processor from problem set 2 question 8 is updated to support a 28-bit address space with byte-addressable memory. Assume that user programs can make use of the whole 28-bit virtual address space. Using the physical memory developed in that problem, we would like to support virtual memory. The virtual memory will support the following features:
  7.         8KB page size
            3 levels of access (similar to VAX architecture discussed in class):
                    none (-)
                    read (R)
                    write (W)
            4 privilege levels (again similar to VAX architecture discussed in class):
                    user (U)
                    supervisor (S)
                    executive (E)
                    kernel (K)
            page replacement using a reference bit for each page
    How many pages are there in virtual memory? How many frames are there in physical memory? What is the minimum number of bits required to encode all the valid combinations of privilege levels and access levels? Show which access level/privilege level combinations are valid and which are invalid.

    Show a PTE for this memory, and specify the number of bits required for each field in the PTE. Finally, describe how a 28-bit virtual address is translated into a 26-bit physical address. 
     
     
  8. The virtual address of variable x is x3456789A. Using the VAX's virtual memory architecture, find the physical address of x.

    You will need to know the contents of P0BR: x8AC40000 and SBR: x000C8000.

    You will also need to know the contents of the following physical memory locations:

    x1EBA6EF0:    x80000A72
    x0022D958:    x800F5D37
    Some intermediate questions to help you:

  9.