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

• US 6,286,130 B1
• Filed: 08/05/1997
• Issued: 09/04/2001
• Est. Priority Date: 08/05/1997
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Petersen, Paul M., Shah, Sanjiv M., Poulsen, David K.
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): OPIE, GEORGE L
• Application Number:
  US08/906,281
• Time in Patent Office: 1,491 Days
• Field of Search: 395/704, 395/706, 717/4, 717/5, 717/6, 717/7, 717/8, 717/9, 714/25
• US Class Current: 717/119
• CPC Class Codes: G06F 8/10 Requirements analysis; Specification techniques
• CPC Class Codes: G06F 8/51 Source to source

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.

Claims

1. 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.

2. The method of claim 1 further comprising the step of inserting, in said sequential computer program, event trace generating machine instructions, said generating instructions for generating said event trace to identify said semantic inconsistencies.

3. The method of claim 1 further comprising the step of inserting, in said sequential computer program, event trace analyzing machine instructions, said analyzing instructions for analyzing said event trace and detecting and reporting said semantic inconsistencies.

4. The method of claim 2 further comprising the steps of:

selecting one or more instrumentation intervals in said sequential computer program, each of said instrumentation intervals comprising one or more machine instructions in said sequential computer program; and

inserting, within each one of said instrumentation intervals, event trace generating machine instructions for generating said event trace to identify said semantic inconsistencies, said generating instructions, when executed, collecting, in a computer storage medium, the portions of said event trace corresponding to said instrumentation intervals.

5. The method of claim 3 further comprising the steps of:

selecting one or more instrumentation intervals in said sequential computer program, each of said instrumentation intervals comprising at least one machine instruction in said sequential computer program, each of said instrumentation intervals being delimited by a start point and an end point; and

inserting, at said end point of each of said instrumentation intervals, event trace analyzing machine instructions, said analyzing instructions for analyzing said event trace and detecting and reporting said semantic inconsistencies.

6. The method of claim 4 further comprising the steps of:

declaring a buffer object, said buffer object being addressable within said instrumentation intervals and being stored in said computer storage medium; and

inserting, within each one of said instrumentation intervals, event trace generating machine instructions for generating said event trace to identify said semantic inconsistencies, said generating instructions comprising machine instructions that, when executed, store buffer object values into said buffer object, each one of said buffer object values corresponding to an event in said event trace for one of said instrumentation intervals.

7. The method of claim 5 further comprising, for each event in said event trace, the steps of:

determining, based on a current state of said sequential computer program, a new state of said sequential computer program, said new state reflecting the effect of said event in said event trace on said current state;

determining if said new state is semantically inconsistent with said current state given said event in said event trace;

detecting and reporting said semantic inconsistencies; and

updating said current state to coincide with said new state.

8. The method of claim 7 wherein said state of said sequential computer program is stored in a computer storage medium and comprises:

a synchronization context comprising a list of at least one synchronization construct that are active at a given point in the execution of said sequential computer program;

a shadow address space comprising, for each of at least one address in the computer storage medium accessed during the execution of said sequential computer and for each synchronization context under which each address was accessed, at least one timestamp; and

an event activation stack, the activation stack comprising entries for the events in said event trace corresponding to the procedures and the parallel programming constructs that are active at a given point in the execution of said sequential computer program.

9. The method of claim 8 wherein said at least one timestamp in said shadow address space further comprises a read timestamp and a write timestamp.

19. The method defined in claim 1, wherein only one trace event is generated for each at least one added instruction.

20. The method defined in claim 1, wherein the step of executing said sequential computer program detects semantic inconsistencies between one or more different parallel executions of said parallel computer program and said corresponding sequential computer program.

21. The method defined in claim 1, wherein the step of executing the sequential computer program is performed only once.

22. The method defined in claim 1, further comprising the step of providing a computer storage medium for storing the sequential computer program and the parallel computer program.

10. 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.

11. The system of claim 10 further comprising means for inserting, in said sequential computer program, event trace generating machine instructions, said generating instructions for generating said event trace to identify said semantic inconsistencies.

12. The system of claim 10 further comprising means for inserting, in said sequential computer program, event trace analyzing machine instructions, said analyzing instructions for analyzing said event trace and detecting and reporting said semantic inconsistencies.

13. The system of claim 11 further comprising:

means for selecting one or more instrumentation intervals in said sequential computer program, each of said instrumentation intervals comprising one or more machine instructions in said sequential computer program; and

means for inserting, within each one of said instrumentation intervals, event trace generating machine instructions for generating said event trace to identify said semantic inconsistencies, said generating instructions, when executed, collecting, in the computer storage medium, the portions of said event trace corresponding to said instrumentation intervals.

14. The method of claim 12 further comprising:

means for selecting one or more instrumentation intervals in said sequential computer program, each of said instrumentation intervals comprising at least one machine instruction in said sequential computer program, each of said instrumentation intervals being delimited by a start point and an end point; and

means for inserting, at said end point of each of said instrumentation intervals, event trace analyzing machine instructions, said analyzing instructions for analyzing said event trace and detecting and reporting said semantic inconsistencies.

15. The system of claim 13 further comprising:

means for declaring a buffer object, said buffer object being addressable within said instrumentation intervals and being stored in said computer storage medium; and

means for inserting, within each one of said instrumentation intervals, event trace generating machine instructions for generating said event trace to identify said semantic inconsistencies, said generating instructions comprising machine instructions that, when executed, store buffer object values into said buffer object, each one of said buffer object values corresponding to an event in said event trace for one of said instrumentation intervals.

16. The system of claim 14 further comprising, for each event in said event trace:

means for determining, based on a current state of said sequential computer program, a new state of said sequential computer program, said new state reflecting the effect of said event in said event trace on said current state;

means for determining if said new state is semantically inconsistent with said current state given said event in said event trace;

means for detecting and reporting said semantic inconsistencies; and

means for updating said current state to coincide with said new state.

17. The system of claim 16 wherein said state of said sequential computer program is stored in the computer storage medium and comprises:

a synchronization context comprising a list of at least one synchronization construct that are active at a given point in the execution of said sequential computer program;

a shadow address space comprising, for each of at least one address in the computer storage medium accessed during the execution of said sequential computer and for each synchronization context under which each address was accessed, at least one timestamp; and

an event activation stack, the activation stack comprising entries for the events in said event trace corresponding to the procedures and the parallel programming constructs that are active at a given point in the execution of said sequential computer program.

18. The system of claim 17 wherein said at least one timestamp in said shadow address space further comprises a read timestamp and a write timestamp.

23. The system defined in claim 10, wherein only one trace event is generated for each at least one added instruction.

24. The system defined in claim 10, wherein the means for analyzing detects semantic inconsistencies between one or more different parallel executions of said parallel computer program and said corresponding sequential computer program.

25. The system defined in claim 10, wherein the sequential computer program is executed only once.