Systolic processing for dynamic programming problems
We investigate systolic processing for problems formulated in dynamic programming. These problems are classified as monadic-serial, polyadic- serial, monadic-nonserial, and polyadic-nonserial. Problems in serial formulations can be implemented easily in systolic arrays; however, nonserial problems may have to be transformed into a serial one before an efficient implementation can be found. A monadic-serial dynamic programming problem can be solved as the search of an optimal path in a multistage graph and can be computed as a string of matrix multiplications. Three efficient systolic-array designs are presented. A polyadic-serial dynamic programming problem can be solved by either a divide-and-conquer algorithm or the search of optimal solutions in a serial AND/OR-graph. We have evaluated the asymptotically optimal architecture for divide-and-conquer algorithms and have developed efficient methods of mapping a regular AND/OR-graph into systolic arrays. Cases are studied for transforming a problem in a nonserial formulation into a serial one.
- A new algorithm for the solution of the secondary optimization problem in non-serial dynamic programming
- Branch-and-Bound Strategies for Dynamic Programming
- Dynamic Programming as Graph Searching: An Algebraic Approach
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Finite-State Processes and Dynamic Programming
- scientific article; zbMATH DE number 3174053 (Why is no real title available?)
- scientific article; zbMATH DE number 3657150 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3543634 (Why is no real title available?)
- scientific article; zbMATH DE number 3334757 (Why is no real title available?)
- Minimizing the Number of Operations in Certain Discrete-Variable Optimization Problems
- Nonserial dynamic programming
- Optimal Sorting Algorithms for Parallel Computers
- Solvable classes of discrete dynamic programming
- The Design of Optimal Systolic Arrays
- The Power of Dominance Relations in Branch-and-Bound Algorithms
- A high level dynamic programming algorithm for processing nonserial looped systems
- A systolic algorithm for dynamic programming
- Mapping dynamic programming onto modular linear systolic arrays
- scientific article; zbMATH DE number 3958722 (Why is no real title available?)
- Systolic algorithms for the dynamic programming problem
- Systolic algorithms for some scheduling and graph problems
- Mapping dynamic programming onto a linear systolic array
This page was built for publication: Systolic processing for dynamic programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099090)
