Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2020, Vol. 14 Issue (5) : 145316    https://doi.org/10.1007/s11704-019-8184-3
RESEARCH ARTICLE
An efficient GPU-based parallel tabu search algorithm for hardware/software co-design
Neng HOU1,2, Fazhi HE1(), Yi ZHOU3, Yilin CHEN1
1. School of Computer Science, Wuhan University,Wuhan 430072, China
2. School of Computer Science, Yangtze University, Jingzhou 434023, China
3. School of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081, China
 Download: PDF(971 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Fazhi HE   
Just Accepted Date: 19 August 2019   Issue Date: 17 March 2020
 Cite this article:   
Neng HOU,Fazhi HE,Yi ZHOU, et al. An efficient GPU-based parallel tabu search algorithm for hardware/software co-design[J]. Front. Comput. Sci., 2020, 14(5): 145316.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-019-8184-3
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I5/145316
1 G De Michell, R K Gupta. Hardware/software co-design. Proceedings of the IEEE, 1997, 85(3): 349–365
https://doi.org/10.1109/5.558708
2 W Wolf . A decade of hardware/software co-design. Computer, 2003, 6(4): 38–43
https://doi.org/10.1109/MC.2003.1193227
3 J Teich. Hardware/software co-design: the past, the present, and predicting the future. Proceedings of the IEEE, 2012, 100: 1411–1430
https://doi.org/10.1109/JPROC.2011.2182009
4 A Ouyang, X Peng, J Liu, A Sallam. Hardware/software partitioning for heterogeneous MPSoC considering communication overhead. International Journal of Parallel Programming, 2017, 45(4): 899–922
https://doi.org/10.1007/s10766-016-0466-x
5 N Hou, X Yan, F He. A survey on partitioning models, solution algorithms and algorithm parallelization for hardware/software co-design. Design Automation for Embedded Systems, 2019, 23(1–2): 57–77
https://doi.org/10.1007/s10617-019-09220-7
6 W Shi, J Wu, S Lam, T Srikanthan. Algorithms for bi-objective multiple-choice hardware/software partitioning. Computers & Electrical Engineering, 2016, 50: 127–142
https://doi.org/10.1016/j.compeleceng.2016.01.006
7 R P Dick, D L Rhodes, W Wolf. TGFF: task graphs for free. In: Proceedings of the 6th International Workshop on Hardware/Software Codesign. 1998, 97–101
https://doi.org/10.1145/278241.278309
8 J Henkel , R Ernst. An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Transactions on Very Large Scale Integration Systems, 2001, 9(2): 273–289
https://doi.org/10.1109/92.924041
9 G Jiang, J Wu, S Lam, T Srikanthan, J Sun. Algorithmic aspects of graph reduction for hardware/software partitioning. The Journal of Supercomputing, 2015, 71(6): 2251–2274
https://doi.org/10.1007/s11227-015-1381-4
10 P Arató, S Juhász, Z Mann, A Orbán, D Papp. Hardware-software partitioning in embedded system design. In: Proceedings of IEEE International Symposium on Intelligent Signal Processing. 2003, 197–202
11 P Arató, Z Mann, A Orbán. Algorithmic aspects of hardware/software partitioning. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1): 136–156
https://doi.org/10.1145/1044111.1044119
12 Y Zhou, F He, N Hou, Y Qiu. Parallel ant colony optimization on multicore SIMD CPUs. Future Generation Computer Systems, 2018, 79(2): 473–487
https://doi.org/10.1016/j.future.2017.09.073
13 R Wang, W Hung, G Yang, X Song. Uncertainty model for configurable hardware/software and resource partitioning. IEEE Transactions on Computers, 2016, 66(10): 3217–3223
https://doi.org/10.1109/TC.2016.2519895
14 X Yan, F He, N Hou, H Ai. An efficient particle swarm optimization for large scale hardware/software co-design system. International Journal of Cooperative Information Systems, 2018, 27(1): 1741001
https://doi.org/10.1142/S0218843017410015
15 A Trindade, L Cordeiro. Applying SMT-based verification to hardware/ software partitioning in embedded systems. Design Automation for Embedded Systems, 2016, 20(1): 1–19
https://doi.org/10.1007/s10617-015-9163-z
16 H Li, F He, X Yan. IBEA-SVM: an indicator-based evolutionary algorithm based on pre-selection with classification guided by SVM. Applied Mathematics—A Journal of Chinese Universities, 2019, 34(1): 1–26
https://doi.org/10.1007/s11766-019-3706-1
17 J Luo, F He, J. YongAn efficient and robust bat algorithm with fusion of opposition-based learning and whale optimization algorithm. Intelligent Data Analysis, 2020, 24(3): 500–519
18 J Yong, F He, H Li, W Zhou. A novel bat algorithm based on cross boundary learning and uniform explosion strategy. Applied Mathematics—A Journal of Chinese Universities, 2019, DOI: 10.1007/s11766-019-3714-1
https://doi.org/10.1007/s11766-019-3714-1
19 R Gupta, G Micheli. Hardware-software co-synthesis for digital systems. IEEE Design & Test of Computers, 1993, 10(3): 29–41
https://doi.org/10.1109/54.232470
20 R Ernst, J Henkel, T Benner. Hardware- software co-synthesis for microcontrollers. IEEE Design & Test of Computers, 1993, 10(4): 64–75
https://doi.org/10.1109/54.245964
21 R Dick, N Jha. MOGAC: a multi-objective genetic algorithm for hardware-software co-synthesis of distributed embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(10): 920–935
https://doi.org/10.1109/43.728914
22 G Wang, W Gong, R Kastner. Application partitioning on programmable platforms using the ant colony optimization. Journal of Embedded Computing, 2006, 2(1): 119–136
23 F Ferrandi, P Lanzi, C Pilato, D Sciuto, A Tumeo. Ant colony optimization for mapping, scheduling and placing in reconfigurable systems. In: Proceedings of IEEE NASA/ESA Conference on Adaptive Hardware and Systems. 2013, 47–54
https://doi.org/10.1109/AHS.2013.6604225
24 M Koudil, K Benatchba , A Tarabet. Using artificial bees to solve partitioning and scheduling problems in co-design. Applied Mathematics and Computation, 2007, 186(2): 1710–1722
https://doi.org/10.1016/j.amc.2006.08.166
25 M Abdelhalim, S Habib. An integrated high-level hardware/software partitioning methodology. Design Automation for Embedded Systems, 2011, 15(1): 19–50
https://doi.org/10.1007/s10617-010-9068-9
26 K Garg, Y Aung, S Lam. Knapsim-run-time efficient hardwaresoftware partitioning technique for FPGAs. In: Proceedings of the 28th IEEE International Conference on System-on-Chip. 2015, 64–69
https://doi.org/10.1109/SOCC.2015.7406912
27 Y Zhang, W Luo, Z Zhang, B Li, X Wang. A hardware/software partitioning algorithm based on artificial immune principles. Applied Soft Computing, 2008, 8(1): 383–391
https://doi.org/10.1016/j.asoc.2007.03.003
28 Y Jiang, H Zhang, X Jiao, X Song, W Hung, M Gu, J Sun. Uncertain model and algorithm for hardware/software partitioning. In: Proceedings of IEEE Computer Society Annual Symposium on VLSI. 2012, 243–248
https://doi.org/10.1109/ISVLSI.2012.14
29 G Li , J Feng, C Wang, J Wang. Hardware/software partitioning algorithm based on the combination of genetic algorithm and tabu search. Engineering Review, 2014, 34(2): 151–160
30 X Yan, F He, Y Chen. A novel hardware/software partitioning method based on position disturbed particle swarm optimization with invasive weed optimization. Journal of Computer Science and Technology, 2017, 32(2): 340–355
https://doi.org/10.1007/s11390-017-1714-2
31 A Kalavade, P Subrahmanyam. Hardware/software partitioning for multi-function systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(9): 819–837
https://doi.org/10.1109/43.720318
32 N Govil, R Shrestha, S Chowdhury. PGMA: an algorithmic approach for multi-objective hardware software partitioning. Microprocessors and Microsystems, 2017, 54: 83–96
https://doi.org/10.1016/j.micpro.2017.09.002
33 A Farahani, M Kamal, M Salmani-Jelodar. Parallel genetic algorithm based HW/SW partitioning. In: Proceedings of International Symposium on Parallel Computing in Electrical Engineering. 2006, 337–342
34 Y Wu, H Zhang, H Yang. Research on parallel HW/SW partitioning based on hybrid PSO algorithm. In: Proceedings of International Conference on Algorithms and Architectures for Parallel Processing. 2009, 449–459
https://doi.org/10.1007/978-3-642-03095-6_43
35 Y Pan, F He, H Yu, H Li. Learning adaptive trust strength with user roles of truster and trustee for trust-aware recommender systems. Applied Intelligence, 2019, DOI: 10.1007/s10489-019-01542-0
https://doi.org/10.1007/s10489-019-01542-0
36 X Lv, F He, W Cai, Y Cheng. An optimized RGA supporting selective undo for collaborative text editing systems. Journal of Parallel and Distributed Computing, 2019, 132: 310–330
https://doi.org/10.1016/j.jpdc.2019.05.005
37 K Li, F He, H Yu. Robust visual tracking based on convolutional features with illumination and occlusion handing. Journal of Computer Science and Technology, 2018, 33(1): 223–236
https://doi.org/10.1007/s11390-017-1764-5
38 H Yu, F He, Y Pan. A novel region-based active contour model via local patch similarity measure for image segmentation. Multimedia Tools and Applications, 2018, 77(18): 24097–24119
https://doi.org/10.1007/s11042-018-5697-y
39 T Van Luong, N Melab, E Talbi. GPU computing for parallel local search meta-heuristic algorithms. IEEE Transactions on Computers, 2013, 62(1): 173–185
https://doi.org/10.1109/TC.2011.206
40 Y Zhou, F He, Y Qiu. Dynamic strategy based parallel ant colony optimization on GPUs for TSPs. Science China Information Sciences, 2017, 60(6): 068102.
https://doi.org/10.1007/s11432-015-0594-2
41 W Zhu, J Curry, A Marquez. SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration. International Journal of Production Research, 2010, 48(4): 1035–1047
https://doi.org/10.1080/00207540802555744
42 K Wei, X Sun, H Chu, C Wu. Reconstructing permutation table to improve the tabu search for the PFSP on GPU. The Journal of Supercomputing, 2017, 73(11): 4711–4738
https://doi.org/10.1007/s11227-017-2041-7
43 L Bukata, P Šucha, Z Hanzálek. Solving the resource constrained project scheduling problem using the parallel tabu search designed for the CUDA platform. Journal of Parallel and Distributed Computing, 2015, 77: 58–68
https://doi.org/10.1016/j.jpdc.2014.11.005
44 N Hou, F He, Y Chen, Y Zhou. An adaptive neighborhood taboo search on GPU for hardware/software co-design. In: Proceedings of the 20th International Conference on Computer Supported Cooperative Work in Design. 2016, 239–244
https://doi.org/10.1109/CSCWD.2016.7565995
45 N Hou, F He, Y Zhou, H Ai. A GPU-based tabu search for very large hardware/software partitioning with limited resource usage. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2017, 11(5): JAMDSM0060
https://doi.org/10.1299/jamdsm.2017jamdsm0060
46 J Wu, T Srikanthan, G Chen. Algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Transactions on Computers, 2010, 59(4): 532–544
https://doi.org/10.1109/TC.2009.173
47 J Wu, P Wang, S Lam, T Srikanthan. Efficient heuristic and tabu search for hardware/software partitioning. The Journal of Supercomputing, 2013, 66(1): 118–134
https://doi.org/10.1007/s11227-013-0888-9
48 Z Chen, J Wu, G Song, J Chen. Noderank: an efficient algorithm for hardware/software partitioning. Chinese Journal of Computers, 2013, 36(10): 2033–2040
https://doi.org/10.3724/SP.J.1016.2013.02033
49 H Quan, T Zhang, Q Liu, J Guo, X Wang, R Hu. Comments on algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Transactions on Computers, 2014, 4(63): 1055–1056
https://doi.org/10.1109/TC.2012.174
50 M Billeter, O Olsson, U Assarsson. Efficient stream compaction on wide SIMD many-core architectures. In: Proceedings of the Conference on High Performance Graphics. 2009, 159–166
https://doi.org/10.1145/1572769.1572795
51 N Wilt. The Cuda Handbook: a Comprehensive Guide to GPU Programming. Pearson Education, 2013
52 K Gupta, J Stuart, J Owens. A study of persistent threads style GPU programming for GPGPU workloads. In: Proceedings of Innovative Parallel Computing. 2012, 1–14
https://doi.org/10.1109/InPar.2012.6339596
53 M Guthaus, J Ringenberg, D Ernst, T Austin, T Mudge, R Brown. MiBench: a free, commercially representative embedded benchmark suite. In: Proceedings of IEEE International Workshop on Workload Characterization. 2001, 3–14
54 Y Pan, F He, H Yu. A novel enhanced collaborative autoencoder with knowledge distillation for top-n recommender systems. Neurocomputing, 2019, 332: 137–148
https://doi.org/10.1016/j.neucom.2018.12.025
55 S Zhang, F He, W Ren, J Yao. Joint learning of image detail and transmission map for single image dehazing. The Visual Compute, 2018, DOI: 10.1007/s00371-018-1612-9
https://doi.org/10.1007/s00371-018-1612-9
56 X Chen, F He, H Yu. A matting method based on full feature coverage. Multimedia Tools and Applications, 2019, 78(9): 11173–11201
https://doi.org/10.1007/s11042-018-6690-1
57 H Yu, F He, Y Pan. A novel segmentation model for medical images with intensity inhomogeneity based on adaptive perturbation. Multimedia Tools and Applications, 2019, 78(9), 11779–11798
https://doi.org/10.1007/s11042-018-6735-5
58 F Fang, M Yi, , H Feng, S Hu, C Xiao. Narrative collage of I mage collections by scene graph recombination. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(9): 2559–2572
https://doi.org/10.1109/TVCG.2017.2759265
59 Y Wu, F He, D Zhang, X Li. Service-oriented feature-based data exchange for cloud-based design and manufacturing. IEEE Transactions on Services Computing, 2018, 11(2): 341–353
https://doi.org/10.1109/TSC.2015.2501981
60 Y Pan, F He, H Yu. A correlative denoising autoencoder to model social influence for top-N recommender system. Frontiers of Computer Science, 2020, 14(3): 143301
https://doi.org/10.1007/s11704-019-8123-3
61 X Lv, F He, X Yan, Y Wu, Y Cheng. Integrating selective undo of feature-based modeling operations for real-time collaborative CAD systems. Future Generation Computer Systems, 2019, 100: 473–497
https://doi.org/10.1016/j.future.2019.05.021
62 K Li, F He, H Yu, X Chen. A parallel and robust object tracking approach synthesizing adaptive Bayesian learning and improved incremental subspace learning. Frontiers of Computer Science, 2019, 13(5): 1116–1135
https://doi.org/10.1007/s11704-018-6442-4
63 L Yang, Q Yan, Y Fu, C Xiao. Surface reconstruction via fusing sparsesequence of depth images. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(2): 1190–1203
https://doi.org/10.1109/TVCG.2017.2657766
[1] Article highlights Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed