BOOSTING LINKED LIST THROUGHPUT

摘要

Multiple listlets function as a single master linked list to manage data packets across one or more banks of memory in a first-in first-out (FIFO) order, while allowing multiple push and/or pop functions to be performed per cycle. Each listlet can be a linked list that tracks pointers and is stored in a different memory bank. The nodes can include a pointer to a data packet, a pointer to the next node in the listlet and a next listlet identifier that identifies the listlet that contains the next node in the master linked list. The head and tail of each listlet, as well as an identifier each to track the head and tail of the master linked list, can be maintained in cache. The individual listlets are updated accordingly to maintain order of the master linked list as pointers are pushed and popped from the master linked list.

主权项

1. A method comprising:
receiving, by a computer processor, a first dequeue request to pop a data packet from a master linked list; determining, by the computer processor, from a master linked list head identifier, that a first listlet from a plurality of listlets that make up the master linked list, includes a head of the master linked list; dequeueing, by the computer processor, a head node from the first listlet, wherein the head node from the first listlet includes:
a first data pointer to a data packet stored in a first memory bank,a first next node pointer to a next node of the first listlet, anda first next listlet identifier that identifies a second listlet from the plurality of listlets that includes a new head of the master linked list; and updating, by the computer processor, the master linked list head identifier to be equal to the first next listlet identifier such that, after being updated, the master linked list head identifier identifies the second listlet instead of the first listlet.