Method of, system for, and computer program product for minimizing loop

Abstract

An optimized set of block sizes for a nest of loops for improved data locality is determined by estimating a memory cost per iteration as a function of the block sizes and selecting a set of block sizes that yield a minimum memory cost per iteration subject to a plurality of constraints. An objective function is an estimated memory cost per iteration as a function of the block sizes. An optimal solution is provided by evaluating the objective function for candidate points in the iteration space. These candidate points comprise: corner points of the iteration space, intersections between constraints and the edges of the iteration space, zero-derivative points for the curve that is the intersection of constraints with the objective function, intersection points between constraints, and local optimum of the objective function. Alternatively, an optimized set of block sizes for a nest of loops may be determined by iteratively searching the iteration space for the optimal solution. The advantages provided include improved compiler optimization, improved selection of loop tile sizes, improved execution time for selection of loop block sizes, improved data access locality, improved execution time of nested program loops, different optimal block sizes for each loop of a loop nest, optimal block sizes for a loop nest containing an array variable whose number of dimensions are different from the number of loops in the loop nest, and optimal block sizes for a loop nest containing non-uniformly generated data.