Discounts for dynamic programming with applications in VLSI processor arrays
Daniel Lopresti · 1987
Dynamic programming is a powerful technique for formulating and solving optimization problems. Because such algorithms are often computation-intensive, researchers have proposed parallel implementations for many, utilizing various general- and special-purpose computers. A number of these architectures, including custom VLSI processor arrays, do not have predetermined word-lengths. When this is the case, problems whose costs require fewer bits to represent are favored over those whose costs require more. In this dissertation, we introduce a method for transforming certain dynamic programming problems into ones which require less space and time to solve under the logarithmic cost criterion, an appropriate complexity measure for flexible word-length machines. Our mapping is based on discounts which change the costs but not the identities of optimal policies. Under the proper circumstances, the structure present in the original problem is preserved in the image so that the functional equations of dynamic programming still apply. We illustrate the practical value of the theory by demonstrating that a previously published VLSI processor array can be made asymptotically smaller and faster. The second half of this work addresses issues that arise in parallel sequence comparison. Our paradigm here is deoxyribonucleic acid (DNA) which may be considered a string over a four character alphabet. We show how a number of popular sequence matching algorithms can be mapped onto linear arrays of processors. One of these, the Princeton Nucleic Acid Comparator (P-NAC), has been fabricated, tested, and found to work perfectly. Its efficient implementation is due entirely to an application of discounts; benchmark results prove that it is several hundred times faster than a minicomputer. We conclude the thesis by providing two procedures for comparing strings of arbitrary length on an array of fixed length, a vital concern when hardware is limited.