Dynamic programming implementation on array processor architectures

Dynamic Programming (DP) applies to many signal and image processing applications including boundary following, the Viterbi algorithm, dynamic time warping, etc. This paper presents an array processor implementation of generic dynamic programming. Our architecture is a SIMD array attached to a host computer. The processing element of the architecture is based on an ASIC design opting for maximum speed-up. By adopting a torus interconnection network, a dual buffer structure, and a multilevel pipeline, the performance of the DP chip is expected to reach the order of several GOPS. The paper discusses both the dedicated hardware design and the data flow control of the DP chip and the total array.This work was supported in part by the NATO, Scientific and Environmental Affairs Division, Collaborative Research Grant SA.5-2-05(CRG.960201)424/96/JARC-501.