Parallel programming using possible parallel regions and its language profiling compiler, run-time system and debugging support

1. A method of dynamic parallelization for programs in systems having at least two processors, the method comprising the steps of:

examining computer code of a program to be performed by the system;

determining a largest possible parallel region in the computer code using profiling to identify a high-level phase structure of the program and using dependence profiling to find a phase with a largest portion of run-time instructions that can be executed in parallel, wherein the profiling and dependence profiling include examining both the computer code and at least one training execution of the computer code;

classifying data to be used by the program based on a usage pattern obtained during the profiling; and

initiating multiple, concurrent processes to perform the program, the multiple concurrent processes comprising a lead process executing the program non-speculatively, an understudy process executing the program non-speculatively and providing correct processing when a speculation process fails, and each speculation process executing at least a portion of the program speculatively in parallel with the lead and understudy processes and providing faster processing than the lead and understudy processes when the speculation process does not fail;

wherein the multiple, concurrent processes ensure a baseline performance that is at least as efficient as a sequential performance of the computer code.

2. A method of dynamic parallelization for programs according to claim 1 , wherein the step of classifying data comprises classifying data as either shared data, checked data or private data.

3. A method of dynamic parallelization for programs according to claim 1 , wherein the method improves performance of the computer code by integer factors when compared to the sequential performance of the computer code.

4. A method of dynamic parallelization for programs according to claim 1 , wherein the computer code was written to be run on systems having a single processor.

5. A method of dynamic parallelization for programs according to claim 1 , wherein the examining, determining and classifying steps are performed through examination of a portion of the total computer code.

6. A method of dynamic parallelization for programs according to claim 1 , wherein the method is performed in a step-by-step fashion to allow a programmer to discover hidden dependencies preventing successful parallel execution of multiple, concurrent processes.

7. A method of dynamic parallelization for programs according to claim 1 , further comprising:

displaying to a user markers of programmable hints of possible parallel regions of computer code; and

after performing the program, displaying to the user indications of conflicting memory access.

8. A method of dynamic parallelization for programs according to claim 1 , wherein the classifying step further comprises performing value-based correctness checking to permit parallel execution in the presence of true dependencies.

9. A computer program product, embodied on a non-transitory computer-readable medium, having instructions to perform steps comprising:

examining computer code of a program to be performed by a system having at least two processors;

determining a largest possible parallel region in the computer code using profiling to identify a high-level phase structure of the program and using dependence profiling to find a phase with a largest portion of run-time instructions that can be executed in parallel, wherein the profiling and dependence profiling include examining both the computer code and at least one training execution of the computer code;

classifying data to be used by the program based on a usage pattern obtained during the profiling; and

initiating multiple, concurrent processes to perform the program, the multiple concurrent processes comprising a lead process executing the program non-speculatively, an understudy process executing the program non-speculatively and providing correct processing when a speculation process fails, and each speculation process executing at least a portion of the program speculatively in parallel with the lead and understudy processes and providing faster processing than the lead and understudy processes when the speculation process does not fail;

wherein the multiple, concurrent processes ensure a baseline performance that is at least as efficient as a sequential performance of the computer code.

10. A computer program product according to claim 9 , wherein the instructions for classifying data comprises instructions for classifying data as either shared data, checked data or private data.

11. A computer program product according to claim 9 , wherein the instructions improve performance of the computer code by integer factors when compared to the sequential performance of the computer code.

12. A computer program product according to claim 9 , wherein the computer code was written to be run on systems having a single processor.

13. A computer program product according to claim 9 , wherein the instructions for examining, determining and classifying steps are performed through examination of a portion of the total computer code.

14. A computer program product according to claim 9 , wherein the instructions cause the steps to be performed in a step-by-step fashion to allow a programmer to discover hidden dependencies preventing successful parallel execution from the multiple, concurrent processes.

15. A computer program product according to claim 9 , further comprising instructions to perform steps comprising:

displaying to a user markers of programmable hints of possible parallel regions of computer code; and

after performing the program, displaying to the user indications of conflicting memory access.

16. A computer program product according to claim 9 , wherein instructions to perform the classifying step further comprise instructions to perform value-based correctness checking to permit parallel execution in the presence of true dependencies.

17. A compiling system comprising at least one processor, memory, and computer program code for performing dynamic parallelization for programs in computing systems having at least two processors, comprising:

means for examining computer code of a program to be performed by a computing system having at least two processors;

means for determining a largest possible parallel region in the computer code using profiling to identify a high-level phase structure of the program and using dependence profiling to find a phase with a largest portion of run-time instructions that can be executed in parallel, wherein the profiling and dependence profiling include examining both the computer code and at least one training execution of the computer code;

means for classifying data to be used by the program based on a usage pattern obtained during the profiling; and

means for initiating multiple, concurrent processes to perform the program, the multiple concurrent processes comprising a lead process executing the program non-speculatively, an understudy process executing the program non-speculatively and providing correct processing when a speculation process fails, and each speculation process executing at least a portion of the program speculatively in parallel with the lead and understudy processes and providing faster processing than the lead and understudy processes when the speculation process does not fail;

wherein the multiple, concurrent processes ensure a baseline performance that is at least as efficient as a sequential performance of the computer code.

18. A compiling system according to claim 17 , wherein the means for classifying data comprises means for classifying data as either shared data, checked data or private data.

19. A compiling system according to claim 17 , wherein the compiling system is configured to improve performance of the computer code by integer factors when compared to the sequential performance of the computer code.

20. A compiling system according to claim 17 , wherein the computer code was written to be run on systems having a single processor.

21. A compiling system according to claim 17 , wherein the means for examining, the means for determining and the means for classifying are configured to perform their functions through examination of a portion of the total computer code.

22. A compiling system according to claim 17 , wherein the compiling system is configured to perform such that a programmer running the compiling system can discover hidden dependencies preventing the successful parallel execution from multiple, concurrent processes.

23. A compiling system according to claim 17 , further comprising:

means for displaying to a user markers of programmable hints of possible parallel regions of computer code; and

means for after performing the program, displaying to the user indications of conflicting memory access.

24. A compiling system according to claim 17 , further comprising:

means to perform value-based correctness checking to permit parallel execution in the presence of true dependencies.