A parallel dynamic programming algorithm on a multi-core architecture

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.

REFERENCES

• 1: http://grape--dr.adm.s.u--tokyo.ac.jp/system-en.html.
• 2: http://www.cray.com/products/xmt/.
• 3: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 4: Francisco Almeida , Rumen Andonov , Daniel Gonzalez , Luz M. Moreno , Vincent Poirriez , Casiano Rodriguez, Optimal tiling for the RNA base pairing problem, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564901]
• 5: D. Bader and K. Madduri. Design and implementation of the hpcs graph analysis benchmark on symmetric multiprocessors. In The 12th International Conference on High Performance Computing (HiPC 2005), pages 465--476, 2005.
• 6: Rajesh Bordawekar , Alok Choudhary , Ken Kennedy , Charles Koelbel , Michael Paleczny, A model and compilation strategy for out-of-core data parallel programs, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-10, July 19-21, 1995, Santa Barbara, California, United States
• 7: P. G. Bradford. Efficient parallel dynamic programming. in 30th annual allerton conference on communication. In Control and Computing, pages 185--194, 1992.
• 8: Jih-H. Chen , Shu-Yun Le , Bruce A. Shapiro , Jacob V. Maizel, Optimization of an RNA folding algorithm for parallel architectures, Parallel Computing, v.24 n.11, p.1617-1634, Oct. 1998 [doi>10.1016/S0167-8191(98)00054-4 ]
• 9: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 10: J. Cuvillo, W. Zhu, Z. Hu, and G. R. Gao. Fast: A functionally accurate simulation toolset for the cyclops-64 cellular architecture. In Workshop on Modeling, Benchmarking and Simulation (MoBS), held in conjunction with the 32nd Annual International Symposium on Computer Architecture (ISCA'05), 2005.
• 11: Juan del Cuvillo , Weirong Zhu , Ziang Hu , Guang R. Gao, TiNy Threads: A Thread Virtual Machine for the Cyclops64 Cellular Architecture, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 14, p.265.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.434]
• 12: Juan del Cuvillo , Weirong Zhu , Ziang Hu , Guang R. Gao, Toward a Software Infrastructure for the Cyclops-64 Cellular Architecture, Proceedings of the 20th International Symposium on High-Performance Computing in an Advanced Collaborative Environment, p.9, May 14-17, 2006 [doi>10.1109/HPCS.2006.48]
• 13: M. Denneau and H. S. Warren. 64-bit cyclops priciples of operation. Technical report, IBM Watson Research Center, 2005.
• 14: P. Edmonds, E. Chu, and A. George. Dynamic programming on a shared memory multiprocessor. Parallel Computing, 19(1):9--22, 1993.
• 15: I. H. M. Fekete and P. Stadler. Prediction of rna base pairing posibilities for rna secondary structure. Biopolymers, 9:1105--1119, 1990.
• 16: Zvi Galil , Kunsoo Park, Parallel algorithms for dynamic programming recurrences with more than O(1) dependency, Journal of Parallel and Distributed Computing, v.21 n.2, p.213-222, May 1994 [doi>10.1006/jpdc.1994.1053 ]
• 17: A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing. Addison Wesley, 2003.
• 18: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 19: L. Guibas, H. Kung, and C. Thomson. Direct vlsi implementation of combinatorial algorithms. In Caltech Conference on VLSI, pages 509--525, 1979.
• 20: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 21: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 22: B. Louka , M. Tchuente, Dynamic programming on two-dimensional systolic arrays, Information Processing Letters, v.29 n.2, p.97-104, Sept. 30, 1988 [doi>10.1016/0020-0190(88)90036-1 ]
• 23: R. B. Lyngso and M. Zuker. Fast evaluation of internal loops in rna secondary structure prediction. Bioinformatics, 15(6), 440--445 1999.
• 24: J. Ramanujam , P. Sadayappan, Tiling multidimensional iteration spaces for nonshared memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.111-120, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125893]
• 25: B. A. Shapiro, J. C. Wu, D. Bengali, and M. J. Potts. The massively parallel genetic algorithm for rna folding: Mimd implementation and population variation. Bioinformatics, 17(2):137--148, 2001.
• 26: T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195--197, 1981.
• 27: Guangming Tan , Shengzhong Feng , Ninghui Sun, Locality and parallelism optimization for dynamic programming algorithm in bioinformatics, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188538]
• 28: Guangming Tan , Shengzhong Feng , Ninghui Sun, Load Balancing Algorithm in Cluster-based RNA secondary structure Prediction, Proceedings of the The 4th International Symposium on Parallel and Distributed Computing (ISPDC'05), p.91-96, July 04-06, 2005 [doi>10.1109/ISPDC.2005.32]
• 29: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 30: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 31: Michael Wolfe, Data dependence and program restructuring, The Journal of Supercomputing, v.4 n.4, p.321-344, 1990 [doi>10.1007/BF00129834]
• 32: Jingling Xue , Chua-Huang Huang, Reuse-driven tiling for improving data locality, International Journal of Parallel Programming, v.26 n.6, p.671-696, Dec. 1998 [doi>10.1023/A:1018734612524 ]
• 33: Wenduo Zhou , David K. Lowenthal, A Parallel, Out-of-Core Algorithm for RNA Secondary Structure Prediction, Proceedings of the 2006 International Conference on Parallel Processing, p.74-81, August 14-18, 2006 [doi>10.1109/ICPP.2006.10]
• 34: W. Zhu, Z. Hu, and G. R. Gao. Efficient fine-grain synchronization on a multi-core chip architecture: A fresh look. Technical report, CAPSL, University of Delaware, Technique Report 57.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms, Measurement, Performance

Keywords:
data dependence, dynamic programming, memory hierarchy, multi-core, scalabilitiy