Parallel Dynamic Programming II
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 10: Parallel Dynamic Programming II
This second DP topic applies parallelization strategies to optimization problems with sequential dependencies, such as the Matrix-Chain Multiplication and the 0/1 Knapsack problem. The primary challenge discussed is exploiting parallelism along the anti-diagonals (waves) of the DP table, and designing blocked or pipelined schemes that minimize idle time while correctly handling the inherent data dependencies.
Learning Outcomes
Learning Outcomes
The formulation and parallelization of the Matrix-Chain Multiplication problem are understood, and the effects of blocked decomposition on locality and scalability are analyzed.
The roles of dynamic partitioning and pipelining in reducing synchronization overhead are explained and evaluated.
The mapping of the Longest Common Subsequence and related sequence-alignment algorithms onto parallel architectures is examined, with emphasis on scalability and communication efficiency.
Topic Outline
Topic Outline
Handout: Parallel Dynamic Programming II*
When Optimization Finds Its Form
2. Parallel Optimal Substructure Applications
Matrix-Chain Parallelization
Dynamic Partitioning and Pipelining
Parallel Approaches to Longest Common Subsequence
LCS: Wavefront Dependencies
Sequence Alignment Parallelism
From Optimization to Transformation
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
Readings
Readings
Parallel LCS and Sequence Alignment
Aluru, S., & Patnaik, L. M. (1995). Parallel implementation of the Longest Common Subsequence algorithm. Journal of Parallel and Distributed Computing, 26(1), 1–16.
General Parallel DP and Matrix-Chain
Thompson, C. D., & Kung, H. T. (1977). Sorting on a mesh-connected parallel computer. Communications of the ACM, 20(4), 263–270. (Provides the foundational parallel mapping ideas for 2D DP grids).
Advanced Parallel DP Techniques (Pipelining and Tiling)
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley. (Covers general principles of parallelizing DP, including blocking, tiling, and pipelining techniques).
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 10: Parallel Dynamic Programming II
Page updated
Report abuse