Management of linked lists within a dynamic queue system

摘要

A method and apparatus are disclosed for management of linked lists within a dynamic queue system. In a dynamic queue system where a central memory is shared amongst a set of queues, the method organizes the linked list structures of the queues. The linked list pointers of the queues are organized over a set of single port memories. Memory for the queue entries is allocated in an alternating fashion, which allows the method to provide per-cycle access to queues while reducing the footprint of the memory elements used for maintaining the linked list structures. The method disclosed reduces the overall memory requirements for the design and implementation of queue systems with multiple queues sharing a common pool of memory.

主权项

1. A method of linked list management in a dynamic queue system, comprising:
logically dividing an uninitialized common memory pool into first and second sub-pools of equal size, each sub-pool configured to store a queue entry and perform a queue operation on the queue entry; tracking unallocated memory locations in the first and second sub-pools using first and second free lists, respectively, the first and second free lists stored on separate first and second single port memories; and alternating storing the queue entries in the first and second sub-pools, such that performing a queue operation on the queue entry in either the first or second sub-pool comprises accessing the first free list and the second free list in one clock cycle by performing, in the one clock cycle, both a first memory transaction at the first single port memory and a second memory transaction at the second single port memory, wherein each of the queue operation, the first memory transaction, and the second memory transaction comprises a read or a write operation.