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
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
106 Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
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. - View Dependent Claims (10, 11, 12, 13, 14)
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.
Specification