DARC: dynamic analysis of root causes of latency distributions

ABSTRACT

OSprof is a versatile, portable, and efficient profiling methodology based on the analysis of latency distributions. Although OSprof has offers several unique benefits and has been used to uncover several interesting performance problems, the latency distributions that it provides must be analyzed manually. These latency distributions are presented as histograms and contain distinct groups of data, called peaks, that characterize the overall behavior of the running code. By automating the analysis process, we make it easier to take advantage of OSprof's unique features.

We have developed the Dynamic Analysis of Root Causes system (DARC), which finds root cause paths in a running program's call-graph using runtime latency analysis. A root cause path is a call-path that starts at a given function and includes the largest latency contributors to a given peak. These paths are the main causes for the high-level behavior that is represented as a peak in an OSprof histogram. DARC performs PID and call-path filtering to reduce overheads and perturbations, and can handle recursive and indirect calls. DARC can analyze preemptive behavior and asynchronous call-paths, and can also resume its analysis from a previous state, which is useful when analyzing short-running programs or specific phases of a program's execution.

We present DARC and show its usefulness by analyzing behaviors that were observed in several interesting scenarios. We also show that DARC has negligible elapsed time overheads for normal use cases.

REFERENCES

• 1: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 2: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 3: Andrew R. Bernat , Barton P. Miller, Incremental call-path profiling: Research Articles, Concurrency and Computation: Practice & Experience, v.19 n.11, p.1533-1547, August 2007 [doi>10.1002/cpe.v19:11]
• 4: Harold W. Cain , Barton P. Miller , Brian J. N. Wylie, A Callgraph-Based Search Strategy for Automated Performance Diagnosis (Distinguished Paper), Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.108-122, August 29-September 01, 2000
• 5: W. Cohen. Gaining insight into the Linux kernel with Kprobes. RedHat Magazine, March 2005.
• 6: Luiz DeRose , Felix Wolf, CATCH - A Call-Graph Based Automatic Tool for Capture of Hardware Performance Metrics for MPI and OpenMP Applications, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.167-176, August 27-30, 2002
• 7: Nathan Froyd , John Mellor-Crummey , Rob Fowler, Low-overhead call path profiling of unmodified, optimized code, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088161]
• 8: Nikolai Joukov , Avishay Traeger , Rakesh Iyer , Charles P. Wright , Erez Zadok, Operating system profiling via latency analysis, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 9: 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
• 10: David Melski , Thomas W. Reps, Interprocedural Path Profiling, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.47-62, March 22-28, 1999
• 11: Barton P. Miller , Mark D. Callaghan , Jonathan M. Cargille , Jeffrey K. Hollingsworth , R. Bruce Irvin , Karen L. Karavanic , Krishna Kunchithapadam , Tia Newhall, The Paradyn Parallel Performance Measurement Tool, Computer, v.28 n.11, p.37-46, November 1995 [doi>10.1109/2.471178]
• 12: A. V. Mirgorodskiy and B. P. Miller. CrossWalk: A tool for performance profiling across the user-kernel boundary. In Proc. of PARCO 2003, pp. 745--752, Dresden, Germany, September 2003. Elsevier.
• 13: A. Nataraj, A. Malony, S. Shende, and A. Morris. Kernel-level measurement for integrated parallel performance views: the ktau project. In Proc. of the 2006 IEEE Conference on Cluster Computing, Barcelona, Spain, September 2006
• 14: C. Nentwich and M. Tiihonen. Intel2gas. http://www.niksula.hut.fi/~mtiihone/intel2gas/, 2000.
• 15: V. Patkov. Hacker disassembler engine. http://vx.netlux.org/vx.php?id=eh04, 2007.
• 16: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, A Metric for Distributions with Applications to Image Databases, Proceedings of the Sixth International Conference on Computer Vision, p.59, January 04-07, 1998
• 17: Sameer S. Shende , Allen D. Malony, The Tau Parallel Performance System, International Journal of High Performance Computing Applications, v.20 n.2, p.287-311, May 2006 [doi>10.1177/1094342006064482]
• 18: Ariel Meir Tamches , Barton P. Miller, Fine-grained dynamic instrumentation of commodity operating system kernels, The University of Wisconsin - Madison, 2001
• 19: Ariel Tamches , Barton P. Miller, Using Dynamic Kernel Instrumentation for Kernel and Application Tuning, International Journal of High Performance Computing Applications, v.13 n.3, p.263-276, August 1999 [doi>10.1177/109434209901300309]
• 20: Charles P. Wright , Nikolai Joukov , Devaki Kulkarni , Yevgeniy Miretskiy , Erez Zadok, Auto-pilot: a platform for system software benchmarking, Proceedings of the annual conference on USENIX Annual Technical Conference, p.53-53, April 10-15, 2005, Anaheim, CA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Measurement, Performance

Keywords:
dynamic instrumentation, root cause