Credit-based flow control technique in a modular multiprocessor system

• US 20020146022A1
• Filed: 04/09/2001
• Published: 10/10/2002
• Est. Priority Date: 05/31/2000
• Status: Abandoned Application

• Current Assignee: Compaq Computer Corporation (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Steely, Simon C. Jr., Van Doren, Stephen R., Tierney, Gregory E., Sharma, Madhumitra
• Application Number:
  US09/829,038
• Publication Number:
  US 20020146022A1
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/506 Backpressure

Abstract

A credit-based, flow control technique utilizes a plurality of counters to conserve resources of a switch fabric within a modular multiprocessor system while ensuring that transaction packets pending in virtual channel queues of the fabric efficiently progress through those resources. The multiprocessor system includes a plurality of nodes interconnected by the switch fabric that extends from a global input port of a node through a hierarchical switch to a global output port of the same or another node. The resources include shared buffers within the global ports and hierarchical switch. Each counter is associated with a virtual channel queue and the flow control technique uses the counters to essentially create the structure of the shared buffers.

Claims

1. A method for creating a load balancing, deadlock-free virtual channel communication structure in a shared buffer resource of a switch fabric within a modular multiprocessor system, the switch fabric interconnecting a plurality of nodes and configured to transport transaction packets having a plurality of types from a global input port of a first node through a hierarchical switch to a global output port of a second node, the method comprising the steps of:

establishing within the switch fabric a plurality of virtual channel queues, each queue storing a type of transaction packet;

providing a plurality of counters, each counter associated with a virtual channel queue;

and

structuring the shared buffer resource through use of the counters so as to create;

a generic buffer region having entries for accommodating any type of transaction packet,

a forward progress region having one or more entries for accommodating a first type of transaction packet, and

a deadlock avoidance region having entries for accommodating one or more second types of transaction packets.

2. The method of claim 1 further comprising the steps of:

issuing a transaction packet from a virtual channel queue to the shared buffer resource;

in response to the step of issuing, incrementing the counter associated with the virtual channel queue, and one of;

if the packet is of the first type of transaction packet and a previous value of the associated counter is zero, assigning the packet to a respective entry of the forward progress region; and

if the packet is one of the second types of transaction packets and a previous value of the associated counter is equal to zero, assigning the packet to a respective entry of the deadlock avoidance region.

3. The method of claim 2 further comprising the steps of:

if the packet is of the first or one of the second types of transaction packets and a previous value of the associated counter is non-zero, assigning the packet to a respective entry of the generic buffer region; and

incrementing a generic counter in addition to the counter associated with the virtual channel packet.

4. The method of claim 3 further comprising the step of, when the generic counter reaches a predetermined value, issuing only those types of transaction packets that can be accommodated within unused entries of the deadlock avoidance and forward progress regions of the shared buffer resource.

5. The method of claim 4 further comprising the steps of:

removing a transaction packet from the shared buffer resource;

issuing an acknowledgement that specifies the type of transaction packet that was removed;

in response to the acknowledgement, decrementing the counter for the virtual channel queue associated with the transaction packet type that was removed from the shared buffer resource; and

if a successive value of the decremented counter is non-zero, decrementing the generic counter.

6. The method of claim 5 wherein

the first type of transaction packets correspond to programmed input/output (I/O) read and write requests, and

the second types of transaction packets correspond to:

read and write requests directed to memory,

ordered responses and probes associated with programmed I/O and memory read/write requests, and

unordered responses to programmed I/O and memory read/write requests.

7. The method of claim 6 wherein the virtual channel queues include:

a programmed input/output (I/O) read/write virtual channel queue;

a memory read virtual channel queue;

a memory write virtual channel queue;

an ordered response and probe virtual channel queue for responses and probes associated with programmed I/O and memory read/write requests, and

an unordered response virtual channel queue for responses associated with programmed I/O and memory read/write requests.

8. The method of claim 7 wherein the memory read and memory write virtual channel queues share a single counter.

9. The method of claim 1 wherein the shared buffer resource is dedicated to a single node of the multiprocessor system.

10. The method of claim 1 wherein the shared buffer resource is shared among a plurality of nodes of the multiprocessor system.

11. A switch fabric for interconnecting a plurality of nodes of a modular multiprocessor system, the nodes configured to source and receive transaction packets having a plurality of types, the switch fabric comprising:

a plurality of virtual channel queues, each queue configured and arranged to store a type of transaction packet;

a plurality of counters, each counter associated with a virtual channel queue;

an arbiter for incrementing and decrementing the counters; and

a shared buffer resource coupled to the virtual channel queues and configured to transport transaction packets among the nodes of the multiprocessor system,

wherein the arbiter utilizes the counters to organize the shared buffer resource into a plurality of regions including;

a generic buffer region having entries for accommodating any type of transaction packet,

a forward progress region having one or more entries for accommodating a first type of transaction packet, and

a deadlock avoidance region having entries for accommodating one or more second types of transaction packets.

12. The switch fabric of claim 11 wherein the arbiter, in response to a transaction packet being issued from a virtual channel queue to the shared buffer resource, increments the counter associated with the respective virtual channel queue, and one of:

if the packet is of the first type of transaction packet and a previous value of the associated counter is zero, the arbiter considers the packet as being assigned to a respective entry of the forward progress region of the shared buffer resource, and

if the packet is one of the second types of transaction packets and a previous value of the associated counter is equal to zero, the arbiter considers the packet as being assigned to a respective entry of the deadlock avoidance region.

13. The switch fabric of claim 12 wherein, if the packet is of the first or one of the second types of transaction packets and a previous value of the associated counter is non-zero, the arbiter considers the packet as being assigned to a respective entry of the generic buffer region, and increments a generic counter in addition to the counter associated with the virtual channel packet.

14. The switch fabric of claim 13 wherein the arbiter is configured such that, when the generic counter reaches a predetermined value, the arbiter issues only those types of transaction packets that can be accommodated within unused entries of the deadlock avoidance and forward progress regions of the shared buffer resource.

15. The switch fabric of claim 14 further comprising control logic operably coupled to the shared buffer resource, wherein

in response to a transaction packet being removed from the shared buffer resource, the control logic issues an acknowledgement to the arbiter that specifies the type of transaction packet that was removed,

in response to the acknowledgement, the arbiter decrements the counter for the virtual channel queue associated with the transaction packet type that was removed from the shared buffer resource, and

if a successive value of the decremented counter is non-zero, the arbiter decrements the generic counter.