Implementing FIFOs in shared memory using linked lists and interleaved linked lists
View Patent ↗FIFOs may be implemented in shared memory using linked lists and interleaved linked lists such that any individual FIFO can dynamically use any free memory location. The system may be implemented in hardware efficiently and does not pre-allocate memory to any FIFO, so that the whole shared memory may be used by any one of the FIFOs. The maximum physical size of a FIFO is then limited only by the size of the physical memory and not by the number of FIFOs sharing the same physical memory or by any mechanism for pre-allocating physical memory to the FIFOs. The linked lists contain data words, each data word containing a data field and a reference to a subsequent free memory location. A subsequent data word may be enqueued to the FIFO at the last referenced free memory location. A dequeue operation returns free memory locations to the free memory pool. Multiple linked lists may be interleaved to accelerate reading of data words from the FIFO.
1. A First In First Out (FIFO) data structure in a physical memory, comprising:
at least first and second separate linked lists collectively forming the FIFO data structure, each of the linked lists having a plurality of memory locations, each memory location including a data field and a pointer field, wherein a pointer field of an earlier memory location in a given linked list points to a memory address of a subsequent memory location in that same linked list, and where the first and second separate linked lists are interleaved such that consecutive data words to be stored in the FIFO will be stored on different ones of the first and second separate linked lists, and such that data is read from the FIFO data structure by reading memory locations of the first and second separate linked lists in a selected order.
2. The FIFO data structure of claim 1 , further comprising a head_fifo register representing a dequeue memory location address, and a tail_fifo register representing an enqueue memory location address.
3. The FIFO data structure of claim 2 , wherein the enqueue memory location address is empty prior to an enqueue operation.
4. The FIFO data structure of claim 1 , wherein an enqueue operation on the FIFO data structure causes a data word to be written to one of the memory locations in the first linked list and then to a memory location in the second linked list.
5. The FIFO data structure of claim 1 , further comprising a free memory data structure configured to supply free memory locations to the first linked list to perform an enqueue operation at each clock cycle of the physical memory.
6. A method of sharing a pool of available memory between a plurality of first in first out (FIFO) memory structures, the method comprising the steps of:
establishing a plurality of FIFO memory structures in the pool of available memory, each FIFO memory structure including at least first and second separate linked lists, the at least first and second separate linked lists being interleaved and collectively forming the FIFO memory structure, each of the separate linked lists having a plurality of memory locations, each memory location including a data field and a pointer field, wherein a pointer field of an earlier memory location in a given linked list points to a memory address of a subsequent memory location in that same linked list, and wherein the first and second separate linked lists of a given FIFO are interleaved such that consecutive data words to be stored in the FIFO will be stored on different ones of the first and second separate linked lists; and
enqueuing data words into the interleaved linked lists to write the data words to the FIFO.
7. The method of claim 6 , further comprising the step of retrieving from a pool of available memory, free memory addresses for use with the step of enqueuing data words into the linked list memory structures.
8. The method of claim 7 , wherein the pool of available memory comprises the free memory addresses, and wherein any of the plurality of linked lists may use any of the free memory addresses.
9. The method of claim 6 , wherein successive enqueue operations iterate across the multiple interleaved linked lists.
10. The method of claim 9 , wherein the enqueue operations are controlled by a successive enqueue register for that plurality of linked lists.
11. The method of claim 9 , wherein successive dequeue operations iterate across the multiple interleaved linked lists in the same order as the successive enqueue operations.
12. The method of claim 11 , wherein the dequeue operations are controlled by a successive dequeue register for that plurality of linked lists.