A GPU-based Parallel Ant Colony Algorithm for Scientific Workflow Scheduling

Pengfei Wang, Huifang Li, Baihai Zhang
School of Automation, Beijing Institute of Technology, 5 South Zhongguancun Street, Haidian District, Beijing, 100081, China
International Journal of Grid Distribution Computing, Vol. 8, No.4, pp. 37-46, 2015


   title={A GPU-based Parallel Ant Colony Algorithm for Scientific Workflow Scheduling},

   author={Wang, Pengfei and Li, Huifang and Zhang, Baihai},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: