×

Outer loop vectorization

  • US 5,802,375 A
  • Filed: 11/23/1994
  • Issued: 09/01/1998
  • Est. Priority Date: 11/23/1994
  • Status: Expired due to Fees
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.

View all claims
  • 8 Assignments
Timeline View
Assignment View
    ×
    ×