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

Claim 3

A method as in claim 1 wherein the first node sends a first request packet to the second node and the second node rejects the first request packet, step (a) further including the step of: (a1) placing the time value into the first packet when the first node resends the first packet to the second node, thereby creating a resent request packet.

Claim 4

A method as in claim 2 wherein step (b) further includes the step of: (b2) rejecting request packets based on ones that have no time value because they have not-yet been resent, followed by rejecting the resent packets that have the largest time value.

Claim 5

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 and second nodes each include a queue for storing incoming request packets; precedence means for providing precedence information in the request packets, wherein the precedence means further includes a time value in the request packets indicating time of original packet transmission; and means for determining which request packets to process during a conflict and which request packets to reject based on the precedence information, wherein when either the queue for the first or second node becomes full, the determining means further includes comparing the time values included in the incoming request packets and rejecting the request packets having the largest time value.

Claim 6

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 and second nodes each include a queue for storing incoming request packets; precedence means for providing precedence information in the request packets, wherein the precedence means further includes a time value in the request packets indicating time of original packet transmission; and means for determining which request packets to process during a conflict and which request packets to reject based on the precedence information, wherein when either the queue for the first or second node becomes full, the determining means further includes comparing the time values included in the incoming request packets and rejecting the request packets having the largest time value.

Claim 7

A system as in claim 4 wherein the first node sends a first request packet to the second node and the second node rejects the first request packet, wherein the precedence means places the time value into the first packet when the first node resends the first packet to the second node, thereby creating a resent request packet.

Claim 8

A system as in claim 5 wherein the determining means rejects request packets based on ones that have no time value, followed by rejecting the resent packets that have the largest time value.

Claim 9

A computer-readable medium containing program instructions for avoiding starvation and deadlocks in a split-response-bus multiprocessor computer system, the multiprocessor computer system including a first node and a second node coupled to a split-response bus, wherein the first and second nodes communicate by passing request packets over the split-response, wherein the first and second nodes each include a queue for storing incoming request packets, the program instructions for: (a) providing precedence information in the request packets, wherein the providing instructions further includes the instructions for providing a time value in the request packets indicating time of original packet transmission; 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, wherein the instructions further includes instructions for determining which request packets to reject when either the queue for the first or the second nodes is full by comparing the time value included in all tentatively accepted request packets and rejecting the resent packets that have the largest time value.

Claim 10

A computer-readable medium containing program instructions for avoiding starvation and deadlocks in a split-response-bus multiprocessor computer system, the multiprocessor computer system including a first node and a second node coupled to a split-response bus, wherein the first and second nodes communicate by passing request packets over the split-response, wherein the first and second nodes each include a queue for storing incoming request packets, the program instructions for: (a) providing precedence information in the request packets, wherein the providing instructions further includes the instructions for providing a time value in the request packets indicating time of original packet transmission; 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, wherein the instructions further includes instructions for determining which request packets to reject when either the queue for the first or the second nodes is full by comparing the time value included in all tentatively accepted request packets and rejecting the resent packets that have the largest time value.

Claim 13

A method as in claim 8 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.

Claim 14

A method as in claim 9 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.

Claim 15

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 and the multiprocessor system includes a particular topology; precedence means for providing precedence information in the request packets, wherein the precedence information comprises a first precedence label that indicates the requesting node is a split-response requester, wherein the first label is SPLIT, a second precedence label that indicates the requesting node is a higher-level requester in a bus hierarchy, wherein the second label in MIN, a third precedence label that indicates the requesting node is a same-level requester, wherein the third label is MID, and a fourth precedence label that indicates the requesting node is a lower-level requester, wherein the fourth label is MAX, wherein the precedence means labels requests as MIN, MID, and MAX in order to resolve asymmetric hierarchical conflicts; a PCI bus; and a PCI adapter having a node Id coupled to the split-response bus 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, 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, 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.

Claim 16

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 and the multiprocessor system includes a particular topology; precedence means for providing precedence information in the request packets, wherein the precedence information comprises a first precedence label that indicates the requesting node is a split-response requester, wherein the first label is SPLIT, a second precedence label that indicates the requesting node is a higher-level requester in a bus hierarchy, wherein the second label in MIN, a third precedence label that indicates the requesting node is a same-level requester, wherein the third label is MID, and a fourth precedence label that indicates the requesting node is a lower-level requester, wherein the fourth label is MAX, wherein the precedence means labels requests as MIN, MID, and MAX in order to resolve asymmetric hierarchical conflicts; a PCI bus; and a PCI adapter having a node Id coupled to the split-response bus 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, 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, 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.

Claim 17

A computer-readable medium containing program instructions for avoiding starvation and deadlocks in a split-response-bus 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, wherein the first node is a requesting node, the program instructions for: (a) providing precedence information in the request packets, wherein the precedence information comprises a time value in the request packets indicating time of original packet transmission and identification of a location of the requesting node in a topology of the multiprocessor system, wherein the time value is placed into the first packet when the first node resends the first packet to the second node, thereby creating a resent request packet; 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.

Claim 18

A computer-readable medium containing program instructions for avoiding starvation and deadlocks in a split-response-bus 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, wherein the first node is a requesting node, the program instructions for: (a) providing precedence information in the request packets, wherein the precedence information comprises a time value in the request packets indicating time of original packet transmission and identification of a location of the requesting node in a topology of the multiprocessor system, wherein the time value is placed into the first packet when the first node resends the first packet to the second node, thereby creating a resent request packet; 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.

Claim 19

A computer-readable medium as in claim 12 wherein instruction (b) further includes the instruction of: (b2) rejecting request packets based on ones that have no time value because they have not-yet been resent, followed by rejecting the resent packets that have the largest time value.

Claim 20

A computer-readable medium as in claim 13 wherein the precedence information is implied from information included in standard request packets.

Claim 21

A computer-readable medium as in claim 14 wherein the first node is a requesting node, and the multiprocessor system includes a particular topology, instruction (a) further including an instruction for: (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.

Claim 22

A computer-readable medium as in claim 13 wherein instruction (a) further includes instructions for: (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 requester in a bus hierarchy; (a4) providing a third precedence label that indicates the requesting node is a same-level requester; and (a5) providing a fourth precedence label that indicates the requesting node is a lower-level requester.

Claim 23

A computer-readable medium as in claim 14 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.

Claim 24

A computer-readable medium as in claim 15 wherein instruction (a) further includes an instruction for: (a6) labeling requests as MIN, MID, and MAX in order to resolve asymmetric hierarchical conflicts.

Claim 25

A computer-readable medium as in claim 18 wherein the multiprocessor system further 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 further including the step of: (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 an received read-request, and ii) the adapter node Id is less than the target Id of the active read request.

Claim 26

A computer-readable medium as in claim 19 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.

Claim 27

A computer-readable medium as in claim 20 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.