Xilinx, Inc.

Sachin Kumawat

David K Liddell

Paul R Schumacher

Hare Krishna Verma

Jiayou Wang

Vincent Mirian

A system includes a multi-port random-access memory (RAM) configured to store an instruction table. The instruction table specifies a regular expression for application to a data stream. The system includes a regular expression engine configured to process the data stream based on the instruction table. The regular expression engine includes a decoder circuit configured to determine validity of active states output from the RAM, a plurality of active states memories operating concurrently, wherein each active states memory is configured to initiate a read from a different port of the RAM using an address formed of an active state output from the active states memory and a portion of the data stream, and switching circuitry configured to route the active states to the plurality of active states memories according, at least in part, to a load balancing technique and validity of the active states.

High-throughput regular expression processing using an integrated circuit

A system includes a multi-port RAM configured to store an instruction table. The instruction table specifies a regular expression for application to a data stream. The system includes a regular expression engine (engine) that processes the data stream using the instruction table. The engine includes a decoder circuit that determines validity of active states output from the multi-port RAM and a plurality of priority FIFO memories (PFIFOs) operating concurrently. Each PFIFO can initiate a read from a different port of the multi-port RAM. Each PFIFO can track a plurality of active paths for the regular expression and a priority of each active path by, at least in part, storing entries corresponding to active states in each respective PFIFO in decreasing priority order. The engine includes switching circuitry that selectively routes the active states from the decoder circuit to the plurality of PFIFOs according to the priority order.

High-throughput regular expression processing with path priorities using an integrated circuit

A system includes a first multi-port RAM storing an instruction table. The instruction table specifies a regular expression for application to a data stream and a second multi-port RAM configured to store a capture table having capture entries decodable for tracking position information for a sequence of characters matching a capture sub-expression of the regular expression. The system includes a regular expression engine processing the data stream to determine match states by tracking active states for the regular expression and priorities for the active states by storing the active states of the regular expression in a plurality of priority FIFO memories in decreasing priority order. The system includes a capture engine operating in coordination with the regular expression engine to determine character(s) of the data stream that match the capture sub-expression based on the active state being tracked and decoding the capture entries of the capture table.

High-throughput regular expression processing with capture using an integrated circuit

A processing circuit includes a random access memory (RAM) configured to look up a first next state based on a first address simultaneously with looking up a second next state based on a second address. The first address is formed of a first current state and an input data and the second address is formed of a second current state and the input data. The processing circuit includes a state control circuit that receives the first and second next states, the first current state, and the second current state, and a first-in-first-out (FIFO) memory that stores selected ones of the first and second next states, the first current state, and the second current state. The processing circuit includes a multiplexer configured to selectively pass two states from the FIFO memory or two states from the state control circuit as a third current state and a fourth current state.

Growing community of inventors

San Jose, CA, United States of America

Sachin Kumawat