（计算机软件与理论专业论文）同步时序电路中的重定时算法研究.pdf

哈尔滨i ：程人学硕+ 学位论文 摘要 随著集成电路规模的扩大及其应用的推广追切需要缩短没计时 l 铷，降低设计难度。高层次综合( h l s ) 系统就起着这样的作用。但是 由于综合器综合得到的电路网表不一定能达到设计者的设计要求， 所以需针对给定的速度要求，对综合得到的时序电路进行速度优化。 优化的方法大致可分为两类：( 1 】组合优化方法，即将组合电路的优 化方法直接用于时序电路。( 2 ) 重定时，重定时在保证功能不变的前 提下，通过移动时序元件的位置和改变时序元件的个数束优化同步 时序电路的速度、面积和功耗。 l e is e f s o n 和s a x e 于1 9 8 3 年提出了利用重定时优化同步时序电 路，并于1 9 9 1 年对重定时优化算法做了全面的总结。近年来，重定 时技术被应用于电子设计自动化的各个领域中。遗憾的是，以自d 提 出的重定时算法不能很好地与组合优化方法结合起束。而实际的电 路优化系统应该将重定时算法与其它组合优化方法结合在一个优化 流中。充分发挥二者的优势。本文提出一种新的重定时算法，可以 与其它组合优化算法很好地结合。 当给定设定的时序约束条件，知目标时钟周期时，利用重定时优 化可以消除时序冲突，我们称此重定时优化方法为时序调整策略。 有效重定时的判定算法是重定时优化豹关键，因此也是时序调整策 略的关键。在时序调整策略中，有效重定时的判定算法主要分为两 类，一类是基于图中最小权路径算法的有效重定时的判定算法，另 一类是基于简单重定时的有效重定时的判定算法。本文在基于简单 重定删的基础上提出了一种重定时算法f a m ，此算法的时i n j 计算复 杂度较经典算法f e a s 有所改善。 本文对重定时算法进行了深入研究，目的在于消除同步时序电路 的时亭冲突，从而缩短集成电路的设计时间。 关键词：集成电路；同步时序电路：重定时；时序调整策略 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h eg r o w i n go fs c a l eo fi n t e g r a t e dc i r c u i t sa n dp o p u l a r i z i n g o fi t sa p p l i c a t i o n ，t h e r ei sag r e a td e m a n df o rm a k i n gs h o r td e s i g n p e r i o da n dd e c r e a s i n gd e s i g nd i f f i c u l t y h i g h - l e v e ls y n t h e s i s ( h l s ) s y s t e m sf o rd i g i t a li ca r ep l a y i n gs u c har o l e ，b u tc i r c u i t r yn e tt a b l e w h i c hi ss y n t h e s i z e db ys y n t h e s i z e ri sn o tn e c e s s a r i l ya c h i e v et h e d e m a n do fd e s i g n e r ，s oa i mf o rt h es p e e dd e m a n do fd e s t i n a t i o n ，t h e s e q u e n c ec i r c u i tw h i c hi ss y n t h e s i z e dd e m a n ds p e e do p t i m i z a t i o n t h e m e t h o do fo p t i m i z a t i o ni sc l a s s i f i e di n t ot w oc a t e g o r i e s ：( 1 ) c o m b i n a t i o n a lo p t i m i z a t i o nm e t h o d ，w h i c hi s t h e o p t i m i z a t i o n a l m e t h o do fc o m b i n a t i o n a lc i r c u i ti sd i r e c t l yu s e df o rt h es e q u e n c e c i r c u i t ( 2 ) r e t i m i n g ，w h i c h c a no p t i m i z et h er a p i d i t y ，a r e aa n d f u n c t i o n a le x t r a v a g a n c et h r o u g hm o v i n gt h es e q u e n t i a le l e m e n t sa n d c h a n g et h en u m b e ro fs e q u e n t i a le l e m e n t s o p t i m i z es y n c h r o n o u ss e q u e n t i a l c i r c u i tw i t hr e t i m i n gw a s i n t r o d u c e d b y l e i s e r s o na n ds a x ei n19 8 3 ，a n d r e t i m i n g o p t i m i z a t i o n a la l g o r i t h mw a ss u m m a r i z e dc o m p r e h e n s i v e l yi n 19 91 r e t i m i n gh a sb e e nu s e df o rm a n yf i e l d sr e c e n t l y r e g r e t f u l l y ，t h e r e t i m i n ga l g o r i t h m c a nn o tb e u s e d t o g e t h e r w i t h e x i s t i n g c o m b i n a t i o n a lo p t i m i z a t i o nt e c h n i q u e s b u t ，r e t i m i n gs h o u l db eu s e d t o g e t h e rw i t he x i s t i n gc o m b i n a t i o n a lo p t i m i z a t i o nt e c h n i q u e sa n df o r m a no p t i m i z a t i o n a lf l o wi np r a c t i c a lc i r c u i t r ys y s t e mt oe x e r tf u l l yt h e a d v a n t a g eo fb o t h i nt h ep a p e r ，t h en e wr e t i m i n gw h i c hc a nb eu s e d w e l lt o g e t h e rw i t he x i s t i n gc o m b i n a t i o n a lo p t i m i z a t i o nt e c h n i q u e si s i n t r o d u c e d r e t i m i n g c a ne l i m i n a t e s e q u e n c e c o n f i c tw h e ns e q u e n c e c o n s t r a i n tc o n d i t i o nf o re x a m p l ed e s t i n a t i o nc l o c kp e r i o di ss c h e d u l e d ， t h er e t i m i n gi sc a l l e ds e q u e n c ea d j u s ts t r a t e g y t h ee f f e c t i v e l y 哈尔滨 ：程大学硕士学位论文 i i ；j i i i | i i 日i i i i j i i i i i j l r e t i m i n gd e t e r m i n i n ga l g o r i t h mi sk e yo fr e t i m i n g ，s oi ti st h ek e yo f s e q u e n c ea d ju s ts t r a t e g y t h ee f f e c t i v e l yr e t i m i n gd e t e r m i n i n g a l g o r i t h mc a nb em a i n l yc l a s s i f i e di n t ot w oc a t e g o r i e s ：o n ei sb a s e do n m i n i m a lw e i g h tp a t ha l g o r i t h m ，t h eo t h e ri sb a s e do i ls i m p l er e t i m i n g ， ar e t i m i n ga l g o r i t h mf a mw h i c hb a s e do ns i m p l er e t i m i n gi s i n t r o d u c e di nt h ep a p e r ，t h et i m e c o m p u t a t i o nc o m p l e x i t y o ft h e a l g o r i t h mi sb e t t e rt h a nt h ec l a s s i c a la l g o r i t h mf e a s i no r d e rt oe l i m i n a t et h e s e q u e n c ec o n f l i c t o f s y n c h r o n o u s s e q u e n t i a l c i r c u i ta n ds h o r t e nt h e d e s i g n a b l e t i m eo f i n t e g r a t e d c i r c u i t s ，t h ea l g o r i t h m so fr e t i m i n gi sd e e p l yr e s e a r c h e di nt h i sp a p e r k e yw o r d s ：i n t e g r a t e dc i r c u i t s ：s y n c h r o n o u ss e q u e n t i a lc i r c u i t ： r e t i m i n g ：s e q u e n c ea d j u s ts t r a t e g y 1 1 项目背景 第1 章绪论 1 1 1 集成电路的发展 当前，集成电路产业的发展同新月异，1 9 9 9 年世界集成电路的销 售额达l5 7 0 亿美元。据国际权威机构预测，到2 0 1 2 年世界集成电 路的年销售额将达到l 万亿美元，并支持6 8 万亿美元的电子设备 和3 0 万亿美元的电子信息服务，相当于今天全世界g n p 的总和。集 成电路的发展加速了人类社会的信息化进程，已经成为信息产业乃 至2 1 世纪实现知识经济的基础之一。 推动集成电路迅速发展的主要原因主要有以下两方面： 需求牵咧 需求牵引可以概括为算法硬化和系统集成。 算法研究是当前电子信息产业发展中的前沿阵地。以往算法的实 现途径主要是软件编程，这就必须通过冯诺伊曼计算机串行结构 来进行：而今的算法特别是并行算法却更适合于硬件实现。这种着 重将算法以硬件的方式来实现的方法被称为算法硬化。 系统集成比较直观，就是将系统或子系统集成在个芯片上。以 前电子产品没计的基本思路是先选用集成电路厂家提供的标准集成 电路型号芯片( 如7 4 系列) 。再由这些芯片和其它元件构成更大的 电子系统。由于产品元件多，势必造成了结果可靠性低、功耗大、 系统复杂、产品性能差、产品外形体积大、成本高等缺点。而随着 集成电路集成度和组装密度的不断提高，把大量的标准i c 元件的外 引线转变为内引线，进行高密度组装，则达到了消除标准f c 的组装 延迟、大幅度地提高电路器件的性能、减小体积和功耗、减小系统 费用的目的。 技术推动 技术推动可以概括为v l s i 工艺的成熟和电子设计自动化 哈尔滨i 祥入学硕十学位论文 ( e le c t f o r t i cd e s i g na u t o m a t i o l l ，e d a ) 技术的完善。 几年来，集成电路的制造工业发生了飞跃性的变化。晶体管的特 征尺寸已经达到了0 1 微米的水平，在单个芯片上能够集成数以亿 计的晶体管，集成度达到几百万门的水平，同时制造成本在不断地 下降。这就使得原先需要一个系统才能完成的功能在单个芯片上就 能够实现。 随着集成电路复杂程度、组装密度和设计规模的不断提高，产品 生命周期丌始减少。计算机辅助设计( c o m p u t e ra id e dd e s jg n ，c a d ) 工具，尤其是e d a 工具成为i c 设计必不可少的手段。i c 的发展始终 爱到其设计方法自动化的直接影响。c a d 工具的功能不断地完善，为 系统与电路设计师提供了得心应手的设计手段，从而促进了f c 的发 展。可以晓，没有e d a 工具和手段，t c 的设计和发展是不可能的。 而超大规模集成电路( l a r g es c a ei n t e g r a t e dc jr c u j t ，v l s i ) 可以划分为通用集成电路和专用集成电路两大类。存储器等大量生 产且设计规则者称为通用集成电路：面向某一特定应用而专门设计 者称为专用集成电路( a p p l ic a t i o ns p e c l f i ci n t e g r a t e dc if c u i t ， a s i c ) ，a s i c 是近十几年来集成电路设计领域中发展最快的j 技 术。由于它将设计目标直接指向个别用户，从而区别于传统的通用 i c 的设计方法，可以根据不同用户的具体需要，灵活可靠地、高密 度地综合多种功能而形成性能价格比很高的专用芯片。 a s i c ”1 兴起子8 0 年代初期。髓着近年来电子产最市场需求的多 样化和产品更新周期的加快，a s l c 作为其实现手段，_ ：j r 始蓬勃发j 丧。 目前，a s i c 技术已经成为系统和线路板丌发与设计的基础。其品种 数量存不断增加，功能越来越强，应用范围也越来越广。它的丌发 和使用缩小了线路板的面积和体积，减少了系统的丌发费用，提高 了系统的可靠性，扩大和增强了系统在实时性、运算速度和并行处 理等方面的性能以及为新丌发的项目提供了技术保密。 今后，专用集成电路的发展方向将是更复杂的功能，如微处理器， 外围接口电路和存储器等集成电路集成在一个芯片内，即系统的集 成，实现所谓的单片解决。系统、整机、集成电路芯片之l a j 的界限 2 哈尔滨| 稃人学硕+ 学1 ： 7 _ 论文 将越来越模糊，很可能现有的商业单元( 微处理器、外围电路、a s i c ) 将归并为a s i c 一种。这就是目前f 在兴起的芯片系统( s y s t e mo n c h ip ，s o c ) 技术。 1 1 2i c 设计开发技术的发展历史 数字系统的性能和复杂度与e d a 发展，但这两者的水平是逐渐提高的 相互促进、共同发展的。 技术在近二十年中得到飞速的 并且是相伴而行、相辅相成、 近年来计算机硬件系统的性能价格比的飞跃性提高，为i c 设计 自动化技术的发展奠定了物质基础。到目前为j h ，i c 发计技术已经 经历了三代： 第代设计系统( 计算机辅助设计：c a d ) 这阶段产生于七十年代，其代表是版图编辑系统、电路模拟软 件和设计规则检查系统。主要的目的仅仅是提高绘制集成电路版图 的效率。该系统的主要功能是交互图形编辑、设计规则检查、解决 晶体管缴版图设计、p c b 布局布线、门级电路模拟和测试。 第二代设计系统( 计算机辅助工程：c a e ) 这一阶段产生于八十年代初，它把设计层从版图级提刃到原理图 级，设计效率提高了十倍以上。其代表技术是以逻辑原理图作为设 计输入，系统提供逻辑仿真、模拟验证工具来得到功能f 确的网表， 再用布局响i 线工具将网表映射到不同的制造工艺上完成电路的版图 设计。除人工输入电路图外，其它过程全部由系统实现。c a e ( c o m p u t e ra id e de n g in e e r in g ) 的一个重要特征是设计人员丌始 摆脱繁重的全定制版图设计。即基于单元库的半定制设计逐渐成为 设计的主流，a s i c 没计逐渐摆脱了手工方式。 第三代设计系统( 电子设计自动化：e d a ) 二卜世纪九寸年代设计系统是概念驱动设计和l 综合优化。它继承 了第二代设计系统验证和物理实现部分。发展了概念生成和功能生 成，是更高层次的软件系统。其最大特点是在概念设计电路时。首 先进行概念定义和功能描述，确定电路或系统总功能及有关参数， 哈尔滨i 。张人学硕十学位论文 确定各模块的功能及指标，然后从行为级进行电路模拟和综合优化， 最后自动生成相应的逻辑电路图，之后的过程同第二代设计系统相 同。这一阶段的特征就是它引入了硬件描述语言( h d l ) 及高级综合和 逻辑综合工具，采用较高的抽象层次进行设计，并按层次武方式进 行管理，可大大提高处理复杂设计的能力，设计所需周期也大幅度 缩短，综合优化工具的使用使芯片的品质如面积、速度、功耗等获 得了优化。这一阶段最重要的特征就是高层次综合技术，并成为国 内外电子系统设计自动化研究和丌发应用的主流和热点。 随着数字系统设计的同趋复杂和功能的不断扩大，越来越多的系 统要求集成到一块或几块芯片上，从而使一块芯片就可完成一个复 杂的系统功能，这种系统也常被称为系统l s i 或片上系统s o c ( s y s t e f f l o nc h i p ) 。a s i c 向芯片系统( s o c ) 的发展方向将是称之为集成系统 设计方法的第四代a s i c 设计技术，即以c p u ( d s p ) 为核心的设计方 法。它注重编程和软件的固化，以互连线作为问题的核心，用算法 丌发和数据流与控制流的方式描述系统，完成系统设计规范的结构 转化，在虚拟的原型设计环境中验证系统实现、系统集成，并将设 计和测试融为一体。 1 2 电子设计自动化中的重定时技术的理论研究 电子设计自动化( e d a ) 已成为集成电路( i c ) 设计中必不可少 的工具。进入九十年代以来，出现了以高层次综合为蕈要标志的第 三代电子设计自动化( e s d a ) 1 1 4 1 工具，实现了在当日i 工：艺下i c 设汁 的全部自动化。i c 设计输入由硬件描述语言编写的行为级电路描述， 经高级综合、寄存器传输级( r t l ) 综合、逻辑级综合和版图绒综合 实现电路的版图。同时，由于用户对i c 性能要求的提高和i c1 = 艺 的发展，使得设计技术越来越重视电路的性能。面i 柚性能 ( p e r f o r m a n c e d r c c t e d ) 的i c 设计与以往的设计不同时序榆 查、分析不仅是在每一次综合过程之后用束验证设计的讵确性，而 是j 4 1 - 设计综合”2 1 划分为若干设计步骤后，先进行时序分析，并根据 时序分析结果做电路综合，然后在此基础上再进行时序捡禽和分析， 喻尔滨i 科人学硕十学何论文 并驱动下一步综合过程。 以面积、速度为优化目标的组合逻辑研究较为成熟，而面向性能 的时序逻辑”】的优化方法主要分为两类，类是利用组合逻辑的综合 优化方法。另一类是利用重定时( r e i 躜i n g ) 优化对序忘路。 l e i s e r s o n 等人于1 9 8 3 提出重定时的概念，井于 9 9 1 年总结了 重定时的基本理论。 重定时是在保证电路功能不变的前提下，通过移动电路中的时序 元件的位置来优化时序电路，它具有不改变电路中组合逻辑电路的 特点。简单的重定时变换将组合逻辑门所有输出端连线上的时序元 件移至所有的输入端，结果是仅延迟了相应组合逻辑门进行逻辑运 算所处于游时钟周期，但对于整个电路的输入、输出特性并来改变。 图1 1 为重定时变换实例。 4 # i 未荨 一 图i 1 简单重定时变换实例 经过重定时后的电路与原电路的区剐主要在于电路中时序元件 的位置和个数发生了变化。若同步时序电路中时序元件的初始态决 定电路的功能，如控制器电路，那么经重定时后电路中时序元件的 幻始叁蔫重新计算。 重定时主要针对以下目标对同步时序电路进行优化。 时钟周期，即电路中纯组合逻辑最长通路的延时。 时序元件的个数。 荏一定的时钟周期的约束f ，优化时序元件个数。 在时钟周期优化中，同步时序电路被表示成有向图，图中的顶点 代表逻辑门或组合逻辑功能块，边为组合逻辑之间的连接，时序元 件棱作为边上的权重。重定时定义为有商图的顶点集合v 到整数集 i 上的一个映射，即r ：v l ，重定时对边上的时序元件的影响为： 对于任意一一条边e ：u v ，e 上的时序元件个数为w ( e ) ，那么经重定 s 哈尔滨i 群人学硕士学位论文 时后边e 上的时序元件个数的改变为 w ( e ) = w ( e ) + r ( v ) 一r ( u )( 卜1 ) 凶此，重定时优化问题为针对特定的目标，求解同步时序电路有 向图中所有顶点的重定时映射r 。 以时钟周期为优化目标的重定时优化算法中，约束条件有两大 类，一是经重定时后电路有向图中边上的时序元件个数非负，二是 在经重定时后电路有向图中，任意一条延迟时间大丁给定目标的路 径上，至少存在一个时序元件。这两个约束条件用藿定时映射r 表 示后，形成一一个线性规划问题，而此线性规划问题对应图中求解由 某一顶点到其余顶点的最小权路径算法。此算法可以在0 ( v l2 ) 时i a j 内求解其中fv f 为电路中所有组合逻辑顶点的个数。 以时序元件个数为优化目标的重定时算法中，约束条件为经重定 时后电路有向图中边上的时序元件个数非负。对于任意一个组合逻 辑顶点v 的重定时映射r ( v ) ，使得电路中的时序元件仑数改变 r ( v ) in d ( v ) 一o u t d ( v ) 个，in d ( v ) 和o u t d ( v ) 分别表示顶点v 的扇 入端数和扇出端数，因此电路的重定时变换使得时序元件个数改变 r ( v ) in d ( v ) 一0 u t d ( v ) ( 1 _ 2 ) ( 卜2 ) 式即是利用重定时优化时序兀件个数问题的优化目标。此 问题也可表述成个线性规划问题，其对偶问题可以用图中最小费 用流算法1 3 3 1 求解，考虑到逻辑门的相同输出端连线上的时序元件可 以共享，即逻辑门的扇出问题，那么只需在求解最小费用流豹约束 图中增加相应的汇顶点。 在一定的时钟周期下，利用重定时优化时序元件个数l 1 0 1 1 42 1 ，需要 增加以一f 约束条件，即在经重定时后电路有向图中。任意一条延迟 时i 铷大于给定目标的路径上，至少存在一个时序元件。当增加了此 约束条件后，得到的线性规划问题形式上与无时钟周期约束时以时 序元件个数为优化目标的重定时优化相同，可以归结为求解阁中最 小费用流问题n “。 以上是单相、沿触发同步时序电路中的重定时算洼理论。对于多 相、电平触发同步时序电路，时序约束条件与时序模型的建立有关， 6 喻尔滨l 。科人学硕十学位论文 ；j i i = ；i ；i i i i ；i i i ；i i ；i ；j i i ；i i i i i i i i i ；j ；i i i ；i ；i i 较单相、沿触发同步时序电路中的时序约束条件远为复杂，困此重 定时仅对特定相时钟的电路或特定结构的电路能够有效优化，或者 仅在存在时序冲突的局部电路中进行重定时优化。同时，n v s h e n 0 y 等研究了多相、电平触发同步时序电路中重定时变换下电路的时，爷 等价性f t e m p o r a le q u i v a l e n c e ) 4 1 。 对于初始念决定电路功能的一类电路，在进行重定时优化后需重 新汁算电路中时序元件的初始念。对于电路中组合逻辑输入端上的 时序元件移至输出端上的后向重定时变换，时序元件的初始态呵以 由相应组合逻辑的逻辑运算求解。由式( 1 1 ) 可知，所有顶点的重定 时映射r 增加一个相同的常数，并不改变重定时的结果，因此任意 重定时优化的解均可由后向重定时变换表示，此时直接与基本输入 端相连的组合逻辑的后向重定时变换增加的时序元件，可以看成是 由直接与基本输出端相连的组合逻辑的后向重定时变换移出的。因 此。已知原电路的扔始态s o ，需构造另初始态s 和一组输入序列 i ，使得电路在以s 为初始态时输入i 后达到状念s o ，而每一次与基 本输入端直接相连的组合逻辑做后向重定时时，当时序元件加入到 电路的基本输入端时，只需赋予i 中相应的一组矢量即可。 在重定时优化的理论研究中，除了用蚪上的算法求解优化问题 外，以时钟周期为目标的重定时优化可以在时序分析的基础上，循 环进行简单重定时变换求解，由于上述方法的时问计算复杂度为 o ( i v h e i ) ，在电路有向圉为稀疏图的情况下，与基于线性规划的重定 时优化算法的时刨计算复杂度为0 ( 【v i3 ) 比较有所改善，同时较为 直观，易于与其它优化算法相结合，因此在实际应用方面更具有研 究价值。而且重定时优化问题转化为混合整数的线性规划问题。 s d e y 等将同步时序电路的性能优化中关键路径和关键回路定义为 重定时优化瓶颈( r e t i m in gb o t t l e n e c k ) ，然后利用重定时算法进行 优化。 1 3 重定时技术的应用研究 重定时的基本算法理论较为成熟，近年来，重定时技术广泛应用 哈a ；滨| 科人学硕十学位论文 到电子系统设计自动化的许多具体领域。 首先在高层次综合中，重定时可以对综合出的逻辑级电路结果进 行优化，用于此目的的重定时己被加入到国外一些商用e d a 公司和 高层次综合工具中，例如s y n o p s y s 公司的高层次综合一工具行为级编 译器( b e h a v i o r a lr e t i m i n g ) 。另外，重定时作为启发式变换指导操 作的调度，在逻辑综合中，重定时被应用于基于树匹配的工艺映射 算法中。 便携式消费类电子产品的普及使得功耗成为a s i c 设计中除丽积 和速度以外的又优化目标，重定时变换可以通过改变时序元件的 位置减小电路中逻辑的丌关活动度( s w i t c h i n ga c t i v i t y ) ，从而优 化电路的功耗。 一般组合逻辑优化方法应用于时序电路时，仅对电路中组合逻辑 部分进行优化，重定时技术使得被时序元件分丌的组合逻辑电路可 以 超应用纯组合逻辑的优化方法，同时利用基于重定时的划分算 法优化时序电路。重定时不仅能与组合逻辑优化技术相结合，而且 可以和时钟偏斜优化1 6 1 统一在一个线性规划问题中对电路进行优化。 对于电路实例的分析表明，一般情况下，以速度为目标的重定时 优化会降低电路的可测性，主要表现在时序逻辑的测试矢量的7 l 成 时问增加和故障覆盖率降低等。但是近几年来，重定时技术被应用 于电路的可测性设计领域，从而提高电路的可测性。 重定时技术和其它一些算法级的变换技术被广泛应用于数字信 号处理( d s p ) 电路的设计和优化中，例如优化电路的资源利用率、 将电路变换为特定的结构和进行数据同步等。 电路的流水线结构化( p i i p e l i n e d ) 可以看作 种特殊的重定n 十， 重定时不仅对无反馈电路可以增加系统的吞吐量，而且对1 ：有反馈 的电路同样可以增加，应用重定时技术和图的最大流算法可以有效 地将组合逻辑电路转化为流水线型的电路。 重定时技术还被应用于电路设计的系统级和电路级。 国外一些大学也已研究了基于重定时技术的软件包，例如麻省理 工大学( m i t ) 的t i m 软件包。 r 哈尔滨一i 程人学硕十学何论文 1 3 1 高层次综合中的重定时技术 高层次综合【1 2 】【13 】【2 6 】 2 7 】是电子设计自动化领域中快速发展的一 门技术，它将电路的行为级描述转换为相同功能的r t l 级描述或逻 辑级描述。在高层次综合过程中，用户用硬件描述语言，如v h d l 、 v e r i l o g h d l 等，编写电路的行为级描述，经编译后生成中i h j 格式， 中问格式一般为控制、数据流图( c d f g ) 。然后利用调度和分配算法， 确定c d f g 中的操作所位于的控制步( c o n t r o ls t e p ) 和各种功能操 作、存储元件和连线单元的个数，在调度和分配过程中一般需满足 一一定的目标，例如速度、资源或二者兼而有之。对于调度和分配后 的操作赋予确定的逻辑功能单元，中间结果和逻辑表达式的输入、 输出赋予相应的存储单元，并确定逻辑功能单元之问的连接，即进 行组装( b i n d in g ) ，形成完整的数据通道【2 ”( d a t ap a t h ) i 刊时进行 控制器的综合，生成控制电路，控制电路一般由微程序控制方式或 用基于p l a 的有限状态机电路实现，组装的结果可颤是r t l 敛的库 单元表示，中问数据格式、r t l 级或逻辑级的硬件描述语吉文本。图 1 2 为利用高层次综合进行i c 设计的流程。 调度算法u 3 1 是高层次综合中的关键技术。调度算法巾类是利用 启发式的算法进行局部优化，它包括a s a p a l a p 问度算法、l l s t 调度算法和力向量( f o r c ed i r e c t e d ) 调度算法，另一类是全局优化的 调度算法，它基于整数线性规划( i l p ) 问题。 循环流水线( l o o pp i p e l i n i n g ) i | “是高层次综合中的关键技术之 一，它通过重迭相邻循环迭代( l o o pi t e r a t i o n s ) 增加系统的吞叶量。 在循环流水线技术中，循环( l o o p ) 可以用数据流图( c d f g ) 表示，数 据流图中的顶点表示计算单元，边表示计算单元之蚓的优先关系， 边上的权重表示时序元件的个数，顶点的权重表示计算单元的汁算 时、日j ，去除时序元件的个数不为零的边，数据流图被划分为一些子 图，这些子图为有向无环图( d a g ) ，满足有向无环图中优先关系的凋 度为循环的静态调度( as t a t i cs c h e d u l e ) ，静念调度的k 度为数据流图 的迭代周期。重定时通过移动时序元件的位置和改变时序元件的个 哈尔滨i 样人学硕十学付论文 数，使得数据流图中的子图发生变化，因此使得循环中的调度发生 改变。在一定的资源约束下，使得循环中的调度达到最优的重定时 变换町以通过启发式算法得到。 重定时不仅能够用束指导高层次综合的调度算法，而且对于高层 次综合后端得到的逻辑级电路描述，可以进行以特定目标( 而积、速 度l 的优化，如图1 3 所示。 否 i + 夏南面o 、 i 描述 ， 行为级模拟 为是否 合要求 高缀综合：编译 调度分配，组装 优化等 重设约束 逻辑综合，优化工 艺映射 逻辑级网表 否 一一疆看富岔 一耄 结束 一一一 ，行为级1 f d l 描述 行为级模拟 j 陌誊遂爹， 叫重设约束h 是 高级综合：编译、 清度分配、鲤装、 优化等 叫重设约束h 逻辑综合优化工 艺映射 逻辑级网表 重定时优化 否 一一一一菩舌高。旁 结乘 一一一 幽1 2 高级综合流科图1 3 重定时优化在高级综合中厉端的麻川 1 3 2 考虑连线延时和时钟偏斜的重定时技术 在一般的重定时技术中，连线延时 j o l 2 9 1 和时钟偏斜【1 7 】【18 1 作为常 数，可以加入到组合逻辑单元的延时中，然而在电路的物理实现时 1 0 哈尔滨i 程人学硕十学位论文 时序元件位于电路有向图的不同边上时，边上的延时发生了改变，同 时信号由时钟信号源到达相应时序元件的时钟延时( c l o c kd e l a y ) 也 发生了改变，所以当考虑更加实际的时序模型和时序约束时，需要 重新建立重定时优化中的约束条件，这对于连线延时占电路延刖 ! 导地位的深亚微米设汁1 4 i 】具有重要意义。 在电路的物理实现时，面积被划分为具有相似时钟延时的区域， 重定时技术中，如果时序元件的位置改变并不足够影响到电路的最 终物理实现，那么位于电路有向图中同边上的时序元件个数具有 相同的时钟延时，在考虑时钟分布、时序元件可变延时和连线延时 的情况下，同步时序电路有向图中的每条边被赋予寄存器电学特性 ( r e c l ，包括此边上时序元件的时钟延时，建立时f 、丑，信号相对于 时钟信号在时序元件输出端稳定的时间，以及当此边上加入时序元 件后，连线被划分为两部分后每部分的延时。时钟偏斜定义为山 组合逻辑电路相连的两个时序元件的时钟延时之差。 在考虑以上寄存器电学特性后，时序元件之阳j 的延时被表述为i 乜 路有向图中边到边的延时，而不是如一般重定时优化中表述为顶点 之蒯的延时。相应的约束条件除了非负边权约束和最大延时约束外， 由于时钟偏斜还必须考虑最小延时约束，另外需考虑内部延时约束， 即如果同一边上的两个时序元件间的延时大于给定的约束常数时， 则此边上的时序元件个数不能超过一个。同时，在重定时优化过程 中，最优时钟周期的求解仍然可以采用二分搜索法，但是每一步的 时钟剧期约束常数不是在。个集合中查找，而是用算术平均的方法 求得，而有效重定时的判定过程不再对应图中的最小权路径算法， 而是逐个检查约束条件，从而缩小相应顶点重定时映射的过程求得， 即采用分支和边界方法( b r a n c h a n d b o u n d ) 。 1 3 3 电路可测性设计中的重定时技术 为了降低时序电路的测试困难和测试丌销，需要在电路的发i i 阶 段考虑电路的可测性 2 5 1 。电路的可测性设计分为两类，类是针对 特定电路的可测性设计，另一类是通用的电路可测性设计。后者采 哈尔滨1 ：科人学硕十学位论文 用扫描( s c a np a t h ) 技术。全扫描( f u l ls c a n ) 需要在测试模式下将所有 的时序元件连接成一个扫描链，使得所有时序元件易于控制和观察。 然而在全扫描技术中需要改变所有时序元件的类型，电路的面积丌 销较大，于是提出了韶分扫描( p a r t i a ls c a n ) 技术，在部分扫描技术中 仅将电路中一部分时序元件连入扫描链中，因此除去扫描链中的时 序元件，电路仍然是时序逻辑电路，所以在部分扫描技术中，需要 采用时序电路的自动测试模式生成( a t p g ) 方法得到百分之百的故障 覆盖率，或采用不能覆盖所有故障的组合逻辑电路的a t p g 方法。 重定时的优化目标之一为时序元件的个数，在时序元件个数最优 化的电路中，每一时序元件所处于的回路的个数，在所有经重定时 变换的电路中最大。直观上，在时序元件个数最优化的电路中选择 扫描链中的时序元件的结果对于部分扫描链时序元件的选择应是最 优的，但是考虑到同步时序电路有向图中同一条边上可以同时存在 一个以j 二的时序元件，此时可能使得其它处于两个以上回路中的边 上不存在时序元件，因此利用重定时求最适合部分扫描技术的电路 结构时，需限制以时序元件个数为优化目标重定时的约束条件，使 得每条边上最多存在一个时序元件，由此得到的电路优化结构称 为双态结构( b i n a r ys t a t ec o n f i g u r a t i o i l ) 。 在基于重定时的部分扫描技术中，首先计算同步时序电路有向图 中每条边所在的回路数c c ( e ) ，选择具有最大c c ( e ) 的一部分时序儿件， 对于这些时序元件所处的边应用固态重定对变换，同时使得1 j 这些 边处于相同链路的其它边应用禁态重定时变换，然后利用以时序元 件个数为优化目标的重定时求解双念结构。在此双态结构的电路中 应用已有的启发式算法求解，完成扫描链时序元件的选择。 以上基于重定时的部分扫描技术中，利用重定时使得原电路变换 为有利于选择扫描链时序元件的功能相同的电路结构形式，而在另 一种部分扫描技术中，重定时和组合逻辑的再综合技术一起变换电 路结构，使之能够得到优化的扫描链时序元件的选择。 在电路的可测性设计中，重定时不仅可以应用于部分扫描技术 中，最近h y l i o u 和t t l i n 利用重定时进行电路划分，将i 乜路转 2 哈尔滨i 、科人学硕十学位论文 化为易于进行流水线型的伪穷举例测试( e e e t ) 中。 1 3 4 以功耗为目的的重定时技术 近年来，由于消费类电子产品的普及，例如便携式移动电话和笔 记本电脑等，使得功耗在a s i c 设计中可能超过面积和速度成为首要 优化目标，而a s i c 设计需要较短的设计周期，使得功耗分析4 ；能仅 到电路级设计时进行，而是在设计过程中的逻辑级综合，甚至高层 次综合中就应该考虑”耶”。 算出每一逻辑门的开关活动度和平均功耗，从而求出电路的平均 功耗。对于组合逻辑电路，上述方法是有效的，但是由于在时序电 路中缀合逻辑部分的输入不仅包含基本输入信号，而且包含n 路巾 时序元件所保存的现态信号，所以由上述方法求出的电路平均功耗 存在定的误差，如果时序电路是流水线型的，则第k 级时序元件 的输出仅与电路k 个时钟周期以前的基本输入有关，因此对于这种 结构的电路，上述方法仍然有效。以下论述重定时变换对此类结构 的电路进行功耗优化的方法。 在以功耗为目标的重定时优化1 中，首先对电路中每一逻辑门的 输出端计算加入对序元件后所引起的功耗减小权重，即费用函数。 计算出电路中每一逻辑门的费用函数后，在满足边上不出现负数时 序元件的约束下，进行以功耗为目标的重定时变换，同时要满足 定的时钟周期约束和时序元件个数约束。重定时的操作过程为，每 一步只进行一级流水线结构化，首先将电路的所有基本输入端处加 入时序元件，选择费用函数较大的一个逻辑门顶点集合，利用递归 向后重定时变换将基本输入端处的时序元件变换至上述集合中逻辑 门的输出端，在不改变上述集合中逻辑门输出端处时序元件的前提 下，利用重定时变换优化时钟周期和时序元件的个数，最后重复上 述步骤达到电路预先设定的流水线级数。 i 3 5 重定时技术与其它优化技术相结合 重定时优化不仅可以作为一种局部变换优化方法与其它方法州 哈尔滨1 群人学硕十学位论文 结合而且可以转化为线性规划问题与其它一些全局优化方法相结 合。以下讨论重定时优化分别与纯组合逻辑优化技术1 2 4 1 和时钟偏斜 优化技术相结合后的优化方法， 出于时序元件的存在，传统组合逻辑优化方只能优化出时序元件 分离丌的组合逻辑功能块，重定时通过移动时序元件使得原来组合 逻辑优化方法不能用的部分变为能用。其优化的一般步骤为首先通 过周缘重定时变换( p e r i p h e r a lr e t i m i n g ) 12 3 1 将电路内部边上的时序元 件移至周缘边上。然后通过纯组合逻辑优化方法 1 对除去周缘边的组 合逻辑部分进行优化，最后通过合法的重定时将时序元件移回电路 内部，从而得到与原电路功能等价的优化电路。这种重定时与组合 逻辑优化方法相结合的方法的优化目标出纯组合逻辑优化方法的优 化目标而定，可以以面积为目标，也可以以速度为目标。 幽】i4 周缘重定对变换豹例子 周缘重定时允许重定时后的电路在周缘边上出现负数的时序元 件个数，负数的绝对值可以等价地看成由外界环境借用的时序元件 个数，这种情形之所以允许是因为在随后的合法重定时过程中将等 值的时序元件个数还给外部环境。 图1 4 给出了周缘重定时变换的一个实例。 经过周缘重定时变换后的电路可以用已存在的任何纯组合逻辑 优化方法。经纯组合逻辑优化方法优化后的电路可以不存在合法的 重定时变换，此时需调整纯组合逻辑优化方案。如果存纯组合逻辑 优化后的电路中存在权重为负的出基本输入到基本输出的路径，则 1 4 哈尔滨i 料入学硕十学位论文 不存在合法重定时变换。 时钟偏斜优化又称为时钟延时优化，是通过在时序元件的时钟端 加固定延迟实现。由时序电路的f 确性约束，即最大延时约束和最 小延时约束。可以给出一个求解时钟延迟优化的线性规划方法。此 方法与重定时的般数学方法m i l p 一起给出一个将重定时与时钟 延迟优化相结合的线性规划方法。 1 3 。6 重定口寸在d s p 电路中的应用 重定时在d s p 电路中具有许多应用”】，它可以和其它算法绒的 变换优化方法一起对具体的d s p 电路进行优化，在d s p 的高层次综 合中优化电路的资源利用率和将电路变换为特定的效率更高的结 构，例如s y s t o l i c 结构和块处理( b l o c kp r o c e s s i n g ) 结构等。本节介绍 重定时在流水线电路的数据同步问题中的应用。 流水线系统的描述可以用信号流图( s f g ) ，在信号流图中，顶点 为处理节点( p r o c e s s i n gn o d e s ) ，边为数据通道( d a t a p a t h ) 。信号的延时 作为边的权重，即为u 与v 的延时d