Solving 0/1 Knapsack Problem for Light Communication SLA-Based Workflow Mapping Using CUDA
Dang Minh Quan, Laurence Tianruo Yang · 2009
Mapping and running jobs on suitable resources are the core tasks in grid computing. In the algorithm to map light communication Grid-based workflow within the SLA context, there is an operation of resolving the conflict period which is exact a 0/1 knapsack problem. When the size of the workflow is large such as in the case of mapping a group of workflows, the time to solve this problem is long and thus, makes the whole mapping process long. In this paper, we describe a way to solve this problem by exploiting the parallel computing power of graphic processing unit (GPU) with compute unified device architecture (CUDA). The experiment shows that the approach is very efficient with huge problem.