Overlapped Scheduling of Fine-Grain 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 static multiprocessor scheduling problem. An overlapped iterative data-flow graph (IDFG) is mapped on a target architecture that allows fine-grain parallelism. The goal is the optimization of the iteration period. The method can deal with nonzero delay times to communicate data between processors as well as with given link capacities in the interconnection network. The method consists of three layers. At the highest layer, a genetic algorithm generates different permutations of the operations in the IDFG. At the next layer, a "global scheduling heuristic" uses a permutation of all operations to guide the choices made by a greedy algorithm. Link occupancy is not directly taken into account at this layer. This is done at the lowest layer by a "black-box algorithm" that has the most detailed knowledge of the hardware, but can only make local modifications to a given schedule by inserting cycles if necessary. Experimental results show th...