Efficiency of Various Tiling Strategies for the Zuker Algorithm Optimization

Piotr Blaszynski (), Marek Palkowski, Wlodzimierz Bielecki and Maciej Poliwoda
Additional contact information
Piotr Blaszynski: Faculty of Computer Science and Information Systems, West Pomeranian University of Technology, Zolnierska 49, 72210 Szczecin, Poland
Marek Palkowski: Faculty of Computer Science and Information Systems, West Pomeranian University of Technology, Zolnierska 49, 72210 Szczecin, Poland
Wlodzimierz Bielecki: Faculty of Computer Science and Information Systems, West Pomeranian University of Technology, Zolnierska 49, 72210 Szczecin, Poland
Maciej Poliwoda: Faculty of Computer Science and Information Systems, West Pomeranian University of Technology, Zolnierska 49, 72210 Szczecin, Poland

Mathematics, 2024, vol. 12, issue 5, 1-13

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/5/728/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/5/728/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:5:p:728-:d:1348695

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().