Method of, system for, and computer program product for minimizing loop execution time by optimizing block/tile sizes
US5953531A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 25, 1997 |
| Grant date | Sep 14, 1999 |
| Priority date | — |
| Expiry date | Jul 25, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/443
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 execut…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.