VLSI布局结构表示研究进展

《VLSI布局结构表示研究进展》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、VLSI布局结构表示研究进展作者：徐宁，洪先龙，董社勤2006.11摘要：超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化软件工具的支持。布局是布图设计中一个极为重要的环节。目前，在深亚微米、超深亚微米工艺下的超人规模、甚人规模集成电路设计中，布局结果的好坏直接影响整个布图设计，因此如何高效地表示布局结构，从而提高布局质量成为布图设计中的一个国际上的研究热点。文中介绍并分析了当前国内外比较流行的布局结构的表示方法研究工作的进展情况。关键词：VLSI；布局；结构表示；模拟退火布图设计过程包括划分、布图规划、布局、布线、压缩等。随着制造工艺进入了深亚微米工艺

2、阶段，电路的尺寸和复朵度迅速增加，布图规划和布局的地位显得比以往更加重要。(1)布图规划和布局是布图设计过程中的早期阶段，其完成质量的优劣对布线工作的顺利完成乃至最终芯片面积和性能的影响非常之大；(2)混合模式(MixeDModuleProblem,MMP)的设计越来越多;(3)模拟电路和数模混合电路在芯片设计屮的比例大幅度增加；(4)知识产权(IP)模块在VLSI设计中的应用增加:(5)多芯片模块(MCM)问题也H益受到重视。这些都为研究布图规划乃至布局工具提出了更高的要求。布图规划技术的产生主要是由于BBL(BuildingBlockLayout)模式分级设8BA1的需要。

3、BBL模式又称宏单元模式，是设计中最灵活的一种方法。在这种布局模式中，单元或模块可以有任意的形状和尺寸，可以安排在芯片的任意位置上而且没有固定的布线区域，因此具有更高的布局密度。BBL布局的过程就是将一组模块或单元安置在芯片合适的位置上，使芯片的面积最小、模块间的连线最短并容易布通。其输入一般包括:(1)-个由模块或单元组成的集合A={Mi,M2,Mm},其屮每个模块是有固定边长的矩形或具他形状的硬模块，或是面积固定而长宽比可以变动的矩形软模块。每一•模块Mi均有一个引线端的集合Pi={pii,pi2,.},其中每个引线端pij都被安置在模块的边界上。对属于电源线网的引线端，会

4、记录其所需的最大吸纳电流和允许的最低电压；(2)网表N={h，L2,.},其中每个线网Li是一个引线端的集合。属于同一个线网的引线端将由布线工具把它们连结在一起；(3)由用户给定的各种约束条件，如芯片的长宽比或芯片的最大长(宽)度等几何方面的约束，关于引线端或压焊块的约束，以及一纽路径或一组线网上的最人时间延迟即所谓时延的约束等。给定输入以后，需要确定所有模块的位置和方向，使得在满足所有约束条件的情况下，达到芯片面积的最小化。进入深亚微米乃至超深亚微米工艺阶段后，性能驱动或时延驱动的算法己经成为布图设计的热门课题。但由于约束或限制条件增多，设计过程中要考虑的因素也大人增加，因此

5、具复杂程度是前所未有的，更有效的时延佔计模型和时延驱动算法还有待于进一步的深入研究。其中布局结构的表示成为算法的核心部分，也成为EDA(ElecTronicDesignAutomation).!作者研究的热点课题。布局结构BBL布局结构通常有两种：一种是可二划分的结构(Slicing)；另一种是不可二划分的结构(Non-Slicing)o图1两种布局结构Slicing结构是具有特殊性的布局结构。如果一个布局具有这种结构，那么可以通过递归地使用垂直或水平划分线，把芯片或划分芯片后得到的矩形划分为两个部分，直到划分芯片所得到的每个子区域中只包含一个模块，如图1a所示。这种结构可以方

6、便地使用二叉树或波兰表达式的数据结构来表示，其布局解空间为0(m!23m-3/m15)；但是这种结构不具有一般性，因此可能会浪费芯片的面积。Non-SLicingNon-Slicing结构包括所有可能出现的布局结构，是一种更为一般的布局结构，如图1b所示。使用NomSlicing结构可以获得更高的布局密度，具有更大的优越性。由于Slicing结构只能解决部分布局问题，它是NomSlicing结构的子集，因此对NorvSIicing结构的布局结构表示研究成为热点。本文仅对Nori-Slicing结构的布局结构表示的研究进展进行论述。布局结构表示研究进展求解NomSlicing结构

7、的布局问题，就是要在众多的解屮寻找一个满足设计约束条件的、最优的解。随着电路规模的迅速增大，模块数越来越多，耍在合理的时间内找到最优解是不可能的，只能找到次优解。因此如何表示解，如何降低冗余解，从而降低解空间，成为求解布局问题的热点。布局表示就是用字母或数字代表各模块，并将其用一定的数据组织形式(如序列、树、图等)组织起来从而表达模块Z间的几何位置关系。对应着一个模块布局的序列、树或图称为编码。从编码到模块布局的映射称为解码。所有可能的编码形式称为这个布局表示法的组合空间或解空间。在20世纪