基于Pipeline的一类动态规划并行算法

动态规划是解决组合优化问题的有效方法之一，本文基于Ｐｉｐｅｌｉｎｅ结构，提出并分析了三个相似的动态规划并行算法（求简单最短路径，求最长公共子串和解背包问题），获得了较理想的加速比、并行效率等指标，进而提出并讨论了这一类问题之动态规划并行处理的一般化思想及方法。

A CLASS OF PARALLEL DYNAMIC PROGRAMMING ALGORITHMS BASED ON PIPELINE ARCHITECTURES

Based on pipeline architectures, three similar parallel algorithms of dynamic programming for combinatorial problems (simple shortest path problem, longest common string problem and knapsack problem) are designed and analyzed in this paper. These algorithms achieve an optimal speed-up by using processor array.Furthermore, the general idea and methodology for designing the dynamic programming parallel algorithms based on pipeline architectures are presented and discussed.