Date Added: Oct 2009
Many computation kernels that analyze large data streams can be accelerated by converting their recurrences to parallel systolic arrays. Application domains such as bioinformatics seek to minimize the total time to analyze a large set of discrete small inputs. While traditional methods for array synthesis produce a single most efficient array design, modern computational platforms support fast runtime reconfiguration that can choose among a collection of arrays optimized for different input characteristics, such as input size. In this paper, the authors give dynamic programming algorithms to efficiently select a few array implementations from a large set of candidates so as to minimize total execution time on a dataset with a known distribution of input sizes.