Outer loop vectorization
First Claim
Patent Images
1. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of:
- analyzing each iterative loop to determine if it is vectorizable, wherein the step of analyzing each iterative loop includes the steps of;
preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; and
extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein each level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level;
determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge;
determining for each iterative loop whether there are dependence cycles within its respective level dependence graph; and
if an iterative loop from the plurality of iterative loops has no vectorization preventing dependence edges and no dependence cycles within its respective level dependence graph, indicating that the iterative loop is vectorizable; and
if more than one iterative loop is vectorizable, applying a selection criteria to select an optimal iterative loop from the plurality of iterative loops.
8 Assignments
0 Petitions
Accused Products
Abstract
A system and method for vectorizing a non-innermost loop of a nested loop. Iterative loops of a nested loop are analyzed to determine if they can be vectorized (vector legality). If more than one iterative loop can be vectorized, a selection criteria is applied to select the iterative loop which would provide the most return from vectorization (vector selection).
-
Citations
8 Claims
-
1. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of:
-
analyzing each iterative loop to determine if it is vectorizable, wherein the step of analyzing each iterative loop includes the steps of; preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; and extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein each level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level; determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge; determining for each iterative loop whether there are dependence cycles within its respective level dependence graph; and if an iterative loop from the plurality of iterative loops has no vectorization preventing dependence edges and no dependence cycles within its respective level dependence graph, indicating that the iterative loop is vectorizable; and if more than one iterative loop is vectorizable, applying a selection criteria to select an optimal iterative loop from the plurality of iterative loops. - View Dependent Claims (2)
-
-
3. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, including a kth-level iterative loop, wherein k is an integer greater than one, the method comprising the steps of:
-
preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; extracting, from the program dependence graph, a level dependence graph for the kth-level iterative loop, wherein the level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at level k; determining whether any dependence edges within the level dependence graph are k-vectorization preventing; determining if there are any dependence cycles within the level dependence graph; and if none of the dependence edges are k-vectorization preventing and if there are no dependence cycles within the level dependence graph, vectorizing the kth-level loop.
-
-
4. A computer-implemented method of vectorizing a nested loop having a plurality of iterative loops, the method comprising the steps of:
-
preparing a program dependence graph for the nested loop, wherein the program dependence graph explicitly represents both control and data dependencies; extracting, from the program dependence graph, a level dependence graph for each of the plurality of iterative loops, wherein the level dependence graph includes all control and data dependencies relevant to vectorization of the nested loop at that level; determining for each iterative loop whether dependence edges in its respective level dependence graph include a vectorization preventing dependence edge; determining for each iterative loop whether there are dependence cycles within its respective level dependence graph; building a list of those iterative loops having no vectorization preventing dependence edges and no dependence cycles within their respective level dependence graphs; selecting an iterative loop from the list of iterative loops; and vectorizing the selected iterative loop. - View Dependent Claims (5, 6, 7)
-
-
8. For computer program code having a nested loop, wherein the nested loop includes a plurality of vectorizable iterative loops, a computer-implemented method of selecting an optimal vectorizable iterative loop from the plurality of vectorizable iterative loops, the method comprising the steps of:
-
calculating a metric for each of the plurality of vectorizable iterative loops, wherein the step of calculating a metric includes the step of calculating overhead for an iterative loop as;
space="preserve" listing-type="equation">O.sub.l =(VLO+(T.sub.l /VL)*(ML+MS)/T.sub.lwhere (Tl /VL) is the number of vector trips; and selecting the iterative loop having the best metric.
-
Specification