Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Estimating feature importance in circuit network using machine learning

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Identifying the feature of the circuit network is a crucial step to understanding the behavior of the Very Large Scale Integration (VLSI). Unfortunately, the growing complexity of the VLSI design makes enormous computations for estimating the property of the network. We propose a machine learning framework to overcome the intractable estimation of feature importance in the circuit network. We extract complex network features at the placement stage and compute circuit wire length at the routing stage, then study their correlation using machine learning and estimate the importance of complex network features by the learned correlation. The experimental result on TAU 2017 Benchmark shows the high efficiency of the framework that the prediction accuracy achieves an average of 96.722%. The estimated importance of complex network features is in order of the number of nodes, the average degree, the average edge weight, the average betweenness, the average strength, and the average weighted clustering coefficient. The result is convincing and consistent with the previous work, demonstrating the reliability of our method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data Availability

Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

References

  1. Khan HN, Hounshell DA, Fuchs ER (2018) Science and research policy at the end of Moore’s law. Nat Electron 1(1):14–21

    Article  Google Scholar 

  2. DHuys O, Vicente R, Erneux T, Danckaert J, Fischer I (2008) Synchronization properties of network motifs: Influence of coupling delay and symmetry. Chaos: An Interdisciplinary Journal of Nonlinear Science 18(3)

  3. Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86(14):3200

    Article  ADS  CAS  PubMed  Google Scholar 

  4. Boguna M, Krioukov D, Claffy KC (2009) Navigability of complex networks. Nat Phys 5(1):74–80

    Article  CAS  Google Scholar 

  5. Smith O, Crowe J, Farcot E, O’Dea RD, Hopcraft KI (2020) Cascading failures in networks of heterogeneous node behavior. Phys Rev E 101(2):020301

    Article  ADS  CAS  PubMed  Google Scholar 

  6. Shishavan ST, Gharehchopogh FS (2022) An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks. Multimed Tools Appl 81(18):25205–25231

    Article  Google Scholar 

  7. Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Sys 30(1–7):107–117

    Article  Google Scholar 

  8. Kleinberg JM (1999) Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM) 46(5):604–632

    Article  MathSciNet  Google Scholar 

  9. Tang X, Wang J, Zhong J, Pan Y (2013) Predicting essential proteins based on weighted degree centrality. IEEE/ACM Trans Comput Biol Bioinforma 11(2):407–418

    Article  Google Scholar 

  10. Barthelemy M (2004) Betweenness centrality in large complex networks. Eur Phys J B 38(2):163–168

    Article  ADS  CAS  Google Scholar 

  11. Salavati C, Abdollahpouri A, Manbari Z (2019) Ranking nodes in complex networks based on local structure and improving closeness centrality. Neurocomputing 336:36–45

    Article  Google Scholar 

  12. Newman ME (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104

    Article  ADS  MathSciNet  CAS  Google Scholar 

  13. Nie T, Guo Z, Zhao K, Lu ZM (2016) Using mapping entropy to identify node centrality in complex networks. Physica A: Stat Mech Appl 453:290–297

    Article  Google Scholar 

  14. Berahmand K, Bouyer A, Samadi N (2018) A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks. Chaos, Solitons Fractals 110:41–54

  15. Samadi N, Bouyer A (2019) Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks. Computing 101:1147–1175

    Article  MathSciNet  Google Scholar 

  16. Wang DEJ (2006) Fast approximation of centrality. Graph Algoritm Appl 5(5):39

    Google Scholar 

  17. Cohen E, Delling D, Pajor T, Werneck RF (2014) Computing classic closeness centrality, at scale. In the second ACM conference on Online social networks, pp 37–50

  18. Rattigan MJ, Maier M, Jensen D (2006) Using structure indices for efficient approximation of network properties. In the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 357–366

  19. Saxena A, Iyengar S (2020) Centrality measures in complex networks: A survey. arXiv preprint arXiv:2011.07190

  20. Grando F, Granville LZ, Lamb LC (2018) Machine learning in network centrality measures: Tutorial and outlook. ACM Comput Surv (CSUR) 51(5):1–32

    Article  Google Scholar 

  21. Mendona MR, Barreto AM, Ziviani A (2020) Approximating network centrality measures using node embedding and machine learning. IEEE Trans Netw Sci Eng 8(1):220–230

    Article  MathSciNet  Google Scholar 

  22. i Cancho RF, Janssen C, Sol RV, (2001) Topology of technology graphs: Small world patterns in electronic circuits. Phys Rev E 64(4):046119

  23. Raman K, Wagner A (2011) The evolvability of programmable hardware. J R Soc Interface 8(55):269–281

    Article  PubMed  Google Scholar 

  24. Nie T, Fan B, Zhu Z, Zhou L (2020) Performance and Correlations of Weighted Circuit Networks. IEEE Access 8:72683–72693

    Article  Google Scholar 

  25. Aggarwal K, Mijwil MM, Al-Mistarehi AH, Alomari S, Gk M, Alaabdin AMZ, Abdulrhman SH (2022) Has the future started? The current growth of artificial intelligence, machine learning, and deep learning. Iraqi J Comp Sci Math 3(1):115–123

    Google Scholar 

  26. Huang G, Hu J, He Y, Liu J, Ma M, Shen Z et al (2021) Machine learning for electronic design automation: A survey. ACM Trans Des Autom Electron Syst (TODAES) 26(5):1–46

    Article  Google Scholar 

  27. Onnela JP, Saramki J, Kertsz J, Kaski K (2005) Intensity and coherence of motifs in weighted complex networks. Phys Rev E 71(6):065103

    Article  ADS  Google Scholar 

  28. Pretorius A, Bierman S, Steel SJ (2016) A meta-analysis of research in random forests for classification. In 2016 Pattern Recognition Association of South Africa and Robotics and Mechatronics International Conference (PRASA-RobMech), pp 1–6

  29. Friedman JH, Roosen CB (1995) An introduction to multivariate adaptive regression splines. Stat Methods Med Res 4(3):197–217

    Article  CAS  PubMed  Google Scholar 

  30. Hua Y, Guo J, Zhao H (2015) Deep belief networks and deep learning. In 2015 International Conference on Intelligent Computing and Internet of Things, pp 1–4

  31. Basheer IA, Hajmeer M (2000) Artificial neural networks: fundamentals, computing, design, and application. J Microbiol Meth 43(1):3–31

    Article  CAS  Google Scholar 

  32. Roy JA, Adya SN, Papa DA, Markov IL (2006) Min-cut floorplacement. IEEE Trans Comput Aided Des Integr Circ Sys 25(7):1313–1326

    Article  Google Scholar 

  33. Yang X, Choi BK, Sarrafzadeh M (2002) Routability driven white space allocation for fixed-die standard-cell placement. In 2002 international symposium on Physical design, pp 42–47

  34. Viswanathan N, Pan M, Chu C (2007) FastPlace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. In 2007 Asia and South Pacific Design Automation Conference, pp 135–140

  35. Khatkhate A, Li C, Agnihotri AR, Yildiz MC, Ono S, Koh CK, Madden PH (2004) Recursive bisection based mixed block placement. In 2004 international symposium on Physical design, pp 84–89

  36. Chan TF, Cong J, Shinnerl JR, Sze K, Xie M (2006) mPL6: Enhanced multilevel mixed-size placement. In 2006 international symposium on Physical design, pp 212–214

  37. Chen TC, Jiang ZW, Hsu TC, Chen HC, Chang YW (2008) NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Trans Comput Aided Des Integr Circ Sys 27(7):1228–1240

    Article  Google Scholar 

  38. Hu J, Roy JA, Markov IL (2010) Completing high-quality global routes. In the 19th international symposium on Physical design, pp 35–41

  39. Kapre N, Chandrashekaran B, Ng H, Teo K (2015) Driving timing convergence of FPGA designs through machine learning and cloud computing. In 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines, pp 119–126

  40. Al-Hyari SH, Foxcroft A, Martin J, Noel T, Grewal DG, Areibi S (2020) Machine learning for congestion management and routability prediction within FPGA placement. ACM Trans Des Autom Electron Syst (TODAES) 25(5):1–25

    Article  Google Scholar 

Download references

Acknowledgements

Project 61572269 supported by NSFC. And project ZR2021MF101 supported by Shandong Provincial Natural Science Foundation.

Author information

Authors and Affiliations

  1. School of Information and Control Engineering, Qingdao University of Technology, Jialingjiang Road, Qingdao, 266520, Shandong, China

    Tingyuan Nie, Mingzhi Zhao, Zuyuan Zhu, Kun Zhao & Zhenhao Wang

Authors
  1. Tingyuan Nie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mingzhi Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zuyuan Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kun Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Zhenhao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tingyuan Nie.

Ethics declarations

Conflicts of Interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Mingzhi Zhao, Zuyuan Zhu, Kun Zhao, and Zhenhao Wang are contributed equally to this work.

Appendix A: Table of notations

Appendix A: Table of notations

Notations

Definitions

\(v_{i}\)

Node i of a network.

\(w_{ij}\)

Element of the adjacency matrix.

\((x_i,y_i)\)

Coordinate of node i.

\(k_{i}\)

The number of adjacent edges of node i.

\({y_i}\)

True value of the i-th data.

\({\hat{y_i}}\)

Predicted value of the i-th data.

\({ \mathop y\limits ^\_ }\)

Average true values of the data.

\(f_i\)

The i-th complex network feature.

e

Original value of a metric.

\({e_{f_i}}\)

Value of a metric after removing the i-th feature.

N

Size of a network.

\(S_i\)

Strength of node i.

\(B_i\)

Betweenness of node i.

K

Average degree of a network.

E

Average edge weight of a network.

S

Average strength of a network.

\(C_{O,i}^{w}\)

Clustering coefficient of a weighted network.

W

Adjacency matrix of a network.

MAE

Mean Absolutee Error.

MSE

Mean Square Error.

\(R^2\)

Coefficient of Determination.

\(\Delta \Phi \)

Change ratio of metric.

\(Score_{f_i}\)

Score of complex network feature \(f_i\).

Rank(i)

Rank of feature i.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nie, T., Zhao, M., Zhu, Z. et al. Estimating feature importance in circuit network using machine learning. Multimed Tools Appl 83, 31233–31249 (2024). https://doi.org/10.1007/s11042-023-16814-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-023-16814-8

Keywords

Search

Navigation