Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU

kai-cheng wei, Xue Sun, Hsun Chu, Chao-Chin Wu

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)4711-4738
Number of pages28
JournalJournal of Supercomputing
Volume73
Issue number11
DOIs
Publication statusPublished - 2017 Nov 1

Fingerprint

Permutation Flowshop
Flow Shop Scheduling
Tabu search
Tabu Search
Scheduling Problem
Table
Permutation
Scheduling
Data storage equipment
Graphics Processing Unit
Heuristic Optimization
Tabu Search Algorithm
Computing
NP-hard Problems
Metaheuristics
Computational Experiments
Execution Time
Accelerate
System Performance
Computational complexity

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture

Cite this

@article{a2764a1954cf484b8aa50267007604d2,
title = "Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU",
abstract = "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.",
author = "kai-cheng wei and Xue Sun and Hsun Chu and Chao-Chin Wu",
year = "2017",
month = "11",
day = "1",
doi = "10.1007/s11227-017-2041-7",
language = "English",
volume = "73",
pages = "4711--4738",
journal = "Journal of Supercomputing",
issn = "0920-8542",
publisher = "Springer Netherlands",
number = "11",

}

Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU. / wei, kai-cheng; Sun, Xue; Chu, Hsun; Wu, Chao-Chin.

In: Journal of Supercomputing, Vol. 73, No. 11, 01.11.2017, p. 4711-4738.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU

AU - wei, kai-cheng

AU - Sun, Xue

AU - Chu, Hsun

AU - Wu, Chao-Chin

PY - 2017/11/1

Y1 - 2017/11/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85018943248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018943248&partnerID=8YFLogxK

U2 - 10.1007/s11227-017-2041-7

DO - 10.1007/s11227-017-2041-7

M3 - Article

AN - SCOPUS:85018943248

VL - 73

SP - 4711

EP - 4738

JO - Journal of Supercomputing

JF - Journal of Supercomputing

SN - 0920-8542

IS - 11

ER -