Dynamic programming on a functional memory computer

In a previous paper [1], we described the solution of dynamic programming p roblems on a new class of parallel processing systems, the Hawaii Parallel Computer (HPC). The HPC has a novel architecture distinguished by its incor poration of field programmable gate arrays to evaluate expressions and by i ts use of a decision-table data structure to represent computer programs. A s specific examples, we showed how the HPC can be used to implement dynamic programming solutions of shortest-path and traveling-salesman problems. In that earlier implementation, we simply adapted algorithms intended for exe cution on conventional deterministic von Neumann computers. More recently, we designed a successor to the HPC, a "functional memory" computer, which i ncludes constructs for nondeterministic computation. In this paper, we disc uss how dynamic programming; algorithms can be adapted to take advantage of this nondeterminism. (C) 1999 Elsevier Science Ltd. All rights reserved.