Estimating Resource Capacity for Time-constraint Workflows

Abstract

Workflow technologies have become a major vehicle for easy and efficient implementation of large-scale distributed applications especially in scientific domain. Workflow management systems including Pegasus, Askalon, Triana provide users with easy ways to execute workflow-based applications. In the meantime, state-of-the-art resource provisioning technologies enable users to acquire computing resources dynamically and elastically. This thesis suggests an architecture for automatic execution of large-scale workflow-based applications on dynamically and elastically provisioned computing resources. A critical challenge in integrating workflow technologies with resource provisioning technologies is to determine the right amount of resources which minimizes the financial cost and maximizes the resource utilization. This thesis introduces an algorithm named BTS (Balanced Time Scheduling), which estimates the minimum number of computing hosts required to execute workflows within a user-specified finish time. BTS is designed to be abstract so that it can be easily integrated with any resource description languages and resource provisioning systems. The experimental results, based on a number of synthetic workflows and five real application workflows, demonstrate that the BTS estimate of resource capacity approaches to the theoretical lower bound. The BTS algorithm is scalable and its turnaround time is only tens of seconds, even with huge workflows with thousands of tasks and edges.

However, BTS is limited not to handle elastic resource allocation which is common in cloud computing environment. Thus, we also suggest an improved algorithm named PBTS (Partitioned Balanced Time Scheduling) which estimates the resource capacity of each time-partition and schedule of tasks for completing a workflow within the deadline. The PBTS algorithm is designed to fit both elastic resource provisioning models such as Amazon EC2 and malleable parallel application models such as MapR...