Related Experiment Videos
Tuning iteration space slicing based tiled multi-core code implementing Nussinov's RNA folding.
Marek Palkowski1, Wlodzimierz Bielecki2
1West Pomeranian University of Technology, Faculty of Computer Science, Zolnierska 49, Szczecin, 71-210, Poland. mpalkowski@wi.zut.edu.pl.
BMC Bioinformatics
|January 17, 2018
Summary
This study optimizes RNA folding by using polyhedral compilation to automatically select optimal tile sizes for parallel code. This enhances computational biology algorithm performance on multi-core processors.
Area of Science:
- Computational Biology
- Bioinformatics
- Computer Science
Background:
- RNA folding is a computationally intensive bioinformatics task.
- Parallelization and code locality are crucial for RNA folding algorithms.
- Nussinov's RNA folding algorithm can be represented using the polyhedral model.
Purpose of the Study:
- To develop a method for automatically selecting optimal tile sizes and dimensions for parallel tiled code.
- To improve the performance of RNA folding algorithms through optimized parallelization.
Main Methods:
- Utilized polyhedral compilation techniques and the iteration space slicing framework.
- Generated parallel parametric tiled code by deriving an affine model for integer factors.
- Implemented the tile size selection (TSS) technique to find optimal tile parameters.
Main Results:
- Developed a parallel parametric tiled code for Nussinov's RNA folding algorithm.
- The approach successfully identifies optimal tile sizes and dimensions within a defined search space.
- Experimental results show performance improvements over existing methods for RNA strands longer than 2500.
Conclusions:
- The presented approach effectively optimizes tile size and dimension selection for parallel RNA folding code.
- The optimized code demonstrates superior performance on modern multi-core processors for large RNA strands.
- This work contributes to efficient computational biology by enhancing parallel algorithm design.