Flow control mechanisms for avoidance of retries and/or deadlocks in an interconnect
Flow control mechanisms avoid or eliminate retries of transactions in a coherency interconnect. A class of transaction (CoT) framework is defined whereby individual transactions are associated with CoT labels consistent with chains of dependencies that exist between transactions initiated by any of the cooperating devices that participate in a given operation. In general, coherency protocols create dependencies that, when mapped to physical resources, can result in cycles in a graph of dependencies and deadlock. To support architectural mechanisms for deadlock avoidance, CoT labels are applied to individual transactions consistent with a precedence order of those transactions both (i) with respect to the operations of which such transactions are constituent parts and (ii) as amongst the set of such operations supported in the coherency interconnect. CoT labels applied to respective transactions constitute a CoT framework that may be used by coherency managers to efficiently support concurrent in-flight transactions without retry.
1. A method of controlling transaction flow in an event-based coherency interconnect operatively coupled between devices to support operations amongst the devices relative to a coherency domain of addressable memory locations, the method comprising:
associating class of transaction (CoT) labels with constituent transactions of the supported operations, wherein the CoT labels associated with respective constituent transactions of a particular supported operation differ, but are in accordance with an acyclic precedence order of the constituent transactions;
receiving transaction requests from devices linked to the coherency interconnect, wherein, for at least address-type ones of the received transaction requests, the received transaction requests each specify a CoT label;
the coherency interconnect supplying CoT labeled grant indications in correspondence with, and responsive to, a subset of the received, CoT labeled transaction requests, wherein by supplying a particular CoT labeled grant indication to a particular requesting device, the coherency interconnect grants unconditional availability of a buffer for a transaction of the corresponding class from the particular requesting device.
2. The method of claim 1 , further comprising:
wherein the subset of received, CoT labeled transaction requests for which corresponding CoT labeled grant indications are supplied is based on decision logic that ensures that, if a particular one of the received transaction requests is granted, interconnect resources are available for the particular transaction requested and for all possible successor transactions thereof after accounting for current and possible successor transactions that are constituents of uncompleted operations already in flight in the coherency interconnect.
3. The method of claim 1 , further comprising:
receiving from the particular requesting device, a transaction that corresponds to the particular CoT labeled grant indication; and
at the coherency interconnect, ordering the received transaction relative to at least a subset of other received transactions.
4. The method of claim 3 ,
wherein the received and ordered transaction is an address transaction, the method further comprising:
presenting the address transaction to a target device; and
presenting the address transaction to at least one snoop device.
5. The method of claim 4 ,
wherein the other received transactions include one or more of:
other address transactions from other requesting devices; and other address transactions destined for other target devices.
6. The method of claim 3 , further comprising:
presenting ordered subsets of the received transactions to respective ones of the devices, wherein, at least for transactions targeting addressable memory locations of a same coherency granule, ordering of the received transaction subsets presented to any particular device is in accord with a total ordering imposed by the coherency interconnect.
7. The method of claim 6 ,
wherein, for those of presented transactions labeled with a same CoT and targeting a same coherency granule, the respective devices process the presented transactions in an order presented by the coherency interconnect, and
wherein, for a pair of presented transactions labeled with different CoTs but targeting a same coherency granule, the respective devices process the pair of presented transactions in accord with a CoT-denominated order thereof.
8. The method of claim 3 ,
wherein the coherency interconnect implements plural ordering points; and wherein the ordering is relative to other transactions received at a same ordering point.
9. The method of claim 1 ,
wherein for each transaction that is a constituent of a particular instance of one of the supported operations, respective CoT labels are associated such that a first CoT label associated with a given transaction is precedence ordered with respect to a second CoT label associated with a predecessor of the given transaction, if any.
10. The method of claim 9 ,
wherein for a set of supported operations and for all possible dependency chains of constituent transactions thereof, associated CoT values are collectively in accord with the acyclic precedence order.
11. The method of claim 9 ,
wherein each of the constituent transactions of the particular operation instance is tagged, and thereby correlatable by the coherency interconnect with other constituent transactions of the particular operation instance.
12. The method of claim 1 ,
wherein at least some of the supported operations include a data-type transaction that is a successor, in the acyclic precedence order, of an initiating address-type transaction;
wherein data-type ones of the received transaction requests specify respective CoT labels; and
wherein responsive to a subset of the received, CoT labeled data-type transaction requests, the coherency interconnect supplies corresponding CoT labeled grant indications, wherein by supplying a particular CoT labeled grant indication to a particular requesting device, the coherency interconnect grants unconditional availability of data path resources for a data-type transaction of the corresponding class from the particular requesting device and for all possible successor data-type transactions of the same operation.
13. The method of claim 1 ,
wherein the supported operations include as constituents address-type, address-response-type and data-type transactions wherein at least the address-type transactions are subject to a CoT label denominated request-grant protocol, and
wherein no address-response-type transaction ever requires a correlated address transaction to be retried.
14. The method of claim 13 ,
wherein at least a subset of the data-type transactions are subject to a CoT label denominated request-grant protocol.
15. The method of claim 13 ,
wherein address-response-type transactions are each associated with respective CoT labels but are not subject to a CoT label denominated request-grant protocol.
16. The method of claim 1 ,
wherein the devices include processors, memory controllers and bridges;
wherein the coherency interconnect implements separate address path and data path portions; and
wherein at least initiating address-type transactions seek to transit the address path portion are subject a CoT label denominated request-grant protocol.
17. The method of claim 1 , further comprising:
transacting the supported operations amongst the devices without retry, at a transaction protocol layer, of any of the constituent transactions.
18. The method of claim 1 ,
wherein for at least some load-type ones of the supported operations, the constituent transactions include separate address-type, address response-type and data-type transactions.
19. An apparatus comprising:
a coherency manager for coupling between plural devices to support operations amongst the devices relative to a coherency domain of addressable memory locations, wherein at least some of the supported operations include plural constituent transactions, and wherein class of transaction (CoT) labels associated with respective constituent transactions of a particular supported operation differ, but are in accordance with an acyclic precedence order thereof of the constituent transactions;
a first set of interfaces of the coherency manager including signal paths for receiving transaction requests from respective ones of the devices, wherein, for at least address-type ones of the transaction requests, interfaces of the first set allow respective devices to specify respective CoT labels in correspondence with respective transaction requests; and
a second set of interfaces of the coherency manager including signal paths for supplying CoT labeled grant indications in correspondence with, and responsive to, a subset of the received, CoT labeled transaction requests, wherein supply of a particular CoT labeled grant indication to a particular device signifies unconditional grant to the particular device of availability of resources for a transaction of the corresponding class.
20. The apparatus of claim 19 , configured as a system on a chip (SoC) and further comprising:
the plural devices, including at least one memory controller and plural processors, each with integrated cache memory,
wherein the coherency manager and the first and second interfaces thereof are operatively coupled between the devices, and wherein the supported operations are transacted amongst the devices without retry, at a transaction protocol layer, of any of the constituent transactions.
21. The apparatus of claim 19 , further comprising:
a transaction table for representing status of constituent transactions of operations in flight in the coherency interconnect; and
decision logic operatively coupled to the transaction table and to the first and second interfaces, the decision logic operable to ensure that, if a particular one of the received transaction requests is granted, interconnect resources are available for the particular transaction requested and for all possible successor transactions thereof after accounting for current and possible successor transactions that are constituents of the operations already in flight in the coherency interconnect.
22. The apparatus of claim 19 , further comprising:
separate address path and data path portions of the coherency manager, wherein at least some of the supported operations include a data-type transaction that is a successor, in the acyclic precedence order, of an initiating address-type transaction, the data-type transaction transiting the data path portion and the address-type transaction transiting the address path portion;
the first set of interfaces including signal paths for receiving data-type ones of the transaction requests and thereby allowing respective ones of the devices to specify respective CoT labels in correspondence with respective data-type transaction requests; and
the second set interfaces including signal paths for supplying CoT labeled grant indications in correspondence with, and responsive to, a subset of the received, CoT labeled data-type transaction requests, wherein supply of a particular CoT labeled grant indication to a particular device signifies unconditional grant to the particular device of availability of data path resources for a data-type transaction of the corresponding class and for all possible successor data-type transactions of the same operation.
23. The apparatus of claim 22 ,
wherein for at least some load-type ones of the supported operations, the constituent transactions include separate address-type, address response-type and data-type transactions.
24. An apparatus comprising:
a device suitable for coupling with a coherency manager that supports operations amongst multiple devices relative to a coherency domain of addressable memory locations, wherein at least some of the supported operations include plural constituent transactions, and wherein class of transaction (CoT) labels associated with respective constituent transactions of a particular supported operation differ, but are in accordance with an acyclic precedence order of the constituent transactions;
the device including an interface that includes respective signal paths for presenting the coherency manager with a CoT-denominated request to initiate individual instances of at least address-type ones of the constituent transactions and for receiving from the coherency manager CoT-denominated grants, the interface further including signal paths for supplying CoT-labeled address-type transactions to the coherency manager in correspondence with respective ones of the received CoT-denominated grants.