（计算机应用技术专业论文）面向微处理器系统结构的布图规划算法研究.pdf

武汉理工大学硕- 上学位论文 捅芰 集成电路技术的发展已经进入了超深亚微米工艺的时代，微处理器系统结 构也随之面临着巨大的挑战。由于系统结构的设计涉及多方面的设计因素，因 此其设计问题的解空间随着系统的设计复杂度而急剧增加。作为布图设计的最 初阶段，布图规划和模块布局的质量对于芯片的性能有着显著的影响。高效的 布图规划和布局算法对布图设计的许多方面都是十分重要的。本文针对微处理 器的布图规划优化问题，以优化系统性能和片上温度为主要目标，提出了完整 的设计流程，取得了以下成果： 针对芯片温度这一重要因素，通过阅读、追踪大量文献，深入了解、研究 当前国际国内的最新发展成果，对集成电路设计中热问题研究现状进行了 综述，并结合实际对现代优化算法有了较深的领悟。 在h o t s p o t 的基础上，提出了一个精简的互连时延周期估计模型，并结合 互连时延周期对性能的影响，提出了同时优化性能和热效应的布局算法， 得到的布局结构更加合理，芯片最高温度有明显的降低，系统性能得到了 进一步改善。 针对多目标优化问题中各个分目标间的矛盾性，根据互连时延周期与互连 时延的差异，提出了三种能进一步降低芯片最高温度的智能策略，并在此 基础上提出了一个二阶段优化的布局算法框架，与第一阶段布局结果比 较，最高温度能再降低4o c 以上，而系统性能没有受到影响。 本文的研究将布图规划算法应用到微处理器系统设计中，为微处理器体系 结构设计提供了物理设计验证工具以及设计指导，在布图规划算法，布图规划 设计以及面向微处理器性能优化的布图规划设计等方面都取得了一定的成果， 为面向微处理器系统结构的物理设计开辟了崭新的研究领域。由于物理设计和 微处理器体系结构设计内容广泛，优化问题多样性，还有很多值得研究和探讨 的课题，能够结合集成电路工艺发展推动整个微处理器设计的发展。 关键词：布图规划，微处理器，热效应，性能 武汉理上大学硕i 学位论文 a b s t r a c t w i t hf a b r i c a t i o nt e c h n o l o g ye n t e r i n gd e e ps u b m i c r o ne r a ，m i c r o p r o c e s s o rd e s i g n s i nc u r r e n ts e m i c o n d u c t o rt e c h n o l o g i e sa r ea l r e a d yi n t e r c o n n e c t - l i m i t e d ，a n di n t e r c o n - n e c tl a t e n c ya n dp o w e rc o n s u m p t i o nh a v eb e e np r e d i c t e dt oh a v eal a r g e ri m p a c ti n f u t u r et e c h n o l o g i e s w i t ht h ed e s i g no ft h es y s t e mi n v o l v e dm a n yc o n s t r a i n t s ，t h es p a c e o ft h ed e s i g na l ei n c r e a s e dd r a m a t i c a l l y a st h ei n i t i a ls t a g eo fl a y o u t ，f l o o r p l a n n i n gh a s am a r k e di m p a c tw i t ht h ec h i p sp e r f o r m a n c e e f f i c i e n tf l o o r p l a n n i n ga l g o r i t h mi sv e r y i m p o r t a n t i nt h i st h e s i s ，i tp r e s e n t sm u l t i o b j e c t i v em i c r o a r c h i t e c t u r e l e v e lf l o o r p l a n n i n g a l g o r i t h mf o rd e s i g n i n gh i g h - p e r f o r m a n c e ，h i g h r e l i a b i l i t ym i c r o p r o c e s s o r s t h ec o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： f o rt h ef a c t o ro fc h i p st e m p e r a t u r e ，t h r o u g hr e a d i n g ，t r a c k i n gl o t so fn e wp a p e r s ， i th a si n d e p t hu n d e r s t o o dt h el a t e s td e v e l o p m e n to ft h et h e r m a li nt h ed e s i g no f i n t e g r a t e dc i r c u i t s ，a l s oh a v ek n o w n s o m eo p t i m i z a t i o na l g o r i t h m b a s e do nh o t s p o t i th a sp r o p o s e das t r e a m l i n e di n t e r c o n n e c td e l a ym o d e l w i t h t h ei m p a c to ft h ed e l a yc y c l e ，w ea l s op r e s e n t e dm u l t i o b j e c t i v em i c r o a r c h i t e c t u r e l e v e lf l o o r p l a n n i n ga l g o r i t h mf o rd e s i g n i n gh i g h p e r f o r m a n c e 。h i 【g h r e l i a b i l i t y m i c r o p r o c e s s o r s i ts i m u l t a n e o u s l yc o n s i d e r e db o t hp e r f o r m a n c ea n dt e m p e r a - t u r eo b j e c t i v e ss u c ht h a to u ra u t o m a t e df l o o r p l a n n e rc a np r o v i d eab a l a n c e do r g o a l d i r e c t e dp r o c e s s o ro r g a n i z a t i o nt h a ta c h i e v e sb o t ho p t i m i z e do b j e c t i v e s i nt h i st h e s i s ，i tt r i e st oh a n d l et h es m o o t ho p t i m i z a t i o no ft h ec o n f l i c t i n go b j e c - t i v e so fp e r f o r m a n c ea n dt h e r m a le f f e c t s i tp r e s e n t saf l o o r p l a n n i n go p t i m i z e r t h a tc o n s i s t so ft w os t e p s u n l i k et h ep r e v i o u sw o r k s w h i c hi n t e g r a t i n gt h et w o o b j e c t i v e ss t r a i g h t f o r w a r d ，w ea n a l y s i st h ep i p e l i n i n gd e s i g ni nm i c o a r c h i t e c t u r a l d e s i g n sa n dt a k ea d v a n t a g eo ft h es l a c k sa l o n ge a c hp a t hs ot h a tt h ef l o o r p l a n n e r c a r lb eg u i d e dt oo p t i m i z et h et h e r m a le f f e c tw i t h o u td e g r a d i n gt h ep e r f o r m a n c e t o om u c h b yu s i n gt w o - s t a g eo p t i m i z a t i o n ，w ec a ne f f e c t i v e l yr e d u c et h ep e a l 【 t e m p e r a t u r ew h i l em a i n t a i n i n gh i g hp e r f o r m a n c e i nt h i st h e s i s ，i ta p p l i e st h ef l o o r p l a n n i n ga l g o r i t h mi nt h ed e s i g no fm i c r o p r o c e s - s o r s y s t e m i tp r o v i d e da nv e r i f i c a t i o nt o o l sf o rp h y s i c a ld e s i g na n dh a sa c h i e v e dc e r t a i n 武汉理工大学硕上学位论文 r e s u l t sf o rt h ef l o o r p l a n n i n go ft h em i c r o p r o c e s s o r sp e r f o r m a n c eo p t i m i z a t i o n i ta l s o h a so p e n e du pan e wf i e l do fs t u d y w i t ht h ew i d er a n g eo fp h y s i c a ld e s i g na n da r c h i t e c - t u r em i c r o p r o c e s s o rd e s i g n ，t h e r ea l em a n ys u b j e c t sn e e d e dt ob er e s e a r c h e d w i t ht h e d e v e l o p m e n to fi n t e g r a t e dc i r c u i tt e c h n o l o g yd e s i g n e d , i tc a l lp r o m o t et h ed e v e l o p m e n t o ft h em i c r o p r o c e s s o r k e yw o r d s ： f l o o r p l a n n i n g ，m i c r o a r c h i t e c t u r e ，t h e r m a l ，p e r f o r m a n c e i i 武汉理工大学硕上学位论文 表格 1 1 2 0 0 5 年国际半导体技术蓝图报告1 t r sr e p o r t 中的预测数据 2 2 1 模拟退火算法流程1 3 2 2 已有的一些布图表示方法1 7 3 1 电流与热的等价对比2 3 3 2 不同温度、电压的功率比较2 8 4 1 近三十年微处理器设计发展概括3 0 4 2s p e cc p u2 0 0 0 标准测试用例3 4 5 1芯片制造工艺参数4 2 5 2 不同目标函数下的实验结果4 8 5 3 a l p h a 2 1 3 6 4 微处理器芯片各功能模块的信息4 9 5 4 各功能模块之间的互连信息4 9 v 武汉理工大学硕士学位论文 插图 1 1芯片的规模和设计能力的对比。 3 1 2 自顶向下设计方法中电子系统设计的阶段 4 1 3 高性能处理器的电源电压、电流和功率的变化趋势 6 1 4 芯片功耗密度的发展趋势 6 1 5门延时和互连线延时的发展比较7 2 1 ( a ) 二划分结构( b ) 非二划分结构( n o n s l i c i n g ) 1 5 3 1 摩尔定律2 0 3 2 温度和功耗的关系2 l 3 3 热阻模型。2 3 3 4 增量式的高层次综合算法2 4 3 5基于网格的热模型2 6 4 1超标量处理器的功能部件3 l 4 2 不考虑物理布图情况下的目标周期与实际物理设计完成后不考虑 互连线上流水线的实际周期比较3 5 4 3 不考虑互连线流水线设计的示例3 5 4 4 i p c 灵敏度模型示意：随着周期数增加i p c 的变化3 7 4 5 关键路径上的周期数：t o t a ll a t e n c y = b l o c kl a t e n c y + w i r el a t e n c y 3 8 5 1 热r c 模型4 l 5 2 不同互连线时延周期的增加对系统性能的不同影响4 3 5 3 二次布局设计流程4 5 5 4 智能策略示意图之一4 6 5 5 智能策略示意图之二4 6 5 6 不考虑热效应( 上) 和考虑热效应( 下) 的布图热分布5 0 5 7 优化改善后的布图结果：5 1 5 8 采用二次布局优化得出的周期和温度的振荡图比较( 上周期，下 温度)5 2 v 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 关于论文使用授权的说明 日期2 竺墨：茎：兰! 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：导师签名：缓叠日期丝鲨：互：p 武汉理上大学硕士学位论文 1 1 工业背景和课题意义 第一章引言 信息技术革命使人类的生活发生着日新月异的变化，微处理器也得到了迅 速的发展，尤其近几年随着半导体工艺技术的进一步细微化，超大规模集成电 路的发展进一步推动了微处理器性能的提高。而芯片的设计能力一般总是落后 于工艺能力，尤其在深亚微米工艺下由于互连线效应的影响，传统的设计流程 受到了很大的冲击，物理设计在高层次设计中的应用已经成为保证设计流程收 敛的重要手段。 1 1 1 集成电路迅猛的发展速度 1 9 5 8 年，n 成功开发出全球第一个i c ( i n t e g r a t e dc i r c u i t ) ，意味着晶体管时 代的结束，i c 时代的正式开始，给电子工业尤其是计算机业带来了巨大变革， 它使个人计算机的发明成为可能。在高速发展的现代科学技术中，作为信息产 业基础的集成电路i c 技术在经济中的地位越来越重要。目前，世界国民生产总 值增值部分的6 5 和i c 技术相关。i n t e l 公司的g o r d o nm o o r e 博士提出了著名 的摩尔定律，即所谓每1 8 个月，相同面积大小的芯片内，晶体管数量会增长一 倍的规则。几十年来，这一规律正是i c 产品集成度不断提升的最佳写照。目 前，有专家学者认为i c 产业的发展已经进入了后摩尔时代。2 0 0 5 年，美国、 欧洲、亚洲等地区的半导体协会联合撰写了该年度的国际半导体技术蓝图报告 ( i n t e r n a t i o n a lt e c h n o l o g yr o a d m a pf o rs e m i c o n d u c t o r $ ，1 t r s 2 0 0 5 ) 0 1 ，给出了 从2 0 0 5 年到2 0 2 0 年的集成电路发展趋势，预计集成电路仍将保持特征尺寸每3 年缩小3 0 的高速度发展。表1 1 列出了相关预测数据。2 0 0 7 年工艺特征尺寸 进入6 5 n m ，动态存储器芯片( d r a m ) 容量可达1 6 g 字节，高性能微处理器 ( m p u ) 可包含1 0 亿个晶体管，时钟频率达9 g 赫兹。综合1 t r s 的报告可以 看出，集成电路的设计规模正广泛地由超大规模集成( v l s i ) 、甚大规模集成 ( u l s i ) 向g 大规模集成( g i g a s c a l ei n t e g r a t e dc i r c u i t s ，g s d 的方向发展，制 造工艺已从小于0 5 微米的深亚微米( d e e p s u b m i c r o n ，d s m ) 工艺进入到小于 0 2 5 微米的超深亚微米( v e r y d e e p s u b m i c r o n ，v d s m ) 工艺阶段，预计2 0 0 9 年左右可以进入o 0 5 微米以下的纳米级工艺阶段。 武汉珲工大学硕上学位论文 更有意思的是，历年i t r s 给出的预测几乎都被早早的打破。比如2 0 0 1 年，当时预测2 0 0 4 年工艺特征尺寸进入9 0 n m ，高性能微处理器( m p u ) 时钟 频率可达4 g 赫兹。但是在2 0 0 2 年，芯片制造商i n t e l 公司就已经成功利用9 0 纳米制造工艺开发出新一代芯片产品p r e s c o t t ，该芯片频率就达到了4 g h z 。 表1 i2 0 0 5 年国际半导体技术蓝图报告i t r sr e p o r t 中的预测数据 由此我们也可以看出，集成电路制造业的发展，就是一个制造工艺不断提 高、特征尺寸迅速减小、芯片集成度不断增加、工作频率不断增大的过程。集 成电路技术正迅速向着更高集成度、更高速度、更高性能和更高可靠性的方向 发展。 1 1 2 课题意义 与飞速增长的集成电路产业相比。相关的集成电路设计能力却远远跟不上 发展的脚步。基本与摩尔定律一致的电路复杂性的发展以每年5 8 的速度在增 长，近1 0 年增长了近1 0 0 倍，但是相应的设计能力每年的长幅只有2 1 ，大约 l o 年增加了7 倍，正如图1 1 所示f 4 】，图中左边的纵坐标是晶体管集成数，右边 2 武汉理工大学硕士学位论文 是设计能力( 人月) ，下边横轴是年代。从图中可以直观地看出，设计能力 远远跟不上集成电路的发展速度，而且相差越来越远。 一l o , o o o ，o o o 体1 ，o o o ，o o o 管l o o o o o 数 ( k ) l o , o o o 1 o o o 芯 片 1 0 0 1 0 图1 1 芯片的规模和设计能力的对比 设 计 能 力 1 人 月 这种设计能力的一个集中体现就是计算机辅助的电子设计自动化( e d a ) 的设计方法和辅助设计的工具。在以往小规模的设计中，人工可以较多的参 与，在当前的深亚微米以及纳米阶段，设计的复杂度和质量要求都很高，人工 的参与度也逐渐被迫地减少，对自动设计系统的依赖也大大增加。同时，集成 电路设计的布局设计也面临着集成规模和电路性能两方面的巨大的挑战，所 以，为了集成电路产业继续高速的发展，改善产业发展需求和设计能力之间的 矛盾状况，必须加大电子设计自动化e d a 技术的研究，加大高性能布局技术的 研究。这也是本课题的意义所在。 1 2v l s i 设计流程及布图模式 因设计目标及设计者的不同，超大规模集成电路系统的设计有很多种方 法，很难有一种统一的方法适用所有的情况。图1 2 给出了典型的自项向下设 计方法 3 1 的主要阶段，并给出了不同阶段用到的不同的设计表示，对不同的设 计者和设计目标而言，各阶段的划分会有所不同。 布图设计过程包括划分( 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 ) 、布线( r o u t i n g ，包括总体布线，详细布线) 、压缩( c o m p a c t i o n ) 等。布局 的任务是要确定模块在芯片上的精确位置，其目标是在保证线网布通的前提下 使芯片面积尽可能的小。布线阶段的首要目标是百分之百的完成模块间互连， 3 武汉理工大学硕士学位论文 其次是在完成布线的前提下进一步优化布局结果。 需求上一级 i 系统描述 厂 设计规范l ，l i 功能设计 厂 行为表示i r _ 土_ 一 j 逻辑设计 。厂 结构表示l 广_ l 一 l 电路设计 厂 结构表示i 土 i 物理设计 厂 物理表示i 芯片制造 功能模拟 逻辑模拟 电路分析 提取和 验证 - _ _ - _ _ _ _ _ 一 拒 绝 下一级 下一级 上一级 甲 布图规划和布局 图1 2自顶向下设计方法中电子系统设计的阶段 在超大规模集成电路系统设计过程中会用到不同类型的设计表示，这些设 计表示大致可分为三类：行为表示，结构表示和物理表示。行为表示描述电路 的功能，如对系统的过程化的描述，布尔表达式，一些硬件描述语言等，其不 包含任何实现细节；结构表示描述电路的单元组成，部件及其间的互连等，如 逻辑门的网表；物理表示包含了制造和掩膜物理系统的所有信息，如物理布 图。 如图1 2 所示，自顶向下的设计方法主要包含的阶段有：系统设计( s y s t e m s p e c i f i c a t i o n ) 、功能设计( f u n c t i o n a ld e s i g n ) 、逻辑设计( l o g i cd e s i g n ) 、 电路设计( c i r c u i td e s i g n ) 和物理设计( p h y s i c a ld e s i g n ) 。各个阶段又可分为 综合、分析和验证。综合基于上一设计阶段的设计表示，推导出新的设计阶段 的设计表示，在较低级的阶段( 电路设计，物理设计) ，综合的自动化程度较 高，在高级的阶段，综合的自动化还有相当的研究工作要做；对超大规模集成 电路来说，分析的功能在于评估芯片的尺寸、系统性能、功耗等是否满足需 要；验证的功能在于证明当前综合的系统设计表示是否等价于另一种设计表 示，典型的验证如比较某电路图及从该电路图综合的物理布图。 4 武汉理工大学硕- 上学位论文 根据布局布线位置和布局模块的限制，布图设计可分如下几种模式【3 】： 积木块模式( b b l ) ，标准单元模式( s t a n d a r dc e l l ) ，门阵列模式( g a t e a r r a y ) 和门海模式( s e a - o f - g a t e s ) 等。 b b l 模式又称宏单元模式( m a c r oc e l l ) ，是设计中最灵活的一种设计方法。 在这种布图模式中，单元或模块可以有任意的形状和尺寸，可以安排在芯片的 任意位置上而且没有固定的布线区域。显然，这种布图模式接近人工的设计方 法，因此可望得到比门阵列和标准单元模式更高的布图密度。本文所研究的布 图规划算法主要针对b b l 模式。 1 3 布局面临的挑战 设计能力和集成电路发展的极大不匹配，大大地阻碍了集成电路的发展， 而且，随着深亚微米和纳米阶段的到来，设计能力和实际的需求相差有越来越 远之势。产业需求和设计能力之间的矛盾主要体现在集成规模和电路性能两个 方面。具体包括面向集成规模的芯片功耗、散热、成品率( 良品率) 、设计周 期等问题；以及面向电路性能的时延、时钟频率、可靠性等问题。 1 3 1 面向集成规模的问题 在如今的集成规模下，一个芯片通常要集成数目成千万上亿甚至十亿的晶 体管，而且要求集成电路设计者能够一次处理含有一千万n - 千万单元的功能 电路。鉴于此，目前的设计速度必须要提高二倍以上，设计质量还要保持甚至 提高。，否则这样的设计很难满足产业的需要，这就要求设计者提高设计能力， 必须在可接受的时间内处理如此大的问题规模。首先，从设计时间来看，现在 的设计者一般可接受的时间是四周左右，而这其中大部分时间( 大约一半以 上) 又被测试和验证占用了，留给传统的物理设计的时间又是很少的一部分。 而传统的这些物理设计的问题，比如布局、布图优化问题大多都是n p 难题， 要高质量快速的完成设计就需要很高的算法。其次，从单个的设计目标来看， 诸如功耗、散热、成品率等，伴随着特征尺寸的减小和集成规模的增大，设计 者遇到的都是一个个极其重要且尚待很好解决的问题。为了说明这种发展趋 势，图1 3 给出了一个以高性能处理器为例，电路电压、电流和功耗方面的发 展趋势图【4 1 。 从图1 3 中可以看出，即使电源电压不断的降低，而电流的增长速度仍然 很快，预测在2 0 1 6 年将达到惊人的7 2 0 安培，而且功耗也是一直在增加。图 5 武汉理工大学硕i 学位论文 图1 3高性能处理器的电源电压、电流和功率的变化趋势 1 4 给出了一个关于芯片功耗密度的发展趋势【4 1 ，从图中可以看出，按功耗密度 来衡量，以i n t e l 的芯片为例，从3 8 6 、4 8 6 一直到奔腾2 代、3 代、4 代以及以 上，在纳米级以后，芯片将很快变得像一个核反应堆( p e n t i u m 4p r e s c o t t 就已经 达到了) ，再后来就和火箭的喷火口一样，甚至最后会拥有像太阳表面那样的 能量密度。 1 咖 y p r o t o n u l - u _ 蔓- 叠- - i i u ,- 簟峨工艺 图1 4 芯片功耗密度的发展趋势 也正是因为这个原因，低功耗和散热问题也越来越显得重要，甚至成为关 6 电源由瘫a) 功率 锄 伯 ， 武汉理工大学硕上学位论文 键问题。如果这两个问题处理不好将不仅直接导致一个失败设计而且会使集成 电路产业的规模很难进一步发展。 除此之外，如图1 5 所示，在深亚微米阶段以前，晶体管内部的延时( 门 延时) 在电路延时中是占主导地位的，但是在深亚微米阶段以后就是互连线延 时占主导地位了。 为此，业界采用低电阻率的铜作为互连线的材料，而且为了降低互连线上 的电容而降低时延，采用掺杂( 比如掺杂氟) 的方法降低二氧化硅的绝缘系数 从3 9 到3 5 左右。这些方法都是对以往设计规则的改变，大大增加了成品率和 可制造性问题解决的难度。而且，由于新工艺下的高掺杂度和新材料的应用， 使制造过程中更加容易发生工艺变化，这些不定的因素都是提高成品率和可制 造性的障碍。 r 仂 _ _ x 日 a ) o g e n e r a t i o n 【p m l 图1 5门延时和互连线延时的发展比较 1 3 2 面向电路性能的问题 电路总体的集成规模提高很快，同时性能要求也在不断增加。根据2 0 0 5 年的国际半导体协会撰写的国际半导体技术蓝图报告( i n t e r n a t i o n a lt e c h n o l o g y r o a d m a pf o rs e m i c o n d u c t o r s ，i t r s 2 0 0 5 ) 1 1 ，如果照目前的发展速度，到2 0 1 6 年，工艺特征尺寸缩小到2 2 n m ，存储器芯片容量可达6 4 g 字节，高性能微处 理器可含1 6 3 亿个晶体管，时钟频率达2 8 g 赫兹! 当工艺本身趋于物理极限， 7 武汉理工大学硕士学位论文 再加上工业生产的基于成本、可制造性等要求，电路设计者要面对传统但是更 加严峻的时延、时钟频率、可靠性等等棘手的问题，这些问题的解决需要比往 常更加高的质量要求。 时延( t i m i n g ) 是面向电路性能设计中的一个重要衡量手段。为了达到理想 的电路速度，在具体的设计中对时延的控制有很高的要求。正如图1 5 所示， 互连线延时是占主导地位的，如何降低互连线延时就是提高电路速度的一个有 效方法和目标。与之统一的，在具体的大规模集成电路布局、布图中，设计者 通常采用总线长做为优化目标，通过相应的优化来达到提高电路的性能的目 的。 除此之外，由于当前集成电路的高集成度和高精密度，时钟设计和供电网 络设计也成为当前关系集成电路性能的新热点和难点。相关的优化问题包括除 了时钟周期优化、时钟布线树优化以及电源地线规划这些比较传统的优化课题 外，还有随着当前高精密集成而来的信号噪声、低功耗、供电噪声和电压降效 应等优化需求。这些新的问题都是威胁整个电路的可靠性、安全性的重要因 素，也是提高电路性能必须要解决的问题。 除了这里提到的新热点问题，在面向电路性能方面的问题多是传统的问 题，比如反映在布局中的线长、时延、可布性等设计目标，由于比较常见和经 典，这里就不再详细叙述了。 1 4 本文的主要工作和组织结构 正如前面章节所述，集成电路技术的发展已经进入了超深亚微米工艺的时 代，微处理器系统结构也随之面临着巨大的挑战。由于系统结构的设计涉及多 方面的设计因素，因此其设计问题解空间随着系统的设计复杂度而急剧增加。 作为布图设计的最初阶段，布图规划和模块布局的质量对于芯片的性能有着显 著的影响。高效的布图规划和布局算法对布图设计的许多方面都是十分重要 的。本文的选题正是针对这一有意义的课题，探索超深亚微米工艺条件下v l s i 布图规划的一些新方法，尤其是热约束和互连性能优化方法。本文的算法以波 兰表达式表示( p o l i s he x p r e s s ) 1 5 1 作为算法平台，利用模拟退火优化算法，针对 深亚微米工艺下布图规划所面临的新问题提出了相应的应用算法，同时各个算 法在整个布图规划优化过程中协调作用，可以系统地解决热约束和互连优化的 布图规划问题。 本文针对微处理器的布图规划优化问题，以优化系统性能和片上温度为主 8 武汉理工大学硕- 上学位论文 要目标，提出了完整的设计流程，取得了以下成果： 针对芯片温度这一重要因素，通过阅读、追踪大量文献，深入了解、研究 当前国际国内的最新发展成果，对集成电路设计中热问题研究现状进行了 综述，并结合实际对现代优化算法有了较深的领悟。 在h o t s p o t t 2 l 的基础上，提出了一个精简的互连时延周期估计模型，并结 合互连时延周期对性能的影响，提出了同时优化性能和热效应的布局算 法，得到的布局结构更加合理，芯片最高温度有明显的降低，系统性能得 到了进一步改善。 针对多目标优化问题中各个分目标间的矛盾性，根据互连时延周期与互连 时延的差异，提出了三种能进一步降低芯片最高温度的智能策略，并在此 基础上提出了一个二阶段优化的布局算法框架，与第一阶段布局结果比 较，最高温度能再降低4 0 c 以上，而系统性能没有受到影响。 本文的主要工作来源于国家自然科学基金科研项目的部分内容，得到了维 吉尼亚大学c a d 实验室【2 1 提供的开源软件代码的支持，并与清华大学电子设 计自动化实验室合作研究开发，该课题与清华大学计算机系的洪先龙教授以及 马昱春老师进行了广泛的合作和交流。与目前采用的微处理器设计相比可以从 时延，吞吐量，面积以及片上温度等多方面进行优化，帮助设计者实现多约 束、多目标的优化设计。本文在布图规划算法，面向微处理器性能优化的布图 规划设计等方面都取得了一定的成果，为面向微处理器系统结构的物理设计开 辟了崭新的研究领域。 本文剩余部分组织如下：第二章简要介绍布图设计的一些背景知识以及面 向为处理器的布局算法的研究现状；在第三章将对集成电路设计中热问题研究 进展进行了综述；第四章将介绍微处理器的性能设计；第五章研究和设计了面 向微处理器的布图规划算法框架；第六章给出本文的结论及进一步的工作。 9 武汉理工大学硕上学位论文 第二章集成电路布图与布局研究 本章对布图规划问题和典型算法进行介绍，首先对布图规划给出了问题的 描述。在第二节中介绍布局中的常用的随机优化算法一模拟退火算法，基于布 图规划结构的划分在第三节中介绍各种不同的布图结构表示。最后对面向微处 理器系统结构的热驱动和性能驱动的布图规划算法发展现状进行综述。 2 1 布图规划和布局问题的描述 布局( p l a c e m e n t ) 是v l s i 物理设计中的最重要的步骤之一，布局质量的好 坏将直接影响芯片的面积和电性能。简单来说布图规划是对一些可变尺寸的 模块的布局，可变尺寸是指模块面积固定，而长和宽是可变的。随着工艺的发 展，布图规划问题已经从单纯的面积和线长优化发展成为多目标多约束的问 题。s r c 前沿问题报告对布图规划的问题进行归纳，指出当前设计工艺下的 布图规划问题是多目标组合优化问题。其优化目标是多样化的，可以是芯片面 积、线长和互连因素( 拥挤度、时延等) 等的组合目标，其输入包括： ( 1 ) 由模块或单元组成的集合b = _ 6 1 ，6 2 ) ，其中每个模块是有固定长 和宽的矩形模块，或是面积固定而长和宽可以变动的矩形软模块。每一个布局 的模块阮均含有引线端的集合纯= 西，疵) ，其中每个引线端硝都位于模块 b i 的边界上，每个软模块的期望宽高比的上界和下界分别为刷和砰，布图规 划算法确定的模块玩的宽度w i 和高度h f 必须满足r w d h i 研； ( 2 ) 表示模块之间连接关系的网表集合n = 1 ，2 】，其中每个线网 越是一个引线端的集合，位于该集合中的引线端相互之间具有连接关系；在时 延约束驱动的布图规划布局方法中需要给出线网上的时延约束。 其输出包括： ( 1 ) 一个合理的布局结果：确定了所有模块的方向、位置和形状，满足模 、块之间相互不重叠及相关约束的条件，优化目标最小化： ( 2 ) 在电路模块间的空白区合理的插入缓冲器，使得各线网满足时延约 束。 设模块集合b = 6 1 ，6 2 ，6 n ) 中每个模块b i 的高度和宽度为( h i ，w i ) ，则 模块的宽高比定义为w t h i 。布图结果p = ( 如，y i ) ，i = 1 ，扎) ，其中( z i ，y i ) 1 0 武汉理工大学硕上学位论文 是模块5 4 的右上角的坐标。布图规划问题可以形式化为最小化问题： m i n i m i z e ：o b j e c t i v e s s u b j e c t t o ： ( z i 一奶一嘶) v ( 戤一吻w d v ( v i 一协h i ) v ( 统一幼一如) ，v 玩，如b x i 0 ， v i 0 ，硝w , h t 磁，v 玩，b ( 2 1 ) ( 2 - 2 ) 其中式2 1 表示模块之间的无重叠约束，而式2 2 表示软模块变形约束。布 图规划问题是一类非常复杂的组合优化问题，一些被简化的问题都已经证明是 n p - 困难问题： ( 1 ) 若仅仅考虑模块的形状和面积而忽略模块间的互连，优化目标 ( o b j ) 定为面积的最小化，则问题就转化为平面上的填装( p a c k i n g ) 问题； ( 2 ) 若只考虑模块之间的连接关系，而不考虑它们的形状和大小，并假 设每个线网只连接两个单元，这时布局问题就变成一个典型的“二次分配 问 题。 无论平面填装问题还是二次分配问题都已经被证明是n p 一困难问题。 2 2v l s i 布局设计中的模拟退火算法 模拟退火算法是由k i r k p a t r i c k 1 8 l 提出来的。今天，它已经发展成为一种解 决组合优化问题的有效而又通用的算法。模拟退火算法通过将组合优化问题与 统计力学的热平衡问题相类比，开辟了求解组合优化问题的一条新途径。它是 一种随机搜索算法，所以它具有以往确定性算法所不可比拟的优越性。通过模 拟退火过程，算法可望找到全局( 或近似) 最优解。 模拟退火算法的出发点是注意到了统计物理中固体物质的退火过程与组合 优化问题之间的相似性。固体退火的过程是先将固体加热至溶化，再徐徐冷却 使之凝固成规整晶体的热力学过程。加热固体时，固体粒子的热运动不断增 强，随着温度的升高，粒子与其平衡位置的偏差越来越大。当温度升至溶解温 度后，固体原有的规则被彻底破坏，固体溶解为液体。冷却时，液体粒子的热 运动渐渐减弱，随着温度的徐徐降低，粒子运动渐趋有序，当温度降至结晶温 度时，液体凝固成固体的晶态，这个过程称为退火。退火过程必须徐徐进行， 武汉理工大学硕- 上学位论文 这是为了使系统在每一温度下都达到平衡态，最终达到稳态，即系统的能量达 到最小。冷却时，若急剧降低温度，则会引起淬火效应，固体只能凝结为非均 匀的亚稳态，系统能量不能达到最小。 1 9 5 3 年，m e t r o p o l i s 提出了所谓“重要性采样法 即m e t r o p o l i s 准则来模 拟固体在恒定温度下达到热平衡的过程。某一状态i 的的能量为最，随机产生 一个微小的摄动而得到一个新的状态j ，其能量为e 。若e j 最，则考虑到热运动的影响，该新状态是否“重 要要依据固体处于该状态的几率来判断。固体处于状态t 和歹的几率的比值 等于r = e 印( 兰铲) ( 7 ，则歹作为重要状 态，否则舍去j 而仍以暮作为重要状态。从以上过程可以看出，高温下可以接 受与当前状态能差较大的新状态作为重要状态，而在低温下只能接受能差较小 的新状态作为重要状态。 文献【2 4 】首先将组合优化问题与决定最低能量的物理系统之间进行类比， 类似地引入了“温度 的概念，在每一温度上，系统模拟m e t r o p o l i s 过程直到 系统达到平衡。( 注意，在组合优化中b o l t z m a n n 常数合并到温度中，统称为 温度。它表示优化过程中的一个参数) 。 对于布局问题而言，模拟退火算法已经发展成为一种非常成功的算法，它 主要用来进行布局的迭代改善。给定一个布局的构形( p l a c e m e n tc o n f i g u r a t i o n ) ， 在它的邻域内的一个可行解可以通过移动一个单元或交换两个单元的位置而得 到。但人们往往会发现，虽然一个构形的代价函数均远远高于最优值，但没有 任何两个单元的对交换可以使代价函数降低。在这种情况下，算法就陷入了局 部极小之中。一般说来，许多组合优化问题的目标函数均是非凸函数，因此它 往往在达到某个局部优化解后就无法跳出“谷底 而达到更优的解。而s a 就 不同了，它可以接受比现行解较差的解，允许爬山( h i l l u p ) ，即允许向比现行解 恶化的方向运动。因此，它可能越过“小山 而进入另一个局部优化区域。通 过概率接受代价函数增加的解，可以减少搜索陷入局部极小解的可能性。 一般面向线长和面积优化的布图规划方法所采用的代价函数可以表示如 下： c o s t ( s ) = a r e a ( s ) + w l 木w i r e ( s ) + w 2 奉r ( s ) ( 2 3 ) 1 2 武汉理工大学硕士学位论文 公式2 3 中a r e a ( s ) 表示布图结果的面积，w i r e ( s ) 表示布图结果中的半周 长线长估计，通常人们用包含线网所有顶点的最小矩形的半周长( h a l f p e r i m e t e r ) 来估计线网长度。半周长的线网长度为： l = z 竹。o 二z m 讥+ 3 h 昭一3 f m 机 ( 2 4 ) 公式2 4 中r ( s ) 是宽长比惩罚项： r ( 8 ) = m a z ( 1 r a t i o w i d t h ( s ) l h e i g h t ( s ) ，i r a t i o h e i g h t ( s ) w i d t h ( s ) 1 ) ( 2 5 ) r a t i o 是期望的宽高比