Split-queue architecture with a first queue area and a second queue area and queue overflow area having a trickle mode and an overflow mode based on prescribed threshold values

• US 6,401,147 B1
• Filed: 05/24/1999
• Issued: 06/04/2002
• Est. Priority Date: 05/24/1999
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Erimli, Bahadir, Yang, Edward, Sang, Jinqlih
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mai, Rijue
• Application Number:
  US09/317,147
• Time in Patent Office: 1,107 Days
• Field of Search: 702/229, 710/14, 710/31, 710/38, 710/39, 710/54, 710/56, 710/7, 710/35, 710/52, 710/55, 710/57, 370/235, 370/390
• US Class Current: 710/56
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A programmable split-queue structure includes a first queue area for receiving entries, a second queue area for outputting entries input to said first queue area, and a queue overflow engine logically coupled to the first queue area and the second queue area. The queue overflow engine functions to transfer entries from the first queue area to the second queue area using one of two transfer modes. The queue overflow engine selects the most appropriate transfer mode based on a prescribed threshold value that can be dynamically programmed. An overflow storage area having high capacity may be provided in an external memory in order to increase the overall capacity of the queue structure.

Claims

1. A queue structure for queuing entries, comprising:

a first queue area for receiving entries, said first queue area including an input portion and an output portion;

a second queue area for outputting entries input to said first queue area, said second queue area including an input portion and an output portion;

a queue overflow engine logically coupled to both said first queue area and said second queue area, said queue overflow engine including logic circuitry for transferring entries from said first queue area to said second queue area using one of a trickle mode and an overflow mode, based on a prescribed threshold value that identifies one of a maximum number of entries allowed in said first queue area and a minimum number of entries allowed in said second queue area;

an overflow storage area operatively coupled to said queue overflow engine for selectively receiving entries from said first queue area and forwarding said entries to said second queue area, said overflow storage area having a relatively larger storage capacity than said first and second queue areas;

wherein said prescribed threshold value identifies a predetermined number of entries allowed in said first queue area, and said logic circuitry is further configured to;

compare the number of entries stored in said second queue area to a second prescribed threshold value that identifies a minimum number of entries allowed in said second queue area; and

if the number of entries stored in said second queue area is less than said second threshold value, then transferring entries into said second queue area using said trickle mode.

2. The queue structure of claim 1, wherein said overflow mode requires a first transfer of entries from the output portion of said first queue area into said overflow storage area, and a second transfer of entries from said overflow storage area into the input portion of said second queue area.

3. The queue structure of claim 1, wherein said trickle mode requires a transfer of entries directly from the output portion of said first queue area into the input portion of said second queue area.

4. The queue structure of claim 1, wherein said queue overflow engine transfers entries from said first queue area to said second queue area based on a priority associated with each entry.

5. The queue structure of claim 1, wherein said prescribed threshold value identifies a maximum number of entries allowed in said first queue area.

6. The queue structure of claim 1, wherein said prescribed threshold value identifies a minimum number of entries allowed in said second queue area.

7. The queue structure of claim 1, wherein said logic circuitry is further configured to perform the steps:

determine if said first queue area is empty; and

if said first queue area is empty, then performing the steps;

waiting a prescribed time interval for entries to be input to said first queue area,

if entries are input into said first queue area within said prescribed time interval, then transferring entries from said first queue area into said second queue area using said trickle mode, and

if no entries are input into said first queue area within said prescribed time interval, then transferring entries from said external memory area into said second queue area.

8. The queue structure of claim 7, wherein said prescribed time interval is determined based on the time required for the number of entries stored in said second queue area to reach said second prescribed threshold value.

9. A method of queuing entries into a queue structure, the method comprising the steps:

receiving entries in a first queue area of the queue structure;

comparing the number of entries stored in the first queue area to a prescribed threshold value that identifies one of a maximum number of entries allowed in the first queue area and a minimum number of entries allowed in the second queue area; and

transferring entries from the first queue area into a second queue area using one of a trickle mode and an overflow mode, based on the step of comparing;

determining, prior to performing the step of transferring, if there is available capacity in the second queue area;

performing the step of transferring based on both the step of comparing and the step of determining;

wherein the prescribed threshold value corresponds to a maximum number of entries allowed in the first queue area, and further comprising a step of setting a second threshold value corresponding to a minimum number of entries allowed in the second queue area;

wherein the step of transferring entries from the first queue area comprises the steps;

determining if the number of entries in the first queue area is greater than the first threshold value;

receiving additional entries into the first queue area if the number of entries stored therein is less than the first threshold value; and

transferring entries to an overflow storage area if the number of entries in the first queue area exceeds the first threshold value and the number of entries in the second queue area exceeds the second threshold value.

10. The method of claim 9, wherein a trickle mode is used, and the step of transferring entries from the first queue area includes a step of transferring entries from an output portion of the first queue area directly into an input portion of the second queue area.

11. The method of claim 9, wherein an overflow mode is used, and the step of transferring entries from the first queue area further includes the steps:

transferring entries from the first queue area into an overflow storage area; and

transferring entries from the overflow storage area into the second queue area.

12. The method of claim 9, wherein it is determined that there is available capacity in the second queue area, and the step of transferring includes a step of transferring entries from the first queue area into the second queue area using the trickle mode.

13. The method of claim 9, wherein it is determined that there is no available capacity in the second queue area, and the step of transferring includes a step of transferring entries from the first queue area into the second queue area using the overflow mode.

14. The method of claim 9, further comprising a step of dynamically setting the prescribed threshold value and the second threshold value based on the relative throughput of the queue structure.