SIMPLE AND STRAIGHTFORWARD APPROACH TO STATIC TASK SCHEDULING IN A HOMOGENEOUS COMPUTING ENVIRONMENT

摘要

List-based scheduling is generally accepted as an attractive approach to static task scheduling in homogeneous environment, since it pairs low complexity with good results. This paper presents a static list-scheduling algorithm: Critical Path Parent Trees (CPPT) algorithm. The CPPT algorithm divides the task graph into a set of unlisted parent-trees, the root of each parent-tree is a critical-path node. The analysis and experiments have shown that the algorithm provides very low complexity and comparable results.