A Genetic Approach to the Overlapped Scheduling of Iterative Data-Flow Graphs for Target Architectures with Communication Delays
Erwin Bonsma, Sabih H. Gerez · University of Twente Research Information · 1997
This paper presents a method to solve the overlapped fully-static multiprocessor scheduling problem. An iterative data-flow graph (IDFG) is mapped on a target architecture that allows finegrain parallelism. The goal is the minimization of the iteration period. The method can deal with nonzero delay times to communicate data between processors as well as with link capacities in the interconnection network. Excellent results for benchmark IDFGs have been obtained by the method that consists of three layers, each concentrating on a different aspect of the optimization problem. I. Introduction An algorithm that contains computations that can be executed simultaneously, offers possibilities of exploiting the parallelism present by implementing it on appropriate hardware such as a multiprocessor system. The class of algorithms considered in this paper is limited to algorithms that can be represented by homogeneous synchronous data-flow graphs [1], also called iterative data-flow graphs (ID...