# US 2004/0064627 A1 · Method and apparatus for ordering interconnect transactions in a computer system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0064627 A1
- Document ID: US20040064627A1
- Status: Published application
- Kind: A1
- Application number: 10/259,241
- Filed: 2002-09-27
- Published: 2004-04-01
- Earliest claimed: 2002-09-27
- Assignees: Compaq Information Technologies Group, L.P.
- Inventors: Paras A. Shah; Ryan J. Hensley
- Web page: https://patentgrep.com/patent/US20040064627A1

## CPC

- G06F 13/4031: {with arbitration}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system allows queuing interconnect transactions of a first transaction type and a second transaction type according to an interconnect protocol for a computer system with multiple nodes in a transaction order queue (TOQ). Interconnect transactions are dequeued from the TOQ and scheduled for a destination node through a buffer between the TOQ and a scheduler. Interconnect transactions of the first transaction type are blocked from the scheduler until all interconnect transactions scheduled for other nodes in the computer system have completed. No interconnect transactions are dequeued from the TOQ while an interconnect transactions of the first transaction type is blocked from the scheduler. The queuing technique imposes an additional ordering on interconnect transactions in addition to ordering rules of the interconnect protocol.

## Claims

### Claim 1

A method of ordering interconnect transactions in a computer system having a plurality of nodes, comprising the steps of:
(a) receiving an interconnect transaction from an interconnect interface, the interconnect interface operating according to an interconnect protocol;
(b) identifying a transaction type of the interconnect transaction;
(c) enqueueing the interconnect transaction as a queued transaction on a transaction ordering queue (TOQ), imposing a stricter ordering on the interconnect transaction than an interconnect-protocol-imposed ordering;
(d) dequeueing the queued transaction from the TOQ as a dequeued transaction;
(f) if the dequeued transaction is of a second transaction type, scheduling the dequeued transaction for a destination node of the plurality of nodes;
(g) if the dequeued transaction is of a first transaction type and no transactions are active for any of the plurality of nodes other than the destination node, scheduling the dequeued transaction for the destination node; and
(h) if the dequeued transaction is of the first transaction type and any transactions are active for any of the plurality of nodes other than the destination node, blocking the dequeued transaction from scheduling and blocking the execution of step (d) until no transactions are active for any of the plurality of nodes other than the destination node.

### Claim 2 (depends on 1)

The method of claim 1, step (a) comprising the step of:
buffering the dequeued transaction in a buffer of a plurality of buffers; and
if the interconnect transaction is of the second transaction type and no transactions of the first transaction type are in the TOQ and no transactions of the first type are awaiting scheduling in any of the plurality of buffers, bypassing step (c)-(d) and handling the interconnect transaction as a dequeued transaction,
wherein steps (f) and (g) schedule the dequeued transaction from the plurality of buffers.

### Claim 3 (depends on 1)

The method of claim 1, wherein the interconnect interface operates according to the PCI-X extension of the PCI protocol.

### Claim 4 (depends on 3)

The method of claim 3, wherein the second transaction type is a relaxed ordering type transaction type and the first transaction type is a non-relaxed ordering transaction type.

### Claim 5 (depends on 1)

The method of claim 1, step (g) comprising the steps of:
(g1) counting dequeued transactions scheduled for the destination node; and
(g2) counting dequeued transactions completed on the destination node.

### Claim 6 (depends on 5)

The method of claim 5,
step (g1) comprising the step of:
updating a counter associated with the destination node to indicate the dequeued transaction has been scheduled for the destination node;
step (g2) comprising the step of:
updating the counter to indicate the dequeued transaction has been completed on the destination node.

### Claim 7 (depends on 6)

The method of claim 6,
step (g1) comprising the step of:
incrementing the counter;
step (g2) comprising the step of:
decrementing the counter,
wherein no transactions are active for any of the plurality of nodes other than the destination node if the counter associated with each of the plurality of nodes other than the destination node is zero, and
wherein the counter associated with each of the plurality of nodes is initialized to zero.

### Claim 8 (depends on 6)

The method of claim 6,
step (g1) comprising the step of:
decrementing the counter;
step (g2) comprising the step of:
incrementing the counter,
wherein no transactions are active for any of the plurality of nodes other than the destination node if the counter associated with each of the plurality of nodes other than the destination node is a maximum value, and
wherein the counter associated with each of the plurality of nodes is initialized with the maximum value.

### Claim 9

A system for ordering interconnect transactions in a computer system with a plurality of nodes, comprising:
an interconnect interface, coupled to an interconnect operating according to an interconnect protocol;
a transaction ordering queue (TOQ), coupled to the interconnect interface, adapted to queue interconnect transactions as queued transactions of a first transaction type and a second transaction type, imposing a stricter ordering on the interconnect transactions than an interconnect-protocol-imposed ordering, further adapted to dequeue queued transactions as dequeued transactions;
a scheduler, adapted to schedule a dequeued transaction from the TOQ;
a plurality of buffers, the plurality of buffers coupled to the TOQ and the scheduler and adapted to buffer interconnect transactions for scheduling by the scheduler for a destination node of the plurality of nodes;
circuitry to send the dequeued transaction to the scheduler from the plurality of buffers; and
circuitry to block the dequeued transaction from the scheduler if the dequeued transaction is of the first transaction type and any interconnect transactions are active on any of the nodes of the plurality of nodes other than the destination node.

### Claim 10 (depends on 9)

The system of claim 9, the circuitry to send the dequeued transaction to the scheduler from the plurality of buffers comprising:
a plurality of counters, each of the plurality of counters associated with one of the plurality of nodes, each of the plurality of counters adapted to count active transactions scheduled on the associated node;
circuitry to update the counter associated with the destination node of the dequeued transaction when the dequeued transaction is scheduled by the scheduler for the destination node; and
circuitry to update the counter associated with the destination node when any dequeued transaction is completed by the destination node.

### Claim 11 (depends on 10)

The system of claim 10,
wherein the circuitry to update the counter associated with the destination node increments the counter, and
wherein the circuitry to update the counter associated with the destination node when any dequeued transaction is completed by the destination node decrements the counter.

### Claim 12 (depends on 10)

The system of claim 10,
wherein the circuitry to update the counter associated with the destination node decrements the counter, and
wherein the circuitry to update the counter associated with the destination node when any dequeued transaction is completed by the destination node increments the counter.

### Claim 13 (depends on 9)

The system of claim 9,
wherein the interconnect protocol allows interconnect transactions of the second transaction type to pass interconnect transactions of the first transaction type and interconnect transactions of the second transaction type, and
wherein interconnect transactions of the second transaction type enqueued in the TOQ can not pass interconnect transactions of the first transaction type enqueued in the TOQ.

### Claim 14 (depends on 9)

The system of claim 9, the TOQ comprising:
circuitry to queue interconnect transactions in a first-in-first-out (FIFO) queue; and
circuitry to dequeue a queued transaction from the FIFO queue.

### Claim 15 (depends on 9)

The system of claim 9,
wherein the interconnect protocol is the PCI-X extension to the PCI protocol,
wherein interconnect transactions of the second transaction type have the Relaxed Ordering attribute set in an attribute phase of the interconnect transactions, and
wherein interconnect transactions of the first transaction type have the Relaxed Ordering attribute unset in the attribute phase of the interconnect transactions.

### Claim 16 (depends on 9)

The system of claim 9, wherein interconnect transactions of the second transaction type are not enqueued in the TOQ if no interconnect transactions of the first transaction type are in the plurality of buffers and no interconnect transactions of the first transaction type are in the TOQ.

### Claim 17 (depends on 9)

The system of claim 9, wherein the interconnect interface, the TOQ, the scheduler, and the plurality of buffers are implemented in an application-specific integrated circuit (ASIC).
