9,617
edits
Compiler Design: Difference between revisions
From dankwiki
→Memory Hierarchy
(→Caches) |
|||
| Line 37: | Line 37: | ||
* Loop interchange -- are we striding through nested loops optimally? If not, we can interchange levels, provided all dependencies are preserved. Especially powerful when combined with hardware- or software-based prefetching and further augmented with non-blocking caches. Optimal interpositioning is NP-hard in general but excellent heuristics exist. See Allen/Kennedy p. 472-474. | * Loop interchange -- are we striding through nested loops optimally? If not, we can interchange levels, provided all dependencies are preserved. Especially powerful when combined with hardware- or software-based prefetching and further augmented with non-blocking caches. Optimal interpositioning is NP-hard in general but excellent heuristics exist. See Allen/Kennedy p. 472-474. | ||
** This can be valuable enough that we perform small transformations to accommodate it: loop alignment, loop peeling, etc | ** This can be valuable enough that we perform small transformations to accommodate it: loop alignment, loop peeling, etc | ||
* Loop blocking/tiling/strip-mining -- breaking out subloops to work on a cache-friendly block at once, good for parallelizing | |||
==See Also== | ==See Also== | ||
* [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math] | * [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math] | ||
* The [http://llvm.org/ LLVM] Compiler Infrastructure Project at [http://www.cs.uiuc.edu/ UIUC] | * The [http://llvm.org/ LLVM] Compiler Infrastructure Project at [http://www.cs.uiuc.edu/ UIUC] | ||
