Optimized streaming in an un-ordered interconnect

• US 10,423,466 B2
• Filed: 10/18/2016
• Issued: 09/24/2019
• Est. Priority Date: 12/15/2015
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: Tummala, Ashok Kumar, Jalal, Jamshed, Meyer, Paul Gilbert, Kaseridis, Dimitrios
• Primary Examiner(s): Patel, Hiren P
• Application Number:
  US15/296,283
• Publication Number:
  US 20170168876A1
• Time in Patent Office: 1,071 Days
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: H04L 65/60 Network streaming of media packets

Abstract

A method, system, and device provide for the streaming of ordered requests from one or more Senders to one or more Receivers over an un-ordered interconnect while mitigating structural deadlock conditions.

Claims

1. A method of optimized streaming in a data processing system, the method comprising:

transmitting in any order first and second reservation requests for reservation of one or more resources over an un-ordered interconnect by a sender to a receiver;

responsive to receiving in any order the first and second reservation requests, the receiver reserving a resource of the one or more resources and transmitting an acknowledgement of the reservation to the sender;

the sender determining from the acknowledgement of the reservation whether the receiver has reserved the resource responsive to the first reservation request or to the second reservation request and further correlating the determined first or second reservation request with a first transaction request or a second transaction request, the second transaction request to be executed by the sender subsequent in order to execution, by the sender, of the first transaction request; and

responsive to the sender determining that the reserved resource is reserved for the second transaction request and that a second resource of the one or more resources for the first transaction request is not reserved within a period of time and a deadlock condition exists, the sender transmitting instructions to the receiver;

responsive to instructions received from the sender, the receiver;

releasing the resource reserved for the second transaction request and thereby breaking the deadlock condition; and

reserving the second resource for the first transaction request and transmitting a second acknowledgement of the reservation of the second resource; and

responsive to the second acknowledgement received from the receiver, the sender executing the first transaction request using the reserved second resource; and

when the receiver reserves the second resource for the first transaction request within the period of time;

the sender transmitting instructions to the receiver to execute the first transaction request using the second resource; and

the receiver executing the second transaction request using the resource in accordance with the transmitted instructions.

2. The method of claim 1, where determining that the deadlock condition exists further comprises detecting that the receiver does not reserve the second resource for the first transaction request within the period of time.

3. The method of claim 1, further comprising, prior to transmitting in any order the first and second reservation requests, the sender receiving the first and second transaction requests and establishing an ordering of the first and second transaction requests.

4. The method of claim 1, where the period of time is tracked by a timer having a timeout value, the method further comprising the sender starting the timer in response to one or more of issuance of the first transaction request, issuance of the second transaction request, and the acknowledgement that indicates the resource is reserved for the second transaction request.

5. The method of claim 1, where the period of time is tracked by a timer having a timeout value and where the timeout value is based on a fixed value, is programmable or is adaptive based upon hysteresis.

6. A method of optimized streaming in a data processing system, the method comprising:

transmitting in any order first and second reservation requests for reservation of one or more resources over an un-ordered interconnect by a sender to a receiver;

responsive to receiving in any order the first and second reservation requests, the receiver reserving a resource of the one or more resources and transmitting an acknowledgement of the reservation to the sender;

the sender determining from the acknowledgement of the reservation whether the receiver has reserved the resource responsive to the first reservation request or to the second reservation request and further correlating the determined first or second reservation request with a first transaction request or a second transaction request, the second transaction request to be executed subsequent in order to the first transaction request;

responsive to determining that the reserved resource is reserved for the second transaction request, the sender detecting whether the receiver also reserves within a period of time a second resource for the first transaction request;

when the receiver does not reserve the second resource for the first transaction request within the period of time, the sender determining that a deadlock condition exists, and the receiver, responsive to control by the sender, releasing the resource reserved for the second transaction request, reserving the second resource for the first transaction request and transmitting a second acknowledgement of the reservation of the second resource for the first transaction request and thereby breaking the deadlock condition;

the receiver executing the first transaction request using the reserved second resource and thereafter releasing the reserved second resource;

the sender transmitting to the receiver over the un-ordered interconnect a third reservation request to reserve a third resource for the second transaction request;

responsive to receiving the third reservation request, the receiver reserving the third resource for the second transaction request and transmitting a third acknowledgement of reservation of the third resource; and

the receiver executing the second transaction request using the reserved third resource and thereafter releasing the reserved third resource; and

when the receiver reserves the resource for the first transaction request within the period of time, further comprising;

the sender transmitting instructions to the receiver to execute the first transaction request using the resource; and

the receiver executing the second transaction request using the resource in accordance with the transmitted instructions.

7. The method of claim 6, where detecting whether the receiver also reserved within the period of time a second resource for the first transaction request further comprises:

the sender not receiving an acknowledgement of reservation of the second resource for the first transaction request; and

the receiver not transmitting within the period of time acknowledgement of reservation of the second resource for the first transaction request.

8. The method of claim 6, where the resource, the second resource, and the third resource are the same resource.

9. The method of claim 6, the receiver releasing for the second transaction request responsive to receiving a cancel message from the sender.

10. The method of claim 6, further comprising:

tracking, by the sender, the period of time by a timer having a timeout value based on a fixed value, a programmable value or an adaptive value based upon hysteresis.

11. The method of claim 10, further comprising the sender starting the timer in response to one or more of issuance of the first transaction request, issuance of the second transaction request, and the acknowledgement that indicates the resource is reserved for the second transaction request.

12. The method of claim 6, further comprising responsive to receiving the second acknowledgement:

the sender transmitting instructions to the receiver to execute the first transaction request using the reserved second resource.

13. The method of claim 6, further comprising responsive to receiving the third acknowledgement:

the sender transmitting instructions to the receiver to execute the second transaction request using the reserved third resource.

14. The method of claim 6, further comprising responsive to receiving the first transaction request and the subsequent second transaction request:

the sender transmitting reservation requests for the first and second resources over the unordered interconnect.

15. A sender device configured to transmit a plurality of transaction requests and a plurality of reservation requests in a data processing system, the sender device comprising:

a processor;

an outgoing requests element in communication with and controlled by the processor;

a deadlock detection element in communication with the processor; and

a response detector in communication with the deadlock detection element and configured to receive incoming communications;

the outgoing requests element configured to transmit in any order first and second reservation requests for reservation of one or more resources needed for execution of first and second transaction requests, the second transaction request to be executed by a receiver subsequent in order to the first transaction request,

responsive to receipt by the response detector of an acknowledgement of reservation of a resource, the deadlock detection element determines from the acknowledgment whether the resource is reserved responsive to the first reservation request or to the second reservation request and further correlates the determined first or second reservation request with a first transaction request or a second transaction request,

responsive to determination by the deadlock detection element of the sender device that the reserved resource is reserved for the second transaction request and that a second resource for the first transaction request is not reserved by the receiver within a period of time, the processor of the sender device is configured to generate instructions to;

release the resource reserved for the second transaction request and thereby break a deadlock condition detected by the deadlock detection element;

reserve the second resource for the first transaction request and transmit a second acknowledgement of the reservation of the second resource; and

execute the first transaction request using the reserved second resource, and

responsive to a determination by the deadlock detection element of the sender device that the reserved resource is reserved within the period of time, further comprising;

the sender transmitting instructions to the receiver to execute the first transaction request using the resource; and

the receiver executing the second transaction request using the resource in accordance with the transmitted instructions,

where the processor controls the outgoing requests element to transmit the instructions to the receiver.

16. The sender device of claim 15, where prior to the outgoing requests element transmitting in any order the first and second reservation requests, the response detector receiving the first and second transaction requests and establishing the order of the second transaction request subsequent the first transaction request.

17. The sender device of claim 15, where the deadlock detection element is configured to track the period of time with a timer having a timeout value based on a fixed value, a programmable value or an adaptive value based upon hysteresis.

18. The sender device of claim 17, where the deadlock detection element is configured to start the timer in response to one or more of issuance of the first transaction request, issuance of the second transaction request, and the acknowledgement that indicates the resource is reserved for the second transaction request.