SO SÁNH HIỆU NĂNG CỦA THUẬT TOÁN MAZE ROUTING  VÀ RIP-UP & REROUTE TRONG ĐỊNH TUYẾN MẠCH VLSI

Nguyễn Thị Thanh Bình; Nguyễn Xuân Kiên

doi:10.34238/tnu-jst.12092

SO SÁNH HIỆU NĂNG CỦA THUẬT TOÁN MAZE ROUTING VÀ RIP-UP & REROUTE TRONG ĐỊNH TUYẾN MẠCH VLSI

Thông tin bài báo

Ngày nhận bài: 19/02/25 Ngày hoàn thiện: 07/05/25 Ngày đăng: 09/05/25

Các tác giả

1. Nguyễn Thị Thanh Bình, Đại học Thái Nguyên
2. Nguyễn Xuân Kiên , Trường Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên

Tóm tắt

Bài báo thực hiện so sánh hiệu năng của hai thuật toán định tuyến Maze Routing và Rip-Up & Reroute trong thiết kế VLSI, về khả năng đáp ứng các yêu cầu về tốc độ xử lý và chất lượng đường đi. Thông qua thu thập dữ liệu và phân tích thống kê với 100 lần mô phỏng trên lưới vi mạch dạng lưới với hai kích thước (20×20 và 40×40) và hai mức mật độ vật cản (5% và 10%), các net được khởi tạo ngẫu nhiên trên các cell không chứa vật cản. Các chỉ số đánh giá bao gồm thời gian thực thi, độ dài đường đi, số lần uốn, tỷ lệ định tuyến thành công và số lần rip-up. Kết quả, trên lưới 20×20, thời gian thực thi của Maze Routing (0,0032 ± 0,0051 giây) ở kịch bản với 5% vật cản và 3 nets bằng 10% so với Rip-Up & Reroute (0,0336 ± 0,0522 giây), trong khi Maze Routing duy trì tỷ lệ định tuyến thành công cao (88,7% so với 78,0% của Rip-Up & Reroute). Trên lưới 40×40, Maze Routing vẫn có thời gian xử lý nhanh, (0,0047 đến 0,0075 giây) và số lần rip-up thấp. Nghiên cứu cho thấy Maze Routing có ưu thế về thời gian xử lý và tỷ lệ định tuyến thành công, trong khi Rip-Up & Reroute cho kết quả về độ dài đường đi ngắn hơn trong một số kịch bản nhưng bị hạn chế do chi phí tính toán cao và số lần rip-up tăng. Đánh giá này nhấn mạnh tầm quan trọng của việc cân bằng giữa hiệu quả tính toán và chất lượng trong việc lựa chọn thuật toán định tuyến cho các ứng dụng VLSI.

Từ khóa

VLSI; Maze Routing; Rip-Up & Reroute; Định tuyến mạch; Mô phỏng VLSI

Toàn văn:

PDF (English)

Tài liệu tham khảo

[1] X. Chen, G. Liu, N. Xiong, Y. Su, and G. Chen, "A Survey of Swarm Intelligence Techniques in VLSI Routing Problems," IEEE Access, vol. 8, pp. 26266-26292, 2020.

[2] K. Lakshmanna, F. Shaik, V. K. Gunjan, N. Singh, G. Kumar, and R. M. Shafi, "Perimeter Degree Technique for the Reduction of Routing Congestion during Placement in Physical Design of VLSI Circuits," Complexity, vol. 2022, no. 1, 2021, Art. no. 8658770.

[3] R. A. Solovyev et al., "PAGR: Accelerating Global Routing for VLSI Design Flow," IEEE Access, vol. 13, pp. 6440-6450, 2025.

[4] M. B. Raith, “Rip-Up and Reroute Strategies,” in Advanced Routing of Electronic Modules, CRC Press, 2024, pp. 347-368.

[5] Z. Qi, J. Zhang, G.-L. Chen, and H. You, "Effective and Efficient Detailed Routing with Adaptive Rip-up Scheme and Pin Access Refinement," in Proceedings of the Great Lakes Symposium on VLSI, 2022, pp. 165-168.

[6] M. Gao and D. Forte, "Detour: Layout-aware Reroute Attack Vulnerability Assessment and Analysis," in IEEE International Symposium on Hardware Oriented Security and Trust (HOST), San Jose, CA, USA, 2023, pp. 122-132.

[7] M. Gao, L. K. Biswas, N. Asadi, and D. Forte, "Detour-RS: Reroute Attack Vulnerability Assessment with Awareness of the Layout and Resource," Cryptography, vol. 8, no. 2, 2024, Art. no. 13.

[8] U. Gandhi, E. Aghaeekiasaraee, P. Mousavi, I. S. K. Bustany, and L. Behjat, "Applying Reinforcement Learning to Learn Best Net to Rip and Re-route in Global Routing," ACM Transactions on Design Automation of Electronic Systems, vol. 29, no. 4, 2024, Art. no. 69.

[9] M. A. Zapletina, D. A. Zheleznikov, and V. M. Khvatov, "The Rip-up and Reroute Technique Research for Island-Style Reconfigurable System-on-Chip," in 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), Saint Petersburg and Moscow, Russia, 2019, pp. 1593-1596.

[10] S. Yao, X. Yang, Z. Song, X. Yang, D. Duan and H. Yang, "Maze Routing: An Information Privacy-aware Secure Routing in Internet of Things for Smart Grid," 2022 7th International Conference on Communication, Image and Signal Processing (CCISP), Chengdu, China, 2022, pp. 461-465 .

[11] X. Jiang et al., "FPGA-Accelerated Maze Routing Kernel for VLSI Designs," in 27th Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE, 2022, pp. 592-597.

[12] Z. Fu et al., "An Efficient Maze Routing Algorithm for Fast Global Routing," in Proceedings of the Great Lakes Symposium on VLSI, 2022, pp. 169-172.

[13] Z. Li, J. Zhai, Z. Li, Z. Qi, and K. Zhao, "Effective Resource Model and Cost Scheme for Maze Routing in 3D Global Routing," in IEEE International Symposium on Circuits and Systems (ISCAS), Singapore, Singapore, 2024, pp. 1-5.

[14] S. Lin, J. Liu, E. F. Y. Young, and M. D. F. Wong, "GAMER: GPU-Accelerated Maze Routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 42, no. 2, pp. 583-593, Feb. 2023.

[15] K.-H. Chang, H.-H. Pan, T.-C. Wang, P.-Y. Chen, and C.-F. C. Shen, "On Predicting Solution Quality of Maze Routing Using Convolutional Neural Network," in 23rd International Symposium on Quality Electronic Design (ISQED), Santa Clara, CA, USA, 2022, pp. 1-6.

DOI: https://doi.org/10.34238/tnu-jst.12092

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ