图的steiner最小树构建与其布线应用

《图的steiner最小树构建与其布线应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第一章引言研究动机和背景自从1958年美国德州仪器和仙童公司分别研制出世界上第一块集成电路(IC)，人类开启了微电子和信息时代的大门。随着计算机、网络以及各种移动终端的普及，集成电路技术在推动人类生活和生产方式的变革中发挥了举足轻重的作用。在短短50多年的时间，集成电路经历了小规模集成(SSI)、中规模集成(MSI)、大规模集成(LSI)的发展阶段，目前己进入了超大规模集成(VLSI)和特大规模集成(ULSI)阶段，形成了片上系统(Systemonchip，SOC)和片上网络(Networkonchip，NOC)的时代。遵循著名

2、的摩尔定律[1】，集成电路芯片上晶体管的集成度按指数级的速度不断增长着，同时芯片的特征尺度也从早期的微米级别、深亚微米级别进入了如今的纳米级别。2012年Intel发布的酷睿i7四核处理器，芯片的特征尺寸已达到了22nm，集成的晶体管的数量也达到了惊人的14．8亿[2]。根据国际半导体技术发展路线图ITRS2011公布的数据【3]，2016年处理器将以1lnm工艺制造，片上能集成的晶体管数量可以达到1280亿。随着半导体制造工艺的发展以及芯片设计规模指数级的增长，电子设计自动化(ElectricDesignAutomation，EDA)

3、技术已成为了电子设计技术的核心【4】。EDA技术是以计算机和微电子技术为基础，汇集了计算几何、拓扑学、逻辑学、计算数学等多学科的最新研究成果，来自动化地实现电路的综合、分析、仿真等工作。目前，EDA技术已经覆盖了电路设计的整个流程。如图1．1所示，EDA软件成本占了现代芯片设计制造成本中相当大的比重。fiRS2009芯片成本f璺位：百万S)200920102011201220132014加1520162017∞182lDt920202021202220232024●硎牛消毒自戎本囵EDA软件消幕目j5：本图1．1芯片设计制造成本[4]l

4、O0O0加∞O万方数据第一章引言随着计算机、通信、消费类电子、移动互联网的蓬勃发展，人们对高性能、低功耗芯片的需求曰益增长，这对EDA技术带来了更多的挑战。一方面，特征尺寸的下降、次级物理效应的凸显，使得现有的EDA技术需要考虑更多可实现性、成品率等问题。另一方面，芯片规模的增长、从设计到投入市场的时间(TimetoMarket，TTM)不断缩短，对EDA设计算法的性能提出了更多更高的要求。因此，研究EDA领域所出现的新问题，并设计更高效的EDA算法，对于满足日益复杂困难的集成电路设计制造具有极其重要的意义。1．1VLSI设计流程及物理

5、设计集成电路的设计周期一般包括：设计，物理设计，设计验证，制造，【系统规范说明◆功能设计J逻辑设计◆电路设计J物理设计1Ir设计验证———]_—一测试封装系统规范说明，功能设计，逻辑设计，电路封装和测试等。其流程如下图1．2所示：电路划分J布图规划J布局J布线J压缩图1．2VLSI设计流程及物理设计物理设计也称版图设计，通常是VLSI设计中最耗时的一步。物理设计需要根据电路和工艺要求完成芯片上单元或功能块的几何安置以及它们的互连。它既需要将每个元件的电路表示转换为几何表示，同时也要将元件间的互连线转换为圄豳卤圆窜虿万方数据第一章引言几何

6、连线图形。所有几何表示需要符合制造工艺相关的设计规则的约束。由于物理设计的复杂性，通常将它进一步分解为如下几个子步骤：电路划分，布图规划，布局，布线和压缩等。电路划分过程是将电路分组，形成多个模块，简化问题规模。布图规划和布局过程是确定各模块在芯片上的精确位置，主要的优化目标是最小化芯片的面积，同时满足工艺需要的设计规则约束。布线包括总体布线和详细布线两个过程，实现各模块之间的互连走线以及生成各线网的几何版图，主要优化目标包括互连线最短、通孔数最小等。压缩是布线之后的优化过程，通过从各个方向上压缩版图来实现芯片面积的进一步减少。物理设计

7、直接影响着芯片的性能、面积、功耗、可靠性和良率等，因此物理设计的高效算法显得尤为重要。通常，物理设计涉及的都是具有多优化目标的组合最优问题，如满足芯片面积最小、线长最短、通孔数最少等。由于优化问题的复杂性，实际物理设计是各个步骤反复迭代求解的过程。为了得到一个好的布图结果，可能需要反复进行布局和布线过程，后一个步骤的结果依赖于前一个设计步骤，因此好的物理设计需要注意各个布图步骤间算法优化目标的一致性，前面阶段的算法需要尽可能考虑到对后续阶段的影响[5]。1．2互连线对集成电路的影响在集成电路发展的早期，芯片的性能(速度、功耗、面积等)主

8、要取决晶体管的性能，互连线被认为是理想的连接，不考虑其引入的寄生效应。然而，随着芯片的特征尺寸的不断减少，集成电路进入了SOC时代。如今最先进的微处理器芯片内部集成了上亿的晶体管，铜互连线高达10多层，互连