Scheduling task chains on an array of reconfigurable FPGAs

Author

Carl Wayne Shetters

Date of Award

12-1999

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Dinesh Mehta

Committee Members

Bruce Whitehead, Don Bouldin

Abstract

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.

Recommended Citation

Shetters, Carl Wayne, "Scheduling task chains on an array of reconfigurable FPGAs. " Master's Thesis, University of Tennessee, 1999.
https://trace.tennessee.edu/utk_gradthes/10013