Parallel Dynamic Programming I
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 09: Parallel Dynamic Programming I
This week establishes the framework for parallel DP by first examining sequential DP solutions and explicitly identifying data dependencies that constrain parallel execution. The core topic is the parallelization of the All-Pairs Shortest Path problem using the DP formulation, analyzing how the computational mesh can be mapped onto processors and how data must be communicated in a systolic or pipelined fashion to maintain correctness.
Learning Outcomes
Learning Outcomes
The principles of optimal substructure and overlapping subproblems are understood as foundations for identifying parallel opportunities in dynamic programming.
The visualization of dynamic programming dependencies as directed acyclic graphs (DAGs) is applied to explain wavefront parallelism.
The mapping of the Floyd–Warshall algorithm onto two-dimensional processor grids and systolic arrays is analyzed in terms of communication efficiency and scalability.
Topic Outline
Topic Outline
Handout: Parallel Dynamic Programming I*
When Dependencies Find Their Rhythm
Fundamentals of Dynamic Programming (DP)
Core DP Principles and Parallel Opportunities
Dependency Graphs and Wavefronts
All-Pairs Shortest Path (APSP) – DP Formulation
Floyd-Warshall on a 2D Grid
Systolic Arrays and Pipelined Communication
From Waves to Patterns of Optimization
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
Floyd-Warshall Algorithm (Original Formulation)
Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.
Systolic Arrays and Pipelined DP
Kung, H. T., & Leiserson, C. E. (1979). Systolic arrays (for VLSI). Sparse Matrix Proceedings 1978, 256–282.
General Parallel DP and Scalability
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.
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 09: Parallel Dynamic Programming I
Page updated
Report abuse