We use cookies to improve your experience with our site.

基于优先级的串扰驱动综合布线资源分配

Priority-Based Routing Resource Assignment Considering Crosstalk

  • 摘要: 随着集成电路工艺的发展,特征尺寸不断缩小,相邻金属导线间的耦合日益显著。耦合电容和耦合电感导致的信号线互相影响的效应称为串扰。串扰可能导致电路性能下降甚至逻辑错误。在超深亚微米工艺下的高速集成电路中,串扰已经成为物理设计必须解决的重大问题。针对超深亚微米集成电路中串扰避免的问题,本文从设计流程和算法两个层次进行讨论。布线是物理设计中确定信号线位置的操作,对串扰影响重大。在布线的各阶段中,总体布线有较大的灵活性,但对各区域或信号线上的串扰难以估计;详细布线可以精确地计算串扰,但灵活性太小,往往出现反复拆线重布,难以达到设计收敛;相比之下,总体布线和详细布线中间的阶段既有一定的灵活性,又可以相对准确地计算噪声,是解决串扰问题的理想时机。同时,中间阶段问题规模适中,可以找到复杂度比较低的算法,解决大规模问题。这些中间阶段包括层分配(确定线网各段所在的布线层)、轨道分配(确定较长线段占据的轨道)、屏蔽插入(在某些轨道上插入屏蔽线)等。本文提出一个新的布线流程,将传统设计流程中总体布线和详细布线之间若干分开的操作结合起来,形成一个综合布线资源分配阶段。这个阶段有利于各种中间操作的互相合作,充分发挥中间操作在串扰优化方面的优势,实现布线优化。在新的流程下,本文提出一个基于优先级的构造性算法。为了减小问题规模,提高求解效率,算法每次处理处理总体布线图上的一行或一列。该算法以减小串扰为主要目标,兼顾到包括拥挤度、通孔、层取向在内的其他各种因素。根据拥挤度、串扰敏感度、线长等参数,每条线段都可以计算一个优先级,进行分配时按优先级从高到低进行。为了克服顺序布线的固有缺陷,算法采用了一种轨道资源预留的策略,在分配前期考虑到后续线网的资源需求情况,尽量不在早期占据固定某些预留轨道。我们通过实验,得到了预留轨道占总轨道数的比例与算法结果之间的关系,并报告了相关结果。在一系列ISPD98标准测试例子上的实验结果表明,本文提出的算法与一个基于图论的同类算法相比,可以减少约70%的串扰(在ibm02中完全避免了有害的容性耦合),同时布通率没有明显减小。为了考察算法在拥挤度很大的电路中的性能,我们减少了部分标准测试例子上的布线层数,形成一组新的测试例子。在这组例子上的实验结果表明,当拥挤度很大时,本文提出的算法在多数电路中仍然具有较好的性能。

     

    Abstract: Crosstalk has become one of the most critical concerns in verydeep sub-micron era. This paper deals with the problem ofcrosstalk mitigation at both methodological and algorithmiclevels. Noting that intermediate operations between global routingand detailed routing are very effective in crosstalk estimationand reduction, the authors propose to incorporate several intermediatesteps that are separated in traditional design flow into anintegrated routing resource assignment stage, so that theoperations could easily cooperate to fully exert their power oncrosstalk reduction. An efficient priority-basedheuristic algorithm is developed, which works slice by slice. Crosstalkavoidance, and many other aspects that are critical inrouting practice including congestion, vias, layer preference,etc., are taken into account. A track reservation strategy isadopted in the algorithm framework to compensate the undesiredeffects caused by sequential routing. Experimental results on aseries of ISPD98 and industrial benchmarks show that the proposedapproach is able to reduce capacitive crosstalk by about 70\% onaverage without compromising completion ratio compared with apreviously reported graph based algorithm, demonstrating theadvantages of the approach.

     

/

返回文章
返回