Automatic software interference detection in parallel applications

ABSTRACT

We present an automated software interference detection methodology for Single Program, Multiple Data (SPMD) parallel applications. Interference comes from the system and unexpected processes. If not detected and corrected such interference may result in performance degradation. Our goal is to provide a reliable metric for software interference that can be used in soft-failure protection and recovery systems. A unique feature of our algorithm is that we measure the relative timing of application events (i.e. time between MPI calls) rather than system level events such as CPU utilization. This approach lets our system automatically accommodate natural variations in an application's utilization of resources. We use performance irregularities and degradation as signs of software interference. However, instead of relying on temporal changes in performance, our system detects spatial performance degradation across multiple processors. We also include a case study that demonstrates our technique's effectiveness, resilience and robustness.

REFERENCES

• 1: Andrzejak, A., L. M. Silva, "Deterministic Models of Software Aging and Optimal Rejuvenation Schedules," CoreGRID Technical Report TR-0047.
• 2: Bailey, D., et. al., "The NAS Parallel Benchmarks," RNR Technical Report, RNR-94-007, March 1994.
• 3: Kirk Bryan, A numerical method for the study of the circulation of the world ocean, Journal of Computational Physics, v.135 n.2, p.154-169, Aug. 1997 [doi>10.1006/jcph.1997.5699 ]
• 4: Anton A. Bougaev, Pattern recognition based tools enabling autonomic computing., Proceedings of the Second International Conference on Automatic Computing, p.313-314, June 13-16, 2005 [doi>10.1109/ICAC.2005.45]
• 5: Karen J. Cassidy , Kenny C. Gross , Amir Malekpour, Advanced Pattern Recognition for Detection of Complex Software Aging Phenomena in Online Transaction Processing Servers, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.478-482, June 23-26, 2002
• 6: Castelli, V., et. al., "Proactive Management of Software Aging," IBM Journal of Res. and Dev., pp. 311--332, vol. 45, no. 2, 2001.
• 7: Chakravorty, S., et. al., "Proactive Fault Tolerance in Large Systems," HPCRI workshop in conjunction with HPCA'05, 2005.
• 8: Charng-Da Lu , Daniel A. Reed, Scalable diskless checkpointing for large parallel systems, University of Illinois at Urbana-Champaign, Champaign, IL, 2005
• 9: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 10: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 11: Dorothy E. Denning, An Intrusion-Detection Model, IEEE Transactions on Software Engineering, v.13 n.2, p.222-232, February 1987 [doi>10.1109/TSE.1987.232894]
• 12: Dukowicz, J. K., R. D. Smith, and R. C. Malone, "A Reformulation and Implementation of the Bryan-Cox-Semtner Ocean Model on the Connection Machine," Journal of Atmospheric and Oceanic Technology, vol. 10, no. 2, pp. 195--208, Apr. 1993.
• 13: Florez, J., et. al., "Detecting Anomalies in High-Performance Parallel Programs" J. Digital Inf. Mgmt, vol. 2, no. 2, June 2004.
• 14: Anup K. Ghosh , Aaron Schwartzbard, A study in using neural networks for anomaly and misuse detection, Proceedings of the 8th conference on USENIX Security Symposium, p.12-12, August 23-26, 1999, Washington, D.C.
• 15: Kenny C. Gross , Vatsal Bhardwaj , Randy Bickford, Proactive Detection of Software Aging Mechanisms in Performance Critical Computers, Proceedings of the 27th Annual NASA Goddard Software Engineering Workshop (SEW-27'02), p.17, December 05-06, 2002
• 16: Steven A. Hofmeyr , Stephanie Forrest , Anil Somayaji, Intrusion detection using sequences of system calls, Journal of Computer Security, v.6 n.3, p.151-180, August 1998
• 17: Javitz, H. S., A. Valdes, "The NIDES Statistical Component: Description and Justification" Tech. Report. Computer Science Lab., SRI International, 1993.
• 18: Guofei Jiang , Haifeng Chen , Cristian Ungureanu , Kenji Yoshihira, Multi-resolution Abnormal Trace Detection Using Varied-length N-grams and Automata, Proceedings of the Second International Conference on Automatic Computing, p.111-122, June 13-16, 2005 [doi>10.1109/ICAC.2005.42]
• 19: Terry Jones , Shawn Dawson , Rob Neely , William Tuel , Larry Brenner , Jeffrey Fier , Robert Blackmore , Patrick Caffrey , Brian Maskell , Paul Tomlinson , Mark Roberts, Improving the Scalability of Parallel Jobs by adding Parallel Awareness to the Operating System, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.10, November 15-21, 2003
• 20: 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
• 21: Nataraj, A., et. al., "Kernel-Level Measurements for Integrated Parallel Performance Views: The KTAU Project," Proc. of IEEE Int. Conf. on Cluster Computing, pp. 1--12, Sep. 2006.
• 22: Nevill-Manning, C. G., I. H. Witten, "Compression and Explanation Using Hierarchical Grammars," The Computer Journal, vol. 40, pp. 103--116, 1997.
• 23: Fabrizio Petrini , Darren J. Kerbyson , Scott Pakin, The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8,192 Processors of ASCI Q, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.55, November 15-21, 2003
• 24: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 25: http://climate.lanl.gov/Models/POP/