US 6,445,680 B1 · Linked list based least recently used arbiter

Abstract

An arbiter utilizing a link list to arbitrate access between multiple data sources and a single destination. The arbiter is of the least recently used type whereby the data source that has not sent data for the longest time is given the highest priority. The arbiter provides an arbitration function in a simple manner and at high speeds. The arbiter utilizes a Non Empty Source Queue (NESQ) list that comprises only sources that are non empty, i.e., that have data ready to send. If a source queue chosen for data transmission still has data to send, it is placed at the end of the NESQ list. When a source queue becomes empty after the transmission of data, the source index is removed from the linked list. Conversely, when a source queue that was previously empty receives a new packet it is added to the end of the linked list.

Claims10

Dependent claims

An arbiter for managing data flow between a plurality of input sources and an output destination, comprising:

a non empty source queue (NESQ) list having a plurality of entries, each entry corresponding to one input source and comprising a data pointer;
a linked list containing an ordered list of pointers to input sources, said ordered list having a head and a tail pointed to by a head pointer and a tail pointer, respectively, said ordered list representing the order said plurality of input sources are permitted to send data to said output destination;
wherein each input source is associated with a backpressure indication that indicates whether an input source is permitted to transmit data to said output destination;
wherein input sources are selected from the head of said linked list, once a selected source transmits data, it is placed at the tail of said linked list if it has additional data to transmit and is removed from said linked list otherwise;
and
wherein an input source not previously on said linked list is added thereto when said input source has data available for transmission.

3 more elements

Dependencies are inferred from the claim text.

Linked list based least recently used arbiter

Life of this patent

Linked list based least recently used arbiter

Life of this patent

Abstract

Claims10