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
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.
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?
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.
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
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?
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
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
An instruction is said to generate a page fault if a page fault occurs
at any time during the processing of that instruction.
(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
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
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.
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
8KB page size
3 levels of access (similar to VAX architecture discussed in class):
4 privilege levels (again similar to VAX architecture discussed in class):
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.
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:
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?