US Patent No. 9,785,367

SYSTEM AND METHOD FOR ENABLING HIGH READ RATES TO DATA ELEMENT LISTS


Patent No. 9,785,367
Issue Date October 10, 2017
Title System And Method For Enabling High Read Rates To Data Element Lists
Inventorship William Brad Matthews, San Jose, CA (US)
Bruce H. Kwan, Sunnyvale, CA (US)
Mohammad K. Issa, Los Altos, CA (US)
Neil Barrett, Palo Alto, CA (US)
Avinash Gyanendra Mani, San Jose, CA (US)
Assignee Innovium, Inc., San Jose, CA (US)

Claim of US Patent No. 9,785,367

1. A memory system for a network device comprising:
a main memory including memory locations that store data elements;
a link memory including a plurality of memory banks that includes a first memory bank and a second memory bank, each memory
bank of the plurality of memory banks having a latency for consecutively executed memory access operations, wherein each memory
bank is configured to store a plurality of nodes that each store (i) a respective data-element pointer to the main memory
for accessing a respective memory location, and (ii) a respective next-node pointer for accessing a next node in the same
memory bank, wherein each of the data-element pointers in the plurality of memory banks points to a respective data element
stored the main memory, and wherein one or more data packets are formed by linking the data elements stored in the main memory;

circuitry configured to:
store at least a first data element, a second data element, and a third data element in a first memory location, a second
memory location, and a third memory location of the main memory, respectively, wherein the first data element is to be read
before the second data element, and wherein the second data element is to be read before the third data element;

store, in a first node of a first memory bank of the plurality of memory banks, (i) a first data-element pointer to the first
memory location and (ii) a first next-node pointer for accessing a second node of the first memory bank;

after storing the first data-element pointer in the first node, determine that accessing the second node of the first memory
bank to store a second data-element pointer to the second memory location does not satisfy the latency for consecutively executed
memory access operations for the first memory bank;

in response to determining that accessing the second node of the first memory bank to store a second data-element pointer
to the second memory location of the main memory does not satisfy the latency for consecutively executed memory access operations
for the first memory bank, store, in a first node of a second memory bank of the plurality of memory banks, (i) the second
data-element pointer to the second memory location of the main memory and (ii) a second next-node pointer for accessing a
second node of the second memory bank;

after storing the second data-element pointer in the first node of the second memory bank, determine that accessing the second
node of the first memory bank to store a third data-element pointer to the third memory location of the main memory satisfies
the latency for consecutively executed memory access operations for the first memory bank; and

in response to determining that accessing the second node of the first memory bank to store a third data-element pointer to
the third memory location of the main memory satisfies the latency for consecutively executed memory access operations for
the first memory bank, store, in the second node of the first memory bank, (i) the third data-element pointer to the third
memory location and (ii) a third next-node pointer for accessing a third node of the first memory bank,

wherein at least the first next-node pointer and the third next-node pointer form a first skip list for the first memory bank,
and

wherein at least the second next-node pointer and forms a second skip list for the second memory bank; and
a context manager including a first head entry for the first memory bank and a second head entry for the second memory bank,
the context manager configured to maintain at least the first skip list and the second skip list wherein the first head entry
stores a first link-memory pointer pointing to the first node of the first memory bank, and wherein the second head entry
stores a second link-memory pointer pointing to the first node of the second memory bank.