Method and system for controlling information flow in a high frequency digital system from a producer to a buffering consumer via an intermediate buffer

• US 6,598,086 B1
• Filed: 11/09/1999
• Issued: 07/22/2003
• Est. Priority Date: 11/09/1999
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Starke, William John, Clark, Leo James, Cargnoni, Robert Alan, Bell, Robert Henry Jr.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): LIN, WEN TAI
• Application Number:
  US09/436,961
• Time in Patent Office: 1,351 Days
• Field of Search: 709/227-229, 709/230, 709/213, 709/312-313, 709/232-233, 709/215, 709/217, 709/250, 370/431-433, 370/437, 370/439, 370/352-353, 370/389, 370/390, 370/392, 370/398, 370/400, 370/402, 370/409-412, 370/414, 370/416, 370/429, 370/424, 370/460, 370/462, 370/468, 370/230, 370/259
• US Class Current: 709/233
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

An information handling system includes a plurality of sequentially connected units including a first unit, a second unit and a third unit. Packets of information flow from the first unit directly to the second unit and then to the third unit, and each of the plurality of units provides a respective dynamic output indication indicating if that unit output a packet. The information handling system further includes a control unit that determines, utilizing all of the plurality of dynamic output indications, packet buffering capacities of the plurality of units, and guaranteed packet flows between adjacent ones of the plurality of units, if the first unit can output a packet directly to the second unit without packet loss. In response to this determination, the control unit outputs a control signal to the first unit.

Claims

1. A method for dynamically controlling ongoing packet flow in an information pipeline containing a plurality of sequentially connected units including a first unit, a second unit and a third unit, wherein packets flow in a forward direction from said first unit directly to said second unit and then to said third unit and then out of said third unit, said method comprising:

at a control unit, receiving a respective dynamic output indication from each of said plurality of units, wherein each dynamic output indication indicates if a respective one of said plurality of units has output a respective one of a plurality of different packets in the forward direction;

said control unit dynamically determining during packet flow in the forward direction from at least some of said plurality of units if said first unit can output a packet directly to said second unit without packet loss, wherein said control unit performs said determining utilizing all of said dynamic output indications, packet buffering capacities of said plurality of units, and guaranteed packet flows between adjacent ones of said plurality of units, wherein said determining is further based upon a number of packets said control unit has authorized said first unit to output within a feedback latency of said control unit, wherein said feedback latency includes a first latency for a control signal to reach said first unit from said control unit and a second latency for a output indication generated by said control unit to reach said control unit from said first unit; and

in response to said determining, said control unit generating and outputting a control signal to said first unit indicative of whether said first unit can output a packet directly to said second unit without packet loss, wherein said outputting said control signal to said first unit utilizes a control feedback path physically separate from said information pipeline.

2. The method of claim 1, wherein determining if said first unit can output a packet further comprises:

maintaining a consumer count of a number of packets buffered by said third unit;

calculating a sum of a buffer count indicating a number of packets held in said second unit and a grant count indicating a number of packets said first unit has been authorized to output within a feedback latency of said control unit; and

determining that said first unit can output a packet without packet loss if a buffer capacity of said second unit is larger than both (1) said sum plus a number of output indications from said first unit less a number of output indications from said second unit and less a minimum per-cycle packet flow from said second unit to said third unit and (2) said sum plus a number of output indications from said first unit plus said consumer count less a number of output indications from said third unit less a buffering capacity of said third unit.

3. The method of claim 2, wherein calculating said sum comprises calculating a buffer count subject to a transmission latency of said dynamic output indication of said first unit to reach said control unit.

4. The method of claim 1, wherein outputting a control signal comprises outputting a grant message indicating how many packets said first unit is permitted to output.

5. The method of claim 4, and further comprising in response to receipt of said grant message at said first unit, outputting at least one packet directly to said second unit.

6. The method of claim 5, wherein outputting at least one packet comprises outputting all information pertaining to said at least one packet, such that said first unit retains no record of said at least one packet.

7. The method of claim 1, wherein receiving a respective dynamic output indication from each of said plurality of units comprises receiving signaling via control signaling connections separate from said information pipeline.

8. The method of claim 1, wherein said plurality of units and said control unit are each implemented as components of a single integrated circuit device, and wherein said receiving, said determining and said outputting are all performed within the single integrated circuit device.

9. An information handling system, comprising:

an information pipeline containing a plurality of sequentially connected units including a first unit, a second unit and a third unit, wherein packets of information flow in a forward direction from said first unit directly to said second unit and then to said third unit and then out of said third unit, each of said plurality of units providing a respective dynamic output indication indicating if that unit has output a respective one of a plurality of different packets in the forward direction;

a control feedback path coupled to said first unit and physically separate from said information pipeline; and

a control unit coupled to said first unit by said control feedback path, wherein said control unit, during packet flow in the forward direction from at least some of said plurality of units, dynamically determines, utilizing all of said dynamic output indications, packet buffeting capacities of said plurality of units, and guaranteed packet flows between adjacent ones of said plurality of units, if said first unit can output a packet directly to said second unit without packet loss and, responsive thereto, generates and outputs a control signal to said first unit via said control feedback path indicative of whether said first unit can output a packet directly to said second unit without packet loss;

wherein said control unit further determines if said first unit can output a packet directly to said second unit without packet loss based upon a number of packets said control unit has authorized said first unit to output within a feedback latency of said control unit, wherein said feedback latency includes a first latency for a control signal to reach said first unit from said control unit and a second latency for a output indication to reach said control unit from said first unit.

10. The information handling system of claim 9, wherein said control unit further comprises:

a counter set that maintains a buffer count of a number of packets residing in said second unit, a grant count of a number of packets said first unit has been authorized to output within a feedback latency of said control unit, and a consumer count of a number of packets buffered by said third unit;

determination logic that determines that said first unit can output a packet without packet loss if a buffer capacity of said second unit is larger than both (1) a sum of said buffer count and said grant count plus a number of said output indications from said first unit less a number of output indications from said second unit and less a guaranteed packet flow from said second unit to said third unit and (2) said sum plus a number of said output indications from said first unit plus said consumer count less a number of output indications from said third unit less a buffering capacity of said third unit.

11. The information handling system of claim 10, wherein said buffer count is subject to latency of said dynamic output indication from said first unit reaching said control unit.

12. The information handling system of claim 9, said control signal indicating how many packets said first unit is permitted to output.

13. The information handling system of claim 9, wherein said first unit is memoriless such that said first unit has no record of packets that have been output.

14. The information handling system of claim 9, wherein said first unit outputs a packet only in response to receipt of a control signal from said control unit authorizing outputting of a packet.

15. The information handling system of claim 9, and further comprising:

first, second and third control signaling connections separate from said information pipeline, wherein said first, second and third control signaling connections couple said plurality of sequentially connected units to said control unit, and wherein said control unit receives said plurality of dynamic output indications via said first second and third control signaling connections.

16. The information handling system of claim 9, wherein said plurality of units and said control unit are each implemented as components of a single integrated circuit device.

17. A controller for dynamically controlling ongoing packet transfer in an information handling system including an information pipeline containing a plurality of sequentially connected units including a first unit, a second unit and a third unit, wherein packets of information flow in a forward direction from said first unit directly to said second unit and then to said third unit and then out of said third unit, said controller comprising:

an input set receiving a respective dynamic output indication from each of said plurality of units, wherein each dynamic output indication indicates if a respective one of said plurality of units has output a respective one of a plurality of different packets in the forward direction; and

determination logic that, during packet flow in the forward direction from at least some of said plurality of units, dynamically determines, utilizing all of said dynamic output indications, packet buffering capacities of said plurality of units, and guaranteed packet flows between adjacent ones of said plurality of units, if said first unit can output a packet directly to said second unit without packet loss and, responsive thereto, generates and outputs a control signal to said first unit indicative of whether said first unit can output a packet directly to said second unit without packet loss, wherein said determination logic outputs said control signal to said first unit via a feedback control path physically separate from said information pipeline;

wherein said determination logic further determines if said first unit can output a packet directly to said second unit without packet loss based upon a number of packets said controller has authorized said first unit to output within a feedback latency of said controller, wherein said feedback latency includes a first latency for a control signal to reach said first unit from said controller and a second latency for a output indication to reach said controller from said first unit.

18. The controller of claim 17, wherein:

said controller further comprises a counter set that maintains a buffer count of a number of packets residing in said second unit, a grant count of a number of packets said first unit has been authorized to output within a feedback latency of said controller, and a consumer count of a number of packets buffered by said third unit; and

said determination logic determines that said first unit can output a packet without packet loss if a buffer capacity of said second unit is larger than both (1) a sun of said buffer count and said grant count plus a number of said output indications from said first unit less a number of output indications from said second unit and less a guaranteed packet flow from said second unit to said third unit and (2) said sum plus a number of said output indications from said first unit plus said consumer count less a number of output indications from said third unit less a buffering capacity of said third unit.

19. The controller of claim 18, wherein said buffer count is subject to latency of said dynamic output indication from said first unit reaching said controller.

20. The controller of claim 17, said control signal indicating how many packets said producer is permitted to output.

21. A program product for dynamically controlling packet transfer in an information handling system including an information pipeline containing a plurality of sequentially connected units including a first unit, a second unit and a third unit, wherein packets of information flow in a forward direction from said first unit directly to said second unit and then to said third unit and then out of said third unit, said program product comprising:

input code receiving a respective dynamic output indication from each of said plurality of units, wherein each dynamic output indication indicates if a respective one of said plurality of units has output a respective one of a plurality of different packets in the forward direction;

determination code that, during packet flow in the forward direction from at least some of said plurality of units, dynamically determines, utilizing all of said dynamic output indications, packet buffering capacities of said plurality of units, and guaranteed packet flows between adjacent ones of said plurality of units, if said first unit can output a packet directly to said second unit without packet loss and, responsive thereto, generates and outputs a control message to said first unit indicative of whether said first unit can output a packet directly to said second unit without packet loss,

wherein said determination code outputs said control signal to said first unit via a feedback control path physically separate from said information pipeline, and

wherein said determination code further determines if said first unit can output a packet directly to said second unit without packet loss based upon a number of packets that said first unit is authorized to output within a control feedback latency, said feedback latency including a first latency for a control signal to reach said first unit from said determination code and a second latency for an output indication to reach said input code from said first unit; and

a data processing system usable medium encoding said input code and said determination code.

22. The program product of claim 21, wherein:

said program product further comprises counter code that maintains a buffer count of a number of packets residing in said second unit, a grant count of a number of packets said first unit has been authorized to output within a control feedback latency, and a consumer count of a number of packets buffered by said third unit; and

said determination code determines that said first unit can output a packet without packet loss if a buffer capacity of said second unit is larger than both (1) a sum of said buffer count and said grant count plus a number of said output indications from said first unit less a number of output indications from said second unit and less a guaranteed packet flow from said second unit to said third unit and (2) said sum plus a number of said output indications from said first unit plus said consumer count less a number of output indications from said third unit less a buffering capacity of said third unit.

23. The program product of claim 22, wherein said buffer count is subject to a transmission latency of said dynamic output indication from said first unit to be received by said input code.

24. The program product of claim 21, said control message indicating how many packets said producer is permitted to output.