Dynamic programming on a functional memory computer

✍ Scribed by A. Lew; R. Halverson Jr.

• Book ID: 104353563
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 367 KB
• Volume: 37
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(99)00138-8

✦ Synopsis

ln a previous paper [I], we described the solution of dynamic programming problems on a new class of parallel processing systems, the Hawaii Parallel Computer (HPC). The HPC has a novel architecture distinguished by its incorporation of field programmable gate arrays to evaluate expressions and by its use of a decision-table data structure to represent computer programs. As 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 execution on conventional deterministic yon Neumann computers. More recently, we designed a successor to the HPC, a "functional memory" computer, which includes constr~cts for nondeterministic computation. In this paper, we discuss how dynamic programming algorithms can be adapted to take advantage of this nondeterminism. (~) 1999 Elsevier Science Ltd. All rights reserved.