CS 352: Project

    Assigned: Friday, April 9, 2010
    Due: Thursday, April 29, 2010 at the beginning of class

    Objective: Build a Level 1 data cache simulator and run a set of experiments using your simulator.

    Authorship: You must use the pair programming approach for this assignment, which requires actively working together on the assignment for 80 to 90% of the time. You may only spend 10 to 20% of working independently.

    Due dates:

    • 5pm on April 9 Choose a partner. Send email to upendra@cs.utexas.edu identifying your partner or requesting assistance to match you up with someone if you are having trouble finding someone.
    • 9:30am on April 29, 2010. Your code and written report are due. If you turn in the assignment late, BOTH partners must have the necessary number of slip days.


    Links:
    Specification | Source code | Testing | Report & Experiments | Turnin instructions | Output format



    Specification:

    1. You can write your program in either Java or C++ -- your choice. It must run on the CS department linux machines. For information on UTCS Java, see http://www.cs.utexas.edu/facilities/documentation/java/. For information on UTCS C++ see http://www.cs.utexas.edu/facilities/faq/programming/#83

    2. Your Level 1 Data Cache Simulator should accept the following command-line options:
      -c <capacity> with <capacity> in KB: 4, 8, 16, 32, or 64.
      -b <blocksize> with <blocksize> in bytes: 4, 8, 16, 32, 64, 128, 256, or 512.
      -a <associativity> where <associativity> is integer size of set: 1, 2, 4, 8, 16.

      The baseline configuration (i.e., the first one that you should test) is: capacity = 8K, blocksize = 16 bytes (i.e., 4 words), set associativity = 4 with one of the following commands (NOTE: the code we provide requires no spaces between the letter and number):
      • cache_sim -c8 -b16 -a4
      • java cache_sim -c8 -b16 -a4

    3. Additionally, your cache should have the following functionality:
      • write back (for write hits)
      • write allocate (for write misses) - read the cache line, modify it with the write, then mark it as dirty.
      • LRU replacement

    4. The input to the cache simulator will be a sequence of memory access traces, one per line, terminated by end of file. In the following format, with a leading 0 for loads and 1 for stores.
      • 0 <address>
      • 1 <address> <dataword>

      Each address will be the address of a 32-bit data word. The address and data are expressed in hexadecimal format.

    5. To support testing of your data cache simulator, you will implement a simple model of main memory. The capacity of the memory should be 16 MB (4 megawords). At simulator start-up time, initialize the contents of each word to be the word's address. For example, the 32-bit word that starts at byte 0x00001004 should be initialized to 0x00001004.

    6. The output of your program will consist of a set of statistics gathered during the simulation as well as the contents of the cache and memory at the end of the simulation. The format of the output is described in detail at the end of this document. You must use the code fragments available for download on the project web page http://userweb.cs.utexas.edu/users/mckinley/352/homework to print the output. This consistent output format is required for automate grading.

      We provide a framework below for both C++ and Java versions of the code to get you started. These files will help with input and output, so you can focus on cache simulation.

    7. Your program will be graded for correctness and design.

      Design: We expect to see well-chosen classes that reflect the application. Be sure that your method names and variable names reflect memory hierarchy terms. When done, anyone reading your code should have learned how a cache works. Towards that end, you should define constants such as "dirty".

      Correctness: You should create your own trace files to help you test and debug your cache configurations.

    8. Keep in mind these details
      1. You should initialize all of the cache locations to be 'invalid' and initialize all of the tag and data fields to zero.
      2. All of the parameters on the command line are base 10 numbers (e.g. 32, 64, 128, etc.)
      3. The addresses and data in the trace files are expressed as base 16 (hexadecimal) numbers. Note that these numbers might (or might not) have extra zeros in front... e.g. 00de2a vs. de2a.
      4. Read your input from 'stdin' and write your output to 'stdout'. (i.e., read from the terminal and write to the terminal)
      5. Use the unix shell's ability to redirect input and output to pull input from disk files and write output to disk files. For example:
        csh> cache_sim -c32 -b16 -a4 < test.trace > test.output
        NOTE: No spaces between the number and the letter, which the code we provide requires.
      6. Your output should be formatted as described below in Output format. You will print out the entire contents of the cache, and 1024 words of memory starting at address 0x003f7f00.
      7. We have provided the output code and a tool to check it (see testing). If you do not use the correct format, we will not grade your project.
      8. At the end of the trace, write all dirty blocks to the memory, so that the memory contains updated data. However, do not count them in "Number of Dirty Blocks Evicted From the Cache", since they have not really been evicted from the cache.



    Source code

      C++ Files: The following files can be used as a starting point for the project.
      • Makefile is the configuration file for building your project. You will probably need to make changes to it as your project evolves. Look in its comments for more details, or in the man page:
        	      $ man make
        	    
      • funcs.cc contains parseParams(), which helps you parse the command line parameters that are passed to your cache simulator. The command line options are:
        • -c = cache capacity
        • -b = blocksize
        • -a = associativity
        The parseParams function reads and parses these options; just call it with the appropriate variables. Remember to check the return value of the function as in main.cc.
      • main.cc is the top-level entry point for the project. It currently simply illustrates the use of parseParams() to parse the commandline.
      • funcs.h is the header file for funcs.cc
      • io.cc is sample code for reading the input trace format.

      Java:

      • cache_sim.java is the top level entry point for the project and contains the parseParams routine.
      • io.java contains routines for reading in data and writing out final cache statistics and contents. You should move these routines to your own classes and code.


    Testing your simulator

    We have provided a perl script that checks the formatting of your program's output and sample files.

    • checker.pl
    • We will use a variation of this script for grading. You should verify that it can parse your output correctly. We will not grade your project if we cannot parse your output. To run this program, download it and then change the file to executable. You can do this using chmod +x checker. Then use checker outputfile to check the output file.
    • Input file: sample_input_file.trace
    • Output file from above for configuration -c4 -b32 -a4 : sample_output_file.txt
    • File containing input traces for test cases #1-#4: smalltraces.txt
    • File containing main address trace: cs352.trace

    We are not providing the solutions to the four small test cases, but the test cases are small enough that you can hand calculate the results. Once your program is complete and passes the simple test cases, you can use the trace file from the compress benchmark (cs352.trace) for a "stress test" and for the experiments as described below.


    Report and Experiments

    After you test your cache simulator, you will use it as a tool to evaluate several cache configurations, to determine which one results in the lowest miss rate for the compress benchmark. The trace file for the compress benchmark in cs352.trace. You will write a 3-page report summarizing the design of your simulator and your experimental results. Your report and experiments should be structured as followed.

      1. Describe your experiences in the development of your code.
        • How did you structure your code and why?
        • What were the challenges in simulating a cache and memory?
        • Describe how you partitioned the 32 bit addresses into tag, index, and offset, when given a particular configuration.
      2. Rather than running all possible combinations of cache parameters, you will develop a plan that tests a partial set of combinations. Describe your plan and justify it.
      3. Provide a table of the statistics you collected from each of the five best configurations in rank order (best first) and specify the criteria for choosing the best.
      4. Discuss factors we did not consider in these experiments that architects must consider before selecting a specific cache configuration, and how these factors would influence the selection. You should consider potential cache access time (i.e., hit time), the die area that the cache might occupy, etc.



    Turn in instructions:
    You will turn in code and your report electronically and you will also turn in one hardcopy of your report in class. Only one of the two partners should electronically submit the project.

    Electronic
    1. Your last submission to the turn in directory determines the 'timestamp' of your submission.
    2. All of your source files, header files, and makefiles (if used). All of these files must be well documented with comments.
    3. If your submission is in C++, then the command "make" should build your executable binary. If your submission is in Java, then "javac cache_sim.java" should build your java binary.
    4. A compiled binary that executes on the departmental linux machines. The binary file must be named "cache_sim" and accept command line arguments in the exact form specified above.
    5. Five output files: The output from simulating test cases 1 through 4, and the stress test (cs352.trace) using the baseline configuration)
    6. An electronic copy of your report (in either ASCII text-file format, named 'report.txt' or PDF format, named 'report.pdf')
    7. You will use the following command to turn in your files electronically:
      csh> turnin -submit upendra cs352-project <filename>
    8. To verify that your files have been successfully submitted, use:
      csh> turnin --list upendra cs352-project

    Hardcopy turned in at beginning of class.
    1. Your three page report as specified above.
    2. One page with the statistics for test cases 1,2,3,4 and the stress testcase
    3. A printout of your source files, header files, and makefiles (if used) that you turned in electronically.
    4. A printout of the cache contents and the 1024 words of memory contents for ONLY Test Case 3



    Format of Output:
    Key to the following description:
    base of output: (10 = decimal and 16 refers to hex)
    rate should be a real number, with 4 digits of accuracy
    0/1: print either 1 for True or 0 for False

    ------------------------------------------------------------------------------
    STATISTICS:
    Misses: <Total (10)> <DataReads (10)> <DataWrites (10) >
    Miss Rate: <for total> <for dataread> <for datawrites>
    Number of Dirty Blocks Evicted From the Cache: <Total (10)>

    CACHE CONTENTS:
    Set_Number Valid Tag Dirty Word0 Word1 ...
    <base 16> 0/1 <16> 0/1 <16> <16>...
    ...

    MAIN MEMORY: {print 1024 words of memory starting at address address 0x003f7f00. Print 8 words of memory per line, all values should be base 16}

    <address of word0> <word0> <word1> <word2> ... <word7>
    <address of word8> <word8> <word9> <word10> ... <word15>
    ...
    <address of word1016> <word1016> <word1017> <word1018> ... <word1023>