Loading...
Please wait, while we are loading the content...
Automatic Tiling of “ Mostly-Tileable ” Loop Nests
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wonnacott, David G. |
| Copyright Year | 2014 |
| Abstract | Polyhedral compilation techniques have proven to be a powerful tool for optimization of dense array codes. In particular, their ability to tile imperfectly nested loops has provided dramatic speedups by countering limits of memory or network bandwidth. Unfortunately, certain codes, including RNA secondary-structure prediction codes, cannot be tiled effectively using the standard tiling algorithm used with polyhedral techniques. We have developed a more general variant of polyhedral tiling. It can be applied to loop nests that we consider “mostly tileable”. Mostly-tileable loop nests are nests for which classic tiling is prevented by an asymptotically insignificant number of iterations. Our tiling algorithm follows directly from this definition: we peel the problematic iterations of the loop nest and apply classic tiling only to the remaining iterations. We have applied our algorithm by hand to Nussinov’s algorithm for RNA secondary-structure prediction, and more recently developed a ISCC script that derives the transformation from the dependence structure of the code and then performs the transformation. The optimized code is dramatically faster than the un-tiled code, or codes in which only the outer loops are tiled. In future work, we plan to apply our technique to the more challenging codes such as Zuker et. al.’s more recent algorithms for RNA secondarystructure prediction, and seek other important “mostlytileable” loop nests. We have not yet explored the performance impact of these tilings on multi-core systems. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://perso.ens-lyon.fr/christophe.alias/evalM2/impact2015-wonnacott.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
