JPH0362277A - Method and mechanism for detecting deadlock - Google Patents

Abstract

PURPOSE:To easily detect a deadlock by securing a check sum of normal tokens for each round of a dummy token and deciding a deadlock based on the presence or absence of the change of the check sum and when the no-change states of the check sum are continuous in the prescribed times. CONSTITUTION:The check sum of the token data is calculated every time a dummy token has a round along a circular pipeline by a check sum calculation part of a deadlock monitor part 10 secured between a taken branch part 6a and a program storage part 5. A check sum coincidence deciding part decides whether the calculated check sum is coincident or not with the preceding check sum stored in a check sum store part. When the coincidence is confirmed between both check sums, the frequency of coincidence is counted by a counter part. When the count value of the counter part reaches a prescribed level, a deadlock deciding part decides the occurrence of a deadlock. Thus the deadlock can be easily detected.

Description

DETAILED DESCRIPTION OF THE INVENTION <Field of Industrial Application> The present invention relates to a deadlock detection method and a deadlock detection mechanism in a self-synchronous data flow microprocessor used in a supercomputer or the like.

<Prior Art> A conventional self-synchronous data blow microprocessor has a configuration as shown in FIG. In Figure 5, l
is a memory device with a processing mechanism, 2 is an arithmetic processing unit, 3 is a token branching unit, 4 is a token waiting unit, 5 is a program storage unit, 6a, 6b, 6c are token merging units, 7 is a token buffer unit, 8 is an external unit It is a token human power section, and includes from the arithmetic processing section 2 to the merging section 6b, the branching section 3, the buffer section 7, the merging section 6a,
A circular pipeline is formed which returns to the arithmetic processing section 2 via the program storage section 5, the waiting section 4, and the branching section 3.

<Problem to be solved by the invention> In the configuration shown in Figure 5, if a token gets stuck in the circular pipeline, the processor will fall into a deadlock, and the token will not transfer control to the next token, and only the same token will be sent to the circular pipeline. - A situation such as a situation where the pipeline continues to circulate (infinite loop) occurs, but since the data processing order and processing instructions per unit time in the circular pipeline are not constant, it is not easy to detect deadlock. be. Furthermore, since it is completely impossible to know from the outside that a deadlock has occurred, deadlocks have conventionally been avoided by making appropriate program settings. Therefore, when creating a program, it is necessary to perform sufficient simulation and adjust the program to prevent deadlock from occurring, which makes creating the program extremely troublesome.

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide a deadlock detection method for easily detecting the occurrence of deadlock in a self-synchronous data flow microprocessor, and a deadlock detection mechanism capable of detecting deadlock and notifying the outside. It is to provide.

<Means for Solving the Problems> In order to achieve the above object, the deadlock detection method of the present invention circulates a dummy token on a circular pipeline in a self-synchronized data flow microprocessor, and the dummy token After passing through a predetermined point in the circular pipeline, the checksum of the token passing through the above point is calculated, and then the checksum calculated this time matches the checksum calculated last time. If they match, the checksum is counted as a number of times, and if not, the number of times that the same checksum continues is determined by returning the number of times counted to the initial value. Next, the number of consecutive checksums is compared with a predetermined value, and if they are the same, it is assumed that the same token continues to circulate in the circular pipeline, and a deadlock is detected.

Further, in the deadlock detection mechanism of the present invention, in a self-synchronized data flow microprocessor, a deadlock monitoring unit is provided on a circular pipeline in which a dummy token circulates, and the deadlock monitoring unit A checksum calculation unit that calculates the checksum of the token that passes through the deadlock monitoring unit between passing through the deadlock monitoring unit and passing it again, and storing the checksum calculated by the checksum calculation unit. a checksum storage unit that determines whether the checksum output from the checksum storage unit matches the checksum newly calculated by the calculation unit; - A counter unit that counts the number of consecutive identical checksums based on the determination result by the determination unit, and a deadlock that determines a deadlock when the value counted by the counting unit becomes equal to a predetermined value. The present invention is characterized in that it includes a deadlock determination section that outputs a determination signal.

<Operation> According to the deadlock detection mechanism of the present invention, the checksum calculation section of the deadlock monitoring section calculates the checksum of token data every time the dummy token makes one round on the circular pipeline. A checksum match determining unit determines whether this calculated checksum matches the previous checksum already stored in the checksum storage unit. If it is determined that the current and previous checksums match, the counting unit counts the number of times they match. When the count value by the counting section reaches a predetermined value, the deadlock determining section determines that a deadlock has occurred, and outputs a deadlock determining signal.

<Example> Hereinafter, the present invention will be explained in detail with reference to illustrated embodiments.

FIG. 1 is a schematic diagram of an embodiment of a self-synchronous data flow microprocessor (hereinafter referred to as processor) equipped with a deadlock detection mechanism according to the present invention. The configuration of this processor is almost the same as that of the conventional processor shown in FIG. This differs from the conventional processor configuration shown in FIG. 5 in that a deadlock monitoring unit IO is added to inform the outside. In FIG. 1, the same components as those of the conventional processor in FIG. 5 are given the same reference numerals, and the explanation thereof will be omitted. In Figure 1, the white circles have, for example, 3 bytes of information, and the black circles are tokens for executing a predetermined program while going through the circular pipeline and changing values in each part of the processor. This shows a dummy token that does not participate in program execution and continues to circulate on the circular pipeline without changing its value.

FIG. 2 shows a register configuration provided in the deadlock monitoring unit IO, where the X register is used for the dummy token passing through the deadlock monitoring unit 10 until it passes through the deadlock monitoring unit 10 again. The X register is the register that calculates the checksum of the regular token passing through O.
This register is used as a stack of checksums calculated by the register.

In this embodiment, by comparing the value of the X register and the value of the I am trying to determine. More specifically, the third
As shown in the figure, if the checksum calculated this time by the X register is Xt, this value Xt is stored in the stack X register, and the next checksum X2
It is output as the comparison value Y1. therefore,
XI, X2. As long as ... have the same value, Yl.

Y2. . . . become the same value, and it is determined that the same token continues to circulate through the circular pipeline.

N13. The checksum in this embodiment is the sum of 2-byte data representing address information out of each 3-byte token.

Output value Y1 from the above X register. Y2. The number of times the dummy token passes through the deadlock monitoring section without any change in . This counting register is returned to its initial value if the value of the X register differs from the value of the X register. The value counted by the counting register CNT is compared with the reference value V stored in the register CMAX, and the reference value V
When it becomes equal to , the deadlock monitoring unit 10 determines that an infinite loop has occurred, and outputs a deadlock determination signal to the outside.

Note that if the reference value V set in the above register CMAX is set too small, deadlock detection is based on checksums, and there is a risk of misjudgment, such as determining a deadlock when it is not a deadlock. It is important to set the value to a sufficiently large value so that the probability of correctly determining that it is approximately 100%.

Next, the flow of deadlock detection processing using the processor with the above configuration will be explained according to the broached yard in FIG.

(Step St) First, at the same time as the processor starts,
A dummy token is injected into the circular pipeline.

(Step S2) In the deadlock monitoring unit IO, checksum X, X registers and counting register C
At the same time as NT is cleared, reference value V is set in register CMAX.

(Step S3) Next, the deadlock monitoring unit lO
reads the data of the token that comes in through the circular pipeline.

(Step S4) Based on the result of the token data read in step S3, it is determined whether the token that has just passed is a dummy token.

(Step S5) If it is determined in step S4 that it is not a dummy token, that is, it is a regular token, the token data read in step S3 is added to the X register and stored, and then the process returns to step S3.

Above step S3. S4. The process of S5 is repeated from when the dummy token passes through the deadlock monitoring section 10 until when it passes through the deadlock monitoring section 10 again, during which time the checksum of the regular token passing through the deadlock monitoring section 10 is determined by the X register.

(Step S6) According to the determination result in step S4, if the token input to the deadlock monitoring unit IO is a dummy token, the value of the X register (for example, X2 in FIG. 3) is set as the current checksum in the X register. It is determined whether the value is equal to the value output from the X register (the previous checksum, for example, Yl in FIG. 3).

(Step S7) If the determination result is xf-Y, the counting register CNT is set to zero, the value of the X register is rewritten to the current checksum X, and the process returns to step S3.

That is, step S6 above. In the process of S7, by comparing the value of the X register with the value of the X register, it is determined whether the checksum of the current token matches the checksum of the previous token. Since there is no flow, it is determined that no deadlock has occurred, and monitoring for deadlock continues.

(Step S8) If it is determined in step S6 that the value of the X register is equal to the value of the X register, 1 is added to the counting register CNT.

(Step S9) It is determined whether the value of the counting register CNT is equal to the value V of the register CMAX. If both values are not equal, the process returns to step S3.

That is, step S8 above. In the process of S9, when the checksums match consecutively, the number of consecutive checksums is compared with a reference value V representing a predetermined upper limit number of times,
If the above-mentioned number of times has not yet reached the upper limit, it is assumed that an infinite loop has not yet occurred, and deadlock monitoring is continued.

(Step 5IO) When the value of the counting register CNT becomes equal to the value V of the register CMAX, the deadlock monitoring unit IO considers that an infinite loop has occurred and outputs a deadlock determination signal.

As described above, according to the present embodiment, after the dummy token is inserted in step Sl, deadlock can be detected and notified to the outside by performing the processing from steps 82 to SIO described above by the deadlock monitoring unit IO. This allows you to quickly deal with deadlocks. Therefore, there is no need to make complex program adjustments as in the past.

Furthermore, the processor of this embodiment is similar to the conventional processor J described above.
Deadlock monitoring unit 1 with a very simple register configuration
Since only 0's are added, the configuration is less complicated than that of conventional processors, and therefore there is no problem in terms of cost.

Note that in this embodiment, the checksum is calculated using 2 bytes of address information of the token data, but the amount of data used for checksum calculation is not limited to this.

Furthermore, although the dummy token is input into the circular vibe line from the outside, the dummy token may be generated in, for example, the program storage unit 5 on the circular pipeline.

Also, the counting register CRT adds l when the checksums match, and the count value reaches the register CMAX.
In this configuration, it is determined that a deadlock has occurred when the predetermined value V stored in the count value register CNT is reached.However, the initial value of the count value register CNT is set to the predetermined value V, and when the checksums match, it is determined that a deadlock has occurred. It is also possible to subtract the value, and when it reaches zero, determine whether there is a deadlock. In this case, the register CMAX becomes unnecessary, so the register configuration is further simplified.

Further, the installation position of the deadlock monitoring unit IO is not limited to this embodiment, and may be on the circular pipeline.

<Effects of the Invention> As is clear from the above explanation, according to the deadlock detection method of the present invention, the checksum of the regular token is taken every round of the dummy token, and the presence or absence of a change in the checksum is used. Since deadlock is detected when the checksum remains unchanged for a predetermined number of times, deadlock can be easily detected. However, due to the use of checksums, there is a possibility that deadlocks may be detected incorrectly, but by increasing the predetermined number of times used as the deadlock judgment criterion, deadlocks can be detected with a probability close to 100%. .

Furthermore, the deadlock detection mechanism of the present invention adds a deadlock monitoring section to the conventional processor configuration, takes a checksum of the regular token every cycle of the dummy token, and
Since the presence or absence of a change in the checksum is used to detect a deadlock when the checksum remains unchanged for a predetermined number of times, deadlocks can be detected with a simple and inexpensive configuration, and can be communicated externally. I can let you know.

[Brief explanation of drawings]

FIG. 1 is a schematic configuration diagram of a processor equipped with a deadlock detection mechanism of the present invention, FIG. 2 is a diagram schematically showing the register configuration of the deadlock monitoring section shown in FIG. 1, and FIG.
FIG. 4 is a diagram showing the relationship between register values and Y register values, FIG. 4 is a diagram showing the flow of deadlock detection processing performed using the processor of FIG. 1, and FIG. 5 is a schematic configuration diagram of a conventional processor. . 1...Memory device, 2...Arithmetic processing section, 3...Token branching section, 4...Token waiting section, 5...Program storage section, 6a, 6b, 6c... Token confluence, 7
... Token buffer section, 10... Deadlock monitoring section.

Claims (2)

[Claims] (1) In a self-synchronous data flow microprocessor, a dummy token is made to circulate on a circular pipeline, and the dummy token passes through a predetermined location of the circular pipeline before passing again. Next, determine whether the checksum calculated this time matches the checksum calculated last time. If they match, count it as the number of checksum matches; if not, check the checksum. The number of consecutive checksums with the same checksum is determined by returning the number of times counted up to the initial value to the initial value. Next, the number of consecutive checksums is compared with a predetermined value, and if the number of consecutive checksums is the same, the same token is found. A deadlock detection method characterized by detecting a deadlock by assuming that the circular pipeline continues to circulate. (2) In a self-synchronous data flow microprocessor, a deadlock monitoring section is provided on a circular pipeline in which a dummy token circulates, and the deadlock monitoring section is configured to monitor the deadlock monitoring section after the dummy token passes through the deadlock monitoring section. a checksum calculation unit that calculates a checksum of a token that passes through the deadlock monitoring unit until it passes through the deadlock monitoring unit again; a checksum storage unit that stores the checksum calculated by the checksum calculation unit; and a checksum storage unit that stores the checksum calculated by the checksum calculation unit; a checksum match determination unit that determines whether the checksum output from the sum storage unit matches the checksum newly calculated by the calculation unit; and based on the determination result by the checksum match determination unit, a counting unit that counts the number of consecutive identical checksums; and a deadlock determining unit that determines deadlock when the value counted by the counting unit becomes equal to a predetermined value and outputs a deadlock determination signal. A deadlock detection mechanism characterized by comprising: