An efficient GPU-based parallel tabu search algorithm for hardware/software co-design |
| |
Authors: | Neng HOU Fazhi HE Yi ZHOU Yilin CHEN |
| |
Affiliation: | 1. School of Computer Science, Wuhan University,Wuhan 430072, China2. School of Computer Science, Yangtze University, Jingzhou 434023, China3. School of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081, China |
| |
Abstract: | Hardware/software partitioning is an essential step in hardware/software co-design. For large size problems, it is difficult to consider both solution quality and time. This paper presents an efficient GPU-based parallel tabu search algorithm (GPTS) for HW/SW partitioning. A single GPU kernel of compacting neighborhood is proposed to reduce the amount of GPU global memory accesses theoretically. A kernel fusion strategy is further proposed to reduce the amount of GPU global memory accesses of GPTS. To further minimize the transfer overhead of GPTS between CPU and GPU, an optimized transfer strategy for GPU-based tabu evaluation is proposed, which considers that all the candidates do not satisfy the given constraint. Experiments show that GPTS outperforms state-of-the-art work of tabu search and is competitive with other methods for HW/SW partitioning. The proposed parallelization is significant when considering the ordinary GPU platform. |
| |
Keywords: | hardware/software co-design hardware/software partitioning graphics processing unit GPU-based parallel tabu search single kernel implementation kernel fusion strategy optimized transfer strategy |
|
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |