378 Homework 8

Due Date: Monday, December 7 by the start of class

Well, for the final assignment, we are back to programming and electronic turnin. But, I've decided to have some (small) amount of mercy, and it won't be in assembly language. That's right folks, the final assignment should be written in C. For each source code file that you turn in, please put your name in a comment at the top of the file.

For this assignment, you'll be implementing a simulator that models the memory components of a computer system. You should build your implementation of the simulator on the instructional Alpha machines. There are two C compilers on the Alpha: /usr/bin/cc and /usr/local/bin/gcc, either one is fine. There are two debuggers available on the Alpha, /usr/bin/dbx and /usr/local/bin/gdb. If you choose gcc as your compiler, I highly recommend using gdb as your debugger. When you use turnin, you should submit the source code for your simulator, as well as the compiled version so that I don't have to build it.

Your program will simulate all the major components of the virtual memory system: the instruction cache, the data cache, the TLB, the operating system page tables, and the paging file. Further detail about how to simulate each of these components is provided below.

The Trace File

As input, your simulator will read in an address trace file named "trace.in". This file contains a list of addresses and operations, and this represents the memory reference behavior of a program running on the simulated machine. Each reference is categorized as either a read or a write. The format of the trace file is: one entry per line, with an address category (i = instruction and d = data), a single space, an operation field (r = read and w = write), a single space, and finally an address field (the ASCII decimal representation of the address being referenced).

To illustrate, here is a very short sample trace file that contains only 4 references: 

i r 440
d w 410
i r 76
d r 348
The first line says that the instruction at address 440 was read, and second line says that the data at address 410 was written. The values read or written at these addresses are NOT contained in trace file, since they are irrelevant for simulating the virtual memory system.

Simulating the Caches

You should have two caches, one for data and one for instructions. Both caches will have the same structure. Assume that each cache contains 16 entries and is 4-way set associative. The replacement policy for your caches should be LRU. You may implement the LRU scheme however you choose. During the simulation, you should record the # of accesses to each Cache, as well as the # of hits.

Output from your simulator

At the end of the simulation, you should print out the miss rate (as a percentage) for both the Instruction Cache and the Data Cache. Your simulator, when invoked with the "-verbose" option, should print out the contents of both the Instruction Cache and the Data Cache when the simulation ends.

Simulating the TLB

The TLB structure that you will simulate is a split TLB. The page size for the simulated machine is 1KB. The instruction TLB (ITLB) will have 32 entries and is fully associative. The replacement policy you should implement for the ITLB is LRU. The data TLB (DTLB) will have 16 entries and be fully associative. You should use a random replacement policy for the DTLB. You should use the srandom() and random() functions from the standard C library to implement your random replacement policy, and you should use an initial seed value of 37982 (this requirement is needed so that everyone's DTLB will behave identically for testing purposes). Since random() returns an unsigned random value between 0 and 2^32-1, you should take that value modulo 16 to generate a random number between 0 and 15. During the simulation, you should record the # of accesses to each TLB, as well as the # of hits.

Output from your simulator

At the end of the simulation, you should print out the miss rate (as a percentage) for both the ITLB and the DTLB. Your simulator, when invoked with the "-verbose" option, should print out the contents of both the ITLB and the DTLB when the simulation ends.

Simulating the OS Page Tables

The page table structure that you will simulate is a linear page table (as opposed to the inverted page tables or the hierarchical page tables described in the book). Each page table entry should contain a valid bit, a physical page number, and a dirty bit. You should use an LRU replacement policy to simulate how main memory is managed. The size of main memory on the machine you are simulating is 64 pages. Initially, main memory should be empty (so your virtual memory system page freelist contains every physical page). Your page allocation policy should simply hand out the physical pages in order of increasing page number (starting at 0), until the freelist is empty. From that point on, all physical pages will be obtained by page replacements. In our simulation, pages will never be added back to the freelist since we're only simulating a single process and it never dies.

Output from your simulator

The output of your simulation for this component should be the total number of page faults. When your simulator is invoked with the "-verbose" option, it will print out the contents of all the valid entries in the page table when the simulation ends.

Simulating the Paging File

You do not have to model the actual placement of virtual pages on disk (a more accurate simulation would record the disk block number for all those entries in the page table where the valid bit is not set). Instead, you should simply keep track of the number of disk read and write operations that are needed to handle the page faults. You can assume that the disk block size matches the 1KB page size, so it only takes 1 disk read operation to load a 1KB page from disk.

Output from your simulator

When the simulation ends, you should print out the total number of disk read operations and the total number of disk write operations that were needed to handle all the page faults.

Extra Credit

For extra credit, implement your instruction cache using each of the following schemes (all caches should contain 16 instructions total):

Run your code on this input file for each cache structure. You must include a file called "extra.credit" with your turnin. If I do not see this file, you will not get credit for this. This file should show the results of each of these by cutting and pasting a run of your code (without the -verbose option) using each cache. So you will run your code 5 times and show me the results of each of these. If you do the extra credit, make sure the final version of your code that you turn in uses a 4-way set associative cache so that it runs properly when I am testing the rest of the homework!