Compiling regular expressions for programmable content addressable memory devices
View Patent ↗A content search system includes CAM device, a compiler, and an image loader. The CAM device, which includes a plurality of rows of CAM cells and a number of counter circuits selectively interconnected by a programmable interconnect structure (PRS), performs regular expression search operations. The compiler selectively converts the regular expression into a number of various bit groups, and the image loader loads corresponding bit groups into the CAM cells, into a number of memory elements that control configuration of the PRS, and into the counter circuits.
1. A content search system comprising:
a content addressable memory (CAM) device having a plurality of rows of CAM cells and a number of counter circuits selectively interconnected by a programmable interconnect structure (PRS) and configured to implement search operations for a regular expression;
a compiler having an input to receive the regular expression and configured to selectively convert the regular expression into a number of first bit groups, a number of second bit groups, and a number of third bit groups; and
an image loader coupled to the compiler and to the CAM device, the image loader configured to load the first bit groups into the CAM cells, to load the second bit groups into a number of memory elements that control configuration of the PRS, and to load the third bit groups into the counter circuits.
2. The search system of claim 1 , wherein the first bit groups embody a number of characters of the regular expression, the second bit groups embody a number of metacharacters of the regular expression, and the third bit groups embody a number of quantifiers of the regular expression.
3. The search system of claim 2 , wherein a portion of one of the first bit groups configures the PRS to selectively route match results from a first CAM row as an input match signal to any number of other arbitrarily selected CAM rows at the same time.
4. The search system of claim 2 , wherein a portion of one of the third bit groups configures the counter circuit to identify only matching portions of an input string that have at least a specified minimum number of characters.
5. The search system of claim 2 , wherein a portion of one of the third bit groups configures the counter circuit to identify all matching portions of an input string.
6. The search system of claim 2 , wherein a portion of one of the third bit groups configures the counter circuit to count a match length of a matching substring.
7. The search system of claim 2 , wherein the metacharacter comprises a logical OR operator.
8. The search system of claim 2 , wherein the third bit groups comprise at least one greedy quantifier.
9. The search system of claim 2 , wherein one of the quantifiers comprises a Kleene star.
10. The search system of claim 2 , wherein one of the quantifiers comprises a ‘+’ operator.
11. The search system of claim 2 , wherein one of the quantifiers comprises a character.
12. The search system of claim 2 , wherein one of the quantifiers comprises a “{n,}” interval expression.
13. The search system of claim 2 , wherein one of the quantifiers comprises a “{n}” interval expression.
14. The search system of claim 2 , wherein one of the quantifiers comprises a “{n,m}” interval expression.
15. The search system of claim 1 , further comprising:
a placement module coupled to the compiler and configured to store information indicating which of the counter circuits, CAM rows, and memory elements of the PRS are available for receiving corresponding bit groups.
16. The search system of claim 1 , wherein one of the counter circuits includes inputs to receive an active signal, an increment signal, and a reset signal from one or more of the CAM rows, includes a first output to generate a first output signal indicating whether a count value CNT≧N, and includes a second output to generate a second output signal whether 0<CNT<N, wherein N is a quantifier specified by the regular expression.
17. The search system of claim 16 , wherein the active signal, the increment signal, and the reset signal are generated during a first compare operation in the CAM device, and the first and second output signals selectively enable one or more of the CAM rows for a next compare operation.
18. The search system of claim 1 , wherein the compiler transforms regular expression into an architecture-dependent regular expression characterized by a determination of the available resources of the CAM device.
19. A method for programming a content addressable memory (CAM) device having a plurality of rows of CAM cells and a number of counter circuits selectively interconnected by a programmable interconnect structure (PRS) to implement search operations for a regular expression, the method comprising:
compiling the regular expression into a number of first bit groups, a number of second bit groups, and a number of third bit groups;
loading the first bit groups into the CAM cells using an image loader;
loading the second bit groups into a number of memory elements that control configuration of the PRS using the image loader; and loading the third bit groups into the counter circuits using the image loader.
20. The method of claim 19 , wherein the first bit groups embody a number of characters of the regular expression, the second bit groups embody a number of metacharacters of the regular expression, and the third bit groups embody a number of quantifiers of the regular expression.
21. The method of claim 20 , wherein the metacharacter comprises a logical OR operator.
22. The method of claim 20 , wherein a portion of one of the first bit groups configures the PRS to selectively route match results from a first CAM row as an input match signal to any number of other arbitrarily selected CAM rows at the same time.
23. The method of claim 20 , wherein a portion of one of the third bit groups configures the counter circuit to identify only matching portions of an input string that have at least a specified minimum number of characters.
24. The method of claim 20 , wherein a portion of one of the third bit groups configures the counter circuit to identify all matching portions of an input string.
25. The method of claim 20 , wherein a portion of one of the third bit groups configures the counter circuit to count a match length of a matching substring.
26. The method of claim 19 , further comprising:
determining which of the counter circuits, CAM rows, and memory elements of the PRS are available for receiving corresponding bit groups.
27. The method of claim 26 , further comprising:
selectively altering the compiling in response to the determining.
28. The method of claim 19 , wherein compiling the regular expression comprises a reroll operation.
29. The method of claim 19 , wherein compiling the regular expression comprises a mid-level alternation split.
30. The method of claim 19 , wherein compiling the regular expression comprises a top-level alternation split.