Back to results
US 9,753,727 B2Granted
Partial vectorization compilation system
AssigneeIntel Corporation
InventorsTin-Fook Ngai, Chunxiao Lin, Yingzhe Shen, Chao Zhang
Life of this patent
Estimating the term…
Abstract
Generally, this disclosure provides technologies for generating and executing partially vectorized code that may include backward dependencies within a loop body of the code to be vectorized. The method may include identifying backward dependencies within a loop body of the code; selecting one or more ranges of iterations within the loop body, wherein the selected ranges exclude the identified backward dependencies; and vectorizing the selected ranges. The system may include a vector processor configured to provide predicated vector instruction execution, loop iteration range enabling, and dynamic loop dependence checking.
Claims16
A system for processing partially vectorized code, said system comprising:
- a partial vectorizing compiler to:
- determine hot paths and cold paths within a loop body;
- remove any determined cold paths from consideration for vectorization;
- identify backward dependencies within a plurality of iterations within the loop body of said code, wherein at least one of said plurality of iterations includes at least one backward dependency, wherein said identifying includes:
- generating a static single assignment (SSA) analysis of said loop body;
- generating a loop dependence graph (LDG) based on said SSA of said loop body, said LDG comprising nodes and edges, wherein said nodes are associated with vectorization units of said SSA and said edges are associated with dependence relations between said nodes, and wherein said vectorization units comprise statements, expressions and operations, and said dependence relations comprise control dependence edges (CDE) and data dependence edges (DDE);
- partitioning said LDG into one or more first-type regions and one or more second-type regions, wherein said first-type regions comprise backward dependency loops and said second-type regions do not comprise backward dependency loops;
- and
- classifying at least one first-type region into a first category including loops having induction variables, a second category including strictly sequential backward dependency loops or a third category including conditionally vectorized backward dependency loops;
- select one or more ranges of said plurality of iterations within said loop body, wherein said selected ranges exclude said identified backward dependencies, and
- vectorize said selected ranges;
- and
- a vector processor to execute said selected ranges, wherein said vector processor is a hardware processor including one or more scalar processors.
10 more elements
A method for partial vectorization of code, said method comprising:
- determining hot paths and cold paths within a loop body;
- removing any determined cold paths from consideration for vectorization;
- identifying backward dependencies within a plurality of iterations within the loop body of said code, wherein at least one of said plurality of iterations includes at least one backward dependency, wherein said identifying comprises:
- generating a static single assignment (SSA) analysis of said loop body;
- generating a loop dependence graph (LDG) based on said SSA of said loop body, said LDG comprising nodes and edges,
- wherein said nodes are associated with vectorization units of said SSA and said edges are associated with dependence relations between said nodes, and
- wherein said vectorization units comprise statements, expressions and operations, and said dependence relations comprise control dependence edges (CDE) and data dependence edges (DDE);
- partitioning said LDG into one or more first-type regions and one or more second-type regions, wherein said first-type regions comprise backward dependency loops and said second-type regions do not comprise backward dependency loops;
- and
- classifying at least one first-type region into a first category including loops having induction variables, a second category including strictly sequential backward dependency loops or a third category including conditionally vectorized backward dependency loops;
- selecting one or more ranges of said plurality of iterations within said loop body, wherein said selected ranges exclude said identified backward dependencies;
- and
- vectorizing said selected ranges.
10 more elements
A non-transitory computer-readable storage medium having instructions stored thereon which when executed by a processor result in the following operations for partial vectorization of code, said operations comprising:
- determining hot paths and cold paths within a loop body;
- removing any determined cold paths from consideration for vectorization;
- identifying backward dependencies within a plurality of iterations within the loop body of said code, wherein at least one of said plurality of iterations includes at least one backward dependency, wherein said identifying comprises:
- generating a static single assignment (SSA) analysis of said loop body;
- generating a loop dependence graph (LDG) based on said SSA of said loop body, said LDG comprising nodes and edges,
- wherein said nodes are associated with vectorization units of said SSA and said edges are associated with dependence relations between said nodes, and
- wherein said vectorization units comprise statements, expressions and operations, and said dependence relations comprise control dependence edges (CDE) and data dependence edges (DDE);
- partitioning said LDG into one or more first-type regions and one or more second-type regions, wherein said first-type regions comprise backward dependency loops and said second-type regions do not comprise backward dependency loops;
- classifying at least one first-type region into a first category including loops having induction variables, a second category including strictly sequential backward dependency loops or a third category including conditionally vectorized backward dependency loops;
- selecting one or more ranges of iterations within said at least one sub-loop body, wherein said selected ranges exclude said identified backward dependencies;
- and
- vectorizing said selected ranges.
9 more elements
Dependencies are inferred from the claim text.