（电路与系统专业论文）用于VLSI物理设计的计算智能算法研究及应用[电路与系统专业优秀论文].pdf

摘要 大规模集成电路设计正向深亚微米工艺不断推进，已经突破1 0 0 n m 大关。现 有t d a 工具难以应付复杂度呈指数增长的诸多v l s i 设计难题，也缺乏对深亚微 米工艺下一系列新问题的考虑。v l s i 物理设计巾的布局、总体布线和详细布线 是典型的n p 问题，而计算智能方法为解决n p 复杂度的大规模问题展示了广阔前 景，因此研究各种计算智能算法求解这类问题，对于满足深亚微米工艺下高性能 物理设计中的诸多要求是十分重要的。 本文工作正是在这样的背景下，基于中国博二e 后基金，结合四j j i 省科技厅的 应用基础项目计算智能在超大规模集成电路物理设汁巾的应用，对汁算 智能算法及其在v l s i 物理设计中的应用，展开了一些研究工作。l 本文完成的主要工作如下： 1 )首次将分形技术引入到v l s i 物理设计小，提_ 1 5 了一种崭新的布局线长估计 方法，它与传统的线长估计方法比较，估i - i + 结果更接近于实际线长。汁算机 仿真结果表明它是一种实用且有效的线长估汁方法。 2 ) 首次将禁忌搜索算法与结群技术相结合，并将其分别应用于门阵列布局和 b b l 布局中，计算机模拟结果表明该算法鲁棒性强、有效，适应性广，适用 于大规模门阵列布局和b b l 布局问题。 3 )分别用神经网络技术、遗传算法和蚁群算法埘两端线网砸线问题进行了研 究，并对结果进行了分析比较。在不同布线阶段，分别采用上述方法，可大 大提高两端线网布线效率。 4 ) 提出了一种基于均场退火的通道布线算法，并与基于h o p f i e l d 神经网络的 通道算法进行了比较，结果表明在得到较好布线结果的情况下，其求解优化 时间大大降低。 关键词：v l s i 物理设计：计算智能；分形z 布局k 两端线网布线；通道布线k 接簦 a b s t r a c t v e r yl a r g es c a l ei n t e g r a t e dc i r c u i td e s i g ni sp r o g r e s s i n gr a p i d l yi n d e e ps u b m i c r o nt e c h n o l o g y ，w h i c hh a sb r o k e nt h r o u g ht h ec h a r a c t e r i s t i c m i n i m u ms i z eo fl o o n m 。t h i st r e n dh a sp u tg r e a tc h a l l e n g e sf o rt h ep r e s e n t a v a i l a b l et o o l so fe l e c t r i cd e s i g na u t o m a t i o n ( e d a ) 1 ti si m p o s s i b l eo r v e r yd i f f i c u l tt os o l v et h e s eh i g h l yc o m p l e xp r o b l e m sb ym e r e l yu s i n g t r a d i t i o n a lo p t i m i z a t i o na l g e r i t h m s b e s i d e s ，m a n yn e w l ye m e r g i n ga n d s p e c i f i cd e e ps u b m i c r o nt e c h n o l o g yp r o b l e m s ，w h i c hw i l l s i g n i f i c a n t l y i n f l u e n c ec h i p sp e r f o r m a n c e ，s h o u l db et a k e ni r i t ea c c o u n ti nm o d e r ne d a d e s i g nt o o l s a sf a r a st h ev l s i p h y s i c a ld e s i g n i s c o n c e r n e d ，m a n y p r o b l e r o sh a v eb e e np r o v e dt ob en p - c o m p l e t e ，s u c ha sp i a c e m e n t ，g l o b a l r o u t i n ga n dd e t a i l e dr o u t i n g o n t h eo t h e r h a n d ，t h ec o m p u t a t i o n a l i n t e l l i g e n c e ，an o v e la p p r o a c ho fo p t i m i z a t i o nt e c h n i q u e sh a v es h o w i n g i t s g r e a tc a p a c i t y a n d p o t e n t i a l i n s o l v i n g1 a r g e s c a l ec o m p l e x p r o b l e m s ，h e n c et h es t u d yo fc o m p u t a t i o n a li n t e l l i g e n c em e t h o d st os o l v e e x i s t i n gp r o b l e m si sv e r yn e c e s s a r yf o rh i g hp e r f o r m a n c ep h y s i c a ld e s i g n i nt h ed e e ps u b m i c r o nt e c h n o l o g y + u n d e rt h i sb a c k g r o u n d ，b a s e do nt h ec h i n ap o s t d o c t o r a t ef o u n d a t i o n a n dt h ep r o j e c te n t i t l e d “a p p l i c a t i o no ft h ee o 辩p 娃t a t i o n a li n t e l l i g e n c e i nv l s ip h y s i c a ld e s i g n ”o fs i c h u a ns c i e n c ea n dt e c h n o l o g yb u r e a u ，t h i s d i s s e r t a t i o ni si n t e n d e dt od e v e l o ps o m ea l g o r i t h m sf o i v l s ip h y s i c a l d e s i g nb a s e do nc o m p u t a t i o n a li n t e l l i g e n c em e t h o d o l o g y t h em a i ne o n t r i b u t i o n so ft h i sd i s s e r t a t i o n a r es u m m a r i z e da s f o l l o w s ： i ) i n t r o d u c et h ef r a c t a lt e c h n i q u ei n t ot h ev l s ip h y s i c a ld e s i g na r e a an o v e lf r a c t a la p p r o a c hh a sb e e nd e v e l o p e dt oe s t i m a t et h ew i r e l e n g t h o fp l a c e m e n t 。t h ec o m p a r i s o nb e t w e e nt r a d i t i o n a lm e t h o d sa n dt h en e w a p p r o a c hh a sb e e nd o n e t h es i m u l a t i o nr e s u l to b t a i n e db yt h en e w a l g o r i t h mi ss u p e r i o rt ot h a to ft h eo l do n e 。t h i sf a c ti m p li e st h a t t h ef r a c t a la l g o r i t h mi s v e r ye f f e c t i v ea n di np r a c t i c 0 1 2 ) b yc o m b i n i n gt h et a b us e a r c ha n dt h ec l u s t e r i n gt e c h n i q u e ，w ep r o p o s e 电子科技大学博士论文 ah y b i r da l g o r i t h mt os o l v et h ep l a c e m e n tp r o b l e m s b o t hf o rt h eb b l a n dt h eg a t e a r r a yp l a c e m e n t s i m u l a t i o nr e s u l t ss h o wt h a to u rh y b i r d a l g o r i t h m i s o fr o b u s t n e s sa n d e f f e c t i v e n e s s ，i t i s e x p e c t e d t h e a l g o r i t h mi s a l s ou e s f u li no t h e ro p ti m i z a ti o np r o b l e m s 3 ) t ot e s t i f yt h ef e a s i b i l i t yo fu s i n gv a r i o u sc o m p u t a t i o n a li n t e l l i g e n t a l g o r i t h m ，s u c ha sn e u r a ln e t w o r k s ，g e n e t i ca l g o r i t h ma n da n tc o l o n y s y s t e ma p p r o a c hi ns o l v i n gat y p i c a lr o u t i n gp r o b l e r r r 一七w ot e r m i n a l n e t l i s tr o u t i n g ac o m p a r a t i v es t u d yo ft h e s ea l g o r i t h m sw i t hr e s p e c t t oat r a d i t i o n a la p p r o a c h m a z er o u t i n ga l g o r i t h mi sc o n d u c t e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ec o m p u t a t i o n a li n t e l l i g e n ta l g o r i t h m s a r es u p e r i o rt ot h et r a d i t i o n a lo n e 4 ) am e t h o db a s e do nm e a nf i e l da n n e a l i n gi sd e s i g n e dt os o l v et h ec h a n n e l r o u t i n g ，ac o m p a r a t i v es t u d yw i t hr e s p e c tt oh o p f i e l dn e u r a ln e t w o r k a p p r o a c h i sp e r f o r m c e d s i m u l a t i o nr e s u l t si n d i c a t et h a to u ra l g o r i t h m i sa b l et o g i v e h i g hq u a l i t y s o l u t i o na n d r e m a r k a b l y r e d u c e d c o m p u t a t i o nt i m e k e yw o r d s ：v l s ip h y s i c a ld e s i g n ，c o m p u t a t i o n a li n t e l l i g e n c e ，f r a c t a l t e c h n o l o g y ，p l a c e m e n t t w o - t e r m i n a lr o u t i n g c h a n n e l r o n t i n g i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 徐兰日期：沙。年，月少日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编人有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：知刃年f 月形日 第一章绪论 第一章绪论 1 8 世纪中时，王致革会将人类从农业时代繁到了正业射代，近5 0 年电予产 业的发展使人类进入了信息时代。信息技术( i n f o r m a t i o n t e c h n o l o g y , i t ) 产般是 二十世纪以寒发展最为迅速的产业，其基础怒集成电路( i n t e g r a t e dc i r c u i t , 憋 产业。i c 不仅改变了以计算机和通信为代表的整个现代电予工业，而且被认为 是现代工业的“粮食”。其发艘水平楚衡量一个国家综合实力的重要标志i l j 。9 0 年代，以集成电路为熬础的多媒体和因特网的发展推动着人必从工业经济向知谈 经济发展，促j 挂了信患产业的商速发熙。据统钢，信息产业疆以每年3 0 的遮度 增长，1 9 9 0 年产值是1 4 8 9 亿美元，1 9 9 5 年为6 4 0 0 亿美元，2 0 0 0 每已超过了1 万亿美元，成为全球第一大产业。世界发达嗣家的信息产业融占g d p ( 国内，土产 总值) 的1 0 以上。单程1 9 9 5 年，美溺、f l 本、法国、英国等函的信怠技术国日 就已占全球市场的7 7 。现在因特网已经渗透到社会的各个领域，履正以每年 1 0 0 的速度发袋。全球十强公司，半数与信憨产韭有关。我瓣l e 产娩正处在加 速发展的前夕。为加强基础性制造业的建设，在集成电路方丽做了臣大的投入， 如2 0 0 0 年1 1 月上海宏力率寻体公司投入1 6 3 亿美元建立了凝有0 2 5 微米强下 生产工艺的尘产线，2 0 0 0 年1 2 月北京投入1 5 亿美元建设北寐北方微电子基地。 并诗翔在未来l o 年内投入2 0 0 亿美嚣建立2 0 条技术承平在8 英寸0 2 5 微米及 更高水平的集成电路歙产线，预计用1 0 年左右的时间，将建成在微电子工艺研 发、集成电路设计、集成电路垒产线专用设螽研制良及集成电路材j l i 研制等方面 与世界先进水平同步的国家级研发中心。以上事实表明，集成电路已成为了信息 产韭的藿要支撵弘| 。 集成电路自诞生以来，经历了小规模集成( s s i ) 、中规模集成( m s i ) 、犬规 模集成( l s i ) 鑫擘发震阶段，瓣嚣邑滋入超大靛模集残( v l s i ) 和特大矮楱集成 ( u l s i ) 阶段，进入了片上系统( s y s t e mo nc h i p ，s o c ) 时代。伴随着集成电 路懿发袋，e d a ( e l e c t r o n i cd e s i g na u t o m a t i c ) 技术已成为奄子设计技术瓣孩 心。e d a 是指以计算机为工作平台，融合了戍用电子技术、计算机技术、智熊化 技术簸新成果褥研秘裁豹毫予e 矗d ( c o m p u t e r - i d e dd e s i g n ) 逶弱软 孚包，主 要能辅助进行三方面的设计工作：i c 设计，电子电路设计以及p c b 设计。 1 。1 e d a 技术的发展与寒来豹挑战 。 。 e d a 技术豹发展过耩 回顾近3 0 年电子设计技术的发展历程，w 将e d a 技术分为三个阶段。 l u 予科技人学博：i ：学位论文 七十年代为c a d 阶段，这一阶段人们行始用计算机辅助进行i c 版图编辑和 p c b 蠢蜀蠢线，取代了手王搡终，产玺了诗算祝辘糖设计鳃概念。 八十年代为c a e ( c o m p u t e r - a i d e de n g i n e e r i n g ) 阶段，与c a d 相比，除了 纯粹鼢图形绘制功能终，又增撩7 电鼹臻能浚诗穗结擒设诗，势纛逮过憩气连接 网络表将两者结含在一起，以实现工程设计，这就是计算机辅助工程的概念。 c a e 豹主鼗凌爱爨：琢瑗强输入，逻辑辏寞，惫糖分援，自动奄弱蠢线，p c b 后分析。 丸卡缮霞为e s d a ( e l e c t r o n i cs y s t e md e s i g na u t o m a t i c ) 黢段。尽管e a 轻c 勰 技术取得了巨大的成功，但并没有把人从繁重的设计工作中彻底解放出来。在整 令设谤过程孛，叁动鼗和麓毙化稷发还不摩，各秘e d a 软馋赛瑶母差万别，学习 使用困难，并且虱不兼容，直接影响到设计环节问的衔接。基于以上不越，人们 嚣始追求樊缨整个设诗过糙豹自动化，这就是e s d a 即电予系统设计自动他，其 主疆标志是系统级设计工其的推出( 包捕目前已广泛使厢的硬件描述语言v h d l 翻v e r i l o g ) 秘逻辑设计王具豹广泛应用i t - i l l 。 目前的e d a 系统功能覆盖了电子设计的全过程，且有肝放的环境和标准化的 数据接日，可以说宥担当舞豹水乎。虽然翔此，e d a 的设计技术仍然落麟子工艺 生产制造技术的发展。 1 9 6 5 年，i n t e l 公司创始人之一豹蘩攀长g o r d e nm o o r e 在研究存贮器芯片 上晶体管增长数与时间的关系时发现，每过1 8 2 4 个月，芯片集成度提高一倍。 这一关系披称为穆尔定律( m o o r e sl a w ) ，一直淞用至今。见图1 1 1 1 8 l 。 m c | 坤糟“州撕kh 坩r0 呻 娜 翻i ，lm o o r e sl a w 从集成电路的发展肴，每前避一步，线宽将莱上一个o 7 的常数。邵：如聚 把o 2 5 p m 看作下一代技术，那么几年后又一代新产品将达到o 1 8 岬，网前已选 2 iviosg 第一窄缔论 到o 1 3 p m ，进入了深溉微米时代，依次类推，辩经过两三代，具体将在2 0 1 2 年， 集成电路帮将巅达0 0 5 9 u n ，甏迸入纳米瓣我。集成懿路发袋豹每一代大约黎要 经过3 年左右。这些演变在半导体工业协会1 9 9 7 年发撕i 的荚国半导体技术蓝 图中褥到了缀努匏籀述。这魏颈嚣零获蟪褥剿工韭棼熬 委实，翔2 0 0 0 年1 2 嚣 1 1 日，英特尔公司说它最新研制成功3 0 纳米晶体管( 1 纳米为十亿分之一米) 。 这一突玻将使酝睡芯嚣速疫在令惹5 翻1 0 年内提裹刭蟊藏熬l o 嫠，褥使英特零 公司可以在未_ 宋5 到l o 年内生产出集成度为4 亿个晶体管、运行速度为每秒 i o g h z 、王露惫蘧在i 铰苏下蠹冬凝型蕊冀。瑟疆熬，蛮场上爨售戆速发最抉懿芯 片“奔腾4 代”集成了4 2 0 0w 个晶体管。芯片制造商难在向0 1 0 微米处理器工 艺迈遴，如n e c 公司予2 0 0 0 冬1 0 月3 0 目宣奄，其麟发或功豹、毽界上首次突 破o 1 微米的半导体加工技术，并且将应用到实际的系统中。2 0 0 2 年8 月1 3 同， 英特承公司宣蠢，决定采用鞭嚣发出豹线宽纳米豹制造技零，在2 0 0 3 年下半 年大批量生产下一代芯片，它可以使芯片中晶体管的长度从先前的6 0 纳米降至 5 0 纳米，从嚣擞抉处壤器豹处理速度 1 9 l 。 1 1 2 未来十年v l s l 布网技术的新挑战 1 9 9 9 年4 旁，在美国举幸子的第三拜国际玲圈技术学术讨论会上，对未来l g 年布图设计的嚣求与发展趋势进行了深入的讨论，提出了“米来十年v l s i 稚图 技术韵十大闻藤”。它蹩基予涞来千攀的半导体工艺鹃发展情况丽稳掰的粒承猫。 表1 i 给出了1 9 9 7 年一2 0 0 9 年世界集成电路正艺发展的趋势，包括线宽、芯片 蟊袄、萃冀上的晶体镑数、露钟频率、稚线滋羧、电源电压、连线总长；嚣佟内 部延迟、连线延迟等。从表1 1 中可以看出，朱来十年中，布豳技术高集成度( 数 百g & l j q ，多麓( 7 8 层) 金瘸静毒秘密绫离趱，在分级设计策珞、嵩经能豹摩 局算法的采用就更显羹要。除此之外，芯片的性能也对布图技术提出了更高的要 求，嚣丽必矮在布蚕辩考虑互连线懿瓣延帮串捷阗瑟。 表1 11 9 9 7 2 0 0 9 邻世界集成电路丁就发展的趋势 y e a r1 9 9 71 9 9 92 0 0 1 2 0 0 32 0 溺2 g t e c h n o l o g y ( n m ) 2 5 01 8 01 5 01 3 01 0 0 7 0 t r a n s i s t o r sl l 蝇2 1 m4 0 m7 6 m2 0 0 m 5 2 0 m a r e a ( m m 53 3 4 03 8 54 3 05 2 06 2 0 c l o c k ( m h z ) 7 5 01 2 0 01 4 0 0 1 6 0 02 0 0 02 5 0 0 m i n w i r e 。w i d t h 轴园2 鑫。1 8 01 5 01 3 01 0 07 0 m e t a ll a y e r s66 7777 88 9 v d d ( v )2 1 51 6 51 3 51 3 51 0 50 7 5 t o t a lw i r el e n g t h ( m ) 8 2 01 4 8 072 8 4 0 5 1 4 01 0 0 0 0 l b u f f e r sp e rc h i p6 k2 5 k? 5 4 k2 3 0 k7 9 7 k | d e v i c ei n t r i n s i cd e l a y ( n s ) 0 7 0 5o 。5 1 10 ，4 8 70 。4 5 80 ，3 9 2 0 。2 1 9 u 予科技人学博“l ：学位论义 s r c 提出的i o 个棚i 图技术关键问题怒： 1 2 。 穰| 夹级帝黼援术 在设计芯片时，用于模块级柑局和时延分析验证的迭代时间是大爨的，在 满足用户对时延要求的情况下，希望有模块缀布崩算法来影响对延、臻声和面积 的参数，以减少迭代过程，缩短产品设计阆期。其目的是开发一种模块级布局算 法，满足一些约束条件，闻对考虑所需缓冲单元的铅届。般采瑙层次武戏称分 级式的设计策略，在芯片上设若干层次。模块级布局算法先估计模块面积和时延， 然后进入该模块，按照约慕条彳睾对下一缀模块遴符布局奄绕。算法优先考虑饶亿 时延，然麟是面积，噪声和功耗作为可选。 1 1 2 2 布豳规踅f j 的模块外形生戒技术 靠局搜划时，瓣要有糖确估计其面积翔外形的模块作为输入，并能给出几种 不同可能的选择。其目标怒开发一个设计工其，它能根掇模块类型、内部单元数 量、互连线要求和工艺参数去计算模块恧积和外形，且考虑到阵列、随机控制逻 辑、多米洛逻辑和数据通道等不问电路的特点和复杂往。 1 2 。3 甚大模块妁布局技术 在目前的a s i c 设计中，希望有能处理2 0 m 晶体管的半定制的设计工具。此 终，在分级设计审，终为模块级设诗工具也露要蠢这样的撩准单廷设计王具，势 希塑模块能设计得越大越好，从而减轻模块级设计负担。其目标是丌发个能处 理l ，0 0 0 ，o o o 个零元弱掰妁蠢弱算法，能在王 擘站上运行，计算对闽不超过1 2 1 6 小时。它鼹考虑时延约束。允许对时延、面积和功耗进行局部优化，其优化顺序 楚鼹延、嚣积、嗓声彝功耗。必要慰还娶考虑工艺制造约束。 1 1 2 4 溉连线驱动的布豳规划 在深鼹徽寒下，互连线已戏为葱慧惩避豹圭婺因素，在设计翡冬令除段都要 考虑它，考虑得越早越有利，以防止最餍结果不9 满足时延、功耗或芯片面积的 要求。其瓣标是秀发一个霉嚣蕊鲻工具，把互连线搀为个重要郝分，在把一个 溅辑模块布在一个二维空问的同时，把甄连线和在三维空间内。这样的布图规划 王其能处灌模块翁嚣积、j 蓼状，爻圣准拳l 纛送约索，毙处壤互连线熬跨殛、藕会、 噪声和屏蔽约束，也能考虑缓冲单元的捕入以满足长互连线对时延的要求。 ，2 5 考虑功率翻融镑绥差瓣纛逮度辩锋弼竣话 在同步数字系统中，时钟信号用作系统中数据传送的时间参考。时钟线网具 脊最大斡扇出和激大线长，它受工艺交纯豹影鹅最大，警线宽交夸辩，佟为长纛 连线网的时钟线的线电阻变大，鼠时钟线网的设计对芯片性能的影响最大。其研 究蟊标是拜发一个时锋线两静设计工兵，它能褥侯所有时锋线网端熹哥纛豹露镑 第一章缝论 信号，弗具有所有要求的时钟偏差和功耗要求。 1 i 2 6 考虑嘏阻、电感和电容的布线技术 出予太宽度、长距离豹互逑线豹成用和运算速度的增加，电感的作用已不能 忽视。同时，互连线间的耦合电容也在增加。以往的布线算法都是在基fe l m o r e 、 m o m e n t 或r c 模型，在深亚微米、超深甄微米蕤至于纳米工艺下，和线算法辩也 不能忽略电感和耦合电容的作用。其两标是开发一个r l c 柿线器，稚线时考虑线 网豹电感l 和精合电容c ，这就器要裔一个快速时延釉噪声估计的r l c 模型。 1 1 2 7 布图驱动的综合技术 为了捷予浓薅，羁瓣把综会和农图餐或趸掰个独立豹予过程分别求孵。织髓 着传输线延迟的增加，在综合时必须考虑枷圈信息。当前的做法是改进连线熊载 模型，势把连线信息反馈到综合俊化蚋锤环中。但此做法没蠢解决离性能设计中 所需癸的综合和布图的集成，并且由予综合怒非增量式的，困此所需时间太长。 萋曩究王俘熬晷椽是开发个用于艇枫控铡逻辑集成的逻辑综食和矩燃工具。 1 1 2 8 面向s 0 i 特殊工艺且比映射方法更好的物理设计技术 绝缘薅底( s 0 1 ) 3 1 艺毙穰滔_ i 慧鸯雯，j 、瓣延迟，逛箕低堪金属连线豹攒会 效应又比c m o s 大，因此，用单纯的映射方法不能发挥s 0 1 工艺的优点。开发 令铮辩s 0 1 王艺，毙考虑瑟获、辩延、功耗秘耦合效疲豹物璎设计算法巍软传是 必要的。 i 。 。2 。9 苓藩糙蓬戆毫蕊疆取羧零 由于有长和宽的艇连线及芯片速度的增加，电感的作用融不能忽视。此外， 精确静电惑撬敬需要疆全三绦分析技术，太费时阕。磷究露溶莛嚣发一个鼹乎锈 理布圈设计的不同精度要求的电感模魁。它可以为用户提供从特别快速但粗略到 + 分精确经费辩静范瓣凑秘不溺豹横挺选释。 i 1 2 1 0 与耦合效应有关的静态时惩分析技术 溺前，静态时延分析仅考虑连线r e 和器件的延遴，并来考虑线游的耦含电 容，两互连线上耦会电容的增加严重地影响静态时延估计，并且相邻连线的开关 跳变可能减少或增大连线的薅遮。倍弩延迟误差可能影响稚黧凌诗的最终缩祭建 否满足给定的约束。研究目标是开发一个考虑耦合效应的静态时延分析算法。 l ；l 上千个布图设计关键阐惩已受割整赛务蘸v l s ic a d 学者、磷究入受耩工 业界的广泛关注，这蝗闯题的解决必将进一步推动i c 工业的发展。 程2 0 0 1 年的d a c 会议上。提斑了e d a 技术发展的三犬危梳：葫率危撬、 复杂度危机和互连线危机，它对布图技术提出了更高的要求，对v l s ic a d 工作 者来说，又迎来了新的挑战。 u 予科技人学博- ：学位论史 1 2 大规模集成电路设计概述 1 2 1 大规模集成电路设计过程 大蕊模集成电路( 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 ) 设计周瓣分为良 下几个步骤：系统规范说明，功姥设计，逻辑设计，电路设计，物理设计，设计 验证，蒂避，葑装和灏试。v l s i 设计可能会在一个步骤中，或在咒个步骤之阉 反复交替进行。v l s i 电踌的设计流程如圈1 2 所示。 其中，系统蕊范说明包括系统葫能、经能稻物理尺寸。j l ：羚，还器黉考虑逡 掭设计模式和制造工艺。最终结果是确定芯片尺寸、工作速度、功耗和系统功能。 在功能设计审圭要考虑系统酌行楚特往，常蹋豹方法是辩穿鬻或者表示各予 模块问关系的关系图。利用这些信息可以激进整个设计过程或简化后续的设计步 骤。 i系统规范说明 l功能垃谴 毒 逻辑设计 t i 乜姑嫂计 物理设计 设计璇证 毒 制造 毒 封装和测试 翻1 2 ￥璐 莰谗漉程 逻辑设计中可以得到一个表示系统功能的逻辑结构并反复测试其m 确性。设 计者逶鬻翅文本、添理黧或逻辑嚣表示设诗，鸯孵也爰搬零方程表示设诗。在设 计过程中，还要对该逻辑结构进行模拟以验证芨正确性，并对其进行优化设计成 称之为逻辑最，l 、貔。 电路设计时骥考虑逻辑部件的电路实现，包括速度和功耗。此外，还要注意 嚣耱元移豹意毪能。逶豢爰诿缨瓣毫路嚣来表承邀黪设诗。 矗 第一常绪论 物理设计即版图设计，是v l s i 设计中最费时的一步。物理设计要把每个元 件的电路表示转换为几何表示，同时，元件闯连接的线网也被转换成几何连线图 形。电路的几何表示称为版图。版图设计要符合与制造工艺有关的设计规则要求。 由于版图设计的复杂性，往往把版图设计分成若二l ：予步骤进行，如图1 2 所示。 设计验证也称版图验证，它确保版图设计完成后所得到的几何图形满足制造 工艺要求和符合系统的设计规范。 芯片制造过程包括芯片准备、杂质注入、扩散和光刻等工艺。 在完成芯片制造后，要进行封装和测试。安置在印制电路板上的芯片可封装 成双列直插式或引脚阵列式。用于多芯片模块的芯片可以不封装。 用户根据不同产品的性能要求、生产量的大小和设计周期的长短，有多种稚 图模式可以选择。v l s i 设计的布图模式主要包括积木块自动布图( b u i i d i n g b l o c kl a y o u t ，b b l ) 、标准单元、门阵列、门海设计模式和f p g a ( f i e l d p r o g r a m m a b l eg a t ea r r a y ) 。实现相同的功能，f p g a 是最快的方法，b b l 布图模 式则最慢，然而f p g a 占用的芯片面积最大、性能最差。反之b b l 布图模式因为 单元( 或模块) 的类型、大小和单元布局都很灵活，故能够设计出高性能的芯片。 但由于b b l 布图设计非常复杂，它的设计周期比其它稚图模式要长，且自动化过 程最难，因此要耗用更大的计算资源 i , 2 3 - 2 6 1 。 1 2 2 物理设计过程 v l s l 物理设计( p h y s i c a ld e s i g n ) 也称为布图设计( l a y o u td e s i g n ) 。其输入 是电路的元件说明和网表，输出是设计好的版图。即根据电路和工艺要求完成芯 片上单元或功能块的安簧，实现它们之| l i j 所需要的互连。 由于物理设计的复杂性，它又分为以下几个步骤：划分、布图规划、布局、 总体布线、详细布线和压缩。物理设计流程如后页图1 3 所示。 一个芯片可以包含数以百万计的晶体管。划分过程将各部件分组形成多个模 块( b l o c k ) ，各模块的大小和在芯片上的精确位置由稚图规划和相局算法确定。 布图规划和布局算法的目标是最小化芯片的面积同时满足约束条件，如模块间无 重叠且完全互连等。总体布线和详细布线组成了复杂的布线过程，总体布线确定 一个线网的大致走线，它将各线网合理地分配到各布线区域中，以确保尽可能高 的布通率：详细布线则是最终产生线网在芯片上的实际走线，及生成各线网的几 何版图。压缩的任务是从各个方向上压缩芯片的版图，以期将芯片的总面积减小。 在整个集成电路设计过程中，物理设计是与产品研制和生产直接相关的一个 设计过程，直接关系到芯片设计的周期、生产成本和产品质量。这一步骤也是以 往人工设计中耗时最多、错误率最高的设计过程之一。因此，它也是近年来e d a 工具中发展最快，自动化程度最高的领域之一。而且，随着v l s i 向深亚微米， 7 电爹科技人学搏。j ：学位论义 甚至纳米推进时，它也是受工艺影响最大，面临的机遇和挑战缴大的领域之一。 物墁设计 7 l列拉 0 布豳规划和布局 i 电路设l 十 0 芯片瓤造 慧体布线 l 详嘲毒筏 1 3 计算智能算法 篷i 3 锈理澄讳避程 山上带概述可见，v l s l 物理设计巾的棚f 局、嘶i 线锦问题晟高度复杂的，风 荑孛缀多溜题已彼迁暖搀n 卜灏难阗题。疆羞v l s i 韵深亚微寒、超深亚擞涨 撼至纳米置艺推进时，系统规模不断扩犬，问题空闻维数随之居0 增，传统的优化 葵法要么疆辐诗舞塞擦炫( 如穷举法，线性溪越等) ，要么易骥入禺邦极癯，嚣 法接近全局最优解( 如最速下降，贪心法等p , 2 4 2 6 1 ) 。因此对各种新的智能优化方 浚弱职究应运嚣起，先爨提出了入= 神经网络、遗传算法、摸拟退火、蚁群算法、 綮忌搜索筹算法。各种方法各有千秋，但到目前为止，还没有任何一种方法可以 鸯效遗威趱于勰决v l s i 豹理设转中魏蜒骞润题。人们越来越认识到将各秘蜣化 方法相结合，即采用所谓鸡尾酒式综合优化算法( c o c k t a i lo p t i m i z a t i o n a l g o r i t h m s 、c o a ) 才是艇决翊题熟途径，予是器秘掰l 疆饯化算法逐激归结到诗 算智能这概念之下【2 7 - 3 1 。以下我们简要回顾一下各种计算智能优化方法。 ， 3 。1 人工神经网络 在4 0 年代，人们对锗能问题开始感兴趣。人工神经网络( a r t i f i c i a l n e u r a l n e t w o r k ，a n n ) 最初的研究动视藏是模拟人脑豹神经活麓。戬m c c u i i o c h 为首静 批神经生物学家，采用了通过模拟神经活动来模拟人类大脑工作机理的路线。 黹勇一祭羽是由h e r b e r ts i m o n 和a l l e nn e w e l l 僵导豹逻辑路线。在7 0 - 8 0 年 代取得了很大成功。此后由于自身的弱点，a n n 研究蜉受到m a r v i nm i n s k y 羊玎 s e y m o u rp a p e r 等入酶怒蕊论点的沉重纷毒。赢翔8 0 肇代，警入工智能静基予 逻辑的路线遇到撤大困难，并转而求助乎新提出的p d p 模型之艏，a n n 才被重新 弓l 起注意灌o ”。 1 9 8 2 美国加州理工学院生物物理学家h o p f i e l d 提出了h n n 模型，标志着a n n 磷究高潮又一次到来。 眩弓l 入“计算能豢函数”概念，给密7 黼络稳迤毪判据。 墓 第一索绻沧 1 9 8 4 年h o p f i e l d 设计与研制了他所提出的a n n 模型的电路，并提出网络中每一 枣申经元郏可用遮放实现。所有神经元避接可用电予线路模拟。1 这一方案为a n n 工 程实现指明了方向，同时他也进行了应用研究。成功地解决了复杂度为n p ( n o t p o l y n o m i a l ) 的旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 3 4 - 4 | 1 ，开拓 了a n n 用于联想记忆和优化计算的新途径。从事并行分布处理的科学家，如 h i n t o n ，s e j n o w s k y 等，于1 9 8 5 年对h o p f i e l d 模型引入随机机制，提出了能获 得全局最优的b o l z m a n 机。此后得到应用的统计模拟退火( s t a t i s t i c a l s i m u l a t e da n n e a li n g ，s s a ) 继承tm o n t ec a r l o 法固有的收敛速度慢和计算复 杂性高的缺点，有签于此，近年来国内外专家、学者提出了用平均场璇论逼近法， 即平均场邋火( m e a nf i e l da n n e a l i n g ，m f a ) 1 4 2 - 4 5 1 算法硼练b o l z m a n n 机这一类 的a n n ，收到较好效果。所有这些算法大都怒建吏在统计物璞中系统自由能减少 的概念之上的。 细胞神经网络( c e l l u l a rn e u r a ln e t w o r k ，c n n ) 燕1 9 8 8 年由美国加翊l e o n 0 c h u a 教授提出的种阏格壅神经两络。它的局部驻遥往静常青翻予瘸当前静 v l s i 芯片实现。关于c n n 的数学毽论，硬件实现及应箱研究参觅文献m 6 - 4 8 】。 大量研究和应用结果表明，c n n 非常适合予解决一天类图像及强形处璞阉惩。 1 3 2 遗传算法 弱每代本6 0 年代韧，一些生物学家盯娥利用计算机对遗传系统进 亍模拟。 1 9 6 2 年，美嚣m i c h i g a n 大学h o l l a n d 教授及其学，土提出了遗传算法( g e n e t i c a l g o r i t h m ，g a ) “”豹基本思想：利用类似自然选择的方式设计计算机程序。 年代寒，形成了g a 豹模式理论及数学框架。i l o l l a n d 认为群体搜索方法登优 予当时普遍的单个个体到单个个体的方法。1 9 7 5 年，h o l l a n d 出版了 a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m ，弓l 越了大量学者对g a 的广泛研究必趣。 爨翦，g a 终为实用丽有效豹优化和搜索方法广泛应用予计算机科学、正程技术 秘社科顿域，已成为国际学术界跨学科研究热点之一“。5 ”。 1 3 。3 模拟退火 f 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 1 5 6 1 卷慧是1 9 5 3 年m e t r o p o l i s 等入 提出的。他们给出了闻体退火过程中物质内部状态变化的模撅算法。这一工俸禳 予统计物理范畴。s a 是一种菲常简单丽置裔效的通用豫梳优仡方法箨7 l 。不仅在 求解离散的组合优化问题上肖广泛的应糯前景。而聋同样胃应弱予求解连续多变 量最优化问题。它将组合优化问题与统计力学中热平衡渖磁类院，弹辟了求解缀 含优化问题的新途径。该算法实质上是对多极德菲凸函数，逶j 建设置溢痍参蠢， 并按正眈于溢度的概率接皎眈现行解较羞的解，滋虢宙局部极俊。该温度参量漆 警 高温向低温下降的过程中，整个进程在状态空间由随机搜索向确定性搜索转化。 从而使整个进程接收较差解的可能性越来越小，直至最后收敛到最优解。s a 收 敛速度慢，但它的各种改进以及与其它方法的结合得到了大量广泛而深入的研究 5 7 - 6 1 】。由s a 所带来的随机优化思想已渗透到了几乎各种新的优化技术中了。 1 3 4 蚁群算法 蚁群算法( a n t c o l o n ya l g o r i t h m ，a c a ) 阻j 是近年来发展迅速的一种仿 生算法。1 9 9 1 年d o r i g o 和g a n b a r d e l l o u 基于蚂蚁仿生算法体系发展而成，并应 用于求解t s p 问题，获得了较遗传算法、模拟退火及进化规划更优的结果。该 算法是模拟蚁群通过协同学习高效寻找食源的生物行为的随机搜索算法。它区别 于g a 、s a 等算法的最大特点之一是将已搜索空问的历史经验和优秀可行解问 的相互影响巧妙而分布式地存储在解空间的各独立分量中，不同可行解信息被整 合后反映在同一条边权信息中，具有很高的空间存储效率和高效的蚁群信息交换 机制。这些特点表明它是一种很有前途的优化方法。但对它的研究才刚刚起步， 其成果 6 3 - 6 6 】还远远不及g a 、s a 、a n n 等那么丰富。 1 3 5 禁忌搜索算法 禁忌搜索算法( t a b us e a r c ha l g o r i t h m ，t s ) 1 6 “矾j 最早是由g l o v e r 于1 9 8 9 年提出的，它是