Netronome Systems Incorporated

Intel Corporation

Steven W Zagorianakos

Gavin J Stark

Ronald N Fortino

Ron Lamar Swartzentruber

Salma Mirza

Richard P Bouley

Donald D McManus

George P Merrill

Frank J Zappulla

Rajesh Vaidheeswarran

A network flow processor integrated circuit includes a plurality of processors, a plurality of multi-threaded transactional memories (MTMs), and a configurable mesh posted transaction data bus. The configurable mesh posted transaction data bus includes a configurable command mesh and a configurable data mesh. Each of these configurable meshes includes crossbar switches and interconnecting links. A command bus transaction value issued by a processor can pass across the command mesh to an MTM. The command bus transaction bus value includes a reference value. The MTM uses the reference value to pull data across the configurable data mesh into the MTM. The MTM then uses the data to carry out the commanded transactional memory operation. Multiple such commands can pass across the posted transaction bus across different parts of the integrated circuit at the same time, and a single MTM can be carrying out multiple such operations at the same time.

Configuration mesh data bus and transactional memories in a multi-processor integrated circuit

Multiple processors share access, via a bus, to a pipelined NFA engine. The NFA engine can implement an NFA of the type that is not a DFA (namely, it can be in multiple states at the same time). One of the processors communicates a configuration command, a go command, and an event generate command across the bus to the NFA engine. The event generate command includes a reference value. The configuration command causes the NFA engine to be configured. The go command causes the configured NFA engine to perform a particular NFA operation. Upon completion of the NFA operation, the event generate command causes the reference value to be returned back across the bus to the processor.

NFA completion notification

A dispatcher circuit receives sets of instructions from an instructing entity. Instructions of the set of a first type are put into a first queue circuit, instructions of the set of a second type are put into a second queue circuit, and so forth. The first queue circuit dispatches instructions of the first type to one or more processing engines and records when the instructions of the set are completed. When all the instructions of the set of the first type have been completed, then the first queue circuit sends the second queue circuit a go signal, which causes the second queue circuit to dispatch instructions of the second type and to record when they have been completed. This process proceeds from queue circuit to queue circuit. When all the instructions of the set have been completed, then the dispatcher circuit returns an 'instructions done' to the original instructing entity.

Chained-instruction dispatcher

An island-based integrated circuit includes a configurable mesh data bus. The data bus includes four meshes. Each mesh includes, for each island, a crossbar switch and radiating half links. The half links of adjacent islands align to form links between crossbar switches. A link is implemented as two distributed credit FIFOs. In one direction, a link portion involves a FIFO associated with an output port of a first island, a first chain of registers, and a second FIFO associated with an input port of a second island. When a transaction value passes through the FIFO and through the crossbar switch of the second island, an arbiter in the crossbar switch returns a taken signal. The taken signal passes back through a second chain of registers to a credit count circuit in the first island. The credit count circuit maintains a credit count value for the distributed credit FIFO.

Distributed credit FIFO link of a configurable mesh data bus

A registered synchronous FIFO has a tail register, internal registers, and a head register. The FIFO cannot be pushed if it is full and cannot be popped if it is empty, but otherwise can be pushed and/or popped. Within the FIFO, the internal signal fanout of incoming data circuitry and push control circuitry and is minimized and remains essentially constant regardless of the number of registers of the FIFO. The output delay of the output data also is essentially constant regardless of the number of registers of the FIFO. An incoming data value can only be written into the head or tail. If a data value is in the tail and one of the internal registers is empty, and if no push or pop is to be performed in a clock cycle, then nevertheless the data value in the tail is moved into the empty internal register in the cycle.

Registered FIFO

A method for supporting in-flight packet processing is provided. Packet processing devices (microengines) can send a request for packet processing to a packet engine before a packet comes in. The request offers a twofold benefit. First, the microengines add themselves to a work queue to request for processing. Once the packet becomes available, the header portion is automatically provided to the corresponding microengine for packet processing. Only one bus transaction is involved in order for the microengines to start packet processing. Second, the microengines can process packets before the entire packet is written into the memory. This is especially useful for large sized packets because the packets do not have to be written into the memory completely when processed by the microengines.

In-flight packet processing

An NFA hardware engine includes a pipeline and a controller. The pipeline includes a plurality of stages, where one of the stages includes a transition table. Both a first automaton and a second automaton are encoded in the same transition table. The controller receives NFA engine commands onto the NFA engine and controls the pipeline in response to the NFA engine commands.

Command-driven NFA hardware engine that encodes multiple automatons

In response to receiving a novel 'Return Available PPI Credits' command from a credit-aware device, a packet engine sends a 'Credit To Be Returned' (CTBR) value it maintains for that device back to the credit-aware device, and zeroes out its stored CTBR value. The credit-aware device adds the credits returned to a &#x201c;Credits Available&#x201d; value it maintains. The credit-aware device uses the &#x201c;Credits Available&#x201d; value to determine whether it can issue a PPI allocation request. The &#x201c;Return Available PPI Credits&#x201d; command does not result in any PPI allocation or de-allocation. In another novel aspect, the credit-aware device is permitted to issue one PPI allocation request to the packet engine when its recorded &#x201c;Credits Available&#x201d; value is zero or negative. If the PPI allocation request cannot be granted, then it is buffered in the packet engine, and is resubmitted within the packet engine, until the packet engine makes the PPI allocation.

Return available PPI credits command

In response to receiving a 'Return Available PPI Credits' command from a credit-aware (CA) device, a packet engine sends a 'Credit To Be Returned' (CTBR) value it maintains for that device back to the CA device, and zeroes out its stored CTBR value. The CA device adds the credits returned to a &#x201c;Credits Available&#x201d; value it maintains. The CA device uses the &#x201c;Credits Available&#x201d; value to determine whether it can issue a PPI allocation request. The &#x201c;Return Available PPI Credits&#x201d; command does not result in any PPI allocation or de-allocation. In another aspect, the CA device issues one PPI allocation request to the packet engine when its recorded &#x201c;Credits Available&#x201d; value is zero or negative. If the PPI allocation request cannot be granted, then it is buffered in the packet engine, and is resubmitted within the packet engine, until the packet engine makes the PPI allocation.

Using a credits available value in determining whether to issue a PPI allocation request to a packet engine

Circuitry to provide in-order packet delivery. A packet descriptor including a sequence number is received. It is determined in which of three ranges the sequence number resides. Depending, at least in part, on the range in which the sequence number resides it is determined if the packet descriptor is to be communicated to a scheduler which causes an associated packet to be transmitted. If the sequence number resides in a first 'flush' range, all associated packet descriptors are output. If the sequence number resides in a second 'send' range, only the received packet descriptor is output. If the sequence number resides in a third &#x201c;store and reorder&#x201d; range and the sequence number is the next in-order sequence number the packet descriptor is output; if the sequence number is not the next in-order sequence number the packet descriptor is stored in a buffer and a corresponding valid bit is set.

Guaranteed in-order packet delivery

An automaton hardware engine employs a transition table organized into 2rows, where each row comprises a plurality of n-bit storage locations, and where each storage location can store at most one n-bit entry value. Each row corresponds to an automaton state. In one example, at least two NFAs are encoded into the table. The first NFA is indexed into the rows of the transition table in a first way, and the second NFA is indexed in to the rows of the transition table in a second way. Due to this indexing, all rows are usable to store entry values that point to other rows.

Automaton hardware engine employing memory-efficient transition table indexing

A remote processor interacts with a transactional memory that has a memory, local BWC (Byte-Wise Compare) resources, and local NFA (Non-deterministic Finite Automaton) engine resources. The processor causes a byte stream to be transferred into the transactional memory and into the memory. The processor then uses the BWC circuit to find a character signature in the byte stream. The processor obtains information about the character signature from the BWC circuit, and based on the information uses the NFA engine to process the byte stream starting at a byte position determined based at least in part on the results of the BWC circuit. From the time the byte stream is initially written into the transactional memory until the time the NFA engine completes, the byte stream is not read out of the transactional memory.

Transactional memory having local CAM and NFA resources

An NFA (Non-deterministic Finite Automaton) circuit includes a hardware byte characterizer, a first matching circuit (performs a TCAM match function), a second matching circuit (performs a wide match function), a multiplexer that outputs a selected output from either the first or second matching circuits, and a storage device. N data values stored in first storage locations of the storage device are supplied to the first matching circuit as an N-bit mask value and are simultaneously supplied to the second matching circuit as N bits of an N+O-bit mask value. O data values stored in second storage locations of the storage device are supplied to the first matching circuit as the O-bit match value and are simultaneously supplied to the second matching circuit as O bits of the N+O-bit mask value. P data values stored in third storage locations are supplied onto the select inputs of the multiplexer.

NFA byte detector

Within a networking device, packet portions from multiple PDRSDs (Packet Data Receiving and Splitting Devices) are loaded into a single memory, so that the packet portions can later be processed by a processing device. Rather than the PDRSDs managing and handling the storing of packet portions into the memory, a packet engine is provided. A device interacting with the packet engine can use a PPI (Packet Portion Identifier) Addressing Mode (PAM) in communicating with the packet engine and in instructing the packet engine to store packet portions. Alternatively, the device can use a Linear Addressing Mode (LAM) to communicate with the packet engine. A PAM/LAM selection code field in a bus transaction value sent to the packet engine indicates whether PAM or LAM will be used.

Growing community of inventors

Brookline, NH, United States of America

Steven W Zagorianakos