Fall 1997, CDA4101, Assignment 5

Due Wednesday 12/3 at the start of class

You are to write a program in Ada, C, C++, Java, Pascal, PC Assembler, or VAX Assembler that simulates a 2-way set-associative cache, using the LRU page replacement policy. Do not use Perl, Awk, Visual Basic, COBOL, Lisp, Prolog, SmallTalk, RPG, Lotus Script, Visual FoxPro, etc.

You may assume that the memory size of the computer is 1K, the block size is 4 bytes, the cache will have 32 slots, and each slot can hold two different entries.

• Addresses will be in the range from 0000000000 to 1111111111
• Cache slots will be in the range 00000 to 11111
• Entry numbers will be in the range 0 to 1

At a later date, I will supply an input file consisting of 10-bit addresses, one per line. The file will have a format like this:

0101001010
1100100101
0001101001
1111011010

You will read each line and determine if the address is in the cache.

The above addresses would have the following tag and slot

Address	Tag	Slot
0101001010	010	10010
1100100101	110	01001
0001101001	000	11010
1111011010	111	10110

Here is what the output should be:

• For each address, you will print the address and its slot and tag numbers. Print the slot and tag numbers in decimal, print the address in binary.
• If the address is in the cache then print out the slot and entry where its block is located. Print the slot and entry numbers in decimal.
• If the address is not in the cache then print the slot and entry where its block will go in the cache. Also print the starting address of the block to be loaded from memory. Print the entry and slot numbers in decimal, print the address in binary.

An example of the output for the above addresses might be

0101001010 : Slot 18 Tag 2 is in Slot 18 Entry 0
1100100101 : Slot 9 Tag 6 will be loaded into Slot 9 Entry 1 from address 1100100100
0001101001 : Slot 26 Tag 0 will be loaded into Slot 26 Entry 0 from address 0001101000
1111011010 : Slot 22 Tag 7 is in Slot 22 Entry 1

Of course, whether or not the address is in the cache, and which entry it is in will depend on the state of the cache.

For the page replacement policy use LRU.