Near-Optimal Scheduling of Synchronous Data-Flow Graphs by Exact Calculation of Inter-Processor Communication Costs

; p j ) the earliest time, when all input data for vertex v i are available at processor p j . The algorithm assigns v i to the processor p j that maximises DL. In (1) DA(v i ; p j ) characterizes interprocessor communication cost and represents the earliest possible time to start the computation of v i with respect to communication. The common estimation which will be used as reference assumes that the difference between DA(v i ; p j ) and the time when all ancestor tasks of v i are finished is equal to the maximal product of the amount of data to be transferred and the number of hops between the two communicating processors. This approach will be compared to the exact calculation of interprocessor communication costs by software ro