Programming method for concurrent programs and program supporting apparatus thereof

• US 5,860,009 A
• Filed: 04/27/1995
• Issued: 01/12/1999
• Est. Priority Date: 04/28/1994
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Nagai, Yasuo, Ohsuga, Akihiko, Ito, Satoshi, Sawashima, Nobuyuki, Uchihira, Naoshi, Tahara, Yasuyuki, Handa, Keiichi, Seki, Toshibumi, Honiden, Shinichi, Shiotani, Hideaki
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/429,782
• Time in Patent Office: 1,356 Days
• Field of Search: 395/704
• US Class Current: 717/149
• CPC Class Codes: G06F 11/362 Software debugging
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 11/3696 Methods or tools to render software testable
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

An apparatus for supporting parallelization according to the invention is characterized by comprising a serialization unit for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed, a debugging unit for debugging the sequential program and forming debugging information, and a concurrent program programming unit for performing parallelization of the debugged sequential program on the basis of the debugging information to convert the sequential program into a second concurrent program. With above configuration, the debugging unit includes a unit for introducing information associated with concurrency to the sequential program.

Claims

1. An apparatus for supporting parallelization comprising:

serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

parallelization means for performing parallelization of the sequential program to convert the sequential program into a second concurrent program; and

concurrency introduction means for introducing information associated with concurrency to the sequential program.

2. An apparatus according to claim 1, wherein said serialization means includes

execution means for executing the first concurrent program,

storing means for storing a set of execution logs generated by said execution means,

analysis means for analyzing the set of execution logs stored in said storing means and the first concurrent program, and

rearranging means for rearranging execution logs stored in said storing means on the basis of an analysis result from said analysis means.

3. An apparatus according to claim 1, wherein said concurrency introduction means includes

field data generating means for converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition to generate field data representing said field,

tuning means for tuning said field represented by the field data generated by said field data generating means, and

display means for displaying said field represented by the field data generated by said field data generating means.

4. An apparatus according to claim 1, wherein

said serialization means includes execution means for executing the first concurrent program and storing means for storing a set of execution logs generated by said execution means, and

said concurrency introduction means includes rearranging means for rearranging execution logs stored in said storing means.

10. An apparatus according to claim 4, wherein said concurrency introduction means includes

field data generating means for converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition to generate field data representing said field,

tuning means for tuning said field represented by the field data generated by said field data generating means, and

display means for displaying said field represented by the field data generated by said field data generating means.

5. An apparatus for supporting parallelization comprising:

serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

parallelization means for performing parallelization of the sequential program to convert the sequential program into a second concurrent program; and

first analysis means for analyzing dependency relations between instructions in the first concurrent program, and wherein

said parallelization means includes means for using an analysis result from said first analysis means to parallelize the sequential program, thereby converting the sequential program into the second concurrent program.

6. An apparatus according to claim 5, wherein said serialization means includes

execution means for executing the first concurrent program,

storing means for storing a set of execution logs generated by said execution means,

second analysis means for analyzing the set of execution logs stored in said storing means and the first concurrent program, and

rearranging means for rearranging execution logs stored in said storing means on the basis of an analysis result from said second analysis means.

7. An apparatus according to claim 5, further comprising:

field data generating means for converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition to generate field data representing said field,

tuning means for tuning said field represented by the field data generated by said field data generating means, and

display means for displaying said field represented by the field data generated by said field data generating means.

8. An apparatus for supporting parallelization, comprising:

serialization means for converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

concurrent structure analysis means for analyzing the concurrent structure of the predetermined section of the first concurrent program;

sequential structure analysis means for analyzing a sequential structure of a predetermined section of the sequential program;

graph information display means for displaying, as graph information, a correlation associated with the concurrent structure analyzed by said concurrent structure analysis means and a correlation associated with the sequential structure analyzed by said sequential structure analysis means;

concurrency introduction means for performing parallelization of selected sections of the sequential program to convert the sections into a partial sequential program partially having the concurrent structure; and

parallelization means for performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

9. An apparatus according to claim 8, wherein said serialization means includes

execution means for executing the first concurrent program,

storing means for storing a set of execution logs generated by said execution means,

analysis means for analyzing the set of execution logs stored in said storing means and the first concurrent program, and

rearranging means for rearranging execution logs stored in said storing means on the basis of an analysis result from said analysis means.

11. An apparatus for supporting parallelization comprising:

serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

parallelization means for performing parallelization of the sequential program to convert the sequential program into a second concurrent program;

field data generating means for converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition to generate field data representing said field;

tuning means for tuning said field represented by the field data generated by said field data generating means; and

display means for displaying said field represented by the field data generated by said field data generating means.

12. An apparatus for supporting parallelization, comprising:

serialization means for converting a first concurrent program to a plurality of sequential programs;

concurrency introduction means for introducing information associated with concurrency to the plurality of sequential programs;

debugging means for independently debugging the plurality of sequential programs; and

parallelization means for performing parallelization of the debugged plurality of sequential programs to convert the plurality of debugged sequential programs into a second concurrent program.

13. An apparatus for supporting parallelization, comprising:

serialization means for converting a first concurrent program to a plurality of sequential programs;

first analysis means for analyzing dependency relations between instructions in the first concurrent program;

debugging means for independently debugging the plurality of sequential programs; and

parallelization means for performing parallelization of the debugged plurality of sequential programs to convert the plurality of debugged sequential programs into a second concurrent program by using an analysis result from said first analysis means.

14. An apparatus for supporting parallelization, comprising:

serialization rule storing means for storing a serializing rule;

serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed in accordance with the serializing rule stored in said serializing rule storing means;

serializing rule changing means for changing the serializing rule stored in said serializing rule storing means to introduce information associated with concurrency to the sequential program;

debugging means for debugging the sequential program; and

parallelization means for performing parallelization of the sequential program, debugged by said debugging means, in which the information associated with the concurrency is introduced by said serializing rule changing means, to convert the sequential program into a second concurrent program.

15. A method of programming a concurrent program, comprising:

the step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the step of introducing information associated with concurrency to the sequential program; and

the step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program.

16. A method according to claim 15, wherein the step of introducing information includes the substep of introducing designated nondeterminism to the sequential program.

17. A method according to claim 15, wherein the step of converting a first concurrent program includes

the first substep of executing the first concurrent program,

the second substep of storing a set of execution logs generated in the first substep,

the third substep of analyzing the set of execution logs stored in the second substep and the first concurrent program, and

the fourth substep of rearranging execution logs stored in the second substep on the basis of an analysis result in the third substep.

18. A method according to claim 17, wherein the third substep includes the substep of extracting precedence constraints between processes from the set of execution logs stored in the second substep and the first concurrent program and storing the precedence constraints as an analysis result.

19. A method according to claim 15, wherein the step of introducing information includes the substep of converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition, the substep of tuning said field, and the substep of introducing the information associated with the concurrency.

20. A method according to claim 15, wherein

the step of converting a first concurrent program includes the first substep of executing the first concurrent program and the second substep of storing a set of execution logs generated in the first substep, and

the step of introducing information includes the substep of rearranging execution logs stored in the second substep to introduce the information associated with concurrency.

21. A method of programming a concurrent program, comprising:

the first step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the second step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program, wherein

the first step includes the substep of analyzing a dependency relation between instructions in the first concurrent program, and

the second step includes the substep of performing parallelization of the sequential program by using the concurrent structure of the first concurrent program.

22. A method according to claim 21, further comprising the step of introducing designated nondeterminism to the sequential program.

23. A method according to claim 21, wherein the first step includes

the first substep of executing the first concurrent program,

the second substep of storing a set of execution logs generated in the first substep,

the third substep of analyzing the set of execution logs stored in the second substep and the first concurrent program, and

the fourth substep of rearranging execution logs stored in the second substep on the basis of an analysis result in the third substep.

24. A method according to claim 23, wherein the third substep includes the substep of extracting precedence constraints between processes from the set of execution logs stored in the second substep and the first concurrent program and storing the precedence constraints as an analysis result.

25. A method according to claim 21, further comprising the step of converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition, the step of tuning said field, and the step of introducing information associated with the concurrency.

26. A method of programming a concurrent program, comprising:

the step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the step of introducing designated nondeterminism to the sequential program; and

the step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program.

27. A method of programming a concurrent program, comprising:

the first step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the second step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program,

wherein the first step includes

the first substep of converting a predetermined section of the first concurrent program having the concurrent structure into the sequential program capable of being sequentially executed,

the second substep of analyzing the concurrent structure of the predetermined section of the first concurrent program,

the third substep of analyzing a sequential structure of a predetermined section of the sequential program,

the fourth substep of displaying, as graph information, a correlation associated with the concurrent structure analyzed in the second substep and a correlation associated with the sequential structure analyzed in said third step, and

the fifth substep of performing parallelization of the selected predetermined section of the sequential program to convert the section into a partial sequential program partially having the concurrent structure, and wherein

the second step includes the substep of performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

28. A method of programming a concurrent program, comprising:

the first step of converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the second step of analyzing the concurrent structure of the predetermined section of the first concurrent program;

the third step of analyzing a sequential structure of a predetermined section of the sequential program;

the fourth step of displaying, as graph information, a correlation associated with the concurrent structure analyzed in the second step and a correlation associated with the sequential structure analyzed in the third step;

the fifth step of performing parallelization of at least two selected sections of the sequential program to convert the sections into a partial sequential program partially having the concurrent structure; and

the sixth step of performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

29. A method according to claim 28, wherein the first step includes the substep of debugging the sequential program until a desired execution result of the sequential program is obtained.

30. A method according to claim 29, wherein the first step includes

the first substep of executing the first concurrent program,

the second substep of storing a set of execution logs generated in the first substep,

the third substep of analyzing the set of execution logs stored in the second substep and the first concurrent program, and

the fourth substep of rearranging execution logs stored in the second substep on the basis of an analysis result in the third substep.

31. A method according to claim 30, wherein the third substep includes the substep of extracting precedence constraints between processes from the set of execution logs stored in the second substep and the first concurrent program and storing the precedence constraints as an analysis result.

32. A method according to claim 28, wherein the fourth step includes the substep of displaying the graph information while defining the predetermined section as a node, the correlation associated with the concurrent structure as a first arc, and the correlation associated with the sequential structure as a second arc.

33. A method according to claim 28, wherein the fifth step includes the substep of debugging the partial sequential program until a desired execution result of the partial sequential program is obtained.

34. A method according to claim 28, wherein the fifth step includes the substep of analyzing the sequential structure of a predetermined section of the partial sequential program, and further comprising a seventh step of repeating processing from the fourth step to the fifth step.

35. A method according to claim 28, wherein the first step includes

the first substep of executing the first concurrent program,

the second substep of storing a set of execution logs generated in the first substep,

the third substep of analyzing the set of execution logs stored in the second substep and the first concurrent program, and

the fourth substep of rearranging execution logs stored in the second substep on the basis of an analysis result in the third substep.

36. A method according to claim 35, wherein the third substep includes the substep of extracting precedence constraints between processes from the set of execution logs stored in the second substep and the first concurrent program and storing the precedence constraints as an analysis result.

37. A method of programming a concurrent program, comprising:

the first step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed; and

the second step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program,

wherein the first step includes

the first substep of executing the concurrent program,

the second substep of storing a set of execution logs generated in the first substep,

the third substep of analyzing the set of execution logs stored in the second substep and the first concurrent program, and

the fourth substep of rearranging execution logs stored in the second substep on the basis of an analysis result in the third substep, and

wherein the third substep includes

the substep of extracting precedence constraints between processes and their sections from the set of execution logs stored in the second substep and the first concurrent program and storing the precedence constraints as an analysis result.

38. A method of programming a concurrent program, comprising:

the step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the step of converting a flow of processes of the sequential program into a field consisting of a constraint and a transition condition;

the step of tuning said field;

the step of introducing information associated with the concurrency; and

the step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program.

39. A method of programming a concurrent program, comprising:

the first step of converting a predetermined process group of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed in accordance with a predetermined execute order;

the second step of designating some processes in the predetermined process group as a parallelization candidate for the sequential program;

the third step of changing the execution order of said process group designated in the second step to convert the sequential program into a pseudo-concurrent program;

the fourth step of converting the pseudo-concurrent program into a partial sequential program partially having a sequential structure; and

the fifth step of performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

40. A method according to claim 39, wherein the first step includes the substep of debugging the sequential program until a desired execution result of the sequential program is obtained.

41. A method according to claim 39, wherein the second step includes

the substep of analyzing the first concurrent program, and

the substep of extracting said process group as a parallelization candidate from an analysis result.

42. A method according to claim 39, wherein the third step includes the substep of debugging the pseudo-concurrent program until a desired execution result of the pseudo-concurrent program is obtained.

43. A method according to claim 39, wherein the third step includes the substep of eliminating a pseudo-concurrent behavior determined as unnecessary from an execution result of the pseudo-concurrent program.

44. A method according to claim 39, wherein the fourth step includes the substep of designating said some processes in the predetermined process group as a parallelization candidate for the partial sequential program, and further comprising

the step of repeating processing from the third step to the fourth step a predetermined number of times.

45. A method of programming a concurrent program, comprising:

the first step of converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed; and

the second step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program,

wherein the first step includes

the first substep of converting the first concurrent program into the sequential program in accordance with a serializing rule, and

the second substep of changing the serializing rule to introduce information associated with concurrency to the sequential program, and

the second step includes the substep of performing parallelization of the sequential program on the basis of debugging information and the information associated with the concurrency to convert the sequential program into a second concurrent program.

46. An apparatus for supporting parallelization comprising:

serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

parallelization means for performing parallelization of the sequential program to convert the sequential program into a second concurrent program; and

nondeterminism introduction means for introducing designated nondeterminism to the sequential program as information associated with the concurrency.

47. An apparatus according to claim 46, wherein said nondeterminism introduction means includes

execution means for executing the first concurrent program,

storing means for storing a set of execution logs generated by said execution means,

analysis means for analyzing the set of execution logs stored in said storing means and the first concurrent program, and

rearranging means for rearranging execution logs stored in said storing means on the basis of an analysis result from said analysis means.

48. An apparatus for supporting parallelization, comprising:

serialization means for converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

graph information display means for displaying, as graph information, the sequential program;

concurrency introduction means for performing parallelization of at least two selected sections of the sequential program to convert the sections into a partial sequential program partially having the concurrent structure; and

parallelization means for performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

49. An apparatus for supporting parallelization, comprising:

serialization means for converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

graph information display means for displaying, as graph information, the sequential program;

concurrency introduction means for canceling a sequential part of the sequential program and introducing designated concurrency to the sequential program by using information of the graph information display means to provide a partial sequential program; and

parallelization means for performing parallelization of the partial sequential program to convert the sequential program into a second concurrent program.

50. An apparatus for supporting parallelization, comprising:

serialization means for converting a predetermined process group of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed in accordance with a predetermined execution order;

process designating means for designating some processes in the predetermined process group as parallelization candidates for the sequential program;

simulated concurrent program conversion means for changing an execution order of said processes designated by said process designating means to convert the sequential program into a plurality of pseudo-concurrent programs;

concurrency introduction means for converting the plurality of pseudo-concurrent programs into a partial sequential program partially having a concurrent structure; and

parallelization means for performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

51. A method of programming a concurrent program, comprising:

the first step of converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the second step of displaying, as graph information, the sequential program;

the third step of introducing concurrency of at least two selected predetermined sections of the sequential program to convert the sections into a partial sequential program partially having the concurrent structure; and

the fourth step of performing parallelization of the partial sequential program to convert the partial sequential program into a second concurrent program.

52. A method of programming a concurrent program, comprising:

the first step of converting a predetermined section of a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed;

the second step of displaying, as graph information, the sequential program;

the third step of canceling a sequential part of the sequential program and introducing designated concurrency to the sequential program by using information of the graph information display means; and

the fourth step of performing parallelization of the sequential program to convert the sequential program into a second concurrent program.