Method of, system for, and computer program product for performing weighted loop fusion by an optimizing compiler

Claim 3

The method of claim 1 wherein the minimizing step comprises minimizing a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (ij).di-elect cons.B∪C, subject to a set of constraints comprising: ##EQU11##

Claim 4

The method of claim 2 further comprising the steps of: arranging subproblems in the form of a branch and bound tree wherein a node (C',O) of the branch and bound tree is characterized by two disjoint subsets: (i) C'C, a set of arcs have been decided to remain not contracted, and (ii) OC, a set of arcs that have already been contracted; defining b ij =0 if and only π i =π j , and b ij =1 otherwise; for each subproblem, minimizing a summation of a product of w ij and b ij over a set of nodes (i,j).di-elect cons.B∪C-(C'∪O), subject to a set of constraints comprising: ##EQU12## determining a lower bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≧[V 2 (C',O)]/n'+Σ.sub.(i,j).di-elect cons.O w ij , wherein an optimal value of (C',O) 1 is V 1 (C',O), an optimal value of (C',O) 2 is V 2 (C',O), and n' is a number of nodes remaining after a contraction given by O; and deriving an upper bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≦V 2 (C',O)+Σ.sub.(i,j).di-elect cons.O w ij .

Claim 5

An article of manufacture for use in a computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to: create a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest; associate a weight w ij =w ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused; determine a set, AN×N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n}; determine a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA; determine a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C determine a set, B, of unordered pairs of nodes (i,j) that have a w ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A; associate a (0,1)-variable x ij with each unordered pair of nodes (i,j), and setting the x ij =0 if and only if i and j are placed in a same cluster and setting x ij =1 otherwise; determine a set of multipliers π i (i.di-elect cons.N) wherein each of the multipliers π i are an integer between 0 and n=|N|, wherein π j -π i ≧1 for all (i,j).di-elect cons.A, wherein π i =π j if x ij =0, wherein π j -π i ≧1 if x ij =1 and (i,j).di-elect cons.A; and minimize a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (i,j).di-elect cons.B∪C, subject to a set of constraints comprising: ##EQU13## perform loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.

Claim 6

An article of manufacture for use in a computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to: create a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest; associate a weight w ij =w ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused; determine a set, AN×N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n}; determine a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA; determine a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C determine a set, B, of unordered pairs of nodes (i,j) that have a w ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A; associate a (0,1)-variable x ij with each unordered pair of nodes (i,j), and setting the x ij =0 if and only if i and j are placed in a same cluster and setting x ij =1 otherwise; determine a set of multipliers π i (i.di-elect cons.N) wherein each of the multipliers π i are an integer between 0 and n=|N|, wherein π j -π i ≧1 for all (i,j).di-elect cons.A, wherein π i =π j if x ij =0, wherein π j -π i ≧1 if x ij =1 and (i,j).di-elect cons.A; and minimize a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (i,j).di-elect cons.B∪C, subject to a set of constraints comprising: ##EQU13## perform loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.

Claim 7

The article of manufacture of claim 4 wherein the computer program in causing the computer system to minimize the summation may further cause the computer system to minimize a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (i,j).di-elect cons.B∪C, subject to a set of constraints comprising: ##EQU14##

Claim 8

The article of manufacture of claim 5 wherein the computer program may further cause the computer system to: arrange subproblems in the form of a branch and bound tree wherein a node (C',O) of the branch and bound tree is characterized by two disjoint subsets: (i) C'C, a set of arcs have been decided to remain not contracted, and (ii) O∪C, a set of arcs that have already been contracted; define b ij =0 if and only π i =π j , and b ij =1 otherwise; for each subproblem, minimize a summation of a product of w ij and b ij over a set of nodes (i,j).di-elect cons.B∪C-(C'∪O), subject to a set of constraints comprising: ##EQU15## determine a lower bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≧[V 2 (C',O)]/n'+Σ.sub.(i,j).di-elect cons.O w ij , wherein an optimal value of (C',O) 1 is V 1 (C',O), an optimal value of (C',O) 2 is V 2 (C',O), and n' is a number of nodes remaining after a contraction given by O; and derive an upper bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≦V 2 (C',O)+Σ.sub.(i,j).di-elect cons.O w ij .

Claim 9

A computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said computer system comprising: means for creating a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest; means for associating a weight w ij =w ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused; means for determining a set, AN×N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n}; means for determining a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA; means for determining a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C means for determining a set, B, of unordered pairs of nodes (i,j) that have a w ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A; means for associating a (0,1)-variable x ij with each unordered pair of nodes (i,j), where the x ij =0 if and only if i and j are placed in a same cluster and x ij =1 otherwise; means for determining a set of multipliers π i (i.di-elect cons.N) wherein each of the multipliers π i are an integer between 0 and n=|N|, wherein π j -π i ≧1 for all (i,j).di-elect cons.A, wherein π i =π j if x ij =0, wherein π j -π i ≧1 if x ij =1 and (i,j).di-elect cons.A; and means for minimizing a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs ##EQU16## means for performing loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.

Claim 10

A computer system for performing weighted loop fusion on a plurality of loop nests by the computer system, said computer system comprising: means for creating a loop dependence graph (LDG) representing the plurality of loop nests, wherein each of the plurality of loop nests is associated with a node of the LDG, and wherein an edge of the LDG represents a loop-independent data dependence from a source loop nest to a destination loop nest; means for associating a weight w ij =w ji with each pair of nodes i and j, wherein the weight represents a cost savings obtained if loop nests i and j are fused; means for determining a set, AN×N, of directed summary arcs on N, wherein N is a set of nodes of the loop dependence graph, N={1, 2, . . . , n}; means for determining a set, C, of contractable arcs wherein C is a subset of the set of directed summary arcs, CA; means for determining a set, NC, of noncontractable arcs wherein NC is a subset of the set of directed summary arcs, NC=A-C means for determining a set, B, of unordered pairs of nodes (i,j) that have a w ij >0 and that are not connected by a summary arc, both (i,j).epsilon slash.A and (j,i).epsilon slash.A; means for associating a (0,1)-variable x ij with each unordered pair of nodes (i,j), where the x ij =0 if and only if i and j are placed in a same cluster and x ij =1 otherwise; means for determining a set of multipliers π i (i.di-elect cons.N) wherein each of the multipliers π i are an integer between 0 and n=|N|, wherein π j -π i ≧1 for all (i,j).di-elect cons.A, wherein π i =π j if x ij =0, wherein π j -π i ≧1 if x ij =1 and (i,j).di-elect cons.A; and means for minimizing a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs ##EQU16## means for performing loop fusion on the plurality of loop nests using loop partitions based on the minimized summation.

Claim 11

The computer system of claim 7 wherein the minimization further comprises a minimization of a summation of a product of w ij and x ij over a set of nodes (i,j) comprising a union of the set B and the set of contractable arcs C, (i,j).di-elect cons.B∪C, subject to a set of constraints comprising: ##EQU17##

Claim 12

The computer system of claim 8 further comprising: an arrangment of subproblems in the form of a branch and bound tree wherein a node (C',O) of the branch and bound tree is characterized by two disjoint subsets: (i) C'C, a set of arcs have been decided to remain not contracted, and (ii) OC, a set of arcs that have already been contracted; a set b ij where b ij =0 if and only π i =π j , and b ij =1 otherwise; a minimization for each subproblem of a summation of a product of w ij and b ij over a set of nodes (i,j).di-elect cons.B∪C-(C'∪O), subject to a set of constraints comprising: ##EQU18## a determination of a lower bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≧[V 2 (C',O)]/n'+Σ.sub.(i,j).di-elect cons.O w ij , wherein an optimal value of (C',O) 1 is V 1 (C',O), an optimal value of (C',O) 2 is V 2 (C',O), and n' is a number of nodes remaining after a contraction given by O; and a determination of an upper bound for a node (C',O) of the branch and bound tree by determining V 1 (C',O)≦V 2 (C',O)+Σ.sub.(i,j).di-elect cons.O w ij .