Plug-and-Play Dynamic Programming for Parallel Execution and Benchmarking

This paper presents the first comprehensive implementation and experimental evaluation of a modular, plug-and-play Dynamic Programming (DP) framework that bridges the gap between theoretical recursion and practical multi-core execution. We extend the theoretical PPDP framework with a complete C++ implementation that enables systematic exploration of all possible DP tabulation orderings—a significant contribution that demonstrates the framework’s practical utility. Our implementation includes three core solving interfaces: dp_solve for sequential execution, dp_tile_solve for tiled computation, and dp_dag_solve for parallel execution via dynamic Directed Acyclic Graph (DAG) scheduling. Through extensive experiments on two high-core platforms (Intel Xeon Gold 6252 and AMD EPYC 7Y83), we demonstrate unprecedented scalability: achieving up to 137x speedup on the cut-rod problem using 128 cores, significantly outperforming existing OpenMP-based approaches that typically saturate at 16–32 cores with 6–10x speedup. Our framework enables comprehensive evaluation of different parallelization configurations, revealing that optimal performance depends on architecture-specific factors including tiling strategies, in-tile traversal order, and memory layout. The implementation successfully demonstrates the framework’s educational value by making DP algorithm design more accessible through pattern-oriented rather than code-centric approaches, while simultaneously achieving state-of-the-art performance on classical problems including Longest Common Subsequence, Matrix Chain Multiplication, and the Cut-Rod problem.