【作者】 张凌；

【导师】 经彤；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2004， 硕士

【摘要】 集成电路一直在迅猛发展。制造工艺由超深亚微米(VDSM)进入到纳米(nanometer)阶段;设计规模由超大规模(VLSI)、甚大规模(ULSI)向G规模集成(GSI)发展;越来越多的功能、甚至是一个系统都被集成到单个芯片之中,出现了系统级芯片(SOC)的设计概念。于是,作为物理设计(physical design,layout)中重要阶段的总体布线(global routing),其算法研究与工具设计面临巨大挑战。其中之一是:随着集成度更高,芯片上模块和互连线的排列更加紧密,互连线的间距进一步减小;元件数目的增加和线宽的缩小使互连线的相对长度大大增加;电路工作频率更高。这都使得集成电路中的耦合效应明显,串扰(crosstalk)成为一个突出的问题。因此,在布线阶段如何恰当有效地估算并消除串扰,是目前亟待解决的理论与技术热点问题。论文设计、实现了一个标准单元模式下能够消除由耦合电感引起的串扰并同时进行性能优化的总体布线器PO-GR。该布线器的功能是:在满足给定串扰、时延约束的基础上,对总线长和布线拥挤进行优化。该布线器还是一个平台,为深入研究性能优化布线问题、改进布线算法创造了条件。实验结果表明:PO-GR能够求得满足给定串扰和时延约束,并优化线长与布线拥挤的总体布线解。论文提出了基于禁忌搜索技术的高效串扰消除算法T-PO-GR。基于所设计的PO-GR布线平台,研究了高效消除串扰的策略。提出采用禁忌搜索技术设计串扰消除算法,以获得高效的除扰性能。实验结果表明:新的除扰算法比PO-GR中原有的方法速度提高20倍左右,布线器整体的布线速度提高14倍左右。而得到的布线质量与原来基本一致。论文提出了考虑面积优化的消除串扰总体布线算法AT-PO-GR。力图从整体优化角度出发,对PO-GR的总体算法流程进行全面改进,力求一致优化布线拥挤、时延和串扰噪声。其结果是在快速满足串扰和时延约束的基础上,减少屏蔽线(shield)的使用数目,从而减小最终电路的总面积;同时做到不影响总线长和拥挤度。实验结果表明:所提出方法的设计思想有发展前途,效果也好。更多还原

【Abstract】 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 <WP=5>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.更多还原