JPH06101044B2 - Deadlock avoidance execution control method - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a deadlock avoidance execution control method, and more particularly to an execution control method for avoiding deadlock in a data flow type information processing apparatus.

[Prior Art] FIG. 4 is a block diagram showing an example of a conventional data flow type information processing apparatus. Further, FIG. 5 is a diagram showing a field structure of a data packet in the information processing apparatus shown in FIG.

In FIG. 4, reference numeral 1 is a program storage means for storing a data flow program, and by the address designation based on the destination information of the input data packet in FIG. 5, the next destination information and the next instruction information are given. Are read, and the respective read information are stored in the destination field and the instruction field of the input data packet and output. Two
Waits for the data packet output from the program storage unit 1, that is, detects two different data packets having the same color information and destination information, and detects the two data packets having the same color information and destination information. Data pair generating means for storing the operand data of one data packet, for example, the contents of the data 1 field in FIG. 5 in the data 2 field of the other data packet and outputting the data. Three
Is an arithmetic processing means for performing a predetermined arithmetic processing on the data packet output from the data pair generating means 2, storing the result in the data 1 field of the input data packet, and outputting the result to the program storage means 1. In addition, 4 and 5 are data transmission paths connecting the program storage means 1 and the data pair generation means 2. 6 is a data pair generation means 2
It is a data transmission line that connects the processing unit 3 and the arithmetic processing unit 3. Further, 7 is a data transmission path connecting the arithmetic processing means 3 and the program storage means 1.

The data packet continues to rotate in the order of the program storage means 1 → the data pair generation means 2 → the arithmetic processing means 3 → the program storage means 1 → ..., whereby the arithmetic processing proceeds based on the data flow program stored in the program storage means 1. .

Further, FIG. 6 shows a part of the field structure of the stored contents in the program storage means 1. Further, FIG. 7 shows a field structure of a matching memory which is an example of the data pair generating means 2.

Conventionally, in this type of information processing device, the IPSJ 34th National Convention Lecture Collection, 2Q-7, pages 249 to 250 (1987)
As shown in FIG. 5, when a matching memory is used as the data pair generating means 2, the value obtained by performing the hash operation on the contents of the color field and the destination field shown in FIG. As a result, the physical address space of the matching memory is effectively used. However, in the method of accessing the matching memory with the hashed address, a plurality of different data having the same hash address may cause access conflict (hereinafter referred to as hash collision), and the processing may not be continued. Therefore, in the above paper, the "data replacement method" is introduced as the processing at the time of hash collision. That is, in the data exchange method, the data pair generating means 2 performs the following operation. However, before the execution of the data flow program, all the presence bits (PB) in the matching memory of the data pair generating means 2 shown in FIG.
Is set to "invalid".

(1) The hash operation is performed on the color information and the destination information of the input data packet shown in FIG. 5, and the contents of the matching memory are read using the obtained value as an address.

(2) If the PB in the read content is "invalid", the contents of the color information, the destination information and the data 1 feed in the input data packet are written in the matching memory according to the hash address, and the PB is "invalid". ", And the process ends. If PB is "valid", the following process (3) is performed.

(3) The contents of the color information and the destination information of the input data packet are compared with the contents of the color information and the destination information in the contents read from the matching memory, and the input data packet is larger in the numerical value of the contents. If it is (4), if it is smaller, (5), and if they match, the processing of (6) is performed.

(4) After setting the through packet flag of the input data packet shown in FIG. 5 to "valid", it is sent from the data pair generating means 2 and the processing is ended.

(5) A data packet is generated from the content read according to the address of the matching memory, and further,
After the through packet flag of the newly generated data packet is set to "valid", it is sent from the data pair generating means 2 and the color information, the destination information, the command information and the data 1 field of the input data packet are set. The contents are written in the matching memory according to the hash address, and the process is completed.

(6) A data pair is generated by combining the contents of the data field in the input data packet and the contents of the data field read from the matching memory, and further, color information, destination information, and destination information in the input data packet are generated. A new data packet is generated by adding the contents of the command information, the through packet flag of the newly generated data packet is set to "invalid", and then the data pair generating means 2 sends the packet and the matching memory. The PB of the relevant address of is set to "invalid", and the processing is ended.

A data packet whose through packet flag is "valid" is sent from the data pair generation means 2 and then passes through the arithmetic processing means 3 and the program storage means 1 without any processing to generate a data pair. Returning to the means 2, the above processing is performed again.

[Problems to be Solved by the Invention] FIG. 8 shows a part of an example of a data flow program. In the figure, N1 and N2 are 2-input 1-output operation nodes, D1
And D2 represent the destination information of the input data packet for nodes N1 and N2, respectively. In addition, the broken line in the figure means the data dependency. That is, in the figure, the output of node N1 is followed to reach the left input of node N2, and there is no data dependency between the output of node N1 and the right input of node N2. There is. Further, ● marks P1L and P2R in the figure are input data packets to each node. That is, the input data packet P1L for the left input of the node N1 and the node N
Generation of the input data packet P2R for the right input of 2 has been completed, in other words, for example, the data packet P1
The L waits for the arrival of the data packet P1R to be the data pair in the data pair generation means 2 when the destination information D1 and the command information of the node N1 are read from the program storage means 1.

For simplification of description, the contents of the color information of the input data packets for the nodes N1 and N2 are all the same in FIG. In FIG. 8, if the same hash address is generated from the destination information D1 and D2 and the numerical value of the content is D1> D2, the data packet P1
Regardless of the generation order of L and P2R, the above "data replacement method"
As a result, the content of the data packet P2R is finally written in the matching memory of the data pair generating means 2. On the other hand, the data packet P1L is sent from the data pair generating means 2 with the through packet flag set to "valid", and circulates in the information processing apparatus shown in FIG. 4 until the data pair for the node N2 is generated. to continue. Incidentally, the data pair for the node N2 is generated when the input data packet P2L for the left input of the node N2 is generated and input to the data pair generating means 2, but the data packet P2L is generated. Is after the operation for the node N1 is executed, that is, after the data pair for the node N1 is generated due to the data dependency relationship between the node N1 and the node N2. However, the data pair generation for node N1
Since the data packet P2R is written in the matching memory of the data pair generation means 2, it cannot happen before the data pair for the node N2 is generated.

From the above, in the situation shown in FIG.
Deadlock when the contents of the color information of the input data packet for 1 and N2 match, and the contents of the destination field D1 and D2 generate the same hash address and D1> D2 in the numerical value of the contents. It can be seen that occurs. Regarding this problem, in the above paper,
By limiting the destination information of the input data packet, that is, the method of setting the node number, deadlock caused by hash collision is avoided. That is,
When paying attention to any two 2-input 1-output nodes having data dependency in the data flow program, input to any two nodes that can be fired first based on the data dependency A method is adopted in which the content of the destination field of the data packet is set to be small. For example, in the example shown in FIG. 8, the destination information, that is, the node number is set based on the data dependency so that D1 <D2 is always satisfied.

If the data flow program to be executed does not include a loop structure, the method of the above paper can be adopted to avoid deadlock due to hash collision. However, if the data flow program includes a loop structure, the deadlock due to hash collision cannot be avoided only by the method of the above paper. FIG. 9 shows a part of an example of the data flow program including the loop structure. N in the figure
The meanings of 3, N4, D3, D4, and ● marks P3L, P4R and the meaning of the broken line are the same as in the case of FIG. In addition, a black square mark P3r in FIG. 9 represents a path from the output of the node N3 to the right input of the node N3 again, that is, one of the node inputs of the node group forming the loop. Represents the data packet that produces the right input data packet P3R of node N3. For simplicity of explanation, P3
The color information of L, P4R, and P3r are all the same. FIG. 9 shows a situation in which the input data packet for the node N4 is input to the data pair generating means 2 before the operation of the node N4 is executed and the input data pair for the node N3 is generated. In FIG. 9, nodes N3 and N4
Assuming that the same hash address is generated from the destination information D3 and D4 of the input data packet for D1, and D3> D4 in the numerical value of the content, D1> in FIG.
Deadlock caused by hash collision occurs for exactly the same reason as D2. Further, in the data flow program shown in FIG. 9, even if the same hash address is generated from the destination information D3, D4 of the input data packet for the nodes N3, N4, and D3 <D4 in the numerical value of the content. Since the data dependency relations of the nodes N3 and N4 in the data flow program have the same structure, the input data packet for the right input of the node N3 is written in the matching memory of the data pair generation means 2 and deadlocked. May occur.

From the above, when executing a dataflow program including a loop structure, it can be seen that deadlock due to hash collision cannot be avoided only by the method shown in the above paper.

The present invention has been made to solve the above problems, and provides a deadlock avoidance execution control method capable of avoiding a deadlock even when a data flow program including a loop structure is executed. With the goal.

[Means for Solving the Problem] A deadlock avoidance execution control method according to the present invention is output from a program storage means in an information processing apparatus including a program storage means, a matching memory, a data pair generation means, and an arithmetic processing. The priority information is given to the field of the data packet, and when a hash collision occurs in the data pair generation means, the priority order of the data pair generation processing is determined according to the priority information of the input data packet.

[Operation] By setting the priority information as described above, a deadlock due to a hash collision at the time of execution is avoided even for a data flow program including a loop structure.

[Examples] Hereinafter, the present invention will be described in detail based on Examples.

FIG. 1 shows the field structure of a data packet in one embodiment of the data flow type information processing apparatus. The field structure of the data packet shown in FIG. 1 is the same as the field structure of the data packet in the conventional apparatus shown in FIG. 5 except that information indicating that the data packet should be preferentially executed in the data pair generation means 2 is added. It is provided with a priority information field for storing. In addition, the block diagram of the information processing apparatus in the embodiment is
It is the same as in FIG.

Further, FIG. 2 shows a part of the field structure of the stored contents in the program storage means 1 of the information processing apparatus in the embodiment. The field structure of the stored contents of the program storage means 1 in FIG. 2 is a data packet to be preferentially executed in the data pair generation means 2 in addition to the field structure of the stored contents in the conventional apparatus shown in FIG. Priority information indicating that is added.

Further, FIG. 3 shows the field structure of the matching memory in the data pair generating means 2 of the information processing apparatus in this embodiment. The field structure of the matching memory in the data pair generating means 2 in FIG. 3 is the same as that of the matching memory in the conventional apparatus shown in FIG. It is provided with a priority information field for storing information indicating that it is present.

The program storage means 1 in this embodiment stores the data flow program shown in FIG. 2, and uses the color information and the destination information of the input data packet as an address, the next priority information, the next destination information, and the next destination information. The order command information is read out, and each of these pieces of information is stored in the priority information field, the destination field and the command field of the input data packet and output. Further, the data pair generation means 2 in the embodiment waits for the data packet output from the program storage means 1 in accordance with the following "data replacement method based on priority information" (color information and destination information match). Detection of two data packets to be performed) to generate a data pair. The function of the arithmetic processing means 3 in this embodiment is the same as that of the information processing device in the conventional example.

In the "data replacement method based on priority information", the data pair generating means 2 performs the following operation. However, it is assumed that all the presence bits (PB) in the matching memory of the data pair generating means 2 shown in FIG. 3 are set to "invalid" before the execution of the data flow program is started.

(1) A hash operation is performed on the color information and destination information of the input data packet shown in FIG. 1, and the obtained value is used as an address to read the contents of the matching memory shown in FIG.

(2) If PB in the read contents is "invalid", the contents of the color information, destination information and data 1 field of the input data packet are written in the matching memory shown in FIG. 3 according to the hash address. , PB
Is set to "valid", and the process ends. If PB is "valid", the process of (3) is performed.

(3) Contents of the priority information of the input data packet,
When both the content of the priority information in the content read from the matching memory is "valid", the process of (4) is performed. If only the contents of the priority information field in the contents read from the matching memory are "valid", the process of (5) is performed. When only the content of the priority information field of the input data packet is "valid", the process (6) is performed.

(4) The contents of the color information and the destination information of the input data packet are compared with the contents of the color information and the destination information in the contents read out from the matching memory, and the input data packet has a numerical value of the contents. If it is larger, (5) If it is smaller, (6) If they match, the processes of (7) are performed.

(5) After setting the through packet flag of the input data packet shown in FIG. 1 to "valid", it is sent from the data pair generating means 2 and the processing is ended.

(6) A data packet is generated from the contents read according to the address of the matching memory shown in FIG.
Further, after the through packet flag of the newly generated data packet is set to "valid", it is sent from the data pair generation means 2 and the input data packet shown in FIG. The information, the command information, and the contents of the data 1 field are written in the matching memory in accordance with the hash address, and the process ends.

(7) A data pair is generated by combining the contents of the field storing valid data in the input data packet shown in FIG. 1 and the contents of the data field read from the matching memory shown in FIG. Furthermore, a new data packet is generated by adding the contents of priority information, color information, destination information and command information in the input data packet. At this time, after setting the through-packet flag of the newly generated data packet to "invalid", it is sent from the data pair generating means 2 and the PB of the address in the matching memory is set to "invalid", The process ends.

A data packet whose through packet flag is "valid" is sent from the data pair generation means 2 and then processed in the arithmetic processing means 3 and the program storage means 1 as in the case of the conventional embodiment. Pass without being made,
It returns to the data pair generation means 2 and receives the above-mentioned processing again.

The data pair generation means based on the "data replacement method based on priority information" includes the "data replacement method" as is apparent from the above processing procedure.

FIG. 10 shows a development form of a data flow program for a while type loop structure, that is, a structure in which an end condition is determined before executing a loop process. In FIG. 10, 10 represents the whole while loop structure. The loop structure 10 has n inputs and m outputs. Reference numeral 11 is a main body block, which is a processing main body in the loop structure. Body block
Reference numeral 11 designates n inputs and n outputs, and as shown in FIG. 10, it is assumed that there is always a data dependency between corresponding inputs / outputs, that is, between inputs / outputs having the same input number and output number.
A condition determination block 12 determines the end of the loop from the input data and outputs "true" (continuation of loop processing) or "false" (end of loop processing). The condition decision block 12 has n inputs and 1 output, and as shown in FIG. 10, all inputs have a data dependency relationship with one output. An output selection block 13 selects a data destination according to "true / false" output from the condition determination block 12. The output selection block 13 has n + 1 inputs n
The TG in the same output selection block is a node that outputs left input data when the right input is "true" and outputs nothing when the right input is "false", that is, a node that absorbs the left input data. SW is a node that outputs the left input data to the left output when the right input is "true" and outputs the left input data to the right output when "false". Reference numeral 14 denotes a node group that is processed before the loop structure 10 is executed, that is, a node group having a data dependency relationship with the input of the loop structure 10. Also, 15 is a loop structure
The node groups to be processed after the execution processing of 10, that is, the node groups having a data dependency relationship with the output of the loop structure 10. Body block 11, condition determination block 12, output selection block 13, processing 14 before execution of loop structure, and
There is a connection relationship as shown in FIG. 10 between the processes 15 after the loop structure is completed.

In FIG. 10, 2 belonging to processing 14 before execution of loop structure
The content of the destination information for the input node is smaller than the content of the destination information for the two input nodes belonging to the loop structure 10 in the numerical value of the content, and the content of the destination information for the two input nodes belonging to the loop structure execution end processing 15 Is set to be larger than the contents of the destination information for the two input nodes belonging to the loop structure 10 in the numerical value of the contents, the two data input nodes belonging to the process 14 before the loop structure is executed by the "data replacement method". Deadlock due to hash collision does not occur between the two input nodes belonging to the loop structure 10 and between the two input nodes belonging to the process 15 after the loop structure is executed and the two input nodes belonging to the loop structure 10.

Next, in FIG. 10, the contents of the destination information for the two input nodes increase in the order of the two input nodes belonging to the main body block 11, the two input nodes belonging to the condition determination block 12, and the two input nodes belonging to the output selection block 13. Is set as follows. Due to the connection structure of the loop structure 10, the processing of the body block 11 for the next loop stage is not started until after the processing of the condition determination block 12 is completed. Deadlock due to hash collision does not occur between the two input nodes belonging to the condition determination block 12.
On the other hand, after the processing of the condition judgment block 12 is completed, the execution of the two input nodes (TG and SW) belonging to the output selection block 13 is started, but in FIG. And N19 are processed first, the left input data packet P16L for the node N16 or the right input data packet P17R for the node N17 arrives at the data pair generating means 2 and, from the destination information for the nodes N20, N16 and N17, When the same hashed address is generated, according to the "data replacement method", the data packet P16L or the data packet P17R has a higher processing priority in the data pair generation means 2 than the input data packet to the node N20. So between nodes N20 and N16 and between nodes N20 and N17,
Deadlocks due to hash collisions can occur. However, if the content of the priority information of the right input data packet P20R for the node N20 is set to "valid", the processing of the data packet P20R is prioritized in the data pair generation means 2 by the "data replacement method based on the priority information". Therefore, deadlock due to hash collision is avoided. At this time, the content of the priority information of the left input data packet P20L for the node N20 should not be set to "valid", but the content of the priority information of the data packet P20R should be set to "valid". If the data packet
It is assumed that the priority information content of P20L is set to "valid". For example, the initial input data for the loop structure 10 is input from the inputs # 2 and #n, and the data packets P17R and P2 are input.
When 0L arrives at each of the nodes N17 and N20, the data pair generation means 2 gives priority to the process for the data packet P20L by the "data exchange method based on the priority information", and a deadlock due to hash collision is generated. On the other hand, the right input data packet P20 for node N20
If the method of setting the content of the priority information of R to “valid” is adopted, the data packet P20R
Is generated only after the execution of the nodes belonging to the main body block 11 and the condition determination block 12 is completed, so that as long as the content of the priority information of the data packet P20R is set to "valid", a new one caused by hash collision is generated. Deadlock does not occur.

From the above, in the execution of the while type loop structure 10, by adopting the following execution control method, it is possible to avoid the deadlock caused by the hash collision.

(1) The data pair generation means 2 adopts the "data replacement method based on priority information".

(2) Adopt the expanded form of the loop structure 10 shown in FIG.

(3) The content of the destination information for the two input nodes belonging to the process 14 before the loop structure execution is smaller than the content of the destination information for the two input nodes belonging to the loop structure 10 in the numerical value of the content, and the loop structure execution end Later processing
The content of the destination information for the two-input node belonging to 15 is set to be larger than the content of the destination information for the two-input node belonging to the loop structure 10 in the numerical value of the content.

(4) The contents of the destination information for the two-input node are the two-input node belonging to the main body block 11, the condition determination block 12
2 input nodes belonging to, and 2 belonging to output selection block 13
Set to increase in order of input node.

(5) Two input nodes (TG
And SW) set the content of the priority information of the right input data packet to "valid", and set the content of the priority information of the input data packet for the left input data packet of the 2-input node and 2-input nodes other than the 2-input node. Set to "Disable".

In the present embodiment, it was shown that a deadlock due to a hash collision can be avoided for a data flow program in which a while type loop structure is expanded. However, by adopting a similar execution control method, do- while
Type loop structure, that is, the loop body is first processed, and then the loop end judgment is performed, or the for loop structure, that is, the initial value of the loop control variable is first set, and then the loop end judgment is performed. Done,
Further, after the processing of the loop body is performed, the deadlock due to the hash collision can be avoided even in the loop structure in which the value of the loop control variable is reset.

[Effects of the Invention] As described in detail above, if the deadlock avoidance execution control method according to the present invention is adopted in the data flow type information processing apparatus, it is impossible to continue the processing due to deadlock in the conventional apparatus. Execution without deadlock can be guaranteed in a data flow program that includes a loop structure.

[Brief description of drawings]

FIG. 1 is a diagram showing a field structure of a data packet according to an embodiment of the present invention. FIG. 2 is a diagram showing a part of the field structure of the stored contents of the program storage means in one embodiment of the present invention. FIG. 3 is a diagram showing a field structure of the matching memory of the data pair generating means in the embodiment of the present invention. FIG. 4 is a block diagram showing a configuration of an information processing apparatus to which an embodiment of the present invention and a conventional example are applied. FIG. 5 is a diagram showing a field structure of a data packet in the conventional example. FIG. 6 is a diagram showing a part of the field structure of the stored contents of the program storage means in the conventional example. FIG. 7 is a diagram showing a field structure of the matching memory of the data pair generating means in the conventional example. FIG. 8 is a diagram showing an example of the data flow program. FIG. 9 is a diagram showing an example of a data flow program including a loop structure. FIG. 10 is a diagram showing a development format of a data flow program for a while loop structure. In the figure, 1 is a program storage means, 2 is a data pair generation means, 3 is an arithmetic processing means, 4 to 7 are data transmission paths, and 10
Is a while loop structure, 11 is a main block, 12 is a condition judgment block, 13 is an output selection block, 14 is processing before loop structure execution, 15 is processing after loop structure execution, N1 to N4, N16
~ N20 is a node, D1 ~ D4 is destination information, P1L, P1R, P2R, P3L, P
3r, P4R, P16L, P17R, P20L and P20R indicate data packets.

Claims (1)

[Claims] 1. By specifying an address based on the contents of a color field (hereinafter referred to as color information) and the contents of a destination field (hereinafter referred to as destination information) of an input data packet including a tag portion and a data portion. , Information indicating data to be preferentially executed and stored as a data flow program (hereinafter referred to as priority information), next destination information and next instruction information, and the read Program storing means for storing and outputting the respective information in the priority information field, the destination field, and the instruction field (dug section) of the input data packet, and the color information and the color information of the data packet output from the program storing means. The value obtained by performing the hash operation on the next destination information is the physical address (hereinafter, A matching memory having an address space corresponding to a hash address), color information of the input data packet and the next destination information, and the content of the matching memory indicated by the hash address obtained from the input data packet. Then, according to the comparison result, a data pair is generated and output, the input data packet is written in the matching memory indicated by the hash address, the input data packet is output as it is, or the input data is output. Data pair generating means for performing any process of exchanging the content of the packet and the content of the matching memory indicated by the hash address, and decoding the command information of the data packet output from the data pair generating means, For the two operand data included in the data pair An information processing apparatus comprising: an arithmetic processing unit that performs a predetermined arithmetic process, stores the result in a data field of an input data packet, and outputs the result to the program storage unit; and in the data pair generating unit, color information or destination information. When the input data packet having a different address and the data packet stored in the matching memory have the same hash address and access conflict (hereinafter referred to as hash collision) occurs, the input data packet A deadlock avoidance execution control method characterized by avoiding a deadlock caused by a hash collision by determining a priority order of data pair generation processing according to priority information.