（微电子学与固体电子学专业论文）soc布图规划与考虑热量的测试规划研究.pdf

摘要 摘要 当今系统级芯片( s o c ) 己成为热点，而且芯片规模以及复杂度不断提高，基 于口复用的设计方法已经成为必然趋势。对于这种层次化的设计流程，作为物 理设计第一阶段的布图规划将变的越来越重要。而且随着s o c 复杂度和规模的 不断增加，s o c 的测试变得越来越复杂，测试的费用也越来越高。基于上述原 因，本文主要研究s o c 的布图规划算法和考虑热量的测试规划算法。 在基于权重的布图规划算法中，本文提出在模拟退火过程中不是以均匀分布 的概率来选择当前进行移动的模块，而是权重大的模块选择概率较小，权重小的 模块选择概率较大。首先提出了模块权重的概念，并在此基础上提出基于权重的 布图规划算法，实验表明基于权重的布图算法取得了较好布图结果。 布图规划问题规模不断增大，使用模拟退火算法其求解时间过长，本文提出 快速布图算法。构造法可以快速的得到一个布图，但是结果并不是最优解。而线 性规划算法速度较快，最终结果也令人满意，却需要输入一个好的初始布图。综 合考虑后，本文结合两者算法，用快速的构造法来构造初始布图，并保证得到一 个较好的拓扑结构，再用线性规划对这个初始布图进行优化，从而得到最优解。 实验表明本算法能在较短的时间内得到较好的布图。 随着集成电路工艺发展，工作电压降低，电流密度和连线长度增大，电源网 络电压降的问题将越发突出。本文提出在布图规划过程中考虑电压降的优化，降 低最终布图的电压降以及尽量满足各模块的电压降容限，加快物理设计收敛。首 先提出在布图规划过程中优化电压降的目标函数，然后讨论模拟退火过程中的选 择策略，最后用线性规划进行软模块压缩。实验表明本算法取得一个较好的布图 同时，能有效地降低最终布图平均电压降和最大电压降。 考虑到测试过程的高发热对于芯片的不良影响，本文提出在对s o c 进行测 试规划时考虑避免热点和均匀地分布热量，从而提高芯片测试的成品率。文中将 热点问题以及热量均匀分布问题转化为模块之间距离问题，通过模块之间的距离 来决定它们是否可以同时测试。然后，用测试兼容图来描述各个测试之间的约束 关系，并通过测试兼容图中来提取并行测试集合。最后，通过b i n - p a c k i n g 算法 对并行测试集合进行测试规划。实验表明本算法能有效地降低测试过程中的平均 温度以及最高温度，并且只带来较小的测试时间增加。 关键字：系统级芯片：布图规划；测试规划；电压降；线性规划；装箱算法 a b s t r a c t a b s t r a c t i n t e g r a t e dc i r c u i th a se n t e r e dt h ee r ao fs o cr s y s t e m - o n c h i p ) w i t i ll a r g e r s c a l ea n dm o l ec o m p l e xf u n c t i o nt h a ne v e rb e f o r e ，d e s i g nm e t h o d o l o g yb a s e do ni p r e u s ei st h ei n e v i t a b l et r e n d a st os u c hh i e r a r c h i c a id e s i g nf l o w , f l o o r p l a n n i n ga st h e f i r s ts t a g eo fp h y s i c a ld e s i g ni sb e c o m i n gm o r ea n dm o r ei m p o r t a n t a sar e s u l to f t e c h n o l o g ya d v a n c e m e n ts o ct e s ti sb e c o m i n gm o r ec o m p l e xa n dt h ec o s to fi t i s b e c o m i n gm o r ee x p e n s i v e c o n s i d e r i n gt h e r e a s o n sm e n t i o n e dt h i sd i s s e r t a t i o n f o c u s e so nt h es o cf l o o r p l a n n i n ga n dt e s ts c h e d u l i n gw i t hh e a tc o n s i d e r a t i o n a b o u tt h ef l o o r p l a n n i n gb a s e do nw e i g h t ，t h ed i s s e r t a t i o np r o p o s e st h a tt h e d i s t r i b u t i o no fs e l e c t i n gp r o b a b i l i t yi sn o te v e n d u r i n gs i m u l a t i n ga n n e a l i n g p r o c e d u r e b u tt h ei a r g e r t h ew e i g h to fam o d u l ei st h es m a l l e rt h es e l e c t i n g p r o b a b i l i t yi s t h ed i s s e r t a t i o np r o p o s e st h ec o n c e p to fm o d u l ew e i g h ta n dt h e c o r r e s p o n d i n gf l o o r p l a n n i n ga l g o r i t h m 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 tt h i s a l g o r i t h mi m p r o v e st h eq u a l i t yo faf l o o r p l a nc o m p a r e dw i t ht h ef l o o r p l a n n i n g a l g o r i t h mw i t h o u tw e i g h t w i t ht h es i z eo ff l o o r p l a n n i n gp r o b l e mb e i n gl a r g e r , t h es o l v i n gt i m eo f s i m u l a t i n ga n n e a l i n g i st o ol o n g ，s ot h ed i s s e r t a t i o np r o p o s ef a s t f l o o r p l a n n i n g a l g o r i t h m f i r s tt h ec o n s t r u c t i n ga l g o r i t h mi su s e dt oo b t a i na l li n i t i a lf l o o r p l a nw i t h f e a s i b l et o p o l o g yq u i c k l y t h e nl i n e a rp r o g r a m m i n go p t i m i z e st h ei n i t i a lf l o o r p l a nt o g e t t h eb e s ts o l u t i o n e x p e r i m e n t a lr e s u l t ss h o wt h e a l g o r i t h mc a n o b t a i ng o o d f l o o r p l a nq u i c k l y w i t ht h ea d v a n c e 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 y , t h ei r d r o pp r o b l e mw i l l b em o r es e r i o u s t h e r e f o r ei r - d r o pc o n s t r a i n ti sc o n s i d e r e di nf l o o r p l a n n i n gs t a g et o l o w e rt h ei r d r o po ft h ef i n a lf l o o r p l a na n dq u i c k e nt h ed e s i g nc o n v e r g e n c e f i r s tt h e c o s tf u n c t i o no fi r - d r o pi sp r o p o s e da n dt h e nt h es e l e c t i o ns t r a t e g y f i n a l l yl i n e a r p r o g r a m m i n go p t i m i z e st h ef l o o r p l a nb ys o f tm o d u l ea d j u s t m e n t e x p e r i m e n t a lr e s u l t s s h o wt h ea l g o r i t h mg e t sg o o df l o o r p l a nw i t hl o w e rm a x i m u m i r d r o pa n da v e r a g e i r - d r o p c o n s i d e r i n gt h ei m p a c to fh i g hh e a td u r i n gc h i pt e s t ，t h ed i s s e r t a t i o np r o p o s et e s t s c h e d u l ew i t ha v o i d i n gh o t - s p o ta n dd i s t r i b u t i n gh e a te v e n l y i nt h ep r o p o s e d a l g o r i t h mt h em a n h a r a nd i s t a n c eb e t w e e nt w om o d u l e si su s e dt od e t e r m i n ew h e t h e r i tc a nb et e s t e ds i m u l t a n e o u s l y t h e nt h ec o n s t r a i n tr e l a t i o n s h i pa m o n gm o d u l e si s m o d e l e db yt e s tc o m p a t i b l eg r a p ha n dp a r a l l e lt e s ts e t si se x t r a c t e df r o mi t f i n a l l ya t e s ts c h e d u l ei so b t a i n e db yb i n - p a c k i n ga l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h e p r o p o s e da l g o r i t h mc a nl o w e rm a x i m u ma n da v e r a g et e m p e r a t u r ee f f i c i e n t l yw i t ha s i n a i lt e s tt i m ei n c r e a s e k e y w o r d s ：s o c ；f l o o r p l a n n i n g ；t e s ts c h e d u l i n g ；i r - d r o p ；l i n e a rp r o g r a m m i n g ； b i n p a c k i n g 2 第一章引言 1 1 集成电路的发展现状 第一章引言 表1 1 国际半导体发展路线图2 0 0 5 【i t r s 0 5 y e a r 2 0 0 62 0 0 82 0 1 02 0 1 32 0 1 62 0 1 82 0 2 0 t e c h n o l o g y 7 05 74 53 22 21 81 4 d e n s i t y ( # mt r a n c m 2 ) 2 1 93 4 85 5 2 1 1 0 42 2 0 93 5 0 6 5 5 6 5 v d d ( v ) 1 1110 90 8o 70 7 p o w e r ( w ) 1 8 01 9 81 9 81 9 81 9 81 9 81 9 8 f r e q u e n c y ( g h z ) 6 7 8 31 0 9 7 21 5 0 7 92 2 9 8 03 9 6 8 35 32 0 77 3 1 2 2 c h i ps i z e ( m m 2 ) 3 5 32 2 22 8 02 8 02 8 03 5 32 2 2 t o t a ii n t e r e o n n e c t1 2 1 21 7 1 22 2 2 23 1 2 5 4 5 4 5 5 5 5 57 1 4 3 l e n g t h ( m c m 2 ) 陆 拌w i r el e v e l sl l 1 51 2 1 61 2 - 1 61 3 1 71 3 1 71 4 l81 4 18 【注 c a l c u l a t e db ya s s u m i n gt h a to n l yo n eo f e v e r yt h r e em i n i m u mp i t c hw i r i n gb a c k sf o r m e t a l1a n df i v ei n t e r m e d i a t ew i r i n gl e v e l sa r ep o p u l a t e d 从集成电路首次发明到如今，短短四十多年的时间里，集成电路制造工艺迅 猛发展，市场和用户对i c 要求越来越高，促使集成电路发生了几个显著的变化。 首先，器件特征尺寸急剧缩小，根据国际半导体发展路线图2 0 0 5 版本预测( 表 1 1 ) ，特征尺寸将从2 0 0 6 年的7 0 r i m 缩小到2 0 2 0 年的1 4 n m ；其次，集成电路的 规模越来越来大，集成电路技术已经历了小规模集成( s s i ) ，中规模集成( m s i ) ， 大规模集成的发展阶段，目前已进入超大规模集成( v l s i ) ，甚大规模集成( u l s i ) 和吉规模集成( g s i ) 阶段，集成度已提高了8 9 个数量级，据预测到2 0 2 0 年 每平方厘米集成的晶体管个数将达到5 5 6 5 兆；再者，集成电路的工作频率将越 来越高，在2 0 0 6 年已经达到了6 7 8 3 g h z ，预计到2 0 2 0 年将增加1 0 倍多；再者， 连线长度和布线层数迅速增加；最后，器件的工作电压却越来越低。 集成电路已经进入了系统级芯片s o c ( s y t e m o n c h i p ) 时代，即单个芯片集 成各种各样的i p 核而实现一个系统的功能，基于i p 复用的设计不仅缩短了上市 时i 司( t i m e - t o - m a r k e t ) ，也提高了芯片的性能。而且随着芯片复杂程度的越来越高， 片上网络n o c ( n e t w o r k s 一0 n c h i p ) 的概念也被提出，n o c 致力于提高具有大量 i p 核的芯片其模块之间的通信效率，n o c 反映了集成电路朝着更大规模发展的 趋势。集成电路朝着高集成度，高性能和多样化的方向发展，一个芯片上可集成 高达几亿，甚至几十亿个晶体管，并且工作在上g h z 的频率，要完成如此大规 第一章引言 模和高复杂度的集成电路设计，离开计算机辅助设计技术( c a d ) 的支持将是 不可想象的，而且在未来c a d 技术将变得愈发重要。 1 2 集成电路发展而带来的新问题 集成电路的发展给计算机辅助设计领域带来新的问题，传统的e d a ( 电子设 计自动化) 将难于解决当今的新问题，新的工具迫切需要去适应集成电路的高速 发展。虽然e d a 工具近年来得到了快速的发展，但仍旧无法适应越来越复杂的 集成电路设计的需要。 首先，芯片内部连线的快速增加，使得在以前不是很重要的连线因素已经逐 渐成为了制约芯片性能以及芯片设计收敛的决定性因素，例如，全局连线的延时 超过器件本身的延时决定了芯片最高工作频率，连线的布通率成为决定设计收敛 的因素之一。其次，集成电路工作电压的降低，使得信号的抗干扰能力变差，例 如，一个较小电压降将可能使芯片逻辑上出问题，而且高工作频率和集成密度， 使信号更容易相互干扰，因此，信号完整性问题也变的越来越重要。最后，系统 级芯片( s o c ) 已经成为超大规模集成电路发展的趋势和未来集成电路的主流，但 随着其复杂度和规模的不断增加，其测试变得越来越复杂，测试的费用也越来越 高。s o c 不仅包括数字信号，还有模拟信号，同时精确地检测出模拟和数字两 种电路，并支持扫描链测试和嵌入式存储器测试，将是一件很困难的事 z o r i a n 9 8 】、【z o r i a n 0 0 】；与此同时测试工程师还必须面对缺少检测触点的现状， 对于s o c 不可能通过探针来对各个模块进行检测；此外，高达数百兆的系统时 钟频率以及各模块内和模块间错综复杂的时序关系也给测试带来了很多困难。 1 3 研究动机以及贡献 考虑到出现的新问题，本文主要研究如何在布图规划以及测试规划中考虑新 因素，从而加快设计收敛，缩短上市时间，并对芯片进行测试时，降低测试成本， 提高测试成功率。 1 3 1 布图规划研究 布图规划是物理设计的第一个阶段，在这个阶段，模块的尺寸以及相对位置 被确定，而且布图在整个物理设计中是非常重要的一环，因为集成电路的性能指 标，包括芯片面积，时延特性，布线的布通率，信号的可靠性等等，强烈地依赖 于布图设计过程。传统的布图规划一般只是优化面积或者线长【w o n 9 8 6 】，而当今 面积已不是主要优化的目标，而其他因素，例如，信号完整性，电压降，布通率 第一章引言 等已经成为主要因素。并且随着集成电路制造技术的不断发展，芯片的集成度越 来越高，芯片的规模越来越大，复杂性越来越高，层次化设计将成为必然趋势， 布图规划必将发挥出更大的作用。 本文在布图规划方面的主要贡献在于：首先，本文在 d o n 9 0 1 1 的基础上重新 定义了模块自由度的概念并给出模块权重的定义，然后提出基于模块权重及 b * - t r e e s 表示法的平面布图规划算法；其次，考虑到线性规划算法和构造算法各 自的优缺点，本文提出结合构造法和线性规划方法的快速布图算法，来解决软模 块布图问题；最后，本文提出考虑电压降的布图规划算法，在布图阶段便考虑电 压降的影响，从而降低最终芯片中的最大电压降以及平均电压降，并且尽量满足 各个模块的电压降容限，加快设计收敛。 1 3 2 考虑热点以及热量均匀分布的测试规划 测试规；e l j ( t e s t s c h e d u l e ) 是在测试资源有限的情况下，合理的安排各个模块 的测试时间，从而在满足一定约束条件的情况下，尽量减小测试时间，降低测试 成本。进入s o c 时代以后，测试变的越来越复杂，由于各个模块都被集成在一 个芯片里，那么对与各个模块的测试，不可能通过传统方法( 使用探针和示波器) 进行，也即是施加激励和观测响应都需要特殊的方式进行。对于s o c 中的某个 模块进行单独测试时，首先要将这个模块和其他电路进行屏蔽，也即为了在测试 过程中不受其他电路的影响，然后需要使用测试通道( t a m ) 将输入测试激励和输 出测试响应。 s o c 强大的功能带来了更大的功耗发热，而集成度的提高使得热量更集中， 这些都可能在芯片工作时产生热点( h o t s p o t ) ，热点的出现将使得芯片变得极不 稳定，甚至烧毁芯片。而在测试模式下由于更高的翻转频率使得s o c 的功率比 远大于正常工作模式的功率 z o r i 9 3 ，这使得芯片在测试时可能被烧毁或由于高 发热引起性能不稳定而通不过测试，进而降低了成品率。因此，在测试时更应该 去考虑功率与集成度带来的发热问题，为了保护测试模式下的s o c ，必须合理 安排各个i p 核的测试顺序，从而在测试时避免出现热点( h o t s p o t ) 的情况，并使 得热量能均匀地分布在s o c 上。但以前的关于s o c 测试的文章中 i y e n 0 2 a 1 、 【l y e n 0 2 b 】、 i y e n 0 2 c 、 i y e n 0 2 d 】、 c h o u 9 7 】很少涉及到在测试中如何避免 h o t s p o t 以及热量均摊的问题。 本文在测试规划方面的主要贡献在于：提出在对s o c 进行测试规划时考虑 避免h o t s p o t 以及热量均摊的问题。 第一章引言 1 4 论文组织 在下文中，本文依次涉及了如下论题： 第二章讨论了布图的表示方法，并且对序列对和b * - t r e e s 的表示方法进行了 实验，以比较两者的优劣。 第三章讨论了基于权重的平面布图规划算法，在模拟退火过程中并不是以均 匀分布的概率来选择当前进行移动的模块，而是权重大的模块选择概率较小，权 重小的模块选择概率较大。模块的权重与模块的面积以及模块长边的长度成正 比，本章工作主要的启发点是，在实际情况中面积较大以及长边较长的模块移动 的空间较小，在布图中更容易确定其位置。 第四章讨论了结合构造法和线性规划的快速布图算法，用构造法来构造初始 布图，然后再用线性规划方法对初始布图进行软模块调整。主要考虑到模拟退火 方法达到全局最优需要较长的运行时间。构造法可以快速的得到一个布图，但是 结果并不是最优解。线性规划算法速度较快，最终结果也令人满意，但是需要输 入一个好的初始布图。综合考虑后，本章提出构造法来构造初始布图，并保证得 到一个较好的拓扑结构，再用线性规划对这个初始布图进行求解。 第五章为考虑电压降的布图规划算法，提出在布图规划的同时考虑电压降的 优化，降低最终布图的电压降以及尽量满足各模块的电压降容限，从而加快物理 设计收敛。首先，介绍提取优化电压降的目标函数，然后再讨论模拟退火过程中 的选择策略，最后用线性规划进行软模块压缩。 第六章为考虑热点以及热量均匀分布的测试规划算法，提出在对s o c 进行 测试规划时考虑避免热点和均匀地分布热量，从而提高芯片测试的成品率。本章 将热点问题以及热量均匀分布问题转化为模块之间距离问题，通过模块之间的距 离来决定它们是否可以同时测试。 第七章为总结和展望，总结了本文讨论的算法以及对未来研究展望。 第二章布图表示方法 第二章布图表示方法 布图表示问题是自动布图规划中的基本问题，研究人员此问题已经进行大量 的研究 w o n 9 8 6 “m u r a 9 5 、 n a k a 9 6 、 g u 0 9 9 】、 c h a n 9 0 0 、 h o n 9 0 0 、 l i n 0 1 等，提出了多种数据结构来表示布图当中各个模块的相对位置。一种合理的布图 表示方法，应该具备以下几个基本的要求：它的解空间必须是有限的，满足这 个要求才有可能在有限的时间内收敛到最优解；每个表示都能还原为一个可行 的布图；每个表示都能在有限的时间进行评价，也即是能在有限的时间内对一 个表示的目标函数进行评价；在所有表示中存在着最优解。 任意一个布图都可以归属为可二分( s l i c i n g ) 结构或者不可二分( n o n s l i c i n g ) 结 构。一个可二分结构的布图，是指可以通过水平或垂直线划分将芯片所在的矩形 划分成两个区域，而且这一过程可以递归地进行直到每个区域只有一个模块为 止；否则就是不可二分结构。如图2 1 所示，其中( a ) 为不可二分结构的布图；( b ) 为可二分结构的布图；( c ) 为二分的过程，如图所示，首先可以由垂直切割线划 ( a ) 不可二分结构布局( b ) 可二分结构布局 垂直切割线 i cc 胜兰i a a _ 二| | ；户 鬻。l 一啊 b 琴r ii l b ( i | _ 1 e ； 。卜 t ， ( c ) 二分过程 水平切割线 图2 i 可二分结构布图不可和二分结构布图 分成两个区域，其中一个区域只包括两个模块 a ，b ) ，另一个区域包括三个模块 c ，d ，e ) ，此区域再经过水平切割，便得到一个模块的区域以及两个模块的区域。 由于在实际中大部分布图为不可二分结构的布图，而且一般情况下能表示不可二 第二章布图表示方法 分结构布图的表示方法，也能表示可二分结构布图，反之则不成立，因此基于可 二分结构布图表示方法的算法将有可能找不到最优解，实际情况也是当今不可二 分结构布图的表示方法已经成为绝大部分算法的选择。 在文献 h o n 9 0 0 1 中提出一种新的布图结构的分类方法，分为马赛克结构与非 马赛克结构。马赛克结构一种基于划分的结构，马赛克结构的布图将芯片通过线 段划分成了n 个区域，用来放置各个模块，其中n 为模块的个数，因此马赛克 结构的布图中没有都没有空白区域，芯片面积被n 个区域占满。一个布图被称 为是马赛克结构必须满足如下三个性质：布图中没有空白区域，也即n 个区 域占满整个布图，如图所示2 2 ( a ) ，其中有空白区域，因此不是马赛克结构； 线段移动前后布图的拓扑结构是等效的，如图所示2 2 ( b ) ( c ) ，线段移动前后的两 个马赛克布图的拓扑结构是等效；不允许有两个t 形连接相交于一点，如图 所示2 2 ( d ) ，两个t 形连接相交在点，因此并不是马赛克结构布图。 。a i 争b j q l | d ( b ) 移动前 k j ob c 一。f 。7 d ( a ) 有空白区域，不 ( c ) 移动后 是马赛克布局 a 氍 _ j - e ! i i ；i i i文 h ( d ) 两个t 形连接交于一 点，不是马赛克布局 图2 2 马赛克与非马赛克结构布圈 由上面对马赛克结构布图的描述可以看出，这个分类方法不同于可二分与不 可二分结构布图的分类方式，它们之间的关系如图2 3 所示，有交集，但是没有 相互包含关系。在本章下文中，将首先介绍可二分结构的布图表示方法，主要介 图2 3 两种分类方法的比较 绍二叉树表示法；然后再介绍不可二分结构的布图表示方法，主要介绍序列对表 第二章布图表示方法 示法；最后在介绍马赛克结构的布图表示法，主要介绍c b l 表示法。 2 1 各种表示方法的解空间以及结果 表2 1 各种表示方法的解空间以及最好的结果 表示方解空间评价时间 a m i 3 3 a m i 4 9 a p t e x e f o x h p 法 n p e o ( n1 2 2 5 4 3 n 15 1 n an an an an an a s p o ( ( n ! ) 2 )o f n l o g l o g n ) l2 1 3 6 54 6 91 9 88 9 5 t c g o ( ( n ! ) 2 )o ( n 2 ) 1 2 03 6 84 691 9889 5 t c g - s 0 ( ( n ! ) 2 ) o m l o g n ) l1 93 644 691 9 88 9 5 o 仃e e o ( n 1 2 2 ”2 n 11 o ( n ) l2 43 77 4 692 0 29 1 6 b + t r e e o ( n1 2 2 “2 n 1 5 、 o ( 1 ) 1 2 73 6 84 6 91 9 88 9 5 c b l o ( n 1 2 3 ”3 n 1 5 、 o ( n ) 1 1 83 6 1n a1 9 8n a t b sn a n a1 2 l3 7 04 7 21 9 89 0 3 注其中n a 表示没袁这方面信总 在布图规划过程中，我们一般采用随机搜索( r a n d o ms e a r c h ) 算法，特别是模 拟退火算法被广泛地使用，而且在随机搜索算法中，时间主要是开销在不停地 移动以构造新布图；评价新布图。因此，一种表示方法的解空间大小以及评价 时间大小将主要决定算法的优劣程度。在表2 1 中，我们列出了几种表示方法的 解空间、评价时间复杂度以及m c n c 9 2 m c n c 9 2 坝, , 1 1 试电路的最优结果。 2 2 可二分结构布图表示方法 可二分结构的布图表示方法研究的较早，在文献 o r e n 8 2 提出用二叉树来表 示可划分布图，但是二叉树和可二分布图并不是对应的关系，有时一个布图 对应多个二叉树，这增大了问题的解空间。文献 w o n 9 8 6 】在此基础上提出n p e 表示方法，n p e 被认为是目前求解可二分布图最有效也是最常用的表示方法， 它和可二分布图是一一对应的关系。下面我们首先先介绍二叉树表示法，再介绍 n p e 表示法。 2 2 1 二叉树( s l i c i n gt r e e ) 表示法 二叉树是较早提出的表示可二分结构布图的表示方法，一个二叉树又可以由 一个p e ( p o l i s he x p r e s s i o n ) 来表示，而且二叉树与p e 之间是对应的关系 w o n 9 8 6 。如图2 4 ( a ) 所示，对一个布图进行垂直切割在二叉树中由节点“ 表示，其左子为垂直切割线左边的模块，右子为垂直切割线右边的模块，这个二 叉树对应的p e 为“1 2 + ”；对一个布图进行水平切割在二叉树中用节点+ 表 第二章布图表示方法 示，其左子为水平切割线下面的模块，右子为水平切割线上面的模块，这个二叉 树对应的p e 为“1 2 + ”。但由于二叉树表示方法本身的局限性，已经不太被使用， 首先，它和可二分结构的布图并不是一一对应关系，因此这个增大了问题的解空 间；而且每个可二分布图对应的二叉树的个数并不一样如图2 4 ( b ) ( c ) 所示，2 4 ( b ) 的布图只能对应一个二叉树，而2 4 ( c ) 的布图确对应着两个二叉树，这种现象在 用模拟退火算法搜索最优解过程中很可能会导致偏向某些布图，从而无法找到最 优解 w o n 9 8 6 。 + 口团 p e ：1 2 p e ：1 2 + ( a ) 基本的变换 圆 圈 + 1 + +4 2 3 + 1 +4 32 p e ：3 2 + 4 1 + ( b 】对应着一个二分树 p e ：1 2 3 + 4 “或1 ( ( 2 3 4 + ) + + +4 + 2 3 ( c ) 对应着两个二分树 图2 4 二二叉树表示布图的情况 2 2 2n p e ( n o r m a l i z e dp o l i s he x p r e s s i o n ) 表示法 针对二叉树( 也即p e ) 表示的不足，文献 w o n 9 8 6 提出用n p e 唯一表示可二 分结构的布图，并且证明n p e 和可二分结构的布图是一一对应的关系。因此， 这个表示法解决了二叉树的不足，并且在该文献中实现的算法非常有效，很好地 解决了可二分结构布图问题。 关于n p e 的些定义： 一个p e = q 。，当且仅当其中没有连续的“”或者“+ ”， 才能被称为n p e ，因此，在图4 2 ( c ) 中左边二叉树的p e = 1 2 3 + 4 * ，并不是 n p e ，因为其中有连续的“幸，而右边二叉树的p e = 1 2 3 + 4 ，是n p e ； n p e 中的数字( 1 、2 、n ) 被称为操作数，而符号“”和“+ ”被称为操 作符。 日八 第二章布图表示方法 一个n p e 所代表布图的面积的计算： 计算在n p e 对应的二叉树中各个节点的面积，计算一个节点面积时， 只需要累加它所有叶子的面积，最后计算根节点的面积，根节点的面积就 是布图的面积。 用n p e 表示方法的模拟退火过程中的三种移动方式： 移动l ：交换两个相邻的操作数； 移动2 ：对某段由操作符组成的链取补，即用+ 替代+ ，用+ 替代+ ； 移动3 ：交换相邻的操作数和操作符。 三种移动方式对应的布图变化如图2 5 所示。 l ；f； 34 3 2 4 5 + i + 移动i - 移动2 一 l 4 | | ： l j 豢 ：i 1 3z i _ i i j l 移动3 i 图2 5 ：n p e 的三种移动方式 显然对于一个n p e 表示式，经过移动1 或者移动2 后的表达式仍满足n p e 表达式的条件，而移动3 可能会将一个n p e 表示式转化为一个非n p e 表示式， 因此为保证得到一个新的表达式仍为n p e 表示式，在进行移动3 时首先要检查 一下移动后是否还是n p e 表达式，文献 w o n 9 8 6 证明是检测一个表示式是否符 合n p e 可以在线性时间内完成。 2 3 不可二分布图表示方法 由于很多布图都是不可二分的，特别是在最优解是不可二分结构的情况下， 基于可二分布图表示方法的算法无法搜索到最优解。因此，近年来研究人员提出 对不可二分布图表示方法进行了大量的研究，并提出了多种有效的表示方法，例 如序列对 m u m 9 5 m u r a 9 6 、o t r e e g u 0 9 9 、b * - t r e e c h a n 9 0 0 、t c g l i n 0 1 等 等。 第二章布图表示方法 文献 m u r a 9 5 1 用序列对来求解矩形模块的布图问题，主要的想法是用序列对 来表示各个模块的空间上的相对位黄，并对序列对进行评价来计算所对应的目标 布图的面积。它的解空间大小为( n ! ) 2 ，从序列对转换到实际布图的时间复杂度为 o ( n l g ) ，其中n 为模块的个数。 文献 g u 0 9 9 】提出一种基于树的表示方法：o - t r e e ，它解空间仅为 o ( n1 2 2 ”2 n 15 ) ，评价一个0 t r e e 的时间复杂度为o ( n ) ，但是由于o - t r e e 的结构是 不规则的，一个基本的操作如搜索、插入比较复杂。 针对o t r e e 的操作上的复杂性，文献c h a n 9 0 0 提出基于有序的二叉树 ( o r d e r e db i n a r y t r e e ) 的表示方法：b + t r e e s ，这个表示方法有着与o t r e e 一样的解 空间，但是基本的操作更加简便。 参考文献 l i n 0 1 冲提出了t c g 表示法，一方面t c g 与b + t r e e 和o t r e e 类 似，是一种直观的表示法，根据t c g 可以直观的表示模块的位置信息；另一方 面与序列对类似，t c g 也是一种可拓扑的表示方法，任意平面布图均可以由t c g 表示。在下面小节中，我们将主要介绍序列对表示以及b + t r e e s 表示法。 2 3 1 序列对表示法 序列对在9 0 年代中期提出 m u r a 9 5 ，它的解空间为( n ! ) 2 。序列对能描述所 有布图的拓扑结构，而且对它的操作很方便，只需要对序列里面的两个元素进行 交换位置，是一个优秀的表示方法。序列对用两个序列来描述各个模块之间的空 间相对位置关系，一个为正序列，个为负序列。 2 3 1 1 从布图到正负序列 序列对通过正负序列来描述一个布图。正序列是通过正阶梯线构造的，正阶 梯线是通过从模块的中心位置开始分别通过“上一右”以及“下一左”移动得到 的；“上一右”即向上移动碰到边界就向右移动，再碰到边界就向上移动，并重 复这样的移动过程直到布图的右上角；同理“下一左”即先向下移动碰到边界就 向左移动，再碰到边界又向下移动，重复这样的移动过程直到布图的左下角。边 界有三种分别为如下：模块边界布图边界已有的阶梯线。 正阶梯线如图2 6 ( a ) 中所示，图中只画出模块e 的正阶梯线，“上一右”移 动过程如下：首先从e 模块的右上角出发，向上边移动，碰到布图的边界后向右 移动，一直移动到布图右上角( p 3 点) ；同理“下一左”移动也是类似过程：从 模块e 的左下角出发向下移动，碰到模块f 边界后向下移动，一直到布图左下角 ( p 1 点) 。 第二章布图表示方法 ( a ) 正阶梯线 ( b ) 负阶梯线 图2 6 正负阶梯线的构造 而负序列则通过负阶梯线得到，负阶梯线是通过从模块的中心位置开始分别 通过“左一上”以及“右一下”移动得到的；“左一上”即向左移动碰到边界( 模 块边界或者芯片边界) 就向上移动，再碰到边界就向左移动，并重复这样的移动 过程直到布图的左上角；同理“右一下”即先向右移动碰到边界就向下移动，再 碰到边界又向右移动，重复这样的移动过程直到布图的右下角。图2 6 ( b ) 显示了 模块e 的负阶梯线，可阻看出通过“左一上”以及“右一下”移动得到负阶梯线。 参考文献 m u r a 9 6 1 中已经证明对任一平面布图，由于只要碰到已有的阶梯线 便要改变方向，所以，不同模块的正阶梯不会相交，不同模块的负阶梯也不会相 交。 ( a ) 正序列二 t + 。 e ，c ，a , d ，f , b ) ( b ) 负序列： t - = e c ，b ，e ，叫) 图2 7 正负序列对的构造 正序列的构造：在画出各个模块正阶梯线之后，按照各条正阶梯线之问的上 下位置来构造正序列。如图2 7 ( a ) 所示模块e 的正阶梯线处于最高位置，因此在 正序列中e 处于第一位，接下来按照正阶梯线的上下位置依次是c 、a 、d 、f 、b 。 第二章布图表示方法 负序列的构造则是按照负阶梯线之间的上下位置，不同与正序列，负阶梯线处于 下方的模块，在负序列中处于前面的位置。如图2 7 ( b ) 所示，模块f 的负阶梯线 处于最低位置，但是它在负序列中处于第一位，其他从下到上依次为c 、b 、e 、 a 、d 。 2 3 1 2 正负序列中的空间位置信息 ( a ) 模块e 在模块c 的上面 ( t + ，t 七= ( ec ，ce ) 一上下 ( b ) 模块a 在模块e 的右边 ( t + t _ ) _ ；( ea ，ea ) 一左右 正负序列：( t + ，t - ) ：( ecad fb ，fc be ad ) 图2 8 序列对中的位置对应布图中的位置 序列对中元素的相对位置关系可以反应模块间的空间相对位置关系，如果两 个模块在正负序列中的位置关系是“单调”的，则它们在空间的位置关系是左右 关系，如果是“非单调”的，则在空间的中位置关系是上下关系。如图2 8 ( a ) 所 示，在正序列中模块e 在模块c 的左边，而负序列中模块e 在模块c 的右边，它 们在正负序列中是非单调的，所以对应的布图中模块c 在模块c 的上边；而图 2 8 ( b ) 则是另一种情况，在正负序列中模块c 都在模块a 的左边，是单调关系， 所以布图中模块e 在模块a 的左边。下面将描述模块正负序列中的位置是如何对 应到空间上的位置。 一个模块的正负阶梯线将相对于本模块的空间划分成了四个部分，如图 2 8 ( a ) 所示，模块e 的正负阶梯线构成了四个相对位置一“上”、“下”、“左”、“右”： 正阶梯线的下方包含了“下”和“左”的位置空间，上方则是“上”和“右”的 位置空间，同理可以分析负阶梯线的情况。 例如模块c ，在正序列中处于模块e 的右边，也即布图中模块c 的正阶梯线 处于模块e 正阶梯线的下方( 见上小节正阶梯线的画法) ，因此，模块c 在布图中 位于模块e 的“下”或“左”；在负序列中模块c 处于模块e 的左边，也即布图 中模块c 的负阶梯线处于模块e 负阶梯线的下方，因此，模块c 在布图中位于模 块e 的“下”或“右”；最后，两者交集， “下”、“左”) n f “下”、“右” = 第二章布图表示方法 “下”，因此模块c 处于模块e 的下方。同理也可分析图2 8 ( b ) 的情况，即模块a 在正负序列中都处于模块e 的右边。 2 3 1 2 从正负序列到布图 从正负序列构造布图的过程，也即是计算各个模块的空间相对坐标的过程， 当每个模块的空间相对坐标都确定了，那么布图的尺寸也就决定了。文献 m u r a 9 6 】 中提出通过构造水平约束图以及垂直约束图来计算各个模块的相对坐标。 水平约束图g ( 矿，e ) 是根据序列对中的“左右”关系以及模块的宽度得到的， 其中v 是节点的集合，包括源点5 、终点f 、各个模块x ( 1 x n ) ；e 是边的边 界集合，包括：p ( j ，z ，) 其中而为布图最左边的模块，即没有模块在的左边， e ( x r ，t ) 其中x ，为布图最右边的模块，e ( x ，x ) 其中模块x 在模块x 的左边；对于源 点s 和终点f 权重为0 ，对于其他节点权重为此模块的宽度。例如对于序列对 ( t + ，y ) = ( ec ad f b ，f cbea d ) 的水平约束图，如图2 9 ( a )