Parallel Tiled Cache and Energy Efficient Code for Zuker’s RNA Folding

In this paper, we consider Zuker’s RNA folding algorithm, which is a challenging dynamic programming task to optimize because it is resource intensive and has a large number of non-uniform dependences. We apply a previously published approach, proposed by us, to automatically tile and parallelize each loop in the Zuker RNA Folding loop nest, which is within the polyhedral model. First, for each loop nest statement, rectangular tiles are formed within the iteration space of the Zuker loop nest. Then, those tiles are corrected to honor all dependences exposed for the original loop nest. Correction is based on applying the exact transitive closure of a dependence graph. We implemented our approach as a part of the source-to-source TRACO compiler. We compare code performance and energy consumption with those obtained with the state-of-the-art PluTo compiler based on the affine transformation framework as well as with those generated by means of the cache-efficient manual method Transpose. Experiments were carried out on a modern multi-core processor to achieve the significant locality improvement and energy saving for generated code.