Prediction and trace compression of data access addresses through nested loop recognition

ABSTRACT

This paper describes an algorithm that takes a trace (i.e., a sequence of numbers or vectors of numbers) as input, and from that produces a sequence of loop nests that, when run, produces exactly the original sequence. The input format is suitable for any kind of program execution trace, and the output conforms to standard models of loop nests. The first, most obvious, use of such an algorithm is for program behavior modeling for any measured quantity (memory accesses, number of cache misses, etc.). Finding loops amounts to detecting periodic behavior and provides an explanatory model. The second application is trace compression, i.e., storing the loop nests instead of the original trace. Decompression consists of running the loops, which is easy and fast. A third application is value prediction. Since the algorithm forms loops while reading input, it is able to extrapolate the loop under construction to predict further incoming values. Throughout the paper, we provide examples that explain our algorithms. Moreover, we evaluate trace compression and value prediction on a subset of the SPEC2000 benchmarks.

REFERENCES

• 1: Jean Christophe Beyler , Philippe Clauss, Performance driven data cache prefetching in a dynamic software optimization system, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275000]
• 2: Martin Burtscher , Ilya Ganusov , Sandra J. Jackson , Jian Ke , Paruj Ratanaworabhan , Nana B. Sam, The VPC Trace-Compression Algorithms, IEEE Transactions on Computers, v.54 n.11, p.1329-1344, November 2005 [doi>10.1109/TC.2005.186]
• 3: P. Clauss, B. Kenmei, and J. C. Beyler. The periodic-linear model of program behavior capture. In Euro-Par 2005, volume 3648 of LNCS, pages 325--335. Springer, 2005.
• 4: Luiz DeRose , K. Ekanadham , Jeffrey K. Hollingsworth , Simone Sbaraglia, SIGMA: a simulator infrastructure to guide memory analysis, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-13, November 16, 2002, Baltimore, Maryland
• 5: E. E. Johnson and J. Ha. PDATS: Lossless address space compression for reducing file size and access time. In Proceedings of 1994 IEEE International Phoenix Conference on Computers and Communication, 1994.
• 6: M. Kobayashi, Dynamic Characteristics of Loops, IEEE Transactions on Computers, v.33 n.2, p.125-132, February 1984 [doi>10.1109/TC.1984.1676404]
• 7: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Aleksandar Milenkovic , Milena Milenkovic, Stream-Based Trace Compression, IEEE Computer Architecture Letters, v.2 n.1, p.4, January 2003 [doi>10.1109/L-CA.2003.7]
• 9: T. Moseley, D. Grunwald, and R. V. Peri. Seekable compressed traces. In Proceedings of the 2007 IEEE International Symposium on Workload Characterization (IISWC), 2007.
• 10: C. G. Nevill-Manning and I. H. Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. J. Artif. Intell. Res. (JAIR)}, 7:67--82, 1997.
• 11: A. D. Samples, Mache: no-loss trace compaction, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.89-97, May 23-26, 1989, Oakland, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

General Terms:
Algorithms, Performance

Keywords:
data access, nested loop recognition, trace analysis, trace compression, value prediction