Efficient Hierarchical Task Scheduling on GRIDS Accounting for Computation and Communications

This chapter proposes a novel Grid-based scheduling algorithm that optimizes both computation and communications costs of workflow applications. Based on a hierarchical two-steps optimization process, a super scheduler first applies a Recursive Convex Clustering Algorithm (RCCA) that efficiently clusters tasks while minimizing communication costs. In the second step, a resource-broker assigns the generated convex sets to resources clusters. Local schedulers then optimize the makespan for the group of tasks assigned to their cluster, using a graphic processing unit (GPU)-based parallel cellular Genetic Algorithm(cGA). The performance improvement brought by this novel two-step scheduling algorithm compared to a hierarchical list-scheduling approach is empirically demonstrated on different real-world workflow applications.