Performance And RLC Crosstalk Driven Global Routing

In recent years, the VLSI/ULSI (very/ultra large scale integrated circuits) technology has profoundly advanced. Now, one chip contributes more than one hundred million towards the number of transistors inside. Thus, we can design a single chip with more and more functions and many more transistors. This advance enables system-on-a-chip (SOC) integration. Meanwhile, fabrication technology moves into nano device size. We can design a single chip with large overall dimension but smaller feature size and wire space. Global routing plays an important role in VLSI/ULSI physical design. New challenges to routing are "rigorous" performance optimizations. One of the concerns is crosstalk. The decreasing of interconnect spacing and giga-hertz clock frequencies bring on great inter-wire coupling capacitance and inductance, which causes coupling noise (crosstalk). It may lead to significant deviations between actual and nominal timing responses, power consumptions and functional behaviors if we failed to consider the issue in performance optimization. So, it is useful to do research on advanced and efficient crosstalk estimation and elimination algorithms for global routing.One of the contributions of this paper is that the RLC coupling noise, timing performance, and routability are studied simultaneously at global routing level. Regarding wire length as the objective and letting timing, RLC coupling noise, and routability be the constraints, this paper presents a performance optimization global routing algorithm under multi-constraints. This algorithm has been implemented and the global router is called PO-GR. The experimental results show that PO-GR is able to: (1) Tackle RLC coupling noise, timing performance and routability simultaneously; (2) Obtain good routing results; (3) Efficiently eliminates crosstalk throughout the process of global routing by inserting shields, which has little influence on wire length and timing performance.The other contribution of this paper is that an efficient crosstalk elimination algorithm based on Tabu search, named T-PO-GR, is proposed. The experimental results show that T-PO-GR is able to preserve the good routing result and greatly decrease the running time. This paper also proposes an algortithm named AT-PO-GR, which tries to improve the top level optimizing flow of PO-GR in order to minimize the routing area while satisifies the crosstalk, timing and congestion constrants. The experimental results show that the area and the number of shield in routing results have been reduced, and the constraints of crosstalk, timing and congestion have been met as well, and the wire length is not affected. Hence, it is proved that the idea of AT-PO-GR is promising, and could obtain good result.