DAG Scheduling for Heterogeneous Systems Using Biogeography-Based Optimization

Efficient scheduling algorithm is critical for DAG-based applications to obtain high-performance in heterogeneous computing systems. In comparison with heuristic-based algorithms, meta-heuristic based scheduling algorithms can produce better results by searching in a guided manner. Biogeography-based optimization (BBO) is a recently proposed optimization technique which has shown less parameters, faster convergency, and superior performance than existing meta-heuristics. In this article, we introduce this novel optimization technique into the field of DAG scheduling. To reduce scheduling overhead, the proposed algorithm only encodes task mapping while using a heuristic strategy to determine task ordering. Moreover, it uses heuristic-based algorithms as baseline algorithms to obtain better results. We evaluate the BBO-based scheduling algorithm using three real world DAG-based applications under various parameter settings. The results show that the BBO-based scheduling algorithm outperforms the state-of-the-art meta-heuristic based algorithms.