（微电子学与固体电子学专业论文）系统级芯片布局算法研究.pdf

摘要 摘要 f 随着集成电路工艺技术，设计技术的迅速发展，集成电路进入了一个片j i 系统的时代，系统级芯片( s y s t e m o n c h i p ，简称为s o c ) 已成为微电子领域 当前最引人瞩目的话题之一。s o c 是在a s i c 的基础上发展起来的电路系统， 但是与传统的a s i c 芯片相比，它又有很多显著的不同，如：s o c 多采用深、i 微米加工工艺；由于规模大，结构复杂，s o c 多采用基于口核复用的设计技术： s o c 的测试比较困难等。s o c 自身的特点，给集成电路的c a d 设计带来了外 多新的问题和新的挑战。但目前的e d a 工具还不成熟，其处理能力跟不上s o c 工艺技术的发展，这使得s o c 设计不能充分发挥出全部性能。因此，发展适? ? s o c 设计的集成电路c a d 技术已成为当前的紧迫任务。 布局是芯片设计的重要环节，它对芯片性能的影晌至关重要。系统级芯| 的出现，给v l s i 自动布局算法的研究提出了许多新的要求。寻求高效率， 速度，符合s o c 设计特点的布局算法，无疑已成为当耵算法研究的一个着眼，c ， 和基本趋势。，本文主要围绕系统级芯片的布局问题这一方面的内容来展丌。 本文完成的主要工作包括： 1 基于口核集成的系统级芯片需要更为有效的宏模块的碲局算法。 本文采用基于规划方法的宏模块布局算法。该算法利用了规划方法可以川 时求解各模块位置的特点，将原布局问题转构造成一个约束优化问题。彦 算法不仅求解简单，且能处理较大规模的宏模块布局问题。峙其它算法棚 比，本算法对原有的规划算法做了改进，并具有如下一些特点： ( a ) 在线长的计算中使用了引脚的具体坐标。由于使用了引脚坐标，算7 可以在布局过程中同时引入模块的平移，旋转等操作，大大改善了拓 局的质量。 ( b ) 为了简化模块引脚的坐标表示，该算法引入了取向向量这一表示形式 这一表示形式不仅可以更为有效地描述模块的取向情况，并可将目扼 函数构造为具有一种对称的性质，方便了问题的求解。 ( c ) 算法利用布局问题的特点提出了一种交替求解的迭代策略。利用该爱 略原问题可被转化为规模较小的两个子问题，从而大大降低了求解所 摘要 复杂度h 、 2 由于系统级芯片采用的是基于p 核复用的设计技术，总线的重要 性显得日渐突出。为了能反映出总线的这种重要地位，开发出符合s o c 芯片设计的e d a 工具，本文提出了一种基于总线优化的宏模块布局算法， 用以解决基于核的数据通道系统的布局问题。该算法首次提出在布局 过程中将总线资源做为优化目标之一。为了能更为有效地描述总线的资 源，本算法提出了一种虚模块模型。旧其它的线网模型相比，虚模块模型 具有如下特点： 、 ( a ) 虚模块模型能够更好地反映出总线的拓扑结构，因此能在布局过程中 提供总线有关的走线信息。 ( b ) 通过使用虚模块模型，在处理与总线有关的线网时可以避免出现过大 的线网，便于以优化线长为目标函数的布局方法的应用，保证了布局 的质量。通过使用虚模块模型，该算法可以针对总线的分布情况对总 线资源做具体的优化。实验结果表明该算法切实有效。 3 由于系统级芯片具有多采用深亚微米工艺实现的特点，在系统级芯 片的布局算法中必须考虑到连线的延迟问题。本文提出了一种总线时延驱 动的布局算法，用以解决系统级芯片中的总线延迟问题。为了能对总线的 时延进行有效估算，该算法提出了一种总线时延的估算模型，该估算模型 具有如下特点： ( a ) 计算简单方便，便于在布局过程中估算总线的时延，用于指导进一步 的布局。 ( b ) 可针对总线具体的走线情况对总线的时延进行计算，因此能更准确地 反映出总线真实的时延情况。本算法将时延要求作为约束条件带入问 题中。通过采用拉格朗日松弛法，本算法可有效地解决总线时延驱动 的布局问题。 ) f i i a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ed r a m a t i cd e v e l o p m e n to fd e e p s u b m i c r o nt e c h n o l o g y , t h ei n t e g r a t e dc i r c u i t i n d u s t r y i s e n t e r i n g as y s t e m o n c h i p ( s o c ) e r a ，a n ds o c d e s i g ne n t e r si n t om a i n s t r e a mu s a g e 。s o ci sd e r i v e df r o mt h ea s i c ，b u tc o m p a r e d w i t ha s i c ，s o ch a sm a n y s p e c i a lc h a r a c t e r s ：t h et e c h n o l o g yu s e di ns o cd e s i g ni s d e e p - s u b m i c r o nt e c h n o l o g y ；t h es t r n e g yt or e d u c ed e s i g nt i m ea n dh e n c em e e tt i m e - t o m a r k e tr e q u i r e m e n t si st h r o u g ht h eu s eo fr e u s a b l ec o r e so ri n t e l l i g e n c ep r o p e r t y ( 口) ；t h et e s t i n go fs o ci sv e r yh a r d s o cb r o u g h ta b o u tt r e m e n d o u sp r o b e m sa n d c h a l l e n g e s t ot h ev l s ip h y s i c a l d e s i g nr e s e a r c h ，a s t h e e x i t i n ge d at o o l s i s n t s o p h i s t i c a t e df o rs o cd e s i g n ，p e o p l e c a r l tm a k e g o o d u s eo f s o c p o t e n t i a la tp r e s e n t d a y o b v i o u s l y , i t san e c e s s i t o u sw o r ka tn o w t or e s e a r c ht h ee d at o o l sf o rs o c p l a c e m e n ti sak e yp r o c e s si nf l o o r p l a n ，p l a c e m e n tr e s u l ti n f l u e n c et h es y s t e m p e r f o r m a n c es e r i o u s l y s o cb r o u g h ta b o u tal o to fr e q u i r e m e n tt ot h ep l a c e m e n t r e s e a r c h a tp r e s e n t ，t h em a i ng o a lo f p l a c e m e n ta l g o r i t h i ni su n d o u b t e d l yt op u r s u e f a s t e ra n dm o r ee f f i c i e n ta l g o r i t h mf i tf o rs o c o u rw o r ka r ea l s ot o w a r dt h i so b j e c t t h em a i nc o n t r i b u t i o u so f t h i sd i s s e r t a t i o n 戳p r e s e n t e da sf o l l o w s ： 1 w eh a v ep r e s e n t e dam a c r o c e l lp l a c e m e n ta l g o r i t h mb a s e do np r o g r a m m i n g t e c h n o l o g y t h i sa l g o r i t h mc o n s t u c tt h ep l a c e m e n tp r o b l e ma sac o n s t r a i n e d o p t i m a lp r o b l e m ，t h ep o s i t i o no fe v e r 3 , m o d u l ei ss o l v e ds i m u l t a n e o u s l y t h e c h a r a c t e r so ft h i sa l g o r i t h mi sp r e s e n t e da sf o l l o w s ： ( a ) t h ep i np o s i t i o ni st a k e ni n t oa c c o u n ti nt h ew i r e l e n g t hf u n c t i o n 。s ot h e t r a n s a l a t i o na n dr o t a t i o nm a n i p u l a t i o nc a nb e p e r f o r m e ds i m u l t a n e o u s l y ( b ) t h e o r i e n t a t i o nv e c t o ri s u s e dt od e s c r i b et h em o d u l eo r i e n t a t i o n i t s i m p l i f yt h ec o o r d i n a t ep r e s e n t a t i o no ft h ep i n ，a n dm a k et h eo b j e c t i v e f u n c t i o ns y m m e t r i c a l ( c ) t h ed u l e i t e r a t i o nm e t h o di su s e dt os o l v et h eo p t i m a lp r o b l e m b yu s i n g t h i sm e t h o d ，t h e o r i g i n a lp r o b l e mc a nb et r a n s l a t e dt ot w o s u b p r o b l e m ，t h i s r e d u c et h e c o m p l e x i t y o ft h e p o b l e ms u b s t a n t i a l l y ，t h ee x p e r i m e n t a l i ， a b s t r a c t r e s u l t sh a v ed e m o n s t r a t e dt h a tt h i sa l g o r i t h mi sf a s ts p e e da n dc a nb eu s e d f o rl a r g e s c a l ep l a c e m e n t p r o b l e m 2 w eh a v ep r e s e n t e dam a c r o c e l lp l a c e m e n ta l g o r i t h mb a s e do no p t i m i z i n gb u s r e s o u r c et od e a lw i t ht h ep l a c e m e n tp r o b l e mo fd a t a p a t hs y s t e mb a s e do n 口 c o r e t h i sa l g o r i t h mt a k et h eb u sr e s o u r c ea sao p t i m a lo b j e c ta tt h ef i r s t t i m e t od e s c r i b et h eb u sr e s o u r c em o r ee f f e c t i v e l y , w ep e s e n t e dav i r t u a l m o d u l em o d e l t h ec h a r a c t e r so ft h ev i r t u a l m o d u l em o d e li sp r e s e n t e da s f o l l o w s ： ( a ) t h i sm o d e lc a nr e f l e c tt h eb u st o p o l o g ym o r ee f f e c t i v e l y ( b ) t h i sm o d e lc a ng u a r a n t e et h ep a l c e m e n tq u a l i t yb ya v o i d i n gd e a l i n gw i t h t h e h u g en e t b yu s i n g t h ev i r t u a l m o d u l e m o d e l ，t h ea l g o r i t h mc a n e f f e c t i v e l yo p t i m i z et h eb u sr e s o u r c e t h ee 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 i sa l g o r i t h mi se f f e c t i v e 3 w ep r e s e n t e dab u sd e l a y - d r i v e nm a c r o c e l lp l a c e m e n ta l g o r i t h mt od e a lw i t h t h ei n t e r c o n n e c t d e l a yp r o b l e mi ns o c t oc a c u l a t et h eb u s d e l a y m o r e e f f e c t i v e l y , w ep r e s e n t e d ab u sd e l a ym o d e l t h ec h a r a c t e r so ft h e d e l a y m o d e l i s p r e s e n t e d a sf o l l o w s ： ( a ) t h i s m o d e li sf i tf o r e s t i m a t i n g t h eb u s d e l a yd u r i n g t h e p l a c e m e n t p r o c e d u r e ( b ) b yu s i n gt h i sm o d e l ，t h eb u sd e l a yc a nb ec a c u l a t e db y t h ea c t u a ls i t u a t i o n o fb u s d i s t r i b u t i o n ，s o t h ee x a c tb u s d e l a y i n f o r m a t i o nc a nb e a c h i e v e d t h i sa l g o r i t h mt a k et h eb u sd e l a yr e q u i r e m e n ta st h ec o n s t r a i n t ， b yu s i n gl a g r a n g i a nr e l a x a t i o nm e t h o d ，t h i sa l g o r i t h mc a nr e s o l v et h i s c o n s t r a i n e d p r o b l e me f f e c t i v e l y 第一章引衰 第一章引言 擞龟子技术是将半导体耪科置予超净环境中，通过极精密的徽缅加工制造 微奄子器件，微电子系统的门技术。箕核心楚集成电路技术，也有人称集成 电路技术为徽电子技术。在信息时代的今天，电子信息技术做为强大的社会生 产力，在推动经济发展，社会产业结构和生活方式的变革中的作用日盏增长。 在电子信息技术中，集成电路( i c ) 被称为现代工业的“食蹙”，是电子信息技 术发展的核心和綦础。集成电路技术的发展，大大撼动了靛空航天技术，爨测 遥感技术通讯技术，计算机技术，网络技术以及家用电器产她的迅猛发鼹。 据报道，世界国民生产总值的增馕部分数6 5 与集戏电路霄关，集残电路鼓术 已残为缓基一个爨家戳学技术进步释综合莺力鲶蓬要标恚。 鸯然1 9 5 9 年第块集戏电路诞生以来，集成电路的迅猛发展达到了令人 髫不冁接豹程度。在短翘酌滔十凡年的蟊寸问蓬，集成电路技术已经历了小规模 集成( s s i ) ，中糯模集成( m s i ) ，大规模集成的发展阶段，目前已进入超大规 模集成( v l s i ) ，甚大规模集成( u l s i ) 和吉规模集成( g s i ) 阶段，集成度已 擞高了8 9 个数量级，题一个“s y s t e mo nc h i p ”( s o c ) 的时代。以最普遍的 个人计算机微处理器为例，第一代1 6 位的8 0 8 8 芯片中，共容纳了约2 8 万个 晶体管，丽i n t e l 公司推出的最耘豹雾腾芯片( p e n t u i mi v ) ，英工作频率为i 3 2 g h z ，采用0 1 8 微米c m o s 工艺，集戏凄为4 2 0 0 万鑫体餐；箍辩m 最邋更 是塞称宅墨礤襄成全世界速凄最快髂微芯片，该芯片采爝硅锗为基确的芯片制 造技术工艺，运算达到一再一十g h z 。滔前商、监纯半导 本芯片制造技术的主流 已达到0 3 5 u m 的线宽，预计今后将缓快发展到o 1 3 u m 甚至0 i u m 以下，即集 成电路技术已进入个深旺微米工艺时代，并正在迈向超深亚微米的工艺时代。 集成电路技术正迅速向着更高集成度，超小型化，高性能和多样化的方向发展， 一个芯片上可集成高达几亿，甚至几十亿个晶体管。要究成如此规模积复杂度 的集成电路设计，离开计簿机辅助设计技术( c a d ) 蛇支持将是不可想象黢。 随莓集成度的提赢，芯片内郝是体管数晕越来越多，集成毫路设计静复杂洼也 越来越蕙，i c c a d 鼓术将愈发交得重要。久稍麸实践中得虱了一个毋庸溉疑的 络论：v l s i 懿遴一步发震摇巢离开i c c a d 援术将寸步难行。 第一章引言 1 1v l s i 物理设计 1 1 1 布图设计概念 集成电路( v l s i ) 设计包括了功能设计，逻辑设计，物理设计，设计验证 和制造等过程。物理设计也称为布图设计或版图设计，在整个集成电路设计过 程中，布图设计是重要的一环：因为设计出来的集成电路的性能指标，包括芯 片面积，增益大小，时延特性，电路可靠性等等，强烈地依赖于布图设计过程。 布图设计通常可分为两个阶段：布局阶段和布线阶段。布局阶段要根据集成电 路逻辑图的联结信息把逻辑图中的逻辑单元版图( 例如门。触发器，全加器 等) 放置在芯片合适的位置上；布线阶段要将这些单元按逻辑信号进行互连。 布图设计的要求是在满足集成电路基本特性( 例如逻辑功能，静态和动态电特 陛，功耗等) 和一定工艺条件下使芯片面积最小。布图设计是整个集成电路设 计过程中与产品研制和生产直接相关的一个设计过程，它直接关系到性能v l s i 的设计成本，周期，正确性和产品质量，而且也是人工设计中费时最长和差错 率最高的设计步骤之一。随着超大规模集成电路技术的发展，往往需要在几个 平方厘米的芯片上完成线条只有零点几个微米的上百万个器件电子系统的设 计，这使得利用计算机辅助设计技术进行自动布图设计己成为芯片设计中必不 可少的一部分。正因为如此，布图设计自动化也就成为近年来在设计自动化方 面发展最快，自动化程度最高的领域之一。布图自动化设计的输入是电路的元 件说明和网表，输出是设计良好的版图，它具有缩短设计周期，降低成本，提 高效率，又易于进行设计正确性验证等特点。随着集成电路制造技术的不断发 展，芯片的集成度越来越高，布图的规模越来越大，复杂性越来越高，在此情 况下，布图设计自动化必将发挥出更大的作用。 1 1 2 布图设计的模式 由于版图设计是一个极为复杂的过程，人们提出了不同的设计方式以便针 对不同性质的电路能有效地予以处理和实现。如果按照对布局布线位置的限制 和对布局模块的限制来分，则可以把版图设计方法分成全定制( f u l l c u s t o m ) 设计模式和半定制( s e m i c u s t o m ) 设计模式两大类。全定制模式对单元和布局 2 第一章引言 位置没有限制；半定制模式对单元的高度，电源线位置和单元引线端的日l 出方 向都有一定的限制。自动布图工具主要应用于半定制布图模式。 另一方面。为了解决日益复杂的版图设计问题，人们不断地寻求具有规则 性和分级性电路结构，以此为划分标准又可以得到各种布图模式。在自动化设 计中所常用的典型模式有门阵列，标准单元和宏模块等。 1 1 2 1 门阵列设计模式 门阵列( g a t ea r r a y ) 设计模式 t a n a k a 8 t h o f i b a 8 1 又称为母片法，它预 先设计和制做好各种规模的母片，其上除金属连线和通- t l 夕i 的单元图形是固定 不变且以二维阵列排列，单元图形之间是水平和垂直走线道，每个这样的单元 图形可以通过不同的金属连线得到不同功能的单元电路，如各种门电路，触发 器和寄存器等。如图1 1 所示。门阵列布图可以利用自动布局布线技术来完成。 门阵列设计模式由于其设计和制造周期短，费用低而广泛应用于小批量产品的 a s i c 设计。该方法的主要缺点是芯片利用率低，电性能差，这主要是由以下三 个因素所导致的 d e c a m p 8 6 ：首先，门阵列中所有的器件都是同尺寸，但有 些情况下需要器件尺寸小，有些情况下希望器件尺寸大，这时就得做折衷考虑； 第二，由于门阵列中布线区域是预制的，因此在布线拥挤的区域资源很紧张， 而在布线松散的区域资源又得不到充分利用；最后，随着门阵列中门的数目的 日益增加，在通常的设计中总会有些门弃置不用，因此门阵列的资源得不到完 全利用。 门阵列的一种特殊情形是去掉走线通道的门阵列，称为门海( s e a - o f - g a t e s ) s h r a 9 8 8 】。门海模式仍然保留了半定制设计方法的优点，母片预制，不同功能 的电路只需要改变金属连线。母片上没有通道，只有个二维的单元阵列。阵 列上一些区域为功能块区，其他区域为布线区。由于门海模式的功能块大小、 形状和位置都比较灵活，允许设计象r o m 和r a m 这样较大的模块，因此，与 门阵列相比，它有更高的芯片利用率和更广泛的灵活性。图1 2 示出了门海模 式的版图结构。 第章引言 图1 i 门阵列版图结构图尉1 2 门海版图结构 1 1 2 2 掭准单元设计模式 标准单元( s t a n d a r dc e l l ) 设计模式 k o l i e r 7 7 r i c h a r d 8 4 1 比全定制设计方 法简单。系统事先准备好2 0 0 到4 0 0 个包括有逻辑符号，拓扑和物理版图的“标 准单元”存入单元麾中，以供用户选用。所有标准单元的物理版图必须等商， 电源线和地线的位鼍是规范 七的，单元按行摊列，行与行之矧是肖线通道。对 三层残四层枣线赦标准单元，出于增加了囊线资源翻采用“跨单元蠢线”技术， 霹霓雪午出现不等嵩蕈元霸位蓬餐意懿；| 线端，这样膏剽于提高芯片鹃利雳率。 标准荦元模式弗鍪可以秘瘸舀动布局布线技术来完成。诧方法效率菇，设计周 期短，十分适用于专用集成电路( a s i c ) 的设计，楚目前应用黢广泛的设计方 法之一。图1 3 避一个典型的标准单元版图示意瞄。 一二正 一 l 一百卫 卫卫一； l 工 工口 | _ 匝工口 皿- | 图1 3 标准单元版图结构图图1 4 宏模块版图结构 。矗 第一章引言 1 1 2 3 宏模块设计模式 随着集成电路设计复杂性的增加，基于分级方式的设计策略显得越来越重 要 l a n 9 8 6 1 。在这样的设计策略中，一个复杂电路会被划分成一系列的子系统， 每一个子系统能够被一个或几个设计者单独完成。由于子系统的分散性，保持 尺寸相同或等高已不可能，因此需要处理不同尺寸子系统的布局方法，这就是 宏模块的布局问题 d a i 8 7 b u r n s 8 7 】。宏模块在理论上可以是任意多边形，但限 于实现上的困难它通常是具有任意比例的矩形。相比于门阵列和标准单元模式， 宏模块布局中模块的大小和位置都是任意的，因此宏模块布图模式可以取得更 高的芯片利用率和更好的电路性能。宏模块布图模式既具有布图密度高和布图 灵活的优点，又具有自动设计的高效率的优点，它是一种很理想的设计方法。 但由于宏模块布图的布图算法和布图系统较其它设计方法复杂，目前还没有一 个很成功的实用系统。一个典型的宏模块布图模式的版图示于图1 4 。 i 1 3 布图设计内容 布图设计问题是一个非常复杂的组合优化问题，一些经过再三简化的布图 子问题，如几何划分，平面填装，平面网格点的互连问题等，都已被证明是n p - - c o m p l e t e 问题或n p h a r d 问题 g a r r y 7 9 ，o h t s u k i 8 6 ，s a h n i 8 0 】。由于布图设计 的复杂性，要获得真正的最优设计几乎不可能。一般处理布图问题的方法是基 于分治策略，把布图问题( 即物理设计) 划分为逻辑划分( p a r t i t i o n ) ，布图规 划( f l o o r - p l a n n i n g ) ，布局( p l a c e m e n t ) ，总体布线( g l o b a lr o u t i n g ) ，详细布线 ( d e t a i l r o u t i n g ) 等几个相对独立的阶段，各个阶段分别求解难度相对较小的 几个子问题。各子问题的目标不尽相同，但做为同一问题的子问题，它们之间 又存在着内在的紧密联系。本文中，我们将着重围绕计算机辅助布图技术中的 布局问题展开研究。 1 2v l s i 布局问题 布局( p l a c e m e n t ) 是布图设计中的一个关键环节。一个质量很差的布局不 仅浪费芯片的面积，而且会直接影响其后的布线设计，造成布线困难。布局的 第一章引言 任务是要确定模块在芯片上的确定位置，其目标是在保证布通的前提下使芯片 面积尽可能小。随着工艺技术的发展，目前又提出一些希望优化芯片电性能的 布局要求，如考虑性能优化的时延驱动的布局。由于布局问题比较复杂，通常 把布局分成两步完成：初始布局和改进布局。一般情况下，在初始布局时用构 造方法给出布局问题的初始解；然后，通过迭代改进以优化布局结果。 在布局过程中需要考虑到很多因素，它们大体上可分为两类：第一类与单 元间的连接特性有关，本文中称它们为布局问题的拓扑特性；另一类与单元的 形状及尺寸有关，本文中称它们为布局问题的几何特性，最重要的几何约束就 是单元间不可交叠。 从布局的角度讲，上节所列的三种布图模式的主要差别在于它们的几何特 性及可对单元施加的有效操作。通常可对单元施加三种操作：平移，旋转和翻 转，门阵列具有最简单的几何特性( 所有单元都有同一尺寸) ，因而只需要做平 移操作。标准单元因为单元长度不同，几何特性显得相对复杂，除平移外，也 可以沿垂直于单元行的纵轴做翻转。三者中宏单元必须处理最复杂的几何特性 s h e r w a n i 9 5 】，因为单元的长和高都没有限制，对单元的三种操作都有可能。 由于单元间相互连接，每一单元的最优位置都与其它的单元有关，因此， 考虑布局问题全局的拓扑特性并同时地移动每一个单元是很有好处的。如果仅 考虑这一点，那么即使单元数目再大也可以用现在的计算机技术进行解决，然 而，由于单元间不可交叠等几何约束的存在，布局过程还必须考虑单元的形状 和尺寸，这就使得布局问题变得非常复杂。简而言之，需要同时考虑全局的拓 扑特1 洼和单元的几何特性是导致布局问题复杂化的主要原因。事实上，布局问 题是如此复杂以致于在一般情况下无法保证得到最优解，也不存在一个在大多 数实际应用中比其它方法好的“标准方法”，因此，对布局问题的研究无论是在 理论上还是在应用上始终吸引着众多v l s i 设计者的兴趣。 1 3 系统级芯片的发展对v l s i 布局算法的影响 随着集成电路的深亚微米制造技术，设计技术的迅速发展，集成电路己进 入片上系统时代。所谓的片上系统，又称为系统级芯片，也称为系统级集成电 路，其英文缩写为s o c ( s y s t e m o n a - c h i p ) 或者s l i ( s y s t e m l e v e l i c ) 。系 6 第一章引言 统级集成电路( s o c ) 在单一硅芯片上实现信号采集，转换，存储，处理和i o 等功能，或者说在单一硅芯片上集成了数字电路，模拟电路，信号采集和转换 电路存储器，m p u ，m c u ，d s p ，m p e g 等，实现了一个系统的功能。与传 统的芯片相比，系统级芯片具有以下一些特点： ( a ) 采用深亚微米加工技术 系统级集成电路多采用深亚微米加工技术。当代s o c 多数为o2 5 u m 0 1 3 u m 的设计规则，并采用多层布线技术( 一般在4 层以上) ，这与传统的i c 设计技术完全不同，因此给s o c 芯片设计带来了很多新的困难。集成电路设计 进入深亚微米阶段后，芯片上高密度互连线的寄生参数，如电阻，电容，电感， 以及由此引起的信号传输延时和信号串扰已成为设计极高速超大规模集成电路 的一个主要考虑因素 b a k o g l u 8 5 。在深亚微米工艺条件下，器件的特征尺寸缩 小，芯片内的互连线长度却急剧增大，走线延迟和门延迟相比变得不可忽视， 并成为主要因素 d o n a t h 9 0 j s u t a n 9 0 。由于深亚微米工艺条件下线闻矩和层间距 均非常小，线间和层间的信号耦合作用增强，在系统工作频率非常高的情况下 电磁干扰，信号串扰等现象变得很严重 g a l 9 5 y i m 9 9 】。这些变化给系统级集成 电路的设计引入许多新问题，也给s o c 的e d a 设计提出了更多的挑战。 ( b ) 采用基于p 核的设计技术 由于s o c 设计规模大，集成度高( 包括数百万门乃至上亿个元器件) ，而 且电路结构复杂( 包括m p u 、s r a m 、d r a m 、e p r o m 、f l a s hm e m o r y 、 a d c 、d a c 以及其它模拟和射频电路) ，要完成系统级芯片的设计是一项十分 艰难的任务。为了缩短投放市场时间，降低设计成本，s o c 的设计大量采用被 称为知识产权( p ) c h i a n 9 0 1 y a m a s h i t a 0 1 】的较大的电路部件或模块。碑 ( i n t e l i g e n tp r o p e r t y ) ，也有人称它为系统宏单元；( s y s t e m l e v e l m a c r o ) ，或虚拟部 件( v i r t u a lc o m p o n e n t ) ，芯核( c o r e ) 等，是一些已经过验证，可重复利用的i c 模 块。采用这些模块做为设计的基本模块无疑会大大降低设计的复杂度。 ( c ) 测试技术难度较大 s o c 上涉及到几种技术的集成，其上不仅包括数字信号，还有模拟信号。 同时精确地检测出模拟和数字两种电路，并支持扫描检测和嵌入式存储器检测， 将是一件很困难的事 z o r i a n 9 8 z o d a n 0 0 。与此同时检测工程师还必须面对缺 第一章引言 少俭测触点的现状。此外，高达数百兆的系统时钟频率以及各模块内和模块间 错综复杂的时序关系也给测试带来了很多困难。 系统级芯片的发展，给集成电路设计c a d 技术提出了许多新的需求 m a r t i n 9 9 c h e n 9 0 0 ，但目前的e d a 工具还不成熟，其处理能力跟不上s o c 工艺技术的发展，使得s o c 的设计不能充分发挥出全部性能。因此，发展符合 s o c 特点的集成电路c a d 技术，使之能适用于s o c 的设计，已成为当前刻不 容缓的紧迫任务。 1 4 论文组织 本论文的安排如下：第二章简要地介绍了v l s i 自动布局算法的设计目标， 线长漠型及常用的布局方法。第三章简单介绍了一些关于规划方面的数学知识。 第四章提出了取向向量的描述方式，并介绍了一种基于数学规划方法的宏模块 布局算法。第五章提出了虚模块的概念，并在此基础上介绍了一种基于总线优 化的宏模块布局算法。第六章首先介绍了互连线时延的具体计算方法，并以此 为基础提出了我们的总线时延的计算方法，然后介绍了总线时延驱动额定布局 算法。第七章为总结。 第二章v l s i 自动布局 第二章v l s i 自动布局 布局( p l a c e m e n t ) 是集成电路布图设计的重要环节。布局就是把元件或模 块安置在芯片的适当位置上，并使其满足一定的目标函数，它的输入是一组模 块，各模块的尺寸以及每个模块上的引线端信息和网表。由于布局的对象不同， 布局问题的详细含义和目标会有所不同。对于门阵列模式和p c b 的布局，布局 问题变成分配问题，其目标是达到较高的布通率：对于标准单元的布局，目前 一般是芯片的面积最小或连线总长度最小：对于宏模块模式的布局，所有模块 均为硬模块时为布局问题，其中一部分模块或全部模块均为软模块时则为布图 规划问题。 在v l s i 的布图设计中，布局是决定线网分配和长度的重要环节，它的结 果对于后续的布线质量有很大影响，并直接影响到电路的内部连线延迟。由于 在深亚微米工艺下，互连线造成的延迟己成为影响芯片性能的主要因素，因此 在现在的布局过程中，不仅要追求传统的优化目标减少布局区域。还应 当考虑到使整个芯片的连线延迟最小。所以在布局时还需要将连线延迟考虑在 布局问题的目标函数中，这样的布局问题称作性能驱动的布局( p e r f o r m a n c e d d v e n p l a c e m e n t ) 或时延驱动的布局( t i m i n g d r i v e n p l a c e m e n t ) 。 2 1 布局中的线长估计 一般布局问题的目标都与连线长度有关，而且考虑时延优化也与线长有 关。由于在布局阶段我们还没有完成最终布线，若希望在无几何走线的情况下 判断一个布局结果的好坏，就需要有简单且又有一定精度的线网长度估计方法 来估算线长。对线长的估计速度对于布局算法的性能具有决定性的影响，因此 一个好的线长估计方法对于任何布局算法都是至关重要的。对线长估计方法的 基本要求是：在保证速度的情况下，精度越高越好；另外，在产生“不可避免” 的偏差时，力争使对所有线网估计的差错率要大致相同。在线长估计中另个 基本假设是线网走线全部是水平或垂直走线，即所谓“曼哈顿距离”。 布局中使用的线网估算模型主要有以下几种，在这里我们假设n 为线网的 第二章v l s i 自动布局 端点集，( x 、，y i ) 为端点i 的坐标 2 1 1 最小斯坦纳树模型 最小斯坦纳树是一种线网拓扑的最小树，其端点除了线网端点集n 外，还 有斯坦纳交叉点。可以说最小斯坦纳树是最优的线长估计模型，但是求解最小 斯坦纳树却是一个n p c o m p l e t e h i 题 g a r e y 7 7 ，因此利用最小斯坦纳树来计算 线网长度，虽然精度高，但计算量太大。 2 1 2 最小生成树模型 最小生成树是另一种最小长度树，其端点只包括线网端点集n 。最小生成 树可以在多项式时间内完成，它比最小斯坦纳树计算量小，但精度不如后者， 不过h w a n g 己证明直线最小生成树的长度与直线最小斯坦纳树长度的比不超过 3 2 h w a n 9 7 6 ，h w a n 9 7 9 。 2 1 3 最小生成树模型 源到漏端的最小连接( m i n i m u ms o u r c e t o s i n k c o n y l e c t i o n ) 也是棵树， 其根是线网的源端，树的每条边都是从源端到漏端的连接。这种连接也日q 作星 形连接，假设源点为s ，其总长度可写为： 。= 艺( 1 x ，一x ，i + i y f y ，| )f 2 1 ) f # i 其中( x ；，y s ) 为源端坐标。如果在布局中考虑线网延迟，由于线网的延 迟与线网总长度和线网的源端到漏端的距离有关，因此在优化连线总长的目标 函数中用源到漏端的最小连接来表示线网长度有利于减小芯片的最大延迟。 2 1 4 边界框和半周长模型 边界框( b o u n d i n g - b o x ) 是指包含线网端点的最小矩形，其周长印为线网 线长： l = 工一x 咖+ y 眦一) ，m ( 2 2 ) 第二章v l s i 自动布局 半周长模型( h a l f - p e r i m e t e r ) 为边界框周长的一半。 边界框和半周长模型是两种十分简单的线网长度计算方法，被广泛应用于 以线网总长作为优化目标函数的布局中。在不考虑绕线情况时，对于两端线网 和三端线网，半周长模型给出的是线网线长的精确值。在一个典型电路中，由 于两端和三端线网所占的比率往往比较高，因此半周长模型通常都能给出比较 高效的结果。 2 i 5 完全图模型 完全图( c o m p l e t eg r a p h ) 是包括线网所有端点的一个完全图，用完全图 来描述一个信号网实际上是把多端线网转化为两端线网的一种做法。为了避免 过于强调大线网的影响，般在应用完全图模型时，在每条线网前都要加上一 个权重u 。完全图线长公式为： l 。= 0 3 。+ ( 1 x 。一x ，l + l y 。一y j l ) ( 2 3 ) f t ，l ，t “ 式中，完全图两端点间的边长用它们之间的曼哈顿距离来计算，权重u 。一般取 作1 n 或2 n ，n 为线网的端点数。在一般情况下，一条线网用完全图描述的连 线长度与最小生成树的连线长度基本上是线性关系 o h i s u k i 8 6 。 2 1 6 二次线长模型 这个模型最早由h a l l 提出 h a l l 7 0 】以后在许多布局系统中得到了成功的应 用。这个模型用如下的表达式作为线网的线长估算公式： l 。= ( x 。一x j ) 2 + ( y ，一y 1 ) 2 ( 2 4 ) f ， 式中l 。是线网引脚之间欧几里德距离的平方和。二次线长模型的最大优点在于 函数的连续性，它的缺点是当线网较大时( n 2 ) ，估算公式往往会过大估计线 长，因为二次线长模型的计算中实际也暗含了完全图的计算方法。此外该模型 的计算时间和n 2 成正比。二次线长模型较为广泛地应用于基于数学规划的布局 系统e 0 h a l l 7 0 ，c h e n 9 8 4 ，t s a y 8 9 。 笙三里竖坠鱼垫变旦 一一 2 1 7 重心模型 重心模型 s h a 8 9 实际是二次线长模型的一种。对于个n 端线网，重心线 长模型是指：首先确定这n 个端点的质心s 的位置，然后计算由s 到各个端点 的平方距离之和，作为线网的线长。重心线长模型的计算公式为： 工。= ( j ，一z ：) 2 十( y 。一y ，) 2 】 ( 2 5 ) 其中( x ；，y s ) 为质心s 的坐标，定义为： 铲亩+ 善_ 但6 胪击+ 酗 重心模型保留了二次线长模型连续性的优点 算时间只和端点数n 成正比。 ( 2 7 ) 并能避免过大估算线长，它的计 2 2 布局的目标函数 布局阶段的要求是把模块分配到芯片的合适位置，一股的目标包括芯片面 积最小，布通率最高，电性能最优等。除此之外，布局时还需考虑一些工艺和 电学上的约束条件，如：模块之间不能重叠：某些模块( 如p a d ) 必须布在芯 片周围：电源线的散热要求；信号线不能相交；某几个模块( 如i o 模块和p a d ) 必须邻接安置等。 目前比较实际的布局方法是寻找一个比较简单，计算时间较短而又能反映 布局优化目标的目标函数。不同的芯片布局模式对目标函数的选取应有所不同， 较为常用的有以下三种目标函数： 2 2 1 基于连线总长的目标 设某一个芯片的布局p ，其连线总长为： r ( p ) = l 。 ( 2 8 ) 函 其中，。是采用某种线网模型所得到的线网长度估计值，n 为所有线网集合。 基于连线总长布局的目标是使t 口) 最小化。当前大部分的布局方法都以总线长 第二章