Chapter 14. GPU Accelerated RNA Folding Algorithm
Guillaume Rizk, Dominique Lavenier and Sanjay Rajopadhye
In this chapter, we present an implementation of the main kernel in the widely used RNA folding package Unafold. Its key computation is a dynamic programming algorithm with complex dependency patterns, making it an a priori bad match for GPU computing. This study, however, shows that reordering computations in such a way to enable tiled computations and good data reuse can significantly improve GPU performance and yields good speedup compared ...