Back to results
US 8,620,940 B1Granted
Pattern matching
AssigneeTilera Corporation
InventorsMathew Hostetter, Kenneth M. Steele, Vijay Aggarwal
Life of this patent
Estimating the term…
Abstract
A method for processing data for pattern matching includes: receiving a first sequence of data values; and generating a second sequence of data values based on the first sequence and one or more patterns and history of data values in the first sequence, wherein the second sequence has fewer data values than the first sequence and all subsequences in the first sequence that match at least one of the one or more patterns are represented in the second sequence.
Claims24
A method comprising:
- receiving a first sequence of data values;
- preprocessing the first sequence for pattern matching, by:
- generating by a compressor engine a second sequence of data values that is based on the first sequence of values;
- by
- replacing an original subsequence of data values in the first sequence with a shorter subsequence of data values that corresponds to the same transition vector in the first sequence, with the second sequence having fewer data values than the first sequence and subsequences in the first sequence that include data values that match in the first sequence of data values, a first pattern of the one or more patterns is represented in the second sequence with at least the data values that match the first pattern;
- and
- sending the second sequence to a pattern matcher finite state machine associated with the one or more patterns as the original subsequence.
4 more elements
A system, comprising:
- a plurality of processor cores interconnected by an interconnection network the system configured to:
- receive a first sequence of data values,
- preprocess the first sequence for pattern matching, by the cores configured to:
- generate in a first portion of the processor cores a second sequence of data values that is based on the first sequence of values;
- by:
- replace an original subsequence of data values in the first sequence with a shorter subsequence of data values that corresponds to the same transition vector, with the second sequence having fewer data values than the first sequence and subsequences in the first sequence that include data values that match in the first sequence of data values, a first pattern of the one or more patterns is represented in the second sequence with at least the data values that match the first pattern, and
- match in finite state machine executing on a second portion of the processor cores the second sequence of data values to the one or more patterns of data values associated with the one or more patterns as the original subsequence.
4 more elements
A system, comprising:
- a plurality of processor cores, comprising:
- a computation unit;
- and
- a switch including switching circuitry to forward data to and received from data paths of an interconnection network;
- the interconnection network configured to connect the plurality of processor cores;
- the system configured to:
- receive by a first portion of the processor cores a first sequence of data values, the first portion of processor cores configured to break down the first sequence of data values into segments and distribute the segments to a second portion of the processor cores;
- generate in the second portion of the processor cores a second sequence of data values that is based on the distributed segments from the first sequence of values and one or more patterns;
- replace an original subsequence of data values in the first sequence with a shorter subsequence of data values that corresponds to the same transition vector in the first sequence, with the second sequence having fewer data values than the distributed segments from the first sequence;
- and
- match in a third portion of the processor cores the second sequence of data values to one or more patterns of data values.
8 more elements
Dependencies are inferred from the claim text.