Description
Overview
For this assignment, you are going to use C to implement a Virtual Address to Physical Address memory mapping using bit-level operators for the given scheme:
- Virtual Address 18 bits (9 bit VPN, 9 bit VPO)
- Physical Address 20 bits (11 bit PPN, 9 bit PPO)
You will be building a paged memory management system with three components, CPU, Cache, and Memory, where for a given virtual address, you will output the associated byte in the system memory.
Visual Representation (Simplified)
Details of the Implementation
The project handout consists of a tar archive that contains a directory and a series of files. Of these, you will be modifying caching.c and you have the option of creating a header file to use with it.
Your objective is to modify caching.c to provide an implementation for the TLB, a Page Table, and Memory Caching, along with Virtual Address to Physical Address translation.
The main memory will be provided for you in a supporting archive (libframesupport.a), which is described below. Since the virtual addresses and physical addresses are shorter than 32 bits in length, you will use the standard 32-bit int data type in C to represent them. You must use an integer (and bit-level operators) to do you work. Use masks and shifting to get these parts of the addresses you need to use at a given time.
The program input will be a series of virtual addresses. The input may be made directly when running the program by entering addresses in decimal at the prompt. You may also create testing files that consist of one address on each line, with -1 as the last address. When the program encounters a negative number, it will quit. This testing file may be read into the program using the Unix redirect in operator (demonstrated in the sample output section). Each line of input represents a virtual address that a program wants to read memory from.
For a given virtual memory address, you will first compute the physical address by first checking the
TLB. If the Physical Page Number (PPN) is in the TLB, then you can get it and then return the Physical Address (PA). Otherwise, if the data is unavailable, you will try to get the PPN from the page table using the VPN. When accessing the Page Table, you will need to check to see if the page has been loaded in to RAM and has an entry in the page table. If so, you can then update the TLB with the information and return the PA. If not, you will use a supporting library function to load the page into memory, after which you can update both the page table and the TLB with the PPN before returning the PA.
You must use the provided logging functions (described here and in the code) to document where you are getting your PPN (TLB, Page Table, or Page Fault Handler) and what the physical address is.
- TLB: You will be implementing a TLB to cache memory addresses. Implement it as a directmapped cache, which will initially be empty (i.e. all entries have valid set to 0), but you will update and use this data structure based on the memory addresses provided. For the TLB, you will use the first 5 bits of the VPN as the tag and the remaining 4 bits for the index. The data the TLB will hold are the most recently used PPNs (11-bits).
Virtual Address
- Page Table: You will be implementing a simple page table that is indexed by the VPN and consists of a valid bit and the PPN entry for the VPN index. If the data is not in the TLB, you will search the page table for the value. If you find the value in the page table, make sure to update your TLB with the information! If you do not find the value in the page table, then you will need to call the library function, load_frame(vpn), which will load the frame from memory and return the PPN where it is loaded. You will then update the page table AND the TLB with the information so the next time you search for it, it will be in both places. For this project, once you have loaded a frame, it will stay in memory. You will not have to remove anything from your page table.
Once you have computed the physical address, you will use this address to get your data. To do this, you will first check the memory cache for the data. If it is not there, you will need to get it directly from main memory. Just as computing the address, you must use the logging functions to document where your data came from (Cache or Memory).
- Cache – The first 13 bits of the physical address will be used for the tag. The next 5 bits will be for the index and the last 2 bits is the offset. Your cache will hold 4 bytes of data; use the last two bits of the physical address to get the correct byte to return.
Physical Address
PPN PPO
Tag Index Byte
Offset
- Just like the TLB, this cache should initially have everything marked as invalid. The data will be stored little endian, meaning if the data in the cache is 0x12345678 and the offset bits 1, you will be returning 0x56.
- This will be a two-way set associative cache, meaning each set has two possible entries. The added issue here is that when you put something into the cache, you have two possible location choices. So that we are all doing the same thing, our replacement algorithm is:
- If both entries are invalid, use the first one
- If one entry is valid and one is invalid, use the invalid one o If both entries are valid, use the oldest one
- Oldest entry: To figure out which entry is the oldest one, you should use a timestamp like approach, where you always replace the entry with the lowest timestamp.
Main Memory: The supporting library implements main memory via a function get_word(addr) which returns a 4-byte integer at address (addr &~0x3). For example, if you request the byte at address 0x101, you will get the 4 bytes starting at 0x100 (0x100, 0x101, 0x102, and 0x103). Be sure to update the cache if you have to get data from memory.
rting the Assignment
The starting tar file (project3.tar) has 5 files in it:
- h : This is the starting header file. It currently only contains some constant definitions you should use. Do not modify this code.
- c : This is the driver program implementation. Do not modify this code.
- c : This is the file you will edit. It already contains some stubs used by the driver to do the computations. You may write other functions as well. Put all of the code for your assignment in this single file.
- a : This is a static library that contains several functions needed to make the entire system work. You will be using get_word and load_frame functions.
- Makefile : This is a makefile that will make and clean your program. When you make it, you will get an executable called mem
You may add a header file if you like for your caching.c implementation.
Implementation Notes
- You must use an integer (and bit-level operators) to do your work. Use masks and shifting to get the parts of the address you need to use at a given time.
- You may implement the TLB, Page Table, and Cache however you want as long as it behaves correctly as a cache given the specification above.
