Method and apparatus for queue depth detection in a memory system
A method and apparatus for detecting a queue depth of a memory queue in a memory system is described. The method includes estimating a start position of the queue by examining a portion of a queue start identifier of the memory queue, estimating an end position of the queue by examining a portion of a queue end identifier of the memory queue, and utilizing the start position and the end position to estimate the queue depth of the memory queue. The apparatus applies the method. One embodiment of the method and apparatus may be suitable for implementation on look-up tables of field general programmable gate arrays.
1. A method for detecting a queue depth of a memory queue in a memory system, comprising:
estimating, in a network interface card, a start position of the memory queue by examining a portion of a queue start identifier of the memory queue;
estimating, in the network interface card, an end position of the memory queue by examining a portion of a queue end identifier of the memory queue;
comparing the start position and the end position to estimate the queue depth of the memory queue; and
performing both a coarse-grained comparison of the first and second most significant bits of both the queue start identifier and the queue end identifier and a fine-grained comparison of the third and fourth most significant bits of both the queue start identifier and the queue end identifier to provide a warning window of time before queue full or queue empty conditions are encountered.
2. The method of claim 1 , wherein the queue start identifier is a queue start memory pointer, and the queue end identifier is a queue end memory pointer.
3. The method of claim 2 , wherein the memory queue is a first-in-first-out queue.
4. The method of claim 3 , wherein the queue start and queue end memory pointers are binary pointers.
5. The method of claim 4 , wherein the queue start identifier comprises binary bits, the portion of the queue start identifier is a subset of the binary bits of the queue start identifier, the queue end identifier comprises binary bits, and the portion of the queue end identifier is a subset of the binary bits of the queue end identifier.
6. The method of claim 5 , wherein the subset of binary bits of the queue start identifier includes the two most significant bits of the queue start pointer, and the subset of binary bits of the queue end identifier includes the two most significant bits of the queue end pointer.
7. The method of claim 6 , wherein the most significant bit of each of the queue start pointer and the queue end pointer is a redundant bit for determining a queue full and a queue empty condition.
8. The method of claim 7 , wherein the subset of the binary bits of the queue start identifier comprises the four most significant bits of the queue start memory pointer, and the subset of the binary bits of the queue end identifier comprises the four most significant bits of the queue end memory pointer.
9. The method of claim 8 , wherein the queue depth to be estimated is an almost empty condition of the memory queue.
10. The method of claim 9 , wherein the queue depth to be estimated is an almost full condition of the memory queue.
11. The method of claim 10 , wherein an adjustable threshold is provided for detecting the almost full condition.
12. The method of claim 11 , wherein the first and second most significant bits of each of the queue start and queue end pointers define one of four pointer quarters in a pointer space, and the step of comparing the start position and the end position to estimate the queue depth of the memory queue comprises:
determining from the first and second most significant bits of each of the queue start and queue end pointers whether the queue start and queue end pointers identify adjacent pointer quarters or the same pointer quarter; and
examining the third and fourth most significant bits of each of the queue start and queue end pointers for detecting the almost full condition if the queue start and queue end pointers identify adjacent quarters or the same pointer quarter.
13. The method of claim 12 , wherein the steps of determining whether the queue start and queue end pointers identify adjacent pointer quarters or the same pointer quarter, examining the third and fourth most significant bits and detecting the almost full condition are performed with the use of look-up tables.
14. The method of claim 13 , wherein the look-up tables are found within one or more field programmable gate arrays.
15. The method of claim 12 , wherein the steps of determining whether the queue start and queue end pointers identify adjacent pointer quarters or the same pointer quarter, examining the third and fourth most significant bits and detecting the almost full condition are performed with the use of application specific integrated circuits.
16. The method of claim 1 , further comprising:
selecting among optimistic, nominal, and pessimistic thresholds for the coarse-grained comparison.
17. The method of claim 1 , further comprising:
selecting among optimistic, nominal, and pessimistic thresholds for the fine-grained comparison.
18. The method of claim 1 , further comprising:
subdividing each quarter of pointer space into four sub-quadrants.
19. The method of claim 1 , further comprising:
performing the fine-grained comparison concurrently with the coarse-grained comparison.
20. The method of claim 1 , further comprising:
combining results of both the coarse-grained comparison and the fine-grained comparison.