（微电子学与固体电子学专业论文）基于序列对的集成电路版图布局算法研究.pdf

y 6 8 9 2 0 1 浙江大学硕士学位论文 基干序列对的集成电路版图 布局算法研究 摘要 集成电 路 版图 ( l a y o u t ) 设 计或物理设 计( p h y s i c a l d e s i g n ) 是v l s i 设 计中重要的一环， 也是最费时的一步。由 于布图的复杂性， 整个布图过 程往往分成划分、 布图规划、 布局、总体布线、 详细布线和压缩等若干 步骤， 每一步骤完成布图的一部分工作口 本文目前所做的研究处于布图 规划和布局设计阶段。 本文综述了各种布图表示方法， 并对比各种方法 的 优 缺 点 ， 在 此 基 础 上 选 9 y r d 对 ( s e q u e n c e p a ir , 留 ) 作 为 丰 到燮兰 互 基 础。以 模拟退火算法作为程序框架， 实现了多种布局方法， 其中提出了 一种增量式的布局算法， 该算法原理简单、 通用， 可用于任何的实现框 架之中， 在优化效果和运行时间上都具有一定的优势。 文中还实现了两 个流行的用于搜索的数据结构: 平衡止叉搜索树和优先级队列， 并且把 它们用在基于s p的版图布局中以加快运行速度。对一个给定的布局产 生期序列对在很多情况下也是必须的， 本文提出了一种快速的序列对的 产生方法和相应的一 个简便的算法。 该算法性能优越， 实现简单， 并利 用它证明了 对于n 个模块组成的布局， 若模块之间的几何关系只有水平 和垂直两种， 任何的p * - a d m i s s i b l e 的表示方法， 其解空间的大小必须是 ( n ! ) 2 。 最后开发并应用了 一个版图 的显示 程序， 该程序可 以 利用多 屏显 示技术以方便版图信息的显示。 关键词: 物理设计， 序列对， v l s i ， 版图， 模拟退火算法， 布局， 布图 规 划 摘要 ab s t r a c t l a y o u t d e s i g n o r p h y s i c a l d e s i g n i s t h e m o s t i m p o r t a n t a n d t i m e - c o n s u m i n g s t e p o f i c d e s i g n . d u e t o t h e c o m p l e x i t y o f a fl o o r p l a n , p h y s i c a l d e s i g n i s o f t e n d i v i d e d i n t o a s e t o f s t a g e s , s u c h a s p a r t i t i o n , fl o o r p l a n n i n g , p l a c e m e n t , r o u t i n g a n d c o m p a c t i o n e t c , e a c h o f t h e s t e p s s o l v i n g a s u b - p r o b l e m . r e s e a r c h e s m a d e i n t h e p a p e r f o c u s e o n t h e s t a g e s o f fl o o r p l a n n i n n g a n d p l a c e m e n t . mo s t r e p r e s e n t a t i o n s f o r fl o o r p l a n s w e r e r e v i e w e d a n d c o m p a r e d , a n d s e q u e n c e p a i r ( s p ) w as s e l e c t e d a n d h i g h ly r a n k e d , o n w h i c h s t u d i e s w e r e m a d e a n d s e v e r a l e v a l u a t i o n a p p r o a c h e s w e r e i m p l e m e n t e d , i n t h e f r a m e w o r k o f s i m u l a t e d a n n e a l i n g a l g o r i t h m . a n i n c r e m e n t a l fl o o r p l a n a l g o r i t h m w as g i v e n w h i c h i s a g e n e r a l a n d c o n c i s e t e c h n i q u e a n d o u t p e r f o r m s o t h e r s . t w o p o p u l a r d a t a s t r u c t u r e s w e r e a l s o d e s i g n e d , n a m e ly b s t r e e a n d p q u e u e , t o s p e e d u p t h e e v a l u a t i o n . a q u i c k g e n e r a t i o n m e t h o d a n d i t s c o r r e s p o n d i n g a l g o r i t h m w e r e i n t r o d u c e d a n d v a l i d a t e d . t h e a l g o r it h m s h o w e d it s h i g h p e r f o r m a n c e i n r u n n i n g t i m e . i t i s s h o w n t h a t t h e s o lu t io n s p a c e s iz e o f a p * - a d m i s s ib le r e p r e s e n ta t io n i s ( n !) 2 , w it h b l o c k r e l a t i o n s o n l y v e r t i c a l o r h o r i z o n t a l . a m u lt i - h e a d p r o g r a m t o d i s p l a y t h e fl o o r p l a n s e ff i c i e n t l y w a s a l s o d e v e l o p e d a n d e m p l o y e d , w h i c h u s e t h e x i n e r a m a t e c h n o l o g y . k e y w o r d s : p h y s i c a l d e s i g n , s e q u e n c e p a i r , v l s i , l a y o u t , s i m u l a t e d a n n e a l i n g , p l a c e m e n t , f l o o r p l a n 浙江大学硕士学位论文 基子序列对的 集成电 路 版图 布局算 法研究 一 气 母 第1 章 计算机辅助布图设计 1 . ， 摘要 本章首先介绍了计算机辅助设计在集成电路产业中的必要性， 然后简要介绍了 集成电 路的设计流程和布图 设计以 及布图设计自 动化的 概念， 尤其是和本文关系密 切的物理设计中的布图规划和布局的 概念。 然后提出了 集成电路技术在物理设计方 面的发展和挑战， 概述了国内外的产业现状。 最后提出了 本文所做的 研究的方向和 内容。 1 .2概述 自 从1 9 5 8 年 集成电 路 诞生以 来， 已 经 历了 小 规 模集成 s s i ) 、 中 规模集成 ( m s i ) , 大 规模集成 ( l s i ) 的 发展阶段，目 前已 进入 超大规 模集成 ( v l s i ) 和特大规 模集成 ( u l s i ) 阶 段， 是一 个“ s y s t e m o n c h ip ” 的 时代。 集 成电 路 技 术迅速向 着更 高集 成 度、 超小型化、高性能、高可靠性的方向发展，一个芯片上可集成高达几亿，甚至几十 亿个晶体管. 集成电路技术的飞速发展除了 工艺技术、设备和材料等因素外， 计算 机辅助设计技术的进步也是一个不可忽视的原因。 并且， 随着集成度的提高， 芯片 内部晶体管数目 越来越多， 使得集成电路设计的复杂性也越来越高。 v l s i的 进一 步发展离不开设计自 功化( d a ) 和计算机辅助设计( c a d ) . 集成电路设计包括了功能设计、 逻辑设计、电路设计、 版图设计、设计验证和 制造等过程。 在整个设计过程中， 版图 设计( 或 称为物理没计) 是其中 重要的 一环， 它是在几十平方毫米的硅片上完成单个芯片已可以制作台几百万个晶体管的一个 完整的数字系统或数、 模混合的电 子系统， 在整 个设计过程中，版图 ( l a y o u t ) 设计 或 称 作物理设 计( p h y s i c a l d e s i g n ) 是 其中 重要的 一 环。 物理设 计是 最复 杂也是v l s i 设计中最费时的一步， 它要把每个元件的电 路表示转换成几何表示。同时， 元件间 的连线也要被转换成几何连线图 形. 我们把电 路的几何表示叫作版图， 而把版图的 设计称为布图。 版图设计要符合与制造工艺有关的设计规则的要求。 由于布图的复 杂性，整个布图过程往往被分成包括划分、 布图 规划、 布局、总体布线、详细布线 和压缩等若干子步骤， 每一步骤完成布图的一部分。此外， 对布图对象作某些限制 也会有利于简化问题。 版图设计自 动化涉及的几何图形很简单，包括矩形、 直角多边形相连线。 但布 图算法涉及了图论、 组合优化、 线性规划、 非线性规划以 及运筹学等. 布图算法的 实现则又要涉及到版图的数据结构和数据管理【 1 0 第一章 计算机辅助布图设计 i . a . i 计算机辅助设计的必要性 集 成电 路 ( i n t e g r a t e d c ir c u it ) 是 在半导 体( 或绝 缘体 ) 衬底上 做成的 完整的电 子 线 路， 它是5 0 年代末期随着硅晶体管的平面工艺的发展而出现的一种新型电子器件。 集成电路以 其信息含量大、 发展快、 渗透力强而成为本世纪最重要和员有影响力的 产品和技术，并成为国民经济中具有战略重要性的基础工业。 集成电路的产生相发 展对电 于工业和其它工业产生了巨大的 促进作用， 尤其是对计算机的发展产生了 革 命性的影响。而计算机科学技术的 发展又促进了i c的迅速发展。 计算机辅助设计( c o m p u t e r a id e d d e s i g n ， 简称c a d ) 是以 计算机为主要工具的 设计方法， 是计算机的一个很重要的应用领域。 它是在计算技术、 模拟理论和应用 数学等基础上发展起来的一门 新的而又发展极为迅速的学科，目 前已广泛应用于各 个领域。 电子线路的c a d则是c a d技术中发展较早和较成熟的一个方面。 由于集 成电 路的发展极为迅速， 因 此集成电 路计算机辅助设计( 简称i c c a d ) 又是一门 新兴 的学科， 尤其是大规模和超大规模集成电路的计算 机辅助设计， 目 前仍是许多专家、 学者努力探索的领域，新的设计理论、新的实用的设计系统层出不穷。 随着电 路与系统的日 趋复 杂， 标志着i c 水平的 两大指标 集成度( i n t e g r a t e d l e v e l) 和工艺恃征尺寸( i c f e a t u r e s iz e ) 也在迅速发展。就集成度而言， i c的发展可 分为以下几个阶段: 1 ) s s i ( s m a l l s c a l e i n t e g r a t e d c ir c u it ) 小 规 模 集成电 路。 2 ) m s i ( m e d i u m s c a l e i n t e g r a t e d c ir c u it 卜一 . 中 规 模 集成电 路。 3 ) l s i ( s c a l e i n t e g r a t e d c ir c u it ) 大规 模集 成电 路。 4 ) v l s i ( v e ry l a r g e s c a l e i n t e g r a t e d c ir c u it )大规模集成电路。 5 ) u l s i ( u l t r a l a r g e s c a le i n t e g r a t e d c ir c u it ) - 特大规模集成电路。 6 ) g s i ( g i g a n t i c s c a l e i n t e g r a t e d c i r c u it ) 巨 大规模集成电路。 这几个发展阶段中，目 前处于v l s i 向g s i 发展的阶段。 以i n t e l 公司的微处理器的发展史为例，更能说明集成电路的迅速发展。 通常 用m o o r e 定律来说明和预测集成电 路的发展，即每经过 1 8 个月，集成电路的 性能 就翻番，在过去的3 0 年间，一块芯片上集成的晶体管数目 增加了2 .2 万倍。例如， 1 9 7 1 年问 世的4 0 0 4 微处理器芯片上仅有2 3 0 0 个晶体管， 到 1 9 9 7 年发布的p e n t i u m i i 芯片上增加到7 5 0 万个晶体管，到2 0 0 0 年的p e n t iu m 4己 经接近5 亿个晶体管， 见cm i - 1 。 浙江大学硕七学位论文基于 序列 对的 集成电路 版图 布局算法研究 m oore s la wt r a n s i s t o r s 1 0 0 , 0 0 0 , 0 0 0 1 9 7 0 1 9 7 5 1 9 8 0 1 9 8 51 9 9 01 9 9 5 2 0 0 0 2 0 0 5 图 1 - 1 摩尔 x律( m o o r e s l a w ) 由 于i c的 发展 进 入v l s i 阶 段或 ( 称为 达到v l s i 水平 ) 之后， 各方面都与 一 般 的i c有了很大的不同，其独特之处在于; ( i ) v l s i 综合体现了 半导体工艺技术和电 路设计、系统结构设计的全面成果。 ms i 是器件和电路设计的结合， l s i 是逻辑设计和元件设计的结合， v l s i 则是体系 设计、 逻辑设计、电 路设计及半导体材料与工艺设计、 测试技术和图形的产生等的 综合。 ( 2 ) v l s i 是系统的集成。目 前一个v l s i 芯片上的管子数已达几十万个甚至几 百万个，它的功能可以是一个完整的系统。 ( 3 ) v l s i 中的 所有元器件及其连接是整体封 装的， 各个子系统或电 路， 只能 在 芯片封装后才能测试，如果发现差错或缺陷，将无法进行修理和调整，v l s i的设 计成功率应要求 工 00%。 ( 4 ) 一 般说来， 有源元 件仅占v l s i 芯片面 积的1 0 % - - 2 0 %，芯片的大部分面积 用于连接线、 焊点、 无源元件， 为了使连线最短且占 用面积最小，版图设计的最优 化至关重要。 ( 5 ) v l s i 中的连线宽 度达到了亚微米的量级，因 此 v l s i 制造中要采用超微细 加工技术。 综上所述，对于v l s i 这样的 极其复杂的电 路系统，要使其可靠性强、可测性 高、 研制周期短、 成本低， 单靠人工设计是难以 完成的， 必须采用计算机辅助设计。 例如， 要设计含有4 5 万个管子的3 2 位字长的微处理器芯片， 如果用于上操作， 则 需要 1 0 0 个人年，按目 前的技术发展，这显然是无法接受的。 集成技术的发展使得在一个芯片中可以集成数以亿计的器件， 并且可以集成不 第一章计算机辅助布图设计 同类型的电路，甚至可以将微机械结构集成到硅片上，形成微机电系统( m e m s ) 。 这样的多元化的集成芯片已经成为一个能够处理各种信息的集成系统，这就是所谓 的片上系统或称为系统芯片s o c ( s y s t e mo nc h i p ) 。 一个集成系统通常由一个主控单元和一些功能模块构造而成。主控单元通常是 一个处理器，这个处理器既可以是一个普通的微处理器的核( c o f e ) 。也可以是一个 数字信号处理器( d s p ) 的核，还可以是一个专用的运算逻辑。在这个主控单元的 周围，根据系同所要完成的工作配置一系列的功能模块，完成信号的接收、预处理、 转换以及信号的驱动与执行等任务。 在s o c 上可能集成了传感器( m e m s 元件) 、模拟信号处理电路、模数数模 转换电路、数字信号处理电路等多元化的模块。在s o c 中，将硬件逻辑与智能算 法集成在一起，形象地说，智能算法好像是一个人的大脑，硬件逻辑电路好像是人 的躯干和神经网络，传感器好像是入的五官。传感器感知外界的信息，通过神经网 络传给大脑，经过判断和运算得出正确的结果，并通过躯干产生行为。 从系统集成的角度看，s o c 是以不同类型的电路集成、不同工艺的集成作为支 持基础的，所以，要实现s o c ，必须重点研究器件的结构与设计技末，v l s i 设计 技术，工艺兼容技术，信号处理技术、测试与封装技末，等等。 实际上，随着工艺技术水平的不断提高，i c 的规模越来越大，早期的人工设计 已被计算机辅助设计所取代。现在人们所关心的是i c c a d 系统( 包括软件和硬件) 的先进性、可靠性和自动化程度的高低等因素，用分立元件进行电路模拟实验而后 进行电路设计的方法在许多情况下已经没有意义，而且i c 设计的最终目标电 路版图的实现也早已不是人工所能完成的。因此，离开i c c a d 系统进行i c 设 计已成为不可思议的事情，或者说，没有i c c a d 系统，比设计将寸步难行f 7 1 。 1 2 2 设计流程 v l s i a s i c 设计过程可以简要概括! l u t i 【2 】 1 2 2 1 系统规范说明( s y s t e ms p e c i f i c a t i o n ) 周其它设计一样，v l s i 设计首先要给出待设计系统的规范说明，包括系统功 能、性能和物理尺寸此外，还需要考虑选择设计模式和制造工艺。最终结果是确 定芯片尺寸、工作速度、功耗和系统功能。分析并确定整个系统曲功能、要求达到 的性能、物理尺寸，确定采用何种制造工艺、设计周期和设计费用。建立系统的行 为模型，进行可行性验证 1 2 2 2 功能设计( f u n c t i o nd e s i g n ) 这一步骤包括系统划分( s y s t e md i v i s i o n ) 。将系统分割成各个功能干模块，给 浙江大学硕士学位论文 基于序列对的集成电路版图布局算法研究 出子模块之间信号连接关系。验证各个功能块的行为模型，确定系统的关键时序。 功能设计主要是考虑系统的行为特性，常用的方法是时序图或者表示各于模块间关 系的关系图利用这些信息可以改进整个设计过程或简化后续的设计步骤。 1 2 2 3 逻辑设计( 1 0 9 i cd e s i g n ) 这一步骤也叫逻辑设计与综合( l o g i cd e s i g na n ds y n t h e s i s ) ，将划分的各个于 模块用文本( 网表或硬件描述语言) 、原理图等进行具体逻辑描述。对于硬件描述 语言描述的设计模块需要用综合器进行综合获得具体的电路网表文件。对于原理图 等描述方式描述的设计模块经简单编译后得到逻辑网表文件。可以得到一个表示系 统功能的逻辑结构并反复测试其正确性。设计者通常用文本、原理图或逻辑图表示 设计，有时也用布尔方程表示设计。在设计过程中，还需要综合后仿真( s i m u l a t ea f t e r s y n t h e s i s ) 从上一步得到网表文件，在这一步进行仿真验证正确性，并对其进行优 化设计或称之为逻辑最小化。 1 2 2 4 电路设计( c i r c u i td e s i g n ) 电路设计时要考虑逻辑部件的电路实现，包括速度和功耗此外，还要注意各种 元件的电性能通常用详细的电路图表示电路设计 1 2 2 5 物理设计( p h y s i c a ld e s i g n ) 物力设计及版图设计，是v l s i 设计中最费时的一步。物理设计要把每个元件 的电路表示转换成几何表示，同时，元件间连接的线网也被转换成几何连线图形。 我们把电路的几何表示称为版图。版图设计要符合与制造工艺有关的设计规则要 求。由于版图设计的复杂性，往往把版图设计分成若干子步骤进行。 1 2 2 6 设计验证( d e s i g nv e r i f i c a t i o n ) 在版图设计完成并得到以几何图形形式表示的版图以后，要进行设计验证、也 称版图验证，以确保版图满足制造工艺要求和符合系统的设计规范版图验证包括 版图原理图e b 对( l v s ) 、设计规则检查( d e s i g nr u l ec h e c k i n g ，d r c ) 、版图的电路 网表提取m e t l i s te x t r a c t i o n ，n e ) 、电学规则检查( e l e c t r o n i cr u l ec h e c k i n g ，e r c ) 和寄生参数提取( p a r a m e t e r e x t r a c t i o n ，p e ) 、把取出地参数反标注( b a c k a n n o t a t e ) 至网表文件，进行最后一步仿真验证工作。经过验证后的版图可以送去制作掩模版 并用于制造芯片。 1 2 2 7 制造( f a b r i c a t i o n ) 送i c 生产线进行制版，光罩和流片，进行试验性生产。芯片制造过程包括硅 片准备、杂质注入、扩散、光刻等工艺。 第一章计算机辅助布图设计 1 2 2 8 封装和测试( p a c k a g ea n dt e s t ) 在完成芯片制造后，要进行封装和测试。安置在印制电路板( p r i n t e dc i r c u i t b o a r d ，p c b ) _ e 的芯片可封装成不同形式，用于多芯片模块( m u l t i p l e - - c h i pm o d u l e ， m c m ) 上的芯片可不封装 v l s i 设计可能会在一个步骤中或在几个步骤之间反复交替进行，其设计流程 如图1 - 2 所示。v l s ic a d 的目标就是要尽量减少这种反复次数以缩短产品进入市 场的时间。 系统描述 l 功自e 设计 l 逻辑设计 电路世计 物理设计 设计验证 i 芯片制造 测试封装 图1 2 简化的设计流程 数字和模拟a s i c 的设计流程和相应工具的使用分别如图1 - 3 和图1 - 4 所示。 浙江大学硕士学位论文基于序列对的集成电路版图布局算法研究 一- 第一章计算机辅助布圈设计 a n a l o gi cr e f e r e n c ed e s 蝰nf l o w 模拟电路参考设计流程 图i - 4 a n a l o gd e s i g nf l o w 8 - 浙江大学硕士学位论文基于序列对的集成电路版图布局算法 研究 1 . 2 . 3版图设计的方法 版图 设计的常用方法 有: 全定制、半定制、定制、 积木块布m ( b b l ) 、 现场可 编程和硅编译法等。 版图设计( 又称布图设计，l a y o u t ) 的任务就是在一定的设计指标、电气性能等 条件的约束下，在一块芯片上安置所有的单元电路，完成各单元之间的电学互连， 并使占用的芯片面积最小相连线总长度最短。目 前版图设计是 v l s i 研究领域中最 为 活跃的 一 个分支。 版图 设 计的中 心课 题是 布 局 ( p l a c e m e n t) 和布线 ( r o u t i n g ) 。 布局 和布线的算法已有很多，图论在版图设计中得到了一定的实际应用。 1 .2 .3 . 1 全定制法 ( f u l l c u s t o m d e s i g n ) 这种方法通常利用人机交互图形系统， 由 版图设计人员人工地完成各个器件和 连线的版图设计、输入和编辑，实现电路图到版图的转换。 全定制版图设计的特点是充分利用设计人员的经验与创造力， 尽可能地对每个 晶 体管的电 路参数与版图 参数进行优化。 所以 这种设计方法既有最佳电 路性能( 包 括速度和功 耗) 、 最小芯片面 积的 优点，也存在低效率、高成本、 设计周期长的 缺 点。 全定制版图设计适合于那些生产批量大、电路结构重复性强、 数模混合以及有 特殊要求的电 路， 如r a m . r i s c 、 阵列机、 高压功率集成电路、 集成硅传感器等。 而对于多 数大 规模和超大 规模专用集成电 路 ( a s i c ) 就不适合了。 全定制的设计方法除了 要求有人机交互的图形系统支持外， 还要求有完整的检 查和验证的c a d工具，因为设计人员不可避免会造成版图上的某些错误， 需要通 过自 动的工具加以箱底地纠正。 这些工具包括设计规则检查、电学规则检查、 连接 性检查、版图参数提取、版图与电路图一致性检查等。 1 .2 .3 .2 门阵列法( g a t e a r r a y ) 门阵列是在一块芯片上把门排列成阵列形式。 每个门具有相同的版图形状，门 与门之间暂不相连，因此构成一个未完成的逻辑阵列。 严格地说，门阵列是把单元 ( 若干 器 件) 排 成阵列 形式， 每个 单 元内 含有 若干 器 件， 通过连接单元内 的 器件使每 个单元实现某种类型门的功能，并通过各单元之间的连接实现电路的要求。 早期门阵 列中的单元是等高等宽且面积相同， 因此可以来用统一的掩膜， 预先 完成连线以 外的芯片加工步骤，即 产生母片( m a s t e r s l i c e ) 。不同规格的门阵列，母 片上的单元数目 也不相同，因而选择性很大。 对于一个具体的电路， 只要选择规模 合 适的 母片， 进 行接触孔 相连 线的 掩 膜 版设 计与 制作 ( 一 般为2 -4 层掩 膜) ， 再 完成 其它工序即可，因此也可把门阵列看成是一种掩膜可编程的功能器件。 因为母片己完成了芯片制造工序的绝大部分， 并且是经大批量制造后作为备用 第一章 计算机辅助布图设计 的， 所以电路从设计到芯片完成的整个周期放大大缩短， 制造成本也大大下降。 通 常一个典型门阵列的制造周期， 是所有掩胶版都要单独设计和制作的常规芯片制造 周期的一半，成本为通常情况下的1 / 4 -1 / 8 a 门阵列的设计方法适合于周期短、 批量小的电路产品。所以 它在a s i c领域得 到广泛应用。它的缺点是芯片面积利用率低、速度慢、功耗较大、门延迟的均匀性 差 。 1 .2 .3 .3 门 海法( s e a o f g a t e ) 为了克服面积利用率低的缺点， 提出了一些改进方案。 例如单元采用栅隔离方 式， 取消布线通道等方案。 现代的门阵列设计方法除了母片预制、 布线通道固定外， 与 标 准 单元没 计 法基本相同。 无布线 通道的门 阵 列常 被 称为“ 门 海” ( s e a o f g a t e s ) 或 密 集型门 阵 列 ( c o m p a c t e d a r r a y ) ， 它 进一 步改进了 宏单元元阵列的 版图 结构. 它 取消了 水平方向的 通道， 成为一种无通道( c h a n n e l - l e s s ) 的门阵列。在需要时 将某些 单元区域作为布线区， 这样的布线区宽度可变。它仍然保留了半定制设计力法的优 点， 提高了芯片利用率， 但给自 动布局布线带来了 难度。门 海的布线区类似于b b l 那样的结构，因此，门 海模式的布图算法十分类似b b l模式. 1 .2 .3 .4 标准 单元法 ( s t a n d a r d c e l l) 标准单元法是库单元设计方法中的一种。 标准单元法中的各个单元具有同一高 度 ( 指 版图 尺寸 ) ， 但宽 度不 等。 单元内 的 每个器 件事 先 都经过糟心地设计， 并 经过 设计规则和电 学性能的验证。设计好的各个单元存入 c a d系统的单元库中以 便调 用。 每个单元都有三种描述形式:逻辑符号、拓扑版图和掩膜版图。它们可在设计 的不同阶段被设计系统所调用。 设计时将所需的单元从单元库中调出， 将其排列成 若干行， 行间留有布线通道。 然后根据网络的连接关系用连线联接起来，同时把相 应的输入/ 输出单元和压焊块连接起来，即得到所要求的芯片版图。 标 准单元的 版图 设计与 通常的 版图设 计有所不同。 它要求单元输入和输出 ( i / o ) 端排列 在单元的上下两端， 且希望每 个1 / o端在单元的上下两个方向都能引 入 或引出，以 利于通道布线。 标准单元设计方法由于芯片只包含那些有用的单元， 所以芯片面积利用率比门 阵列要高。 但由于其掩膜版图全部需要定制，而不像门阵列可以事先完成部分加工 工序，所以其设计周期与成本要高于门阵列。它适用于有一定批量的a s i c产品设 计。 目 前已有很好的c a i 工具支持全自 动化的标准单元版图布局布线。 近几年来， 由于自 动布图技术的 发展， 一些标准单元自 动布图系统可以处理芯片上有少量的宏 单元( 它的 大小不受库单元等高的限 制) 的 版图自 动设计。 浙江大学硕士学位论文基于序列对的集成电路版图布局算法研究 1 . 2 . 35积木块 法 积木块法( b u i ld i n g b lo c k l a y o u t , b b l ) 也是 库单 元设计方法的一种。 它与标准 单元法不同 之处在于，它既不要求每个单元( 或 称积木块) 等宽，也不要求等高。每 个单 元 ( 各 种门 单元、 寄 存 器、 r a m , r o m 、 时 钟发生 器等 ) 都可以 根据 最合理的 情 况单独进行版图 设计，因而可获得最佳性能。 设计好的单元存入库内。 此外， 与标 准单元有所不同的是，它没有统一的布线通道。 由 于 布线 通道 不 规则， 加上 各单 元的 连 线 端口 处 于单元的四 周， 且端口 位置 也 不规则，给自 动布局和自 动布线带来很大的困难，因此进行 b b l法自 动布局布线 的方法研究是一个很重耍的领域，现己 有这种系统推出，但仍在不断改进之中。 一般说采用b b l法布局分为初始布局和迭代改善两个过程，简单方法是人机 交互法。即采用 b b l法设计时， 先把各所需的 单元调到屏幕上做出合适的版图布 置，一般把那些会影响延时的单元尽量靠拢安放，然后通过软件工具预估其性能， 如果不合适， 可调整版图 布置。 一旦确定下来， 再进行详细的布局和布线， 这时原 版图 布置会有所变动以 适应布线的 要求。 在布局和布线完成以 后，再进行一次( 版 图后) 模拟以 确定该芯片设计是否符合要求。 本文所做的研究工作主要就是针对积木块法的布图。 1 .2 . 3 6 现场可编程门阵列 现场可编程门 阵列( f ie l d p r o g r a m m in g g a t e a r r a y , f p g a ) 是一种可编程器 件 ( p r o g r a m m a b le l o g ic d e v ic e , p l d ) ， 它是 近 几 年 迅速发 展起来 用于a s i c 设 计的 一 种新方法。f p g a提供了用户可编程和自己制造的能力，极大地缩短了设计和制造 时间， 节省了 费用. f p g、 设计方法与 传统门 阵 列设计方法( 也把它称为掩模编程一 -m p g a 的 有很大的区 别。 一个f p g a芯 片由 若干个可编程的 逻辑模块组成， 它们 既可以被排列成如门阵列那样的模块阵列， 也可以被排列成如宏单元阵列那样的行 模式， 也可以 被排列成如门 海那样无通道的 模块阵列。 这些逻辑模块可用一个可编 程的布线网络进行互连。 一个典型f f g a逻辑模块比门电 路复杂， 但比 标准单元设 计中的单元简单. 1 .2 . 3 .7 硅编译器 硅编 译器 ( s il i c o n c o m p il e r ) 是一 种 理 想的自 动化工具， 这是在7 0 年代末出 现的 一种将数字电 路的行为级描述转换成芯片掩膜版图的设计技术， 这种转换与软件编 译器符高级语言转换成机器语言相似。 这种技术是自 动化程度最高的集成电 路设计 技术。 硅编译器通常可分为自 动逻辑综合和自 动布局布线两大部分。 前者由 行为描述 综合成与集成电 路制造工艺无关的 优化逻辑模块及网表信息; 后者则以这些信息为 基础生成与工艺相应的掩膜版图。 第一章 计 算机辅助布图设计 硅编译器的输入是用某种硬件描述语言对设计对象的行为描述， 同时还要输入 逻辑和电路形式等结构要求、时钟要求及工艺设计规则。 硅编译 器能自 动 地按 控制 流( c o n t r o l p a t h ) 和 数 据流 ( d a t a p a t h ) 对设 计对象自 顶 而下地分解为若干模块， 即完成模块化、 结构化描述。 多数硅编译器有功能模块和 基本单元库( 如存储器、 计数器、时 序控制器、 a l u , p l a . 1 / 0压焊点等) 。 有的 硅 编 译 器有带 参数 模块自 动生 成工 具， 如有限 状态 机任 i n i t e s t a t e m a c h in e ) 自 动生 成 器就是一种典型的控制逻辑生成器。 版图布局布线工具将各功能块合理地放置在芯 片的 特定位置上， 然后再按电 路连接信息完成布线。 对编译器的设计结果， 通常还 用分 析工具 模拟其时 域特性( 速度与功耗) 、 估算其芯片面积， 并将结果通知设计者， 以决定是否需修改设计。 作为一种 1 c自 动设计方法，硅编译器的设计效率很高，但由于自 动综合是一 个难度极大的优化问题，目 前硅编译器所设计的芯片版图面积仍然偏大， 这是硅编 译技术所要解决的难题。 1 . 2 .4 布图设计自 动化 集成电 路的 生产过程就是在芯 片 ( c h ip ) 上 进行一系列微细加工的过程， 为了 在芯片上精确确定的区域内进行扩散和最终布线的要求， 必须进行多次的光刻， 也 即需要一整套的光刻掩膜版。这些掩膜版 ( ma s k ) ,要求具有相当高的图形精度和 定位精度 ( 目 前已经达到 6 5 0 n m ) 。从某种意义上讲，掩膜版的制备是集成电路生 产的关键。 布图设计要解决的问题就是: 通过对给定电路的元、器件描述或单元描述、电 路的逻辑描述或连接性关系描述，电路的电性能参数描述及电路的引出接点描述 等， 确定电路的设计要求。 然后根据采用的集成电 路工艺条件， 将电路的描述自 动 地转变为集成电路制造所需要的掩膜图集。 简言之， 布图设计就是根据电路和工艺 的要求自 动完成芯片上元、 器件或单元一功能块的安置， 并实现它们之间所需要的 互连。 上面提到的生产工艺条件是指工艺类型、 布线层数及层特性、 连线宽度及间 隔、 通孔大小、接点尺寸、套刻精度等 6 . 在v l s i 布图设计中，一般并不直接以晶体管等电 路元件为基础来进行设计， 而是以 单元电 路 ( 逻辑门、寄存器等) 为基础。而单元电路的布图设计， 则一般由 人工完成或由 标准单元库提供。 如果我们把单元电 路的布图设计结果看作是带连线 接点的 模块， 那么v l s i 的布图 设计目 标就可以描述为这样一个问题。对给定的大 规模或超大规模集成电 路， 在满足各项电路及工艺要求的条件下， 如何在尽可能小 的区域内 ( 或在给定区域内) ，互不重迭地安置电路所需要的全部模块，并且完成 它们所有必须的互连。 在布图设计中，除了完成从电路图 ( 或逻辑图) 到掩膜图集的转换外，还将综 浙江大学硕士学位论文 基于序列对的集成电路版图布局算法研究 合地考虑下述设计目 标: 满足电 路的各项电性能参数的要求及工艺要求 使设计结果具有足够高的 集成度。 集成度指标通常以芯片上单位面积内 所含 晶体管或等价逻辑门的数量来表示。 使设计过程具有足够高的设计成功率，其中主要的是指布 线成功率。 使设计结果具有较高的设计质量，如尽可能 减少通孔数量、缩短连线长度、 使寄生参数的影响限制在电路所允许的范围之内等。 此外，还必须考虑设计周期，设计成本以 及结果验证等要求。 在具体电 路的设计过程中， 根据特定的工艺条件， 住往还会对布图设计提出一 些专门的要求。 如某些线网的树型要求、长 度限制等等。 这些要求， 在设计过程中 也必须加以 考虑。 1 .2 . 5 布局和布图 规划 作为集成电路自 动布图设计的重要环节之一， 布局就是把元件或模块安置在芯 片或印制电路板的适当位置上， 并使其满足一定的目 标函数。 布局阶段的输入是一 组模块、 各模块上的引线端信息和网表。如果模块内的电路版图已经完成， 则该模 块的 形状 和大小己 知， 此类模块称为“ 硬模块” ( h a r d b l o c k ) ， 另一类需要在布局阶 段确定其形状和大小的 模块则 称为“ 软模块” ( s o ft b l o c k ) 。 通常所说的“ 布局问 题” 是指待安置的 模块均是硬模块。 此时， 只需考虑给每个模块在芯片上分配一个位置。 但是， 当 模块中 包含有软模块时， 此时的 布局问 题成为“ 布图 规划” ( f lo o r p la n n i n g ) 问 题。因 此， 布局问 题仅是布图规划问 题的一个特例. 在布图 规划问题中。 我们不 仅要确定每一个模块在芯片上的位置， 而且还要确定每个软模块的形状和大小 它 比 布局问 题更复杂 通常， 在完成布图规划后，还需确定软模块上的引线端的分配 ( p i n a s s i g n m e n t ) . 在布图规划中，我们只是在较高层次上完成了 对软模块的形状和大小的估计， 以 及它们的引线端的分配， 还需要真正实现这些软模块的物理设计。此时， 它们又 变成了 较低层次上的布局或布图 规划问 题， 布图 规划中得到的模块形状、 面积和引 线端位置则作为低层布局或布图规划的约束条件， 直到在一个足够低的 层次上， 我 们可以 用手工或自 动的方法完成这些软模块的物理设计，使它成为硬模块。然后， 我们再返回到较高层次上去做布局。 由于布图的对象不同， 布局问 题的详细含义和目 标会有所不同， 对于门阵列模 式和 p c b的 布局，布局问 题变成分配问 题，其目 标是达到较高的布通率; 对于标 准单元的 布局，目 标一般是芯片的面积最小或总连线长度最小;由于这两种模式都 是基于单元库的，而库单元总是事先设计并制作好，也就是说是硬模块.因此，这 第一章 计算机辅助布图设计 两种布图模式通常都只有布局问 题，而对于b b l模式和门 海模式的布局，所有模 块均为硬模块时为布局问 题， 其中一部分模块或所有模块均为软模块时则为布图规 划问 题。 在当前的多层布线工艺下， 有时要在标准单元中插人一两个大的 模块。 它 们可能是硬的， 也可能是软的. 通常把这种模式称作具有宏模块的标准单元布图模 式。因此，对于这种标准单元布图模式，也可能有布图规划问题。 在深亚微米工艺下， 互连线所造成的延迟已成为影响芯片性能的主要因素.因 此， 在布局时 必须考虑性能优化( p e r f o r m a n c e -d r i v e n ) 或时延优化( t im i n g -d r iv e n ) , 即还需要将连线延迟考虑在布局或布图规划的目 标函数中。 这样的布局和布图 规划 问 题称作性能驱动的 布局( p e r f o r m a n c e -d r iv e n p la c e m e n t / f l o o r p l a n n in g ) 或时延驱 动的布x( t im i n g -d r iv e n p l a c e m e n t 1 f lo o r -p la n n in g ) . 1 . 3集成电路技术的发展和挑战 半导 体行 业发展 迅 速， 根 据i t r s 2 0 0 4 1 0 ， 产品 时 代和芯 片大小 模型 在近 几年 又有巨大的进步， 2 0 0 3 年版的国际半导体技术蓝图规划出的中短期的解决方案， 未 来可能发展的技术节点( t e c h n o l o g y n o d e s ) 见表格 1 - 1 .硅片复杂度( s i l i c o n c o m p l e x it y ) 和 系 统 复 杂 度 ( s y s te m c o m p le x it y ) 带 来 的 挑 战 ， 加 上 生 产 率 ( p r o d u c t iv ity ) , 功耗( p o w e r ) ， 制造集成( m a n u f a c t u r in g in t e g r a t i o n ) ，串 扰( i n t e r f e r e n c e ) 和误差容限 ( e r r o