US 6,286,130 B1 · Software implemented method for automatically validating the correctness of parallel computer programs

Abstract

A software-implemented method for validating the correctness of parallel computer programs, written in various programming languages, with respect to these programs' corresponding sequential computer programs. Validation detects errors that could cause parallel computer programs to behave incorrectly or to produce incorrect results, and is accomplished by transforming these parallel computer programs under the control of a general purpose computer and sequentially executing the resulting transformed programs. The validation method is system-independent and is portable across various computer architectures and platforms since validation is accomplished via program transformation; thus, the method does not depend on the features of a particular hardware architecture or configuration, operating system, compiler, linker, or thread environment. The input to the validation method is a parallel computer program. The parallel computer program results from annotating its corresponding sequential computer program with 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 semantic inconsistencies between the parallel computer program and its corresponding sequential computer program. The validation method 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.

Claims25

Dependent claims

A method for detecting individual errors in a parallel computer program by translating a parallel computer program into a sequential computer program, said method comprising the steps of:

identifying a parallel computer program having at least one parallelism specification;
generating a corresponding sequential computer program to the parallel computer program by ignoring said at least one parallelism specification contained in the parallel computer program;
adding to said corresponding sequential computer program at least one first instruction, to generate at least one first trace event, said at least one first instruction relating to said corresponding sequential computer program, and at least one second instruction, to generate at least one second trace event, said at least one second instruction based upon the ignored at least one parallelism specification
logically partitioning the sequential computer program into at least one disjoint group based upon the at least one second trace event, said at least one disjoint group comprising at least one of the at least one first trace events;
and
executing only said sequential computer program a single time, and analyzing said at least one disjoint group of said at least one first trace event based on types of second trace events used to partition said at least one first trace event to detect and report each precise semantic inconsistency between said parallel computer program and said corresponding sequential computer program, thereby detecting one or more semantic inconsistencies associated with a plurality of different executions of the parallel computer program.

3 more elements

A system for detecting errors in a parallel computer program by translating a parallel computer program into a sequential computer program, comprising:

a computer storage medium, the computer storage medium for storing a parallel computer program having at least one parallelism specification;
means for generating a corresponding sequential computer program to the parallel computer program by ignoring said at least one parallelism specification contained in the parallel computer program, the corresponding sequential computer program being stored in the computer storage medium;
means for adding to said corresponding sequential computer program at least one instruction to generate at least one trace event based upon the at least one parallelism specification and the corresponding sequential computer program to produce said sequential computer program, the sequential computer program being stored in the computer storage medium;
and
means for analyzing said at least one trace event when said sequential computer program is executed once to detect and report semantic inconsistencies between said parallel computer program and said corresponding sequential computer program and associated with two or more executions of the parallel computer program.

2 more elements

Dependencies are inferred from the claim text.

Software implemented method for automatically validating the correctness of parallel computer programs

Life of this patent

Software implemented method for automatically validating the correctness of parallel computer programs

Life of this patent

Abstract

Claims25