Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2001-04-27
2003-07-22
Dam, Tuan Q. (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S149000
Reexamination Certificate
active
06598222
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a programming method for concurrent programs and a supporting apparatus for parallelization.
2. Description of the Related Art
Along with the recent progress in semiconductor integrated circuit technology, complex processors or large-capacity memories with a small size can be realized at a low cost, resulting in actual use of concurrent processing systems or distributed processing systems consisting of a large number of processors. Such hardware requires a dedicated program, i.e., a concurrent program or a distributed processing program (to be referred to as a “concurrent program” hereinafter). Therefore, efficient development of a concurrent program is an important factor as in examination of an excellent algorithm.
In program development, a step of finding and correcting a bug in a program (i.e., debug) largely influences the efficiency of program development. In development of a concurrent program, however, a problem inherent to a concurrent program, which is unfamiliar in development of a sequential program, must be taken into consideration. Such a problem inherent to a concurrent program is that processes constituting a concurrent program may exhibit various behaviors depending on timings of interaction among processes, so the entire concurrent program does not properly operate. This problem based on the nature of the concurrent program is generally called “nondeterminism”.
Consider a concurrent program shown in
FIGS. 1A and 1B
.
Referring to
FIG. 1A
, a process P
1
performs initialization (init) of a shared memory M, a process P
2
performs read access (read) to the shared memory M, and a process P
3
performs write access (write) to the shared memory M. When these processes are operated in concurrent processing system which executes these processes by different processors, a total of six (
FIG. 1B
) combinations of operations are available. Normally, the system starts processing with initialization. Assume that a correct result is obtained when the program is operated in an order of processes P
1
(init)→P
2
(read)→P
3
(write) or P
1
(init)→P
3
(write)→P
2
(read). In this case, as for the four remaining combinations (e.g., P
2
(read)→P
3
(write)→P
1
(init)), since initialization is not performed first, a correct result cannot be obtained.
Whenever the concurrent program is operated, the above nondeterminism associated with the behaviors of processes change the result depending on the system status at that point of time. Therefore, unless the problem of nondeterminism is solved, the normal operation of the concurrent program cannot always be guaranteed although the concurrent program normally operates in a test mode.
In addition, it is difficult to detect a bug associated with nondeterminism as compared to a bug in a sequential program. In a sequential program, an operation can be confirmed by executing all paths in the program during a testing and debugging operation. To the contrary, in a concurrent program, paths must be executed in consideration of all matched paths (i.e., not only all paths in each process but also behaviors among processes). When the number of processes is small, as in the above example, all behaviors among the processes can be relatively easily listed. In actual program development, however, the number of processes becomes large to result in a large number of combinations thereof. For this reason, it is impossible to cover all behaviors.
As described above, debugging in concurrent program development is much more difficult than that in sequential program development. Especially, a program itself recently becomes very large to make debugging more difficult.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method of programming a concurrent program and a supporting apparatus for a parallelization, in which the concurrent program can be easily debugged and efficiently developed.
It is a gist of the present invention to temporarily convert a concurrent program into a sequential program, perform test and debugging operations for the sequential program, and restore the concurrency of the program upon completion of the testing and debugging operation. The original concurrent program is debugged as needed.
The reason why programming of a concurrent program is difficult is that “since a human thinking is substantially sequential, it is difficult to logically recognize concurrently operated objects as they are”. In the present invention, a concurrent program is temporarily converted into a sequential program, and programming or debugging (“debugging” used here means an operation including a test operation) is performed for the sequential program. The level of difficulty is the same as that of the conventional serialization. Upon completion of debugging, concurrency is automatically restored using the debugging information.
The above programming style is called “hyper serialization”. According to this “hyper serialization”, difficulty in programming by the conventional method can be solved. The basic concept of the present invention comprises the following three steps (or means).
(1) The step (means) of performing serialization of a concurrent program to generate a hyper sequential program.
(2) The step (means) of performing operations (programming, debugging, and introduction of concurrency) for the hyper sequential program.
(3) The step (means) of performing parallelization of the hyper sequential program upon completion of the operations to generate a concurrent program.
The “hyper sequential program” here means a program which is serialized while information associated with the concurrent structure of an original concurrent program is maintained.
The parallelization for supporting apparatus is characterized by comprising: serialization means for converting a first concurrent program having a concurrent structure into a sequential program capable of being sequentially executed; debugging means for debugging the sequential program and forming debugging information; and parallelization means 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. The method of programming a concurrent program, is characterized by 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 debugging the sequential program and forming debugging information; and the third step of performing parallelization of the debugged sequential program on the basis of the debugging information to convert the sequential program into a second concurrent program.
Preferable embodiments of the present invention will be listed below.
(1) Information associated with concurrency is introduced into the hyper sequential program. The information associated with the concurrency includes, e.g., information associated with intended nondeterminism (to be described later).
(2) The concurrent structure of the first concurrent program is analyzed, and parallelization of the sequential program is performed by using concurrent structure and an execution result obtained upon testing of the sequential program.
(3) The concurrent structure of a section of the first concurrent program, which section is to be converted into the sequential program, and the sequential structure of a section of the sequential program are analyzed, and a correlation associated with the concurrent structure of the first concurrent program and a correlation associated with the sequential structure of the sequential program are displayed as graph information. In display of the graph information, the graph information is displayed while defining the predetermined section as a node, the correlation associated with the concurrent structure as the first arc, and the correlation associated with the sequential structure as the second arc. Concurre
Handa Keiichi
Honiden Shinichi
Ito Satoshi
Nagai Yasuo
Ohsuga Akihiko
LandOfFree
Programming method for concurrent programs and program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programming method for concurrent programs and program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programming method for concurrent programs and program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3022754