RDVIS - Reuse Distance Visualizer


The RDVIS tool highlights the sources of cache misses and poor temporal locality in the source code. Also check out our newer SLO-tool, that next to highlighting the code regions that are responsible for poor locality, also suggests the most appropriate refactorings that are needed to substantially improve the temporal locality.

The RDVIS tool is licensed as citation-ware. It means that you can use RDVIS freely, but if you publish research results for which you used RDVIS, it would be greatly appreciated if you would cite one of the following papers:
If you have Java web-start installed, you can start the RDVIS-tool from this web-site. (If you see a link to start RDVIS below, you have Java web-start installed. If after clicking this link, you get a request to open a jnlp-file, open it with a program called javaws. If you don't already have Java version 1.5 installed, an attempt will be made to automatically install Java version 1.5. It this doesn't succeed, you'll need to install Java 1.5 manually, which can be downloaded from Sun's download page).


After RDVIS has been started, a file selector pops up. In this file selector, you need to indicate an appropriate ZIP-file which contains the source code and the information produced by GCC while compiling the program, and the information recorded in a BRD-file during the execution of the program. Example input-files are provided below.

Tutorial

The theoretical background behind the RDVIS tool is explained in our ICCS05-paper, which describes the insights required to start using the tool.

A first, small tutorial which shows how a matrix multiplication code can be optimized using the RDVIS-tool is available here. A PDF-version of the tutorial can be found here.
I find that my personal typical use pattern of the RDVIS tool is the following:
  1. Open the *.rdvis.zip-file that contains the measured reuse information that you want to visualize and analyze.
  2. When the main source-code window has opened, go to the menu-bar and click Window->Overall Reuse Distance Histogram. This will show up a reuse distance histogram of all memory accesses in the program. Based on this reuse distance histogram, you see what the minimum cache size is that you are interested in. (This minimum cache size is the value that you interpret as being the border value between "small reuse distances" and "large reuse distances". This value can depend on the program that you are analyzing, the specific cache system that you are trying to optimize for, or something else I can't think of right now.
  3. After selecting the minimal interesting cache size in the options-window, I usually continue by doing a cluster analysis on the remaining reuse pairs, by clicking Window->Cluster Analysis in the main window. After a little while (depending on the number of reuse pairs that need to be clustered), the cluster view shows up. In this cluster view, I select an interesting looking cluster, by clicking in the dendrogram on the right. A pop-up menu will show up that gives you the options Select, Unselect and Highlight cluster in Source Pane. First Select a cluster, you'll see the color of the cluster being changed, and the corresponding arrows in the source view window will have the same color. When you click Highlight cluster in Source Pane, all the code that is executed between the reuses in the selected cluster are highlighted in the source code window, by coloring the background of the code yellow, and the code that is executed between colors ranging from black to red. Black means that the code was never executed between reuses in the selected cluster, full red means that the code was executed between all reuses in the selected cluster. Usually, this code highlighting already hint some loop optimizations, when the amount of code between use and reuse is not too large.

Example input files


RDVIS input file
 Description
mxm_N=100_cl64.rdvis.zip
 a simple matrix multiplication program, which multiplies two 100X100 matrices. A cache line size of 64 bytes was assumed.
equake_inlined1_gcc4_ref_nosl.rdvis.zip
 The Equake program from the SPEC2000 benchmark, slightly modified to manually inline one function. The program was run with the reference input. It is assumed that a cache line contains a single data element (i.e. the cache only captures temporal locality).
mcf_ref_cl64.rdvis.zip
 The Mcf program from the SPEC2000 benchmark. The program was run with the reference input. A cache line size of 64 bytes was assumed.
mcf_gcc4_ref_cl0b.rdvis.zip
 The Mcf program from the SPEC2000 benchmark. The program was run with the reference input. It is assumed that a cache line contains a single data element (i.e. the cache only captures temporal locality).
art_ref1.rdvis.zip
 The Art program from the SPEC2000 benchmark. The program was run with the first reference input. It is assumed that a cache line contains a single data element (i.e. the cache only captures temporal locality).
art_ref2.rdvis.zip
 The Art program from the SPEC2000 benchmark. The program was run with the second reference input. It is assumed that a cache line contains a single data element (i.e. the cache only captures temporal locality).
p4_8KB_512KB_double.cachesizes
 A file encoding the cache sizes of a Pentium4 processor, with 8KB L1 cache, 512KB L2 cache, when the main data elements in the programs are 8 byte doubles. This file can be read in reuse distance histogram frames, using the menu entry Options->Read Cache Sizes from file.


Patch for GCC

Now you can generate the *.rdvis.zip for your own programs! A patched version of GCC to instrument programs, a library to measure reuse information, and a small test program can be downloaded here: rdvis-instrument-20050607.tar.bz2. The tar-file contains the following files:

Binary Distribution for Cygwin

Now, a binary distribution (rdvis20051122.cygwin.all.tar.gz) of the patched GCC compiler is made available for cygwin. It makes the installation easier if you do not have much experience in building GCC. To install, make sure that you have the following packages installed under cygwin: tar, make, binutils, gcc*, gcc-mingw*. To install the binary distribution, proceed as follows in the cygwin command shell:
  1. tar -zxvf rdvis20051122.cygwin.all.tar.gz
  2. cd rdvis
  3. ./install-and-test.sh
The test_and_install.sh script installs the patched GCC in directory /tmp. Furthermore, it will attempt to compile and run the small program in directory test. After finishing compilation and running the instrumented program, it will start RDVIS. Remember, you will need at least java 1.5 installed to make RDVIS run! You can check your Java version by running 
java -version
in the cygwin shell.

Comments can be sent to Kristof Beyls, e-mail: Kristof.Beyls at elis.ugent.be

Valid HTML 4.01!