Efficiency of Various Tiling Strategies for the Zuker Algorithm Optimization

Abstract

This paper focuses on optimizing the Zuker RNA folding algorithm, a bioinformatics task with non-serial polyadic dynamic programming and non-uniform loop dependencies. The intricate dependence pattern is represented using affine formulas, enabling the automatic application of tiling strategies via the polyhedral method. Three source-to-source compilers—PLUTO, TRACO, and DAPT—are employed, utilizing techniques such as affine transformations, the transitive closure of dependence relation graphs, and space–time tiling to generate cache-efficient codes, respectively. A dedicated transpose code technique for non-serial polyadic dynamic programming codes is also examined. The study evaluates the performance of these optimized codes for speed-up and scalability on multi-core machines and explores energy efficiency using RAPL. The paper provides insights into related approaches and outlines future research directions within the context of bioinformatics algorithm optimization.

Keywords

• Zuker’s algorithm
• RNA folding
• loop tiling
• polyhedral compilers
• dynamic programming
• computational biology