A Memory-Constraint-Aware List Scheduling Algorithm for Memory-Constraint Heterogeneous Muti-Processor System

An effective scheduling algorithm is vital for the execution efficiency of applications on Heterogeneous Muti-Processor System (HMPS), especially Memory-Constraint Heterogeneous Muti-Processor System (MCHMPS). Stringent local and external memory constraints have significant impact on the execution performance of applications executed on MCHMPS, predictability is also a critical factor for task scheduling on MCHMPS. Therefore, a novel list scheduling algorithm termed Memory-constraint-aware Improved Predict Priority and Optimistic Processor Selection Scheduling (MIPPOSS), essentially a heuristic search optimization algorithm, is proposed in this paper. In MIPPOSS, a predictive approach is applied for task prioritization and processor selection, and a novel memory-constraint-aware approach is employed in the processor selection phase. MIPPOSS has polynomial complexity and produces better results for application scheduling on target architecture. Randomly generated DAGs and 3 real-world applications experiments, including Cybershake, LIGO, and Montage, show that MIPPOSS outperforms the other five competing algorithms by a large margin.