（计算机应用技术专业论文）vlsi高层次综合中可测性和低功耗设计方法研究.pdf

v l s i 高层次综合中可洲性平低功耗设计方法研究 摘要 半导体技术的飞速发展及v l s i 集成度和时钟频率的不断提高，使得电路 的可测性和功耗问题逐渐成为v l s i 设计首要考虑的因素。当前许多研究表明 高层次设计能够最大程度地实现可测性和功耗的优化，这是因为高层次设计对 具体实现的依赖性很小，对算法和架构的选择自由度高，而算法和架构对最终 硬件实现的可测性和功耗影响显著，能够使最终电路在可测性和功耗方面产生 良好的优化效果。因此，高层次测试综合和高层次低功耗综合设计技术引起了 学术界的广泛关注。本文首先对当前高层次综合及可测性和低功耗设计技术进 行了综述，在此基础上对高层次测试综合和高层次低功耗综合进行深入研究， 通过将高层次综合与可测性设计和低功耗设计相结合，来解决当前集成电路发 展所面临的问题。本文主要工作如下： 1 ) 提出一种基于加权相容图的可测性寄存器分配方法，给出了一个基于 可测性高层次综合准则的相容图边的权值公式，并运用改进的加权团划分算法 对加权相容图进行处理，在寄存器分配过程同时考虑可测性高层次综合的四个 准则，达到了设计电路可测性改善的目标。实验结果表明该方法在可测性方面 的有效性。 2 ) 通过对控制流密集型电路高层次功耗优化问题的分析和研究，提出一 种面向控制流密集型电路的高层次低功耗综合设计方法。该方法首先对控制数 据流图中的控制节点进行调度，在控制节点和其目标传递扇入之间建立控制边， 关闭不必要的操作节点，实现功耗的优化；然后运用基于多电压的功耗优化调 度方法对调度完的控制数据流图进行再调度，最终实现设计电路功耗的最大优 化。该方法不但能够很好地解决控制流密集型电路的功耗优化问题，而且对于 数据流密集型电路也同样适用。实验结果表明该方法具有较好的功耗优化能力 和较低的时间复杂度。 3 ) 通过对当前高层次测试综合和高层次低功耗综合技术的深入研究，将 可测性设计和低功耗设计相结合，提出一种基于遗传算法的高层次可测性和低 功耗综合方法。该方法在时间和面积约束下，通过高层次调度和模块分配，对 可测性和低功耗问题进行研究。利用“加权和形式求得综合反映各个子目标 哈尔滨i ：样人学博十学付论文 要求的单一适应度函数，将多目标优化问题转化为可利用单目标进化算法求解 的等效问题。文中给出了一种可以同时进行高层次调度和模块分配的遗传算法 染色体编码方式，并设计了基于数据依赖的单点杂交算子和基于控制步约束的 变异算子，避免了进化过程中不可行解的产生。实验结果表明该方法在可测性 改善和功耗优化方面的有效性。 关键词：超大规模集成电路；高层次综合：可测性；低功耗；调度；分配 v l s i 高层次综合中可洲性和i 低功耗设计方法研究 皇i i ；宣昌暑号昌宣高；。 - -i -imm- ；i i i ；i i ；i i i i 宣i i ；宣i ；暑i ； a b s t r a c t t h et e s t a b i l i t ya n dp o w e rd i s s i p a t i o no fc i r c u i th a v eb e c o m et h ep r i n c i p a l p r o b l e m si nt h ed e s i g no fv e r yl a r g e s c a l ei n t e g r a t i o n ( v l s i ) d u et ot h er a p i d d e v e l o p m e n to fs e m i c o n d u c t o rt e c h n i q u e a n dt h ec o n s t a n t i m p r o v e m e n t o f i n t e g r a t i o nl e v e la n dc l o c kf r e q u e n c yo fv l s i n o w a d a y s ，m a n ys t u d i e ss h o wt h a t k 曲一l e v e ld e s i g nc a nm a x i m a l l yo p t i m i z et e s t a b i l i t ya n dp o w e rd i s s i p a t i o n a sa r e s u l to fi t sl i t t l ed e p e n d e n c eo ni m p l e m e n t a t i o na n dh i g hf r e e d o mo fa l g o r i t h ma n d a r c h i t e c t u r e i na d d i t i o n ，a l g o r i t h ma n da r c h i t e c t u r eh a v ef lr e m a r k a b l ee f f e c t o i l h a r d w a r et e s t a b i l i t ya n dp o w e rd i s s i p a t i o n , w h i c hc a nm a k es a t i s f y i n go p t i m a l e f f e c t so nt e s t a b i l i t ya n dp o w e rd i s s i p a t i o no ff i n a lc i r c u i t t h e r e f o r e ，h i g h 。l e v e lt e s t s y n t h e s i sa n dh i g h l e v e ll o wp o w e rs y n t h e s i sd r a ww i d ea t t e n t i o no f a c a d e m i cw o r l d t h i sd i s s e r t a t i o np r o v i d e sa nu p t o d a t er e v i e wo fh i g h l e v e ls y n t h e s i s ( h l s ) ， t e s t a b i l i t ya n dl o wp o w e rd e s i g n , o nt h eb a s i so fw h i c had e e p r e s e a r c hi sc a r r i e do u t o nh i g h - l e v e lt e s ts y n t h e s i sa n dh i g h - l e v e ll o wp o w e rs y n t h e s i s t h u s ，t h ep r o b l e m s c u r r e n t l yf a c i n gt h ed 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 tc a nb es o l v e dt h r o u g ht h e c o m b i n a t i o no fh l s ，t e s t a b i l i t ya n dl o wp o w e r t h em a j o rc o n t r i b u t i o n so ft h i s d i s s e r t a t i o na r ea sf o l l o w ： 1 ) ar e g i s t e ra l l o c a t i o nm e t h o df o rt e s t a b i l i t yi sp r o p o s e do nt h e b a s i so f w e i g h t e dc o m p a t i b i l i t yg r a p h aw e i g h t e df o r m u l a o fc o m p a t i b i l i t yg r a p he d g eb a s e d o nt h er u l e so fh i g h - l e v e ls y n t h e s i sf o rt e s t a b i l i t yi sp r o v i d e d ，a n da l li m p r o v e d w e i g h t e dc l i q u ep a r t i t i o na l g o r i t h mi su s e dt od e a lw i t ht h i sw e i g h t e dc o m p a t i b i l i t y g r a p h t h e r e b y f o u rr u l e sf o rt e s t a b i l i t yc a nb ec o n s i d e r e ds i m u l t a n e o u s l yi n t h e p r o c e d u r eo fr e g i s t e ra l l o c a t i o n a n dt h eg o a lo fi m p r o v i n gc i r c u i tt e s t a b i l i t yi s a c h i e v e d e x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so f t h i sm e t h o df o rt e s t a b i l i t y 2 ) ah i g h - l e v e ll o wp o w e rs y n t h e s i sm e t h o df o rc o n t r o lf l o wi n t e n s i v ed e s i g ni s p r o p o s e db a s e do nt h ea n a l y s i sa n dt h es t u d yo fh i g h l e v e lp o w e ro p t i m i z a t i o no f c o n t r o lf l o wi n t e n s i v ed e s i g n t h eo p e r a t i o np r o c e d u r eo ft h i sm e t h o di sa sf o l l o w s ： f i r s ts c h e d u l et h ec o n t r o ln o d e si nc o n t r o ld a t af l o wg r a p h , t h e ne s t a b l i s hc o n t r o l 哈尔滨f ：稃人学博十学何论文 e d g e sb e t w e e nc o n t r o ln o d e sa n dt h et a r g e tt r a n s i t i v ef a n i n s ，s h u td o w nu n n e c e s s a r y o p e r a t en o t e st os a v ep o w e rd i s s i p a t i o n ，n e x tr e s c h e d u l et h es c h e d u l e dc o n t r o ld a t a f l o wg r a p hb yu s i n gp o w e rd i s s i p a t i o no p t i m i z a t i o ns c h e d u l i n gm e t h o db a s e do n m u l t i p l ev o l t a g e st om a x i m i z eo p t i m i z a t i o no f c i r c u i tp o w e rd i s s i p a t i o n t h i sm e t h o d c a nn o to n l yp e r f e c t l ys a t i s f yt h en e e d so fp o w e rd i s s i p a t i o no p t i m i z a t i o ni nc o n t r o l f l o wi n t e n s i v ed e s i g n ，b u ta l s o b es u i t a b l ef o rd a t af l o wi n t e n s i v ed e s i g n e x p e r i m e n t a lr e s u l t sh a v es h o w n i t sh i g hp o w e rd i s s i p a t i o no p t i m i z a t i o nq u a l i t ya n d l o wa l g o r i t h mt i m ec o m p l e x i t y 3 ) a f t e rt h ed e e ps t u d yo fh i g h l e v e lt e s ts y n t h e s i sa n dh i g h - l e v e ll o wp o w e r s y n t h e s i s ，ah i g h 1 e v e lt e s t a b i l i t ya n dl o wp o w e rs y n t h e s i sm e t h o db a s e d o ng e n e t i c a l g o r i t h mi sp r o p o s e d ，w h i c hc o m b i n e st e s t a b i l i t yd e s i g na n dl o wp o w e rd e s i g n u n d e rt i m ea n da r e ac o n s t r a i n t ，t h i sm e t h o ds t u d i e st h et e s t a b i l i t ya n dl o wp o w e rb y w a yo fh i g h 1 e v e ls c h e d u l i n ga n dm o d u l ea l l o c a t i n g t h r o u g hw e i g h t e df o r m ，a s i n g l e f i t n e s sf u n c t i o ni so b t a i n e d , w h i c hc a l lr e f l e c tt h er e q u i r e m e n t so fe a c h s u b o b j e c t i v e t h e r e b y , t h em u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e mc a n b ec o n v e r t e dt o as i n g l eo b j e c t i v ep r o b l e m b e s i d e s ，ac h r o m o s o m ec o d i n go fg e n e t i ca l g o r i t h mi s p r o p o s e d t h a tc a nb e u s e df o rh i g h - l e v e ls c h e d u l i n ga n dm o d u l ea l l o c a t i n g s i m u l t a n e o u s l y , a n do n ep o i n tc r o s s o v e ro p e r a t o rb a s e do nd a t ad e p e n d e n c ea n d m u t a t i o no p e r a t o rb a s e do nc o n t r o ls t e pc o n s t r a i n ta r ed e s i g n e d ，h e n c e ，a v o i d i n gt h e g e n e r a t i o no fi n f e a s i b l es o l u t i o n s t h ee f f i c i e n c yo ft e s t a b i l i t yi m p r o v e m e n ta n d p o w e rd i s s i p a t i o no p t i m i z a t i o no ft h i sm e t h o di s d e m o n s t r a t e db ye x p e r i m e n t a l r e s u l t s k e y w o r d s ：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 ) ；h i g h - l e v e ls y n t h e s i s ；t e s t a b i l i t y ； l o wp o w e r ；s c h e d d i n g ；a l l o c a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担o ，刃1 哆哆 作者( 签字) ：孙私 日期： 上p l 9 年岁月多日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生 在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。 哈尔滨工程大学有权保留并向国家有关部门或机构送交论文 的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容 编入有关数据库进行检索，可采用影印、缩印或扫描等复制手 段保存和汇编本学位论文，可以公布论文的全部内容。同时本 人保证毕业后结合学位论文研究课题再撰写的论文一律注明 作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后 适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：撇 导师( 签字) ：耽睁 日期： 力7 年弓月6 日孟k ( 年弓月6 日 第l 章绪论 1 1 研究背景及意义 第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 ) 设计技术和制造工 艺的飞速发展，使得电子系统的复杂性和系统功能一直呈几何级数增长【l 引。根 据国际半导体协会制订的2 0 0 5 年国际半导体技术路线图及其在2 0 0 6 年的更新， 未来1 5 年集成电路仍将按摩尔定律持续快速发展。预测到2 0 1 0 年，4 5 纳米 c m o s 工艺的高速超大规模集成电路将能量产，高性能c p u 芯片上可集成的 晶体管数目将超过2 0 亿个( 到2 0 1 8 年将超过1 4 0 亿个) ，片上局部时钟频率可 达到1 5 g h z ( 到2 0 1 8 年将超过5 3 g h z ) 。国际半导体协会2 0 0 7 年发布的国际 半导体技术路线图报告 3 1 显示，集成电路集成度不断提高的趋势并没有改变。 如表1 1 所示，在未来的十几年中，集成电路制造工艺的进展并没有放缓。在 随同这一技术蓝图报告发布的长期预测中，到2 0 2 2 年，集成电路的特征尺寸将 达到1 1 纳米。 表1 1 半导体产品的特征尺寸 1 a b i e1 1c h a r a c t e r i s t i cd i m e n s i o no fs e m i c o n d u c t o r s 年份 2 0 0 82 0 1 02 0 1 22 0 1 42 0 1 62 0 l82 0 2 02 0 2 2 d r a m 特征尺 5 74 53 62 82 21 81 4l l 寸( n m ) m p u a s l c 特征 5 9 4 53 62 8 2 2 1 81 41 1 尺寸( n m ) f l a s h 特征 4 53 62 82 31 81 4 l l9 尺寸( n m ) m p u 印刷 3 83 02 41 91 51 297 5 fj 长( n m ) m p u 物理 2 31 8 1 4l l 9 75 64 5 fj 长( n m ) 哈尔滨i ：槲人学博十学f _ f 7 ：论文 国际半导体技术路线图报告将这些复杂性问题归结为两个方面：硅复杂性 和系统复杂性。显然，集成电路制造工艺目前远远不是制约集成电路进一步发 展的第一要素。因而，集成电路设计能力作为影响集成电路发展的一个矛盾焦 点浮出水面。当前，设计中存在的一个小错误将可能造成巨大的经济损失甚至 灾难性后果，这些都是对电路和系统设计者的严峻挑战。另外，由于全球性的 竞争又加剧了产品开发周期的缩短，从逻辑门丌始设计的方法已经远远不能与 这样的竞争环境相适应。显然，采用传统的设计方法已经难以应付当的集成电 路的高速发展，要求传统的芯片设计技术必须做出改变。 目前，集成电路复杂度仍旧以每年5 8 的速度增长( 每1 0 年增长1 0 0 倍) ， 然而集成电路设计能力的增长速度却只有每年2 1 ( 每1 0 年增长7 倍) p j 。这 种制造能力和设计能力之间的差距依旧随着集成电路制造工艺的发展进一步拉 大。集成电路设计能力在延续摩尔定律的神话中的作用也越来越大。在当肓矿集 成电路复杂度条件下，手工设计集成电路已经成为不可能的任务。集成电路辅 助设计工具成为提高集成电路设计能力的关键。在这些因素的共同作用下，对 集成电路辅助设计工具的需求和要求都在飞速提高。而随着集成电路特征尺寸 的进一步减小和电路复杂度的急剧增长，在电子设计自动化( e l e c t r o n i cd e s i g n a u t o m a t i c e d a ) 领域不断涌现出新的问题，如电路的可测性和低功耗问题等 等。越来越多的测试、低功耗和综合优化技术必须在高层次进行，以提高效率。 随着集成电路制造工艺的持续发展，一块集成电路上能够集成的晶体管数 目越来越多，使得集成电路的复杂度不断提高；同时，由于集成电路本身的特 征尺寸也在不断缩小，使得集成度不断提高。上述两个集成电路的发展趋势给 集成电路设计方法提出了新的要求。同益增加的电路复杂度要求人们从更高的 抽象层次开始进行电路设计；而日益提高的集成度使得电路的测试和功耗问题 越来越重要。因此，集成电路制造工艺的持续发展确立了集成电路的三个发展 方向m 】。 首先，由于电路集成复杂度的不断提高，使得低层次综合效率越来越低。 因此，高层次综合( h i g h l e v e ls y n t h e s i s ，h l s ) 技术应运而生。在电子设计自 动化的设计流程中，高层次综合是连接系统行为和系统结构之间的纽带。高层 次综合在算法一级接受系统的行为描述，并将其转换成用功能单元、存储单元 和互连元件( 多路选择器，总线等) 描述的寄存器传输级电路结构，然后经过 2 第1 章绪论 寄存器传输级综合、逻辑综合、划分、布图规划、布局、布线等步骤，最终得 到电路的物理版图。在当前的集成电路设计流程中，仍旧有大量的设计工作是 从寄存器传输级( r e g i s t e rt r a n s f e rl e v e l ，r t l ) 丌始进行的。电路集成复杂度 将会渐渐超出从r t l 级丌始进行电路描述的设计方法的设计能力，从而要求设 计人员必须从更高的抽象层次丌始进行电路设计。有研究表明，在5 千力门的 集成电路设计中，一般需要7 百万行的r t l 代码进行描述。这对人工设计是一 个巨大的挑战 7 】。而从行为级丌始进行电路设计可以大大提高设计人员的设计 表述能力。文献 8 ，9 】中所提供的数据表明，高层次综合可以把电路设计所需要 的源代码量减小1 0 倍。同时，更高的抽象层次意味着更加广阔的优化空间，当 然也意味着更大的计算复杂度。有研究表明，高层次综合阶段对电路功耗有9 0 的优化空间，而这一数字在物理设计阶段则下降到10 。因此，从行为级开始 描述电路成为集成电路设计的必然发展趋势。 其次，随着集成电路集成度的不断提高，测试变得越来越复杂，测试问题 已成为电路设计的一个瓶颈。由于在底层测试代价巨大，因此两种技术也就应 运而生，它们分别是测试综合( s y n t h e s i sf o rt e s t a b i l i t y , s f t ) i lu j 和可测性设 计( d e s i g nf o rt e s t a b i l i t y , d f t ) 1 1 2 1 3 】。测试综合是在综合阶段直接引入可测性 的一种技术，它通过综合过程在原有的功能电路基础上增加可测性。可测性设 计是一些应用于v l s i 设计的规则和方法的集合；是通过在电路中增加一些物 理结构，使得该设计具有“容易被测试”的特性，并使其能够实现高质量的制 造测试的方法总称。这两种技术自从出现以来得到了广泛应用，但这些技术还 不能从根本上解决测试问题。现在可测性设计的研究热点集中在可测性高层次 综合上，试图在电路的高层次综合过程中考虑电路的可测性问题，尽量避免电 路中的不可测结构，从根本上提高电路的可测性。 最后，随着v l s i 集成度和时钟频率的不断提高，电路的功耗问题显得越 来越突出。有时可能因为电路某些部分功耗过大引起温度过高，从而导致系统 工作不稳定或失效。同时，功耗过大也会对封装带来很大的困难。因此，功耗 已经逐渐成为v l s i 设计时首要考虑的因素i 降博】。v l s i 低功耗设计技术覆盖面 广，设计灵活多变，既有系统的整体规划，又有物理的局部考虑。v l s i 低功耗 设计方法随着层次的不同，功耗优化的概率也有很大的差别【l 们。许多研究表明 高层次设计能够最大程度地实现功耗优化，这是因为高层次设计对具体实现的 哈尔滨i ：群人学博十学何论文 依赖性很小，对算法和架构的选择自由度高，而算法和架构对最终硬件实现的 功耗影响显著，能够使最终电路在功耗方面产生良好的优化效果。 1 2 研究现状分析 1 2 1 高层次综合研究现状 高层次综合的研究可以追溯到2 0 世纪6 0 年代1 4 1 。i b m 公司w j w a s t o n 研 究中心开发的a l e r t 系统，将寄存器传输级行为特性的算法描述转换成逻辑 级的结构实现。2 0 世纪7 0 年代，综合技术发展迅速，但主要致力于低层次的 逻辑综合和版图综合，而高层次综合的研究仅限于公司与大学的研究室中，但 却有了较大的发展。2 0 世纪8 0 年代，高层次综合的研究非常活跃，并取得了 大量成果。2 0 世纪9 0 年代，面向可测性、低功耗和s o c 的高层次综合研究兴 起。正如数字系统可以在多个不同的层次上进行详细描述一样，综合也可以在 多个层次上进行。通常，综合可以分为四个层次：系统级综合，高层次综合， 逻辑综合和版图综合。高层次综合技术的应用可以明显地提高设计速度，缩短 设计周期，允许设计者进行设计空间的搜索，寻找最优或满意的设计方案。因 此，高层次综合技术的引入使得集成电路的用户，特别是专用集成电路的用户 ( 可以不是集成电路设计专家) ，可以直接进行数字系统从行为描述到芯片结构 描述的设计工作。 高层次综合中的调度和分配问题一直是学术界关一t l , 的热点。高层次综合中 的许多问题都是n p 问题，求解算法的复杂度是指数级的。而且高层次综合中 需要考虑性能、面积、可测性、功耗以及高层次综合与低层次物理信息结合等 问题。根据当前集成电路的发展趋势，高层次综合在性能和面积约束下同时结 合可测性和低功耗问题将成为今后高层次综合研究中两个必然的发展趋势。因 而，高层次测试综合和高层次低功耗综合成为当今学术界研究的热点。 1 2 2 高层次测试综合研究现状 传统的可测性设计集中在逻辑级和门级，采用测试点插入、部分扫描、边 界扫描和内建自测试( b u i l t i ns e l f - t e s t , b i s t ) 等方法提高设计电路的可测性。 由于逻辑级和门级电路结构固有的不可测结构，导致电路可测性提高困难。高 4 第1 章绪论 i ；宣昌i i i i i ；i ；宣；i 罩昌i 宣i i ；i i i 萱宣i i i i w 7 - i i ；i i ；i i ；宣i i i ；i 置i ；i 宣 层次测试综合( h i g h l e v e lt e s ts y n t h e s i s ，h l t s ) 试图在电路的高层次综合过程 中考虑电路的可测性问题，尽量避免电路的不可测结构，从根本上提高电路的 可测性。高层次测试综合【1 9 2 0 l 是近年来出现的一种新技术，它集中了s f t 和 d f t 的优点，同时还可以对电路的可测性有较大的改善。由于现在电路越来越 复杂，电路的测试越来越困难，在高层次综合过程中考虑可测性可以大大减少 底层测试的复杂度，减少测试过程的硬件资源和设计迭代，提高故障覆盖率。 高层次测试综合技术通过电路设计时的可测性调整，可以弥补高层次测试目前 在故障模型方面本身存在的不足，对底层的测试工作具有较好的效果。 高层次测试综合技术的研究始于2 0 世纪9 0 年代，近年来得到越来越多的 关注。文献 2 1 2 3 对当前高层次测试综合发展现状进行了综述，高层次测试综 合技术可分为两类方法，即基于内建自测试的方法和基于自动测试向量产生 ( a u t o m a t i ct e s tp a t t e mg e n e r a t i o n , a t p g ) 的方法。基于b i s t 的方法假定用伪 随机图形产生器产生测试向量，同时用多输入特征寄存器( m u l t i p l ei n p u t s i g n a t u r er e g i s t e r , m i s r ) 或其他特征分析器来压缩测试响应。由于随机测试对 时序电路并不是最有效的测试方法，因此大多数基于b i s t 的方法同时采用全 扫描测试方法。基于a t p g 的方法假定用确定型测试向量产生器产生测试向量， 为简化测试生成，通常采用部分扫描测试方法。 文献 2 4 2 6 将数据通路中的自循环数量的减少作为解决b i s t 问题的目标。 k i m 在文献 2 6 】中提出了一种新的基于整数线性规划( i n t e g e rl i n e a r p r o g r a m m i n g ，i l p ) 的b i s t 数据通路综合方法，该方法可以同时完成系统寄存 器分配和b i s t 寄存器分配，并且最终生成最优的设计。因此，该方法可以根 据面积和测试时间等不同的约束条件搜索到一系列的设计方案。文献 2 7 】提出 了一种基于遗传算法的并发b i s t 综合和测试调度的方法，使用该方法完成的 功能单元、测试寄存器和多路选择器分配可以实现模块的最大化并发测试。 在文献【2 8 】提出了硬件共享的方法，使用最小数量的扫描寄存器来破坏数 据流图( d a t af l o wg r a p h ，d f g ) 中的循环，生成的电路具有部分扫描需求最小 化特点。这种方法首先对数据通路高层次综合中产生循环的原因进行了分析。 在接下来的调度和分配过程中，通过扫描寄存器共享来避免数据通路中循环的 形成，同时也实现了资源的充分利用。 在文献 2 9 ，3 0 中，将可控制性和可观测性改善在高层次综合阶段进行考 气 哈尔滨：稃人。孚：博十学何论文 虑。文献【2 9 提出了可控制性和可观测性分析技术。该方法采用基于c p a t h s 和 o p a t h s 识别的方法，允许通过一个值来确定任何值和通过一个值来观测故障影 响。在寄存器共享过程中使用费用函数进行引导，该费用函数反映所有输入端 口或输入端口子集可控制的( 输出可观测的) 功能单元的数量。h s u 和p a t e l 在文献1 3 0 】中提出了用来提高数字系统可测性的高层次部分扫描变量选择方 法。一个设计在高层次的可测性通过可控制性和可观测性度量进行评估。因为 可测性分级技术能够使变量子集具有完全的可控制性和可观测性，所以它被用 来度量一个设计可测性的改善。能够引起最大可测性改善的变量被选择，这样 的选择过程增量的进行直到没有进一步的可测性改善可以获得为止。被选择的 变量被放置到实现部分扫描的扫描链中。该方法的综合目标是容易的可测性， 也就是综合的寄存器传输级电路很容易应用测试序列从原始输入激励一个故障 ( 容易的可控制性) ，并且故障影响可以传播到原始输出( 容易的可观测性) 。 所以，该方法至少分配给每个寄存器一个输输出变量来提高寄存器的可控制 性和可观测性。 文献f 3 l ，3 2 提出了添加测试点来测试电路中难测试部分。这些方法都是针 对调度已经完成的数据流图( s c h e d u l e dd a t af l o wg r a p h ，s d f g ) 进行的。 h e r m a n a n i 和s a l i b a 在文献【3 3 】中提出了一种通过自动测试点选择策略来实现 b i s t 寄存器最小化的分配方法。他们使用有效的遗传算法来快速搜索复杂的设 计空间。y a n g 和p e n g 在文献1 3 4 提出了一种集成调度和分配的方法。在此方 法中，数据通路分配是通过考虑可控制性和可观测性来实现的，调度是通过改 变默认调度和提高可测性来实现的。 近年来，国内也有很多研究机构开展高层次测试综合的相关研究。文献【1 0 】 系统阐述了高层次测试综合技术及其发展。文献 3 5 】提出了一种面向电路可测 性的寄存器分配方案。该方案首先从已调度的数据流图着手，建立了一种可用 于高层次综合的行为级可测性分析方法：对算子模块的门级实现进行门级可测 性分析，进而抽象出算子的行为级可控制性和可观测性值。文献【3 6 】提出了一 种基于伪随机可测性方法的寄存器分配算法，来减少b i s t 所带来的硬件歼销。 文献【3 7 】提出了一种基于可测性的寄存器分配方法。文献【3 8 】提出了一种基于易 变性的可测数据通路调度方法。这些研究都是对高层次测试综合方法的有益尝 试。 6 第1 章绪论 i n 1 2 3 高层次低功耗综合研究现状 高层次低功耗综合是另外一项新的高层次综合技术。众所周知，随着设计 层次的不同，v l s i 低功耗设计方法的功耗优化概率也有很大的差别。图1 1 表 示不同设计层次的功耗优化概率，通过该图可以很容易看出层次越高低功耗设 计效果越明显【| 4 】。高层次设计能够最大程度地实现功耗优化，这是因为高层次 设计对具体实现的依赖性很小，对算法和架构的选择自由度高，而算法和架构 对最终硬件实现的可测性和功耗影响显著。随着电路集成度和运算速度的提高， 对于需要减小功耗的设计，逻辑层或物理层的功耗优化已经无法满足要求，需 要高层次设计优化来完成。 系统级 结构级 寄存器传输 逻辑l j 级 电路级 版图级 图1 1 不同层次功耗优化概率 f i g u r e1 1t h ep r o b a b i l i t yo f p o w e ro p t i m i z a t i o no f d i f f e r e n tl e v e l s 高层次低功耗综合方法有很多种。例如，在文献 3 9 】中运用“s h u t d o w n ” 技术，通过提前调度控制单元，来关闭不需要执行的条件分支来降低功耗。文 献【4 0 ，4 1 1 j l 豳过基于条件分支的功耗管理技术，在调度过程中根据条件分支的优 先级有序地选择关闭的分支，达到最大的功耗优化。文献 4 2 1 的方法在时间和 资源约束下，统一调度、绑定和重定时来降低开关活动性，实现功耗的优化。 因为v l s i 中总的功耗主要是由动态功耗【4 3 舶j 来决定的，并且电源的供应 电压和动态功耗成二次平方关系，所以降低供应电压是最有效的降低功耗方法， 于是很多研究通过降低电压的方法来减少功耗。然而，减小供应电压会导致电 7 哈尔滨i ：样人。予：博十学何论文 路延迟的增加和吞吐率的降低。为了解决供应电雎和电路延迟之j 日j 的制约j 、口j 题， 一部分研究者在使用降低供应电压实现功耗优化的同时采用并行和流水线结构 的方法来提高吞吐率1 4 引。还有另外一部分人通过在电路上设置多个大小不同的 供应电压【4 8 】来达到上述目的，即在电路关键路径上为操作分配较高的供应电 压来提高系统速度，而在非关键路径上为操作分配较低供应电压来降低系统功 耗。采用此方法，既降低了功耗，又不会使电路的延迟增加和吞吐率降低。因 此，多电压技术在高层次低功耗综合技术中起到了举足轻重的作用。 近几年来，采用多电压方法减小功耗已成为一种趋势，大多数的高层次多 电压设计方法有着相近的流程，如图1 2 所示的三种不同流程，其差别不大。 该流程重点在调度上，因为它决定了v l s i 设计中速度与硬件费用之间的折衷。 高层次多电压调度主要目的是在保证电路性能的前提下，将不同的电源供应电 压分配给相应操作来降低功耗。 输入d f g 和约束条什 卜 调度 划分 一 分配 图1 2 多电压高层次综合流程图 f i g u r e1 2t h ep r o c e d u r eo fh i g h l e v e ls y n t h e s i sf o rm u l t i p l ev o l t a g e s 目前，国内对基于多电压的高层次低功耗综合设计技术有一些研究，并且 取得了一些研究成果。在文献【4 4 - 4 8 】中，作者提出了一种基于时i 日j 约束条件下 8 第1 章绪论 的调度和绑定算法，在进行高层次调度的同时考虑低层次的分区问题。此算法 采用多电压调度方法来降低功耗，同时利用分区的方法来减小连线的复杂性。 实验结果表明此算法具有较高的功耗优化能力和较低的算法时间复杂度。文献 【4 9 提出了- - 种v l s i 高层综合设计方案。该方案是在时间和资源约束条件下， 综合考虑了调度及互连的多电压方法，从调度互连两个角度达到低功耗的目标。 该方案提出了基于g a i n 大小搜索的调度，将功耗增益、灵活度和操作执行密度 因素作为折中函数，考虑操作的属性更加全面。在互连中基于分布式的r s 互连 模型得出互连单元在执行时段的动态功耗，同时考虑单根总线上的翻转和邻线 的耦合。文献【5 0 】综述了当前高层次综合中面向功耗优化的方法与技术。文献【5 1 提出了一种高层次综合中基于整数线性规划模型的多目标功耗优化算法，同时 对峰值周期功耗和峰值模块功耗进行优化。文献 5 2 5 4 也提出了多种不同的高 层次低功耗综合方法。 国外对基于多电压的高层次低功耗综合设计的研究已经比较深入。目前， 基于多电压调度算法的研究大致可分为基于时间约束【5 5 5 6 】、基于资源约束【5 7 , 5 8 】 和基于时间与资源约束1 5 9 躬】三种。 文献【5 5 】根据每个操作的灵活度和不同供应电压下的延迟关系，尽可能把 较低的供应电压分配给操作，达到降低功耗的目的，同时该算法也具有较低的 时间复杂度。文献【5 6 】提出了种基于资源约束的多电压调度算法，这种算法 力求在控制步数目降低和资源最大化利用方面达到平衡。它是基于列表的调度 算法，优先函数由节点深度、节点灵活性、交换能力和互连线复杂性构成。文 献【5 7 】也提出了一种基于资源约束的多电压调度算法，它的时间复杂度为 o ( n 2 ) 。 文献【6 l 】提出了一种在时间和资源约束条件下，基于整数线性规划算法的 多电压调度方法。文献 6 2 】提出了一种基于整数线性规划算法和一种基于启发 式算法的多电压调度方法。文献【6 2 】提出的启发式调度算法时间复杂度为 o ( n 3l o g n ) 。文献【6 3 】提出了一种新颖的调度方法，通过划分并行操作区域的 方法来降低功耗，同时有效的降低了算法的时间复杂度，它的时间复杂度为 0 ( 疗2 ) 。文献【5 9 】提出了种基于时间和资源约束的多电压调度算法。该算法 首先利用基于资源约束的调度算法来获得最小化的执行时间，然后再利用执行 9 哈尔滨i ：柞人宁：博十学何论文 宣宣；i 置i i ；i ；i i ； 时i 日j 和约束时i 日j 之i 日j 的差值，运用基于拉格朗同乘数法的多电压方法选择降低 供应电压的操作，从而达到功耗最大优化的目标。 通常，在v l s i 高层次低功耗设计中主要考虑的调度方法是基于多电压的单 时钟频率调度方法，而近几年来基于多电压的动念时钟频率岬删j 调度方法也丌 始得到了研究，这是因为通过改变供应电压和时钟频率，不仅能够使系统的功 耗和能耗降低，而且能够获得较高的性能。文献 6 7 1 提出了一种动态时钟频率 下的控制模型，首先分配一个最大的时钟频率无。，然后由动态时钟单元 ( d y n a m i cc l o c k i n gu n i t d t u ) 生成系统中对应不同供应电压下操作的时钟频 率，操作的延迟是d t u 产生时钟频率的倒数。文献 6 7 1 提出了一种启发式的调 度算法，该算法采用多电压和动态频率机制达到低功耗的目标。文献【6 8 】采用 多电压和动态频率机制，分别提出了基于时间约束的调度算法和基于资源约束 的调度算法，这两个算法都能有效地降低功耗和能耗，并且提高系统