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 ofncoarse-grained tasks ona linear array ofkreconfigurable 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 innand compute optimal solutions. GPRM can be exponential inkbut is nevertheless practical becausekis 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.

[学科分类] 电子、光学、磁材料