PCP-B~2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications

摘要

Service-oriented computing becomes an attractive environment for executing scientific workflow applications. It enables these applications to use resources in a pay-as-you-go model. However, it also challenges traditional best-effort workflow scheduling strategies, that only focus on minimizing schedule length. One of the most challenging problem is to optimize workflow execution time under QpS constraint of budget. To solve this problem, we propose a heuristic algorithm of PCP-B~2. A PCP-wise budget distribution mechanism is proposed to balance budget among partial critical paths according to their sequential or parallel structure nature. The budget distribution mechanism is implemented using binary search method. Moreover, a partially rescheduling mechanism is designed to further tune budget distribution. Simulation experiments using five well-known scientific workflow applications show that PCP-B~2 algorithm is efficient in scheduling pipeline structured workflows, and performs better than other budget constrained scheduling algorithms on average. The time complexity of PCP-B~2 is O(log |RT | |T |~3), where |RT| denotes the number of resource type, and |T| denotes the total number of workflow task. This time complexity ensures that the proposed algorithm is able to schedule large scale workflows quickly.