Systolic processing for dynamic programming problems

In this paper 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. 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.This research was supported by National Science Foundation Grant DMC 85-19649 and Joint Services Electronics Program Contract N000014-84-C-0149.