Pipelining in dynamic programming architectures

Novel computation techniques to achieve fine-grain pipelining in forward dynamic programming (DP) architectures are proposed. The sequential DP algorithm is proposed using fewer finer grain pipelined processors, and increased hardware efficiency is achieved by using a novel computation sequence. Look-ahead computation is used to obtain a concurrent DP algorithm, and it is used in combination with an appropriate computation sequence to achieve further pipelining in DP architectures. The finer grain pipelined architectures are mapped to ring and mesh processor arrays, and approximately the same iteration rate is achieved as the coarse-grain pipelined architectures, but with use of much less hardware. The design of interleaved architectures using multiple clocks is also outlined