A workflow is a collection of workflow tasks interconnected by workflow control structures according to the workflow process logic. Because the placement of workflow tasks and resources are distributed to several hosts in distributed workflow environments, each workflow task completes its role by accessing system resources located in any hosts and then transfers the work-flow execution control to its neighbor workflow tasks which may be located in remote hosts. If we can assign adjacent workflow tasks as close as possible and keep the workflow tasks close to their required resources, the overhead of workflow processing can be reduced significantly. In this regard, efficient distribution of workflow tasks may be considered as one of the most influential factors on high performance workflow processing. However, this has not been much addressed in the literature so far.
In this thesis, we propose an efficient workflow task allocation method called GM-WTA which is based on the multilevel graph partitioning. This method can improve the performance of workflow processing by minimizing the remote communication costs occurred during workflow execution. The various experimental results show its efficiency compared to the previous methods.
워크플로우는 자동화 및 전산화 된 업무 프로세스로서 워크플로우 제어 흐름에 따라 연결된 워크플로우 작업들로 구성된다. 분산 워크플로우 시스템에는 지리적으로 분산된 여러 호스트들과 워크플로우 작업들에 의해서 공유되는 분산 자원들이 존재하며, 각 워크플로우 작업은 임의의 호스트에 위치하면서 워크플로우 실행시에 이들 공유 자원들을 활용하여 자신의 역할을 수행하고, 인접한 워크플로우 작업들에게 워크플로우 수행 제어를 전달한다. 만약 인접한 워크플로우 작업들을 가능한한 가까이에 위치시키고 이들 워크플로우 작업들을 수행에 필요한 분산 자원들과 가깝게 할당할 수 있다면, 불필요한 원격 호출을 줄일 수 있으므로 워크플로우의 처리 성능을 크게 향상시킬 수 있다. 따라서 효율적인 워크플로우 작업 할당은 고성능 워크플로우 처리에 가장 중요한 요소가 될 수 있지만, 이에 대한 기존의 연구는 미흡한 상황이다.
본 논문에서는 다단계 그래프 분할을 활용한 효율적인 워크플로우 작업 할당 방법인 GM-WTA를 제안한다. GM-WTA는 워크플로우를 수행하는 동안의 원격 통신 비용을 최소화하여 워크플로우의 처리 성능을 향상시킬 수 있다. 부가적으로 기존의 방법들과의 다양한 비교 실험을 통해 제안된 방법의 효율성을 검증한다.