（计算机科学与技术专业论文）基于约束的vlsi布图算法研究与实现.pdf

分类号 u d c 一 密 级 劣j 凑程歹大穿 学位论文 题目基王约塞的y l 墨! 查图簋法硒究墨塞理 英文 题目c o n s t r a i n t - b a s e dv l s ip l a c e m e n ta l g r i t n c m sa n di m p l e i m c n t a t i o n s 一 研究生姓名奎耀龌 一 指导教师 姓名 副指导教师单位名称 职称学位- 邮编 4 3 0 0 7 0 申请学位级别亟 学科专业名称i 土簋扭型堂皇这苤 论文提交日期2 q ! ! 生垒旦 论文答辩日期2 q ! ! 生目 学位授予单位武这理王太堂学位授予日期 答辩委员会主席丝垒堂 评阅入至墨盐 堡亟奎 2 0 11 年5 月 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 期：塑坐堇：型 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位 论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或 其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认 可的国家有关机构或论文数据库使用或收录本学位论文，并向社会 公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) 磊耀凇导师( 签名) 错日期训、如v 中文摘要 当今，随着片上系统( s o c ) 以及片上网络( n o c ) 的不断发展，在层次化 设计中，许多学者根据芯片的性能和可靠性的需求，在布局中增加了一些与实 际需求相关的约束，其中包括模块间的位置约束，比如对齐约束、边缘约束、 性能约束、电性能约束等等。现代布局问题已经从简单的、传统的布局问题， 向具有各种条件约束的、复杂的布局问题转变。在解决带约束的布局问题时， 本文采用b 毒t r e e 表示法进行布局。它是一种灵活高效的有序二叉树表示方法。 本文针对两种约束布局进行了研究，即对齐约束布局和性能约束布局。由 于模块的排布是用坐标来表示，因此对齐约束可按方向分为水平方向对齐约束 和竖直方向对齐约束。本文基于b 母t r 表示法进行约束布局，实现了水平方向 对齐约束布局、竖直方向对齐约束布局和性能约束布局的混合约束布局。并深 入地研究了b 掌t r e e 的构造及特点，提出了三个对应约束的充分条件，提出优化 算法可快速筛选合法解。针对模拟退火算法，也提出了它的优化流程。即在每 次降温迭代的过程中，我们要检测其布局是否合法，如果是非法的，则动态的 将之合法化，完成此温度下的布局。在降温迭代产生新的解空间的过程中，加 入判断步骤以减少时间的开销来提高效率。实验数据验证，本文约束的实现是 成功的、优化流程是行之有效的。 随着v l s i 的不断大型化、复杂化，晶元的个数成指数增长，在现阶段芯 片的设计过程中，布局时延成了布图规划瓶颈。所以，把布局中一些重复劳动 省去，达到减少时延的目的增量式算法成为研究的热点。本文通过深入的分析 研究，我们采取了一种折中的三划分的增量式约束布局。该增量式约束布局分 为两个阶段，第一段是用三划分法解决增量式布局，第二个阶段是基于本文约 束布局的增量式布局。由于二者的约束方法和处理非法解的方法是相同的，因 此实现增量式的约束布局不再赘述。随着测试实例中的模块数量增加，增量式 布局的优势逐渐增强。由此可推知，增量式约束布局对今后的v l s i 布局具有 一定的影响。实验结果表明该增量式约束布局已完成设计要求，很好避免了一 些重复性的操作而节省布局时间。 关键字：超大规模集成电路；布局；对齐；性能；b 誊t r e e ) 模拟退火；增量式 a b s t r a c t a tp r e s e n t , w i t ht h ed e v e l o p m e n to fs o cd e s i g n sa n dn o cd e s i g n s ，m a n y r e s e a r c h e r sa d ds o m ee x t r ac o n s t r a i n t si n t ot h eo p t i m i z i n gp r o c e s so ff l o o r p l a n n i n g t om e e tt h ed i f f e r e n tf u n c t i o n a l i t ya n dp e r f o r m a n c er e q u i r e m e n t s ，i n c l u d i n gt h e l o c a t i o nb e t w e e nm o d u l e s ，s u c ha sa l i g n m e n tc o n s t r a i n t s ，b o u n d a r yc o n s t r a i n t , p o w e ri n t e g r i t yc o n s t r a i n t sa n dp e r f o r m a n c e c o n s t r a i n t sa n ds oo n m o d e m p l a c e m e n to ft h ep r o b l e mh a sb e e nf r o mt h es i m p l ea n dt r a d i t i o n a lt oav a r i e t yo f c o n s t r a i n t sa n dc o m p l e x i ns o l v i n gp r o b l e m sw i t ht h ep l a c e m e n to fc o n s t r a i n e d ，w e i k s eb牝t r e er e p r e s e n t a t i o no ft h ep l a c e m e n t i ti saf l e x i b l ea n de f f i c i e n t r e p r e s e n t a t i o no ft h eo r d e r e db i n a r yt r e e t h i st h e s i ss t u d i e st w ok i n d so fp l a c e m e n tc o n s t r a i n t s ，t h ea l i g n m e n tc o n s t r a i n t s a n dp e r f o r m a n c ec o n s t r a i n t s b e c a u s et h em o d u l e sa r ea r r a n g e dw i t hc o o r d i n a t e s , t h e a l i g n m e n tc o n s t r a i n t sc a nb ed i v i d e di n t oh o r i z o n t a la l i g n m e n tc o n s t r a i n t sa n d v e r t i c a la l i g n m e n tc o n s t r a i n t s t h i sc o n s t r a i n e dp l a c e m e n tw a sb a s e do i lt h eb 奎t r e e r e p r e s e n t a t i o n w ea c h i e v e d t h em i x e dc o n s t r a i n t s p l a c e m e n tw i t h h o r i z o n t a l a l i g n m e n tc o n s t r a i n t s ，v e r t i c a la l i g n m e n tc o n s t r a i n t sa n dp 矾o r m a n c ec o n s t r a i n t s w ei n - d e p t hs t u d yo ft h eb - t r e eo ft h es t r u c t u r ea n dc h a r a c t e r i s t i c sa n dp r o p o s e d t h r e es u f f i c i e n tc o n d i t i o n sf o r t h ec o r r e s p o n d i n gc o n s t r a i n t s ，a n dp r o p o s e da n o p t i m i z a t i o np r o c e s sc a nb eq u i c k l ys i f t e dl e g a l s o l u t i o n s f o rt h es i m u l a t e d a n n e a l i n ga l g o r i t h m ，w ea l s or a i s e d i t so p t i m i z a t i o np r o c e s s t h a ti s ，i ne v e r y i t e r a t i o no ft h ep r o c e s so fc o o l i n g , w eh a v et ot e s tt h el e g a l i t yo fi t sp l a c e m e n t i fi t i si l l e g a l ，t h e nt h ed y n a m i cw o u l dl e g i t i m i z et h i st e m p e r a t u r et oc o m p l e t et h e p l a c e m e n t i nt h ec o o l i n gi t e r a t i o np r o c e s so fg e n e r a t i n gs o l u t i o ns p a c e ，a d d e dt o d e t e r m i n es t e p st or e d u c et i m et oi m p r o v ee f f i c i e n c y t h ee x p e r i m e n t a ld a t a d e m o n s t r a t e d ，t h i st h e s i sr e a l i z e dc o n s t r a i n t sw e r es u c c e s s f u l ，a n do p t i m i z e dp r o c e s s w e r ee f f e c t i v e w i t ht h ev l s ic o n t i n u o u sl a r g e - s c a l ea n dc o m p l e x i t y , t h en u m b e ro fw a f e ri s b e i n ge x p o n e n t i a lg r o w t h a tt h ec h i pd e s i g np r o c e s ss t a g e ，t h ed e l a yo fp l a c e m e n t h a sb e c o m et h eb o t t l e n e c k t h e r e f o r e , t oe l i m i n a t ed u p l i c a t i o ni nt h ep l a c e m e n t , a i m t or e d u c ed e l a yo ft h ei n c r e m e n t a la l g o r i t h mb e c o m et h er e s e a r c hh o t s p o t t h i s t h e s i st h r o u g hi n d e p t ha n a l y s i s ，w eh a v et a k e nac o m p r o m i s eo ft h et h r e ed i v i d e d i n c r e m e n t a lp l a c e m e n tb a s i n go nc o n s t r a i n t s t h ei n c r e m e n t a lc o n s t r a i n e dp l a c e m e n t d i v i d e di n t ot w os t a g e s f i r s ti sb yu s i n gt r i p a r t i t em e t h o dt os o l v ei n c r e m e n t a l p l a c e m e n t s e c o n ds t a g e i si n c r e m e n t a lp l a c e m e n tb a s e do nt h ec o n s t r a i n e d p l a c e m e n t s i n c eb o t hc o n s t r a i n t sm e t h o d sa n dd e a l i n gw i t hi l l e g a lr e s t r a i n ts o l u t i o n m e t h o di st h es a m e ，t h ec o n s t r a i n to ft h ei n c r e m e n t a lp l a c e m e n ti sn o tr e p e a t e d w i t h t h ei n c r e a s i n gt h en u m b e ro fm o d u l e so ft h et e s tc a s e ，t h ea d v a n t a g e so fi n c r e m e n t a l p l a c e m e n ti sg r a d u a l l ye n h a n c e t h u sc a nb ei n f e r r e dt h a ti n c r e m e n t a lc o n s t r a i n t p l a c e m e n to fv l s ih a sa c e r t a i ni m p a c ti nt h ef u t u r e e x p e r i m e n t a lr e s u l t ss h o wt h a t t h ei n c r e m e n t a lc o n s t r a i n e dp l a c e m e n td e s i g nh a sb e e nc o m p l e t e d ，a n di tc a na v o i d s o m er e p e t i t i o nw e l li nt h eo p e r a t i o na n ds a v ep l a c e m e n tt i m e k e yw o r d s ：v l s i ；p l a c e m e n t ；p e r f o r m a n c e ；c o n s t r a i n t s ；b 一t r e e ；s i m u l a t e d a n n e a l i n g ；i n c r e m e n t a l i i i 中文摘要 目录 a b s t r a c t 。 第1 章绪论。 1 1 研究背景l 1 2 相关研究2 1 3 本文主要工作4 1 4 本文组织结构4 第2 章v l s i 布图设计和布局方法 2 1 集成电路发展现状5 2 2v l s i 设计流程5 2 2 1 系统规范说明6 2 2 2 寄存器传输级设计6 2 2 3 逻辑设计7 2 2 4 电路设计7 2 2 5 物理设计7 2 2 6 设计验证7 2 3 布图设计。7 2 3 1 版图划分8 2 3 2 布图规划8 2 3 3 布局9 2 3 4 布线9 2 3 5 压缩1 0 2 4 布图规划常见算法1 0 2 5 布局得表示方法1 0 2 5 1 可二划分结构1 1 2 5 1 不可二划分结构1 2 2 6 层次化布局19 2 7 本章小结1 9 第3 章基于约束布局算法的实现 2 1 3 1 模拟退火算法及其优化流程2 1 3 1 1 模拟退火算法简介2 l 3 1 2 模拟退火算法基本导出一2 2 i v 3 1 3 模拟退火算法的要素2 4 3 1 4 本文提出的优化流程2 6 3 2 约束问题描述与定义2 7 3 2 1 约束问题及其定义2 7 3 2 2 布局问题的描述3 0 3 3 基于b 幸t r e e 的约束布局可行性分析3 l 3 3 1 水平方向对齐约束模块组的可行性分析3 1 3 3 2 水平方向对齐约束模块组的可行性分析3 2 3 3 3 性能约束模块组的可行性分析3 3 3 3 4 基于b 宰t r e e 表示法的约束布局合法条件3 5 3 4 布局中模块的重叠处理和b 事t r e e 表示法的扰动机制3 6 3 4 1 布局中模块的重叠处理3 6 3 4 2b 木t r e e 表示法的扰动机制3 7 3 5 约束的实现3 9 3 5 1 水平方向对齐约束的实现4 0 3 5 2 竖直方向对齐约束的实现4 1 3 5 3 性能约束的实现4 2 3 6 实验结果4 4 3 7 本章小结4 5 第4 章增量式约束布局的研究 4 6 4 1 问题描述4 6 4 2 增量式布局问题分析4 7 4 3 解决方法的可行性分析4 9 4 4 增量式布局问题的解决5 l 4 5 实验结果5 3 4 6 本章小结5 4 第5 章总结及未来发展 5 5 5 1 本文总结5 5 5 2 工作展望5 6 5 2 1 多约束并存的布局一5 6 5 2 2 时延约束的布局方法5 7 5 2 3 精确的增量式布局约束5 7 参考文献 致谢 附录 v 5 8 6 2 6 3 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 随着集成电路的不断复杂化、大型化，大规模集成电路( v e r yl a r g es c a l e i n t e g r a t i o n ，v l s i ) 得到广泛应用，片上系统( s y s t e m o nc h i p ，s o c ) 的日益完 善、片上网络( n e t w o r ko nc h i p ，n o c ) 研究日益发展，越来越多的应用技术 融入超大规模集成电路中，布局方法层出不穷【1 1 ，层次化设计和知识产权核 ( i n t e l l e c t u a lp r o p e r t yc o r e ，i p 核) 都得到了广泛的应用。 随着s o c 、n o c 的迅速发展，许多科研工作者根据芯片功能和性能的特殊 需求，在布局中增加了对一些模块间的相对位置约束；工业生产为了满足消费 者对多功能的要求，对特定功能模块的结构化设计也格外重视。例如，两个矩 形模块间有很强的互联通信关系，这就需要邻接约束，从而形成了“t ”型模块 和“l ”型模块：在基于b u s 总线的布线中，有些模块需要对齐的放置在芯片 适当位置，这就产生了对齐约束，即形成所谓的线性模块；有些时候需要将一 些模块放置在给定的边框内，这就是固定边框约束，可以形成宏模块或p 核； 有些频繁使用的模块需要与i o 连接或者发热量比较大，这就产生了边缘约束， 即所谓的边缘宏模块；还有将模块和电路对称设计，这些约束在可逆电路设计 中也常常被提及，这些约束在布局中占有重要的地位，引领集成电路发展方向。 在这种发展趋势下，芯片版图设计对v l s i 设计的质量起到了决定性的作 用，而布局又是版图设计中一个至关重要的步骤，因此布局的设计和优化问题 成为研究的热点问题。传统布局问题的目标，是随机的将给定模块组合并排列 之，使各模块之间不能有任何的重叠，并且得到版图面积最小、互连线长最短。 现代布局问题已逐步从传统的布局问题向具有各种约束的布局问题转变。 通过阅读大量文献资料，得知布局问题的热点在局部约束布局 2 - 3 。对齐约 束( a l i g n m e n tc o n s t r a i n t s ，a c ) 布局和性能约束( p e r f o r m a n c ec o n s t r a i n t s ，p c ) 布局已经被人们所认知，本文在此基础上对以上两种局部约束布局进行了扩充 和优化改进带有方向的对齐约束，即分为水平方向对齐约束( h o r i z o n t a l a l i g n m e n tc o n s t r a i n t s ，h a c ) 布局和竖直方向对齐约束( v e r t i c a la l i g n m e n t c o n s t r a i n t s ，v a c ) 布局。性能约束布局是为了满足特定功能模块的性能提高要 求。这两种约束有利于不增加，或者微量增加互连线长和布线时空问的同时， 武汉理工大学硕十学位论文 解决了布局的功能和性能的要求。研究这些被约束的模块组成的宏模块实现特 殊的功能具有实际意义，本文对基于该约束的布局问题进行了深入的研究。 随着v l s i 的不断发展，一块硅片上包含的元件达十亿级，布局问题的时 延也越来越严重，在局部范围内快速调整布局已经成为一种设计需要。本文采 取一种基于约束的三划分增量式约束布局法，进一步来研讨和解决时延增加的 问题。 1 2 相关研究 目前，在集成电路物理设计中有一些比较优秀的布局表示方法，例如： h m t u r a t a 等人19 9 5 年提出的序列对( s e q u e n c ep a i r ，胆) 表示法1 4 j ，n a k a t a k e 1 9 9 6 年提出的变形网格( b o u n d e ds l i c e l i n eg r i d ，b s g ) 表示法p j ，p n g u o 等 人1 9 9 9 年提出了o t r e e 表示法【6 】，同年h u a n gg a n g 提出的阶梯网格( s t a r w a y g r i d ，册) 表示法，y u n c h i hc h a n g 等人2 0 0 0 年提出的b - t r e e 表示法 7 1 ，同 年h o n gx i a n l o n g 等人提出马赛克( m o s a i c ) 结构的角模块序列( c o m e r b l o c k l i s t ，c b l ) 表示法【8 】和k s a k a n u s h i 等人提出的q 序列( q u a r t e r - s t a t es e q u e n c e ， p s e q u e n c e ) 表示法【9 1 ，j m l i n 等人2 0 0 1 年提出的传递闭包图( t r a n s i t i v e c l o s u r eg r a p h ，t c g ) 表示法【l o 】，同年x i a o p i n gt a n g 等人提出的快速序列对 ( f a s ts e q u e n c ep a i r ，f a s t s p ) 表示法【1 1 】， j a i m i n gl i n 等人2 0 0 2 提出的 传递闭包图序列( t r a n s i t i v ec l o s u r eg r a p h s e q u e n c e ，t c g s ) 表示法【，以及 2 0 0 3 年提出的角模块队列( c o m e rs e q u e n c e ，c s ) 表示法【1 3 1 。上述每种表示 法都各有特点，各成系统，对本文起着启示性的作用。 除此之外，通过对其他不同表示方法的研究，了解到研究者们提出的各种 处理相应约束的多种方法。例如，在文献 1 4 】和 1 5 】中，作者在布局设计时增加 了对模块的对齐约束和半固定边框约束。他的对齐约束是根据所要约束的模块 组排列成一列，然后用加虚模块的方法调整非法模块，这里所说的非法模块指 的是应该排成一列但又不能排列到起的模块，增加虚模块后使非法模块上移， 使之与其他受约束模块形成公共通道，已达到增加功能的需要；其半固定边框 约束，是指为了使受约束模块组的性能达到最高，而将其排列到一个固定边框 内，其边框大小是粗略的估计出一个可行的边框临界值，该临界值可以在设定 的范围内变动，所以称之为半固定边框约束。在整个布局过程中，研究者和设 计者们都要求所有受约束的模块必须无重叠的放置在设定的边框区域内。例如 在文献 1 6 】中，作者使用序列对表示法，通过给出水平约束图和竖直约束图， 2 武汉理工大学硕十学位论文 并根据该约束图组处理边界约束布局。由于该表示法有诸多局限性，其方法应 用的不是很多。 图1 - 1 宏模块的版图布局 正如文献【1 7 】和 1 8 】中所说，s o c 设计中对宏模块的应用是至关重要的。由 于大量约束模块组的存在，形成了大量具有特殊功能的宏模块，这些宏模块混 杂在这个布局中，因此，选择的版图设计方法的优劣非常关键。由于一些功能 相同或者相关、性能要求特殊的模块有序排列或组合可以形成m 核，能更好的实 现芯片特定的功能或者性能的提高，因此本文提出了两种新颖的约束布局，也 就是对齐约束布局和性能约束布局。如图1 1 所示，在层次化设计中，约束布局 意义重大，所谓宏模块，即为实现特定功能的巨型模块，我们可以将其理解为 一组受约束模块的组合。模块间频繁通信产生大量的热，在电路层面上，热的 影响对其性能和可靠性都具有重要的意义【1 9 j t 2 1 1 ，温度每增加1 0 4 c ，互连线延迟 增加5 【1 2 】；同时，漏电功耗随温度指数增加，在最新的工艺条件下，温度每升 高3 0 c ，静态功率会增加5 0 【2 3 1 ，文献【2 4 】和 2 5 】就是在高层次综合考虑热问题的 资源分配，一般情况下在降低温度的同时是以牺牲资源为代价的。有由于芯片 功耗和其面积成正比，因此芯片热问题与芯片面积增加产生了矛盾。 为了解决上述矛盾，本文采用不同方向上的对齐约束来解决热分散问题。 因为单采取同方向上的对齐约束，可能会出现两个或多个对齐约束模块组毗邻， 可能会导致局部通信量过大产生大量的热，从而使芯片性能大大降低。文献 2 6 】 用序列对( s p ) 法实现了对齐约束和性能约束，但是s p 表示法不仅表达有些 繁琐，实现起来也不是很如意。文献 2 】实现了水平方向对齐约束和性能约束， 武汉理工大学硕十学位论文 只一带而过的说可以交换坐标来实现竖直方向对齐约束，但是这样还是一种对 齐约束，热问题得不到有效解决；而其性能约束是半固定边框约束，需要人为 设定边框值，这样可能发生既费人力又边框不合适的情况。在高层设计阶段， 受约束的模块组标准单元可以以看作虚拟的大模块，这种虚拟的大模块可以作 为宏模块来处理。此做法有利于层次化布局设计，因此研究局部约束布局方法 很有必要。 1 3 本文主要工作 在约束布局问题研究中，本文完成了以下工作： 1 ) 本文提出了在布局规划设计中应该考虑的受约束模块的方向问题水 平方向对齐约束布局和竖直方向对齐约束布局，它有效缓解芯片热问题。 2 ) 本文提出了可自动生成最小面积的性能约束布局，这对性能约束模块的 自动化有指导性的定义。 3 ) 本文结合b 木t r e e 表示法和模拟退火方法，提出了对不合法模块的调整， 即对不合法解的动态修正，使合法化。并在扰动机制上采取适当约束来保障约 束布局的顺利进行，同时也提高了整个布局的效率。 在增量式约束布局的研究中，本文完成了以下工作： 1 ) 本文提出了一个三段式的增量式布局方法，即把整个布局分为三块，然 后用增量式方法进行布局，此法可有消的减少布局时延，对v l s i 的发展具有 重要意义。 2 ) 本文提出了带约束的增量式布局方法，将上面所讲的约束布局应用在增 量式布局之上，提高了布局效率的同时也增加了芯片的需求。 1 4 本文组织结构 本文共分为五章。第一章是绪论，简介研究背景知识和相关研究及发展以 及本文工作；第二章介绍v l s i 布图设计的基础知识和主要布局方法；第三章 介绍约束布局的实现；第四章增量式约束布局的实现；第五章对全文进行总结 和对今后工作的展望。 4 武汉理工大学硕士学位论文 第2 章v l s i 布图设计和布局方法 上世纪4 0 年代后期，晶体管被发明并应用于集成电路制造，历经了：小规 模集成电路( s m a l ls c a l ei n t e g r a t i o n ，简称为s s i ) 、中规模集成电路( m e d i u m s c a l ei n t e g r a t i o n ，简称为m s i ) 、大规模集成电路( l a r g es c a l ei n t e g r a t i o n ，简 称为l s i ) 、超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t i o n ，简称为v l s i ) 和 甚大规模集成电路( u l t r al a r g es c a l ei n t e g r a t i o n ，简称为u l s i ) 等五个阶段。 当前的片上系统( s o c ) 已是成熟产品，片上网络( n o c ) 是研究热点，集成 电路制造工艺水平已进入深亚微米级，v l s i 设计制造面临：缩小尺寸、增大集 成度、提高性能以及降低功耗等方面的挑战。由于这四个因素的互制约，v l s i 设计变得十分重要，其中的物理设计及优化攸关芯片设计成败，这是我们研究 的重点。 本章主要介绍v l s i 流程、布局设计的基本内容，以及布局阶段比较广泛 应用的算法和层次化布局方法。 2 1 集成电路发展现状 集成电路具有以下特点：体积小、重量轻、寿命长、高可靠性和性能好等 等；同时，制造成本低、便于大规模工业生产。不仅在民用电子设备方面得到 广泛的应用，而且在军事通讯电子领域也得到广泛的应用。 近些年，我国集成电路产业取得突飞猛进的发展，国内集成电路产业已经 形成，集i c 的设计、制造、封装测试为一体的产业化结构已经完成，配套业相 继完善为将来e d a ( e l e c t r o n i cd e s i g n a u t o m a t i o n ) 产业奠定基础，国产布局工 具也相继被开发，例如，北京华大九天软件有限公司的熊猫e d a 系统九天 系列工具( 简称“九天e d a 工具 ，“z e n i ) 。中国的集成电路产业虽然已经成 为半导体业界关注的焦点，但是我国的半导体发展限于诸多因素的影响，集成 电路的发展需要学术界和产业界共同努力。 2 2v l s i 设计流程 v l s i 设计涉及到软硬件方面的知识，是一个十分复杂的设计和实现过程。 它不仅涵盖了计算机相关科学与技术，而且还包含物理电路、通讯系统、微电 5 武汉理工大学硕士学位论文 子学等多专业相关知识，甚至包含精密仪器制造工艺的相关技术。由于v l s i 设计的复杂性要求以及物理元器件的属性，就决定了v l s i 设计要借助必要的 计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 工具才能完成。v l s i 设计 流程图如图，一般可分为：系统规范说明、寄存器传输级设计、逻辑设计、电 路设计、物理设计以及设计验证等六个步骤。以下对每个步骤分别介绍其相关 内容及主要作用。如图2 1 所示。 系统规范说明 行为级仿真及优化 二二j 受二 寄存器传输级设计 二二二受! 二 门级综合仿真 二二二受竺二 测试生效 二二二受窆二 电路设计及分析 二二二受二 物理设计及优化 二二! 受= 二二 版图设计及验证 芯片制造 准备工作 前段设计 前段设计 图2 1 芯片制造流程 2 2 1 系统规范说明 需求分析是项目开始前的准备工作，v l s i 设计也不例外。e d a 工具需要 用户将其需求转化为功能描述以及技术指标，这将组成系统规范化说明。一般 包括系统的功能以及性能、芯片的物理尺寸等。同时，系统规范说明也需要考 虑到设计模式、工艺流程、制造周期以及设计费用等【2 7 1 。 2 2 2 寄存器传输级设计 在寄存器传输级设计阶段，设计者们主要完成系统的功能实现方案。需要 考虑系统的行为特性，要给出系统时序图，以及各子模块相互的数据流图。利 用这些必要信息，设计者们可依据仿真模拟的方法的效果来改进整个设计，优 化设计方法，步骤达到最优状态【2 7 1 。 6 武汉理工大学硕士学位论文 2 2 3 逻辑设计 在逻辑设计过程中，设计者们可以模拟出一个能表示整个系统功能的逻辑 电路结构，并能够多次反复测试其正确性。这将使得各子系统模块更加结构化、 实体化，能够选择合适的逻辑部件使得系统的功能顺利实现。设计者们通常采 用逻辑流程图、文档、原理图来表示设计方案，也有时会使用布尔方程来表示 设计方法【2 7 1 。 2 2 4 电路设计 电路设计比较复杂，设计者们要将逻辑电路设计方案具体得以实现。在进 行具体电路设计时，设计者们需要考虑的因素很多，其中包括电路宽度、走线 密度、功耗和串扰等实际因素。此外，还需注意各种元器件本身的电性能指标。 在本设计阶段，设计者们通常采用详细电路图来表示相关电路的结构。 2 2 5 物理设计 所谓的物理设计，即为版图设计，是v l s i 设计中最时延费力的步骤。物 理设计阶段，设计者们需要把每个元器件的电路图表示转换为几何图表示。同 时，所有元器件间互联也被转换为几何连线图表示。转换后的带有层次的电路 几何图表示被称为版图。版图的设计必须与当前制造工艺水平相一致，如果有 必要，可以超前一点，但是风险很大。由于版图设计及其复杂，设计者们往往 把版图设计细分为若干步骤分别进行。在下面的章节中，我们要详细介绍物理 设计过程的流程。 2 2 6 设计验证 设计验证通常称为版图验证，是版图设计完成后很重要的一个步骤。版图 设计完成之后，它将验证所得到的几何图能否满足制造工艺要求，确保其符合 系统的设计规范要求。在设计验证过程当中，设计者的主要任务包括：设计规 则检查、版图的电路参数提取、电学规则检查以及寄生参数的提取等。 经过整个电路设计的实施，方可将验证合格的版图进行生产制造，或者交 给代工厂家批量生产。 2 3 布图设计 布局是v l s i 物理设计阶段的成果，也是集成电路设计和芯片制造之间的 7 武汉理工大学硕士学位论文 惟一的纽带。在现阶段v l s i 、u l s i 设计中，布图设计结果的优劣直接影响整 个版图的成败。布图设计阶段就是物理设计阶段。布图设计是在人工设计中最 时延耗资、错误率最高的阶段。布图设计过程一般分为版图划分、布图规划、 布局、布线以及压缩等五个阶段，如图2 2 所示。 图2 - 2 布图设计过程 2 3 1 版图划分 版图的划分( p a r t i t i o n ) 是随着科技的发展而产生的，电路版的设计制造工 艺随之发生很大变化，元器件尺寸不断的缩小，现代v l s i 可以包含上十亿个 晶体管。电路的不断复杂化、大型化，使得计算机芯片的功能出现了一定的限 制。通常情况下，研究和开发者们处理物理设计问题时，会把整个芯片划分成 多个子系统来分步骤解决，可使问题规模缩小。据以往，一般5 , - 2 5 个标准模块 划分为一组，形成一个虚拟模块。模块的划分也要考虑到所包含模块的数目、 模块尺寸，以及模块间互连线条数等多个要素。 2 3 2 布图规划 布图规划( f l o o r p l a n n i n g ) 的主要目的是为整个芯片的设计选择较好的布 局。经过版图划分为若干个虚模块是我们研究的重点，一般将其看作矩形模块， 我们将每个划分好的虚拟模块所包含的元器件的具体数目以及各个元器件的宽 和高计算出来，估计出各个需模块的形状、面积以及相应的引脚( p i n ) 脚的位 亟坚堡王查堂堡主兰垡笙壅 置分布【2 8 1 。布图规划阶段的总体设计目标是对芯片互连线长和总体面积的优化。 2 3 3 布局 布局( p l a c e m e n t ) ，在电子设计自动化中起着至关重要的作用。布局的主 要目的是确定模块或者元器件在芯片或者印刷电路中的位置信息，并使其能够 满足一定的性能要求。在布局阶段，需要输入的是一组模块的信息，是指各个 模块上的引线端信息和网表。若模块内的电路版图设计已经完成，则说明该模 块的形状和大小以固定，此类模块通常被称为硬模块( h a r db l o c k ) 若在布局 阶段才需要确定其形状和大小，此类模块则被称之为软模块( s o f tb l o c k ) 。我 们通常所说的“布局问题中的模块，是指待安装的硬模块。因此，我们只需 考虑将各个模块组合在芯片上。如果，模块组中包含软模块，我们将此布局问 题称之为布图规划( f l o o r p l a n n i n g ) 问题。由此可知，布局问题其实是布图规 划问题中的一个特例而己。因此，我们在下一节重点讲解布图规划问题。 一个好的布局不仅能充分展示芯片性能，也有利于芯片的制造；相反，一 个差的布局不但会影响整个芯片的性能，而且会由于互连线超长而使其不能被 制造生产。因此，一个好的布局工具能在确定各个元器件位置的同时，保持面 积最小，还必须满足电路性能需求保持互连线最优，并且能实现和优化多个目 标。布局阶段的完成，标志着电路模块的决定位置以及其引脚的位置已经确定 1 2 8 1 。布局优化的目标一般包括如下五个要点： 1 ) 时序性；2 ) 互连线长；3 ) 拥塞区域；4 ) 电路功耗；5 ) 布局时延。 2 3 4 布线 布线( r o u t i n g ) ，需要根据互连信息实现元器件百分之百互连【2 9 1 ，电路本 身的要求决定了电路网表信息。布线的主要目标就是为了实现所有模块之间的 互通互连，其次，在达到布通率要求的前提下，继续对布线结果优化。例如， 如何减少互连线长度，如何减少通孔数量等等。一般来讲，布线可分成两个步 骤：第一步是总体布线，第二步是详细布线【2 9 1 。总体布线是面向线网的布线， 我们要以线网为考虑对象，但这仅仅是将线网初步分配在合适的区域内，以便 确保能够得到尽可能高的布通率，并不需要去关心实际走线的情况【2 9 1 。详细布 线属于面向区域的布线，是最终