CMSC 411 Fall 2004 Programming ProjectCache Organization and Performance EvaluationDue: December 3, 2004, 6:00PMIn this assignment, you will become familiar with how caches work and how to evaluate their perfor-mance. To achieve these goals, you will first build a cache simulator and validate its correctness. Then youwill use your cache simulator to study several different cache organizations and management policies asdiscussed in lecture and in Chapter 5 of Hennessy & Patterson.Section 1 will walk you through how to build the cache simulator, and Section 2 will specify the perfor-mance evaluation studies you will undertake using your simulator.1 Cache SimulatorIn the first part of this assignment, you will build a cache simulator. The type of simulator you will build isknown as a trace-driven simulator because it takes as input a trace of events, in this case memory references.The trace, which we will provide for you, was acquired on another machine. Once acquired, it can be usedto drive simulation studies. In this assignment, the memory reference events specified in the trace(s) wewill give you will be used by your simulator to drive the movement of data into and out of the cache, thussimulating its behavior.Your cache simulator will be configurable based on arguments given at the command line, and mustsupport the following functionality:Total cache sizeBlock sizeUnified vs. split I- and D-cachesAssociativityWrite back vs. write throughWrite allocate vs. write no allocate (see p. 402 in H & P)In addition to implementing the functionality listed above, your simulator must also collect and reportseveral statistics that will be used to verify the correctness of the simulator, and that will be used for perfor-mance evaluation later in the assignment. In particular, your simulator must track:Number of instruction referencesNumber of data referencesNumber of instruction missesNumber of data missesNumber of words fetched from memoryNumber of words copied back to memory11.1 FilesThe first thing you should do is copy the program files from the/afs/csic.umd.edu/users/als/411/fall04/Project/codedirectory on the Linuxlab clus-ter into your own local directory. Alternatively, the files can be downloaded from the class projects webpage. There are five program files in total, as indicated in the table below which lists the file names and ashort description of their contents. Note, there are also three other files, spice.trace, cc.trace,andtex.trace in the traces sub-directory under the Project directory on the Linuxlab cluster. Do not copythese files since they are very large. We will explain what to do with them later.File Name DescriptionMakefile Builds the simulator.main.c Top-level routines for driving the simulator.main.h Header file for main.c.cache.c Cache model.cache.h Header file for cache.c.The Makefile is a UNIX make file. Try typing make in the local directory where you’ve copied thefiles. This will build the simulator from the program files that have been provided, and will produce anexecutable called sim. Of course, the executable doesn’t do very much since the files we have given youare only a template for the simulator. However, you can use this make file to build your simulator as you addfunctionality. Be sure to update the make file if you have additional source files other than the four programfiles we’ve given you.The four program files, main.c, main.h, cache.c,andcache.h, contain a template for thesimulator written in C. These files contain many useful routines that will save you time (since you don’thave to write them yourself).main.c contains the top-level driver for the simulator. It has a front-end routine called parseargs()that parses command line arguments to allow configuring the cache model with all the different parametersspecified earlier. To see a list of valid command line arguments, try typing sim -h (after compiling thetemplate files). Note that your simulator code should interpret the four size parameters, block size, uni-fied cache size, instruction cache size, and data cache size, in units of bytes. main.c also contains atop-level simulator loop, called playtrace(), and a routine that parses lines from the trace file, calledreadtrace element(). For each trace element read, play trace() calls the cache model, via theroutine performaccess(), to simulate a single memory reference to the cache. While you are free tomodify main.c, you should be able to complete the assignment without making any modifications to thisfile.cache.c contains the cache model itself. There are three routines in this file which you should beable to use without modification. setcache param() is the cache model interface to the argumentparsing routine in main.c. It intercepts all the parameter requests and sets the proper parameter valueswhich have been declared as static globals in cache.c. delete and insert are deletion and inser-tion routines for a doubly linked list data structure, which we will explain below. dumpsettings()prints the cache configuration based on the configured parameters, and printstats() prints the statis-tics that you will gather. In addition to these five routines, there are three template functions which youwill have to write. initcache() is called once to build and initialize the cache model data structures.performaccess() is called once for each iteration of the simulator loop to simulate a single memoryreference to the cache. And flush() is called at the very end of the simulation to purge the cache of itscontents. Note that the simulation is not finished until all dirty cache lines (if there are any) are flushed outof the cache, and all statistics are updated as a result of such flushes.2main.h is self-explanatory. cache.h contains several constants for initializing and changing thecache configuration, and contains the data structures used to implement the cache model (we will explainthese in the next section). Finally, cache.h also contains a macro for computing the base-2 logarithm,called LOG2, which should become useful as you build the cache model.In addition to the five program files, there are also three trace files that you will use to drive yoursimulator. Their names are spice.trace, cc.trace,andtex.trace. These files are the resultof tracing the memory reference behavior of the spice circuit simulator, a C compiler, and the TeX textformatting program, respectively. They represent roughly 1 million memory references each. These filesare