Visualization of Cache Performance

Leon James Derman

Abstract

A system is presented that can be used to visualize exactly where cache misses are occurring and what their cost is. The system takes an instruction trace, the (high-level) specification of the memory hierarchy and simulates cache miss penalties. Finally, it presents the results of the simulation to the user. Information presented to the user includes the cache level which services a given request, the penalty for any misses, classification of misses as compulsary, capacity or conflict, and a visualization of locality that the given code trace exhibits. The user may interactively modify various characteristics of the memory hierarchy to see how performance might be improved.

1 INTRODUCTION

A fundamental problem with computer performance today arises from the gap between processor and main memory cycle times. This gap can cause huge stalls in the pipeline as instructions wait for cache misses to be serviced. Use of multiple ports, pipelining and various other optimization techniques within the cache architecture can help to improve cache performance. However, caches depend upon a program to exhibit at least some temporal and spatial locality. Programs that are not well behaved can often be improved by slight modifications to the code. However, as the memory hierarchy of a system becomes more complex, it is increasingly difficult to pinpoint exactly what portion of the code should be modified, and what effect changes in the memory hierarchy may have on performance.

For this project, I shall present a system, which I shall henceforth refer to as Cache Performance Visualization (CPV), that can be used to visualize exactly where cache miss penalties are occurring and what their cost is in terms of the level that services the request. This system shall be capable of taking an instruction trace, the (high-level) specification of the memory hierarchy, simulating cache miss penalties on this trace, and then presenting this information to the user in a useful fashion. This should aid in ones understanding of a program’s interaction with the cache in the following two ways: by allowing one to see the effect of modifying the memory hierarchy on cache penalties for a given piece of code, and also by enabling one to see the impact of modifying a given piece of code while keeping the memory hierarchy constant.

In order to simulate a memory hierarchy with multiple levels of cache, I shall enable the user to specify the memory hierarchy in a memory hierarchy specification file and/or interactively through the systems X Windows interface. The memory hierarchy specification file shall include information like the number of levels of cache, the size of each level of cache and the penalty for cache misses at each level. I intend to use tools that are already readily available, such as the cache simulator dineroIV [1], for portions of the model. What I shall be achieving with this tool is the simulation of multiple levels of cache, the introduction of penalty time (i.e. applying weight to which level of cache must service a miss), and an intuitive interface with which to present the results.

2 RELATED WORK

Much work has been directed towards the problem of understanding and effectively modeling and building memory hierarchies - for without good cache performance, it simply does not matter how innovative your instruction pipeline is. Lebeck [2] describes a tool called CPROF which can be used to identify common cache usage problems in an arbitrary program. He then goes on to present a “cookbook” of program transformations, such as array merging, padding and structure alignment, loop fusion and blocking. The CPROF program can identify cache misses at the source level - it gleans information from the symbol table. At the University of Wisconsin, the Wisconsin Architectural Research Tool Set (WARTS) project [3] has developed many tools that are usefull when evaluating computer performance. One such tool, called QPT can create program traces - a useful tool for generating input for my cache simulator. Kanbier discusses the use of a cache visualization tool that he and his collegues developed [4]. This tool, which is called CVT, allows the user to visualize cache behavior of selected code sections rather than identifying critical code sections. The functionality of this program is similar to that of the system that I am developing in terms of the user interface. However, there are some important differences in terms of the information that is calculated (gleaned from simulation) and presented to the user. In particular, Kanbier’s CVT tool simulates a single level of cache. Whereas CPV allows one to simulate the complete memory hierarchy by supporting multiple levels of cache. Crucial to this feature is the ability to detect and present to the user what level of cache services a given request. The CPV system presents this information to the user. Phalke presents to the reader a great method of cache analysis [5] in which the concept that high compression implies good predictability is exploited. Phalke goes on to point shortcomings of various statistical methods, such as frequency counting. Grimsrud [6] outlines a method of using locality as a visualiztion tool. In this paper he defines a function which represents the probability that the next occurrence of an access to an address a certain number of words away from the current location occurs with a given temporal distance. Grimsrud then goes on to show how this function can be used to create 3D plots which one can use to tune the given program.

3 PROGRAM SPECIFICS

This program is based upon the dineroIV [1] cache simulator developed by Edler and Hill. DineroIV can simulate a wide range of multi-level memory hierarchies. It is capable of reading in memory traces in a number of different formats. The user may specify cache associativity, replacement algorithm (LRU, FIFO, RANDOM), fetch policy, write allocate policy, write back policy, and so on. DineroIV simulates a memory hierarchy which consists of one or more levels of cache connected as one or more trees. Memory references are read from the given input trace file and handed to the appropriate top-level cache. All misses then filter down the memory hierarchy tree.

One problem with the simulator is that there is no feedback to the user indicating what level of cache services a given memory reference. This is precisely the problem that the Cache Performance Visualization solves. After the simulation is complete for a given input trace and a given memory hierarchy, the user can view a graph which shows, for each instruction, which cache level it was serviced by, with higher values indicating worse performance. Hence the user can use the feedback to determine which areas of code are triggering poor cache performance.

We shall now see an example of using the system.

4 SYSTEM IN USE

To start the system, type vizcp at the unix prompt. A single dialog box will pop up with several options. The buttons on this dialog box allow the user to specify the input trace file, specify the memory hierarchy, run the simulation on the current setup, view the simulation results and, of course, quit the program. I shall now elaborate on the use of these various options.

5 SPECIFYING AN INPUT TRACE FILE

When specifying the name of the input trace file, the user must type the name in the unix window from which she or he started the program. The program checks that a file with the entered name actually exists. If the given file can not be found, then the user is prompted to enter in another file name. The program is smart enough to detect that a given file is compressed (.gz or .Z) and uses the appropriate [gz]cat to pipe the file contents to the simulator. This program expects a dineroIII compatible memory trace.

6 SPECIFYING A MEMORY HIERARCHY

When the user clicks on the memory hierarchy button, another dialog pops up which allows the user to specify the cache configuration. The user may select various characteristics for the current cache, such as the size, block size, replacement policy, etc. The text on the right side of the dialog displays information about the current hierarchy.

When the program first starts, this area is blank - i.e. the user must specify at least one level of cache for the program to correctly function. As the user hits the Add button, with the level set to different values, the cache hierarchy is built. Each time the user clicks the Add button, the current options in the dialog are used to build a cache at the current level in the hierarchy. The user may quickly build a complete hierarchy by changing the level choice object and modifying the desired dialog fields. There is a hard-coded limit of five levels of cache - to change this, the program would have to be recompiled and small portions of the user interface would have to be changed. However, five levels of cache should be sufficient for most simulators. One thing to note is that the size and block size parameters must both be powers of two. One nice feature to add in the future would be to allow the user to specify the size and blocksize in both k-bytes and mega-bytes.

7 RUNNING THE SIMULATION

To execute the simulation, the user must first have specified a valid trace input file and specified the memory-hierarchy. The memory hierarchy can consists of as few as one cache and as many as five caches. After specifying the necessary information, as mentioned above, the user can simply click on the simulate button. A bunch of text will scroll by, indicating the progress of the simulation. When the simulation is complete, then clicking on the visualize button displays the results. The vizcp program simply runs a modified instance of the dineroIV simulator, telling it the memory hierarchy defined by the user. The dineroIV simulator passes information back to vizcp by the use of files. Two files are generated by the simulator. The first file, trace hist file.dat, contains information which specifies which level of cache serviced each memory reference and the type of memory reference (instruction or data). The second file, trace summary.dat, contains summary information for each level of cache, such as the total number of hits, misses, types of misses (compulsary, capacity, conflict), etc. The information contained within these two files may be viewed by clicking on the visualization button.

8 VIEWING THE SIMULATION RESULTS

When the user clicks on the visualization button, three windows pop up. The first new window contains a plot of cache servicing behavior of the simulation. Instruction references are colored blue, whereas data references are colored white. The higher the data point, the further down into the bowels of the memory hierarchy a given request filtered. So it is the areas of the plot which have the highest values values that are the most useful to observe. The user may zoom in and move around in this window by either holding the middle or right mouse buttons and moving the mouse left or right or by sliding the zoom and position sliders in the viz control window.

When the plot is initially displayed, the viewer is positioned so that all data points are contained within the window. For a simulation with more than a hundred instructions (which I imagine describes most simulations) this causes the data points to bunch up and form solid shapes. To see the detail, the user must zoom into the plot. One of the other windows which is currently displayed, shows the summary information for one level of cache. The user may select another cache to view by changing the value of the choice object.

9 FUTURE WORK

Due to the limited implementation time available, there are many simple improvements that would make this a better system. These improvements can be catagorized into three classes. First of all there is the class of “cosmetic” improvments. These include various enhancements to the user interface such as using a file selector when prompting for the trace name. Certainly, the memory hierarchy creation dialog could use some work as well. These improvments are fairly easy to implement - one simply has to take the time to do so. The second catagory of improvemnts can best be described as improvments in visualization techniques. Clearly, the graphs presented show general trends, but there is much that they do not present. The third catagory of improvements can be described as improvments to the simulation, itself. Although the simulation is doing quite a bit of calculation, it could be augmented to include real timing information. In fact, coupling the cache simulator with other systems would be quite useful. Although the system has some fundamental limitations in what it can be applied to, it shall hopefully become a useful tool for certain applications. The ease with which one can adjust the memory hierarchy and re-run the simulation is certainly a nice feature.

References

[1] M. H. J. Edler, “Dinero iv trace-driven uniprocessor cache simulator.”

[2] D. W. A. Lebeck, “Cache profiling and the spec benchmarks: A case study,” pp. 15–26, October 1994.

[3] M. Hill, “Wisconsin architectural researcj tool set.”

[4] O. T. E. G. G. Kanbier, E. van der Deijl, “A cache visualization tool,”

[5] B. G. V. Phalke, “Compression-based program characterization for improving cache memory performance,” November 1997.

[6] R. F. B. N. K. Grimsrud, J. Archibald, “Locality as a visualization tool,” November 1996.