Near-optimal scheduling of synchronous data-flow graphs by exact calculation of inter-processor communication costs

In this contribution we present an optimised method for mapping of data-flow graphs onto parallel processor networks. Its main advantage is the exact consideration of overhead times for data exchange within the network. Therefore, the well known Dynamic Level Scheduler has been extended by a software router which is capable of calculating communication costs for all commonly used network topologies. This task is based on a special minimal routing algorithm for reconfigurable processor networks. Comparisons between the original and our modified scheduling algorithm will show significant reduction of makespan. A possible integration of the algorithm in software environments for parallel processing will be demonstrated by means of the framework PTOLEMY