Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2011-01-04
2011-01-04
Baker, Stephen M (Department: 2112)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S048000, C717S126000, C717S132000
Reexamination Certificate
active
07865778
ABSTRACT:
A method and system for error detection in programs with collective synchronization and/or procedures are provided. In one aspect, the method and system may use interprocedural analysis for matching synchronizations in a program in order to detect synchronization errors, and, if no such errors exist, may determine the synchronization phases of the program. The method and system in one aspect may use a combination of path expressions and interprocedural program slicing to match the synchronization statements that may execute along each program path. If the synchronization matching succeeds, the method and system in one aspect may determine the sets of synchronization statements that synchronize together. A matching failure may indicate the presence of a synchronization error and the method and system in one aspect may construct a counter example to illustrate the error.
REFERENCES:
patent: 5802374 (1998-09-01), Gupta et al.
patent: 6286130 (2001-09-01), Poulsen et al.
patent: 6718484 (2004-04-01), Kodera
patent: 7089543 (2006-08-01), Rising, III
patent: 7159211 (2007-01-01), Jalan et al.
patent: 7475385 (2009-01-01), Huemiller, Jr.
patent: 7552428 (2009-06-01), Stoodley et al.
patent: 7673295 (2010-03-01), Lin
patent: 7716645 (2010-05-01), Dolby et al.
patent: 2002/0124241 (2002-09-01), Grey et al.
Susan Horwitz, et al. “Interprocedural Slicing Using Dependence Graphs”. ACM Transactions on Programming Languages and Systems, Jan. 1990, 26-60, vol. 12, No. 1.
Mark Weiser, “Program Slicing”, IEEE Transactions on Software Engineering, 1981, 352-357,vol.10, No. 4.
Evelyn Duesterwald et al. “Concurrency Analysis in the Presence of Procedures Using a Data-Flow Framework”, In Proceedings of the Symposium on Testing, Analysis, and Verification,1991, pp. 36-48.
Stephen P. Masticola et al. “Nonconcurrency Analysis”, In Proceedings of the Fourth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, May 1993, pp. 129-138, San Diego, California.
Tor E. Jeremiassen et al. “Static Analysis of Barrier Synchronization in Explicitly Parallel Systems”, In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Architectures and CompilationTechniques, PACT '94, pp. 171-180.
Arvind Krishnamurthy et al. “Analyses and Optimizations for Shared Address Space Programs”, J. Parallel Distrib. Comput., 1996, 130-144, vol. 38, No. 2.
Yuan Lin. “Static Nonconcurrency Analysis of Openmp Programs”, In First International Workshop on OpenMP, 2005.
Alexander Aiken, et al. “Barrier Inference”, In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1998, pp. 342-354.
A Krishnamoorthy, et al. “Parallel Programming in Split-C”, In Supercomputing '93 Proceedings, Nov. 1993, pp. 262-273.
Stephen F. Siegel, et al. “Using Model Checking With Symbolic Execution to Verify Parallel Numerical Programs”, In Proceedings of the 2006 International Symposium on Software Testing and Analysis, 2006, pp. 157-167.
Peng Tu, et al. “Gated SSA-based demand driven symbolic analysis for parallelizing compilers”, In Conference Proceedings, 1995 International Conference on Supercomputing, pp. 414-423, Barcelona, Spain, Jul. 1995.
Cormac Flanagan, et al. “Modular Verification of Multithreaded Programs”, Theor. Comput. Sci.,2005, 153-183, vol. 338, No. 1-3.
Alain Darte, et al. “A Linear-time Algorithm for Optimal Barrier Placement”, In Proceedings of the tenthACM SIGPLAN symposium on Principles and Practice of Parallel Programming, 2005, pp. 26-35.
Chau-Wen Tseng, “Compiler Optimizations for Eliminating Barrier Synchronization”, In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, Jul. 1995, pp. 144-155, Santa Barbara, California.
Michael O'Boyle et al, “Compile Time Barrier Synchronization Minimization”, IEEE Trans. Parallel Distrib.Syst., 2002, 529-543, vol. 13, No. 6.
Shuyi Shao et al, “A Compiler Based Communication Analysis Approach for Multiprocessor Systems”, 2006.
P.Hulfinger et al, “Titanium Language Reference Manual”, Technical Report UCB/EECS-2005-15, 2005; U.C. Berkeley.
David Callahan et al, “Analysis of Event Synchronization in a Parallel Programming Tool”, In Proceedings of the Second ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, Mar. 1990, pp. 21-30; Seattle, Washington.
Stephen F. Siegel and George S. Avrunin, “Modeling wildcard free mpi programs for verification”, In Proceedings of the tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 95-106, 2005.
Robert E . Tarjan, “A unified approach to path problems”, Journal of the ACM, 28(3):577-593, Jul. 1981.
G.A. Venkatesh, The semantic approach to program slicing. In Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, pp. 107-119, Toronto, Ontario, Jun. 1991.
Karl J. Ottenstein, et al. “The program dependence graph in a software development environment”, Software Engineering Notes, 9(3), 1984.
Ron Cytron, et al. “Efficiently computing static single assignment form and the control dependence graph”, ACM Transactions on Programming Languages and Systems, 13(4):451-490, Oct. 1991.
Cytron, Ron et al., Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems, Oct. 1991, pp. 451-490, 13(4).
Eclipse Parallel Tools Platform (PTP) project, www. eclipse. org / ptp.
Duesterwald Evelyn
Zhang Yuan
Baker Stephen M
Dougherty, Esq. Anne V.
International Business Machines - Corporation
Scully , Scott, Murphy & Presser, P.C.
LandOfFree
Method and system for detecting synchronization errors in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for detecting synchronization errors in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for detecting synchronization errors in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2727041