A parallel dynamic programming algorithm on a multi-core architecture Export

@inproceedings{citeulike:5689051, abstract = {Dynamic programming is an efficient technique to solve combinatorial search and optimization problem. There have been many parallel dynamic programming algorithms. The purpose of this paper is to study a family of dynamic programming algorithm where data dependence appear between non-consecutive stages, in other words, the data dependence is non-uniform. This kind of dynnamic programming is typically called nonserial polyadic dynamic programming . Owing to the non-uniform data dependence, it is harder to optimize this problem for parallelism and locality on parallel architectures. In this paper, we address the chanllenge of exploiting fine grain parallelism and locality of nonserial polyadic dynamic programming on a multi-core architecture. We present a programming and execution model for multi-core architectures with memory hierarchy. In the framework of the new model, the parallelism and locality benifit from a data dependence transformation. We propose a parallel pipelined algorithm for filling the dynamic programming matrix by decomposing the computation operators. The new parallel algorithm tolerates the memory access latency using multi-thread and is easily improved with tile technique. We formulate and analytically solve the optimization problem determing the tile size that minimizes the total execution time. The experiments on a simulator give a validation of the proposed model and show that the fine grain parallel algorithm achieves sub-linear speedup and that a potential high scalability on multi-core arichitecture.}, address = {New York, NY, USA}, author = {Tan, Guangming and Sun, Ninghui and Gao, Guang R.}, booktitle = {SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures}, citeulike-article-id = {5689051}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1248377.1248399}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1248377.1248399}, doi = {10.1145/1248377.1248399}, isbn = {978-1-59593-667-7}, keywords = {2007, algorithms, dynamic\_programming, parallelization, spaa}, location = {San Diego, California, USA}, pages = {135--144}, posted-at = {2009-08-31 13:54:14}, priority = {2}, publisher = {ACM}, title = {A parallel dynamic programming algorithm on a multi-core architecture}, url = {http://dx.doi.org/10.1145/1248377.1248399}, year = {2007} }

TY - CONF ID - citeulike:5689051 L3 - citeulike-article-id:5689051 N2 - Dynamic programming is an efficient technique to solve combinatorial search and optimization problem. There have been many parallel dynamic programming algorithms. The purpose of this paper is to study a family of dynamic programming algorithm where data dependence appear between non-consecutive stages, in other words, the data dependence is non-uniform. This kind of dynnamic programming is typically called nonserial polyadic dynamic programming . Owing to the non-uniform data dependence, it is harder to optimize this problem for parallelism and locality on parallel architectures. In this paper, we address the chanllenge of exploiting fine grain parallelism and locality of nonserial polyadic dynamic programming on a multi-core architecture. We present a programming and execution model for multi-core architectures with memory hierarchy. In the framework of the new model, the parallelism and locality benifit from a data dependence transformation. We propose a parallel pipelined algorithm for filling the dynamic programming matrix by decomposing the computation operators. The new parallel algorithm tolerates the memory access latency using multi-thread and is easily improved with tile technique. We formulate and analytically solve the optimization problem determing the tile size that minimizes the total execution time. The experiments on a simulator give a validation of the proposed model and show that the fine grain parallel algorithm achieves sub-linear speedup and that a potential high scalability on multi-core arichitecture. CY - San Diego, California, USA SN - 978-1-59593-667-7 AD - New York, NY, USA EP - 144 TI - A parallel dynamic programming algorithm on a multi-core architecture PB - ACM T2 - SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures SP - 135 KW - 2007 KW - algorithms KW - dynamic_programming KW - parallelization KW - spaa AU - Tan, Guangming AU - Sun, Ninghui AU - Gao, Guang PY - 2007/// UR - http://dx.doi.org/10.1145/1248377.1248399 ER -