Скачать или смотреть Topological Analysis and Visualization of Cyclical Behavior in Memory Reference Traces

We present a method for performing topological analysis and visualization of memory reference traces. This allows identifying and visualizing recurrent memory access patterns, which are so common to software, as circular structures.

Our system begins by capturing a list of memory accesses from a running application.

The memory trace records are then converted to a high-dimensional point cloud by combining neighboring references using a sliding window.

Next, topological analysis is performed on the point cloud to detect circular structures. Multiple circular structures may be found for a data set and each is output as a circular parameterization.

Finally, the parameterizations are visualized. The parameterizations are laid out in two dimensions using the radius to indicate time and color to correlate points with source code.

Morphing between parameterization assists in correlating their structures.
Results

Here we see our first parameterization for the bubble sort algorithm. In this case, the input data is already sorted. Here, the 4 cycles of the parameterization represent the 4 comparisons which bubble sort performs.

An alternative parameterization highlights accesses to the two memory locations involved in a comparison, once per comparison, for a total of 8 cycles.

Next, we examine bubble sort with the input in reverse order. In the first parameterization, the cycles represent the algorithm returning to the outer loop, while the teeth capture the compare and swap operations.

This parameterization breaks the operation down even further. Here, each band of 3 cycles represents the compare and swap operations.

Finally, we see the results for a shuffled list of numbers. Here, the cycles represent the compare and swap operations, while the teeth represent the operations which compare but do not swap.

Next, we look at the cycles produced using half of a trace for 4x4 matrix multiply, where 3 interesting parameterizations have been collected. The first parameterization
The next parameterization shows cycles of yellow and purple, each of which represents the execution of the middle looping structure. Four of these cycles appear between each pair of outer loop cycles.

The final parameterization shows red cycles, each representing an execution of the inner most loop. The bands of four cycles represent the four iterations that occur for each of the middle loops.

The final data set is a memory trace for a particle system calculated using the material point method. Here non-looping recurrent structures are identified using our method. This example shows calculation of the stress rate. The first circular structures capture the matrix additions that appear in the code.

The next structure captures matrix subtraction which is implemented as addition with a negated matrix. Had the subtraction been implemented directly, it would have appeared identical to addition, from a memory trace perspective.

The next parameterization captures both the addition and subtraction operations.

The final set of structures captures the matrix scaling operations.

Running a larger trace enables differentiating various portions of the execution. This first set of circular features is able to capture the setting of the mass and momentum variables to zero.

This alternate parameterization captures the next phase of execution, the interpolation of mass and momentum to a background grid.

In conclusion, we have presented a method for identifying looping and non-looping recurrent structures within memory traces by performing topological analysis on the memory trace. It is our hope that these structures, once identified, can be used to better understand software design and for optimizing software performance.

Directed by:
A.N.M. Imroz Choudhury, Paul Rosen

Video produced by: Chems Touati

Research Team:
A.N.M. Imroz Choudhury, Bei Wang,
Paul Rosen, Valerio Pascucci

National Science Foundation awards IIS-0904631, IIS-0906379, and CCF-0702817.
This work was also performed under the auspices of the U.S. De-
partment of Energy by the University of Utah under contract DE-
SC0001922 and DE-FC02-06ER25781 and by Lawrence Livermore National
Laboratory under contract DE-AC52-07NA27344.LLNL- JRNL-453051. This
work was supported in part by the DOE Occie of Science, Biology and
Environment (BER), and the Scientific Discovery through Advanced
Computing (SciDAC) programs Visualization and Analytics Center for
Enabling Technologies (VACET)

NSF CDI, Award ID 0835821
NIH/NCRR Center for Integrative Biomedical Computing, 2P41 RR0112553-12

Scientific Computing and Imaging (SCI) Institute
UNIVERSITY OF UTAH