Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs

This paper considers the problem of scheduling a chain of n coarse-grained tasks ona linear array of k reconfigurable FPGAs with the objective of primarily minimizingreconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms(GPRM and SPRM) that support a wide range of problem formulations and cost functionsis presented. GPRM, the more general of the two schemes, reduces the problem tocomputing a shortest path in a DAG; SPRM, the less general scheme, employs dynamicprogramming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a smallconstant. The deterministic quality of this meta algorithm and the guarantee of optimalsolutions for all of the formulations discussed make this approach a powerful alternativeto other metatechniques such as simulated annealing and genetic algorithms