Pattern matching
View Patent ↗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.
1. 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.
2. The method of claim 1 , wherein generating the second sequence of data values comprises generating data values according to an associated buffer state corresponding to at least some of the first sequence of data values.
3. The method of claim 2 , wherein the buffer state corresponds to data values stored in a buffer.
4. The method of claim 2 , wherein the buffer state corresponds to data values associated with a state of a finite-state machine.
5. The method of claim 2 , wherein generating the second sequence of data values comprises evaluating data values corresponding to the buffer state for possible reduction.
6. The method of claim 2 , wherein the buffer state corresponds to fewer than or equal to a maximum number of data values.
7. The method of claim 1 , wherein generating the second sequence of data values comprises processing the first sequence according to a finite-state machine.
8. The method of claim 7 , wherein the number of states in the finite-state machine are determined according to an amount of compression of the second sequence relative to the first sequence.
9. The method of claim 1 , wherein at least some of the patterns are specified by a regular expression.
10. The method of claim 1 , wherein the method is executed on a system including a plurality of processor cores interconnected by an interconnection network, and the method further comprises performing the generating by the compressor engine that is executed on a first portion of the processor cores and performing pattern matching on the sent second sequence in a second portion of the processor cores to match the second sequence of data values to one or more patterns of data values.
11. 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.
12. The system of claim 11 , further comprising a memory for storing the one or more patterns of data values and information for configuring the system.
13. The system of claim 11 , wherein the interconnection network comprises a two-dimensional network.
14. The system of claim 11 , wherein the interconnection network comprises a bus network, a ring network, a mesh network, or a crossbar switch network.
15. The system of claim 11 , wherein each of the plurality of processor cores corresponds to a tile on an integrated circuit, each tile comprising:
a computation unit; and
a switch including switching circuitry to forward data received over data paths of the interconnection network from other tiles to the computation unit and to switches of other tiles, and to forward data received from the computation unit to switches of other tiles.
16. The system of claim 15 , wherein the computation unit comprises a pipelined processor and the switch is coupled to a plurality of pipeline stages of the pipelined processor.
17. The system of claim 16 , wherein at least one port of the switch is mapped to a register name space of the pipelined processor.
18. The system of claim 11 , wherein a third portion of the processor cores is configured to break down the first sequence of data values into segments and distribute the segments to the first portion of the processor cores.
19. The system of claim 18 , wherein the a third portion of the processor cores is configured to distribute the segments based on respective sets of patterns to be matched.
20. The system of claim 18 , wherein the first portion of processor cores are configured to provide data values to the second portion of the plurality of processor cores configured to match the second sequence of data values to the one or more patterns of data values.
21. The system of claim 20 , wherein at least a fourth portion of the processor cores is configured to collect outputs of second portion of the plurality of processor cores that match the second sequence of data values to the one or more patterns of data values.
22. 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.
23. The system of claim 22 , further comprising a memory for storing the one or more patterns of data values and information for configuring the system.
24. The system of claim 22 , wherein at least a fourth portion of the processor cores is configured to collect outputs of the third portion of the processor cores that match the second sequence of data values to the one or more patterns of data values.