Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/564870.564901 | SPAA |
Keywords | Field | DocType |
memory parallel machine,parallel dynamic programming algorithm,spmd,mpi,large class,dynamic programming,general class,rna base,particular class,rna secondary structure prediction,bsp model,important problem,new parallel scheme,optimization problem,loop partitioning,multistage problem,granularity on distributed memory machines,optimal tiling,combinatorial optimization,distributed memory,dynamic programming algorithm,computer experiment,operations research,computational biology,base pair,control theory | Dynamic programming,SPMD,Computer science,Parallel computing,Algorithm,Distributed memory,Combinatorial optimization,Software portability,Base pair,Optimization problem,Traverse,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-529-7 | 8 | 0.61 |
References | Authors | |
22 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Almeida | 1 | 343 | 49.54 |
| Rumen Andonov | 2 | 269 | 24.24 |
| Daniel Gonzalez | 3 | 8 | 0.61 |
| Luz M. Moreno | 4 | 8 | 0.61 |
| Vincent Poirriez | 5 | 89 | 7.64 |
| Casiano Rodriguez | 6 | 43 | 3.36 |