Method and system for automated improvement of parallelism in program compilation
OwnerLoring G. Craymer, IIIinventor
Life of this patent
Estimating the term…
Abstract
A method of program compilation to improve parallelism during the linking of the program by a compiler. The method includes converting statements of the program to canonical form, constructing a traversable representation, such as an abstract syntax tree (AST), for each procedure in the program, and traversing the program to construct a graph by making each non-control flow statement and each control structure into at least one node of the graph.
Claims22
A computer implemented method of program compilation to improve parallelism during the linking of the program by a compiler, the method comprising:
- converting statements of the program to canonical form;
- constructing a traversable representation for each procedure in the program;
- and
- traversing the program to construct functional dataflow graph, in which an assignment statement or function call is represented as a node, a control flow decision is represented by a first set of nodes, an array or set is represented as a second set of nodes, and edges of the functional dataflow graph represent typed data;
- identifying at least one loop in the functional dataflow graph that can be executed in parallel;
- and
- transforming the at least one loop to a set operation by retyping connections between nodes of the functional dataflow graph.
A non-transitory machine-readable medium having instructions stored thereon, which when executed by a computer system, execute a method of program compilation to improve parallelism during the linking of the program by a compiler, the method comprising:
- converting statements of the program to canonical form;
- constructing a traversable representation for each procedure in the program;
- and
- traversing the program to construct functional dataflow graph, in which an assignment statement or function call is represented as a node, a control flow decision is represented by a first set of nodes, an array or set is represented as a second set of nodes, and edges of the functional dataflow graph represent typed data;
- identifying at least one loop in the functional dataflow graph that can be executed in parallel;
- and
- transforming the at least one loop to a set operation by retyping connections between nodes of the functional dataflow graph.
Dependencies are inferred from the claim text.