文献类型：期刊文献

英文题名：Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU

作者：Wei, Kai-Cheng[1];Sun, Xue[2,3];Chu, Hsun[1];Wu, Chao-Chin[1]

第一作者：Wei, Kai-Cheng

通讯作者：Wu, CC[1]

机构：[1]Natl Changhua Univ Educ, Dept Comp Sci & Informat Engn, Changhua 500, Taiwan;[2]Natl Changhua Univ Educ, Dept Elect Engn, Changhua 500, Taiwan;[3]Beijing Union Univ, Coll Automat, Beijing 100101, Peoples R China

第一机构：Natl Changhua Univ Educ, Dept Comp Sci & Informat Engn, Changhua 500, Taiwan

通讯机构：[1]corresponding author), Natl Changhua Univ Educ, Dept Comp Sci & Informat Engn, Changhua 500, Taiwan.

年份：2017

卷号：73

期号：11

起止页码：4711-4738

外文期刊名：JOURNAL OF SUPERCOMPUTING

收录：;EI(收录号：20171803636364);Scopus(收录号：2-s2.0-85018943248);WOS:【SCI-EXPANDED(收录号:WOS:000413300200004)】；

基金：We would like to express our gratitude for reviewers' valuable comments and thank the National Science Council, Taiwan, for financially supporting this research under Contract No. MOST104-2221-E-018-007.

语种：英文

外文关键词：Tabu Search; GPGPU; Parallel computing; Branch divergence; PFSP

摘要：General-purpose computing on graphics processing unit (GPGPU) has been adopted to accelerate the running of applications which require long execution time in various problem domains. Tabu Search belonging to meta-heuristics optimization has been used to find a suboptimal solution for NP-hard problems within a more reasonable time interval. In this paper, we have investigated in how to improve the performance of Tabu Search algorithm on GPGPU and took the permutation flow shop scheduling problem (PFSP) as the example for our study. In previous approach proposed recently for solving PFSP by Tabu Search on GPU, all the job permutations are stored in global memory to successfully eliminate the occurrences of branch divergence. Nevertheless, the previous algorithm requires a large amount of global memory space, because of a lot of global memory access resulting in system performance degradation. We propose a new approach to address the problem. The main contribution of this paper is an efficient multiple-loop struct to generate most part of the permutation on the fly, which can decrease the size of permutation table and significantly reduce the amount of global memory access. Computational experiments on problems according with benchmark suite for PFSP reveal that the best performance improvement of our approach is about 100%, comparing with the previous work.