SELECTIVE INSERTION OF A DEADLOCK RECOVERY BUFFER IN A BUS INTERCONNECT FOR DEADLOCK RECOVERY

• US 20190020586A1
• Filed: 07/14/2017
• Published: 01/17/2019
• Est. Priority Date: 07/14/2017
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Karanam, Ravi, Basnight, Thomas, Zaidi, Zainab Nasreen
• Application Number:
  US15/649,985
• Publication Number:
  US 20190020586A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 13/4036 and deadlock prevention
• CPC Class Codes: G06F 13/4063 Device-to-bus coupling
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Selective insertion of a deadlock recovery buffer in a bus interconnect for deadlock recovery is provided. A bus interconnect is provided that includes router nodes configured to receive new bus transaction messages from agent devices. The router nodes route the received bus transaction messages to other destination router nodes in the bus interconnect to be communicated to designated agent devices. To recover from a deadlock condition when buffers of all router nodes are full, thus halting forward progress of bus transaction messages, a deadlock recovery circuit is provided. The deadlock recovery circuit is configured to detect a bus deadlock condition in the bus interconnect. In response, the deadlock recovery circuit is configured to insert a deadlock recovery buffer that has additional buffer entries in the bus interconnect as another router node to allow forward progress of bus transaction messages to continue to recover from the deadlock condition.

Claims

1. A deadlock recovery circuit for a bus interconnect, comprising:

a bus interconnect input interface configured to receive input bus transaction messages from a first router circuit in a bus interconnect, each of the input bus transaction messages comprising a data packet;

a bus interconnect output interface configured to receive output bus transaction messages each comprising a data packet from the received input bus transaction messages to be forwarded to a second router circuit in the bus interconnect; and

a deadlock recovery buffer configured to store at least one data packet;

the deadlock recovery circuit configured to;

receive the input bus transaction messages on the bus interconnect input interface;

forward the output bus transaction messages on the bus interconnect output interface, each of the output bus transaction messages comprising at least one data packet from the received input bus transaction messages;

detect a deadlock condition in the bus interconnect; and

in response to the detected deadlock condition in the bus interconnect indicating a deadlock state, selectively communicatively couple the deadlock recovery buffer to the bus interconnect output interface.

2. The deadlock recovery circuit of claim 1, further configured to:

store the data packets from the received input bus transaction messages in the deadlock recovery buffer; and

generate the output bus transaction messages from the at least one stored data packet in the deadlock recovery buffer.

3. The deadlock recovery circuit of claim 1, further configured to, in response to the detected deadlock condition in the bus interconnect indicating a deadlock non-recovery state, selectively communicatively decouple the deadlock recovery buffer from the bus interconnect input interface and the bus interconnect output interface.

4. The deadlock recovery circuit of claim 1, further comprising:

a deadlock recovery detection and recovery (DLDR) circuit comprising a deadlock recovery interface, the DLDR circuit configured to;

detect the deadlock condition in the bus interconnect;

generate a deadlock recovery indicator on the deadlock recovery interface based on the detected deadlock condition in the bus interconnect; and

in response to the detected deadlock condition in the bus interconnect indicating a deadlock state, generate the deadlock recovery indicator indicating a deadlock recovery state; and

a deadlock recovery buffer circuit comprising the deadlock recovery buffer and an output selector circuit communicatively coupled to the deadlock recovery interface;

the output selector circuit configured to selectively communicatively couple the deadlock recovery buffer to the bus interconnect output interface in response to the deadlock recovery indicator indicating the deadlock recovery state.

5. The deadlock recovery circuit of claim 4, wherein:

the DLDR circuit is further configured to, in response to the detected deadlock indicator indicating a deadlock non-recovery state, generate the deadlock recovery indicator indicating a deadlock non-recovery state; and

the output selector circuit is further configured to selectively communicatively decouple the deadlock recovery buffer from the bus interconnect output interface in response to the deadlock recovery indicator indicating the deadlock non-recovery state.

6. The deadlock recovery circuit of claim 4, wherein the deadlock recovery buffer circuit comprises:

an input buffer configured to store at least one data packet from the received input bus transaction messages;

the deadlock recovery buffer configured to store the at least one data packet from the received input bus transaction messages; and

an input selector circuit communicatively coupled to the input buffer, the input selector circuit configured to;

selectively communicatively couple the input buffer to the deadlock recovery buffer in response to the deadlock recovery indicator indicating the deadlock recovery state; and

selectively communicatively couple the input buffer to the output selector circuit in response to the deadlock recovery indicator indicating the deadlock non-recovery state.

7. The deadlock recovery circuit of claim 4, wherein the DLDR circuit is further configured to:

receive bus communications tokens from the bus interconnect; and

detect the deadlock condition in the bus interconnect based on whether the bus communications tokens are received from the bus interconnect.

8. The deadlock recovery circuit of claim 7, further comprising a bus communications token counter configured to store a bus communications token count value;

the DLDR circuit further configured to;

store an initial bus communications token count value in the bus communications token counter;

update the bus communications token count value in the bus communications token counter based on a clock signal; and

detect the deadlock condition in the bus interconnect based on whether the bus communications tokens are received from the bus interconnect before the bus communications token count value expires.

9. The deadlock recovery circuit of claim 4, wherein the DLDR circuit further comprises:

an input probe interface configured to receive a deadlock probe signal from the bus interconnect; and

an output probe interface configured to receive a deadlock probe signal to be sent to the bus interconnect;

the DLDR circuit further configured to detect the deadlock condition of the bus interconnect by being configured to;

assert a deadlock probe signal on the output probe interface indicating a deadlock non-recovery state on a deadlock probe line in the bus interconnect;

receive the deadlock probe signal on the input probe interface indicating the deadlock condition of the bus interconnect in response to the assertion of the deadlock probe signal on the output probe interface; and

detect the deadlock condition in the bus interconnect based on the received deadlock probe signal.

10. The deadlock recovery circuit of claim 9, wherein the DLDR circuit is further configured to detect the deadlock condition in the bus interconnect in a deadlock state if the deadlock probe signal on the input probe interface indicates a deadlock state.

11. The deadlock recovery circuit of claim 9, further comprising a deadlock probe counter configured to store a deadlock probe count value;

the DLDR circuit further configured to;

initialize the deadlock probe counter to an initial deadlock probe count value in response to assertion of the deadlock probe signal on the output probe interface;

update the deadlock probe count value in the deadlock probe counter based on a clock signal; and

detect the deadlock condition in the bus interconnect based on the received deadlock probe signal when the deadlock probe count value of the deadlock probe counter has expired.

12. The deadlock recovery circuit of claim 11, wherein the DLDR circuit is further configured to detect the deadlock condition in the bus interconnect in a deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect before the deadlock probe count value of the deadlock probe counter has expired.

13. The deadlock recovery circuit of claim 4, further comprising:

a throttle communications interface configured to receive a throttle communications signal to be sent to the bus interconnect to halt new bus transaction messages from being injected into the bus interconnect; and

a throttle communications counter configured to store a throttle communications count value;

the DLDR circuit further configured to, in response to the detected deadlock condition in the bus interconnect indicating the deadlock state;

initialize the throttle communications counter to an initial throttle communications count value;

update the throttle communications count value in the throttle communications counter based on a clock signal; and

in response to expiration of the throttle communications count value in the throttle communications counter, generate the deadlock recovery indicator indicating the deadlock recovery state.

14. The deadlock recovery circuit of claim 5, wherein the DLDR circuit is further configured to:

determine if the deadlock recovery buffer is empty; and

generate the deadlock recovery indicator indicating the deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect and the deadlock recovery buffer being empty.

15. The deadlock recovery circuit of claim 14, further comprising a deadlock recovery counter configured to store a deadlock recovery count value;

the DLDR circuit further configured to, in response to the detected deadlock condition in the bus interconnect indicating the deadlock state;

initialize the deadlock recovery counter to an initial deadlock recovery count value;

update the deadlock recovery count value in the deadlock recovery counter based on a clock signal; and

in response to expiration of the deadlock recovery count value in the deadlock recovery counter, generate the deadlock recovery indicator indicating the deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect and the deadlock recovery buffer being empty.

16. The deadlock recovery circuit of claim 4, wherein the DLDR circuit comprises the deadlock recovery buffer circuit.

17. The deadlock recovery circuit of claim 1 integrated into a system-on-a-chip (SoC).

18. The deadlock recovery circuit of claim 1 integrated into a device selected from the group consisting of:

a set top box;

an entertainment unit;

a navigation device;

a communications device;

a fixed location data unit;

a mobile location data unit;

a global positioning system (GPS) device;

a mobile phone;

a cellular phone;

a smart phone;

a session initiation protocol (SIP) phone;

a tablet;

a phablet;

a server;

a computer;

a portable computer;

a mobile computing device;

a wearable computing device;

a desktop computer;

a personal digital assistant (PDA);

a monitor;

a computer monitor;

a television;

a tuner;

a radio;

a satellite radio;

a music player;

a digital music player;

a portable music player;

a digital video player;

a video player;

a digital video disc (DVD) player;

a portable digital video player;

an automobile;

a vehicle component;

avionics systems;

a drone; and

a multicopter.

19. A deadlock recovery circuit for a bus interconnect, comprising:

a means for receiving input bus transaction messages from a first router circuit in a bus interconnect, each of the input bus transaction messages comprising a data packet;

a means for forwarding output bus transaction messages each comprising a data packet from the received input bus transaction messages to a second router circuit in the bus interconnect;

a means for storing at least one data packet;

a means for detecting a deadlock condition in the bus interconnect; and

a means for selectively communicatively coupling the means for storing to the means for forwarding in response to the detected deadlock condition in the bus interconnect indicating a deadlock state.

20. A method for recovering from a detected deadlock condition in a bus interconnect, comprising:

receiving input bus transaction messages from a bus interconnect on a bus interconnect input interface;

forwarding output bus transaction messages comprising at least one data packet from the received input bus transaction messages on a bus interconnect output interface;

detecting a deadlock condition in the bus interconnect; and

in response to detecting a deadlock condition in the bus interconnect indicating a deadlock state;

selectively communicatively coupling a deadlock recovery buffer configured to store at least one data packet to the bus interconnect output interface;

storing the at least one data packet from the received input bus transaction messages in the deadlock recovery buffer; and

generating the output bus transaction messages from the stored at least one data packet in the deadlock recovery buffer.

21. The method of claim 20, wherein, in response to detecting the deadlock condition in the bus interconnect indicating a deadlock non-recovery state:

selectively communicatively decoupling the deadlock recovery buffer from the bus interconnect output interface;

selectively communicatively decoupling the deadlock recovery buffer from the bus interconnect input interface and the bus interconnect output interface; and

generating the output bus transaction messages directly from the input bus transaction messages.

22. The method of claim 20,

further comprising:

generating a deadlock recovery indicator based on the detected deadlock condition in the bus interconnect;

in response to the detected deadlock condition in the bus interconnect indicating a deadlock state, generating the deadlock recovery indicator indicating a deadlock recovery state; and

selectively communicatively coupling the deadlock recovery buffer to the bus interconnect output interface in response to the deadlock recovery indicator indicating the deadlock recovery state.

23. The method of claim 22, further comprising:

receiving bus communications tokens from the bus interconnect; and

detecting the deadlock condition in the bus interconnect based on whether the bus communications tokens are received from the bus interconnect.

24. The method of claim 23,

further comprising:

storing an initial bus communications token count value in a bus communications token counter; and

updating a bus communications token count value in the bus communications token counter based on a clock signal; and

detecting the deadlock condition in the bus interconnect based on whether bus communications tokens are received from the bus interconnect before the bus communications token count value expires.

25. The method of claim 22, wherein detecting the deadlock condition in the bus interconnect comprises:

asserting a deadlock probe signal indicating a deadlock non-recovery state on a deadlock probe line in the bus interconnect;

receiving the deadlock probe signal indicating a deadlock condition of the bus interconnect in response to the assertion of the deadlock probe signal; and

detecting the deadlock condition in the bus interconnect based on the received deadlock probe signal.

26. The method of claim 25, further comprising detecting the deadlock condition in the bus interconnect in a deadlock state if the deadlock probe signal on the input probe interface indicates a deadlock state.

27. The method of claim 26,

further comprising:

initializing the deadlock probe counter to an initial deadlock probe count value in response to the assertion of the deadlock probe signal;

updating a deadlock probe count value in the deadlock probe counter based on a clock signal; and

detecting the deadlock condition in the bus interconnect based on the received deadlock probe signal when the deadlock probe count value of the deadlock probe counter has expired.

28. The method of claim 27, further comprising detecting the deadlock condition in the bus interconnect in a deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect before the deadlock probe count value of the deadlock probe counter has expired.

29. The method of claim 22, further comprising, in response to detecting the deadlock condition in the bus interconnect indicating the deadlock state:

initializing a throttle communications counter to an initial throttle communications count value;

updating a throttle communications count value in the throttle communications counter based on a clock signal; and

in response to expiration of the throttle communications count value in the throttle communications counter, generating the deadlock recovery indicator indicating the deadlock recovery state.

30. The method of claim 22, further comprising:

determining if the deadlock recovery buffer is empty; and

generating the deadlock recovery indicator indicating the deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect and the deadlock recovery buffer being empty.

31. The method of claim 30, wherein, in response to detecting the deadlock condition in the bus interconnect indicating the deadlock state:

initializing a deadlock recovery counter to an initial deadlock recovery count value;

updating a deadlock recovery count value in the deadlock recovery counter based on a clock signal; and

in response to expiration of the deadlock recovery count value in the deadlock recovery counter, generating the deadlock recovery indicator indicating the deadlock non-recovery state in response to receipt of a bus communications token from the bus interconnect and the deadlock recovery buffer being empty.

32. A bus interconnect system, comprising:

a bus interconnect, comprising;

a communications bus; and

a plurality of router circuits each communicatively coupled to the communications bus, each of the plurality of router circuits configured to act as a sender router circuit to send bus transaction messages on the communications bus and to act as a receiver router circuit to receive the bus transaction messages on the communications bus; and

a deadlock recovery circuit, comprising;

a bus interconnect input interface communicatively coupled to the bus interconnect configured to receive input bus transaction messages from the bus interconnect, each of the input bus transaction messages comprising a data packet;

a bus interconnect output interface configured to receive output bus transaction messages each comprising a data packet from the received input bus transaction messages to be forwarded to the bus interconnect; and

a deadlock recovery buffer configured to store at least one data packet;

the deadlock recovery circuit configured to;

receive the input bus transaction messages on the bus interconnect input interface;

forward the output bus transaction messages on the bus interconnect output interface, each of the output bus transaction messages comprising at least one data packet from the received input bus transaction messages;

detect a deadlock condition in the bus interconnect; and

in response to the detected deadlock condition in the bus interconnect indicating a deadlock state, selectively communicatively couple the deadlock recovery buffer to the bus interconnect output interface.

33. The bus interconnect system of claim 32, further comprising a deadlock probe signal bus configured to receive a deadlock probe signal;

each of the plurality of router circuits communicatively coupled to the deadlock probe signal bus and configured to assert a deadlock state on the deadlock probe signal; and

the deadlock recovery circuit configured to detect the deadlock condition in the bus interconnect by being configured to;

assert a deadlock probe signal on the deadlock probe signal bus indicating a deadlock non-recovery state; and

receive the deadlock probe signal from the deadlock probe signal bus indicating a deadlock condition of the bus interconnect in response to the assertion of the deadlock probe signal on the deadlock probe signal bus; and

detect the deadlock condition in the bus interconnect in a deadlock state if the deadlock probe signal indicates a deadlock state.