Hierarchical statistically multiplexed counters and a method thereof
View Patent ↗Embodiments of the present invention relate to an architecture that uses hierarchical statistically multiplexed counters to extend counter life by orders of magnitude. Each level includes statistically multiplexed counters. The statistically multiplexed counters includes P base counters and S subcounters, wherein the S subcounters are dynamically concatenated with the P base counters. When a row overflow in a level occurs, counters in a next level above are used to extend counter life. The hierarchical statistically multiplexed counters can be used with an overflow FIFO to further extend counter life.
1. A method of updating a counter in a counter architecture that includes a hierarchy of levels of statistically multiplexed counters, the method comprising:
determining a number of the hierarchy of levels having a corresponding row of the counter in the hierarchy of levels that overflows;
determining a highest level of the number of the hierarchy of levels that is the highest in the hierarchy; and
processing the highest level and each level of the hierarchy of levels below the highest level of the number using a first routine and processing a remainder of the hierarchy of the levels not a part of the number using a second routine.
2. The method of claim 1 , further comprising, when the highest level of the number is the highest level in the hierarchy of levels, updating an overflow queue.
3. The method of claim 1 , wherein the first routine includes incrementing the counter in the corresponding level and shrinking the counter in the corresponding level.
4. The method of claim 1 , wherein the second routine includes incrementing the counter in the corresponding level.
5. The method of claim 4 , wherein the incrementing the counter includes expanding a size of the counter in the corresponding level.
6. The method of claim 2 , wherein updating the overflow queue includes pushing a counter identifier of the counter and an overflow width into the overflow queue.
7. The method of claim 2 , wherein the overflow queue is a FIFO buffer.
8. The method of claim 2 , further comprising:
processing data in the overflow queue;
identifying a wrap-around counter by the data in the overflow queue;
reading a value stored in the wrap-around counter in each level; and
clearing the wrap-around counter in each level.
9. A method of updating a counter in a counter architecture that includes a hierarchy of levels of counters, the method comprising:
determining a number of the hierarchy of levels having a corresponding row of the counter in the hierarchy of levels that overflows;
determining a highest level of the number of the hierarchy of levels;
processing the highest level using a first routine;
processing each level of the number of the hierarchy of levels below the highest level using the first routine; and
processing a remainder of the hierarchy of the levels not a part of the number using a second routine.
10. The method of claim 9 , further comprising, when the highest level of the number is the highest level in the hierarchy of levels, updating an overflow queue.
11. The method of claim 10 , wherein updating the overflow queue includes pushing a counter identifier of the counter and an overflow width into the overflow queue.
12. The method of claim 9 , wherein the first routine includes incrementing the counter in the corresponding level and shrinking the counter in the corresponding level.
13. The method of claim 10 , wherein the overflow queue is a FIFO buffer.
14. The method of claim 10 , further comprising:
processing data in the overflow queue;
identifying a wrap-around counter by the data in the overflow queue;
reading a value stored in the wrap-around counter in each level; and
clearing the wrap-around counter in each level.
15. The method of claim 9 , wherein the second routine includes incrementing the counter in the corresponding level.
16. The method of claim 15 , wherein the incrementing the counter includes expanding a size of the counter in the corresponding level.
17. The method of claim 9 , wherein the second routine includes incrementing the counter in the corresponding level.
18. The method of claim 17 , wherein the incrementing the counter includes expanding a size of the counter in the corresponding level.
19. A method of updating a counter in a counter architecture that includes a hierarchy of levels of counters, the method comprising:
determining a highest level of a number of the hierarchy of levels having a corresponding row of the counter in the hierarchy of levels that overflows;
processing each level of the number of the hierarchy of levels using a first routine; and
processing a remainder of the hierarchy of the levels not a part of the number using a second routine.
20. The method of claim 19 , further comprising, when the highest level of the number is the highest level in the hierarchy of levels, updating an overflow queue.
21. The method of claim 20 , wherein updating the overflow queue includes pushing a counter identifier of the counter and an overflow width into the overflow queue.
22. The method of claim 19 , wherein the first routine includes incrementing the counter in the corresponding level and shrinking the counter in the corresponding level.
23. The method of claim 20 , wherein the overflow queue is a FIFO buffer.
24. The method of claim 20 , further comprising:
processing data in the overflow queue;
identifying a wrap-around counter by the data in the overflow queue;
reading a value stored in the wrap-around counter in each level; and
clearing the wrap-around counter in each level.