An Integer Linear Programming Approach to the Overlapped Scheduling of Iterative Data-Flow Graphs for Target Architectures with Communication Delays
Sacha L. Sindorf, Sabih H. Gerez · University of Twente Research Information · 2000
Abstract — This paper considers the scheduling of homogeneous synchronous data-flow graphs also called iterative data-flow graphs (IDFGs) on a multiprocessor system. Algorithms described by such graphs consist of a core computation that is iterated “infinitely often”. The computation does not contain data-dependent decisions. All scheduling decisions for such algorithms can be taken at compile time. Fine-grain parallelism is assumed where the basic tasks are primitive operations (such as additions) and the interprocessor communication times are just a few clock cycles. Scheduling methods for such a model have recently been presented by several authors. These approaches assign operations to processors and data transfers to links at appropriate times. The work presented here extends the one reported in [16] based on integer linear programming. Optimal results to problems of reasonable size were found after acceptable computation times. I.