Systolic processing for dynamic programming problems
type: Item
instance of: scholarly article
title: Systolic processing for dynamic programming problems
zbMATH Open document ID: 0637.90098
DOI: 10.1007/BF01602094
author: Guojie Li
author: Benjamin Wah
published in: Circuits, Systems, and Signal Processing
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4039670
zbMATH Keywords: systolic processing
zbMATH Keywords: monadic-serial dynamic programming
zbMATH Keywords: optimal path in a multistage graph
MaRDI profile type: Publication
cites work: Q4091421
cites work: Optimal Sorting Algorithms for Parallel Computers
cites work: Q3292915
cites work: A new algorithm for the solution of the secondary optimization problem in non-serial dynamic programming
cites work: Nonserial dynamic programming
cites work: Minimizing the Number of Operations in Certain Discrete-Variable Optimization Problems
cites work: Dynamic Programming as Graph Searching: An Algebraic Approach
cites work: Solvable classes of discrete dynamic programming
cites work: The Power of Dominance Relations in Branch-and-Bound Algorithms
cites work: Finite-State Processes and Dynamic Programming
cites work: Q4118828
cites work: The Design of Optimal Systolic Arrays
cites work: Branch-and-Bound Strategies for Dynamic Programming
cites work: Q3856120
cites work: Dynamic Programming is Optimal for Nonserial Optimization Problems
cites work: Q5612245
full work available at URL: https://doi.org/10.1007/bf01602094
OpenAlex ID: W248980059
description: scientific article; zbMATH DE number 4039670