Optimal Simultaneous Scheduling, Binding and Routing for Processor-Like Reconfigurable Architectures
Janina A. Brenner, Jan T. van der Veen, Sándor P. Fekete, J. Filho, Wolfgang Rosenstiel · 2006
We discuss the problem of simultaneously scheduling, binding and routing a given data flow graph to a coarse-grain architecture consisting of identical processing elements (PEs) that are connected by a nearest-neighbour mesh-like interconnection network. While there are heuristics trying to solve this problem, we develop the first exact method based on integer linear programming. This allows us to achieve provably optimal solutions for two different objective functions, for small to medium instances. In addition, we describe a heuristic that seems to outperform all other known heuristics