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 MapReduce. The experimental results demonstrate that PBTS estimates the cost close to the optimal value.
워크플로우 기술은 기타 과학 분야 연구자들이 대규모 분산 응용프로그램을 구현하기 위한 방법으로 널리 사용되고 있다. 다양한 워크플로우 관리 시스템들이 개발되어 워크플로우 기반으로 작성된 응용프로그램을 손쉽게 자동으로 실행시켜주는 역할을 한다. 그와 동시에 자원 제공 기술의 발달로 사용자는 전용 컴퓨터가 없이도 자신이 원하는 시간에 원하는 양의 컴퓨팅 자원을 동적으로 할당받아 사용할 수 있게 되었다. 대규모 워크플로우 기반 응용프로그램을 동적이고 탄력적인 컴퓨팅 자원위 에서 실행시키기 위해서는 비용도 최소화 하고 자원의 활용률도 최대화 하는 최적의 자원양을 알아야 한다. 본 논문에서는 워크플로우를 주어진 제한시간 내에 완료하기 위해 필요한 최소의 자원량을 추정해주는 BTS (Balanced Time Scheduling) 알고리즘을 제안한다. BTS는 언어 및 플랫폼 독립적으로 설계되어 어떤 워크플로우 관리 시스템 및 자원 공급 시스템과도 연동되어 쓰일 수 있다. 다수의 워크플로우를 바탕으로 한 실험을 통해 BT를 통해 구한 자원량이 이론적인 최적값에 근접하며, 알고리즘의 수행시간이 아주 큰 워크플로우에도 수백초에 불과하다는 것을 입증하였다.
그러나, BTS는 클라우드 컴퓨팅처럼 자원량을 탄력적으로 변화시킬 수 있는 환경을 제대로 반영하지 못한다는 단점이 있다. 그래서, 그점을 보완한 PBTS (Partitioned Balanced Time Scheduling) 알고리즘도 함께 제안하였다. PBTS는 워크플로우를 주어진 시간내에 완료하기 위해 각 시간단위마다 자원량을 어떻게 조정해야 하는지를 결정한다. 실험을 통해 PBTS를 사용했을 경우에 발생하는 비용이 최소값에 근접하다는 것을 확인하였다. 또한, 제 실행중에 발생한 작업의 늦은 수행을 처리하여 제한시간 초과를 가능한 피할 수 있게 하려면 어떤 기능을 PBTS에 추가해야 하는지도 제안하였다.
