US 8,078,657 B2Granted

Multi-source dual-port linked list purger

AssigneeInternational Business Machines Corporation

InventorsTodd A. Strader, Scot H. Rider

Life of this patent

Estimating the term…

Loading patent…

Abstract

Disclosed is a circuit for simultaneously searching two ends of a vector. The circuit comprises at least one input for receiving a vector of head pointers. A first input of a memory latch receives the vector of head pointers. An input of a first priority decoder receives the vector of head pointers from the memory latch. The first priority decoder traverses the vector of head pointers from a first end of the vector for identifying one active bit in the vector. An input of a first reverse module also receives the vector of head pointers from the memory latch. An input of second priority decoder receives the vector of head pointers (in reverse order) from the first reverse module. The second priority decoder traverses the vector received from the first reverse module from a first end of the reversed vector for identifying one active bit in the vector.

Claims20

Dependent claims

A circuit for simultaneously searching two ends of a vector, the circuit comprising:

at least one input for receiving a vector of head pointers;
a memory latch comprising two inputs and an output, wherein a first input receives the vector of head pointers;
a first priority decoder including an input and an output, wherein the input of the first priority decoder receives the vector of head pointers from the memory latch, wherein the first priority decoder traverses the vector of head pointers from a first end of the vector for identifying one active bit in the vector;
a first reverse module including an input and an output, wherein the input also receives the vector of head pointers from the memory latch;
a second priority decoder including an input and an output, wherein the input of second priority decoder receives a vector of head pointers from the first reverse module, wherein the vector of head pointers received from the first reverse module are the vector of head pointers received at the at least one input in reverse order, and wherein the second priority decoder traverses the vector of head pointers received from the first reverse module from a first end of the reversed vector of head pointers for identifying one active bit in the vector;
and
a gating mechanism comprising a first AND gate, a second AND gate, and an OR gate, wherein a first input of the first AND gate is coupled to the output of the first priority decoder, and wherein a second input of the first AND gate is coupled to a first busy port of a linked list purging circuit,
wherein a first input of the second AND gate is coupled to the output of a second reverse module, and wherein a second input of the second AND gate is coupled to a second busy port of the linked list purging circuit, and
wherein a first input of the OR gate is coupled to an output of the first AND gate, and wherein a second input of the OR gate is coupled to an output of the second AND gate, wherein an output of the OR gate is coupled to a reset port of the memory latch.

6 more elements

A networking device, the networking device comprising:

a memory;
a processor communicatively coupled to the memory;
and
a circuit communicatively coupled to the memory and the processor for simultaneously searching two ends of a vector, the circuit comprising:
at least one input for receiving a vector of head pointers;
a memory latch comprising two inputs and an output, wherein a first input receives the vector of head pointers;
a first priority decoder including an input and an output, wherein the input of the first priority decoder receives the vector of head pointers from the memory latch, wherein the first priority decoder traverses the vector of head pointers from a first end of the vector for identifying one active bit in the vector;
a first reverse module including an input and an output, wherein the input also receives the vector of head pointers from the memory latch;
a second priority decoder including an input and an output, wherein the input of second priority decoder receives a vector of head pointers from the first reverse module, wherein the vector of head pointers received from the first reverse module are the vector of head pointers received at the at least one input in reverse order, and wherein the second priority decoder traverses the vector of head pointers received from the first reverse module from a first end of the reversed vector of head pointers for identifying one active bit in the vector;
and
a gating mechanism comprising a first AND gate, a second AND gate, and an OR gate, wherein a first input of the first AND gate is coupled to the output of the first priority decoder, and wherein a second input of the first AND gate is coupled to a first busy port of a linked list purging circuit,
wherein a first input of the second AND gate is coupled to the output of a second reverse module, and wherein a second input of the second AND gate is coupled to a second busy port of the linked list purging circuit, and
wherein a first input of the OR gate is coupled to an output of the first AND gate, and wherein a second input of the OR gate is coupled to an output of the second AND gate, wherein an output of the OR gate is coupled to a reset port of the memory latch.

10 more elements

Dependencies are inferred from the claim text.