An ILP Formulation for the Task Graph Scheduling Problem Tailored to Bi-dimensional Reconfigurable Architectures

This work proposes an exact ILP formulation for the task scheduling problem on a 2D dynamically and partially reconfigurable architecture. Our approach takes physical constraints of the target device that are relevant for reconfiguration into account. Specifically, we consider the limited number of reconfigurators, which are used to reconfigure the device. This work also proposes a reconfiguration-aware heuristic scheduler, which exploits configuration prefetching, module reuse, and anti-fragmentation techniques. We experimented with a system employing two reconfigurators. This system can be easily implemented using standard FPGAs. Our proposed ILP model can lead to an overall improvement close to 30% compared to other approaches in literature while the heuristic scheduler obtains the optimal schedule length on 60% of the considered instances.