多级自动布线框架中的时延平衡分析

《多级自动布线框架中的时延平衡分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在__年解密后适用本授权书。本学位论文属于不保密□。（请在以上方框内打“√”）学位论文作者签名：李小南指导教师签名：施国勇日期：2008年2月18日日期：2008年2月18日上海交通大学工程硕士学位论文第一章前言第一章前言1.1布

2、线研究前景集成电路一直在迅速发展，制造工艺在不断进步，现在已经进入了深亚微米时代。电路设计规模也越来越大，由超大规模（VLSI）、甚大规模（ULSI）向极大规模集成（GSI）规模发展。越来越多的功能，甚至是整个系统都被集成到单个芯片之中，出现了系统级芯片（SOC）的设计概念。于是，作为物理设计[8][9]（Physicaldesign，layout）中的重要阶段的布线（routing），其算法研究与工具设计面临巨大挑战。其中一个挑战是：随着集成度更高，芯片上模块和互连线的排列更加紧密，互联线的间距进一步减少；元件数目的增加和线宽的缩少使

3、互连线的相对长度大大增加；电路工作频率更高。这都使得集成电路中互连线的时延和耦合效应明显。因此，在布线阶段能恰当有效地估计线网长度，拥塞和串扰情况，并使布线长尽量短（包括总线长最短和最长路径最短），线网尽量均匀分布，串扰尽可能小，这是目前研究的热点。在VLSI电路设计中，物理设计阶段的布线是一个非常复杂的问题。经过多年的发展，通常布线分为两个步骤：总体布线和详细布线。在总体布线阶段，通常的思想是将整个芯片划分为N×N的块(tiles)，并将多端点线网分解成为二端点线网，然后找出所有2端点线网的块到块的路径。一些传统的算法如[4]，他们都

4、无法处理很大的问题，特别是现在工艺发展到90nm以下，集成电路的规模越来越大。因此，2～3级的层级布线应运而生，超大的布线问题然而还是无法很好地解决，所以便有了多级布线框架的产生[1，2]。多级布线算法不同于以往的考虑时延或者拥挤的布线算法[1][2][3][7]，它们将布线区域一级级地划分，并将总体布线，详细布线，延时和拥挤估计集成在每一级中，这样每一级布线，时延或拥挤估计的精度都非常高，当布线传递到下一级时，高精度的上一级布线结果和资源估计对下一级布线将有着良好的指导作用，并且多级的方法能处理很大的布线问题。第1页上海交通大学工程硕

5、士学位论文第一章前言1.2布线算法思想介绍当VLSI电路的芯片布局结束后，电路模块的绝对位置和模块引脚的位置已经确定，此后就要实现模块间的连接。通常有两种策略实现布局后的布线，即直接的区域布线和分两步实现的总体布线和详细布线。布线问题从不同的角度来划分则有不同的布线方式：就布线的对象来分，它可分为面向线网的布线和面向区域的布线，面向线网的布线主要以线网作为考虑对象，如总体布线和区域布线都属于面向线网的布线；而面向区域的布线主要以布线区域作为考虑对象，如两边通道和开关盒都属于面向区域的布线。区域布线是直接在一个区域内（可多层）进行布线。区

6、域可大至整个芯片，也可以是一个子区域。其特点是线网的引线端可分布在区域边界，也可在区域内。总体布线是在布局后产生的总体布线图上完成线网的分配，但不确定具体的走线位置。详细布线则根据布线对象不同，可以是通道布线，也可以是区域布线。通道布线是在总体布线的基础上在一个矩形区域内确定线网的走线位置。从数学上讲，区域布线和总体布线是一类问题，而且许多算法是相通的。当总体布线图上所有边的容量均不超过1时，它就是一个基于网格的区域布线问题。下面讲的线网布线是总体布线和区域布线的基础。1.2.1总体布线介绍两端点线网的总体布线[14…16][20…22

7、]主要是在布线图中寻找最短布线路径并使得期望的目标函数最优，同时在线网路径的分配中必须满足布线图中对应的边（通道）容量的限制。而多端点线网的总体布线可定义成一个寻找连接树问题。斯坦纳树是一棵连接特定要求点集合和一些其它成为斯坦纳点的连接树，其中斯坦纳点的数量是任意的。由于它具有比其它方法求得的连接树总长度更小的优点，往往被用来作为在总体布线中构造连接树的方法。于是，总体布线问题实际上就是在一个总体布线图中，在期望目标函数最优化的条件下，针对每条线网寻找一棵斯坦纳树的问题。通常目标函数是所选择的连接树的总长度最小。一般的总体布线问题可定义

8、如下：给定一个网表NNNN={,,...,}，和一个总体布线图GVE=(,)，对12n∀∈≤≤NNin,1，找到一棵斯坦纳树T，使得ii第2页上海交通大学工程硕士学位论文第一章前言n最小化∑LT()ii=1