Scheduling task chains on an array of reconfigurable FPGAs

Two optimal algorithmic schemes (GPRA and SPRA) for scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable PPGAs are presented. Eachscheme supports several realistic problem formulations and cost functions. GPRA, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG and requires O(nk4^k) time and O(n4^k) storage; SPRA, the less general scheme,employs dynamic programming and runs in O(n³) time. Although the complexity of GPRA is exponential in k, our experimental results show that GPRA is a practical scheme for realistic values of k.