Near-Optimal Scheduling of Synchronous Data-Flow Grphs by Exact Calculaton of Inter-Processor Communication Costs

摘要

Scheduling includes two major aspects: asigning tasks to processors and organising the data exchange between them. Many scheduling algorithms either neglect the costs for data exchange. consider them only for special topologies, or rely on worst case assumptions. Our aim was to optimise the mapping of synchronus data flow (SDF) grapphs onto processor networks by coupling a universal routing algorithm with an appropriate scheduling strategy. For that purpose we chose the Dynamic Level Scheduling (DLS) algorithm (1).