WO2018107658A1 - Method and device for avoiding deadlock of bus, and storage medium - Google Patents

Abstract

Provided is a method for avoiding the deadlock of a bus, the method comprising: establishing a dynamic routing table (101); determining whether deadlock may occur with regard to a bus according to the dynamic routing table (102); and if deadlock may occur with regard to the bus, determining and blocking a write address command causing the deadlock (103). Also provided are a device for avoiding the deadlock of a bus, and storage medium.

Description

Method, device and storage medium for preventing bus deadlock

Cross-reference to related applications

The present application is filed on the basis of the Chinese Patent Application Serial No. No. No. No. No. No. No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No

Technical field

The present invention relates to the field of high performance chip design, and in particular, to a method, device and storage medium for preventing bus deadlock.

Background technique

AXI (Advanced eXtensible Interface) bus protocol is a high performance and high bandwidth on-chip bus protocol proposed by ARM. It is widely used in system-on-chip (SOC). The AXI bus adopts a read-write separation, address/control and data separation transmission mechanism by defining a read address channel (AR), a read data channel (R), a write address channel (AW), a write data channel (W), and a write response. Channel (B) five independent transmission channels, greatly improving transmission efficiency. In the SOC based on the AXI bus protocol, data exchange between the multi-master device (Master) and the multi-slave device (Slave) is often performed through a bus interconnect Interconnect module (also known as a bus matrix). The SOC is often composed of multiple Interconnect modules cascaded. The Interconnect module is compatible with the Outstanding Transport Access and Out-of-Order (OoO) access mechanisms supported by the AXI protocol, which improves the transmission throughput on the one hand, but also increases the risk of bus deadlock on the other hand. Especially in the bus system cascaded by multi-level Interconnect modules.

In AXI transmission, the Master marks each transmission with an ID number, and the Interconnect module passes The ID number of each Master is extended to distinguish different Masters. For the same Master, different transmissions are sent with the same ID number. Different transmissions must be performed in order, and the Slave can return the transmission of different ID numbers in OoO mode. This mechanism may form a Cyclic Dependence between handshake signals when multiple Masters access multiple Slaves at the same time, resulting in deadlocks. This type of deadlock is caused by Slave's out-of-order mechanism in response channels. This type of deadlock is called a "reverse channel deadlock." In the system composed of the existing Interconnect module cascade, the reverse channel deadlock can be circumvented by a single Slave (Single Slave) or the same ID can be used only for a single Slave (Single Slave Per ID) mechanism, wherein Single Slave Per The ID mechanism is described in CN102103560A.

At the same time, in the system composed of Interconnect module cascade, although the outstanding transmission access mechanism of AXI protocol allows the Master to issue the next write data command without waiting for the previous write data command to complete, the vast majority of the actual Slave does not support write interleave operations (in fact, the AXI 4.0 protocol also eliminates support for write interleave), that is, for the same slave, it is only allowed to receive when the write data of one transmission is received. Write data for the next transfer. In other words, although a Master can initiate multiple address/control commands on the AW channel to negotiate access to multiple slaves, a Slave is only allowed and unique, and is granted access during a transmission cycle. The Master exchanges data on the W channel. Due to the above mechanism, in the multi-master multi-Slave data exchange, there is another risk of deadlock, that is, "forward channel deadlock".

FIG. 1 is a schematic diagram of a typical "forward channel deadlock" in the prior art. At the starting time T0, Master0 sequentially sends AW01 and AW00 two write address commands to Slave1 and Slave0 in sequence; at the same time, Master1 successively sends AW10 and AW11 two write address commands to Slave0 and Slave1 in sequence; since Slave interface 0 The path delay between the interface 0 and the master interface 0 is smaller than the path delay between the SLAVE interface 1 and the master interface 0. Therefore, the AW00 is sent first, and the AW10 arrives at the Slave0 and obtains access to the master interface 0. Master interface 0 turns on the W channel and waits for the number of writes. According to the command W00; similarly, since the path delay between the Slave interface 1 and the master interface 1 is smaller than the path delay between the Slave interface 0 and the master interface 1, the AW11 is sent first, before the AW01 arrives at the Slave1, and the master is obtained. Interface 1 access rights. At this time, Master interface 1 opens the W channel and waits for W11. Because it is later than W01 in time sequence, W00 must wait for W01 to send before it can send to Master interface 0. At this time, because AW11 occupies the right Slave1 access, W01 can only wait for W11 to be sent before it can be sent to the destination Master interface 1; similarly, because it is later than W10 in chronological order, W11 must wait for W10 to send before it can be sent to the destination Master interface. 1; At this time, since AW00 still occupies access to Slave0 (W00 is always in a waiting state), W10 can only wait for W00 to be sent before it can be sent to the destination Master interface 0, so the loop waiting situation is formed. 2 is a schematic diagram of the cyclic dependency of the deadlock generated in FIG. 1. As shown in FIG. 2, W00 waits for W01, W01 waits for W11, W11 waits for W10, W10 waits for W00, and the bus transmission is deadlocked.

In order to prevent the AXI bus forward channel deadlock, the Interconnect module adopts a single effective Slave (Slave Active Slave, SAS) mechanism. The SAS mechanism stipulates that the Slave interface of the interconnect module can only initiate the next write address command after all the write data of the current transmission has been sent, thereby avoiding the "when the write address command of the subsequent write transfer arrives at the destination, The previous write data still blocks the necessary conditions for the forward deadlock on the Slave interface. Therefore, in the system of the Interconnect module of the multi-level Switch structure and the cascading of multiple Interconnect modules, a single/single Provider ID (SPI)+SAS mechanism is often used to simultaneously prevent possible Deadlock to the reverse AXI bus.

The SAS mechanism is at the expense of the transmission efficiency of the AW channel in the outstanding transport access mechanism; for some slave devices, the AW write address command is received earlier (even if the write data does not arrive at this time), it can be written The overhead process of the response operation is advanced, such as a double rate synchronous dynamic random access memory (DDR) controller. The AW write address command can be used to perform row/column interleaving calculation in advance, thereby reducing write data. W channel handshake time. In this sense, the SAS anti-deadlock mechanism reduces the data throughput of the bus transmission to a certain extent and reduces the data efficiency of the bus transmission. For SOCs that often need to cascade multiple Interconnect modules to construct a complete bus interconnect, this undoubtedly increases the difference in path delay between each master and slave device, and increases the probability of forward bus deadlock. The difference in path delay for increasing the probability of such a forward bus deadlock is not reflected in the internal path of each Interconnect module, but in the connection relationship of multiple Interconnect modules; in order to completely avoid forward deadlock The approach taken is often to add a SAS mechanism to the Slave interface of all Interconnect modules. In the actual application scenario, there is no deadlock risk in the data exchange between a large number of master and slave devices, and the bus interconnection of distributed SAS nodes cannot identify whether the ongoing access has potential deadlock risk, but only Indiscriminate multiple blocking-release-blocking operations on the AW command further reduce the transmission efficiency of the bus.

Therefore, how to effectively identify the write command that is at risk of potential deadlock, so as to block the write command causing the deadlock in time is a technical problem that needs to be solved nowadays.

Summary of the invention

In view of this, embodiments of the present invention provide a method, apparatus, and storage medium for preventing bus deadlock, so as to be able to effectively identify a write command that is in danger of a potential deadlock, thereby blocking a write command that causes a deadlock in time. .

The technical solution of the embodiment of the present invention is implemented as follows:

Embodiments of the present invention provide a method for preventing a bus deadlock, including:

Establishing a dynamic routing table, where the dynamic routing table is used to record state information of a write address command sent by the master device but not reaching the slave device slave;

Determining whether the bus will generate a deadlock according to the dynamic routing table;

If the bus generates a deadlock, the write address command that caused the deadlock is determined and blocked.

In the method as described above, the determining, according to the dynamic routing table, whether the bus generates a deadlock includes:

Generating a relationship matrix according to the relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is a first identifier, if the master does not send the location to the slave Describe an address command, where a corresponding location of the relationship matrix is a second identifier;

Determining whether the bus will generate a deadlock according to the dynamic routing table and the relationship matrix.

In the method as described above, the determining whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix includes:

Determining whether the relationship matrix is a deadlock matrix; wherein the deadlock matrix is a matrix in the relationship matrix that can cause the bus to generate a deadlock;

If the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is a simplest deadlock matrix; wherein the simplest deadlock matrix is that the deadlock matrix can cause the bus to generate a deadlock And the simplest form of matrix;

If the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix into the simplest deadlock matrix;

Determining whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix.

The method as described above, the determining whether the relationship matrix is a deadlock matrix comprises:

Determining whether there are at least two of the first identifiers in each row and each column of the relationship matrix;

If there are at least two first identifiers in each row and each column of the relationship matrix, determining that the relationship matrix is the deadlock matrix;

If at least two of the first identifiers do not exist in a row or a column of the relationship matrix, it is determined that the relationship matrix is not the deadlock matrix.

In the method as described above, if the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is the simplest deadlock matrix comprises:

If the relationship matrix is the deadlock matrix, determine whether each of the row and each column of the deadlock matrix has two first identifiers;

If there are two first identifiers in each row and each column of the relationship matrix, determining that the deadlock matrix is the simplest deadlock matrix;

If there are more than two of the first identifiers in a row or a column of the relationship matrix, it is determined that the deadlock matrix is not the simplest deadlock matrix.

In the method as described above, if the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix into the simplest deadlock matrix comprises:

个i×i阶子矩阵；其中，m、k均为大于1的整数，l＝min(m,k)，i＝2、3…l；If the m×k order deadlock matrix is not the simplest deadlock matrix, according to the m×k order deadlock matrix

i×i order submatrix; wherein m and k are integers greater than 1, l=min(m,k), i=2, 3...l;

个i×i阶子矩阵中筛选出i×i阶死锁矩阵；From the stated

The i×i order deadlock matrix is selected in the i×i order submatrices;

Determining whether the i×i order deadlock matrix is the simplest deadlock matrix;

If the i×i order deadlock matrix is not the simplest deadlock matrix, the i×i order deadlock matrix is converted into the simplest deadlock matrix.

个i×i阶子矩阵，包括：According to the method as described above, if the m×k order deadlock matrix is not the simplest deadlock matrix, according to the m×k order deadlock matrix

i×i order sub-matrices, including:

If the m×k order deadlock matrix is not the simplest deadlock matrix, the number of i rows and i columns is selected in the m×k order deadlock matrix, and the selected i row and i column numbers are selected and included. Generating the numbers in the i rows and i columns and generating the i×i order matrix;

个所述i×i阶矩阵，得到所述

个i×i阶矩阵。Select

The i×i order matrix, resulting in the

i × i order matrix.

In the method as described above, if the i×i order deadlock matrix is not the simplest deadlock matrix, converting the i×i order deadlock matrix into the simplest deadlock matrix comprises:

If the i×i order deadlock matrix is not the simplest deadlock matrix, there are more than two of the first identified rows or columns in the i×i order deadlock matrix. An identifier is set to the stated The second identifier is such that each of the row and each column of the i×i-order deadlock matrix has two first identifiers, to obtain the simplest deadlock matrix.

In the above method, the status information of the write address command includes an interface name of the source interface, an interface name of the destination interface, information of the first timing closure register slice, and information of the second timing closure register slice, wherein the The information of a timing closure register slice is information of a timing convergence register slice that the write address command needs to pass from the source interface to the transmission path of the destination interface, and the information of the second timing convergence register slice is the current time. The write address command has passed the information of the timing convergence register slice, the source interface is a slave interface connected to the master that sends the write address command, and the destination interface is the same as the command to receive the write address command. The Master interface connected to the Slave.

In the method as described above, the determining whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix comprises:

Obtaining, according to the simplest deadlock matrix and the dynamic routing table, a sending moment that the master sends the write address command to the slave;

Acquiring, according to the simplest deadlock matrix and the dynamic routing table, a delay in a path that the write address command sent by the master reaches the slave;

Determining, according to the sending moment of the write address command and the delay in the path, whether the relationship between the master and the slave meets a deadlock feature; wherein the deadlock feature is the first master first Slave sends a first write address command, and then sends a second write address command to the second slave; the second master first sends a third write address command to the second slave, and then sends a fourth write address command to the first slave. And the second write address command arrives at the second slave before the third write address command; the fourth write address command arrives at the first slave before the first write address command.

If the relationship between the Master and the Slave satisfies the deadlock feature, it is determined that the bus will generate a deadlock.

The method as described above, the obtaining, by the minimum deadlock matrix and the dynamic routing table, a sending moment that the master sends a write address command to the slave, includes:

Acquiring information of the second timing convergence register slice of the write address command in the dynamic routing table according to the simplest deadlock matrix;

Obtaining time information of the current moment;

And calculating, according to the time information of the current time and the information of the second timing convergence register slice, a transmission time at which the master sends a write address command to the slave.

The method as described above, the obtaining the delay in the path of the write address command sent by the master to the slave according to the simplest deadlock matrix and the dynamic routing table, including:

Obtaining information of the first timing convergence register slice in the dynamic routing table according to the simplest deadlock matrix;

And calculating a delay in the transmission path of the write address command sent by the master to the slave according to the information of the first timing convergence register slice.

The method as described above, determining whether the relationship between the master and the slave meets a deadlock feature according to a sending moment of the write address command and a delay in the path, including:

Determining whether the sending time of the first write address command sent by the first master to the first slave is less than the sending time of the first master sending the second write address command to the second slave;

Determining whether the sending time of the third master sending the third write address command to the second slave is smaller than the sending time of the fourth write address command sent by the second master to the first slave;

Determining whether an arrival time of the second write address command to reach the second slave is less than an arrival time of the third write address command reaching the second slave;

Determining whether an arrival time of the fourth write address command to reach the first slave is less than an arrival time of the first write address command to reach the first slave;

And sending, by the first master, the sending time of the second write address command to the second slave is greater than the sending time of the first master sending the first write address command to the first slave, and The arrival time of the second write address command reaching the second slave is less than the arrival time of the third write address command reaching the second slave; and the second master sends the fourth to the first slave The sending time of the write address command is greater than the time when the second master sends the third write address command to the second slave, and the time when the fourth write address command reaches the first slave is less than the first The time at which the write address command arrives at the first slave; determining that the relationship between the master and the slave satisfies the deadlock feature.

In the method as described above, the method determines whether the bus generates a deadlock according to the dynamic routing table, including:

Determining, according to the dynamic routing table, whether the relationship between the master and the slave exists in a pre-emptive manner; wherein, after the first sending, the sending time of the first master sending the first write address command to the first slave is smaller than the first The second master sends a sending moment of the second write address command to the first slave, and the arrival time of the first write address command reaching the first slave is greater than the arrival time of the second write address command reaching the first slave;

And if the relationship between the master and the slave exists in the pre-sending to the situation, generating an incremental relationship matrix according to the second write address command, the third write address command, and the fourth write address command; wherein The third write address command is a write command sent to the second slave and transmitting a time greater than a sending time of the second write address command; the fourth write address command is a write command having a sending time greater than the third write address command ;

Judging whether the bus will generate a deadlock according to the incremental relationship matrix.

In the method as described above, if the relationship between the master and the slave exists in the pre-starting situation, the increment is generated according to the second write address command, the third write address command, and the fourth write address command. Type relationship matrix, including:

If the relationship between the Master and the Slave exists after the first is sent to the situation, respectively a relationship between the master and the slave indicated by the second write address command, the third write address command, and the fourth write address command;

If the relationship between the master and the slave is that the master sends a write address command to the slave, setting a first identifier at a corresponding position of the incremental relationship matrix;

If the relationship between the master and the slave is that the master does not send a write address command to the slave, a second identifier is set at a corresponding position of the incremental relationship matrix.

In the method as described above, the determining whether the bus generates a deadlock according to the incremental relationship matrix includes:

Determining whether there are at least two of the first identifiers in each row and each column of the incremental relationship matrix;

If there are at least two of the first identifiers in each row and each column of the incremental relationship matrix, it is determined whether the bus will generate a deadlock.

The embodiment of the invention further provides an apparatus for preventing bus deadlock, comprising:

a pre-processing module configured to establish a dynamic routing table, where the dynamic routing table is used to record status information of a write address command sent by the master device but not yet reaching the slave device slave;

The determining module is configured to determine, according to the dynamic routing table, whether the bus generates a deadlock;

The processing module is configured to determine and block the write address command causing the deadlock if the bus generates a deadlock.

The device as described above, the determining module comprises:

a first processing unit, configured to generate a relationship matrix according to a relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is a first identifier, if the master Not sending the write address command to the slave, where a corresponding location of the relationship matrix is a second identifier;

The first determining unit is configured to determine whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix.

In the device as described above, the first determining unit is configured to determine whether the relationship matrix is a deadlock matrix; wherein the deadlock matrix is a matrix in the relationship matrix that can cause the bus to generate a deadlock;

If the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is a simplest deadlock matrix; wherein the simplest deadlock matrix is that the deadlock matrix can cause the bus to generate a deadlock And the simplest form of matrix;

If the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix into the simplest deadlock matrix;

Determining whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix.

The device as described above, the status information of the write address command includes an interface name of the source interface, an interface name of the destination interface, information of the first timing closure register slice, and information of the second timing closure register slice, wherein the The information of a timing closure register slice is information of a timing convergence register slice that the write address command needs to pass from the source interface to the transmission path of the destination interface, and the information of the second timing convergence register slice is the current time. The write address command has passed the information of the timing convergence register slice, the source interface is a slave interface connected to the master that sends the write address command, and the destination interface is the same as the command to receive the write address command. The Master interface connected to the Slave.

The device as described above, the processing module comprising:

An obtaining unit, configured to acquire, according to the simplest deadlock matrix and the dynamic routing table, a sending moment that the master sends the write address command to the slave; according to the simplest deadlock matrix and the dynamic routing Obtaining, by the table, a delay in a path that the write address command sent by the master reaches the slave;

a second determining unit, configured to determine, according to the sending time of the write address command and the delay in the path, whether the relationship between the master and the slave meets a deadlock feature; The deadlock feature is that the first master first sends a first write address command to the first slave, and then sends a second write address command to the second slave; the second master first sends a third write address command to the second slave. Sending a fourth write address command to the first slave; and the second write address command reaches the second slave before the third write address command; the fourth write address command precedes the first a write address command arrives at the first slave;

The second processing unit is configured to determine that the bus generates a deadlock if the relationship between the master and the slave satisfies a deadlock feature.

In the device, the second determining unit is configured to determine whether the sending time of the first master sending the first write address command to the first slave is smaller than the first master to the second Slave sends a sending moment of the second write address command;

Determining whether the sending time of the third master sending the third write address command to the second slave is smaller than the sending time of the fourth write address command sent by the second master to the first slave;

Determining whether an arrival time of the second write address command to reach the second slave is less than an arrival time of the third write address command reaching the second slave;

Determining whether an arrival time of the fourth write address command to reach the first slave is less than an arrival time of the first write address command to reach the first slave;

And sending, by the first master, the sending time of the second write address command to the second slave is greater than the sending time of the first master sending the first write address command to the first slave, and The arrival time of the second write address command reaching the second slave is less than the arrival time of the third write address command reaching the second slave; and the second master sends the fourth to the first slave The sending time of the write address command is greater than the time when the second master sends the third write address command to the second slave, and the time when the fourth write address command reaches the first slave is less than the first The time at which the write address command arrives at the first slave; determining that the relationship between the master and the slave satisfies the deadlock feature.

The device as described above, the determining module comprises:

The third determining unit is configured to determine, according to the dynamic routing table, whether the relationship between the master and the slave is in a pre-emptive manner; wherein, after the first sending, the first master sends the first write to the first slave. The sending moment of the address command is smaller than the sending moment of the second master sending the second write address command to the first slave, and the arrival time of the first write address command reaching the first slave is greater than the second write address command reaching the first slave. The situation of the arrival time; whether the bus will be deadlocked according to the incremental relationship matrix;

a third processing unit, configured to generate an incremental type according to the second write address command, the third write address command, and the fourth write address command if the relationship between the master and the slave exists in the pre-start situation a relationship matrix; wherein the third write address command is an address command sent to the second slave and the transmission time is greater than a transmission time of the second write address command; and the fourth write address command is a transmission time greater than the first The address command of the three-write address command.

In the device as described above, the third processing unit is configured to determine the second write address command and the third write address respectively if the relationship between the master and the slave exists in the pre-starting situation. The relationship between the command and the master and the slave indicated by the fourth write address command;

If the relationship between the master and the slave is that the master sends a write address command to the slave, setting a first identifier at a corresponding position of the incremental relationship matrix;

If the relationship between the master and the slave is that the master does not send a write address command to the slave, a second identifier is set at a corresponding position of the incremental relationship matrix.

The embodiment of the invention further provides a computer storage medium, wherein the computer storage medium stores computer executable instructions, and the computer executable instructions are used to execute the foregoing method for preventing bus deadlock.

A method, device, and storage medium for preventing bus deadlock provided by an embodiment of the present invention, the method comprising: establishing a dynamic routing table for recording state information of a write address command issued by a master but not yet reaching a slave; determining a bus according to the dynamic routing table Will there be a deadlock; if the bus will produce a deadlock, determining and blocking the write address command that caused the deadlock; this effectively identifies the write address command that is at risk of a potential deadlock, thereby specifically preventing write address commands that would cause a bus deadlock. The purpose of preventing bus deadlock is achieved, and the problem of data throughput reduction caused by adopting a unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

DRAWINGS

1 is a schematic diagram of a typical "forward channel deadlock" in the prior art;

2 is a schematic diagram of the cyclic dependency of the deadlock generated in FIG. 1;

FIG. 3 is a schematic flowchart diagram of a method for preventing bus deadlock according to an embodiment of the present invention;

4 is a schematic flowchart diagram of another method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 5 is a schematic flowchart diagram of still another method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 6 is a schematic flowchart diagram of still another method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 7 is a schematic diagram of a 3×4 order deadlock matrix according to an embodiment of the present invention;

FIG. 8 is a schematic diagram of a 3×3 matrix generated by FIG. 7 according to an embodiment of the present invention; FIG.

FIG. 9 is a schematic diagram of another 3×3 order matrix generated by FIG. 7 according to an embodiment of the present invention; FIG.

FIG. 10 is a schematic diagram of still another 3×3 order matrix generated by FIG. 7 according to an embodiment of the present invention; FIG.

FIG. 11 is a schematic diagram of still another 3×3 order matrix generated by FIG. 7 according to an embodiment of the present invention; FIG.

12 is a schematic structural diagram of a system in which an Interconnect module is cascaded according to the present invention;

FIG. 13 is a schematic flowchart of still another method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 14 is a simplified deadlock matrix according to an embodiment of the present invention; FIG.

FIG. 15 is a schematic diagram of the cyclic dependency relationship of the deadlock generated by FIG. 14 according to the embodiment; FIG.

16 is a schematic diagram of another system of cascading Interconnect modules provided by the present invention;

FIG. 17 is a flowchart of a method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 18 is still another schematic flowchart of a method for preventing bus deadlock according to an embodiment of the present invention;

FIG. 19 is another flowchart of a method for preventing bus deadlock according to an embodiment of the present invention;

20 is a schematic diagram of an emergency mechanism for preventing bus deadlock according to an embodiment of the present invention;

FIG. 21 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention;

FIG. 22 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention;

FIG. 23 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention;

FIG. 24 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention;

FIG. 25 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention.

detailed description

FIG. 3 is a schematic flowchart of a method for preventing a bus deadlock according to an embodiment of the present invention. As shown in FIG. 3, the method provided in this embodiment includes the following steps:

Step 101: Establish a dynamic routing table, where the dynamic routing table is used to record status information of a write address command sent by the master but not yet reach the slave.

Specifically, the step 101 of establishing a dynamic routing table may be implemented by a device that prevents bus deadlock. It should be noted that the dynamic routing table is an ever-changing routing table, which records the status information of the write address command sent by the master but has not yet reached the slave. If at some point in the future, the master sends a write address command has arrived. The corresponding Slave, then the status information of the write address command is deleted from the dynamic routing table.

Step 102: Determine, according to the dynamic routing table, whether the bus will generate a deadlock.

Specifically, step 102 determines whether the bus will generate a deadlock according to the dynamic routing table, and may be implemented by a device that prevents bus deadlock. According to the dynamic routing table, it is determined whether the bus will generate a deadlock. The dynamic routing table obtains the status information of the write address command sent by the master but has not yet reached the slave, and determines whether the bus will generate a deadlock according to the obtained status information of the write address command issued by the master but not yet reaching the slave.

Step 103: If the bus generates a deadlock, determine and block the write address command that caused the deadlock.

Specifically, if the bus generates a deadlock in step 103, determining and blocking the write address command causing the deadlock can be implemented by a device that prevents the bus from being deadlocked.

The method for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording status information of a write address command issued by the master but not yet reaching the slave; determining whether the bus will generate a deadlock according to the dynamic routing table; Generate a deadlock, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock. Thereby, the purpose of preventing the bus deadlock is achieved, and the problem of reducing the address throughput caused by adopting the unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

FIG. 4 is a schematic flowchart of another method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 4, the method provided in this embodiment includes the following steps:

Step 201: The device for preventing bus deadlock establishes a dynamic routing table. The dynamic routing table is used to record state information of a write address command sent by the master but not yet reach the slave.

Step 202: The device for preventing bus deadlock generates a relationship matrix according to the relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is the first identifier, if the master does not send the write address to the slave The corresponding position of the command and relationship matrix is the second identifier.

It should be noted that the relationship matrix is a matrix of relationships between multiple masters and multiple slaves, that is, which masters of all masters send a matrix of write address commands to all slaves in all slaves, if the number of masters is 4, Slave The number is 5, 4 Masters are represented as Master0, Master1, Master2 and Master3, respectively, and 5 Slaves are respectively represented as Slave0. Slave1, Slave2, Slave3, and Slave4, then the relationship between the four Masters and the five Slaves can be represented by a 4×5 relational matrix (Master and Slave4 represent the rows and columns of the relational matrix, respectively), if Master1 sends a write to Slave2. The address command, then the position of the second row and the third column in the relation matrix is represented by the first identifier.

It should also be noted that in the relation matrix, the first identifier is generally represented by a number "1", and the second representation is generally represented by a number "0".

Step 203: The device for preventing bus deadlock determines whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix.

It should be noted that determining whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix means obtaining the write address of the master but not yet reaching the slave from the dynamic routing table according to the relationship between the master and the slave represented by the relationship matrix. The status information of the command determines whether the bus will generate a deadlock based on the obtained status information of the write address command issued by the master but not yet reaching the slave.

Step 204: If the bus generates a deadlock, the device that prevents the bus deadlock determines and blocks the write address command that caused the deadlock.

It should be noted that the explanation of the same steps or concepts in the other embodiments may refer to the descriptions in other embodiments, and details are not described herein again.

The method for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording state information of a write address command sent by the master but not yet reaching the slave; generating a relationship matrix according to the relationship between the master and the slave; The table and relationship matrix determine whether the bus will generate a deadlock; if the bus generates a deadlock, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock, and then Targeted blocking of the write address command that will cause the bus deadlock, thus achieving the purpose of preventing bus deadlock, while avoiding the problem of reducing the address throughput caused by the unified anti-deadlock mechanism, and improving the address transmission of the bus effectiveness.

FIG. 5 is a schematic flowchart of a method for preventing a bus deadlock according to an embodiment of the present invention. As shown in FIG. 5, the method provided in this embodiment includes the following steps:

Step 301: The device for preventing bus deadlock establishes a dynamic routing table. The dynamic routing table is configured to record state information of a write address command sent by the master but not yet reach the slave.

Step 302: The device for preventing bus deadlock generates a relationship matrix according to the relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is the first identifier, and if the master does not send the write address to the slave The corresponding position of the command and relationship matrix is the second identifier.

Step 303: The device for preventing bus deadlock determines whether the relationship matrix is a deadlock matrix; wherein the deadlock matrix is a matrix in the relationship matrix that can cause the bus to deadlock.

Specifically, determining whether the relationship matrix is a deadlock matrix includes: determining whether each row and each column of the relationship matrix respectively have at least two first identifiers; if each row and each column of the relationship matrix respectively have at least two first identifiers, The relationship matrix is determined to be a deadlock matrix; if there is no at least two first identifiers in a row or a column of the relationship matrix, it is determined that the relationship matrix is not a deadlock matrix.

It should be noted that, if the first identifier is represented by a number “1” and the second identifier is represented by a number “0”, determining whether the relationship matrix is a deadlock matrix includes: determining whether each row and each column of the relationship matrix respectively exist at least 2 The number is "1"; if there are at least two numbers "1" in each row and each column of the relationship matrix, the relationship matrix is determined to be a deadlock matrix; if there is no at least two numbers "1" in one row or column of the relationship matrix, Make sure the relationship matrix is not a deadlock matrix. If it is determined that a relationship matrix is not a deadlock matrix, then the relationship between multiple masters and multiple slaves that the relationship matrix reacts does not cause a bus deadlock. Correspondingly, the write address command sent by the master to the slave in the relation matrix is not blocked.

Step 304: If the relationship matrix is a deadlock matrix, the device for preventing the bus deadlock determines whether the deadlock matrix is the simplest deadlock matrix; wherein the simple deadlock matrix is a deadlock matrix, the bus can be deadlocked, and the form The simplest matrix.

Specifically, if the relationship matrix is a deadlock matrix, it is determined whether the deadlock matrix is the simplest deadlock matrix. The method includes: if the relationship matrix is a deadlock matrix, determining whether each row and each column of the deadlock matrix have two first identifiers; if each row and each column of the relationship matrix has two first identifiers, determining a deadlock matrix It is the simplest deadlock matrix; if there are more than two first identifiers in a row or a column of the relation matrix, it is determined that the deadlock matrix is not the simplest deadlock matrix.

It should be noted that, if the first identifier is represented by a number “1” and the second identifier is represented by a number “0”, determining whether the deadlock matrix is the simplest deadlock matrix includes: determining whether each row and each column of the deadlock matrix is There are 2 numbers "1"; if there are 2 numbers "1" in each row and column of the relationship matrix, it is determined that the deadlock matrix is the simplest deadlock matrix; if there are more than 2 rows or columns of the relationship matrix The number "1" determines that the deadlock matrix is not the simplest deadlock matrix.

Step 305: If the deadlock matrix is not the simplest deadlock matrix, the device for preventing bus deadlock converts the deadlock matrix into a simple deadlock matrix.

Step 306: Determine whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix.

Step 307: If the bus generates a deadlock, the device that prevents the bus deadlock determines and blocks the write address command that caused the deadlock.

It should be noted that the explanation of the same steps or concepts in the other embodiments may refer to the descriptions in other embodiments, and details are not described herein again.

The method for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording state information of a write address command issued by the master but not yet reaching the slave; generating a relationship matrix according to the relationship between the master and the slave; determining the relationship matrix Whether it is the simplest deadlock matrix; if the relational matrix is not the simplest deadlock matrix, the relational matrix is converted into the simplest deadlock matrix; according to the dynamic routing table and the simplest deadlock matrix, it is judged whether the bus will generate a deadlock; Generate a deadlock, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock. Thereby, the purpose of preventing the bus deadlock is achieved, and the problem of reducing the address throughput caused by adopting the unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

FIG. 6 is a schematic flowchart of still another method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 6, step 305 is included in the method provided in this embodiment. The following steps:

个i×i阶子矩阵；其中，m、k均为大于1的整数，l＝min(m,k)，i＝2、3…l。Step 305a, if the m×k order deadlock matrix is not the simplest deadlock matrix, the device for preventing bus deadlock is obtained according to the m×k order deadlock matrix.

i×i order submatrices; wherein m and k are integers greater than 1, l=min(m,k), i=2, 3...l.

个i×i阶子矩阵包括：在m×k阶死锁矩阵中选择i行和i列的数，从所选择的i行和i列的数中选取同时包含在i行和i列中的数生成i×i阶矩阵；选取

个i×i阶矩阵，得到

个i×i阶矩阵。Specifically, according to the m×k order deadlock matrix

The i×i order sub-matrices include: selecting the number of i rows and i columns in the m×k order deadlock matrix, and selecting from the selected i rows and i columns, and simultaneously included in the i rows and i columns. Number i×i order matrix; selection

i×i order matrix, get

i × i order matrix.

It should be noted that FIG. 7 is a schematic diagram of a 3×4 order deadlock matrix according to an embodiment of the present invention. It is assumed that the first identifier is represented by a number “1”, and the second identifier is represented by a number “0”. When i=3, As shown in FIG. 7, the number of three columns in three rows and four columns is selected in the 3×4 order deadlock matrix, and the number included in the selected three rows and three columns is selected from the selected numbers. A 3×3 order matrix is generated, and the number of four columns in the deadlock matrix is traversed, and a total of four 3×3 order matrices are generated. Specifically, FIG. 8 is a schematic diagram of a 3×3 matrix generated by FIG. 7 according to an embodiment of the present invention, and FIG. 9 is a schematic diagram of another 3×3 matrix generated by FIG. 7 according to an embodiment of the present invention. FIG. 10 is a schematic diagram of still another 3×3 matrix generated by FIG. 7 according to an embodiment of the present invention. FIG. 11 is a schematic diagram of another 3×3 matrix generated by FIG. 7 according to an embodiment of the present invention. As shown in FIG. 8, the number of the first column, the second column, and the third column in the three rows and four columns of the 3×4 order deadlock matrix is selected, and the selected number is selected in three rows and four columns. The number in the first column, the second column, and the third column of the number generates a 3×3 order matrix; as shown in FIG. 9, the first of the three rows and four columns of the 3×4 order deadlock matrix is selected. The number of the column, the third column, and the fourth column is selected from the selected number and the number of the first column, the third column, and the fourth column included in the three rows and four columns simultaneously generates a 3×3 order a matrix; as shown in FIG. 10, the number of the first column, the second column, and the fourth column in the three rows and four columns of the 3×4 order deadlock matrix is selected, from the selected number Select a number in the first column, the second column, and the fourth column of the three rows and four columns to generate a 3×3 matrix; as shown in FIG. 11, select a 3×4 order deadlock matrix. The number of the second column, the third column, and the fourth column in the three rows and four columns, and the second column, the third column, and the fourth column of the three rows and four columns are selected from the selected number. The number in the number produces a 3 × 3 order matrix.

个i×i阶子矩阵中筛选出i×i阶死锁矩阵。Step 305b, the device for preventing bus deadlock from

The i×i order deadlock matrix is selected in the i×i order submatrices.

个i×i阶子矩阵中筛选出i×i阶死锁矩阵是指从

个i×i阶子矩阵中筛选满足每一行和每一列至少存在2个第一标识的i×i阶子矩阵作为i×i阶死锁矩阵。Specifically, from

The i×i order deadlock matrix is selected from the i×i order submatrices.

In the i×i order submatrix, an i×i order submatrix satisfying at least two first identifiers in each row and each column is selected as an i×i order deadlock matrix.

Step 305c: The device for preventing bus deadlock determines whether the i×i-order deadlock matrix is the simplest deadlock matrix.

Specifically, determining whether the i×i-order deadlock matrix is the simplest deadlock matrix is to see whether each row and each column of the i×i-order deadlock matrix exists and only two first identifiers exist.

Step 305d: If the i×i order deadlock matrix is not the simplest deadlock matrix, the device for preventing bus deadlock converts the i×i order deadlock matrix into the simplest deadlock matrix.

Specifically, if the i×i-order deadlock matrix is not the simplest deadlock matrix, the redundant first identifier in the row or column in which the i×i-order deadlock matrix has more than two first identifiers is set to the second. The identifier is such that there are only two first identifiers for each row and each column of the i×i-order deadlock matrix, and the simplest deadlock matrix is obtained.

个标识置位后的i×i阶死锁矩阵，然后在这些

个标识置位后的i×i阶死锁矩阵中筛选满足每一行和每一列存在且只存在2个第一标识的死锁矩阵，从而得到i×i阶最简死锁矩阵。It should be noted that if the i×i order deadlock matrix is not the simplest deadlock matrix (ie, the number NE of the first identifier is greater than 2i), the i×i order deadlock matrix is actually converted into the simplest deadlock matrix. In the process, the i×i-order deadlock matrix after a certain first identifier is set to the second identifier by the exhaustive method is listed one by one, and for an i×i-order deadlock matrix, it can be listed.

Identifies the set i × i order deadlock matrix, then in these

The deadlock matrix satisfying the existence of each row and each column and having only 2 first identifiers is selected in the i×i-order deadlock matrix after the flag is set, thereby obtaining an i×i-order simplest deadlock matrix.

It should also be noted that the same steps or concepts in the other embodiments are explained in this embodiment. Reference may be made to the description in other embodiments, and details are not described herein again.

In the method for preventing bus deadlock provided by this embodiment, when the m×k order deadlock matrix is not the simplest deadlock matrix, the m×k order deadlock matrix is processed step by step, and finally the i×i order is the simplest dead. The lock matrix, according to the dynamic routing table and the simplest deadlock matrix to determine whether the bus will generate a deadlock; if the bus will generate a deadlock, determine and block the write address command causing the deadlock; this can effectively identify the occurrence of the The write address command of the potential deadlock risk, in turn, specifically blocks the write address command that will cause the bus deadlock, thereby achieving the purpose of preventing the bus deadlock, and avoiding the data throughput caused by the unified anti-deadlock mechanism. The problem of reduction increases the data transmission efficiency of the bus.

Further, the status information of the write command includes an interface name of the source interface, an interface name of the destination interface, information of the first timing convergence register slice, and information of the second timing convergence register slice, wherein the information of the first timing convergence register slice is The information of the timing convergence register slice that the address command is to pass from the source interface to the transmission path of the destination interface, and the information of the second timing convergence register slice is the information of the timing convergence register slice that the current address write address command has passed, and the source interface is The slave interface connected to the master that sends the write address command. The destination interface is the master interface connected to the slave that receives the write address command.

It should be noted that, in the actual situation, the timing slice of the Interconnect module and the First-In First-Out (FIFO) structure are often uniquely numbered for convenient management. The information of the first timing closure register slice and the information of the second timing closure register slice may be represented by delay coordinates. Specifically, FIG. 12 is a schematic structural diagram of an Interconnect module cascaded according to the present invention. As shown in FIG. 12, the Interconnect module cascaded system has two Interconnect modules (bus matrix), which are a bus matrix 0 and a bus matrix respectively. 1. In the bus matrix 0, a Swich structure is composed of Slave interface 00, Slave interface 01, Master interface 00 and Master interface 01; in the bus matrix 1, it is composed of Slave interface 10, Slave interface 11, Master interface 10 and Master interface 11. A Swich structure. Master has 3 Master0, Master1 and Master2, Slave also has three, Slave0, Slave1 and Slave2; Master0 sends a write command to Slave0 through bus matrix 0, and sends a write address command to Slave1 through bus matrix 0 and bus matrix 1; Master1 sends a write command to Slave0 through bus matrix 0, and sends a write command to Slave1 through bus matrix 0 and bus matrix 1; Master2 sends write commands to Slave1 and Slave2 through bus matrix 1, respectively. There is a timing convergence register slice (timing convergence register slice 0) in Slave interface 00, a timing convergence register slice (timing convergence register slice 1) exists in Master interface 00, and a timing closure register slice exists in Master interface 01 (timing convergence register) Slice 2); there is a timing closure register slice (timing convergence register slice 3) in the Slave interface 10, and a timing closure register slice (timing convergence register slice 4) exists in the master interface 10, and the slave interface 01 is in the path of the master interface 00. There is a timing closure register slice (timing convergence register slice 5), a timing closure register slice (timing convergence register slice 6) exists in the master interface 11, and a timing closure register slice (timing convergence register slice 7) exists in the slave interface 11. Assume that the write address command sent by Master0 to Slave0 arrives at Slave interface 00 at the current time. The write address command sent by Master0 to Slave1 reaches Master interface 01. The write address command sent by Master1 to Slave0 reaches Master interface 00, and the write address command sent by Master1 to Slave1. Upon reaching Master interface 01, the write address command sent by Master2 to Slave1 arrives at Slave interface 11, and the write address command sent by Master2 to Slave2 arrives at Slave interface 11. Therefore, the dynamic routing table established according to the system of the Interconnect module cascade shown in FIG. 12 is as shown in Table 1, wherein the delay coordinate Regj(i) represents the information of the first timing convergence register slice and the second timing convergence register slice. Information, i indicates the sequence number of the converged register slice on the path (starting from 0), and j indicates the label of the corresponding timing closure register slice.

Table 1

Further, based on the foregoing embodiment, FIG. 13 is a schematic flowchart diagram of another method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 13, the bus is determined according to a dynamic routing table and a simple deadlock matrix. Will there be a deadlock, including:

Step 401: The device for preventing bus deadlock acquires, according to the simple deadlock matrix and the dynamic routing table, a sending moment at which the master sends a write address command to the slave.

Specifically, the step 401 includes: acquiring information of the second timing convergence register slice of the write address command in the dynamic routing table according to the simplest deadlock matrix; acquiring time information of the current time; and converge according to the current time information and the second timing The information of the register slice calculates the transmission time at which the Master sends a write address command to the slave.

It should be noted that, in an Interconnect module or a system that is cascaded by multiple Interconnect modules, the delay caused by each timing convergence register slice is certain, so it is only necessary to obtain the current time information and then obtain the current time. By writing the information of the timing-converged register slice that the address command has passed (ie, the information of the second timing-converged register slice), the transmission timing of the write-write address command can be reversed.

Step 402: The device for preventing bus deadlock acquires a delay in a path of the write address command sent by the master to the slave according to the simple deadlock matrix and the dynamic routing table.

Specifically, the step 402 includes: acquiring information of the first timing convergence register slice in the dynamic routing table according to the simplest deadlock matrix; and calculating the master according to the information of the first timing convergence register fragment. The delay in the path of the sent write address command to the slave.

It should be noted that, according to the information of the first timing convergence register slice of the write address command, the information of the timing convergence register slice that the write address command needs to pass in the transmission path can be obtained, and the register fragment is converge according to the timing that needs to pass in the transmission path. The information can be used to calculate the delay of the write address command in the transmission path.

Step 403: The device for preventing the bus deadlock determines whether the relationship between the master and the slave meets the deadlock feature according to the sending moment of the write address command and the delay in the path; wherein the deadlock feature is the first master first a slave sends a first write address command, and then sends a second write address command to the second slave; the second master first sends a third write address command to the second slave, and then sends a fourth write address command to the first slave; and The second write address command arrives at the second slave before the third write address command; the fourth write address command arrives at the first slave before the first write address command.

It should be noted that the arrival time of the write address command can be calculated according to the transmission time of the write address command plus the delay in the transmission path of the write address command.

Specifically, the step 403 includes: determining whether the sending time of the first master sending the first write address command to the first slave is smaller than the sending time of the first master sending the second write address command to the second slave; determining that the second master is the second Whether the sending time of the third write address command sent by the slave is smaller than the sending time of the fourth write address command sent by the second master to the first slave; determining whether the arrival time of the second write address command reaching the second slave is less than the third write address command When the arrival time of the second slave is reached, it is determined whether the arrival time of the fourth write address command to reach the first slave is less than the arrival time of the first write address command to reach the first slave; if the first master sends the second write address command to the second slave The sending time is greater than the sending time at which the first master sends the first write address command to the first slave, and the arrival time of the second write address command reaching the second slave is less than the arrival time of the third write address command reaching the second slave, and The second master sends a fourth write address command to the first slave, and the second master sends the third write address to the second slave. The time of the command, and the time at which the fourth write address command reaches the first slave is less than When the first write address command reaches the first slave, it is determined that the relationship between the Master and the Slave satisfies the deadlock feature. FIG. 14 is a simplified deadlock matrix according to an embodiment of the present invention. Taking FIG. 14 as an example, the deadlock feature is:

T ₀₃ >T ₀₁

T ₀₃ +D ₀₃ <T ₂₃ +D ₂₃

T ₁₀ >T ₁₂

T ₁₂ +D ₁₂ <T ₃₂ +D ₃₂

T ₂₀ >T ₂₃

_{T 20 + D 20 <T 10} + D 10

T ₃₁ >T ₃₂

T ₃₁ +D ₃₁ <T ₀₁ +D ₀₁

Where T _ij represents the transmission timing of Masteri's write address command to Slavej, and D _ij represents the delay of the write address command sent by Masteri to Slavej in the transmission path. FIG. 15 is a schematic diagram of the cyclic dependency relationship of the deadlock generated in FIG. 14 according to the embodiment. As shown in FIG. 15, W10 waits for W20, W20 waits for W23, W23 waits for W03, W03 waits for W01, W01 waits for W31, and W31 waits for W32. W32 waits for W12, W12 waits for W10, and the bus transmission is deadlocked.

It should also be noted that the relationship between the Master and the Slave represented by any M*N-order deadlock matrix may satisfy the deadlock feature. The manifestation of the deadlock feature varies with the order of the deadlock matrix and the Master and The specific relationship between Slave is different.

Step 404: If the relationship between the Master and the Slave satisfies the deadlock feature, the device that prevents the bus deadlock determines that the bus will generate a deadlock.

It should be noted that the explanation of the same steps or concepts in the other embodiments may refer to the descriptions in other embodiments, and details are not described herein again.

The method for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording state information of a write address command issued by the master but not yet reaching the slave; generating a relationship matrix according to the relationship between the master and the slave; determining the relationship matrix Whether it is the simplest deadlock matrix; Array is not the simplest deadlock matrix, the relation matrix is converted into the simplest deadlock matrix; according to the dynamic routing table and the simplest deadlock matrix to determine whether the bus will generate a deadlock; if the bus will produce a deadlock, determine and block the deadlock Write address command; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock, thus achieving the purpose of preventing bus deadlock. At the same time, the problem of reducing the data throughput caused by adopting the unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

Further, the dynamic routing table may further include information of the aggregation interface, where the aggregation interface is an interface where two or more transmission paths are aggregated. On the basis of the above Table 1, the information of the convergence interface and the third timing convergence access information are added, wherein the information of the third timing convergence register slice is the information of the timing convergence register slice that the write address command reaches the convergence interface. The dynamic routing table established according to the system in which the Interconnect module is cascaded as shown in FIG. 12 is as shown in Table 2.

Table 2

The new write address command if possible may exist in the past with the dynamic routing table The address command has an effect such that the delay of the transmission path that could have been calculated by the information of the first timing-converged register slice becomes uncontrollable. Specifically, FIG. 16 is a schematic diagram of another Interconnect module cascaded according to the present invention. As shown in FIG. 16, at the current moment, AW11 arrives at the position in the figure; at this time, Master2 sends AW20 to Slave1 because of the transmission path. The delay, AW20 will arrive at the shadow-filled Master interface in the picture before AW11, so the path between AW11 and the interface will be blocked, and the delay of AW11 reaching the destination Slave1 becomes uncontrollable. Therefore, it is necessary to determine whether the new write address command affects the relationship between the current write address commands: if the new write address command and the current write address command are aggregated on a certain aggregation interface, it is necessary to judge the new according to the dynamic routing table. Whether the write address command advances to the aggregation interface in advance (or at the same time) the current write address command, and if so, updates all previous write address commands of the aggregation interface on the transmission path to the delay in the transmission path to the original transmission. The sum of the delay in the path and the increment T, where the increment T is preset according to the actual situation; otherwise, the delay in the transmission path of the new write address command is set to ∞; then it is judged whether the bus will die. lock.

Further, the method for preventing bus deadlock provided by the present invention may further comprise setting a time margin for preventing deadlock, thereby improving the robustness of the anti-deadlock mechanism for preventing the bus deadlock method. Correspondingly, according to the routing table and the relationship matrix, it is determined whether the system bus will be deadlocked, including: determining whether the system bus will deadlock according to the dynamic routing table, the time margin for preventing deadlock, and the relationship matrix.

It should also be noted that in a system with multiple complex Interconnect modules cascaded, the dynamic routing table dimension increases sharply, which directly leads to a geometric multiplication of the decision complexity of the simplest deadlock subarray. In this case, the conditions for the master to send the write address command can be appropriately tightened. For example, the same master can only initiate write transmission to M slaves at the same time, thereby reducing the dimension of the dynamic routing table and making the computational complexity controllable. Within the scope. At the same time, it may be considered to decompose and reduce the entire cascading system according to the level of transmission efficiency requirements, so as to reduce the computational complexity: the subsystem with high transmission efficiency is required to use the bus deadlock method provided by the present invention; For subsystems with looser transmission efficiency requirements, the NIS400 inherent SAS machine can be used. Finally, the NIC400 can also be used to apply the outstanding transfer access mechanism between the AW channel and the W channel inherent in the master interface of a single matrix (up to only two AW handshakes are successful but the W channel does not fully transmit the successful transmission). Achieve the decomposition of the entire system to achieve the purpose of dimensionality reduction.

FIG. 17 is a flowchart of a method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 17, the method includes: firstly, a relationship between a Master and a Slave is represented as a relationship matrix, and then determining whether the relationship matrix includes the simplest dead. The lock matrix, if the relationship matrix does not contain the simplest deadlock matrix, release the write address command sent by the master to the slave, and if the relation matrix contains the simplest deadlock matrix, the relationship matrix is decomposed into one or more minimal deadlock matrices. Then, it is determined whether each of the simplest deadlock matrices satisfies the deadlock feature. If one or more of the simplest deadlock matrices satisfy the deadlock feature, the corresponding write address command that generates the deadlock is blocked.

The method for preventing bus deadlock in the embodiment provides a relationship between a Master and a Slave as a relationship matrix, and then determines whether the relationship matrix includes a minimal deadlock matrix, and then determines and blocks the deadlock according to the simplest deadlock matrix blocking. Write address command; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock, thus achieving the purpose of preventing bus deadlock. The problem of reducing the data throughput caused by the unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

FIG. 18 is still another schematic flowchart of a method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 18, the method includes:

Step 501: The device for preventing bus deadlock establishes a dynamic routing table. The dynamic routing table is configured to record status information of a write address command sent by the master but not yet reach the slave.

Step 502: The device for preventing bus deadlock determines whether the relationship between the master and the slave exists in a pre-sentence situation according to the dynamic routing table; wherein, after the first transmission, the first master sends a first write address command to the first slave. The sending time is less than the second master sends the first slave The transmission time of the second write address command is sent, and the arrival time of the first write address command reaching the first slave is greater than the arrival time of the second write address command reaching the first slave.

Step 503: If the relationship between the master and the slave is pre-emptive to the situation, the device for preventing the bus deadlock generates the incremental relationship matrix according to the second write address command, the third write address command, and the fourth write address command; The third write address command is an address command sent to the second slave and transmitting a time instant greater than a transmission time of the second write address command; and the fourth write address command is an address command having a transmission time greater than the third write address command.

It should be noted that, if the relationship between the master and the slave is in the first instance, the relationship between the master and the slave indicated by the second write address command, the third write address command, and the fourth write address command is determined; The relationship between the Master and the Slave is that the Master sends a write address command to the Slave, and sets a first identifier in the corresponding position of the incremental relationship matrix; if the relationship between the Master and the Slave is that the Master does not send a write address command to the Slave, the increase is The corresponding position of the quantity relationship matrix sets the second identifier.

Specifically, if the transmission time of the write address command AW _ij (indicating the AW command sent from Masteri to Slavej) precedes the transmission time of another write address command AW _kj (indicating the command sent by Masterk to Slavej), then it will be sent to Slavej transmission time and the transmission time is later than the write address AW _kj command _{Σ Tmj>} Tkj AW _mj (third write address commands), and sent to the Slave and transmits any time later than the time of the write address AW _mj send command Σ _{Tmk >Tmj} AW _mk (fourth write address command), and the relationship between Master and Slave represented by AW _kj (second write address command) is represented by the first identifier at the corresponding position of the incremental relationship matrix.

Step 504: The device for preventing bus deadlock determines whether the bus generates a deadlock according to the incremental relationship matrix.

Specifically, the step 504 includes: determining whether each row and each column of the incremental relationship matrix respectively have at least two first identifiers; if each row and each column of the incremental relationship matrix respectively have at least two first identifiers, Determine if the bus will generate a deadlock.

Step 505: If the bus generates a deadlock, the device that prevents the bus deadlock determines and blocks the write address command that caused the deadlock.

The method for preventing bus deadlock provided in this embodiment establishes state information for recording a write address command sent by the master but has not yet reached the slave; and determining whether the relationship between the master and the slave exists after the first occurrence according to the dynamic routing table. If the relationship between the Master and the Slave exists first-hand, the incremental relationship matrix is generated according to the second write address command, the third write address command, and the fourth write address command; and then the bus is broken according to the incremental relationship matrix. Whether a deadlock will occur, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock in a simple way, thereby specifically preventing the bus from being caused The write address command of the deadlock realizes the purpose of preventing the bus deadlock, and avoids the problem of reducing the address throughput caused by adopting the unified anti-deadlock mechanism, and improves the address transmission efficiency of the bus.

FIG. 19 is another flowchart of a method for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 19, the method includes: first determining whether a relationship between a master and a slave exists after a pre-emptive situation, if not There is a write address command sent by the Master to the Slave. If it exists, an incremental relationship matrix is established, and then the bus is determined to be deadlocked according to the incremental relationship matrix. If it is determined that a deadlock occurs, the corresponding write address command is blocked.

FIG. 20 is a schematic diagram of an emergency mechanism for preventing bus deadlock according to an embodiment of the present invention. The mechanism is configured to cope with an unreasonable parameter setting of an Interconnect module (eg, an Outstanding depth of an entry is greater than an Outstanding depth in a path), which may occur. In the AW command transmission process, there is no competing access and the channel is blocked (self-blocking). Once this happens, it will destroy the timing relationship in the dynamic routing table and the estimated order in the destination queue list, forming a deadlock possibility. As shown in FIG. 20, the mechanism includes: determining whether the self-blocking occurs by the bus. If self-blocking occurs, determining whether the write address command in the dynamic routing table exists and is self-blocking is the same as the master but different from the slave, and enters the Interconnect. The time is later than the other write address of the write address command If so, the write address command issued by the Master that blocks the write address command is blocked, and if it does not exist, the other Slave write address command sent to the write address command is blocked.

FIG. 21 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 21, the apparatus 6 includes:

The pre-processing module 61 is configured to establish a dynamic routing table, where the dynamic routing table is used to record status information of a write address command sent by the master device but not yet reaching the slave device Slave;

The determining module 62 is configured to determine, according to the dynamic routing table, whether the bus generates a deadlock;

The processing module 63 is configured to determine and block the write address command that caused the deadlock if the bus generates a deadlock.

The device for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording status information of a write address command issued by the master but not yet reaching the slave; determining whether the bus will generate a deadlock according to the dynamic routing table; Generate a deadlock, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock. Thereby, the purpose of preventing the bus deadlock is achieved, and the problem of reducing the address throughput caused by adopting the unified anti-deadlock mechanism is avoided, and the address transmission efficiency of the bus is improved.

FIG. 22 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 22, the determining module 62 includes:

The first processing unit 621 is configured to generate a relationship matrix according to the relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is the first identifier, if the master does not send the write address command to the slave The corresponding position of the relationship matrix is the second identifier;

The first determining unit 622 is configured to determine whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix.

Further, the first determining unit 622 is configured to determine whether the relationship matrix is a deadlock matrix; The deadlock matrix is a matrix in the relation matrix that can cause the bus to deadlock; if the relation matrix is a deadlock matrix, it is determined whether the deadlock matrix is the simplest deadlock matrix; wherein the simplest deadlock matrix is in the deadlock matrix The bus that can make the bus deadlock and the simplest form; if the deadlock matrix is not the simplest deadlock matrix, convert the deadlock matrix into the simplest deadlock matrix; determine whether the bus is based on the dynamic routing table and the simplest deadlock matrix Will produce a deadlock.

The first determining unit 622 is further configured to determine whether each row and each column of the relationship matrix respectively have at least two first identifiers; if each row and each column of the relationship matrix respectively have at least two first identifiers, determining that the relationship matrix is Deadlock matrix; if there is no at least 2 first identifiers in a row or a column of the relationship matrix, it is determined that the relationship matrix is not a deadlock matrix.

The first determining unit 622 is further configured to: if the relationship matrix is a deadlock matrix, determine whether each row and each column of the deadlock matrix have two first identifiers; if each row and each column of the relationship matrix has two An identifier determines that the deadlock matrix is the simplest deadlock matrix; if there are more than two first identifiers in a row or a column of the relationship matrix, it is determined that the deadlock matrix is not the simplest deadlock matrix.

个i×i阶子矩阵；其中，m、k均为大于1的整数，l＝min(m,k)，i＝2、3…l；从

个i×i阶子矩阵中筛选出i×i阶死锁矩阵；判断i×i阶死锁矩阵是否是最简死锁矩阵；若i×i阶死锁矩阵不是最简死锁矩阵，将i×i阶死锁矩阵转换成最简死锁矩阵。The first determining unit 622 is further configured to obtain, if the m×k order deadlock matrix is not the simplest deadlock matrix, according to the m×k order deadlock matrix.

i×i order submatrix; where m and k are integers greater than 1, l=min(m,k), i=2, 3...l;

The i×i order deadlock matrix is selected in the i×i order submatrix; whether the i×i order deadlock matrix is the simplest deadlock matrix; if the i×i order deadlock matrix is not the simplest deadlock matrix, The i×i order deadlock matrix is converted into the simplest deadlock matrix.

个i×i阶矩阵，得到

个i×i阶矩阵。The first determining unit 622 is further configured to select the number of i rows and i columns in the m×k order deadlock matrix if the m×k order deadlock matrix is not the simplest deadlock matrix, from the selected i rows and i Select the number in the i row and the i column and generate the i×i order matrix from the number of columns;

i×i order matrix, get

i × i order matrix.

The first determining unit 622 is further configured to: if the i×i order deadlock matrix is not the simplest deadlock matrix, the first row or column in the i×i order deadlock matrix has more than two first identifiers. The identifier is set to the second identifier, so that each row and each column of the i×i-order deadlock matrix has two first identifiers, The simplest deadlock matrix.

Further, the status information of the write address command includes an interface name of the source interface, an interface name of the destination interface, information of the first timing convergence register slice, and information of the second timing convergence register slice, wherein the information of the first timing convergence register slice is The information of the timing convergence register slice that the address command is to pass from the source interface to the transmission path of the destination interface, and the information of the second timing convergence register slice is the information of the timing convergence register slice that the current address write address command has passed, and the source interface is The slave interface connected to the master that sends the write address command. The destination interface is the master interface connected to the slave that receives the write address command.

FIG. 23 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 23, the processing module 63 includes:

The obtaining unit 631 is configured to obtain, according to the simplest deadlock matrix and the dynamic routing table, a sending moment that the master sends a write address command to the slave; and obtain a write address command sent by the master to obtain a path of the slave according to the simple deadlock matrix and the dynamic routing table. Delay

The second determining unit 632 is configured to determine, according to the sending time of the write address command and the delay in the path, whether the relationship between the master and the slave meets the deadlock feature; wherein the deadlock feature is sent by the first master to the first slave. a first write address command, followed by a second write address command to the second slave; the second master first sends a third write address command to the second slave, and then sends a fourth write address command to the first slave; and the second write address The command arrives at the second slave before the third write address command; the fourth write address command arrives at the first slave before the first write address command.

The second processing unit 633 is configured to determine that the bus will generate a deadlock if the relationship between the Master and the Slave satisfies the deadlock feature.

The obtaining unit 631 is configured to obtain information of the second timing convergence register slice of the write address command in the dynamic routing table according to the simplest deadlock matrix; acquire time information of the current time; and time information according to the current time and the second timing convergence register The information of the slice calculates the transmission time at which the master sends a write address command to the slave. Get the first time in the dynamic routing table according to the simplest deadlock matrix The sequence converges the information of the register slice; and calculates the delay in the transmission path of the write address command sent by the master to the slave according to the information of the first timing convergence register slice.

The second determining unit 632 is configured to determine whether the sending time of the first write address command sent by the first master to the first slave is smaller than the sending time of the second write address command sent by the first master to the second slave; Whether the sending time of the second slave address command is less than the sending time of the fourth write address command sent by the second master to the first slave; determining whether the arrival time of the second write address command reaching the second slave is less than the third write address When the command reaches the arrival time of the second slave, determining whether the arrival time of the fourth write address command reaching the first slave is less than the arrival time of the first write address command reaching the first slave;

If the sending time of the first write address command sent by the first master to the second slave is greater than the sending time of the first write address command sent by the first master to the first slave, and the arrival time of the second write address command reaching the second slave is less than the The third write address command arrives at the arrival time of the second slave; and, the second master sends the fourth write address command to the first slave, the transmission time is greater than the second master sends the third write address command to the second slave, and the fourth The time at which the write address command arrives at the first slave is less than the time at which the first write address command arrives at the first slave; it is determined that the relationship between the master and the slave satisfies the deadlock feature.

The device for preventing bus deadlock provided in this embodiment establishes a dynamic routing table for recording state information of a write address command sent by the master but not yet reaching the slave; generating a relationship matrix according to the relationship between the master and the slave; determining the relationship matrix Whether it is the simplest deadlock matrix; if the relational matrix is not the simplest deadlock matrix, the relational matrix is converted into the simplest deadlock matrix; according to the dynamic routing table and the simplest deadlock matrix, it is judged whether the bus will generate a deadlock; Generate a deadlock, determine and block the write address command that caused the deadlock; this can effectively identify the write address command that is at risk of potential deadlock, and thus specifically block the write address command that will cause the bus deadlock. Thereby, the purpose of preventing the bus deadlock is achieved, and the problem of reducing the data throughput caused by the unified anti-deadlock mechanism is avoided, and the data transmission efficiency of the bus is improved.

FIG. 24 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 24, the determining module 62 includes:

The third determining unit 623 is configured to determine, according to the dynamic routing table, whether the relationship between the master and the slave exists after the first transmission; wherein, after the first transmission, the first master sends the first write address command to the first slave. The sending time is less than the sending time at which the second master sends the second write address command to the first slave, and the arrival time of the first write address command reaching the first slave is greater than the arrival time of the second write address command reaching the first slave; Whether the incremental relationship matrix breaks the bus to generate a deadlock;

The third processing unit 624 is configured to generate an incremental relationship matrix according to the second write address command, the third write address command, and the fourth write address command, if the relationship between the master and the slave is pre-emptive to the situation; The third write address command is an address command sent to the second slave and transmitting a time instant greater than the transmission time of the second write address command; and the fourth write address command is an address command having a transmission time greater than the third write address command.

Further, the third processing unit 624 is configured to determine that the relationship between the master and the slave has a pre-send condition, and determine the master and slave respectively indicated by the second write address command, the third write address command, and the fourth write address command. If the relationship between the master and the slave is that the master sends a write address command to the slave, the first identifier is set at the corresponding position of the incremental relationship matrix; if the relationship between the master and the slave is that the master does not send the write to the slave The address command sets a second identifier at a corresponding position of the incremental relationship matrix. .

The third determining unit 623 is configured to determine whether each row and each column of the incremental relationship matrix respectively have at least two first identifiers; if each row and each column of the incremental relationship matrix respectively have at least two first identifiers Determine if the bus will generate a deadlock.

The device for preventing bus deadlock provided in this embodiment establishes state information for recording a write address command sent by the master but has not yet reached the slave; and determining whether the relationship between the master and the slave exists after the first occurrence according to the dynamic routing table. If the relationship between Master and Slave exists After the first transmission to the situation, the incremental relationship matrix is generated according to the second write address command, the third write address command, and the fourth write address command; and further, according to the incremental relationship matrix, whether the bus will generate a deadlock, determine and block A write address command that causes a deadlock; this can effectively identify a write address command that is at risk of a potential deadlock in a simple way, thereby specifically preventing a write address command that would cause a bus deadlock, thereby implementing The purpose of preventing bus deadlock is to avoid the problem of data throughput reduction caused by adopting a unified anti-deadlock mechanism, and improve the data transmission efficiency of the bus.

In an actual application, the pre-processing module 61, the determining module 62, the first processing unit 621, the first determining unit 622, the third determining unit 623, the third processing unit 624, the processing module 63, the obtaining unit 631, and the second The determining unit 632 and the second processing unit 633 may each be a central processing unit (CPU), a microprocessor (Micro Processor Unit (MPU), and a digital signal processor (Digital Signal Processor) located in the management device of the cache space. , DSP) or Field Programmable Gate Array (FPGA) implementation.

FIG. 25 is a schematic structural diagram of another apparatus for preventing bus deadlock according to an embodiment of the present invention. As shown in FIG. 25, the apparatus 7 includes:

The Interconnect module 71 is configured to run a write address command sent by the Master to the Slave.

The monitoring module 72 is configured to monitor the operation of the Interconnect system module 71.

The determining module 73 is configured to determine whether a bus deadlock is generated in the Interconnect system according to the condition monitored by the monitoring module 72.

The blocking module 74 is configured to block a write address command that causes a bus deadlock.

In an actual application, the Interconnect module 71, the monitoring module 72, the judging module 73, and the blocking module 74 can be implemented by a CPU, an MPU, a DSP, an FPGA, or the like located in a management device of the cache space.

In the embodiment of the present invention, if the method for reducing the delay is implemented in the form of a software function module The law, when sold or used as a stand-alone product, can also be stored on a computer readable storage medium. Based on such understanding, the technical solution of the embodiments of the present invention may be embodied in the form of a software product in essence or in the form of a software product stored in a storage medium, including a plurality of instructions. A computer device (which may be a personal computer, server, or network device, etc.) is caused to perform all or part of the methods described in various embodiments of the present invention. The foregoing storage medium includes various media that can store program codes, such as a USB flash drive, a mobile hard disk, a read only memory (ROM), a magnetic disk, or an optical disk. Thus, embodiments of the invention are not limited to any specific combination of hardware and software.

Correspondingly, the embodiment of the present invention further provides a computer storage medium, where the computer storage medium stores a computer program for performing the above method for preventing bus deadlock in the embodiment of the present invention.

Those skilled in the art will appreciate that embodiments of the present invention can be provided as a method, system, or computer program product. Accordingly, the present invention can take the form of a hardware embodiment, a software embodiment, or a combination of software and hardware. Moreover, the invention can take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage and optical storage, etc.) including computer usable program code.

The present invention has been described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (system), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or FIG. These computer program instructions can be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing device to produce a machine for the execution of instructions for execution by a processor of a computer or other programmable data processing device. Means for implementing the functions specified in one or more of the flow or in a block or blocks of the flow chart.

These computer program instructions can also be stored in a bootable computer or other programmable data processing The apparatus is readable in a computer readable memory in a particular manner such that instructions stored in the computer readable memory produce an article of manufacture comprising instruction means implemented in one or more flows and/or block diagrams of the flowchart The function specified in the box or in multiple boxes.

These computer program instructions can also be loaded onto a computer or other programmable data processing device such that a series of operational steps are performed on a computer or other programmable device to produce computer-implemented processing for execution on a computer or other programmable device. The instructions provide steps for implementing the functions specified in one or more of the flow or in a block or blocks of a flow diagram.

The above is only the preferred embodiment of the present invention and is not intended to limit the scope of the present invention.

Industrial applicability

The embodiment of the present invention establishes a dynamic routing table, wherein the dynamic routing table is used to record state information of a write address command sent by the master device but not reaching the slave device Slave; and determining whether the bus is dead according to the dynamic routing table. a lock; if the bus generates a deadlock, the write address command that caused the deadlock is determined and blocked. In this way, the write address command that causes the bus deadlock can be blocked in a targeted manner, thereby preventing the bus deadlock, and avoiding the problem of reducing the data throughput caused by the unified anti-deadlock mechanism, and improving the bus. Data transmission efficiency.

Claims (25)

A method of preventing bus deadlock, the method comprising: Establishing a dynamic routing table, where the dynamic routing table is used to record state information of a write address command sent by the master device but not reaching the slave device slave; Determining whether the bus will generate a deadlock according to the dynamic routing table; If the bus generates a deadlock, the write address command that caused the deadlock is determined and blocked. The method of claim 1, wherein said determining, based on said dynamic routing table, whether a bus will generate a deadlock comprises: Generating a relationship matrix according to the relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is a first identifier, if the master does not send the location to the slave Describe an address command, where a corresponding location of the relationship matrix is a second identifier; Determining whether the bus will generate a deadlock according to the dynamic routing table and the relationship matrix. The method of claim 2, wherein the determining whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix comprises: Determining whether the relationship matrix is a deadlock matrix; wherein the deadlock matrix is a matrix in the relationship matrix that can cause the bus to generate a deadlock; If the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is a simplest deadlock matrix; wherein the simplest deadlock matrix is that the deadlock matrix can cause the bus to generate a deadlock And the simplest form of matrix; If the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix into the simplest deadlock matrix; Determining whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix. The method of claim 3, wherein the determining whether the relationship matrix is a deadlock matrix comprises: Determining whether there are at least two of the first identifiers in each row and each column of the relationship matrix; If there are at least two first identifiers in each row and each column of the relationship matrix, determining that the relationship matrix is the deadlock matrix; If at least two of the first identifiers do not exist in a row or a column of the relationship matrix, it is determined that the relationship matrix is not the deadlock matrix. The method according to claim 4, wherein if the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is a minimalist deadlock matrix comprises: If the relationship matrix is the deadlock matrix, determine whether each of the row and each column of the deadlock matrix has two first identifiers; If there are two first identifiers in each row and each column of the relationship matrix, determining that the deadlock matrix is the simplest deadlock matrix; If there are more than two of the first identifiers in a row or a column of the relationship matrix, it is determined that the deadlock matrix is not the simplest deadlock matrix. The method of claim 5, wherein if the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix to the minimalistic deadlock matrix comprises: If the m×k order deadlock matrix is not the simplest deadlock matrix, according to the m×k order deadlock matrix

i×i order submatrix; wherein m and k are integers greater than 1, l=min(m,k), i=2, 3...l; From the stated

The i×i order deadlock matrix is selected in the i×i order submatrices; Determining whether the i×i order deadlock matrix is the simplest deadlock matrix; If the i×i order deadlock matrix is not the simplest deadlock matrix, the i×i order deadlock matrix is converted into the simplest deadlock matrix. The method according to claim 6, wherein said m×k order deadlock matrix is not said simplest deadlock matrix, and is obtained according to said m×k order deadlock matrix

i×i order sub-matrices, including: If the m×k order deadlock matrix is not the simplest deadlock matrix, the number of i rows and i columns is selected in the m×k order deadlock matrix, and the selected i row and i column numbers are selected and included. Generating the numbers in the i rows and i columns and generating the i×i order matrix; Select

The i×i order matrix, resulting in the

i × i order matrix. The method according to claim 6, wherein said if said i x i order deadlock matrix is not said simplest deadlock matrix, said i x i order deadlock matrix is converted to said minimalist deadlock Matrix, including: If the i×i order deadlock matrix is not the simplest deadlock matrix, there are more than two of the first identified rows or columns in the i×i order deadlock matrix. An identifier is set to the second identifier, so that each of the row and each column of the i×i-order deadlock matrix has two first identifiers, to obtain the simplest deadlock matrix. The method of claim 3, wherein the state information of the write address command comprises an interface name of the source interface, an interface name of the destination interface, information of the first timing closure register slice, and information of the second timing closure register slice. The information of the first timing convergence register slice is information of a timing convergence register slice that the write address command needs to pass from the source interface to the transmission path of the destination interface, and the second timing convergence register fragment The information is the information of the timing convergence register slice that the address command has passed at the current time, the source interface is a slave interface connected to the master that sends the write address command, and the destination interface is Write the master interface of the Slave connected to the address command. The method of claim 9, wherein the determining whether the bus generates a deadlock according to the dynamic routing table and the minimalist deadlock matrix comprises: Obtaining the master to the slave according to the simplest deadlock matrix and the dynamic routing table Sending a transmission time of the write address command; Acquiring, according to the simplest deadlock matrix and the dynamic routing table, a delay in a path that the write address command sent by the master reaches the slave; Determining, according to the sending moment of the write address command and the delay in the path, whether the relationship between the master and the slave meets a deadlock feature; wherein the deadlock feature is the first master first Slave sends a first write address command, and then sends a second write address command to the second slave; the second master first sends a third write address command to the second slave, and then sends a fourth write address command to the first slave. And the second write address command arrives at the second slave before the third write address command; the fourth write address command arrives at the first slave before the first write address command. If the relationship between the Master and the Slave satisfies the deadlock feature, it is determined that the bus will generate a deadlock. The method of claim 10, wherein the obtaining, by the simplest deadlock matrix and the dynamic routing table, a sending moment that the master sends a write address command to the slave comprises: Acquiring information of the second timing convergence register slice of the write address command in the dynamic routing table according to the simplest deadlock matrix; Obtaining time information of the current moment; And calculating, according to the time information of the current time and the information of the second timing convergence register slice, a transmission time at which the master sends a write address command to the slave. The method according to claim 10, wherein the obtaining, in accordance with the simplest deadlock matrix and the dynamic routing table, a delay in a path of the write address command sent by the master to the slave, including : Obtaining information of the first timing convergence register slice in the dynamic routing table according to the simplest deadlock matrix; And calculating a delay in the transmission path of the write address command sent by the master to the slave according to the information of the first timing convergence register slice. The method of claim 12, wherein the determining whether the relationship between the master and the slave meets a deadlock feature according to a sending moment of the write address command and a delay in the path comprises: Determining whether the sending time of the first write address command sent by the first master to the first slave is less than the sending time of the first master sending the second write address command to the second slave; Determining whether the sending time of the third master sending the third write address command to the second slave is smaller than the sending time of the fourth write address command sent by the second master to the first slave; Determining whether an arrival time of the second write address command to reach the second slave is less than an arrival time of the third write address command reaching the second slave; Determining whether an arrival time of the fourth write address command to reach the first slave is less than an arrival time of the first write address command to reach the first slave; And sending, by the first master, the sending time of the second write address command to the second slave is greater than the sending time of the first master sending the first write address command to the first slave, and The arrival time of the second write address command reaching the second slave is less than the arrival time of the third write address command reaching the second slave; and the second master sends the fourth to the first slave The sending time of the write address command is greater than the time when the second master sends the third write address command to the second slave, and the time when the fourth write address command reaches the first slave is less than the first The time at which the write address command arrives at the first slave; determining that the relationship between the master and the slave satisfies the deadlock feature. The method of claim 1, wherein the method determines whether the bus generates a deadlock according to the dynamic routing table, including: Determining, according to the dynamic routing table, whether the relationship between the master and the slave exists in a pre-emptive manner; wherein, after the first sending, the sending time of the first master sending the first write address command to the first slave is smaller than the first The second master sends a sending moment of the second write address command to the first slave, and the arrival time of the first write address command reaching the first slave is greater than the arrival time of the second write address command reaching the first slave; And if the relationship between the master and the slave exists in the pre-sending to the situation, generating an incremental relationship matrix according to the second write address command, the third write address command, and the fourth write address command; wherein The third write address command is a write command sent to the second slave and transmitting a time greater than a sending time of the second write address command; the fourth write address command is a write command having a sending time greater than the third write address command ; Judging whether the bus will generate a deadlock according to the incremental relationship matrix. The method according to claim 14, wherein if the relationship between the Master and the Slave exists in the pre-sending to the case, according to the second write address command, the third write address command, and the fourth write The address command generates an incremental relationship matrix, including: If the relationship between the master and the slave exists in the pre-sending to the case, determine the master and the slave represented by the second write address command, the third write address command, and the fourth write address command, respectively. Relationship between If the relationship between the master and the slave is that the master sends a write address command to the slave, setting a first identifier at a corresponding position of the incremental relationship matrix; If the relationship between the master and the slave is that the master does not send a write address command to the slave, a second identifier is set at a corresponding position of the incremental relationship matrix. The method according to claim 15, wherein said determining whether the bus generates a deadlock according to said incremental relationship matrix comprises: Determining whether there are at least two of the first identifiers in each row and each column of the incremental relationship matrix; If there are at least two of the first identifiers in each row and each column of the incremental relationship matrix, it is determined whether the bus will generate a deadlock. A device for preventing bus deadlock, the device comprising: a pre-processing module configured to establish a dynamic routing table, where the dynamic routing table is used to record status information of a write address command sent by the master device but not yet reaching the slave device slave; The determining module is configured to determine, according to the dynamic routing table, whether the bus generates a deadlock; The processing module is configured to determine and block the write address command causing the deadlock if the bus generates a deadlock. The apparatus of claim 17, wherein the determining module comprises: a first processing unit, configured to generate a relationship matrix according to a relationship between the master and the slave; wherein, if the master sends a write address command to the slave, the corresponding position of the relationship matrix is a first identifier, if the master Not sending the write address command to the slave, where a corresponding location of the relationship matrix is a second identifier; The first determining unit is configured to determine whether the bus generates a deadlock according to the dynamic routing table and the relationship matrix. The device of claim 18, wherein The first determining unit is configured to determine whether the relationship matrix is a deadlock matrix; wherein the deadlock matrix is a matrix in the relationship matrix that can cause the bus to generate a deadlock; If the relationship matrix is the deadlock matrix, determining whether the deadlock matrix is a simplest deadlock matrix; wherein the simplest deadlock matrix is that the deadlock matrix can cause the bus to generate a deadlock And the simplest form of matrix; If the deadlock matrix is not the simplest deadlock matrix, converting the deadlock matrix into the simplest deadlock matrix; Determining whether the bus generates a deadlock according to the dynamic routing table and the simplest deadlock matrix. The apparatus according to claim 17, wherein the status information of the write address command comprises an interface name of the source interface, an interface name of the destination interface, information of the first timing closure register slice, and information of the second timing closure register slice, The information of the first timing convergence register slice is information of a timing convergence register slice that the write address command needs to pass from the source interface to the transmission path of the destination interface, and the second timing convergence register fragment The information is the information of the timing convergence register slice that the address command has passed at the current time, the source interface is a slave interface connected to the master that sends the write address command, and the destination interface is Write the master interface of the Slave connected to the address command. The apparatus of claim 17 wherein said processing module comprises: An obtaining unit, configured to acquire, according to the simplest deadlock matrix and the dynamic routing table, a sending moment that the master sends the write address command to the slave; according to the simplest deadlock matrix and the dynamic routing Obtaining, by the table, a delay in a path that the write address command sent by the master reaches the slave; The second determining unit is configured to determine, according to the sending moment of the write address command and the delay in the path, whether the relationship between the master and the slave meets a deadlock feature; wherein the deadlock feature is The first master first sends a first write address command to the first slave, and then sends a second write address command to the second slave; the second master first sends a third write address command to the second slave, and then the first The slave sends a fourth write address command; and the second write address command arrives at the second slave before the third write address command; the fourth write address command arrives at the first write address command prior to First Slave; The second processing unit is configured to determine that the bus generates a deadlock if the relationship between the master and the slave satisfies a deadlock feature. The device according to claim 21, wherein The second determining unit is configured to determine whether a sending moment of the first master sending the first write address command to the first slave is smaller than the first master to the second Slave sends a sending moment of the second write address command; Determining whether the sending time of the third master sending the third write address command to the second slave is smaller than the sending time of the fourth write address command sent by the second master to the first slave; Determining whether an arrival time of the second write address command to reach the second slave is less than an arrival time of the third write address command reaching the second slave; Determining whether an arrival time of the fourth write address command to reach the first slave is less than an arrival time of the first write address command to reach the first slave; And sending, by the first master, the sending time of the second write address command to the second slave is greater than the sending time of the first master sending the first write address command to the first slave, and The arrival time of the second write address command reaching the second slave is less than the arrival time of the third write address command reaching the second slave; and the second master sends the fourth to the first slave The sending time of the write address command is greater than the time when the second master sends the third write address command to the second slave, and the time when the fourth write address command reaches the first slave is less than the first The time at which the write address command arrives at the first slave; determining that the relationship between the master and the slave satisfies the deadlock feature. The apparatus of claim 17, wherein the determining module comprises: The third determining unit is configured to determine, according to the dynamic routing table, whether the relationship between the master and the slave is in a pre-emptive manner; wherein, after the first sending, the first master sends the first write to the first slave. The sending moment of the address command is smaller than the sending moment of the second master sending the second write address command to the first slave, and the arrival time of the first write address command reaching the first slave is greater than the second write address command reaching the first slave. The situation of the arrival time; whether the bus will be deadlocked according to the incremental relationship matrix; a third processing unit, configured to: if the relationship between the master and the slave exists after the first sending, according to the second write address command, the third write address command, and the fourth write address The command generates an incremental relationship matrix; wherein the third write address command is an address command sent to the second slave and the sending time is greater than the sending time of the second write address command; the fourth write address command is sent The time is greater than the address command of the third write address command. The device according to claim 23, wherein The third processing unit is configured to determine, according to the relationship between the master and the slave, the second write address command, the third write address command, and the fourth The relationship between the Master and the Slave represented by the write address command; If the relationship between the master and the slave is that the master sends a write address command to the slave, setting a first identifier at a corresponding position of the incremental relationship matrix; If the relationship between the master and the slave is that the master does not send a write address command to the slave, a second identifier is set at a corresponding position of the incremental relationship matrix. A computer storage medium having stored therein computer executable instructions for performing the method of preventing bus deadlock according to any one of claims 1 to 16.

Images