（微电子学与固体电子学专业论文）时钟偏差规划关键问题的有效算法研究.pdf

摘要 摘要 半导体工业的迅速发展给集成电路的计算机辅助设计( c a d ) 带来了很多挑 战：一方面，随着特征尺寸的不断缩小，工艺偏差的影响日益严重，使得电路设计 时，需要考虑可实现性、成品率等因素。现有的电路优化方法，如时钟偏差规划， 需要做进一步的研究和改进。另一方面，随着电路规模的指数级增大，其对计算 机辅助设计算法的性能提出了越来越高的要求，这导致许多集成电路优化的问 题，需要研究新的求解方法，以满足超大规模集成电路的需求。 作为强大的时序优化技术之一，时钟偏差规划通过有意地给触发器分配不同 的时钟延时( 触发时间) ，来优化电路的性能。传统的时钟偏差规划可转化为网络 流中的最小环比问题，并采用高效的算法求解。在实际电路设计中，触发器的时 钟延时最终要通过时钟网络中的互连线和额外的缓冲器来实现。传统时钟偏差 规划可能需要大量不同的时钟延时，这导致两个潜在的问题：一个是时钟网络中 缓冲器的大量增加导致不可接受的面积和功耗开销，另一个是，在工艺偏差的影 响日益严重的情况下，同时精准地实现大量不同的时钟延时变得越来越难。最 终传统时钟偏差规划在工业界的应用受到了很大限制。 多域时钟偏差规划技术提出，在优化电路性能的同时，将触发器分配到若干 个时钟域内，这巧妙地解决了时钟网络的可靠实现问题。然而，离散时钟域的引 入，使得问题的复杂度变为n p c o m p l e t e ，无法采用传统的方法求解。现有的算法 要么在时间复杂度上太高，要么在计算精度上无法让人满意，亟需研究高效的求 解算法。本论文围绕多域时钟偏差规划问题的有效算法进行了深入的研究。 首先，本论文提出了一种多域时钟偏差规划问题的快速算法，主要贡献有： 首次提出，通过略微施加更多约束，将问题转换为一种近似的、可解的混合 整数线性规划( m i l p ) 问题。这种转化的优势在于，能够从全局的角度来考 虑时钟域分配，并且一次性最优地求解。 针对转换后的m i l p 问题，研究该问题的特殊性后，提出了一种广义 h o w a r d s 算法来有效地求解。 提出了一种增点t 式的面向关键环的时钟域分配改良算法，以继续改进结果。 为了进一步提高多域时钟偏差规划算法的性能，提出了一种图剪接算法，可 摘要 以用于对时序约束图进行预处理，从而有效地降低输入规模。 实验结果证明，所提出的快速算法具有接近最优解的精度，在i s c a s 8 9 基准 电路上的9 3 次测试中，有8 8 次( = 9 4 6 ) 获得了最优解，同时在性能上比现有算 法有至少一个数量级的提升。对于图剪接算法，实验结果也验证了其有效性，应 用于快速算法后，使后者在性能上有1 4 3 x 4 7 6 x 的进一步提升( 平均2 6 6 x ) 。 随后，针对多域时钟偏差规划问题，为了能够获得理论上保证的最优解，我们 还提出了一种精确算法，主要贡献有： 提出了基于分支定界的算法，来搜索最优的时钟域分配方案。 提出了三种有效的分支策略，来提高搜索效率，包括最小裕量优先分支的策 略、基于负路径的分支限制策略以及最小代价优先处理的策略。 采用了有效的定界算法，其中快速算法被用来作为计算下界的子程序。 实验结果验证了该算法的精确性和有效性。例如，在i s c a s 8 9 基准测试电 路上，精确算法均在3 1 5 秒内获得了最优解。 快速算法和精确算法循序渐进地解决了多域时钟偏差规划的计算问题，为其 在工业界的广泛应用提供了有效的求解方法。 工艺偏差影响的不仅是时钟网络中的延时，同时对电路本身也有广泛的影 响。随着工艺偏差规划影响日益严重，电路延时的不确定性增加，最终导致时序 成品率的问题。因此，如何设计时钟延时以优化成品率，也是时钟偏差规划技术 中的关键问题。通用的成品率驱动时钟偏差规划，结合当前分析电路延时普遍采 用的统计时序分析方法，能够精确地考虑路径延时在工艺偏差下的统计分布，因 而在优化成品率上有天然的优势。本论文围绕此问题展开研究，主要贡献有： 在理论上明确地指出了其广义网络流问题的特殊性。 提出了高效的广义网络流算法来求解，包括广义h o w a r d s 算法( v 2 ) 和改进 的广义最小平衡算法。 实验结果验证了算法的高效性。相比已有算法，所提出的算法在性能上有显 著的优势，尤其是在大电路上，最高有1 5 7 5 5 x 的加速。 关键词：时钟偏差规划；多时钟域；最小环比问题；混合整数线性规划；分支定界； 广义网络流算法 中图分类号：t n 4 7 a b s t r a c t a b s t r a c t t h er a p i dd e v e l o p m e n to fs e m i c o n d u c t o ri n d u s t r yi n t r o d u c e sal o to fc h a l l e n g e s t ot h ei n t e g r a t e dc i r c u i t ( i c ) d e s i g n o no n eh a n d ，w i t ht h eq u i c ks c a l i n gd o w no f f e a t u r es i z e ，p r o c e s sv a r i a t i o n sh a v em o r ea n dm o r ei m p a c to nc i r c u i t s s t a t e - o f - t h e - a 1 1i cd e s i g nm u s tt a k en e wf a c t o r si n c l u d i n gp r a c t i c a l i t ya n dy i e l di n t oc o n s i d e r a t i o n e x i s t i n go p t i m i z a t i o nt e c h n i q u e s ，s u c ha sc l o c ks k e ws c h e d u l i n g ，n e e df u r t h e rs t u d y a n di m p r o v e m e n t o nt h eo t h e rh a n d ，t h ee x p o n e n t i a li n c r e a s eo fi n t e g r a t i o nc a p a b i l i t y d e m a n d sh i g h e rp e r f o r m a n c ef o rt h ea l g o r i t h m si nc o m p u t e ra i d e dd e s i g n ( c a d ) m a n y o p t i m i z a t i o np r o b l e m s n e e dn e w s o l v i n gm e t h o d s t om e e tt h er e q u i r e m e n t so f v e r yl a r g e s c a l ei n t e g r a t e dc i r c u i t s a so n eo ft h em o s tp o w e r f u ls e q u e n t i a lo p t i m i z a t i o nt e c h n i q u e s ，c l o c ks k e w s c h e d u l i n go p t i m i z e st h ep e r f o r m a n c eo fc i r c u i t sb yd e l i b e r a t e l ya s s i g n i n gd i f f e r e n t c l o c kd e l a y st of l i p - f l o p s c o n v e n t i o n a lc l o c ks k e ws c h e d u l i n gc a nb et r a n s f o r m e d i n t oam i n i m u mc y c l er a t i op r o b l e ma n ds o l v e db ye f f i c i e n tn e t w o r kf l o wa l g o r i t h m s i np r a c t i c e ，t h ec l o c kd e l a y sa r ei m p l e m e n t e dt h r o u g ht h ei n t e r c o n n e c t sa n da d d i t i o n a l b u f f e r si nc l o c kd i s t r i b u t i o nn e t w o r k c o n v e n t i o n a lc l o c ks k e ws c h e d u l i n gm a yn e e d al a r g es e to fc l o c kd e l a y s ，w h i c hc a u s e ss e v e r a lp o t e n t i a li s s u e si nt h ei m p l e m e n t a t i o n o fc l o c kn e t w o r k o no n eh a n d ，t h ee x c e s s i v ed e m a n do fb u f f e r si nc l o c kn e t w o r km a y i n t r o d u c eu n a c c e p t a b l ea r e aa n dp o w e ro v e r h e a d 0 nm eo t h e rh a n d w i t ht h ei m p a c to f p r o c e s sv a r i a t i o n s ，i tb e c o m e sm o r ea n dm o r ed i f f i c u l t t or e l i a b l yi m p l e m e n tal a r g es e t o f c l o c kd e l a y ss i m u l t a n e o u s l y c o n s e q u e n t l y ，t h ea p p l i c a t i o no f c l o c ks k e ws c h e d u l i n g i ni n d u s t r i a lf i e l di sg r e a t l yl i m i t e d m u l t i d o m a i nc l o c ks k e ws c h e d u l i n gt a c k l e st h er e l i a b l ei m p l e m e n t a t i o no f c l o c k n e t w o r kb ya s s i g n i n gf l i p f l o p st os e v e r a lc l o c k i n gd o m a i n sw h i l eo p t i m i z i n gt h ep e r f o r m a n c eo fc i r c u i t s h o w e v e r ，d u et ot h ei n t r o d u c t i o no fd i s c r e t ec l o c k i n gd o m a i n s ， t h ec o m p l e x i t yo f t h ep r o b l e mb e c o m e sn p - c o m p l e t e ，w h i c hm a k e s i tu n s o l v a b l eu s i n g t r a d i t i o n a la p p r o a c h e s 。e x i s t i n ga l g o r i t h m sa r ee i t h e rc o m p u t a t i o n a l l yt o oe x p e n s i v e o rp o o ri ns o l u t i o nq u a l i t y t h em u l t i d o m a i nc l o c ks k e ws c h e d u l i n gn e c e s s i t a t e se f f i i i i ! ! ! ! 垦盟 一一 _ _ 一。一 c i e n ta l g o r i t h m st h a ta r eg o o da tb o t hp e r f o r m a n c ea n da c c u r a c y i nt h i st h e s i s ，e f f i c i e n t a l g o r i t h m sf o rt h em u l t i d o m a i nc l o c ks k e ws c h e d u l i n gp r o b l e ma r e s t u d i e d f i r s t af a s ta l g o r i t h mf o rm u l t i d o m a i nc l o c ks k e ws c h e d u l i n gi sp r o p o s e d 。t h e c o n t r i b u t i o n si n c l u d e ： t h ed r o b l e mi st r a n s f o r m e di n t oa na p p r o x i m a t ea n d s o l v a b l em i x e di n t e g e rl i n e a r p r o g r a m m i n g ( m i l p ) p r o b l e m t h ea d v a n t a g eo f t h i st r a n s f o r m a t i o ni st h a t ，i t c o n s i d e r st h ec l o c k i n gd o m a i na s s i g n m e n tg l o b a l l ya n dc a nb es o l v e do p t i m a l l y o n c ea n df o ra 1 1 f o rt h em i l pp r o b l e m b a s e do nt h em o n o t o n i c i t yi nt h ec o n s t r a i n t s ，ag e n e r a l i z e d h o w a r d sa l g o r i t h mi sp r o p o s e dt oe f f i c i e n t l ys o l v ei t a ni n c r e m e n t a lc r i t i c a l c y c l e o r i e n t e dr e f i n e m e n ti sp r o p o s e dt of u r t h e ri m p r o v e t h ed o m a i na s s i g n m e n t t of u r t h e ri m p r o v et h ep e r f o r m a n c eo fa l g o r i t h m sf o rt h em u l t i d o m a i nc l o c k s k e ws c h e d u l i n gp r o b l e m ，ag r a p hp r u n i n ga l g o r i t h mi sd e v e l o p e dt op r e p r o c e s s t h et i m i n gc o n s t r a i n tg r a p ha n de f f e c t i v e l yd e c r e a s et h ei n p u ts i z e t h ef a s ta l g o r i t h mi sa b l et oo b t a i nn e a r - o p t i m a ls o l u t i o n s i to b t a i n so p t i m a ls o 。 l u t i o n sf o r8 8o ft h e9 3 ( = 9 4 6 ) t e s t so ni s c a s 8 9b e n c h m a r k s i na d d i t i o n ，i th a sa d e r f o n n a n c eo fa tl e a s ta no r d e rf a s t e rt h a ne x i s t i n ga l g o r i t h m s f o rt h eg r a p hp r u n i n g a i g o r i t h m 。e x p e r i m e n t a lr e s u l t sa l s ov a l i d a t e t h ee f f e c t i v e n e s s i t sa p p l i c a t i o no nt h ef a s t a l g o r i t h ms h o w sa f u r t h e rp e r f o r m a n c es p e e d u po f1 4 3 x - 4 7 6 xf 2 6 6 xo na v e r a g e ) t oo b t a i nt h et h e o r e t i c a l l y - g u a r a n t e e do p t i m a ls o l u t i o n sf o rm u l t i d o m a i nc l o c k s k e ws c h e d u l i n g ，a ne x a c ta l g o r i t h mi sd e v e l o p e dt os e a r c hf o rt h eo p t i m a lc l o c k i n g d o m a i na s s i g n m e n t t h em a i nc o n t r i b u t i o n si n c l u d e ： a na l g o r i t h mb a s e do nb r a n c h a n d b o u n di sp r o p o s e dt os e a r c hf o rt h eo p t i m a l d o m a i na s s i g n m e n to ff l i p - f l o p s t h r e es t r a t e g i e sa r ep r o p o s e dt oi m p r o v et h ee f f i c i e n c yo ft h es e a r c h ，i n c l u d i n g m i n s l a c k f i r s t b r a n c h i n gs t r a t e g y n e g a t i v e - p a t h - a w a r ec o n f i n e m e n ta n dm i n c o s t f i r s t p r o c e s ss t r a t e g y e f f i c i e n tb o u n d i n ga l g o r i t h m sa r ea d o p t e d ，i nw h i c ht h ef a s ta l g o r i t h m i su s e dt o c o m p u t el o w e rb o u n d so fb r a n c h e s e x p e r i m e n t a lr e s u l t sv a l i d a t et h ea c c u r a c ya n de f f i c i e n c yo f t h ee x a c ta l g o r i t h m a b s t r a c t f o re x a m p l e ，i to b t a i n so p t i m a ls o l u t i o n sf o ra l lt h ei s c a s 8 9b e n c h m a r k si n3 15s e c o n d s p r o c e s sv a r i a t i o n sn o to n l yh a v ei m p a c to nc l o c kn e t w o r k ，b u ta l s oo nt h ed e l a y si n c i r c u i t st h e m s e l v e s t h eu n c e r t a i n t yo fd e l a y si nc i r c u i t sm a yc a u s et h es e q u e n t i a ly i e l d i s s u e t h e r e f o r e ，h o wt oa s s i g nt h ec l o c kd e l a y ss u c ht h a tt h ey i e l di so p t i m i z e di sa l s oa c r i t i c a lp r o b l e mi nc l o c ks k e ws c h e d u l i n g t e c h n i q u e s i n t e g r a t e dw i t h t h ep r e v a l e n ts t a - t i s t i c a ls t a t i ct i m i n ga n a l y s i st e c h n i q u e s ，g e n e r a ly i e l dd r i v e nc l o c ks k e ws c h e d u l i n g c o n s i d e r st h ed i s t r i b u t i o no fp a t hd e l a y sa c c u r a t e l y ，a n dt h u sh a sn a t u r a la d v a n t a g ei n y i e l do p t i m i z a t i o n ，i nt h i st h e s i s ，g e n e r a ly i e l dd r i v e nc l o c k s k e ws c h e d u l i n gi ss t u d i e d t h em a i nc o n t r i b u t i o n si n c l u d e ： t h e o r e t i c a l l y , ac l e a rs t a t e m e n ta b o u tt h es p e c i a lp r o p e r t yi nt h eg e n e r a ly i e l d - d r i v e nc l o c ks k e ws c h e d u l i n gp r o b l e mi sp r o v i d e d ，t h a ti s ，i ti sa c t u a l l yag e n e r - a l i z e dn e t w o r kf l o wp r o b l e m t oe f f i c i e n t l ys o l v et h ep r o b l e m ，t w og e n e r a l i z e dn e t w o r kf l o wa l g o r i t h m s ，a r e p r o p o s e d ，i n c l u d i n gg e n e r a l i z e dh o w a r d sa l g o r i t h m ( v 2 ) a n dg e n e r a l i z e d m i n i - m u mb a l a n c ea 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 sv a l i d a t et h ea d v a n t a g eo f t h ep r o p o s e da l g o r i t h m si np e r f o r - m a n c ec o m p a r e dw i t ht h ee x i s t i n ga l g o r i t h m ，e s p e c i a l l yo nl a r g ec i r c u i t s t h en e w a l g o r i t h m ss h o ws p e e d u p so f u pt o1 5 7 5 5 x k e yw o r d s ：c l o c ks k e ws c h e d u l i n g ；m u l t i - d o m a i n ；m i n i m u mc y c l er a t i op r o b l e m ； m i x e di n t e g e rl i n e a rp r o g r a m m i n g ；b r a n c ha n db o u n d ；g e n e r a l i z e dn e t - w o r kf l o wa l g o r i t h m c l a s s i f i c a t i o nc o d e ：t n 4 7 v 第1 章引言 第1 章引言 1 1研究动机 1 9 6 5 年，英特尔公司的创始人之一戈登摩尔( g o r d o nm o o r e ) 预测：在半导 体行业，每过大约1 8 个月，芯片上晶体管的数目翻一番【l 】。这一预测成为著名 的摩尔定律。四十多年过去了，集成电路的规模依然按照摩尔定律增长着。为了 增加芯片的集成度，集成电路的特征尺寸以指数级的速度不断缩小。如今制造工 艺早已步入纳米时代，英特尔公司也即将推出2 2 r i m 制程的微处理器【2 ，3 1 ，晶体管 数目达到1 4 亿以上。 半导体制造工艺的发展以及电路规模的指数级增长，给集成电路的计算机辅 助设计( c a d ：c o m p u t e ra i d e dd e s i g n ) 带来了很多挑战。 一方面，随着特征尺寸的不断缩小，工艺偏差的影响日益严重，使得在电路设 计时必须考虑可制造性的问题，现有的设计方法需要纳入可实现性、成品率等因 素。光刻工艺产生的图形偏差【4 】、铜互连的化学机械抛光工艺产生的金属互连线 高度的不均匀【5 1 ，都成为工艺偏差的重要来源。根据国际半导体技术蓝图( i t r s ： i n t e r n a t i o n a lt 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 s ) 的报告，受工艺偏差的影响， 电路中电学参数( 如晶体管的阈值电压) 的偏差可能高达3 5 t 6 1 。因此，在集成电 路设计中，包括电路的建模、分析与优化，都必须考虑工艺偏差的影响。尤其是在 进行电路优化时，工艺偏差的存在可能导致电路的性能与最初的设计目标相去甚 远，随之产生成品率下降的问题。现有的电路优化算法，如时钟偏差规划，往往需 要做进一步的研究和改进。 另一方面，随着电路规模的指数级增大，其对计算机辅助设计中算法的性能 提出了更高的要求：必乡t a ij b 够1 1d 时处驯上千万门甚至上亿门规模的设计。更严峻 的是，芯片从设计到投入市场的时间仍在不断地缩短，这就要求有高性能的软件 来支持。这导致许多集成电路设计的问题，需要研究新的求解方法，以满足超大 规模集成电路的需求。 准确地米说，存摩尔最初的论文一 - ，这个预测足t i 体1 j ：数| l 以大致每年翻一f | = 的速度递增；拒1 9 7 5 年， 摩尔：降此期限修正为两年。1 8 个j 的说法滁i n t e l 的d a v i dh o u s e 。 1 1 研究动机 作为强大的时序优化技术之一，时钟偏差规划通过给触发器分配不同的时钟 延时( c l o c k d e l a y ) ，来平衡时序电路中的“流水线”，从而达到优化电路性能的目 的【7 ，8 1 。在本文中，时钟延时指时钟到达时间( c l o c ka r r i v a lt i m e ) ，即触发器的触发 时间：时钟偏差指不同触发器在时钟延时上的差别。传统的时钟偏差规划是一种 特殊的线性规划问题，可以采用很多高效的算法来求解。然而，自1 9 9 0 年提出以 来，时钟偏差规划技术在工业界的应用一直受到很大限制，主要原因在于其可能 产生大量不同的时钟延时( 其中有些延时可能非常大) ，需要通过时钟分配网络【9 】 ( 以下简称时钟网络：因为常以树状结构实现，又可称为时钟树) 中的互连线以及 额外的缓冲器来精确实现。这带来两个潜在的问题，一个是时钟网络中缓冲器的 大量增加导致无法接受的面积和功耗开销，另一个则是，受工艺偏差的影响，这些 时钟延时越来越难以同时精准地实现。最终，传统时钟偏差规划的性能优化能力 无法得到有效发挥。 为了解决时钟网络的可实现性问题，r a v i n d r a n 等在2 0 0 3 年提出了多域时 钟偏差规划技术【l o 】，在优化电路的性能的同时，将触发器分配到若干个时钟域 中。在同一个时钟域内部，触发器之间具有相同的或者可忽略的时钟偏差，可以 通过传统的方式( 如采用对称结构的时钟树) 实现；在不同的时钟域之间，则允 许存在很大的时钟偏差，可以采用比较昂贵的器件，如“结构化时钟缓冲器”【l i i ( s t r u c t u r e dc l o c kb u f f e r s ) 、锁相环 1 2 1 ( p l l ：p h a s e l o c k e dl o o p ) 等来可靠实现。多 域时钟偏差规划巧妙地解决了时钟网络的实现问题，然而由于离散时钟域的引 入，使得问题的复杂度变成n p c o m p l e t e i l 3 【1 4 】。现有的算法要么在计算时间上复 杂度太高，要么就是在精度上不尽如人意，因此亟需研究高效的求解方法。 工艺偏差影响的不仅是时钟网络，同时对电路中的延时也有广泛的影响。电 路延时表现出越来越大的不确定性，引起时序约束的违反，最终导致成品率的损 失( y i e l dl o s s ) ，因此如何设计触发器的时钟延时以优化成品率，也是时钟偏差规 划技术中的关键问题，即成品率驱动的时钟偏差规划 8 1 。需要指出的是，多域时 钟偏差规划主要解决的是在性能优化的同时，触发器的时钟域分配问题，并没有 完全确定时钟延时，因此，在时钟域的分配以及时钟周期给定之后，完全。口j - 以采用 成品率驱动的时钟偏差规划技术来继续优化电路的设计。在优化成品率时、需要 精确地考虑电路中的延时在工艺偏差下的变化，现有的大部分算法都假设电路中 的延时服从特定的分布，如高斯分布，然而近年来越来越多的研究证实，随着工艺 偏差的影响日益严重，电路延时服从高斯分布的假设已经不再有效【1 5 1 9 1 。w a n g 2 第1 章引言 等提出了一种通用的成品率驱动的时钟偏差规划方法 2 0 ，2 1 1 ，结合了当前分析电 路延时普遍采用的统计时序分析方法，能够精确地考虑任意统计分布的电路延 时，从而更好地优化成品率。相应地，这方面也需要研究高效的算法来求解。 本论文主要针对时钟偏差规划技术的关键问题研究有效的算法，包括多域时 钟偏差规划和通用的成品率驱动时钟偏差规划。接下来将展开介绍研究背景和 研究现状。 1 2 研究背景和研究现状 1 2 1传统时钟偏差规划 在传统的时序电路设计中，所有触发器都在同一个时刻翻转，即零时钟偏差 设计【2 2 ，2 3 】。这种设计的优点是控制触发器翻转的时钟网络相对容易实现，如采 用对称结构的时钟树，然而其缺陷在于，电路的性能受限制于最长组合逻辑电路 的延时。早在1 9 9 0 年，f i s h b u r n 提出了时钟偏差规划技术，通过给触发器分配 不同的时钟延时，来优化电路的性1 7 1 。时钟偏差规划的本质是从非关键路径 上“偷取”时间，并用于关键路径。传统的时钟偏差规划要求在满足时序约束的 同时，最小化时钟周期，该问题可以用线性规划的方法来描述，并采用如单纯形 法 2 4 1 ( s i m p l e x a l g o r i t h m ) 、内点法 2 5 1 ( i n t e r i o r p o i n t m e t h o d ) 等通用的方法来求解。 但由于问题的特殊性，时钟偏差规划可以采用一系列更为高效的网络流( n e t w o r k f l o w ) 算法来求解。随后，d e o k a r 等提出采用二分搜索的方法来求解【2 6 】，a l b r e c h t 等提出用带参数的最短路径算法【2 7 ( p a r a m e t r i cs h o r t e s t p a t ha l g o r i t h m ) 来求解【2 8 】， r a v i n d r a n 等则运用b u m s 算法【2 9 】来求解【3 0 】。这一系列研究都为传统的时钟偏 差规划问题提供了有效的求解方法。 然而，传统时钟偏差规划技术一直无法避免的问题是，其结果中可能需要大 量不同的时钟延时。在实际电路中，时钟延时是通过时钟网络中的互连线和额外 的缓冲器来实现的。一方面，这些大量不同的时钟延时( 其中有些延时可能非常 大) ，需要时钟网络中增加很多缓冲器，可能导致无法接受的额外面积和功耗开 销：另一方面，随着半导体工艺制程不断缩小，工艺偏差对时钟网络中延时的影响 越来越大，同时可靠地实现大量的时钟延时变得越来越难。这些都很大程度上限 制了传统时钟偏差规划的优化能力，也是导致其在工业界难以得到广泛应用的根 本原因。 3 1 2 研究背景和研究现状 1 2 2多域时钟偏差规划 为了从根本上解决传统时钟偏差规划存在的时钟网络可实现性问题， r a v i n d r a n 等提出将时钟偏差规划与多时钟域的设计结合起来【1 0 】，即多域时钟偏 差规划技术。在当前的集成电路设计方法学中，时钟域大多都是采用人工的方法 分配，这在一定程度上限制了电路性能优化的空间。多域时钟偏差规划在优化电 路性能( 最小化时钟周期) 的同时，将触发器分配到若干个不同的时钟域中，属于 同一个时钟域的触发器要求有相同的或者可忽略的时钟偏差，通过传统的方法 ( 如对称结构的时钟树) 实现；不同时钟域之间的触发器，则允许存在较大的时钟 偏差，可以采用相对昂贵的相移器件来可靠地实现。多域时钟偏差规划的实质 是，在传统时钟偏差规划的基础上，限制可能的时钟延时的总数目。 自提出以来，多域时钟偏差规划技术受到了广泛的关注。首先，如何有效求 解多域时钟偏差规划一直是个开放的问题。离散时钟域的引入，使问题变得非常 复杂。r a v i n d r a n 等将问题描述为一个o 1 混合整数规划问题【1 0 1 ，并提出了基于 布尔可满足性 3 h ( s a t ：s a t i s f i a b i l i t y ) 的精确算法( 在本文中称为s a t - b a s e d ) 。该 算法通过反复调用s a t 求解器来穷举可能的时钟域分配方案，在获得精确解的同 时，时间复杂度也非常高。例如，在一个只有2 9 2 1 个触发器的电路上，s a t - b a s e d 算法用了2 0 个小时仍然未能获得最优解【1 0 】。后来，c a s a n o v a 在2 0 0 9 年提出了 基于多层聚类的快速算法 3 2 1 ( 在本文中称为m u l t i 1 e v e lc l u s t e r i n g ) ，通过不断对 电路中的触发器进行聚类、来实现时钟域的分配。该算法具有比s a t - b a s e d 算 法好得多的性能，但同时也一定程度上牺牲了结果的质：超。比如，在电路测试结 果中，最大误差达到了7 ，其根本原因在于，聚类时只能实现局部最优而无法考 虑全局的影响。l i 等在2 0 11 年证明了，多域时钟偏差规划问题的理论复杂度为 n p c o m p l e t e i 4 。到目前为止，还没有一种算法能够在性能和精度上达到一种很 好的平衡。 除了求解算法之外，最近有多研究者提出了与多域时钟偏差规划相关的技 术。f i s h b u r n 在论文【3 3 】中提出采用修改过的b e l l m a n f o r d 算法【3 4 】求解一个由 差分约束( d i f f e r e n c ec o n s t r a i n t s ) 构成的问题，其中变：l l 可取的值限制为一系列 离散值。该算法可以用来求解时钟域预先给定的多域时钟偏差规划问题。后 来，h u a n g 等【3 5 】和l i n 等【3 6 】分别提出了考虑峰值电流( p e a kc u r r e n t ) 和延时补充 ( d e l a yp a d d i n g ) 的多域时钟偏差规划技术。在这些工作中，都要求预先确定时钟 4 第1 章引言 域，这在一定程度上限制了性能优化的能力( 即可达的最小时钟周期) 。相反， r a v i n d r a n 等在论文【1 0 】中提出的多域时钟偏差规划问题，除了总数目之外对时钟 域本身没有任何限制，而且其实验结果也证实，在时钟域数目不多的情况下，多域 时钟偏差规划依然具备与传统时钟偏差规划同等强大的电路性能优化能力。因 此，本论文的研究主要围绕论文 1 0 】中的多域时钟偏差规划问题展开。 n i 等提出了一个与多域时钟偏差规划略微不同的问题：给定最优时钟周期， 最小化所需时钟域的数目【3 7 1 ，并采用启发式的算法来求解。在其实验结果中发 现，个别电路可能需要很多个时钟域来实现最小的时钟周期。这个方法的缺陷在 于，可能引入很多个时钟域。考虑到实现时钟域的昂贵代价( 如相移器件) ，尤其 是在电路面积和功耗上的开销【38 1 ，仅仅为了时钟周期微小的改进而增加大量时 钟域往往是不明智的。相反在给定时钟域数目的同时优化电路性能则避免了这 一问题，对于电路设计也更为合理。 m o h a m m a d z a d e h 等 3 8 】和y a n g 等【3 9 】先后提出了多域时钟偏差规划技术与 布局( p l a c e m e n t ) 算法结合的方法，从而有效降低时钟网络的总线长和功耗。这进 一步验证了多域时钟偏差规划技术的优势，并强化了业界对于高效求解该问题的 需求。多域时钟偏差规划在优化电路性能以及时钟网络方面的优势，是我们研究 该问题高效算法的动机所在。 1 2 - 3 成品率驱动的时钟偏差规划 工艺偏差影响的不仅是时钟网络的延时，同时还有电路本身，尤其是门电路 的延时。在时钟偏差规划中，触发器的时钟延时必须同时满足建立时间和保持时 间约束，这两种约束共同给出了触发器间时钟偏差的可行域( f e a s i b l er e g i o n ) 。传 统时钟偏差规划以及多域时钟偏差规划解决了性能优化的问题，然而给出的时钟 延时往往使得触发器间的时钟偏差在这些可行域的边界上。这意味着，一旦电路 中的延时在工艺偏差的影响下发生了变化，便很可能违反时序约束。而对一个电 路而言，任何时序约束的违反，都将造成成品率的损失( y i e l dl o s s ) 。因此，随着半 导体工艺制程的不断减小，工艺偏差的影响日益严重，越来越多的学者开始研究 抗工艺偏差的时钟偏差规划技术，以提高电路的成品率。 f i s h b u m 等最早提出，在最小化时钟周期之前，预先给所有的时序约束分配 固定的裕量【7 2 0 】( s l a c k ) ，以提高抗工艺偏差的能力。这种方法能够确保所有的时 序约束容许一定的工艺偏差，然而其并没有将所有时序约束抗工艺偏差的能力最 5 1 3 本文研究的研究内容和主要贡献 大化，同时也牺牲了电路的部分性能。另一种相对更为合理的方法是，将所有的 时钟偏差都尽可能放在其可行域的中间位置。基于这样的思路，n e v e s 等提出将 问题描述为一个最小二乘问题并求解【4 0 ，4 l 】。这个方法的缺陷在于，在最小化所 有时钟偏差与其可行域中点的误差的平方和时，有可能出现个别时钟偏差的裕量 接近于零的情况，这显然不利于整体成品率的提高。 为了避免最b - - - 乘问题的缺陷，a l b r e c h t 等【2 8 】和w e i 等【4 2 】分别提出采用最 小平衡算法【2 7 】和增量式的时钟偏差分配算法来最大化所有时序约束的裕量。这 些方法的实质是将电路中的延时建模为一个单一的变量，然后将问题转化为一 个最小均环( m i n i m u mm e a nc y c l e ) 问题【4 3 】来求解。这种方法确保所有的时序约 束都获得可观的裕量，然而其没有考虑到不同路径延时之间在统计行为上潜在 的巨大差异。后来，t s a i 等提出时序约束所需要的裕量与相关路径延时的大小 有关【4 4 4 5 ，将问题描述为最小环比( m i n i m u mc