Method and apparatus for compiling regular expressions

Patent metadata

Field	Value
Publication number	US-2016019034-A1
Application number	US-201514868047-A
Country	US
Kind code	A1
Filing date	Sep 28, 2015
Priority date	Jan 25, 2011
Publication date	Jan 21, 2016
Grant date	—

Abstract

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.

First claim

1 . (canceled)

2 . 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:
mapping states of an automaton to hardware elements of a target device, the automaton created from source code elements; identifying at least one of a conflict or an optimization between the automaton and the target device during the mapping; 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.

3 . The machine-readable medium of claim 2 , wherein the target device is a parallel machine, and wherein the hardware elements are machine elements.

4 . The machine-readable medium of claim 2 , 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 2 , 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.

7 . The machine-readable medium of claim 2 , 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.

8 . A machine-implemented method comprising:
mapping states of an automaton to hardware elements of a target device, the automaton created from source code elements; identifying at least one of a conflict or an optimization between the automaton and the target device during the mapping; 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; routing the connections between the hardware elements as a function of the netlist; and producing machine code for the target device from the routed and placed netlist.

12 . 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.

13 . A system 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:
map states of an automaton to hardware elements of a target device, the automaton created from source code elements;
identify at least one of a conflict or an optimization between the automaton and the target device during the mapping;
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.

14 . The system of claim 13 , 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.

15 . The system of claim 13 , 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 system of claim 13 , 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 . 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:
converting 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; converting the automaton into a netlist; and placing and routing the netlist to provide machine code for configuring a target device.

18 . The machine readable medium of claim 17 , wherein the source code includes a quantification; and
wherein converting the source code includes converting the quantification into a plurality of states including the special purpose hardware state when the quantification meets a condition to be mapped to a special purpose hardware element.

19 . The machine readable medium of claim 18 , further comprising optimizing the automaton by splitting a particular state of the automaton into multiple states when an estimated in-degree of the particular state is greater than the constraint of the target device, the splitting including distributing driving states of the particular st

Assignees

• Micron Technology Inc

Inventors

• Glendenning Paul
• Xu Junjuan

Classifications

• G06F8/443

  Optimisation · CPC title

• G06F30/30

  Circuit design · CPC title

• G06F8/447 Primary

  Target code generation · CPC title

• G06F8/427

  Parsing · CPC title

• G06F8/41 Primary

  Compilation · CPC title