（计算机应用技术专业论文）vlsi的高层次综合方法研究.pdf

v l s i 的高层次综合方法研究摘要芯片设计的高速化和复杂化对v l s i 基础理论和设计方法提出了新的挑战。以超深亚微米和纳米工艺及m 核重用为基础的系统芯片是v l s i 的发展趋势。传统的设计方法已经难以应付，出现了许多新的设计技术，如有效的高层次综合技术、验证技术及纳米工艺带来的一系列关键技术等。高层次综合是连接系统行为和结构之间的纽带，它能够缩短设计、布局和验证的时间。高层次综合阶段对电路功耗有巨大的优化空间，而物理设计阶段的功耗优化空间则急剧减少。本文就高层次综合中的调度、分配和多电压低功耗设计等问题展开研究，主要工作如下：1 ) 提出了基于遗传算法与蚂蚁算法相融合的时间约束和资源约束下的高层次调度方法。在充分研究遗传算法和蚂蚁算法独立解决约束条件下的高层次调度问题的基础上，提出了遗传算法的编码方案、交叉算子、变异算子和评估函数及蚂蚁算法的信息素更新规则，并讨论了两个算法之间的动态切换条件。当遗传算法的子代进化率低于事先设定的最小子代进化率或超过最大迭代次数时，结束遗传算法，切换到蚂蚁算法，并由遗传算法得到的优化解产生蚂蚁算法的初始信息素分布。这样避免了蚂蚁算法在初期由于信息素匮乏而做的大量盲目搜索，提高了算法的效率。实验结果表明，与遗传算法和蚂蚁算法相比，本文资源约束的调度方法能明显减少调度长度，本文时间约束的调度方法能明显减少所用资源总数目。2 ) 在充分研究复杂高层次数据流特性的基础上，提出一种适合高层次复杂数据流分解和设计空间搜索的多项式新模型k * t d g 。首先根据复杂数据流多项式中各参数之间的关系，对1 d g 中的边权值重新进行定义。然后讨论了k t d g 模型的两种基本运算：加法和乘法。k * t d g 模型充分利用了t d g 模型的思想，克服了t d g 模型的缺点。在此基础上，借助子m a p l e 中的s i m p l i f y函数和f a c t o r 函数，提出复杂数据流分解匹配算法。在此过程中定义关于面积和关键路径时延的代价函数，使上述过程始终向代价函数更优的方向进行。为了进一步降低算法复杂度，还提出了根据复杂元件多项式次数进行分组的策略，使每次搜索时的空间由整个设计空间变成与k * t d g 中分支次数相等的元件组哈尔滨工程大学博士学位论文l 葺i ；宣；i i 暑；暑i 暑成的局部空间。实验结果表明，在保持面积和延迟近优的前提下，本文方法能明显缩小设计空间。3 ) 提出了基于网络流的多电压高层次低功耗设计方法。定义了一种新的系统功耗模型，同时考虑了功能单元功耗、互连功耗和电压转换功耗。首先进行单电压高层次综合，然后迭代地对单电压高层次综合结果进行局部多电压调度和分配调整。只有当某个操作与其前驱节点或后继节点有分配到同一电压簇器件的可能时，才执行该调整。提取每次迭代时需要调整的网络流子图，对该子图运行最小费用最大流增量算法。该方法充分利用前面迭代中得到的优化解，避免了对整个网络流的重复计算，节省了大量时间。最后，在讨论电路拓扑结构的基础上提出了一种门控填充值算法，能进一步减少电路设计中的伪开关跳变功耗。实验结果表明，本文方法对电路的互连功耗，电平转换功耗和总功耗均有明显的优化。关键词：超大规模集成电路；高层次综合；低功耗设计；调度；分配v l s i 的高层次综合方法研究a b s t r a c tt h eh i g h s p e e da n dc o m p l e x i t yo fc h i pd e s i g np u tf o r w a r dn e wc h a l l e n g e st ot h ef u n d a m e n t a lt h e o r i e sa n dd e s i g nm e t h o d so fv l s i ( v e r yl a r g es c a l ei n t e g r a t i o n ) s o c ( s y s t e mo nc h i p ) ，b a s e do nt h et e c h n o l o g yo fv d s m ( v e r yd e e ps u b m i c r o n ) ，n a n o m e t e ra n di p ( i n t e l l i g e n tp r o p e r t y ) c o r er e u s e ，i st h em a i nd e v e l o p m e n tt r e n do fv l s i h o w e v e ri ti sd i f f i c u l tf o rt r a d i t i o n a ld e s i g nm e t h o d st oh a n d l es u c hp r o b l e m s t h e r e f o r em a n yn e wd e s i g nt e c h n i q u e sh a v ee m e r g e d ，s u c ha se f f i c i e n th i g hl e v e ls y n t h e s i s ，v e r i f i c a t i o nt e c h n o l o g ya n ds e r i e so fk e yt e c h n o l o g i e sb r o u g h ta b o u tb yn a n o m e t e rt e c h n o l o g y a m o n gt h e m , h i g hl e v e ls y n t h e s i s ( h l s ) b r i d g e ss y s t e mb e h a v i o r sa n ds y s t e ma r c h i t e c t u r e s 。h l sc a l ls h o r t e nt i m eo fd e s i g n , l a y o u ta n dv e r i f i c a t i o n t h e r ei sh u g eo p t i m i z a t i o ns p a c eo fp o w e rd i s s i p a t i o na tt h es t a g eo fh l s ；h o w e v e rt h eo p t i m i z a t i o ns p a c eo fp o w e rd i s s i p a t i o ni ss m a l l e ra tt h es t a g eo fp h y s i c a ld e s i g n s c h e d u l i n g ，a l l o c a t i o na n dm u l t i - v o l t a g e sl o wp o w e rd e s i g no fi l l sa l es t u d i e di nt h i sp a p e r t h em a j o rc o n t r i b u t i o n sa r ea sf o l l o w s ：1 ) t h eh i g hl e v e ls c h e d u l i n gm e t h o d sb a s e do nt h ec o m b i n a t i o no fg e n e t i ca l g o r i t h ma n da n ta l g o r i t h mw i ml a t e n c yc o n s t r a i n t sa n dr e s o u r c ec o n s t r a i n t sa l ep r o p o s e d a r e ra na b u n d a n ti n v e s t i g a t i o no ft h ec a p a b i l i t i e so fg e n e t i ca l g o r i t h ma n da n ta l g o r i t h mt os o l v eh i g hl e v e ls c h e d u l i n gi n d e p e n d e n t l y , t h ec o d i n gs c h e m e ，c r o s s t a l ko p e r a t o r , m u t a t i o no p e r a t o r , e v o l u t i o nf u n c t i o no fg e n e t i ca l g o r i t h ma n dt h ep h e r o m o n eu p d a t i n gr u l e so fa n ta l g o r i t h ma r ep r e s e n t e d a n dt h ed y n a m i cs w i t c h i n gc o n d i t i o n so fg e n e t i ca l g o r i t h ma n da n ta l g o r i t h ma r ea l s oe x p l o r e d ：w h e nt h es u b - g e n e r a t i o ne v o l u t i o nr a t i oi sl e s st h a nt h em i ns u b - g e n e r a t i o ne v o l u t i o nr a t i os e tb e f o r e h a n do rt h ei t e r a t i o nt i m e se x c e e dt h eg i v e nm a x i m u mi t e r a t i o nt i m e so fg e n e t i ca l g o r i t h m , g e n e t i ca l g o r i t h mt e r m i n a t e sa n ds w i t c h e st oa n ta l g o r i t h m t h ei n i t i a lp h e r o m o n ed i s t r i b u t i o no fa n ta l g o d t h r ac a nb eg e n e r a t e db yt h eo p t i m i z a t i o n a ls o l u t i o n so fg e n e t i ca l g o r i t h m ，t h u sm a n yb l i n ds e a r c h e si nt h ee a r l ys t a g eo fa n ta l g o r i t h mf o rd e f i c i e n c yo fp h e r o m o n ec a r tb ea v o i d e d , a n dt h ea l g o r i t h me f f i c i e n c yc a i la l s ob ei m p r o v e dg r e a t l y e x p e r i m e n t a lr e s u l t si n d i c a t et h a t ，t h e哈尔溟工程大学博士学位论文i e s o u l v 七c o n s t r a i n e ds c h e d u l i n gm e t h o di nt h i sp a p e rc a nr e d u c es c h e d u l i n gl e n g t ha n dt h el a t e n c yc o n s t r a i n e ds c h e d u l i n gm e t h o di nt h i sp a p e rc a nr e d u c et h et o t a lr e s o u l v 七n u m b e r s ，c o m p a r e d 淅吐lg e n e t i ca l g o r i t h ma n da n ta l g o r i t h m 2 ) an e wp o l y n o m i a lm o d e lk 木t d gi sp r e s e n t e da f t e ra ni n t e n s i v es t u d yo nt h ec h a r a c t e r i s t i co fc o m p l e xh i 曲l e v e ld a t af l o w ，w h i c hi ss u i t a b l ef o rc o m p l e xh i 出l e v e ld a t af l o wd e c o m p o s i t i o na n dd e s i g ns p a c ee x p l o r a t i o n f i r s t ，t h ea r cw e i g h t so ft d ga r er e d e f i n e da c c o r d i n gt ot h er e l a t i o n s h i pb e t w e e nt h ep a r a m e t e r so fc o m p l e xd a t af l o wp o l y n o m i a l t h e nt w ob a s i co p e r a t i o n so fk 幸t d ga r ed i s c m s e d ：a d d i t i o na n dm u l t i p l i c a t i o n n l en e wm o d e lk 宰t d gm a k e st h eb e s to fm o d e lt d gf u l l y , a n do v e r c o m e st h ed i s a d v a n t a g e so ft d g 弱w e l l o nt h i sb a s i s ，ac o m p l e xd a t af l o wd e c o m p o s i t i o nm e t h o di sp r o p o s e db ya p p l y i n gt h es i m p l i f yf u n c t i o na n df a c t o rf u n c t i o ni nm a p l e ac o s tf u n c t i o nr e g a r d i n ga r e aa n dc r i t i c a lp a t hd e l a yi sd e f i n e di nt h i sp r o c e s si no r d e rt om o v et h ed e c o m p o s i t i o nt oam o r eo p t i m a ld i r e c t i o n i no r d e rt or e d u c et h ea l g o r i t h mc o m p l e x i t yf u r t h e r , ag r o u p i n gs t r a t e g yb a s e do nt h ed e g r e e so fc o m p o n e n tp o l y n o m i a l si sp r o p o s e d 1 1 1 es e a r c hs p a c ei st r a n s f o r m e df r o mt h ew h o l es p a c ei n t ot h el o c a lo n et h a ts h a r et h es a m ed e g r e ew i t ht h ek 七t d gb r a n c hi ne a c hi t e r a t i o n e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h em e t h o di nt h i sp a p e rc a l lr e d u c es e a r c hs p a c eg r e a t l yo nt h ep r e c o n d i t i o no fk e e p i n ga r e aa n dd e l a y i n ga p p r o x i m a t eo p _ t i n u a 3 ) al l i g hl e v e ll o wp o w e rm u l t i v o l t a g e sd e s i g nm e t h o db a s e do nn e t w o r kf l o wi sd e v e l o p e d an e ws y s t e mp o w e rd i s s i p a t i o nm o d e li sd e f i n e d ，i nw h i c hf u n c t i o nu n i tp o w e r , i n t c r c o n n e c t i o np o w e ra n dv o l t a g e sc o n v e r t i n gp o w e ra l et a k e ni n t oc o n s i d e r a t i o n s i n g l ev o l t a g eh i 曲l e v e ls y n t h e s i sm e t h o d sr u nf i r s t , a n dt h e nm u l t i v o l t a g e sl o c a la d j u s t m e n t sa r ed o n ei t e r a t i v e l yo nt h es i n g l ev o l t a g eh i g hl e v e ls y n t h e s i sr e s u l t s o n l yw h e no n eo p e r a t i o nn o d ec a nb ea l l o c a t e dt ot h ec o m p o n e n tw h i c hh a st h es a m ev o l t a g ec l u s t e rw i t i li t sp r e 们o u so p e r a t i o nn o d e so rs u c c e s s o ro p e r a t i o nn o d e s ，c a nt h ea d j u s t m e n tb ee x e c u t e d i nt h ef o l l o w i n g ，t h en e t w o r kf l o ws u b - g r a p hn e e d e dt oa d j u s ti se x t r a c t e df r o mt h ep r e v i o u sn e t w o r kf l o wg r a p ha n dt h em i n - c o s tm a x f l o wi n c r e m e n t a la l g o r i t h mi sr u no ni ta tl a s t , t h et o p o l o g ys t r u c t u r eu s e di nt h i sp a p e ri sd i s c u s s e d ag a t e df i l l e rv a l u ec o m p u t a t i o na l g o r i t h mv l s i 的高层次综合方法研究i sp r o p o s e da tl a s tt of u l t h g rr e d u c et h ep o w e rd i s s i p a t i o no fs p u r i o u ss w i t c h i n ga c t i v i t y e x p e r i m e n t a lr e s u l t si n d i c a t em a lt h ei n t e r c o n n e c t i o np o w e r ，v o l t a g ec o n v e r t i n gp o w e ra n dt o t a lp o w e rc a l lb eo p t i m i z e dg r e a t l yb yu s i n gt h em 幽d s k e y w o r d s ：v l s i ；h j l 曲l e v e ls y n t h e s i s ；l o wp o w e rd e s i g n ；s c h e d u l i n g ；a l l o c a t i o n哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体己经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者( 签字) ：，砻乞州趸日期：砖年胡f 妒第1 章绪论i l l第1 章绪论1 1 课题的研究背景和意义随着半导体工艺的迅猛发展，集成电路的规模日益增大，特征尺寸不断减小，复杂性迅速增加。目前，量产芯片的特征尺寸已降到6 5 n m ，实验室最新工艺水平已到3 2 n m 。文献 2 预测，到2 0 1 0 年4 5 n mc m o s ( c o m p l e m e n t a r ym e t a l o x i d e s e m i c o n d u c t o r ) 工艺的高速超大规模集成电路( 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 ) 将能量产，单个芯片能集成数十亿个晶体管，时钟频率将达到1 0 - 2 0 g h z 。集成电路的发展趋势表明，芯片正由集成电路向集成系统的方向转变。以超深亚微米( v e r yd e e ps u b m i c r o n , v d s m ) 和纳米工艺及知识产权( i n t e l e g e n tp r o p e r t y , i p ) 核重用技术为基础的半导体集成化系统芯片( s y s t e mo nc h i p ，s o c ) 是v l s i 的发展趋势。系统芯片具有开放性、可演化性和普适性的特点。长时间以来，芯片复杂度的增长超过了设计能力的增长，芯片的制造能力超过了芯片的设计能力。为了充分发挥巨额投资的集成电路生产线的能力，需要更多的设计者及时提供大量的复杂集成电路设计模块。另外，计算机技术和通讯技术的高速发展，使得数字系统渗透到社会的各个领域，传统的设计方法已难以应付。近十年，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 ) 技术也取得了巨大进步。这些进步不仅表现在工程应用的深广程度上，重要的是正在逐步形成具有前瞻性的设计思想和集成方法学，并出现了许多新的技术和研究方向，如有效的高层次综合( h i g hl e v e ls y n t h e s i s ，i l l s ) 技术、验证技术及v d s m 工艺和纳米工艺所带来的一系列关键技术等。集成电路设计包括许多层次，不同层次中的电路可表示成不同的抽象模型，例如概念级、算法行为级、寄存器传输级( r e g i s t e rt r a n s f e rl e v e l ，r t l ) 、逻辑门级、版图级等。集成电路的设计流程实际上是一个对设计模型逐步“精化 的过程。设计的最初阶段主要是做需求分析，来确定芯片应该具有的功能，这个过程需要用户和设计人员合作完成，称之为概念设计。芯片设计人员接下来将这种非形式化的概念设计转换成形式化的设计规范( s p e c i f i c a t i o n ) ，可以哈尔滨工程大学博士学位论文i m mi用各种形式语言来描述。然后根据设计规范在r t l 级进行系统功能设计，一般用硬件描述语言( v h d l 或v e r i l o g ) 对各功能块及它们之间的相互关系进行描述。利用综合工具将r t l 级模型转换成门级网表，再进行物理设计得到晶体管级版图，最后进行掩膜，制造出芯片的硅片装。高层次综合是连接系统行为和系统结构之间的纽带，它将算法行为级描述转换成用功能单元、存储单元和互连单元组成的电路结构级描述。在当前的设计流程中，仍有大量的设计工作是从r t l 开始的，但集成电路的设计复杂性正在超过现有的r t l 方法的能力 3 1 。在5 0 0 0 万门设计中，一般需要7 0 0 万行的r t l 代码，这是对人工设计的一个巨大的挑战。文献【3 】中所提供的数据表明，高层次综合可以把电路设计所需要的源代码量减少1 0 倍，高层次综合阶段对电路互联功耗有9 0 的优化空间，而这一数字在物理设计阶段则下降到10 。高层次综合和设计重用能够缩短设计、布局和验证的时间。高层次综合中约束条件下的调度、分配和多电压低功耗设计等问题是当前学术界关心的热点，虽然有很多国内外学者致力于这些方面的研究，但这些问题一直没有得到圆满解决。本课题正是在这样的背景下提出，并得到国家自然科学基金项目资助( 国家自然科学基金项目编号和名称：6 0 2 7 3 0 8 1 基于多项式符号代数的系统芯片d a新方法研究) 。1 2v l $ i 的发展美国物理学家巴丁等人在1 9 4 8 年发明了世界上第一个晶体管。1 9 5 8 年，美国科学家在一块硅片上做成了相移振荡器，该振荡器元件之间的连线不再是传统的导线，而是用了很薄的刻蚀获得的金属条，这就是世界上第一块集成电路。1 9 6 7 年诞生了单片集成度在1 0 0 0 个晶体管以上的集成电路，标志着集成电路由中小规模进入大规模时期。2 0 世纪7 0 年代以来，由于c m o s 工艺的发展，尤其是高密度短沟道c m o s 技术的发展，使得c m o s 器件不仅具有很高的集成度，而且器件的工作速度达到甚至超过了1 凡电路的性能。1 9 7 7 年，美国科学家在3 0 m m 2 的硅片上集成了1 3 万个晶体管，制作出了世界上第一块6 4 k b 的d r a m ，标志着集成电路跨入了v l s i 时代。2 0 世纪8 0 年代，集成电路特征尺度是微米级；9 0 代以来，集成电路工艺发展非常迅速，从亚微米( o 5p a n 一1i x m ) 和深亚微米( o 5 1 , t m ) 进入到超深亚微米( 0 2 5 1 m a ) 和纳2第1 章绪论；暑宣暑宣i ；i ；i ；i ；宣；i - - - - -ii i i i i 昌宣暑；暑i j 宣昌宣暑昌宣宣暑；i i i i i i i i米( s ：= 工 3 + 3 x 2 y + x 2 + 3 + x y 2 + 2 x 幸y + 2 卡x 2 木z + y 3 + y 3 +y 2 + 2 y 2 z + 2 y z + z 2 i + z 2 y + z 2 e o n v e r t ( s ， h o m e r ，i x ，y ，z 】)z 2 + ( ( 2 + z ) z 4 - ( 2 z + 1 + y ) y ) 宰j ，+ ( ( 2 + z ) 幸z+ ( 2 + 4 z + 3 y ) 掌y + ( 2 z + l + 3 士y + x ) 幸x ) x6 0第4 章高层次分配模型及方法】，口宰6奉c+d( a )f xyab木c+dd+e木厂( c )图4 6 利用替换和树高度缩减技术最大化并行操作f i g u r e4 6s u b s t i t u t i o na n dt h rc a l lm a x i m i z ep a r a l l e l i s m6 l哈尔滨工程大学博七学位论文4 ) 替换与消除替换是指将一个子表达式替换为另外一个前面未出现的变量，它可以降低原表达式的复杂度。这种变换可能会消除原表达式之间的相互依赖关系，而在变换后的表达式之间建立新的相互依赖关系。替换可以应用于多级组合逻辑优化【1 2 2 - 1 2 3 1 。文献 1 2 4 提出了基于g r s b n e r 基的多变量多项式替换和变量消除的形式化方法组合逻辑综合中不仅可以采用代数分解模型，可以采用更多其它分解模型。例如布尔多项式分解中的有些运算规律在算术多项式中不成立，因为算术多项式中有指数运算，而布尔多项式不支持指数运算。为了使表达式能最大并行化，替换技术和t h r 技术可以结合使用。例如对下面两个电路模块表达式：x = a b c + dy = x + e 厂y 是依赖于x 的，因此y 要等x 计算出来后才能进行计算，如图9 ( a ) 所示。如果在】，中消除x ，则y = a c + d + e f ，于是x 和】，可以并行计算。图9 是对x 和y 采用t h r 之后的结果。为了使x 和y 能最大并行化，可以用一个新变量z 替换子表达式口b c ，结果如图9 ( c ) 所示。表4 1 基准电路的面积、时延及其标准值t a b l e4 1t h ea r e a , d e l a ya n dt h e i rn o r m a l i z e dv a l u e so f b e n c h m a r k s元件时延( 璐)标准时延面积( u m 2 )标准面积加法器7 5 411 5 0 9 01平方器7 8 91 0 58 9 8 1 45 9 5乘法器l o 1 71 3 51 3 3 4 0 l8 8 4s i n e4 5 2 166 2 5 2 1 84 1 4 3c o s i n e4 5 3 76 0 26 2 2 8 4 94 1 2 84 6 实验结果与分析实验中使用的元件有加法器、平方器、乘法器、s i n x 函数和c o s x 函数等，它们是s y n o p s y s 公司硬件设计库中的部分元件，相关测试数据如表4 1 所示。这些数据是使用s y n o p s y s 公司d e s i g nc o m p i l e r 工具对于1 6 位的加法器和1 6 位的乘法器测试得到的。实验时首先将这些元件按其多项式表示的次数进行分组，第4 章高层次分配模型及方法分组的结果与第4 部分的结果类似，不同之处就是在s u b s e t ( 2 ) 中去掉最后两个元件。待匹配的基准电路多项式如表4 2 所示，所用到的策略用c + + 语言实现。利用文献 1 0 3 1 中t d g 模型及方法测得的实验数据如表4 3 所示，利用本章提出的k 木g 模型和方法测得的实验数据如表4 4 所示。表4 3 和表4 4 中的第三列是实现相应的基准电路数据流多项式所需要的标准化面积；第四列是关键路径时延；最后一列是最坏情况下的搜索次数。实验数据表明，在保持面积和时延近优的方情况下( 跟文献 1 0 3 1 中方法相比面积减少了1 7 ，时延增加了1 8 ，即面积稍小、时延稍大) ，利用本章中提出算法和策略，在最坏情况下的搜索空间平均减少了4 9 。表4 2 基准电路多项式t a b l e4 1p o l y n o m i a l so f b e n c h m a r k s基准电路多项式p 1a 2 一b 2挖b 3 + b a 2 cp 31 一_ 2i 2 4l 口+ 曲p 4a 4 一b 4尸5x 5 + x 3 + x + l表4 3 文献 1 0 3 q u 的模型及方法测得的实验数据t a b l e4 3e x p e r i m e n t a lr e s u l t su s i n gm o d e la n dm e t h o di n 10 3 】多项式元件个数标准化面积关键路径时延最坏搜索次数p 131 0 8 42 3 52 6p 253 0 5 84 7 52 5p 345 2 1 27 0 21 9p 452 4 83 14 2p 562 6 6 35 7 52 4t o t a l2 31 4 4 9 72 2 9 71 3 6哈尔滨工程大学博十学位论文表4 4 本章方法测得的实验数据t a b l e4 4e x p e r i m e n t a lr e s u l t su s i n gt h em e t h o di nt h i sp a p e r多项式元件个数标准化面积关键路径时延最坏搜索次数p 13l o 8 42 3 51 4 p 253 0 5 84 7 51 6p 345 2 1 27 0 29p 432 2 7 43 41 7p 562 6 6 35 7 51 3t o t a l2 l1 4 2 5 52 3 3 76 94 7 本章小结本章提出了一种新的多项式模型k * t d g ，讨论了k * t d g 的紧密性和松散分支的相关概念，并研究了其基本的加法运算规则和乘法运算规则。在此基础上提出了一种复杂数据流的分解和匹配算法。为了降低算法的复杂度，还给出了一种根据复杂元件多项式次数分组的策略。根据本章提出的方法和策略，能把一个全局元件搜索问题转换为满足条件的局部元件搜索问题，并保持分解匹配向着面积和时延总体更优的方向进行。实验数据表明本章方法能明显减少设计搜索空间。第5 章多电压低功耗高层次综合方法第5 章多电压低功耗高层次综合方法5 1 引言随着半导体制造工艺的发展，目前单个芯片上可集成的晶体管数目达1 0亿个左右，超深亚微米时代和纳米时代已经到来【1 1 。纳米制造工艺所引入的物理互连寄生效应成为电路的主要功耗。功耗增加引起的芯片温度升高将引发电迁移、热载流子等一系列问题，而且芯片温度每升高1 0 度，电路故障将增加一倍左右。低功耗问题已变得比芯片面积和处理速度更重要，成为制约v l s i 进一步发展的瓶颈。v l s i 有不同描述层次：系统级描述、行为级描述、寄存器传输级描述、门级描述和版图级描述等。其中，高层次综合是连接行为级描述和r t l 结构描述的纽带。在当前v l s i 设计中，仍有大量工作是从r t l 开始的。但芯片的复杂度已超过现有r t l 方法的设计能力 3 1 ，正向更高的设计层次迈进。文献 3 】中的数据表明，高层次综合对电路功耗有9 0 优化空间，而在版图设计阶段则下降到1 0 。因此，高层次综合中的低功耗设计己引起越来越多研究者的重视。早期的高层次综合低功耗研究往往忽略互连线的影响。随着半导体特征尺寸的减小，许多研究者开始考虑高层次综合时的互连功耗。文献 1 2 5 提出通过保持行为的局部性和规则性优化总线功耗的方法，但行为的局部性和规则性并不能保证最终物理设计的局部性和规则性。文献【5 6 】描述了数据流图的开关跳变特性，并把它与布图规划工具结合优化模块内部数据传输，但这种方法仅考虑了互连线的自跳变功耗，没有考虑耦合功耗。近几年，低功耗研究的重点逐渐转移到多电压设计。文献 1 2 利用整数线性规划方法同时优化峰值周期功耗、峰值模块功耗及功耗时延乘积，取得不错的效果。文献【6 5 】提出两个复杂性不同的算法优化多电压低功耗问题。文献 1 2 6 】提出利用动态规划方法优化多电压低功耗问题。上述多电压低功耗设计方法存在的如下问题：1 ) 文献【1 2 】主要考虑了功能单元功耗，文献 6 5 主要考虑了功能单元功耗和低电平到高电平的转换功耗，文献 1 2 6 主要考虑功能单元功耗和不同电平之间的转换功耗，他们均没有同时考虑功能单元功耗、互连功耗和不6 5哈尔滨工程大学博士学位论文同电压信号之间的转换功耗。2 ) 他们均未考虑高层次综合与后续设计的联系，这可能导致复杂的布局布线问题。例如，不同电压的连续操作节点在物理布局中离得很近，导致复杂的布线结果，而且增加了不同电压信号之间的转换功耗。针对上述问题，本章提出了基于网络流的高层次多电压低功耗设计方法，对上述缺陷进行改进。本章方法的特点包括：1 ) 提出了一种新的系统功耗模型，同时考虑了功能单元功耗、互连单线跳变功耗、互连耦合跳变功耗和电平转换功耗。以此模型计算的总功耗为基础，定义了网络流的代价。2 ) 利用电压簇的思想，充分考虑了每个操作节点与其前驱节点或后继节点的电压一致性问题，有效的减少了不同电平之间的转换功耗。3 ) 每次迭代时，只需要提取需要多电压调整的网络流子图，对其运行最小费用最大流增量算法，避免了整个网络流的重复计算，节省了大量的时间，提高了算法效率。5 2 相关知识假设一个数据流图d f g 所有节点对应的操作集合为d = q ，0 2 ，q ) ，玎为d f g 中的节点数目。电路设计用到的功能单元有两类：加法器和乘法器，它们可工作在5 v ( 3 3 v ，2 4 v ，1 5 v ) 电压下。加法器集a d d = 鸣，鸣，4 ，a i ) ，其中鸣鸲，鸣，4 ) 分别表示工作电压为5 v ( 3 3 v ，2 4 v ，1 5 v ) 的加法器子集：乘法器集合m v t = m s ，坞，鸩，m l ，其中眠，m 2 ，m i ) 分别表示工作电压为5 v ( 3 3 v ，2 4 v ，1 5 v ) 的乘法器子集。工作在5 v ( 3 3 v ，2 4 v ，1 5 v ) 电压下的所有器件集合组成电压簇d “5 ( c l u 3 ，c ，“2 ，d ) ，如图5 1 所示。器件有两个属性：功能类别和电压簇。功能类别表示器件完成的功能，如加法或乘法；电压簇表明了器件正常工作时的电压。每个器件都有唯一功能类别和电压簇。肋d = ( b ；矧，i a 2 1 ，；a l ；) ； iii；m u l = 弛；蟛，鲍，幽)c l u 5d u 3c l u 2d u l图5 1 电压分簇示意图f i g u r e5 1d i a g r a mo fv o l t a g ec l u s t e r s操作d l 的高层次综合结果可记为( d l ，c s t e p i ，d e v i c e l ) ，其中q 0 ，c s t e p l表示操作0 1 被调度到的控制步，比v 4u m ，( 卢l ，2 ，3 ，4 ) ，表示操作0 1 绑第5 苹多电压低功耗高层次综合方法定到的器件。所有( 0 j ，c s t e p j ，d e v i c e f ) ( 1 i n ) 构成高层次综合解。本章算法中用到的相关定义如下。定义5 1 ( 自由度) ：操作q 的自由度4 如式( 5 j ) 所示：d ；：c ，“尸一c ，跚( 5 1 )其中，c ，“p 是指单( 最高) 电压a l a p 调度中操作0 ：被调度到的最迟控制步，c ，翻尸是指单( 最高) 电压a s a p 调度中操作q 被调度到的最早控制步。定义5 2 ( m o v e ) ：如果一个操作d j 被调度到的控制步c s t e p ，或绑定到的器件d e v i c e i 发生改变，则称操作d 发生了一次m o v e 。定义5 3 ( m o v e a b l e 操作) ：如果把操作o k 由控制步f 调度到另外一个控制步f 或把操作q 绑定到不同的器件，仍满足时间约束条件和资源约束条件，则称q 为m o v e a b l e 操作。定义5 4 ( 容量网络) 1 2 7 】：给定一个有n 匿t c ( v ，a ) ，其中彳为弧集，v 为节点集，包含一个发点s 和一个收点t 。s 是数据流图中唯一没有先驱的节点，t 是数据流图中唯一没有后继的节点，它们均不表示任何操作。对于v ( v j ，v ，) a ，都存在一个容量c ( v ，v ，) 0 ( 简记为q ，) ，则称d = ( v ，a ，c ) 为容量网络。定义5 5 ( 最大流问题) 1 2 7 1 ：f = 厂( ，) ) 是定义在弧集合上的一个函数，则称f ( v t ，v ，) 为弧( 叶，1 ，) _ k n n 量( 简记为z ，) 。若满足下列条件：1 ) 对v ( u ，v ，) a ，有0 z f c i ，；2 ) 对弧v k ，h ) ，有乃一厶= o( v i ，v j k _q j v i ) c a厶一厶= v ( 厂)( b ，) 爿( ，如) e 爿( 5 2 )( 5 - 3 )乃一f j t = - k f ) ( 5 - 4 )( v t ，v ) c a( ，v f ) 一即中间节点的流出量等于流入量，如式( 5 - 2 ) 所示，发点的流出量等于收点的流入量，如式( 5 3 ) 和( 5 - 4 ) 所示，则厂称为可行流。最大流问题就是求一个可行流厂，使流量v ( f ) 取最大值。定义5 6 ( 最小费用最大流问题) 1 2 7 】：容量网络d = ( v ，a ，c ) 中，每一弧6 7“，) 上除给定容量q ，外，还给出一个单位流量的费用6 ( u ，) ，简记为岛。最小费用最大流问题就是求一个最大流厂，使得网络流的总费用b ( f ) ( 如式( 5 5 ) 所示) 取值最小。6 ( 厂) = 乃( 5 5 )( 叶，v j ) g a定义5 7 ( 剩余图) 【1 冽：在容量网络d = ( v ，a ，c ) 中，若a + o c ) 。 ( m ，巧) l ( v f ，v j ) 彳，乃 0 )则a + n 彳一( 厂) = ，记彳( 厂削+ u a 一( 厂) ，对v ( h ，) 彳( 力，令c 。l ，、= 气i ? 甚! l ：弋三：! ：疋则称勺为弧( _ ，0 ) 关于厂的剩余容量，称d ( 厂) = ( y ，彳( ) ，q ) 为d 关于厂的剩余图。5 3 系统功耗模型多电压系统芯片的功耗主要包括各功能单元功耗、互连功耗和不同电压信号之间的转换功耗等。互连功耗主要是由互连线自身电容和耦合电容的充放电引起的。r 个控制步内互连线f 的互连功耗( f ) 可以用式( 5 - 6 ) 表示：p i n t ( f ) = 岛( f ) + 尼7 ( f )( 5 6 )其中，岛( ，) 表示互连线f 的自跳变功耗，可通过式( 5 - 7 ) 计算：岛