Method and apparatus for compiling regular expressions
Apparatus, systems, and methods for a compiler are described. One such compiler converts source code into an automaton comprising states and transitions between the states, wherein the states in the automaton include a special purpose state that corresponds to a special purpose hardware element. The compiler converts the automaton into a netlist, and places and routes the netlist to provide machine code for configuring a target device.
1. A machine-readable medium that is not a transitory propagating signal, the machine-readable medium including instructions that, when executed by a machine, cause the machine to perform operations comprising:
obtaining an automaton created from source code, the automaton comprising states and transitions between the states;
identifying a target device, the target device including hardware elements and connections between hardware elements;
fitting the automaton to the target device by mapping the states of the automaton to hardware elements of the target device and identifying at least one of a conflict or an optimization between the automaton and the target device during the fitting;
modifying the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton; and
mapping the modified automaton to the target device.
2. The machine-readable medium of claim 1 , wherein identifying the optimization includes identifying a special purpose hardware element of the target device that performs multiple states of the automaton, and wherein modifying the automaton to resolve the optimization includes collapsing the multiple states into a single special purpose state corresponding to the special purpose hardware element.
3. The machine-readable medium of claim 1 , wherein identifying the conflict includes identifying an in-degree limitation to a hardware element from the connections between hardware elements that is smaller than the in-degree of a state mapped to the hardware element, and wherein modifying the automaton to resolve the conflict includes dividing the state until the in-degree of each divided state is less than or equal to in-degree limitation.
4. The machine-readable medium of claim 1 , wherein mapping the modified automaton to the target device includes:
converting the automaton into a netlist, wherein the netlist includes a plurality of instances, each instance corresponding to a hardware element of a target hardware device;
placing each of the instances including assigning each instance in the netlist to a hardware element of the target device; and
routing the connections between the hardware elements as a function of the netlist.
5. The machine-readable medium of claim 4 , comprising producing machine code for the target device from the routed and placed netlist.
6. The machine-readable medium of claim 4 , wherein placing each of the instances includes grouping instances to match location constraints of corresponding hardware elements on the target device.
7. The machine-readable medium of claim 1 , wherein the target device is a parallel machine, and wherein the hardware elements are machine elements.
8. A machine-implemented method comprising:
obtaining an automaton created from source code, the automaton comprising states and transitions between the states;
identifying a target device, the target device including hardware elements and connections between hardware elements;
fitting the automaton to the target device by mapping the states of the automaton to hardware elements of the target device and identifying at least one of a conflict or an optimization between the automaton and the target device during the fitting;
modifying the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton; and
mapping the modified automaton to the target device.
9. The method of claim 8 , wherein identifying the optimization includes identifying a special purpose hardware element of the target device that performs multiple states of the automaton, and wherein modifying the automaton to resolve the optimization includes collapsing the multiple states into a single special purpose state corresponding to the special purpose hardware element.
10. The method of claim 8 , wherein identifying the conflict includes identifying an in-degree limitation to a hardware element from the connections between hardware elements that is smaller than the in-degree of a state mapped to the hardware element, and wherein modifying the automaton to resolve the conflict includes dividing the state until the in-degree of each divided state is less than or equal to in-degree limitation.
11. The method of claim 8 , wherein mapping the modified automaton to the target device includes:
converting the automaton into a netlist, wherein the netlist includes a plurality of instances, each instance corresponding to a hardware element of a target hardware device;
placing each of the instances including assigning each instance in the netlist to a hardware element of the target device; and
routing the connections between the hardware elements as a function of the netlist.
12. The method of claim 11 , comprising producing machine code for the target device from the routed and placed netlist.
13. The method of claim 11 , wherein placing each of the instances includes grouping instances to match location constraints of corresponding hardware elements on the target device.
14. A computer comprising:
a memory including instructions stored thereon; and
a processor communicatively coupled to the memory when the computer is in operation, wherein the instructions, when executed by the processor, cause the processor to:
obtain an automaton created from source code, the automaton comprising states and transitions between the states;
identify a target device, the target device including hardware elements and connections between hardware elements;
fit the automaton to the target device by mapping the states of the automaton to hardware elements of the target device and identifying at least one of a conflict or an optimization between the automaton and the target device during the fitting;
modify the automaton to resolve the at least one of the conflict or the optimization to create a modified automaton; and
map the modified automaton to the target device.
15. The computer of claim 14 , wherein to identify the optimization includes identifying a special purpose hardware element of the target device that performs multiple states of the automaton, and wherein to modify the automaton to resolve the optimization includes collapsing the multiple states into a single special purpose state corresponding to the special purpose hardware element.
16. The computer of claim 14 , wherein to identify the conflict includes identifying an in-degree limitation to a hardware element from the connections between hardware elements that is smaller than the in-degree of a state mapped to the hardware element, and wherein to modify the automaton to resolve the conflict includes dividing the state until the in-degree of each divided state is less than or equal to in-degree limitation.
17. The computer of claim 14 , wherein to map the modified automaton to the target device includes the processor to:
convert the automaton into a netlist, wherein the netlist includes a plurality of instances, each instance corresponding to a hardware element of a target hardware device;
place each of the instances including assigning each instance in the netlist to a hardware element of the target device; and
route the connections between the hardware elements as a function of the netlist.
18. The computer of claim 17 , comprising instructions that cause the processor to produce machine code for the target device from the routed and placed netlist.
19. The computer of claim 17 , wherein to place each of the instances includes grouping instances to match location constraints of corresponding hardware elements on the target device.
20. The computer of claim 14 , wherein the target device is a parallel machine, and wherein the hardware elements are machine elements.