Vectorizing combinations of program operations

• US 8,640,112 B2
• Filed: 03/30/2011
• Issued: 01/28/2014
• Est. Priority Date: 03/30/2011
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Yi, Haoran, Duggan, Brady C., Dye, Robert E., Bordelon, Adam L., Kodosky, Jeffrey L.
• Primary Examiner(s): Kang, Insun
• Application Number:
  US13/076,245
• Publication Number:
  US 20120254845A1
• Time in Patent Office: 1,035 Days
• Field of Search: None
• US Class Current: 717/149
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

System and method for vectorizing combinations of program operations. Program code is received that includes a combination of individually vectorizable program portions that collectively implement a first computation. Each individually vectorizable program portion has at least one array input and at least one array output. The combination of individually vectorizable program portions is transformed into a single vectorizable program portion that is or includes a functional composition of the combination of individually vectorizable program portions. Vectorized executable code implementing the first computation is generated based on the single vectorizable program portion. The generated executable code is directed to SIMD (Single-Instruction-Multiple-Data) computing units of a target processor.

Claims

1. A non-transitory computer accessible memory medium that stores program instructions for vectorizing combinations of program operations, wherein the program instructions are executable to perform:

receiving program code comprising a combination of individually vectorizable program portions that collectively implement a first computation, wherein each individually vectorizable program portion has at least one array input and at least one array output, wherein the program code comprises graphical program code in a graphical program, wherein the graphical program comprises a plurality of interconnected nodes that visually indicate functionality of the graphical program code;

transforming the combination of individually vectorizable program portions into a single vectorizable program portion, wherein the single vectorizable program portion comprises a functional composition of the combination of individually vectorizable program portions; and

generating vectorized executable code implementing the first computation based on the single vectorizable program portion, wherein said generating comprises generating executable code directed to SIMD (Single-Instruction-Multiple-Data) computing units of a target processor.

2. The non-transitory computer accessible memory medium of claim 1, wherein said transforming the combination of individually vectorizable program portions into a single vectorizable program portion comprises:

analyzing data dependences between operations of the individually vectorizable program portions;

generating one or more expressions representing each individually vectorizable program portion, based on said analyzing;

merging the one or more expressions from each individually vectorizable program portion into a single set of expressions representing the first computation; and

creating the single vectorizable program portion implementing the first computation in response to said merging, wherein the single vectorizable program portion comprises the single set of expressions.

3. The non-transitory computer accessible memory medium of claim 2, wherein said analyzing data dependences between operations of the individually vectorizable program portions comprises:

traversing a data flow graph corresponding to the program code in reverse data flow order, including traversing elements in the data flow graph that correspond to the combination of program portions; and

wherein the single set of expressions representing the first computation comprises one or more recursive expressions in an intermediate form.

4. The non-transitory computer accessible memory medium of claim 3, wherein the combination of program portions comprises two or more output arrays, wherein said traversing the data flow graph in reverse data flow order comprises performing said traversing the data flow graph in reverse data flow order from each of the two or more output arrays respectively.

5. The non-transitory computer accessible memory medium of claim 3, wherein the one or more recursive expressions comprises:

one or more expression trees;

or

one or more directed acyclic graph (DAG) representations for the one or more recursive expressions.

6. The non-transitory computer accessible memory medium of claim 3, wherein the program instructions are further executable to perform:

generating the data flow graph based on the program code.

7. The non-transitory computer accessible memory medium of claim 1, wherein the program code is a first part of a program, wherein the program further comprises one or more additional parts, each additional part comprising a respective combination of program portions, and wherein each program portion in each respective combination of program portions has at least one array input and at least one array output, wherein the program instructions are further executable to perform:

performing said receiving and said transforming for each of the respective combinations of program portions, thereby generating one or more respective additional single vectorizable program portions;

merging the single vectorizable program portion with at least one of the one or more additional single vectorizable program portions in response to determining that;

the at least one array input of the single vectorizable program portion and the at least one array input of the at least one additional single vectorizable program portion have equal numbers of elements, and there is no dependency between the single vectorizable program portion and the at least one array input of the at least one of the one or more additional single vectorizable program portions; and

any heterogeneous input structures of the vectorization node and the at least one of the one or more additional single vectorizable program portions have the same type.

8. The non-transitory computer accessible memory medium of claim 1, wherein at least two of the program portions comprise:

polymorphic primitives;

or

vectorizable loops.

9. The non-transitory computer accessible memory medium of claim 1, wherein the program code comprises data flow program code.

10. The non-transitory computer accessible memory medium of claim 1, wherein the program instructions are further executable to perform:

graphically indicating any vectorized program portions in the program code.

11. The non-transitory computer accessible memory medium of claim 1, wherein the program code is configured to perform one or more of:

an industrial automation function;

a process control function;

a test and measurement function.

12. A computer-implemented method for vectorizing combinations of program operations, the method comprising:

utilizing a computer to perform;

receiving program code comprising a combination of individually vectorizable program portions that collectively implement a first computation, wherein each individually vectorizable program portion has at least one array input and at least one array output, wherein the program code comprises graphical program code in a graphical program, wherein the graphical program comprises a plurality of interconnected nodes that visually indicate functionality of the graphical program code;

transforming the combination of individually vectorizable program portions into a single vectorizable program portion, wherein the single vectorizable program portion comprises a functional composition of the combination of individually vectorizable program portions; and

generating vectorized executable code implementing the first computation based on the single vectorizable program portion, wherein said generating comprises generating executable code directed to SIMD (Single-Instruction-Multiple-Data) computing units of a target processor.

13. The computer-implemented method of claim 12, wherein said transforming the combination of individually vectorizable program portions into a single vectorizable program portion comprises:

analyzing data dependences between operations of the individually vectorizable program portions;

generating one or more expressions representing each individually vectorizable program portion, based on said analyzing;

merging the one or more expressions from each individually vectorizable program portion into a single set of expressions representing the first computation; and

creating the single vectorizable program portion implementing the first computation in response to said merging, wherein the single vectorizable program portion comprises the single set of expressions.

14. The computer-implemented method of claim 13, wherein said analyzing data dependences between operations of the individually vectorizable program portions comprises:

traversing a data flow graph corresponding to the program code in reverse data flow order, including traversing elements in the data flow graph that correspond to the combination of program portions; and

wherein the single set of expressions representing the first computation comprises one or more recursive expressions in an intermediate form.

15. The computer-implemented method of claim 14, wherein the combination of program portions comprises two or more output arrays, wherein said traversing the data flow graph in reverse data flow order comprises performing said traversing the data flow graph in reverse data flow order from each of the two or more output arrays respectively.

16. The computer-implemented method of claim 14, wherein the one or more recursive expressions comprises:

one or more expression trees;

or

one or more directed acyclic graph (DAG) representations for the one or more recursive expressions.

17. The computer-implemented method of claim 14, further comprising:

generating the data flow graph based on the program code.

18. The computer-implemented method of claim 12, wherein the program code is a first part of a program, wherein the program further comprises one or more additional parts, each additional part comprising a respective combination of program portions, and wherein each program portion in each respective combination of program portions has at least one array input and at least one array output, the method further comprising:

utilizing the computer to perform;

performing said receiving and said transforming for each of the respective combinations of program portions, thereby generating one or more respective additional single vectorizable program portions;

merging the single vectorizable program portion with at least one of the one or more additional single vectorizable program portions in response to determining that;

the at least one array input of the single vectorizable program portion and the at least one array input of the at least one additional single vectorizable program portion have equal numbers of elements, and there is no dependency between the single vectorizable program portion and the at least one array input of the at least one of the one or more additional single vectorizable program portions; and

any heterogeneous input structures of the vectorization node and the at least one of the one or more additional single vectorizable program portions have the same type.

19. The computer-implemented method of claim 12, wherein at least two of the program portions comprise:

polymorphic primitives;

or

vectorizable loops.

20. The computer-implemented method of claim 12, wherein the program code comprises data flow program code.

21. The computer-implemented method of claim 12, further comprising:

utilizing the computer to perform;

graphically indicating any vectorized program portions in the program code.

22. The computer-implemented method of claim 12,

wherein the program code is configured to perform one or more of:

an industrial automation function;

a process control function;

a test and measurement function.

23. A system for vectorizing combinations of program operations, comprising:

a processor; and

a memory medium coupled to the processor; and

a display device;

wherein the memory medium stores program instructions executable by the processor to;

receive program code comprising a combination of individually vectorizable program portions that collectively implement a first computation, wherein each individually vectorizable program portion has at least one array input and at least one array output, wherein the program code comprises graphical program code in a graphical program, wherein the graphical program comprises a plurality of interconnected nodes that visually indicate functionality of the graphical program code;

transform the combination of individually vectorizable program portions into a single vectorizable program portion, wherein the single vectorizable program portion comprises a functional composition of the combination of individually vectorizable program portions; and

generate vectorized executable code implementing the first computation based on the single vectorizable program portion, wherein said generating comprises generating executable code directed to SIMD (Single-Instruction-Multiple-Data) computing units of a target processor.