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. A processor supports byte-addressable memory with a 26-bit address space. The processor is connected to memory via a 64-bit data bus. Design an eight-way interleaved memory that supports the full address space of the processor. Use only 512KB (2^19 * 1 byte) memory chips. Draw a diagram of your memory system, with chip enables, write enables, data bus, and address bus. On your diagram, label memory locations 0 through 31. How big is this memory? Give a breakdown of each field in a memory address. (Do not worry about the logic for unaligned accesses.)



 
3.   The figure below illustrates the logic and memory to support 512 MB (byte addressable) of physical memory, supporting unaligned accesses.  The ISA contains LDByte, LDHalfWord, LDWord, STByte , STHalfWord and STWord instructions, where a Word is 32 bits. Bit 28 serves as a chip enable (active high). If this bit is high the data of the memory is loaded on the bus, otherwise the output of the memory chip floats(tri-stated). Assume that the rotator for read is a right rotator, and the rotator for write is a left rotator. Also assume that the MDR is already loaded in a previous state for a write.(You can put all zeros for the load signal.)  

 




   

1. What signal should be used for the select signal of the mux (in front of the MDR) and the enable signal of the tristate buffer (connected between the data bus and the rotator)?
2. Construct the truth table to implement the LOGIC block, having inputs PHYS_ADDR[1:0], SIZE, R/W, 1st or 2nd access, and the outputs shown in the above figure. Assume that the value of SIZE can be Byte (00), HalfWord (01), and Word (10). Clearly explain what function each output serves.


 
4. This problem has been moved to Problem Set 4
   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 2
   Frame 4	empty
   Frame 5	Page 0
   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.)

   References (to pages): 0, 13, 5, 2, 14, 14, 13, 6, 6, 13, 15, 14, 15, 13, 4, 3.

   At the end of this sequence, what three entries are contained in the TLB? What are the contents of the 8 physical frames?

5. 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?
6. 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.


 

7. This problem has been moved to Problem Set 4
   Consider a processor that supports a 9-bit physical address space with byte addressable memory. We would like the processor to support a virtual memory system. The features of the virtual memory system are

   
       Virtual Memory Size : 4 Kbytes (12 bit address-space)
       Page Size           : 32 bytes
       PTBR                : 0x380
       SBR                 : 0x1E0
      
   

   The virtual memory system is similar to the VAX in which virtual memory is divided into System Space and User Space. The system page table remains resident in physical memory. Each PTE contains, in addition to the PFN, a Valid bit, a modified bit and 2 bits for access control. The format of the PTE entry is
   

   Valid

   Modified

   Access Control

   PFN

   (Valid bit is the most significant bit of the PTE and the PFN's the least significant.)
   
   
   1. How many virtual pages does the system acomadte?
   2. What is the size of the PFN? How big is the PTE?
   3. How many bytes are required for storing the entire page table? How many pages does this correspond to?
      Since the page table can occupy a significant portion of the the physical memory, this system uses a 2 level address translation scheme, by storing the Page Table's in virtual memory(Similar to the VAX).
   4. Given the virtual address 0x7AC what is the Physical address? To help you, the following table shows the contents of the physical memory that you may need to do the translation :

      Address Data x1F8 xBA x1F9 xBB x1FA xBC x1FB xBD x1FC xBE x1FD xB8 x1FE xB7 x1FF xB6

      Address Data x118 x81 x119 x72 x11A x65 x11B x34 x11C x97 x11D x83 x11E xC6 x11F xB2

   
   
8. This problem has been moved to Problem Set 4
   The virtual address of variable x is x3456789A. Using the VAX's virtual memory architecture, find the physical address of x.

   Remember that in VAX each Vitual Adress consists of 
   
   2 bits to specify the Address Space 
   21 bits to specify Virtual Page Number
   9 bits to specify the byte on the page 
   

   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:
   • What virtual page of P0 Space is x on?
   • What is VA of the PTE of the page containing x?
   • What virtual page of System Space is this PTE on?
   • What is the PA of the PTE of this page of System Space?
   • What is the PA of the PTE of the page containing x?