Tiling across loop nests with possible recomputation
US8671401B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 9, 2007 |
| Grant date | Mar 11, 2014 |
| Priority date | — |
| Expiry date | May 23, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/433
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Described is a technology by which a series of loop nests corresponding to source code are detected by a compiler, with the series of loop nests tiled together, (thereby increasing the ratio of cache hits to misses in a multi-processor environment). The compiler transforms the series of loop nests into a plurality of tile loops within a controller loop, including using dependency analysis to determine which results from a tile loop need to be pre-computed before another tile loop. For dependency analysis, the compiler may use a directed acyclic graph as a high-level intermediate representation, and split the graph into sub-graphs each representing an array. The compiler uses descriptors processed from the graph to determine the controller loop and the tile loops within that controller loop.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.