Associatively indexed circular buffer
Some embodiments of the present disclosure provide an associatively indexed circular buffer (ACB). The ACB may be viewed as a dynamically allocatable memory structure that offers in-order data access (say, first-in-first-out, or “FIFO”) or random order data access at a fixed, relatively low latency. The ACB includes a data store of non-contiguous storage. To manage the pushing of data to, and popping data from, the data store, the ACB includes a contiguous pointer generator, a content addressable memory (CAM) and a free pool.
1. A method of carrying out a push operation at an associatively indexed circular buffer (ACB), the ACB including a data store, a contiguous pointer generator, a content addressable memory (CAM) and a free pool, the method comprising:
receiving a push operation instruction with data that is to be pushed;
obtaining, from the free pool, a data-store address to a physical memory location in the data-store;
obtaining, from the contiguous pointer generator, a contiguous pointer;
writing the contiguous pointer to the CAM at a CAM address corresponding to the data-store address; and
writing, in the data store at the data-store address, the data that is to be pushed.
2. The method of claim 1 , further comprising separating the data-store address from among a plurality of data-store addresses obtained from the free pool.
3. An associatively indexed circular buffer (ACB), the ACB comprising:
a data store;
a contiguous pointer generator;
a content addressable memory (CAM);
a free pool; and
a control element configured to:
receive a push operation instruction with data that is to be pushed;
obtain, from the free pool, a data-store address to a physical memory location in the data-store;
obtain, from the contiguous pointer generator, a contiguous pointer;
write the contiguous pointer to the CAM at a CAM address corresponding to the data-store address; and
write, in the data store at the data-store address, the data that is to be pushed.
4. The ACB of claim 3 , wherein the free pool is implemented as a random-access-memory-based first-in-first-out memory structure.
5. The ACB of claim 3 , wherein the free pool is implemented as a zero-read-latency-based first-in-first-out memory structure.
6. The ACB of claim 3 , wherein the CAM is implemented as a vendor macro.
7. The ACB of claim 3 , wherein the CAM is implemented as a cascaded multi-stage flop-based memory.
8. The ACB of claim 3 , wherein the control element is further configured to separate the data-store address from among a plurality of data-store addresses obtained from the free pool.
9. A method of carrying out a pop operation at an associatively indexed circular buffer (ACB), the ACB including a data store, a contiguous pointer generator, a cam and a free pool, the method comprising:
receiving a pop operation instruction;
obtaining, from the contiguous pointer generator, a contiguous pointer;
providing, to the content addressable memory (CAM), the contiguous pointer;
receiving, from the CAM, a data-store address;
reading, from the data store at the data-store address, data; and
providing the data in answer to the pop operation instruction.
10. The method of claim 9 , further comprising, subsequent to the providing, returning, to the free pool, the data-store address.
11. The method of claim 9 , further comprising, subsequent to the reading, purging, from the data store, the data.
12. An associatively indexed circular buffer (ACB), the ACB comprising:
a data store;
a contiguous pointer generator;
a content addressable memory (CAM);
a free pool; and
a control element configured to:
receive a pop operation instruction;
obtain, from the contiguous pointer generator, a contiguous pointer;
provide, to the content addressable memory (CAM), the contiguous pointer;
receive, from the CAM, a data-store address;
read, from the data store at the data-store address, data; and
provide the data in answer to the pop operation instruction.
13. The ACB of claim 12 , wherein the control element is further configured to return, to the free pool, the data-store address.
14. The ACB of claim 12 , wherein the control element is further configured to purge, from the data store, the data.
15. The ACB of claim 12 , wherein the free pool is implemented as a random-access-memory-based first-in-first-out memory structure.
16. The ACB of claim 12 , wherein the free pool is implemented as a zero-read-latency-based first-in-first-out memory structure.
17. The ACB of claim 12 , wherein the CAM is implemented as a vendor macro.
18. The ACB of claim 12 , wherein the CAM is implemented as a cascaded multi-stage flop-based memory.