Fast Rerouting And Design Rules Satisfaction Methods In Detailed Routing

With the development of the IC manufacturing technology,the complexity of the physical design of VLSI increases rapidly,which makes it necessary to adopt EDA tools.In the physical design automation flow,detailed routing is the most complicated and time-consuming stage.In advanced technology node,a lot of design rule constraints must be satisfied in detailed routing to ensure a chip can be correctly fabricated.In addition,the shrinking of the feature size of transistors greatly enlarges the number of cells of one chip,resulting in enormous nets to connect in detailed routing.Thus,the routing problem with so large a scale takes long time to work out.Even the state-of-the-art academic detailed routers such as Dr.CU and Triton Route,still have some shortcomings including long runtime and remaining design rule violations.Therefore,researches about detailed routing acceleration and handling the design rules are important.To tackle the two problems above,several techniques are proposed in this paper,to accelerate the detailed routing,as well as repair the violations of some design rules.These techniques are verified on the ISPD-2018 testcases,and a comparison with the result of Dr.CU will be shown.A fast design-rule-check(DRC)algorithm is proposed to find all shorts and metal spacing violations in a region,by marking the wires and vias.The fast DRC algorithm can reduce the query times of routing results,and enable parallel check on different regions,which improve the efficiency.Compared with the verify algorithm in Dr.CU,the fast DRC algorithm reduce the runtime by 58.22% on average.A partial rip-up and reroute(R&R)framework is proposed to repair violations.Two different rip-up strategies are developed,which are dedicated to violations need different effort to fix.The framework consists of two repair iterations and the strategies are adopted in each iteration.Experiments show that the wirelength and via counts in the result of the partial R&R framework are similar as those of Dr.CU,while the runtime is 47.22% lower on average.Violations in results of most testcases only increase slightly or even decrease,except a case with an extremely congested region.Three post process techniques are proposed to handle three design rules.The violations of those rules only occur in some specific situations,and the repair of them won't change the routing result too much.After optimizing by these techniques,the number of violations in the results of all testcases decrease by 62.92%,and the wirelength,via counts and runtime are almost the same.