Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-08-05
2001-09-04
Oberley, Alvin E. (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06286130
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
MICROFICHE APPENDIX
A Microfiche Appendix of the presently conferred computer program source code is included and comprises five (5) sheets of fiche, having a total of 441 frames. The Microfiche Appendix is hereby expressly incorporated herein by reference, and contains material which is subject to copyright protection as set forth above.
FIELD OF THE INVENTION
The present invention relates to computer systems and to parallel computer programming, and, more particularly, to methods for automatically validating the correctness of parallel computer programs by identifying errors that could cause such programs to behave incorrectly or to produce incorrect results.
BACKGROUND OF THE INVENTION
Parallel computer programs are fundamentally more difficult to validate, test, and debug than sequential computer programs. While typical programs can exhibit traditional “sequential” errors, such as those caused by incorrect syntax, program logic, control flow, or rounding or truncation of numerical results, parallel programs can exhibit additional types of errors. Parallel programming errors can result from parallelizing a sequential program, wherein constraints on the ordering of operations in the original sequential program are relaxed in order to exploit parallelism, which results in unintended indeterminacy. In addition, errors can result from the incorrect application or use of parallel programming constructs; many of these errors are difficult or impossible to detect statically, especially without employing interprocedural analysis.
In many common parallel programming languages, a parallel program is constructed by starting with a sequential program and then forming its corresponding parallel version by annotating the sequential program, for example, with directives or language-extension statements. The traditional view of these annotations has been that they describe parallel programming constructs to be added to the sequential program. An alternative view, however, is that such annotations describe constraints in the sequential program to be relaxed to allow the exploitation of parallelism. This alternative view facilitates a broad definition of parallel program validation, wherein a parallel program is validated for correctness with respect to its corresponding sequential program, independent of timing, scheduling, or the number of processors or threads used to execute the parallel program. Validation should consider semantic inconsistencies caused by the incorrect use of parallel programming constructs as well as by unintended indeterminacy. Such semantic inconsistencies include not only dynamic dependencies but other errors caused by the modification of the sequential program.
The prior art has largely taken the traditional view in addressing parallel program debugging. Race detection and dynamic dependence analysis schemes have been described that detect errors caused by unintended indeterminacy during parallel execution. Little prior art exists, however, with respect to detecting errors caused by the incorrect use of parallel programming constructs or with respect to the general problem of parallel program validation as defined above.
Race detection schemes employ either static, post-mortem, and on-the-fly analysis methods. Static methods suffer the disadvantage of being overly conservative, even if aggressive interprocedural and symbolic analysis is used, since they do not resolve references that must be analyzed at runtime. Post-mortem methods require the production and storage of extremely large amounts of data in order to provide complete, accurate race analysis. Reducing the amount of data required results in correspondingly less accurate analysis. On-the-fly race analysis methods help eliminate the requirement of storing large amounts of post-mortem analysis data, without sacrificing the accuracy of dynamic analysis techniques. Most race detection schemes, however, require a parallel execution of the program being analyzed. These methods typically require a (particular) parallel machine on which to execute the parallel program, and thus can not analyze parallel programs with severe errors that prevent parallel execution or cause abnormal termination.
Dynamic dependence analysis methods detect data races that could potentially occur during execution of a parallel program via on-the-fly analysis of the corresponding sequential program. These methods do not require parallel execution, and they isolate the analysis from particular timings or interleavings of events, scheduling methods, or numbers of processors or threads used. Dynamic dependence analysis schemes, however, do not detect errors arising from incorrect parallel programming construct use, and do not fully support a complete parallel programming language or dialect.
Most race detection schemes, even those employing so-called sequential traces, are limited in several ways. First, they suffer all the disadvantages of dynamic methods that require parallel execution: the schemes are inherently less portable, and they cannot analyze parallel programs with catastrophic errors. Second, many of these schemes assume simplified parallel programming models, and most are not based on realistic, complete parallel programming languages or dialects. While these schemes address the issue of language generality, they still suffer the disadvantage of requiring parallel execution, which limits the classes of errors that can be analyzed, and the portability and applicability of the methods.
Other relative debugging techniques also suffer the disadvantages of most of the aforementioned schemes (e.g., requiring parallel execution, analyzing one particular parallel execution). Some degree of parallel execution is still required. The prior art, therefore, lacks the advantage of validating the correctness of a parallel computer program without the need for parallel execution.
SUMMARY OF THE INVENTION
The present invention is a software-implemented method for validating the correctness of parallel computer programs that were written in various programming languages. The validation method detects errors that could cause these parallel computer programs to behave incorrectly or to produce incorrect results. Validation is accomplished by transforming input parallel computer programs under computer control and sequentially executing the resulting transformed programs. The validation method is system-independent, is portable across various computer architectures and platforms, and requires no input program modification on the part of the programmer.
The input to the validation method is a parallel computer program. The parallel computer program results from annotating its corresponding sequential computer program according to a parallelism specification; the annotations describe constraints in the sequential program to be relaxed to allow the exploitation of parallelism. Validation is accomplished by detecting the semantic inconsistencies between the parallel computer program and its corresponding sequential computer program. The validation method itself translates the input parallel computer program into a second, sequential computer program such that the second sequential computer program, when executed, detects and reports the semantic inconsistencies between the parallel computer program and its corresponding sequential computer program.
In the preferred embodiment of the present invention, the validation method is implemented by performing a program transformation, under computer control, of the input parallel computer program into a second, sequential computer program. This program transformation comprises two steps. First, machine instructions are added to
Petersen Paul M.
Poulsen David K.
Shah Sanjiv M.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Oberley Alvin E.
Opie George
LandOfFree
Software implemented method for automatically validating the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Software implemented method for automatically validating the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software implemented method for automatically validating the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2440412