A Parallel BSP Algorithm for Irregular Dynamic Programming
Dynamic programming is a widely applied algorithm design technique in many areas such as computational biology and scientific computing. Typical applications using this technique are compute- intensive and suffer from long runtimes on sequential architectures. Therefore, several parallel algorithms for both fine-grained and coarse-grained architectures have been introduced. However, the commonly used data partitioning scheme can not be efficiently applied to irregular dynamic programming algorithms, i. e. dynamic programming algorithms with an uneven load density pattern. In this paper we present a tunable parallel Bulk Synchronous Parallel (BSP) algorithm for such kind of applications. This new algorithm can balance the workload among processors using a tunable block-cyclic data partitioning method and thus is capable of getting almost linear performance gains. We present a theoretical analysis and experimentally show that it leads to significant runtime savings for pairwise sequence alignment with general gap penalties using BSPonMPI on a PC cluster.
BSP Irregular Dynamic Programming Partitioning Load Balancing Scientific Computing
Malcolm Yoke Hean Low Weiguo Liu Bertil Schmidt
School of Computer Engineering, Nanyang Technological University, Singapore 639798 University of New South Wales Asia, 1 Kay Siang Road, Singapore 248922
国际会议
7th International Symposium,APPT 2007(第7届高级并行处理技术大会)
广州
英文
151-160
2007-11-22（万方平台首次上网日期，不代表论文的发表时间）