JP2807026B2 - Execution reproduction method of parallel program - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a parallel program execution reproduction method in a shared-memory multiprocessor system.

[Conventional technology]

In a sequential program, an interactive and cyclic debugging method of repeatedly executing a program to be debugged while changing conditions such as a trace and a breakpoint is often used. In each debugging cycle, the programmer repeatedly interrupts and resumes the program using the step execution function and the breakpoint function of the processor, and checks the execution state while advancing the point of interest little by little.

In many cases, sequential programs can be expected to behave the same (reproduced) when the program is re-executed with the same input, so a cyclic debugging method is effective. Also, when the execution of a program is reproduced, if the execution is interrupted at the point of interest, only the instruction sequence of the route to that point is reproduced, and the execution of other instructions is suppressed (it is said that there is partial replayability). Since it can be expected, a method of advancing the point of interest step by step becomes effective.

In order to perform cyclic debugging even with a parallel program operating on a shared-memory multiprocessor, it is desired that the program have replayability and partial replayability. As illustrated in FIG. 7, these programs communicate with each other by a plurality of processes (Proc) operating on each processor reading and writing shared data placed on a main memory (shared memory). Proceed in parallel. In the drawing, a shared object (Obj) is shared data that is a unit for performing exclusive control (access to shared data by only one processor at a time) and reading and writing correctly. Each process accesses the shared data in this unit using a read / write procedure provided by the system. Each access procedure controls the order of access to shared objects provided in parallel in order to correctly realize exclusive control of a predetermined access protocol.

The fact that the program has partial replay means that only instructions necessary for replaying a specified event (a certain point (instruction) of a certain process) can be reproduced. However, in a parallel program, the behavior of an exclusive control operation on a shared object is non-deterministic, so that there is usually no replay. As a result, there is no partial replay. For this reason, conventionally, a method called a replay method has been proposed, in which the execution operation of a program is recorded, and the re-execution operation of the program is controlled using the record to make the program appear to have reproducibility.

FIG. 8 shows a functional block diagram for reproducing the execution of a parallel program in the conventional replay method. That is, in order to control the access of the user program 12 to the main memory (shared memory) 15 and reproduce the execution, an execution control unit 11, an access processing unit 13, and an exclusive control unit 14 are provided.

The exclusive control unit 14 stores the main memory 15 like the test and set instruction.
Is controlled so that only one processor can access simultaneously. The execution control unit 11 notifies the access processing unit 13 of the execution mode (monitor mode or replay mode) specified by the programmer, and then starts the execution of the program 12. In the monitor mode, the access processing unit 13 records data necessary for reproducing the execution of the program 12 when accessing the shared data. In the replay mode, access is controlled using the data recorded in the monitor mode so that the value of the shared object read by each process is equal in the monitor mode and the replay mode.

Here, if all values of the shared object read by each processor are recorded, the execution operation can be reproduced.
Generally, the time required for recording and the amount of memory are large. Therefore, instead of recording the value of the shared object, an efficient method of recording information on the access order to the shared object has been proposed. In this method, Carver
And the Instant Replay method of Leblanc et al. Hereinafter, these will be described.

In the following description, a program in which the asynchronous events for which the order relation is correctly reproduced by the replay method can be represented as a graph in FIG. 9 will be used as an example. In FIG. 9, the nodes in the graph indicate that an instruction has been issued for the creation, destruction of a process, and access to a shared object, and the bold arrow (PC arc) indicates the execution order in the process, and the thin arrow (IP arc) ) Indicates the order of execution between processes. In the nodes shown in the figure, fork and exit represent process creation and deletion instructions, respectively. created represents a state until a newly created process executes the first instruction. read, w
"rite" indicates a read / write instruction for the shared object. In general, the generation and annihilation of a process are extremely infrequent compared to access to a shared object and the processing time is long, so that the parent-child relationship of the process can be recorded without significantly affecting the execution of the program. Therefore, a method of realizing recording and reproduction of reading and writing to the shared object is important, and this is a basic technique of the replay method.

The program in FIG. 9 has three processes (proc1, proc2,
proc3) and two shared objects (obj1, obj2). FIG. 9 shows that during the execution of the program, proc1 is written to obj1 (node write obj1 in the figure), proc2 is read from obj1 (read obj1), proc1 is written to obj1 for the second time (write obj1), ... has occurred. Also, after proc1 writes to obj2, proc3 and proc3 read the value, then proc1 writes a second time to obj2, and proc2 and proc3 read the value (second write value).
Has been read out. In FIG. 9, proc2 and p
The two readings of roc3 indicate that both processes are reading the same value, so that they can be executed in parallel (that is, the order relationship is not given by thin arrows).

First, the P-sequence method will be described. FIG. 10 shows a processing flow of the access processing unit 13 for the shared object in the P-sequence method. In the case of the P-sequence method, the access processing unit 13 serializes all accesses (reading and writing) to all the shared objects in the monitor mode and the replay mode program execution. That is, in the case of the program illustrated in FIG. 9, this means that all nodes are ordered by thin arrows as shown in FIG. In the monitor mode, the program is executed in the same manner as a normal execution except for accessing the shared object. When accessing shared data, the process
First, one's own process identifier (PID) is added to one history tape (called a system history tape) placed in the main memory. As a result, at the end of the execution, a system history tape is obtained in which the PIDs of the processes that have accessed all the shared data are recorded in the order of access. When executed in the monitor mode as shown in FIG. 11, the system history tape is as shown in FIG.

In the replay mode, each process re-executes the program from the beginning, recalculates the value to be written to the shared object, and makes it available to other processes for reading. The access order to the shared object is controlled using the system history tape so that the access order is the same in the monitor mode and the replay mode. When the history tape of FIG. 12 is used for the program illustrated in FIG. 9, the instructions of all the nodes are re-executed in the same order as in FIG. FIG. 13 is a graph showing instructions to be reproduced when a breakpoint is set and the program is re-executed by a bold line frame and hatched nodes in order to clarify a difference from the present invention described later. is there.

Next, the Instant Replay method will be described. Instant
The Replay method targets programs using the CREW (Concurrent-Read-Exclusive-Write) protocol that allows a plurality of processes to read the same object at the same time in order to extract the parallelism inherent in the program. The CREW protocol allows multiple read accesses to the same object at the same time, but multiple write accesses,
Alternatively, the write access and the read access are not allowed to be performed at the same time, and the accesses are serialized. The read and write procedures consist of two routines, an entrance process and an exit process, respectively. In these routines, the system tells the number of processes (re
ader number). In the entrance management routine, re
If the number of aders is positive, write access is not allowed and the process waits until the number of readers becomes zero. Also, if at least one process is performing a write access, the access of another process is made to wait until the access is completed.

Figure 14 summarizes the read and write procedures,
4 shows a processing flow of a shared object access processing unit 13 in the t Replay method.

In the Instant Replay method, a version number indicating a writing sequence in a total order relation is introduced for each shared object, and an access sequence to each object is expressed in a semi-order relation. The system manages, for each object, a version number indicating the writing order and the number of reading processes of the version. When each process accesses a shared object, the process records the version number of the object on a history tape assigned to itself on the main memory (referred to as a process history tape). At this time,
In the case of writing to a shared object, the number of read processes of the previous version is also recorded on the process history tape.
After the end of the execution in the monitor mode, the program illustrated in FIG. 9 obtains recording data as shown in FIG. Here, a corresponds to the first write obj1 of proc1, and “V1”
Indicates the first writing to obj1, and "0" indicates no reading process at that time. b is the second write obj1 of proc1
"V2" indicates the second write to obj1, and "1" indicates the number of read processes at that time is 1 (because there is read obj1 of proc2). Similarly, c is the first write o of proc1.
bj2 and d correspond to the second write obj2. Where d
Read process number “2” of proc2 is the first read obj2 of proc2
And the first read obj2 of proc3 exists.
e corresponds to read obj1 of proc2, and the first write of proc1
The version is “V1” in response to the state of obj1. In read, the recorded data is only the version. Hereinafter, similarly, the recording data of FIG. 15 is obtained.

In the replay mode, after initializing the version number and the number of read processes for each object managed by the system, each process re-executes the program from the beginning, recalculates the value to be written to the shared object, and executes other processes. To read and use. The recorded data is used to control the access order so that the access order to the shared object is the same in the monitor mode and the replay mode.
When the recording data of FIG. 15 is used for the program illustrated in FIG. 9, the instructions of all the nodes are re-executed in the same order as in FIG. FIG. 16 is a graph in which, when a breakpoint is set and a program is re-executed, instructions to be reproduced are represented by a bold line frame and hatched nodes in order to clarify a difference from the present invention described later. is there.

In the Instant Replay method, the problem that a bottleneck occurs due to unnecessary serialization operation is solved.

[Problems to be solved by the invention]

In the P-sequence method, instructions that can be executed in parallel in the monitor mode and the replay mode are serialized.
Events that have no dependencies can be unnecessarily ordered. For this reason, there is a drawback that parallelism is impaired and a bottleneck occurs in performance. Also, there are situations in which instructions that do not need to be reproduced if they are not ordered must be reproduced first,
This method has a drawback that it is not possible to reproduce only an instruction essential for reproducing a designated event. For example, as shown in FIG. 13, when the first read obj2 of proc2 is set as a break point, proc1 is reproduced from exit, and proc3 is reproduced from created to first read obj2.

Even with the Instant Replay method, there is a disadvantage that it is not possible to reproduce only the commands necessary for reproducing the specified circumstances. That is, in the replay mode, if the execution of the program (ie, all processes) is interrupted when a certain process reaches a certain point, the state of the other processes becomes non-deterministic. If only the execution of the process that has reached the point of interest is interrupted, other processes will proceed. For this reason, there is a drawback that the programmer cannot check the execution state or make changes while gradually paying attention in the same sense as the sequential program. For example, as shown in FIG. 16, when the breakpoints are the same as in FIG. 13, proc
Both 1 and proc3 are reproduced up to exit. Also, Inst
The ant Replay method has a disadvantage that the amount of data to be recorded (version number and the number of read processes) increases as compared with the P-sequence method.

An object of the present invention is to record a relatively small amount of data,
It is an object of the present invention to provide a parallel program execution reproducing method which has a minimal effect on a program execution in a monitor mode and can reproduce only an instruction essential for reproducing a designated event.

[Means for solving the problem]

In order to achieve the above object, according to the present invention, a function of detecting two modes, a monitor mode and a replay mode, and changing an operation of an access processing unit for shared data according to the mode, and starting execution of a process. A process to be accessed by providing an execution control unit with a function and a function of sending an execution request to the process (called an access process)
A function for detecting an identifier of data and an access type (read or write), a function for an access process to send an execution request to another process, and a function for the access process to detect that an execution request is sent from another process. When the program is executed in the monitor mode, the access processing unit specifies the process identifier and the access type at the start of the shared data access by, for example, a data identifier. When the program is executed using the replay data, the recording data is referred to before the access, and the recording data is referred to before the process is accessed. An execution request is sent to the process that performs the access that should be terminated, and another By suspending execution until a process sends an execution request for the next access of the process, the correspondence between the process of writing a value to the shared data and the process of reading the shared data in the monitor mode and the replay mode becomes equal, and That is, only the access to which the execution request was sent is performed.

(Operation)

According to the present invention, in the monitor mode, a program execution operation is recorded in a form divided for each shared object, and in the replay mode, a process is performed based on the recorded data to reproduce only an operation of an instruction necessary for reproducing a designated event. Control the execution of It differs from the prior art in the structure and arrangement of the recording data and the method of controlling the execution of the program in the replay mode.

〔Example〕

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 shows a functional block diagram of one embodiment of the present invention, and the portion shown by a thick line is different from the conventional configuration of FIG. The execution control unit 11 informs the access processing unit 13 of the execution mode (monitor mode or replay mode) designated by the blogger in the same manner as in the related art, and changes the operation when accessing the shared object. In the monitor mode, the execution of the program is simply started as in the conventional case.
In the replay mode, the programmer specifies a replay stop event to the execution control unit 11 together with a replay start request. Here, the replay stop event is data for identifying a breakpoint node. The execution control unit 11 notifies the access processing unit 13 that an execution request signal is sent to the node specified by the replay stop event, and causes the execution of the program 12 to start. The execution operation of the program 12 is controlled by a function of an access processing unit 13 described later in accordance with a request-driven execution model, and only an instruction necessary for reaching a replay stop event specified by the programmer is executed. The exclusive control unit 14 receives a lock / unlock request from the access processing unit 13 and performs exclusive control so that only one processor accesses the shared data stored in the main memory 15 at the same time as in the related art. .

In the request-driven execution model, when the result of a certain node in the data flow graph becomes necessary, an execution request signal is sent to a node ahead of the input arc of that node (hereinafter simply referred to as an input node) to request execution. In the graph illustrated in FIG. 2 (FIG. 9), when an execution request signal is sent to execute a read node of proc2 to obj2, execution is controlled as follows. The node connected to the dotted arrow in FIG. 2 propagates the execution request signal according to the arrow. When the execution request signal reaches the initial node of the graph, the execution of the initial node is started. When each node finishes execution, it sends an execution end signal to the node (output node) ahead of all output arcs. The node that has received the execution request signal starts execution upon receiving an execution end signal from all input nodes.

In the request-driven execution model, all nodes theoretically control the execution timing in parallel. In the present invention, when the process accesses the shared object in the monitor mode, the access processing unit 13 uses the process identifier Pid and r / w representing the read / write type (r / w is 1-bit data. w = r indicates writing and r / w = w indicates writing) on an object history tape for each object. The same number of processes as the number of processes in the monitor mode are also created in the replay mode, the same Pid as in the monitor mode is assigned to each process, and the node executed by the process having the Pid in the monitor mode is sequentially reproduced. Exclusive control on each shared object is similar to the Instant Replay method,
Perform with CREW protocol. Hereinafter, the operation of the access processing unit 13 will be described in detail.

The access processing unit 13 has two procedures of reading and writing a shared object (shared data) in the main memory 15, but the basic control method is common. FIG. 3 shows a schematic processing flow of the access processing unit 13 common to the reading and the writing. In FIG. 3, the portion surrounded by a thick line indicates that it is different from the related art.

In the monitor mode, at the entrance processing of the access processing unit 13,
When access to the shared object in the main memory 15 is permitted, the object history tape (Pi
d, r / w). As a result, in the program illustrated in FIG. 9 (FIG. 2), after the execution is completed, as shown in FIG.
Obtain recording data for each of obj1 and obj2. Since one write data corresponds to one node in FIG. 9, this data is hereinafter referred to as a node. In this case, the node means a node corresponding to this data.

In the replay mode, the execution of the program is controlled using the recorded data, and when the first read obj2 of proc2 is set as a breakpoint (reproduction stop event), it is indicated by a bold frame and hatched nodes in FIG. Reproduce only the execution of the instruction. The feature of the control in the replay mode in the access processing unit 13 is that, as shown by the thick line frame in FIG. The point is that the execution request signal is sent, and it is checked whether execution should be continued each time the access to the shared object is completed, and the process does not proceed until the execution request signal is sent. Hereinafter, the control for this will be described in detail.

In the replay mode, replay control data as shown in FIG. 6 is managed in correspondence with the recorded data in FIG. 4, and is used for execution control during the replay. The replay control data includes the number of execution request signals (number of request tokens) provided for each process, and node state data and replay state data provided for each shared object. The number of execution request signals is a variable representing the number of unprocessed execution request signals sent to each process, and the number of execution request signals of the process proc is represented as dproc.
In the following, the process is abbreviated as P and the number of execution request signals is abbreviated as dp. The node state data is composed of variables demand and signal for recording the reception of the execution request signal and the transmission of the execution end signal for each node (when each variable has the value 1, the event has already occurred. Indicating that). The replay status data is the node that wrote the current value,
The three variables current Writer, Readers, next writer, which represent the number of nodes from which the value is read and the node to which the value is next written
Consists of The exit process of the write procedure examines the record data and the node status data of the object history tape, finds the values of these variables, and writes them.

At the start of the replay, the system executes the number of execution request signals for all processes and the node status data demand and signal for all nodes.
Is initialized to 0. When the programmer specifies a node of interest, the system sends an execution request signal to that node and the nodes of the predecessor node set. Here, the preceding node set means a node set obtained by sequentially tracing the root side of the input arc of the thin arrow in the graph of FIG. 9, and is recorded in the recording data of the shared object. It can be easily obtained from the position and the value of r / w of each node. Sending an execution request signal to a node means that the node's demand
To 1 and increase d _p of the process P by 1.

The process P starts executing the program when d _p becomes positive. Finish execution of a node d _p is decremented by 1 when, waits until execution request signal is sent if becomes 0, and continue execution if left d _p is positive.

The operation of the entry processing and exit processing routines in the reading and writing procedures in the replay mode will be described below. When each exit process is completed, the instruction of one node has been executed, and as described above, d _p is decremented by 1, and whether to wait or continue execution is determined according to the value. In the following description, "resume a node" means that if a process delays access to an object that the node has accessed, a signal is sent to that process to resume execution.
The version number v _oid of each node is the write access record data (r / w
= W) can be obtained.

(A) Read access entrance process For example, when the process proc2 issues a read instruction for the object obj2, Pid = proc2, r / w = r are found from the object history tape of the object obj2, and the object o
From the node state data of bj2, it is v
Retrieve the data with the smallest oid (called my NODE).
Next, find the input node (my Writer). my Writer
When the demand of each node is 0 for the node and the my Node of the preceding node set, an execution request signal is sent. If the current node of the object is my Writer, the value to be read is already written in the object, so that value is read. Otherwise, delay access to this object.

(B) Read access exit processing Decrease the number of Readers of the object by 1, and if it remains positive, 1
Finish execution for the nodes. Readers become 0, next Wr
Resume next writer if iter exists.

(C) Write access entry process For example, when the process proc1 issues a write command for the object obj2, Pid = proc1, r / w = w is found from the object history tape of the object obj2,
void at node of siqnal = 0 from node status data of obj2
Takes out the smallest node (my NODE). de for all nodes in the set of my Node and its predecessors
When mand is 0, an execution request signal is sent. If next write of the object is not my Node or Readers is not 0, access to the object is delayed because these conditions are satisfied. When the two conditions hold, writing to the object is performed.

(D) Write access exit processing Current Write, Readers,
Update the value of next Writer. When there is no node from which the write value is read (Readers = 0), the next writer is resumed if the next writer exists. Otherwise, all nodes from which the write value is to be read (r / w = r and v
_Resume all nodes with the same _oid ).

When the node read obj2 (first reading) of the process proc2 is specified as a break point in the program illustrated in FIG. 9, in the replay mode, the range indicated by the hatched portion in FIG. 5 is re-executed. That is, only instructions (nodes) necessary for reproducing the designated event are reproduced.

〔The invention's effect〕

As described above, according to the present invention, when a program is executed in the monitor mode, only the process identifier and the access type for the first access to the shared object are stored in the main memory for each shared object. Controlling the start, stop, and restart of each process so that when the program is executed in the replay mode by recording it in the area of the provided history tape, only the instructions necessary to reproduce any access instructions are reproduced. So that the monitor mode has a relatively small effect on program performance in parallel mode with shared data, and
There is an advantage that only instructions necessary for reproducing a designated event can be reproduced by recording only a relatively small amount of data. Here, the statement that the program performance has a relatively small effect means that there is no bottleneck due to serialization and the time required to record the execution operation in the monitor mode is short, so that the execution in the monitor mode is performed. Even if this is done, the increase in execution time is smaller than in the case of normal program execution, which means that the program execution operations are almost equal.

In the present invention, the data to be recorded in the monitor mode is only the process identifier and the access type. In general, the number of processes used in one program (or allowed by the system) is smaller than the maximum value that the version number can take, so that the amount of data to be recorded is smaller than the Instant Replay method. There is also an effect.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of one embodiment of the present invention, FIG. 2 is a diagram showing an operation example when a program is controlled to be executed by a demand-driven execution model on which the present invention is based, and FIG. Fig. 4 is a diagram showing a schematic processing flow of an access processing unit in Fig. 4, Fig. 4 is a diagram showing a configuration example of recording data, Fig. 5 is a diagram showing an example of a program execution operation in a replay mode, and Fig. 6 is a diagram of replay control data. FIG. 7 is a diagram showing a configuration example, FIG. 7 is a diagram for explaining a general operation of a parallel program, FIG. 8 is a functional block diagram for realizing a conventional program execution operation reproduction, and FIG. 9 is an example of an asynchronous execution operation of a parallel program. FIG. 10 is a diagram showing a processing flow by a conventional P-sequence method, FIG. 11 is a diagram showing an example of a program execution operation in a monitor mode of the P-sequence method, and FIG. 12 is a P-sequence Fig. 13 shows an example of the structure of recording data by the method Shows an execution reproduction operation example of a program in the replay mode P-sequence method, Fig. 14 shows a processing flow by the conventional Instant Replay method,
FIG. 15 is a diagram showing a configuration example of recording data by the Instant Replay method, and FIG. 16 is a diagram showing an example of a program execution reproduction operation in the replay mode of the Instant Replay method. 11 execution control unit, 12 user program, 13 access processing unit, 14 exclusive control unit, 15 main memory (shared memory).

Continuation of the front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06F 9/46 G06F 11/28 G06F 11/32 G06F 11/34 G06F 15/16

Claims (1)

(57) [Claims] An asynchronous reading of shared data from a main memory;
In the method of reproducing the execution of a parallel program consisting of multiple processes for writing, the monitor mode and the replay mode are instructed. When the program is executed in the monitor mode, the process identifier and access type for each access to shared data When the program is executed in the replay mode, the record data is referred to before the access, and the access to be completed before the access of the process is performed. To the shared data in the monitor mode and the replay mode by stopping execution until another process sends an execution request for the next access of the process at the end of the access in the replay mode. The correspondence between the process of writing the value and the process of reading the value is equal, A method of reproducing the execution of a parallel program, wherein only the access to which the execution request is sent is performed.