A Static Scheduling Heuristic for Heterogeneous Processors

This paper presented a static scheduling heuristic called best-imaginary-level(BIL) scheduling for heterogeneous processors. The input graph is an acyclic precedence graph, where a node has different execution times on different processors. The static level of a node, or BIL, incorporates the effect of interprocessor communication (IPC) overhead and processor heterogeneity. The proposed scheduling technique is proven to produce the optimal scheduling result if the topology of the input task graph is linear. The proposed scheduling is expected to be applicable to the large span of target architectures from the network computing to the hardware/software codesign