Utilizing special purpose elements to implement a FSM
Apparatus, systems, and methods for a compiler are described. One such compiler generates machine code corresponding to a set of elements including a general purpose element and a special purpose element. The compiler identifies a portion in an arrangement of relationally connected operators that corresponds to a special purpose element. The compiler also determines whether the portion meets a condition to be mapped to the special purpose element. The compiler also converts the arrangement into an automaton comprising a plurality of states, wherein the portion is converted using a special purpose state that corresponds to the special purpose element if the portion meets the condition. The compiler also converts the automaton into machine code. Additional apparatus, systems, and methods are disclosed.
1. A computer-implemented method for generating machine code corresponding to a set of elements including a general purpose element and a special purpose element, the special purpose element being a single element implementation of a function that can be performed by a plurality of general purpose elements, the method comprising:
determining whether a portion in an arrangement of relationally connected operators meets a condition to be mapped to the special purpose element;
mapping the portion to a special purpose element if the portion meets the condition and to one or more the general purpose elements otherwise, the mapping including converting the arrangement into an automaton comprising a plurality of states, wherein the portion is converted using a special purpose state that corresponds to the special purpose element if mapped to the special purpose element and the portion is converted into a general purpose state otherwise; and
converting the arrangement of relationally connected operators into machine code by converting the automaton into machine code.
2. The computer-implemented method of claim 1 , wherein the machine code comprises an image for a parallel machine.
3. The computer-implemented method of claim 1 , wherein identifying a portion in the arrangement that corresponds to a special purpose element comprises identifying an operator of the relationally connected operators that can be implemented using the special purpose element.
4. The computer-implemented method of claim 1 , wherein converting the arrangement into an automaton comprises converting each of the operators in the arrangement into one or more of the plurality of states.
5. The computer-implemented method of claim 1 , wherein the portion is converted using a general purpose state and not using a special purpose state that corresponds to a special purpose element if the portion does not meet the condition, wherein the general purpose state corresponds to the general purpose element.
6. The computer-implemented method of claim 1 , wherein the portion comprises a first portion and wherein a second portion of the arrangement is converted using a general purpose state and not using a special purpose state that corresponds to a special purpose element if the second portion is not identified as corresponding to a special purpose element, where the general purpose state corresponds to a general purpose element.
7. The computer-implemented method of claim 1 , wherein the set of elements includes a set of hardware elements of a parallel machine, wherein the general purpose element comprises a programmable element and wherein the special purpose element includes a counter.
8. The computer-implemented method of claim 7 , wherein the programmable element comprises a state machine element.
9. The computer-implemented method of claim 8 , wherein the state machine element includes a memory cell.
10. The computer-implemented method of claim 9 , wherein the memory cell comprises a volatile memory cell.
11. The computer-implemented method of claim 1 , further comprising:
publishing the machine code.
12. The computer-implemented method of claim 11 , wherein publishing the machine code includes loading the machine code onto a parallel machine.
13. The computer-implemented method of claim 11 , wherein publishing the machine code includes storing the machine code on a computer readable medium.
14. A non-transitory computer-readable medium including instructions, which when executed by the computer, cause the computer to perform operations comprising:
identifying a portion in an arrangement of relationally connected operators that corresponds to a special purpose element for a target device, the special purpose element being single element implementation of a function that can be performed by a plurality of general purpose elements of the target device, the target device also including at least one general purpose element;
determining whether the portion meets a condition to be mapped to the special purpose element;
converting the arrangement into an automaton comprising a plurality of states, wherein the portion is converted using a special purpose state that corresponds to the special purpose element if the portion meets the condition and to a general purpose state otherwise; and
converting the automaton into machine code.
15. The computer-readable medium of claim 14 , wherein the instructions cause the computer to perform operations comprising:
converting source code into the arrangement; and
publishing the machine code.
16. The computer-readable medium of claim 14 , wherein determining whether the portion meets a condition to be mapped to a special purpose element comprises determining whether the portion is deterministic.
17. The computer-readable medium of claim 16 , wherein identifying a portion of the arrangement includes:
identifying a quantification; and
wherein determining whether the portion is deterministic includes determining whether a drive expression for the quantification can be matched while the quantification is being processed.
18. The computer-readable medium of claim 16 , wherein identifying a portion of the arrangement includes:
identifying a quantification; and
wherein determining whether the portion is deterministic includes determining whether a repeated expression of the quantification is a prefix of another repeated expression of the quantification.
19. The computer-readable medium of claim 16 , wherein identifying a portion in the arrangement includes identifying a quantification.
20. The computer-readable medium of claim 19 , wherein determining whether the portion is deterministic includes determining whether a drive expression for the quantification can be matched while the quantification is being processed, and determining whether a repeated expression of the quantification is a prefix of another repeated expression of the quantification.
21. The computer-readable medium of claim 20 , wherein the special purpose element includes a counter having a corresponding counter state in the automaton and the general purpose element includes a state machine element having a corresponding state machine element state in the automaton.
22. The computer-readable medium of claim 21 , wherein when the portion corresponds to a quantification and the portion is deterministic, the portion is implemented as a loop comprising a repeated expression of the quantification and a counter state, wherein the counter state is configured to count a number of times the repeated expression is matched, and wherein the counter state activates a downstream state when the repeated expression is matched a number of times specified by the quantification.
23. The computer-readable medium of claim 22 , wherein the loop is exited by a match with a negated version of the repeated expression.
24. The computer-readable medium of claim 22 , wherein when the quantification can be matched with a single number of loops,
configuring the repeated expression to assert a counting input of the counter state;
configuring a negated version of the repeated expression to reset the counter state; and
configuring the counter state to assert an output when the counting input has been asserted a number of times equal to the number of loops without the counter state being reset.
25. The computer-readable medium of claim 22 , wherein when the quantification can be matched with a multiple number of loops,
configuring the repeated expression to assert a counting input of a first counter state and a counting input of a second counter state;
configuring the repeated expression to assert a reset input of the first counter state and a reset input of the second counter state;
configuring the first counter state to assert an output when the counting input of the first counter state has been asserted a number of times equal to a low threshold of the multiple number of loops without the first counter state being reset; and
configuring the second counter state to assert an output of the second counter state when the counting input of the second counter state has been asserted a number of times equal to a high threshold of the multiple number of loops without the second counter state being reset, wherein the output of the second counter state is configured to assert the reset input of the first counter state.
26. A computer comprising:
a memory having software stored thereon; and
a processor communicatively coupled to the memory, wherein the software, when executed by the processor, causes the processor to:
compile regular expressions into code for a target device by parsing the regular expressions to form a syntax tree and converting the syntax tree into an automaton, wherein the target device supports a first type of element and at least one other type of element;
wherein to compile includes mapping a first regular expression that corresponds to the first type of element to the first type of element via a first state in the automaton corresponding to the first type of element; and
wherein compile includes mapping a second regular expression that does not correspond to the first type of element to the at least one other type of element via a second state in the automaton corresponding to the at least one other type of element.
27. The computer of claim 26 , wherein the target device comprises a parallel machine, and the first type of element is a first type of hardware element and the at least one other type of element includes a second type of hardware element.
28. The computer of claim 27 , wherein the second type of hardware element can receive an input stream and provide an output as a function of the input stream; and
wherein the first type of hardware element does not receive the input stream and provides an output as a function of inputs from other elements of the target device.
29. The computer of claim 28 , wherein the first type of element is a counter and the second type of element is a state machine element.
30. The computer of claim 26 , wherein the software causes the processor to:
determine whether a regular expression is of a type that corresponds to the first type of element; and
when the regular expression is not of a type that corresponds to the first type of element, map the regular expression to the at least one other type of element.
31. The computer of claim 30 , wherein determine whether a regular expression is of a type that corresponds to the first type of element includes:
determining whether the regular expression is a quantification; and
when the regular expression is not of a quantification, map the regular expression to the at least one other type of element.
32. The computer of claim 31 , wherein the software causes the processor to:
determine whether the quantification is deterministic;
when the quantification is deterministic, map the regular expression to the first type of element; and
when the quantification is not deterministic, map the regular expression to the at least one other type of element.
33. The computer of claim 32 , wherein determine whether the quantification is deterministic includes determine whether a drive expression for the quantification can be matched while the quantification is being processed and whether a repeated expression of the quantification is a prefix of another repeated expression of the quantification.
34. The computer of claim 26 , wherein compile includes:
converting the automaton into a netlist;
placing instances of the netlist; and
routing connections between the instances of the netlist.
35. The computer of claim 34 , wherein the regular expressions comprise criteria for searching unstructured data.
36. A system comprising:
a computer configured to:
identify a portion in an arrangement of relationally connected operators that corresponds to a special purpose element of a target device, the special purpose element being a single element implementation of a function that can be performed by a plurality of general purpose elements of the target device, the target device also including at least one general purpose element;
determine whether the portion meets a condition to be mapped to the special purpose element;
convert the arrangement into an automaton comprising a plurality of interconnected states, wherein the portion is converted into a special purpose state that corresponds to the special purpose element if the first portion meets the condition and to a general purpose state otherwise; and
convert the automaton into machine code; and
a device for programming a parallel machine, the device configured to load the machine code onto the parallel machine.
37. The system of claim 36 , wherein determine whether the portion meets a condition to be mapped to a special purpose element comprises determine whether the portion is deterministic.
38. The system of claim 36 , wherein identify a portion of the arrangement includes:
identify a quantification; and
wherein determine whether the portion is deterministic includes determine whether a drive expression for the quantification can be matched while the quantification is being processed and whether a repeated expression of the quantification is a prefix of another repeated expression of the quantification.
39. A parallel machine programmed by an image produced using the process of claim 1 .