Application of redundant computation in software performance analysis

ABSTRACT

Redundant computation is an execution of a program statement(s) that does not contribute to the program output. The same statement on one execution may exhibit redundant computation whereas on a different execution, it contributes to the program output. A redundant (dead) statement always exhibits redundant computation, i.e., its execution is always redundant. However, a statement that exhibits redundant computation is not necessarily a redundant statement. Redundant computation represents a partial redundancy of a statement. A high degree of redundant computation in a program may indicate a performance deficiency. Therefore, elimination (or reduction) of redundant computation may improve program's performance. In this paper we present an approach of automated detection of redundant computation in programs and show its application in performance analysis. We developed a tool that automatically detects redundant computations in C programs and identifies potential performance deficiencies related to redundant computation. We have performed an experimental study that showed that redundant computation is a commonly occurring phenomenon in programs, and it is frequently a source of performance deficiency.

REFERENCES

• 1: Zakarya A. Alzamil , Bogdan Korel, Redundant computation and its application in software performance analysis, 2002
• 2: Zakarya Alzamil, RCAT: A Performance Analysis Tool, Proceedings of the 19th IEEE international conference on Automated software engineering, p.366-370, September 20-24, 2004 [doi>10.1109/ASE.2004.57]
• 3: Zakarya Alzamil, Application of the operational profile in software performance analysis, Proceedings of the 4th international workshop on Software and performance, January 14-16, 2004, Redwood Shores, California
• 4: 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
• 5: Jack Dongarra , Joanne Martin , Jack Vorlton, Computer benchmarking: paths and pitfalls, IEEE Spectrum, v.24 n.7, p.38-43, July 1987
• 6: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 7: Lloyd D. Fosdick , Leon J. Osterweil, Data Flow Analysis in Software Reliability, ACM Computing Surveys (CSUR), v.8 n.3, p.305-330, Sept. 1976 [doi>10.1145/356674.356676]
• 8: Graham S., Kessler P., and McKusick M. "An Execution Profiler for Modular Programs", Software Practice and Experience, Vol. 13, 1983, pp. 671--685.
• 9: Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993 [doi>10.1145/176454.176507]
• 10: Rajiv Gupta , Mary Lou Soffa, Hybrid slicing: an approach for refining static slices using dynamic information, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.29-40, October 12-15, 1995, Washington, D.C., United States
• 11: Robert J. Hall, Call Path Refinement Profiles, IEEE Transactions on Software Engineering, v.21 n.6, p.481-496, June 1995 [doi>10.1109/32.391375 ]
• 12: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• 13: Knuth D. "An Empirical Study of Fortran Programs", Software Practice and Experience, Vol. 1, 1971, pp. 105--133.
• 14: Bogdan Korel, The program dependence graph in static program testing, Information Processing Letters, v.24 n.2, p.103-108, January 1987 [doi>10.1016/0020-0190(87)90102-5 ]
• 15: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3 ]
• 16: Bogdan Korel, Computation of Dynamic Program Slices for Unstructured Programs, IEEE Transactions on Software Engineering, v.23 n.1, p.17-34, January 1997 [doi>10.1109/32.581327 ]
• 17: Larus J. and Chandra S. "Using Tracing and Dynamic Slicing to Tune Compilers", Computer Science Dept., University of Wisconsin-Madison, TR. # 1174, August 1993.
• 18: John D. Musa, Operational Profiles in Software-Reliability Engineering, IEEE Software, v.10 n.2, p.14-32, March 1993 [doi>10.1109/52.199724 ]
• 19: Rafael H. Saavedra , Alan J. Smith, Analysis of benchmark characteristics and benchmark performance prediction, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.344-384, Nov. 1996 [doi>10.1145/235543.235545]
• 20: V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989
• 21: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States
• 22: Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.15-26, October 05-08, 1997, Saint Malo, France
• 23: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Measurement, Performance

Keywords:
control dependence, data dependence, dependence analysis, performance analysis, redundant code, redundant computation