A Multicommodity Flow-Based Detailed Router With Efficient Acceleration Techniques

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2018-01, Vol.37 (1), p.217-230
• Main Authors: Jia, Xiaotao, Cai, Yici, Zhou, Qiang, Yu, Bei
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Design rules; detailed routing; Industries; integer linear programing; Layout; multicommodity flow (MCF); Routing; Runtime; Timing; Very large scale integration
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2017.2693270

Detailed routing is an important stage in very large scale integrated physical design. Due to the extreme scaling of transistor feature size and the complicated design rules, ensuring routing completion without design rule checking (DRC) violations becomes more and more difficult. Studies have shown that the low routing quality partly results from nonoptimal net-ordering nature of traditional sequential methods. The concurrent routing strategy is always based on an NP-hard model, thus is at a disadvantage in runtime. In this paper, we present a novel concurrent detailed routing algorithm that routes all nets simultaneously. Based on the multicommodity flow model, detailed routing problem with complex design rule constraints is formulated as an integer linear programming. Some model simplification heuristics and efficient model solving algorithms are proposed to improve the runtime. Experimental results show that, the proposed algorithms can reduce the DRC violations by 80%, meanwhile can reduce wirelength and via count by 5% and 8% compared with an industry tool. In addition, the proposed algorithm is general that it can be adopted as an incremental detailed router to refine a routing solution, so the number of DRC violations that industry tool cannot fix are further reduced by 27%.