8009

Solving very large instances of the scheduling of independent tasks problem on the GPU

Frederic Pinel, Bernabe Dorronsoro, Pascal Bouvry
Faculty of Science, Technology, Communications, University of Luxembourg, Luxembourg
Journal of Parallel and Distributed Computing, 2012

@article{pinel2012solving,

   title={Solving very large instances of the scheduling of independent tasks problem on the GPU},

   author={Pinel, F. and Dorronsoro, B. and Bouvry, P.},

   journal={Journal of Parallel and Distributed Computing},

   year={2012},

   publisher={Elsevier}

}

Download Download (PDF)   View View   Source Source   

716

views

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min-min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min-min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min-min heuristic when more accurate solutions are needed, at the expense of an increased runtime.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: