Method and system for avoiding starvation and deadlocks in a split-response interconnect of a computer system

• US 6,108,739 A
• Filed: 04/29/1999
• Issued: 08/22/2000
• Est. Priority Date: 08/29/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Stone, Glen D., James, David V., North, Donald N.
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): Lefkowitz, Sumati
• Application Number:
  US09/301,865
• Time in Patent Office: 481 Days
• Field of Search: 710/113-125, 710/126-129, 710/240-244
• US Class Current: 710/113
• CPC Class Codes: G06F 13/4036 and deadlock prevention

Abstract

A system and method for avoiding starvation and deadlocks in a split-response-bus multiprocessor computer system. The multiprocessor computer system includes a first node and a second node coupled to the a split-response bus, wherein the first and second nodes communicate by passing request packets over the split-response bus. The method and system includes providing precedence information in the request packets, and then using the precedence information when receiving the request packets to determine which request packets to process and which request packets to reject when a conflict occurs.

Claims

1. A method for avoiding split-response-bus conflicts in a multiprocessor computer system, the multiprocessor computer system including a first node and a second mode coupled to the split-response bus, wherein the first and second nodes communicate by passing request packets over the split-response bus, wherein the first node is a requesting node, further wherein the multiprocessor system includes a PCI adapter having a node Id coupled to a split-response and to a PCI bus, the PCI adapter operable to detect a read request conflict when a split-response-to-PCI-BUS read request is received while a PCI-BUS-to-split-response read request is active, each of the read requests including a source Id and a target Id, the method including the steps of:

(a) providing precedence information in the request packets, wherein the multiprocessor system includes a particular topology, step (a) further including the step of;

(a1) providing the precedence information by including a precedence label in the request packets indicating where the requesting node is located in the topology of multiprocessor system; and

(b) using the precedence information upon receiving the request packets to determine which request packets to process and which request packets to reject when a conflict occurs

(c) performing conflict resolution by rejecting the received read request at the adapter unless I) the adapter node Id is less than the source Id within the received read-request, and ii) the adapter node Id is less than the target Id of the active read request.

2. A method as in claim 1 wherein step (a) further includes the steps of:

(a2) providing a first precedence label that indicates the requesting node is a split-response requestor;

(a3) providing a second precedence label that indicates the requesting node is a higher-level requestor in a bus hierarchy;

(a4) providing a third precedence label that indicates the requesting node is same-level requester; and

(a5) providing a fourth precedence label that indicates the requesting node is a lower-level requester.

3. A method as in claim 2 wherein the first precedence label is SPLIT, the second precedence label is MIN, the third precedence label is MID, and the fourth precedence label is MAX.

4. A method as in claim 3, wherein step (a) further includes the step of:

(a6) labeling requests as MIN, MID, and MAX in order to resolve hierarchical conflicts.

5. A method as in claim 4, wherein the detected read request conflict is caused by same-level read requests, step (c) further including the step of:

(c1) providing same-level read requests with the MID label.

6. A method as in claim 5, wherein step (c) further includes the step of:

(c2) sending a reject response from the PCI adapter after rejecting a read request;

(c3) indicating in the reject response whether the read request was attempting to access a half-duplex address or a full-duplex address;

(c4) in response to the reject response indicating a half-duplex address, providing a resent request with the MIN precedence label; and

(c5) in response to the reject response indicating a full-duplex address, providing a resent request with a MAX precedence label.

7. A multiprocessor computer system for avoiding starvation and deadlocks, comprising:

a split-response-bus;

a first node and a second node coupled to the split-response bus, wherein the first and second nodes communicate by passing request packets over the split-response;

wherein the first node is a requesting node;

precedence means for providing precedence information in the request packets, wherein the multiprocessor system includes a particular topology, wherein the precedence means provides a precedence label in the request packets indicating where the requesting node is located in the topology of multiprocessor system;

means for determining which request packets to process during a conflict and which request packets to reject based on the precedence information;

a PCI bus; and

a PCI adapter having a node Id coupled to a split-response and to the PCI bus, wherein the PCI adapter detects a read request conflict when a split-response-to-PCI-BUS read request is received while a PCI-BUS-to-split-response read request is active, each of the read requests including a source Id and a target Id, the adapter further including means for performing conflict resolution by rejecting the received read request at the adapter unless

I) the adapter node Id is less than the source Id within the received read-request, and

ii) the adapter node Id is less than the target Id of the active read request.

8. A system as in claim 7, wherein the precedence means provides a first precedence label that indicates the requesting node is a split-response requestor, provide a second precedence label that indicates the requesting node is a higher-level requester in a bus hierarchy, provides a third precedence label that indicates the requesting node is a same-level requester, and provides a fourth precedence label that indicates the requesting node is a lower-level requester.

9. A system as in claim 8, wherein the first precedence label is SPLIT, the second precedence label is MIN, the third precedence label is MID, and the fourth precedence label is MAX.

10. A system as in claim 9, wherein the precedence means labels requests as MIN, MID, and MAX in order to resolve asymmetric hierarchical conflicts.

11. The system as in claim 10, wherein the detected read request conflict is caused by same-level read requests, and the same-level read requests are provided with the MID labels.

12. A system as in claim 10, wherein the adapter sends a reject response from the PCI adapter after rejecting a read request, the reject response indicating whether the read request was attempting to access a half-duplex address or a full-duplex address, wherein in response to the reject response indicating a half-duplex address, a requesting node resends the request with the MIN precedence label, and wherein in response to the reject response indicating a full-duplex address, the requesting node resends the request with a MAX precedence label.