Bus protocol independent method and structure for managing transaction priority, ordering and deadlocks in a multi-processing system

• US 6,678,773 B2
• Filed: 01/11/2001
• Issued: 01/13/2004
• Est. Priority Date: 01/13/2000
• Status: Expired due to Term

• Current Assignee: Mercury Computer Systems Incorporated, NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Mercury Computer Systems Incorporated, Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Bouvier, Daniel L., Frisch, Robert C., Marietta, Bryan D.
• Primary Examiner(s): VO, TIM T
• Application Number:
  US09/758,855
• Publication Number:
  US 20010032282A1
• Time in Patent Office: 1,097 Days
• Field of Search: 710/200, 710/220, 710/241, 710/242, 710/243, 710/244
• US Class Current: 710/200
• CPC Class Codes: G06F 15/17 using an input/output type connection, e.g. channel, I/O port

Abstract

A multi-processing system (50) utilizes an interconnect fabric (59) for coupling endpoint devices (52, 54, 56, 66, 67). Bus control functions are managed in a method which is bus protocol independent. Each of the endpoint devices and the fabric function by specific rules to transfer data having a priority. Within the interconnect, higher priority data transfers take precedence of servicing, and for equal priority data the data is serviced first-in, first-out. Requests of endpoint devices that require a response can not be sent at the highest priority. Endpoint devices may not allow the acceptance of data to be contingent on outputting data of equal or lesser priority than the priority of the incoming data. Transaction priority, ordering and deadlocks are efficiently handled without the interconnect fabric needing to implement a set of bus protocol rules. Within the endpoint devices, additional rules related to ordering may be implemented.

Claims

1. In a multi-processing system having a first endpoint device coupled to a second endpoint device via an interconnect, a method for managing transaction transfers, comprising:

creating a priority system in both the first endpoint device and the second endpoint device for the exchange of transaction information in the system wherein;

(1) requests for transaction information that require a response can never be issued at the highest priority;

(2) no endpoint device may allow the acceptance of input transaction information to be contingent on outputting transaction information of equal or lesser priority than the input transaction information;

(3) highest prioritized transaction information must be able to be serviced before lower prioritized transaction information when lower prioritized transactions can not make forward progress; and

(4) for transaction information of a same priority level, transaction information is serviced on a first-in, first-out basis;

in the first endpoint device, implementing a request transaction of the second endpoint device;

transferring the request transaction from the first endpoint device to the second endpoint device via the interconnect; and

in the second endpoint device, implementing the request from the first endpoint device.

2. The method of claim 1 further comprising:

implementing the interconnect as a circuit device, the circuit device having logic circuitry which;

(1) communicates the input transaction information on a highest priority-first basis; and

(2) communicates input transaction information of a same priority on a first-in, first-out (FIFO) basis.

3. The method of claim 1 wherein the step of implementing at the second endpoint device the request from the first endpoint device further comprises:

the second endpoint device responding by communicating a response to the first endpoint device.

4. The method of claim 1 further comprising:

implementing a first bus protocol in the first endpoint device; and

implementing a second bus protocol in the second endpoint device, wherein the interconnect has no dedicated circuitry which is required to implement either the first bus protocol or the second bus protocol.

5. The method of claim 1 further comprising implementing the interconnect as a circuit device which does not have circuitry specifically dedicate to implement a predetermined bus protocol implemented in the first endpoint device.

6. The method of claim 1 further comprising implementing the interconnect as a system bus conductor to couple the first endpoint device to the second endpoint device.

7. The method of claim 1 further comprising implementing the first endpoint device as a data processor and implementing the second endpoint device as a memory controller.

8. The method of claim 1 further comprising coupling additional endpoint devices to the interconnect, each of which implements the priority system.

9. The method of claim 1 further comprising:

selectively bypassing servicing of transaction information on a first-in, first-out basis to avoid a deadlock condition in the multi-processing system by promoting a transaction priority to enable a promoted transaction in be serviced.

10. A multi-processing system comprising:

a first endpoint device having a first bus interface unit;

a second endpoint device having a second bus interface unit;

an interconnect for coupling the first endpoint device and the second endpoint device,

wherein each of the first endpoint device and the second endpoint device comprise circuitry for creating a priority system for the exchange of transaction information in the system wherein;

(1) requests for transaction information that require a response can never be issued at a highest priority;

(2) neither the first endpoint device nor the second endpoint device may allow the acceptance of input transaction information to be contingent on outputting transaction information of equal or lesser priority than the input transaction information;

(3) highest prioritized transaction information must be able to be serviced before lower prioritized transaction information when lower prioritized transactions can not make forward progress; and

(4) for transaction information of a same priority level, transaction information is serviced on a first-in, first-out basis.

11. The multi-processing system of claim 10 wherein the interconnect is a circuit device, the circuit device having logic circuitry which:

(1) communicates input transaction information on a highest priority-first basis; and

(2) communicates input transaction information of a same priority on a first-in, first-out (FIFO) basis.

12. The multi-processing system of claim 10 further comprising:

a bypass mechanism in each of the first endpoint device and the second endpoint device for selectively bypassing servicing of transaction information on the first-in, first-out basis to avoid a deadlock condition in the multi-processing system by promoting a transaction priority to enable a promoted transaction to be serviced.

13. The multi-processing system of claim 11 wherein the interconnect is a multiple conductor bus.

14. The multi-processing system of claim 11 wherein the interconnect is a plurality of circuit devices, each of the circuit devices having logic circuitry which:

(1) communicates input transaction information on a highest priority-first basis; and

(2) communicates input transaction information of a same priority on a first-in, first-out (FIFO) basis.

15. The multi-processing system of claim 12 wherein the bypass mechanism further comprises logic circuitry for detecting a deadlock condition caused by inadequate storage to be able to service transaction information of a predetermined priority on the first-in, first-out basis and promoting the transaction priority by either raising a priority value of the transaction of the predetermined priority or by directly routing the transaction of the predetermined priority to the interconnect.

16. A system interconnect for ordering transactions between multiple processing elements, comprising:

an input for receiving data from a first of the multiple processing elements;

a bit parser having an input coupled to the input for receiving the data and selecting a predetermined number of bits from the data, the bit parser providing the predetermined number of bits to an output terminal;

priority decode logic having an input coupled to the output terminal of the bit parser, the priority decode logic analyzing the predetermined number of bits and determining a priority level assigned to the data which has been received, the priority decode logic providing a control signal which indicates the priority level;

a multiplexer having an input coupled to the input for receiving the data from the first of the multiple processing elements, the multiplexer having a control input for receiving the control signal and having a plurality of prioritized outputs, the multiplexer providing the data at a selected one of the plurality of prioritized outputs in response to the control signal;

a storage device coupled to the multiplexer for receiving the data from the multiplexer and storing the data in priority designated regions; and

selection logic circuitry coupled to the storage device, the selection logic circuitry providing the data from the storage device at an output of the system interconnect by observing the rules of providing transactions on a highest priority first basis, and within a same priority on a first-in, first-out basis,

wherein by observing the rules the system interconnect avoids transaction deadlocking of information transfers and properly prioritizes and orders transactions regardless of specific bus protocol functionality implemented by the multiple processing elements.

17. The system interconnect of claim 16 wherein the predetermined number of bits from the data is two.

18. The system interconnect of claim 16 further comprising a second of the multiple processing elements, the second of the multiple processing elements being based on a communication bus protocol which is different from the first of the multiple processing elements.

19. The system interconnect of claim 16 wherein the priority decode logic selectively bypasses servicing of transaction information on the first-in, first-out basis to avoid a deadlock condition in the storage device by promoting a transaction priority to enable a promoted transaction to be serviced.

20. The system interconnect of claim 19 wherein transaction information is selectively routed from the multiplexer to the output of the system interconnect to avoid a deadlock condition in the system interconnect due to a lack of storage capacity of the storage device.