METHOD AND APPARATUS FOR PROCESSING FINITE AUTOMATA
Granted: March 5, 2015
Application Number:
20150067863
A method and corresponding apparatus for run time processing use a Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) to find the existence of a pattern in a payload. A subpattern may be selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic. The DFA may be generated from selected subpatterns from all patterns in the set, and at least one NFA may be generated for at least one pattern in the set,…
System and Method to Traverse a Non-Deterministic Finite Automata (NFA) Graph Generated for Regular Expression Patterns with Advanced Features
Granted: March 5, 2015
Application Number:
20150067836
In one embodiment, a method of walking an non-deterministic finite automata (NFA) graph representing a pattern includes extracting a node type and an element from a node of the NFA graph. The method further includes matching a segment of a payload for the element by matching the payload for the element at least zero times, the number of times based on the node type.
METHOD AND APPARATUS FOR COMPILATION OF FINITE AUTOMATA
Granted: March 5, 2015
Application Number:
20150067776
A method and corresponding apparatus are provided implementing run time processing using Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) to find the existence of a pattern in a payload. A subpattern may be selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic and a unified deterministic finite automata (DFA) may be generated using the subpatterns selected from all patterns in the set, and at least…
Distributed Delay Locked Loop
Granted: March 5, 2015
Application Number:
20150067383
In an embodiment, a clock distribution circuit includes a global delay locked loop (DLL) configured to receive a global clock input signal (RCLK), a lead/lag input signal and to output a clock signal. The circuit includes a plurality of clock distribution blocks, each clock distribution block configured to receive the output of the global DLL, a lead/lag signal and to output a leaf node clock signal, each clock distribution block further comprises a local DLL. The global DLL is further…
Memory Management for Finite Automata Processing
Granted: March 5, 2015
Application Number:
20150067200
Matching at least one regular expression pattern in an input stream may be optimized by initializing a search context in a run stack based on (i) partial match results determined from walking segments of a payload of a flow through a first finite automation and (ii) a historical search context associated with the flow. The search context may be modified via push or pop operations to direct at least one processor to walk segments of the payload through the at least one second finite…
Generating a Non-Deterministic Finite Automata (NFA) Graph for Regular Expression Patterns with Advanced Features
Granted: March 5, 2015
Application Number:
20150066927
In an embodiment, a method of compiling a pattern into a non-deterministic finite automata (NFA) graph includes examining the pattern for a plurality of elements and a plurality of node types. Each node type can correspond with an element. Each element of the pattern can be matched at least zero times. The method further includes generating a plurality of nodes of the NFA graph. Each of the plurality of nodes can be configured to match for one of the plurality of elements. The node can…
Clock Gated Delay Line Based On Setting Value
Granted: March 5, 2015
Application Number:
20150061743
In an embodiment, a delay circuit includes a delay line with a clock input signal and a delayed clock output signal that is based on a setting value. Each delay element of the delay line receives one of several delay element select signals and outputs a delayed signal based on the delay element select signal. The setting value may be a binary encoded value representing the desired delay. The delay element select signals may correspond to a thermometer encoded value of the binary encoded…
MULTIPLEXER FLOP
Granted: March 5, 2015
Application Number:
20150061741
In an embodiment, a flip flop circuit includes a master latch and a slave latch. The master latch comprises a storage element, a first data leg, and a second data leg. The first and second data legs may be coupled to the storage element. Clock selection logic may be coupled to the first and second data legs. The clock selection logic may have a select input for selecting between the first and second data legs. The slave latch may be coupled to the master latch.
SCANNABLE FLOP WITH A SINGLE STORAGE ELEMENT
Granted: March 5, 2015
Application Number:
20150061740
In an embodiment, a flip flop circuit includes a master latch and a slave latch. The master latch comprises a storage element and at least two legs, including a data leg and at least one scan leg. The first node of the storage element may be driven by the data leg. The opposite node of the storage element may be driven by at least one of the scan legs. The slave latch may be coupled to the master latch.
Network Interface Card with Virtual Switch and Traffic Flow Policy Enforcement
Granted: January 29, 2015
Application Number:
20150033222
A system includes a host computer executing virtual machines under the control of a hypervisor. A network interface card is coupled to the host machine. The network interface card implements a virtual switch with virtual ports. Each (one or more) virtual port is associated with a virtual machine. The network interface card may operate as a co-processor for the host computer by managing selected traffic flow policies, such as QoS and bandwidth provisioning on a per virtual machine basis.
Low Latency Rate Control System and Method
Granted: December 25, 2014
Application Number:
20140376640
An encoder within a video transmission system controls the bit allocation at a sub-frame level. A frame is divided into smaller blocks, known as rate control blocks. Rate control blocks are used as the basic unit for bit allocation. This bit allocation achieves the target bit rate desired by the system as well as meet latency constraints. The encoder uses the slice partitioning capabilities to generate the rate control blocks using one or more slices of the image frame. This feature…
Apparatus and Method for Providing Sort Offload
Granted: September 18, 2014
Application Number:
20140269281
An apparatus includes a core processor and a hardware based sort coprocessor. In one embodiment, the core processor is able to generate an input array. The hardware based sort coprocessor is configured to sort the input array in accordance with a metric and flag of each element to be sorted in the input array and generate a sorted array.
Method and Apparatus for Data Integrity Checking in a Processor
Granted: September 18, 2014
Application Number:
20140281834
In an embodiment, a method of handling data packets within a processor includes intercepting, by a hardware packet integrity checking module, one or more data fields associated with a current segment of a data packet being forwarded from a first hardware entity operating in a cut-through mode to one or more processing clusters, where at least one data field of the one or more data fields is indicative of an operation associated with the data packet. At the hardware error detection…
Merging Independent Writes, Separating Dependent And Independent Writes, And Error Roll Back
Granted: September 18, 2014
Application Number:
20140281809
In an embodiment, a method of updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, can include maintaining a copy of the memory with a plurality of memory lines. The method can further include writing a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy. The method can additionally include determining whether each of the plurality of changes is an…
NSP Manager
Granted: September 18, 2014
Application Number:
20140280357
In an embodiment, a method of updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, can include maintaining a copy of the memory with a plurality of memory lines. The method can further include writing a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy. The method can additionally include determining whether each of the plurality of changes is an…
BATCH INCREMENTAL UPDATE
Granted: September 18, 2014
Application Number:
20140279850
A system, apparatus, and method are provided for adding, deleting, and modifying rules in one update from the perspective of an active search process for packet classification. While a search processor searches for one or more rules that match keys generated from received packets, there is a need to add, delete, or modify rules. By organizing a plurality incremental updates for adding, deleting, or modifying rules into a batch update, several operations for incorporating the incremental…
METHOD AND AN ACCUMULATOR SCOREBOARD FOR OUT-OF-ORDER RULE RESPONSE HANDLING
Granted: September 18, 2014
Application Number:
20140279806
According to at least one example embodiment, a method and a corresponding accumulator scoreboard for managing bundles of rule matching threads processed by one or more rule matching engines comprise: recording, for each rule matching thread in a given bundle of rule matching threads, a rule matching result in association with a priority corresponding to the respective rule matching thread; determining a final rule matching result, for the given bundle of rule matching threads, based at…
Scheduling Method and Apparatus for Scheduling Rule Matching in a Processor
Granted: September 18, 2014
Application Number:
20140279805
In a network search processor, configured to handle search requests in a router, a scheduler for scheduling rule matching threads initiated by a plurality of initiating engines is designed to make efficient use of the resources in the network search processor while providing high speed performance. According to at least one example embodiment, the scheduler and a corresponding scheduling method comprise: determining a set of bundles of rule matching threads, each bundle being initiated…
Apparatus and Method for Media Access Control Scheduling with a Priority Calculation Hardware Coprocessor
Granted: September 18, 2014
Application Number:
20140269530
An apparatus includes a Media Access Control (MAC) scheduler to generate a priority value calculation request with a specified formula and a list of metrics. A hardware based priority value calculation coprocessor services the priority value calculation request in accordance with the specified formula and the list of metrics.
Apparatus and Method for Media Access Control Scheduling with a Sort Hardware Coprocessor
Granted: September 18, 2014
Application Number:
20140269529
An apparatus includes a Media Access Control (MAC) scheduler to generate a sort request. A hardware based sort coprocessor services the sort request in accordance with specified packet processing priority parameters to generate a sorted array.
