A hardware/software partitioning method based on graph convolution network
Tóm tắt
Hardware/software (HW/SW) partitioning is the crucial step in HW/SW co-design, which can significantly reduce the time-to-market and improves the performance of an embedded system. Due to that the majority of previous works have large exploration time and generate often low-quality solutions for large scale systems, we propose a fast HW/SW partitioning approach based on graph convolution network (GCN) to address this problem. To the best of our knowledge, it is a new partitioning method based on GCN which is a gradient-based optimization approach. It can aggressively speed up the partitioning process. To quantify the quality of solutions, the scheduling is integrated into the partitioning process. The experiment results show that not only does our proposed method outperform existing metaheuristics approaches in terms of the efficiency (e.g., 18
$$\times $$
faster than Kernighan–Lin algorithm for the task graphs with 1000 nodes), but it also improves the quality of HW/SW partitioning (e.g., more than 10% acceleration ratio (AR) improvement for the 1000 nodes graphs).
Tài liệu tham khảo
Abdelzaher TF, Shin KG (2000) Period-based load partitioning and assignment for large real-time applications. IEEE Trans Comput 49(1):81–87
Ahmed A, Hasan T, Abdullatif FA, Mustafa S, Rahim MSM (2019) A digital signature system based on real time face recognition. In: 2019 IEEE 9th International conference on system engineering and technology (ICSET). IEEE, pp 298–302
Arató P, Juhász S, Mann ZÁ, Orbán A, Papp D (2003, September) Hardware-software partitioning in embedded system design. In: IEEE International Symposium on Intelligent Signal Processing, 2003. IEEE, pp 197–202
Atwood J, Towsley D (2016) Diffusion-convolutional neural networks. In: Advances in neural information processing systems, pp 1993–2001
Banerjee S, Dutt N (2004, September) Efficient search space exploration for HW-SW partitioning. In: Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pp 122–127
Banerjee S, Dutt N (2004) Very fast simulated annealing for HW–SW partitioning. In: Technical Report, CECS-TR-04-17. Citeseer
Chatha KS, Vemuri R (2002) Hardware–software partitioning and pipelined scheduling of transformative applications. IEEE Trans Very Large Scale Integr (VLSI) Syst 10(3):193–208
Chen J, Zhu J, Song L (2017) Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568
Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graphs for free. In: Proceedings of the sixth international workshop on hardware/software codesign (CODES/CASHE’98). IEEE, pp 97–101
Eles P, Peng Z, Kuchcinski K, Doboli A (1997) System level hardware/software partitioning based on simulated annealing and tabu search. Des Autom Embed Syst 2(1):5–32
Ernst R, Henkel J, Benner T (1993) Hardware–software cosynthesis for microcontrollers. IEEE Des Test Comput 10(4):64–75
Guo B, Wang D, Shen Y, Liu Z (2006) Hardware–software partitioning of real-time operating systems using Hopfield neural networks. Neurocomputing 69(16–18):2379–2384
Gupta RK, De Micheli G (1993) Hardware–software cosynthesis for digital systems. IEEE Des Test Comput 10(3):29–41
Han H, Liu W, Wu J, Jiang G (2013) Efficient algorithm for hardware/software partitioning and scheduling on MPSoC. JCP 8(1):61–68
He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. In: 2016 IEEE Conference on computer vision and pattern recognition, CVPR 2016, Las Vegas, NV, USA, June 27–30. IEEE Computer Society, pp 770–778
Henkel J, Ernst R (2001) An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Trans Very Large Scale Integr (VLSI) Syst 9(2):273–289
Hou N, Yan X, He F (2019) A survey on partitioning models, solution algorithms and algorithm parallelization for hardware/software co-design. Des Autom Embed Syst 23(1–2):57–77
Huang W, Zhang T, Rong Y, Huang J (2018) Adaptive sampling towards fast graph representation learning. arXiv preprint arXiv:1809.05343
Jemai M, Dimassi S, Ouni B, Mtibaa A (2017) A metaheuristic based on the tabu search for hardware-software partitioning. Turk J Electr Eng Comput Sci 25(2):901–912
Jiang G, Wu J, Lam SK, Srikanthan T, Sun J (2015) Algorithmic aspects of graph reduction for hardware/software partitioning. J Supercomput 71(6):2251–2274
Jigang W, Chang B, Srikanthan T (2009, June) A hybrid branch-and-bound strategy for hardware/software partitioning. In: 2009 Eighth IEEE/ACIS International Conference on Computer and Information Science. IEEE, pp 641–644
Jing Y, Kuang J, Du J, Hu B (2013, May) Application of improved simulated annealing optimization algorithms in hardware/software partitioning of the reconfigurable system-on-chip. In: International Conference on Parallel Computing in Fluid Dynamics. Springer, Berlin, Heidelberg, pp 532–540
Kalavade A, Lee EA (1997) The extended partitioning problem: hardware/software mapping, scheduling, and implementation-bin selection. Des Autom Embed Syst 2(2):125–163
Kalavade A, Subrahmanyam P (1998) Hardware/software partitioning for multifunction systems. IEEE Trans Comput Aided Des Integr Circuits Syst 17(9):819–837
Kipf TN, Welling M (2016) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907
Kipf TN, Welling M (2016) Variational graph auto-encoders. arXiv preprint arXiv:1611.07308
Li G, Feng J, Wang C, Wang J (2014) Hardware/software partitioning algorithm based on the combination of genetic algorithm and tabu search. Eng Rev Međunarodni časopis namijenjen publiciranju originalnih istraživanja s aspekta analize konstrukcija, materijala i novih tehnologija u području strojarstva, brodogradnje, temeljnih tehničkih znanosti, elektrotehnike, računarstva i građevinarstva 34(2):151–160
Li Q, Han Z, Wu XM (2018) Deeper insights into graph convolutional networks for semi-supervised learning. arXiv preprint arXiv:1801.07606
Li SG, Feng FJ, Hu HJ, Wang C, Qi D (2014) Hardware/software partitioning algorithm based on genetic algorithm. JCP 9(6):1309–1315
Li Y, Hao Z, Lei H (2016) Survey of convolutional neural network. J Comput Appl 36(9):2508–2515
Li Y, Vinyals O, Dyer C, Pascanu R, Battaglia P (2018) Learning deep generative models of graphs. arXiv preprint arXiv:1803.03324
Li Y, Yu R, Shahabi C, Liu Y (2017) Diffusion convolutional recurrent neural network: data-driven traffic forecasting. arXiv preprint arXiv:1707.01926
López-Vallejo M, López JC (2003) On the hardware–software partitioning problem: system modeling and partitioning techniques. ACM Trans Des Autom Electron Syst (TODAES) 8(3):269–297
Madsen J, Grode J, Knudsen PV, Petersen ME, Haxthausen A (1997) LYCOS: the Lyngby co-synthesis system. Des Autom Embed Syst 2(2):195–235
Mann Z, Orbán A, Farkas V (2007) Evaluating the Kernighan–Lin heuristic for hardware/software partitioning. Int J Appl Math Comput Sci 17(2):249–267
Mann ZÁ, Orbán A, Arató P (2007) Finding optimal hardware/software partitions. Formal Methods Syst Des 31(3):241–263
Nair V, Hinton GE (2010, January) Rectified linear units improve restricted boltzmann machines. In: International Conference on Machine Learning, pp 807–814
Niemann R, Marwedel P (1997) An algorithm for hardware/software partitioning using mixed integer linear programming. Des Autom Embed Syst 2(2):165–193
Pornin T (2013) Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA). Internet Eng Task Force RFC 6979:1–79
Purnaprajna M, Reformat M, Pedrycz W (2007) Genetic algorithms for hardware–software partitioning and optimal resource allocation. J Syst Archit 53(7):339–354
Radulescu A, Van Gemund AJ (2002) Low-cost task scheduling for distributed-memory machines. IEEE Trans Parallel Distrib Syst 13(6):648–658
Saha D, Mitra RS, Basu A (1997, January) Hardware software partitioning using genetic algorithm. In: Proceedings Tenth International Conference on VLSI Design. IEEE, pp 155–160
Shi W, Wu J, Lam SK, Srikanthan T (2016) Algorithms for bi-objective multiple-choice hardware/software partitioning. Comput Electr Eng 50:127–142
Srinivasan V, Radhakrishnan S, Vemuri R (1998, February) Hardware software partitioning with integrated hardware design space exploration. In: Proceedings Design, Automation and Test in Europe. IEEE, pp 28–35
Teich J (2012) Hardware/software codesign: the past, the present, and predicting the future. Proc IEEE 100(Special Centennial Issue):1411–1430
Trindade AB, Cordeiro LC (2016) Applying SMT-based verification to hardware/software partitioning in embedded systems. Des Autom Embed Syst 20(1):1–19
Veličković P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2017) Graph attention networks. arXiv preprint arXiv:1710.10903
Wu J, Srikanthan T (2006) Low-complex dynamic programming algorithm for hardware/software partitioning. Inf Process Lett 98(2):41–46
Wu J, Srikanthan T, Chen G (2009) Algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Trans Comput 59(4):532–544
Wu J, Sun Q, Srikanthan T (2012) Algorithmic aspects for multiple-choice hardware/software partitioning. Comput Oper Res 39(12):3281–3292
Wu MY, Gajski DD (1990) Hypertool: a programming aid for message-passing systems. IEEE Trans Parallel Distrib Syst 1(3):330–343
Wu Z, Pan S, Chen F, Long G, Zhang C, Philip SY (2020) A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 32:4–24
Zill D, Wright WS, Cullen MR (2011) Advanced engineering mathematics. Jones & Bartlett Learning, Burlington
Zou Y, Zhuang Z, Chen H (2004, June) HW-SW partitioning based on genetic algorithm. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), vol 1. IEEE, pp 628–633
Zuo W, Pouchet LN, Ayupov A, Kim T, Lin CW, Shiraishi S, Chen D (2017, June) Accurate high-level modeling and automated hardware/software co-design for effective SoC design space exploration. In: Proceedings of the 54th Annual Design Automation Conference 2017, pp 1–6