Optimal tiling for the RNA base pairing problem
Francisco Almeida, Rumen Andonov, Daniel Leno González, Luz Marina Moreno, Vincent Poirriez, Casiano Rodríguez · 2002
Dynamic programming is an important combinatorial optimization technique that has been widely used in various fields such as control theory, operations research, computational biology and computer science. Many authors have described parallel dynamic programming algorithms for the family of multistage problems. More scarce is the literature for the more general class of problems where dependences appear between non-consecutive stages. Among the important problems falling in this class is the RNA base pairing problem. In this study we propose a new parallel scheme for a large class of recurrences with triangular iteration space and nonuniform dependences that includes the RNA base pairing problem. We derive two different instances of this scheme that correspond to an horizontal and a vertical traverse of the iteration domain. We develop and extend the tiling approach for this particular class. We formulate and analytically solve the optimization problem determining the tile size that minimizes the total execution time of the tiled program on a distributed memory parallel machine. Our analyze is based on the BSP model, which assures the portability of the obtained results. The computational experiments carried out on the CRAY T3E behave according to the predictions of our theoretical model.