Lab Assignment L3: Understanding Cache Memories Solution

Goal



This lab will help you understand the impact that cache memories can have on the performance of your C programs. You will write a small C program that simulates the behavior of a cache memory. This is an individual project.




Introduction



A. How to Start the Cache Lab




To start your cache simulator, you will enter the following command. The options are described in Table 1.




./cachelab -m <m -s <s -e <e -b <b




Table 1. Options




Option Description




-m The size of address used in the cache (bit)

-s The number of index bits (S = 2s is the number of sets)

-e The number of line bits (E = 2e is the number of lines; associativity)




-b The size of block bits (B = 2b is the block size)




The simulator should run on Linux machine at cs.oswego.edu. The options are needed to build a cache; therefore, any missing options must return an error message. It does not have to find which option is missing, but just shows the syntax. Figure 1 shows how to build a direct mapped cache which has 64-bit address (thus m = 64). There are 16 sets (because s = 4), and the size of block is 16 bytes (thus b = 4). Note that direct-mapped cache has only 1 line per set (thus e = 0). The first command has not option for m, so returns an error message.




jwlee@altair~ cc lab3-jwlee.c -o cachelab







jwlee@altair~ ./cachelab -s 4 -e 0 -b 4




[Error] Please enter the following syntax: ./cachelab -m 4 -s 2 -e 0 -b 1 jwlee@altair~ ./cachelab -m 64 -s 4 -e 0 -b 4

M



. . .




Figure 1. Start the cache lab




B. How to Run the Cache Lab




Once the simulator starts, it will read an input file, which consists of cache addresses, for simplicity. Note that address is a hexadecimal. The input file name is given “address.txt.” Figure 2. Example of address.txt shows the address in the input file.




1

CSC322







jwlee@altair~ cat address.txt







10

20

22

18

E10

210

12

jwlee@altair~




Figure 2. Example of address.txt




The simulator reads each address and print out whether it is in a cache (hit) or not (miss), as shown in Figure 3. Cache hit prints H, whereas cache miss prints M. At the end of the output, it presents statistics: the number of hits and misses, miss rate, and total running time. In this lab, we assume that the cache hit time is 1 cycle, and miss penalty is 100 cycles. Note that the total running time is calculated in cycles.




jwlee@altair~ ./cachelab -m 64 -s 4 -e 0 -b 4







M
M



H



H



E10 M




M



M



[result] hits: 2 misses: 5 miss rate: 71% total running time: 507 cycle jwlee@altair~




Figure 3. Output after running the simulator




When a cache has to be replaced, the simulator uses LRU (least-recently used) policy. For the LRU policy, review the supplementary document.




Requirements



A. Developing environment




The program should be implemented in C only. The program in another language will not be graded. And the program should be executable in CS Linux machine. The program which cannot be compiled or executed in the CS Linux machine will be considered as incomplete program and will lose most points.




B. Handling exceptions




In this lab, we only care one exception – missing options. With a missing option, the cache cannot be built, therefore the simulator must catch this exception. The program, which fails to detect any missing options, will lose points.




C. Readability of source code







2

CSC322







The source code should be easy to read with good indentation and proper amount of comments.




D. Creating a readme file




The program should be submitted along with a readme file which has information such as your ID, name, etc. It also may provide a special instruction to run this program if exists. The source file and readme file should be named following the format below. Those who are not following the naming rule will also be taken off penalty points.







lab3-your_loginID.c




lab3-your_loginID_readme.txt




E. Submitting by due




The program should be submitted to Blackboard within the two weeks after the project is posted. Due is November 12. All submission by 11:59 PM on that day will be accepted without any penalty. On the due date, Blackboard may be suffering of too much network traffics and be unstable. There is no excuse about the issue, therefore you are strongly recommended to submit earlier than the due date.




Grading



A. Grading criteria




The lab is assigned 30 points, which is 15% of the final grade. It will be graded by evaluating the requirement. Any missing and unsatisfiable criteria will take off points. The tentative and brief criteria are below.




• Compilation:




• Execution:




5 points




21 points



• Error detection & others: 4 points




Late penalty



Late submission will take off 10% per day per week after due date. Thus, submission after 10 weeks will not be accepted in any circumstances.




Academic Integrity



Any dishonest behaviors will not be tolerated in this class. Any form of plagiarism and cheating will be dealt with according to the guidelines on the Academic Integrity Policy on - line at http://www.oswego.edu/integrity. For more information about university policies, see the following online catalog at:




http://catalog.oswego.edu/content.php?catoid=2&navoid=47#stat_inte_inte




Student who is against the honor code will not have any credits in this project.
















3