Project 1: Cache Design
Problem description:
Given an instruction set architecture (ISA) with 32 bit address for code and data. An implementation of the ISA has a 32K-byte instruction cache. The line size of the cache is 64 bytes. Suppose the cache uses a random replacement policy if there is a conflict miss. Now, assuming that the addresses of the instruction for a given program are distributed normally with mean value of ¦Ì and a standard deviation of ¦Ò, i.e. a normal distribution N(¦Ì,¦Ò). Let LA = ¦Ì-6¦Ò >0 and HA= ¦Ì+6¦Ò. Suppose an address smaller than LA will be set to LA and an address larger than HA will be set to HA. Now, you are asked to write some programs to perform the following tasks:
1. Write a program to generate 109 instruction addresses with a distribution of N(228, 10240). The sequence of instruction addresses represents the order of the instructions executed. Instruction addresses can only be integers.
2. Write a program to calculate (a). compulsory miss rate, (b). capacity miss rate, and (c). conflict miss rate for direct map, two-way, and four-way set associative cache, respectively, using the instruction addresses generated in step 1.
3. Suppose the cache miss penalty is 200 cycles and the cache hit time
is 1 cycle. Calculate the average access time per instruction for a two-way set associative cache.
4. Repeat steps 1~3 for N(228, 2560) and N(228, 20480).
5. Repeat steps 1~4 for a cache with a size of 64K bytes, 128K bytes,
and 256K bytes, respectively.
6. Repeat steps 1~3 for a two-way set associative cache with a victim cache (buffer) of 4 lines. Suppose the victim cache is fully associative. Note that a random replacement policy is always used if there is a conflict miss.
Outputs:
1. Make a probability density function (PDF) graph for the addresses generated based on N(228, 10240).
2. Draw a graph for the miss rates calculated in step 2 for each combination of address distribution and cache size.
3. Draw a graph for the results computed for step 3 both with and without a victim cache for all combinations of address distributions and cache sizes.
4. If you can do more experiments other than those asked here, you will obtain some bonus points. Be mentioning this in the report.
5. Write a decent report consisting of following sections:
A. A cover page that consists of the course name, project title, your
department name, your name, student ID number, your instructor¡¯s name, and date.
B. Abstract
C. Problem Description
D. Methods
For generating addresses based on a given distribution. For calculating compulsory, capacity, and conflict misses. For others.
E.
Results and Discussion
Present experimental results.
Analyze the data obtained above and make a summary about your analysis. Carry out a discussion and make a suggestion for how to improve the average instruction access time.
F. Conclusion
6. Submit your report and source code separately to the course portal on time.