원문정보
초록
영어
Scientific workflow scheduling problem is a combinatorial optimization problem. In the real application, the scientific workflow generally has thousands of task nodes. Scheduling large-scale workflow has huge computational overhead. In this paper, a parallel algorithm for scientific workflow scheduling is proposed so that the computing speed can be improved greatly. Our method used ant colony optimization approaches on the GPU. Thousands of GPU threads can parallel construct solutions. The parallel ant colony algorithm for workflow scheduling was implemented with CUDA C language. Scheduling problem instances with different scales were tested both in our parallel algorithm and CPU sequential algorithm. The experimental results on NVIDIA Tesla M2070 GPU show that our implementation for 1000 task nodes runs in 5 seconds, while a conventional sequential algorithm implementation runs in 104 seconds on Intel Xeon X5650 CPU. Thus, our GPU-based parallel algorithm implementation attains a speed-up factor of 20.7.
목차
1. Introduction
2. Problem Description
3. The Design and GPU Implementation of Parallel Ant Colony Algorithm
3.1. Algorithm for Scientific Workflow Scheduling
3.2. Node Selection Rules
3.3. Pheromone Update Rule
3.4. GPU-based Algorithm Implementation
4. Performance Evaluation
4.1. Experimental Settings
4.2. Experimental Results
5. Conclusions
Acknowledgements
References