Aggregated-DAG Scheduling for Job Flow Maximization in Heterogeneous Cloud Computing

Heterogeneous computing platforms such as Grid and Cloud computing are becoming prevalent and available online. As a result, resource management in these platforms is fundamentally critical to their global performance. Under the assumption of jobs comprised of subtasks forming DAG jobs, we focus on how to increase utilization and achieve near-optimal throughput performance on heterogeneous platforms. Our analysis and proposed algorithm are analytically derived and establish that, by aggregating multiple jobs using good scheduling, a near-optimal throughput can be achieved. Consequently, its limit is asymptotically converging to a certain value and can be written in the form of the service time of subtasks. Furthermore, our analysis shows how to explicitly compute the optimal throughput of computing systems, an important task for such a complex scheduling problem. In addition, we derive a simple super-job scheduling and show that its performance in term of throughput is better than the well-known Heterogeneous Earliest-Finish-Time (HEFT) algorithm.