PCB Network Analysis for Circuit Partitioning
Source abstract
Abstract
The complexity of automatic placement and routing is proportional to the scale of the circuit. Through netlist partition algorithms, printed circuit board (PCB) circuits are divided into different submodules, and the problem scale is effectively reduced in order to obtain the optimal automatic layout and routing. In this paper, we analyze net attributes and potential patterns in netlists through visualization, and propose a heuristic PCB netlist partition approach based on net attributes and potential patterns which we discover from netlists. Our partition approach takes the netlist as input, and module partition set as output. Firstly, the modules are prepartitioned using net attributes. Further, the special patterns in circuits are discovered, and the scattered resistors, capacitors, and other components caused by prepartitioning would be allocated to initial modules by three rules—classifying, matching, and force strategy. Our method is evaluated on 11 PCB netlists which are built manually. Experimental results show that our proposed netlist partition approach significantly outperforms the state of the art on all evaluation indices, which can achieve 80–96% partition accuracy.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: VLSI and FPGA Design Techniques · Industrial Vision Systems and Defect Detection · VLSI and Analog Circuit Testing
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Automation Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
Funding
National Natural Science Foundation of China
References (27)
Show source-provided references
1. An efficient heuristic procedure for partitioning graphs10.1002/j.1538-7305.1970.tb01770.x ↗
2. Kahng, B.K., Lienig, L., and Markov, I.L. (2011). VLSI Physical Design: From Graph Partitioning to Timing Closure, Springer.10.1007/978-90-481-9591-6 ↗
3. Multilevel hypergraph partitioning: Applications in VLSI domain10.1109/92.748202 ↗
4. Design and implementation of move-based heuristics for VLSI hypergraph partitioning10.1145/351827.384247 ↗
5. Meng, D., and Zheng, Y.L. (2022, January 9–11). Circuit Partitioning for PCB Netlist Based on Net Attributes. Proceedings of the International Conference on Machine Learning and Cybernetics, Toyama, Japan.10.1109/ICMLC56445.2022.9941328 ↗
6. An algorithm for partitioning the nodes of a graph10.1137/0603056 ↗
7. Nayak, S., Panda, S., and Panda, M. (2018, January 22–24). Circuit Partitioning optimization using Parallel refinement algorithm. Proceedings of the International Conference on Applied Electromagnetics, Signal Processing and Communication (AESPC), Bhubaneswar, India.10.1109/AESPC44649.2018.9033291 ↗
8. Ford, L.R., and Fulkerson, D.R. (1962). Flows in Networks, Princeton University Press.10.1515/9781400875184 ↗
9. A replication cut for two-way partitioning10.1109/43.384426 ↗
10. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision10.1109/TPAMI.2004.60 ↗
11. Hamada, T., Cheng, C.K., and Chau, P.M. (1991, January 11–14). An efficient multilevel placement technique using hierarchical partition. Proceedings of the IEEE International Sympoisum on Circuits and Systems, Singapore.10.1109/ISCAS.1991.176805 ↗
12. Areibi, S., and Vannelli, A. (1996, January 12–15). An efficient clustering technique for circuit partitioning. Proceedings of the IEEE International Symposium on Circuits and Systems. Circuits and Systems Connecting the World (ISCAS), Atlanta, GA, USA.
13. An efficient eigenvector approach for finding netlist partitions10.1109/43.144852 ↗
14. Fiduccia, C.M., and Mattheyses, R.M. (1982, January 14–16). A linear-time heuristic for improving network partitionse. Proceedings of the Design Automation Conference, Las Vegas, NV, USA.10.1109/DAC.1982.1585498 ↗
15. Sinha, B., Laskar, N.M., Sen, R., and Baishnab, K.L. (2015, January 19–20). Heuristics in Physical Design Partitioning: A Review. Proceedings of the IEEE International Conference on Innovations in Information Embedded and Communication Systems (ICIIECS), Coimbatore, India.10.1109/ICIIECS.2015.7192900 ↗
16. A general purpose, multiple-way partitioning algorithm10.1109/43.331405 ↗
17. Edge Separability-Based Circuit Clustering With Application to Multilevel Circuit Partitioning10.1109/TCAD.2004.823353 ↗
18. Cherng, J.S., and Chen, S.J. (2003, January 4–8). An efficient multilevel partitioning algorithm for VLSI circuits. Proceedings of the IEEE International Conference on VLSI Design, New Delhi, India.
19. Manna, K., Choubey, V., Chattopadhyay, S., and Sengupta, I. (2014, January 11–13). Thermal variance-aware application mapping for mesh based network-on-chip design using Kernighan-Lin partitioning. Proceedings of the International Conference on Parallel, Distributed and Grid Computing, Solan, India.10.1109/PDGC.2014.7030755 ↗
20. Rajan, A.K., and Bhaiya, D. (2017, January 6–8). VLSI partitioning using parallel kernighan lin algorithm. Proceedings of the International Conference on Communication and Signal Processing (ICCSP), Chennai, India.10.1109/ICCSP.2017.8286727 ↗
21. TSV Placement and Core Mapping for 3D Mesh Based Network-on-Chip Design Using Extended Kernighan-Lin Partitioning
22. Lei, X., Liang, W., Li, K.C., Luo, H., Hu, L., Cai, J., and Li, Y. (2019, January 27–29). A New Multilevel Circuit Partitioning Algorithm Based on the Improved KL Algorithm. Proceedings of the IEEE International Conference on Big Data Security on Cloud (BigDataSecurity), Washington, DC, USA.10.1109/BigDataSecurity-HPSC-IDS.2019.00041 ↗
23. Ratio cut partitioning for hierarchical designs10.1109/43.87601 ↗
24. Desai, S.M., Gambhi, S., and Sharma, P. (2016, January 14–15). An Improved and Optimized Layer Assignment Partitioning Algorithm. Proceedings of the IEEE International Conference Cloud System and Big Data Engineering, Noida, India.10.1109/CONFLUENCE.2016.7508158 ↗
25. Placement-Driven Partitioning for Congestion Mitigation in Monolithic 3D IC Designs10.1109/TCAD.2014.2387827 ↗
26. Hu, L.R., Duan, Q., Qi, Z., Wang, J., Lai, J.M., and Yang, M. (November, January 31). A new hyper-graph partitioning for 3D-FPGA. Proceedings of the IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT), Qingdao, China.
27. Zhou, Z.H. (2016). Machine Learning, Tsinghua University Press.