FuzzRoute: A Thermally Efficient Congestion-Free Global Routing Method for Three-Dimensional Integrated Circuits

• Published in: ACM transactions on design automation of electronic systems 2015-11, Vol.21 (1), p.1-38
• Main Authors: Roy, Debashri, Ghosal, Prasun, Mohanty, Saraju
• Format: Article
• Language: English
• ISSN: 1084-4309; 1557-7309
• DOI: 10.1145/2767127

The high density of interconnects, closer proximity of modules, and routing phase are pivotal during the layout of a performance-centric three-dimensional integrated circuit (3D IC). Heuristic-based approaches are typically used to handle such NP-complete problems of global routing in 3D ICs. To overcome the inherent limitations of deterministic approaches, a novel methodology for multi-objective global routing based on fuzzy logic has been proposed in this article. The guiding information generated after the placement phase is used during routing with the help of a fuzzy expert system to achieve thermally efficient and congestion-free routing. A complete global routing solution is designed based on the proposed algorithms and the results are compared with selected fully established global routers, namely Labyrinth, FastRoute3.0, NTHU-R, BoxRouter 2.0, FGR, NTHU-Route2.0, FastRoute4.0, NCTU-GR, MGR, and NCTU-GR2.0. Experiments are performed over ISPD 1998 and 2008 benchmarks. The proposed router, called FuzzRoute , achieves balanced superiority in terms of routability, runtime, and wirelength over others. The improvements on routing time for Labyrinth, BoxRouter 2.0, and FGR are 91.81%, 86.87%, and 32.16%, respectively, for ISPD 1998 benchmarks. It may be noted that, though FastRoute3.0 achieves fastest runtime, it fails to generate congestion-free solutions for all benchmarks, which is overcome by the proposed FuzzRoute of the current article. It also shows wirelength improvements of 17.35%, 2.88%, 2.44%, 2.83%, and 2.10%, respectively, over others for ISPD 1998 benchmarks. For ISPD 2008 benchmark circuits it also provides 2.5%, 2.6%, 1 %, 1.1%, and 0.3% lesser wirelength and averagely runs 1.68×, 6.42×, 2.21×, 0.76×, and 1.54× faster than NTHU-Route2.0, FastRoute4.0, NCTU-GR, MGR, and NCTU-GR2.0, respectively.