AVOIDING DUPLICATED COMPUTATION TO IMPROVE THE PERFORMANCE OF PFSP ON CUDA GPUSAVOIDING DUPLICATED COMPUTATION TO IMPROVE THE PERFORMANCE OF PFSP ON CUDA GPUS

Author : Chao-Chin Wu

Affiliation : Department of Computer Science and Information Engineering, National Changhua University of Education

Country : Taiwan

Category : Computer Science & Information Technology

Volume, Issue, Month, Year : 6, 7, November, 2016

ABSTRACT 

Graphics Processing Units (GPUs) have been emerged as powerful parallel compute platforms for various application domains. A GPU consists of hundreds or even thousands processor cores and adopts Single Instruction Multiple Threading (SIMT) architecture. Previously, we have proposed an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU by using a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Based on the research result, this paper proposes another approach that further improves the performance by avoiding duplicated computation among threads, which is incurred when any two permutations have the same prefix. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 1.5 times faster than another GPU implementation proposed by Czapiński and Barnes.  

KEYWORDS 

GPU, CUDA, Parallel algorithm, Tabu Search, Permutation Flowshop Scheduling Problem  

For More Details : https://airccj.org/CSCP/vol6/csit65402.pdf