（信息与通信工程专业论文）以时钟周期为优化目标的快速重定时算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 随着集成电路规模的扩大及其应用的推广，迫切需要缩短设计时l 、日j ，降低设计难度。 高层次综合( h l s ) 系统就起着这样的作用。但是由于综合器综合得到的电路网表不一定 能达到设计者的设计要求，所以需针对给定的速度要求，对综合得到的时序电路进行速 度优化，其中针对时序逻辑的重定时优化技术，便是一种重要的优化技术。重定时在保 证功能不变的前提下，通过移动时序元件的位置和改变时序元件的个数来优化同步时序 电路的速度、面积和功耗。 本文针对目前重定时算法的时间复杂度较大的弱点，对f e a s 算法进行了改进，提 高了算法的运行速度。接着根据实际电路中周期约束远远大于权重约束的情况，提出一 种减少周期约束的算法，算法首先将路径分类，由不同路径来确定重定时值的取值区间。 不断缩小其取值范围，最终确定其值。 本文实验以i s c a s 8 9 标准测试电路的e d i f 网表为输入数据源，通过编写c 程序对 f e a s 算法、改进的f e a s 算法和基于路径分类的重定时算法进行对比，结果表明我们 的算法能够快速完成同步时序电路的重定时变换。 【关键词】：重定时，同步时序电路，电路优化，电路综合，电子设计自动化 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h eg r o w i n go ft h es 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 go fi t sa p p l i c a t i o n ，i t i sv e r yn e c e s s a r yt os h o r t e nt h ed e s i g n p e r i o da n dd e c r e a s ed e s i g nc o m p l e x i t y h i g h l e v e l s 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 e a c o u s ec i r c u i t r yn e tl i s t 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 rm a yn o ta c h i e v et h ed e m a n do ft h ed e s i g n e r ，t h es e q u e n c e c i r c u i tw h i c hi ss y n t h e s i z e dm u s tb eo p t i m i z e du n d e rr e q u i r eo fs p e e d r e t i m i n gi so n eo ft h e i m p o r t a n tt e c h n i q u e so fo p t i m i z i n gs e q u e n c ec i r c u i t i nr e t i m i n gr e g i s t e r sa r ea d d e da ts o m e p o i n t si nac i r c u i ta n dr e m o v e df r o mo t h e r si ns u c haw a y t h a tt h ef u n c t i o n a lb e h a v i o ro ft h e c i r c u i ta saw h o l ei sp r e s e r v e d b yr e t i m n gw ec a no p t i m i z et h es p e e d ，a r e ao rp o w e ro ft h e c i r c u i t i nt h i sp a p e r , w ei m p r o v ef e a sa l g o r i t h mt h a te x h i b i t sh i 曲t i m ec o m p l e x i t yt od e c r e a s e t h er u n n i n gt i m e t h e nw ep r o p o s ear e t i m i n ga l g o r i t h mb yw h i c hw ec a nr e d u c et h en u m b e r o fp e r i o dc o n s t r a i n t s t h i sa l g o r i t h mi sb a s e so nt h a tt h en u m b e ro fp e r i o dc o n s t r a i n t so fa c i r c u i ti sg r e a tl a r g e rt h a nt h a to fn o n n e g a t i v i t yc o n s t r a i n t so np r a c i t i c a lc i r c u i t s a tf i r s t ，w e c l a s s i f yt h ep a t h e s ，a n dt h e nc o m p u t et h eb o u n d i n go ft h er e t i m i n gv a l u e a tl a s t ，t h er e t i m i n g v a l u e sc a l lb ec o m p u t e d b yd e c r e a s et h er a n g eo ft h eb o u n d i n g i nt h i sp a p e lw e h a v ec o n d u c t e ds o m ee x p e r i m e n t so nt h ei s c a s 8 9b e n c h m a r k st h a ta r e i nf o r mo fe d i ew ec o m p a r ef e a sa l g o r i t h m ，f e a sp l u sa l g o r i t h ma n da l g o r i t h mb a s e do n c l a s s i f yp a t h s o nr u n n i n gt i m e t h o s ea l g o r i t h m sa r ei m p l e m e n t e di ncl a n g u a g e a tl a s tw e c o n c l u d et h a to u ra l g o r i t h m sc a na c h i e v er e t i m i n gt r a n s f o r m i n gq u i c k l y 【k e y w o r d s ：r e t l m l n g , 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 s ，c i r c u i to p t i m i z i n g ，c i r c u i t s y n t h e s i s ，e l e c t r o n i cd e s i g na u t o m a t i o n 国防科学技术大学研究生院学位论文 图1 1 图l 一2 图1 3 图1 4 ， 图2 1 图2 2 图2 - 3 图3 1 图3 2 图3 - 3 图3 4 图3 5 图3 - 6 图3 7 图3 - 8 图3 - 9 图4 1 图4 2 图4 ，3 设计层次 电路级设计工作流程 系统级设计工作流程 重定时变换实例 k = 3 的相关机例 相关机二 图目录 图2 - 1 中相关机的有向图g 路径分类重定时示侧 前向重定时例 后向重定时例 路径p ( ，v o ，心，v o ) 路径p ( v ，v ，吃，v d 重定时后的有向图( a ) 重定时后的有向图( b ) 重定时后的有向圈( c ) 重定时后的有向图( d ) e d i f 格式结构图 ( e d i f v e r s i o n20o ) 的表示图 e d i f 树型结构示例 表目录 表1 1 国际半导体技术发展预测，1 表2 1 图2 - 1 电路的w d 值1 3 裹3 1 实验结果3 3 o o 砖 一m加挖药如 弘”弛弱弼 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：丛吐鲑周期蕴伍焦旦插曲医鎏重定虹篡洼盟窥 学位论文作者签名：! 虱垦生日期：2 却中年，月，f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阋和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：丛垃鲑眉塑遗抗位旦拯啦：陡建重宝吐篡洼盟究 学位论文作者签名：蜀堕垄日期：知衅年t 1 月帅 作者指导教师签名：! 盎遗日期：多牛年，j 月心日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题背景 1 1 1 微电子技术发展基本情况 一摩尔定律 自集成电路发明以来，集成电路一直按照摩尔定律( 大约每三年芯片集成度增大四 倍，微处理器速度提高一倍) 发展。根据美国半导体工业协会( s i a ) 1 9 9 9 年修订的国 际半导体技术发展指南( 1 9 9 9 1 t r s ) ，2 0 1 1 年前，半导体集成电路制造技术仍将按照摩 尔定律保持高速发展。其具体指标如表1 - 1 所示。近几年的研究工作进一步表明，将有 可能在2 0 1 4 年，实现0 0 3 5 m 芯片制造技术。 表卜1 国际半导体技术发展预测 9 9 预测 1 9 9 71 9 9 92 0 0 12 0 0 22 0 0 5 2 0 0 82 0 1 l 线宽( l 面 n2 5o t l 8 0 1 5o 1 30 1 00 0 7o 0 5 圆片尺寸( r 神 2 0 03 0 03 0 03 0 0 4 0 0 4 0 04 5 0 最小工作电压( v ) 1 8 _ 2 51 - 5 _ 1 _ 81 2 _ 1 51 2 - 1 5 0 9 _ 1 20 90 5 - 0 6 布线 66 _ 77 777 卅88 9 苍片频率0 i z ) 7 5 0 1 2 5 01 5 0 02 1 0 03 5 0 06 0 0 01 0 0 0 0 隙 咐( b ) 2 5 6 m1 g2 g 4 g 1 6 g6 4 g2 5 6 g 当前，支持摩尔定律有效的3 项重要制造技术是：超微细光刻技术、铜互连技术和 低k ( 介电常数) 介电材料技术。 二集成电路进入s o c 时代 随着芯片制造技术、嵌入式微处理器技术和软件技术的发展，集成电路历经6 0 、7 0 年代分立器件集成时代( 集成度为数手晶体管) ：8 0 年代功能电路及模块集成时代( 集成度 达到数十万晶体管) ；到9 0 年代末，进入以片上系统s o c ( s y s t e m - o n - c h i p ) 为代表的包括 软件、硬件许多功能全部集成在一芯片内的系统级芯片时代f 单片集成度达数百万晶体管 以上1 。 实现s o c 的关键技术课题是：上面所述的超微细光刻和铝连线3 层、铜连线6 层以 上的高集成制造技术；在1 颗芯片上混载存储器、逻辑电路、模拟电路、高频电路、编 程逻辑电路等的数模混合信号技术；包括系统设计、硬件软件协同设计、低功耗设计、 设计再利用( 职核) 、设计验证技术在内的i c 设计技术和嵌入式中问软件技术。 三i p 核 专有知识产权( 口：i n t e l l e c t u a lp r o p e r t y ) 核的设计再利用是保证系统级芯片开发效率 和质量的重要手段。 这是因为设计能力和制造能力存在距离：按照摩尔定律，芯片制造能力大约每年增 第1 页 国防科学技术大学研究生院学位论文 长5 8 ；随着集成电路规模和复杂性的增大，进入9 0 年代中后期，集成电路设计能力 的年增长比率约为2 1 ，滞后于制造技术能力的提高，二者间存在差距。弥补设计生产 效率和芯片密度之间的差距争取第个进入市场最有效的方法是重复使用已有的设计 ( 设计再利用) 或虚拟器件( v c ) o pi p 核技术。 四可编程器件 s o c 要快速灵活地对应多种应用。因此系统整机设计人员强烈要求系统l s i 的可编 程性。这里的关键是以什么形式能够提供这种可编程性。实现需要的功能有全硬件和 c p u + 软件两种方法。全硬件也有利用掩膜的专用l s i 设计方法和将一部分逻辑电路通 过外部编程( 连接，切断) 来实现的方法。专用l s i 设计制造周期较长，因此产生了门阵列 和f p g a p l d 。目前值得特别注意的是具有c p u 核和存储器等芯核的p l d 已经进入市 场。与此同时，人们在极力追求c p u 的灵活性。c p u 有面向控制的m c u 、面向通用事 务处理的m p u 和面向实时数字信号处理的d s p 。最近出现了处理器结构和命令集可灵 活变更的c p u 。 1 1 2e d a 技术的发展与应用 电子设计技术的核心就是e d a 技术，e d a 是指以计算机为工作平台，融合应用电 子技术、计算机技术、智能化技术最新成果而研制成的电子c a d 通用软件包，主要能 辅助进行三方面的设计工作，即i c 设计、电子电路设计和p c b 设计。e d a 技术已有3 0 年豹发展历程，大致可分为三个阶段。7 0 年代为计算机辅助设计( c a d ) 阶段，人们开始 用计算机辅助进行i c 版图编辑、p c b 布局布线，取代了手工操作。8 0 年代为计算机辅 助工程( c a e ) 阶段。与c a d 相比，c a e 除了有纯粹的图形绘制功能外，又增加了电路 功能设计和结构设计，并且通过电气连接网络表将两者结合在一起，实现了工程设计。 c a e 的主要功能是：原理图输入，逻辑仿真，电路分析，自动布局布线，p c b 后分析。 9 0 年代为电子系统设计自动化( e d a ) 阶段。 e d a 代表了当今电子设计技术的最新发展方向，它的基本特征是：设计人员按照“自 顶向下”的设计方法，对整个系统进行方案设计和功能划分，系统的关键电路用一片或 几片专用集成电路( a s i c ) 【1 】实现，然后采用硬件描述语言( h d l ) 完成系统行为级设 计，最后通过综合器和适配器生成最终的目标器件，这样的设计方法被称为高层次的电 子设计方法。 e d a 技术的每一次进步，都引起了设计层次上的一次飞跃，图1 - 1 示出e d a 技术 设计层次的飞跃。物理级设计主要指i c 版图设计，一般由半导体厂家完成。电路级设计 工作流程如图1 - 2 所示。电路级的e d a 技术使电子工程师在实际的电子系统产生前，就 第2 页 国防科学技术大学研究生院学位论文 设计层次 系统级设计 电路级设计 物理级设计 7 0 年代8 0 年代9 0 年代 图卜1 设计层次 可以全面地了解系统的功能特性和物理特性，从而将开发风险消灭在设计阶段，缩短了 开发时间，降低了开发成本。 图卜2 电路级设计工作流程 进入9 0 年代以来，电子信息类产品的开发明显呈现两个特点：一是产品复杂程度提 高；二是产品上市时限紧追。然而，电路级设计本质上是基于门级描述的单层次设计， 设计的所有工作( 包括设计输入、仿真和分析、设计修改等) 都是在基本逻辑门这一层 次上进行的，显然这种设计方法不能适应新的形势，一种高层次的电子设计方法，也即 系统级设计方法，应运而生。 高层次设计是一种“概念驱动式”设计，设计人员无须通过门级原理图描述电路， 而是针对设计目标进行功能描述。由于摆脱了电路细节的束缚，设计人员可以把精力集 中于创造性的方案与概念的构思上，一旦这些概念构思以高层次描述的形式输入计算机， e b a 系统就能以规则驱动的方式自动完成整个设计。这样，新的概念就能迅速有效地成 为产品，大大缩短了产品的研制周期。不仅如此，高层次设计只是定义系统的行为特性， 可以不涉及实现工艺，因此还可以在厂家综合库的支持下，利用综合优化工具将高层次 描述转换成针对某种工艺优化的网络表，使工艺转化变得轻而易举。系统级设计的工作 第3 页 一 一 詈 国防科学技术大学研究生院学位论文 流程见图卜3 。如果是大批量产品开发，则通过更换相应的厂家综合库，轻易地转由a s i c 形式实现。 图1 3 系统级设计工作流程 综上所述，e d a 技术是电子设计领域的一场革命，目前正处于高速发展阶段，每年 都有新的e d a 工具问世。广大电子工程人员掌握这一先进技术，这不仅是提高设计效 率的需要，更是我国电子工业在世界市场上生存、竞争与发展的需要。 1 2e d a 中的重定时技术 电子设计自动化( e d a ) 己成为集成电路( i c ) 设计中必不可少的工具。进入九十 年代以来，出现了以高层次综合【2 ；3 】为重要标志的第三代电子设计自动化( e s d a ) 【4 】 工具，实现了在当前工艺下i c 设计的全部自动化。i c 设计输入由硬件描述语言编写的 行为电路描述，经高级综合、寄存器传输级( r t l ) 综合、逻辑级综合和版图级综合实 现电路的版图。同时，由于用户对i c 性能要求的提高和i c 工艺的发展，使得设计技术 越来越重视电路的性能。面向性能( p e r f o r m a n c e d i m m e d ) 的i c 设计与以往的设计不同， 时序检查、分析不仅是在每一次综合过程之后用来验证设计的正确性，而是将设计综合 【5 恻分为若干设计步骤后，先进行时序分析，并根据时序分析结果傲电路综合，然后在 此基础上再进行时序检查和分析，并驱动下一步综合过程。 以面积、速度为优化目标的组合逻辑研究较为成熟，而面向性能的时序逻辑【6 】的优 化方法主要分为两类，一类是利用组合逻辑的综合优化方法。另一类是利用重定时 ( r e f i m i n g ) 优化时序电路【7 9 】。 第4 页 国防科学技术大学研究生院学位论文 图卜4 重定时变换实例 l e i s e r s o n 等人于1 9 8 3 提出重定时的概念，并于1 9 9 1 年总结了重定时的基本理论 【1 0 】。重定时是在保证电路功能不变的前提下，通过移动电路中的时序元件的位置优化 时序电路，它具有不改变电路中组合逻辑电路的特点。简单的重定时变换将组合逻辑门 所有输出端连线上的时序元件移至所有输入端，结果是仅延迟了相应组合逻辑门进行逻 辑运算所处于的时钟周期，但对于整个电路的输入、输出特性并未改变。图卜4 为重定 时变换实例。 经过重定时后的电路与原电路的区别主要在于电路中时序元件的位置和个数发生了 变化。重定时主要针对以下目标对同步时序电路进行优化。 1 时钟周期，即电路中纯组合逻辑最长通路的延时。 2 时序元件的个数。 3 在一定的时钟周期的约束下，优化时序元件个数。 定义时序逻辑电路的有向图为g ，e ，d ，w ) ，r 为一重定时。在以时钟周期为优化 目标的重定时优化算法中，约束条件有两大类，一是经重定时后电路有向图中边上的时 序元件个数非负，二是在经重定时后电路有向图中，任意一条延迟时间大于给定目标的 路径上，至少存在一个时序元件。这两个约束条件用重定时映射r 表示后，形成一个线 性规划问题，而此线性规划问题对应图中求解由某一节点到其余节点的最小权路径算法， 此算法可以在硎y f ) 时间内求解，其中川为电路中所有组合逻辑节点的个数。 以时序元件个数为优化目标的重定时算法中，约束条件为经重定时后电路有向图中 边上的时序元件个数非负。对于任意一个组合逻辑节点v 的重定时映射r p ) ，使得电路 中的时序元件个数改变r ( o i n a ( v ) 一o u t ( v ) 个，i n d ( v ) 和o u t d ( v ) 分别表示节点v 的扇入端和 扇出端数，因此电路的重定时变换使得时序元件个数改变 罗 r o ) - 【加d ( v ) 一d ( v ) 】) ( 1 1 ) ( 1 1 ) 式即是利用重定时优化时序元件个数问题的优化目标。此问题也可表述成一个 线性规划问题，其对偶问题可以用图中最小费用流算法求解，考虑到逻辑门的相同输出 端连线上的时序元件可以共享，即逻辑门的扇出问题，那么只需在求解最小费用流的约 束图中增加相应的汇节点。 第5 页 国防科学技术大学研究生院学位论文 在一定的时钟周期下，利用重定时优化时序元件个数，需要增加以下的约束条件， 即在经重定时后的电路有向图中，任意一条延迟时间大于给定目标的路径上，至少存在 一个时序元件。当增加了此约束条件后，得到的线性规划问题形式上与无时钟周期约束 时以时序元件个数为优化目标的熏定时优化相同，可以归结为求解图中最小费用流问题。 在重定时优化的理论研究中，除了用以上的算法求解优化问题外。以时钟周期为目 标的重定时优化可以在时序分析的基础上，循环进行简单重定时变换求解( 即f e a s 算 法) ，由于上述方法的时间计算复杂度为o ( i v l n ) ，在电路有向图为稀疏图的情况下，与 基于线性规划的重定时优化算法的时间计算复杂度为o d v l 3 1 比较有所改善。同时较为直 观，易于与其它优化算法相结合，因此在实际应用方面更具有研究价值。 近年来，随着重定时的基本算法理论使用日趋成熟，重定时技术已逐渐应用到电子 系统设计自动化的许多具体领域。然而对由n 个组合逻辑组成的时序逻辑电路，经典的 f e a s 算法【7 ；1 0 】时间复杂度为d 0 3 ) 空间复杂度为o ( n 2 ) 。因此经典的f e a s 算法不能有 效地应用到大规模的电路中。这也是重定时算法没有得到大规模应用的原因。因此要想 让重定时算法得到广泛应用，必须降低重定时算法的时间计算复杂度。 1 3 本文的主要内容 在超大规模集成电路技术流行的今天，s o c 的一般设计流程是通过高层设计语言 ( 如v h d l 语言) 输入，分别经r t l 综合器、逻辑综合器综合得到的电路的网表输出， 再由自动布局布线器完成版图的综合。由于综合器综合得到的电路网表不一定能达到设 计者的设计要求，所以需针对给定的速度要求，对综合得到的时序电路进行速度优化。 本文将在以时钟周期为优化目标的重定时优化算法的基础上，对快速的重定时算法进行 研究，对f e a s 算法进行了改进以提高其速度，并提出一种以路径分类为基础的重定时 算法。 全文共分为四章，各章内容具体安排如下： 第一章简单介绍了课题的研究背景和重定时技术研究现状，并叙述了本文的主要研 究工作。 第二章介绍以时钟周期为优化目标的熏定时优化理论。 第三章首先在分析经典f e a s 算法的基础上对f e a s 算法进行改进，接着针对不同 路径的特点，研究旨在减少约束数量的重定时算法，最后进行了实验分析，实验结果显 示两种算法在速度上较p e a s 算法都有了很大的提高。 第四章介绍了电子设计交换格式( e d i f ) 以及读取e d i f 文件中电路信息的程序开 发。 第6 页 量堕型兰茎查奎芏塑壅兰坚兰垡笙兰 最后对全文进行了总结。 第7 页 国防科学技术大学研究生院学位论文 第二章重定时的基本理论 2 1 引言 v l s i 设计自动化的目的是在不牺牲系统性能的前提下加快系统的设计。一般采用优 化工具来提高系统设计的质量，本章将介绍一种通过优化分配寄存器的方法来优化时序 逻辑电路。不同于流水线，这种称为重定时( r e t i m i n g ) 7 ；1 0 】的技术不会增加电路延迟。 为了描述重定时，我们首先考虑设计一个数字相关机，这个相关机的输入为序列x 。， 葺，石2 ，而， 把输入与常参数a o ，a l ，8 2 ，口3 ，a t 比较，z 1 0 输出y ： y i 。篆6 ( x t _ j , a j ) ( 2 1 ) d 为冲击函数，定义为： 淝y ) 磊 ( 2 2 ) 图2 - 1 给出了当k 一3 时的一个简单相关机，它包括两种功能元件，加法器和比较器， 各元件之间连线上的长方块表示寄存器。每个时钟置与参数比较，同时加法器输出匹配 数。 a 0 a 6 口2 q ，杏，杏哪 上 图2 - i k - 3 的相关机例 这个系统的最小时钟周期是很容易计算的。假设，每个加法器的传输延迟是7 n s ， 每个比较器的传输延迟是3 n s ，那么系统时钟周期至少为2 4 n r 一即信号从a 处的寄存器 经过一个比较器和三个加法器所用的时间。 第8 页 国防科学技术大学研究生院学位论文 如果我们把a 处的寄存器移动到b 处，得到相关机二，如图2 2 所示。这个相关机 与原始相关机的功能是等价的。当移除a 处的寄存器时，信号到达a 后比较器的时间提 早了一个时钟，则b 处输出信号也提早了一个时钟，在b 处加上一个寄存器后，b 处输 出又回到原来的样子，所以相关机二与原相关机功能相同。图中方框内的三个元件较原 相关机中信号提前一个时钟周期到达。 蕊 瓣 图2 2 相关机二 相关机二与原相关机功能相同，但重定时后的相关机二比原相关机性能要好，相关 机二的最小时钟周期是1 锄r 一即信号从c 处的寄存器经过一个比较器和两个加法器所用 的时间。两个相关机用了同样的元件，组合元件的位置也相同，不同的只是寄存器的位 置。相关机二同样完成公式( 2 1 ) 的功能，但显然较原相关机有效。 在保持电路功能不变的前提下，重定时通过移动时序元件的位置和改变时序元件的 个数来优化同步时序电路。以上电路通过重定时优化还可以得到最小时钟周期为1 4 n s 和1 3 n s 的电路。本章将阐述两种得到最小时钟周期电路的重定时算法。 2 2 时序逻辑电路的有向图 在重定时理论中同步时序逻辑电路可以用一个节点权重、边权重的有向图【7 ；1 0 】 g - g 以，v ，e ，w ，d ) 表示，其中v h 为一特殊节点，表示外部环境，节点集合v 中的每个 节点i - 表示电路中的组合逻辑功能块，例如与非门、加法器、多路选通器。有向边集合 e 中的边。表示组合逻辑功能块之间的连接，边上的权重咄) 表示边e 所连接的两个组 合逻辑功能块之间的时序元件的个数，例如寄存器的个数，边上权重的集合记为h ，。v 中每一个节点的权重d o ) 表示该节点组合逻辑功能块的时延，构成集合d 。图2 3 给出 图2 - 1 中的同步时序电路的有向图表示g ，其中边上的权重代表时序元件的个数。 节点v 。表示外部环境节点，定义v 。的传输延迟为0 。如果有多个与外部连接的节 点时，我们将所有外部节点合为一个，由多条边与节点相连。另外，我们假设各个外部 第9 页 国防科学技术大学研究生院学位论文 节点间是互相独立、互不通信。在我们大多数理论中，外部节点可以看作普通节点。 命。9 。献。、 。杏，杏。，奄 图2 3 图2 - 1 中相关机的有向图g 在有向图中，为了不混淆节点权重( 例如传输延迟d ) 和边权重( 例如寄存器数w ) ， 权重在这里仅表示边权重。实际上，节点权重中我们仅用到了传输延迟d p ) ，边权重指 的是寄存器的数目， ) 。在有向图中，如果e 是由“到v 的一条边，则记为“三一v 。u 称为e 的头节点，y 称为e 的尾节点。如果的头节点或尾节点不确定，我们用符号“? ” 表示，例如u ? 。 如果组合逻辑功能块h 、屹之间存在边u ，v ：相连，则u 、i ：2 分别称为边e 的尾 节点和头节点。所有以节点y 为尾节点的边的头节点组成的集合，称为节点v 的扇出节 点集，记为d f o ( v ) ，同理，所有以节点v 为头节点的边的尾节点组成的集合，称为节点 v 的扇入节点集d f i ( v 、。 在有向图g 中，一条路经p 定义为节点和边的序列。如果路径p 由“出发到达v ， 记为p 一v ) 。如果一条路经中的任意一个节点仅出现一次，则称该路径为简单路径，即 无回路路径。 对于任意路径p ( h 山v 2 山生_ 咋) ( 或记为p “，v ：，唯) ) ，定义路径 p 的权重w p ) ，即路径p 上的时序元件的个数为路径中所有时序元件的和： t - 1 似p ) - 罗w ( 岛) ( 2 3 ) 铷 相应的，我们也可以扩展传输延迟函数d 到一简单路径上。路径p 的时延d 为路 径中所有组合逻辑功能块时延之和： i d ( p ) - d ( u ) ( 2 4 ) 如果一条路经的起始点与终止点相同，则称此路径为有向回路，记为工。即回路l 是一个闭合的路径： l ( v o 丘。+ v l “u l - v o ) 它是路径p 的特例，回路工的权重w 伍) 和时延d ) 的计算同路径p 。 第1 0 页 国防科学技术大学研究生院学位论文 为了使有向图gt g 帆，v ，e ，d ) 表示一个有正确物理意义的电路，传输延迟d ( v ) 和寄存器数w 0 ) 需要满足以下非负条件： d 1 对于任意节点y 传输延迟d d ) 是非负的，即d p ) 0 。 w 1 对于任意边e e ，w 0 ) 是非负的整数，即w 0 ) o ，且w 0 ) 为整数。 同时有向回路必须满足如下条件： w 2 g 的任一有向回路中，必须有一条边上的寄存器数量为正整数，即d 伍1 o ， 且d e ) 为整数。 条件w 2 表示任一有向回路中至少存在一个时序元件，否则电路可能出现异步锁存、 振荡和冒险冲突等现象。 对于同步时序电路c 的有向图g ，最长组合通路的时延为最小可行时钟周期。记为 中( g ) 。在以下章节中，最小可行时钟周期简称为时钟周期。时钟周期的计算如下式所示： 中( g ) 一m a x d ( p ) 1 w ( p ) 一吣 ( 2 5 ) 图2 - 3 的电路图的时钟周期是2 4 n s ，a p 路径p ( v o ，k ，”，以) 或路径p 心以，”，以) 的传输延 迟。 计算电路的最小可行时钟周期的算法，简称c p 算法 7 ；1 0 】，描述如下： 算法c p ： 1 g 0 表示g 的子图，g o 中所有边权为零，即w ( e ) - 0 ； 2 由条件w 2 知g o 是无环的，对于每一子图g 0 中的任一边“l ，v ，有序对( h ，v ) 构成有序关系，对g 中所有节点依据有序关系进行拓扑排序( 若有u 三_ 一v ，则 h 必在v 前) ； 3 对于步骤2 中得到的序列，由以下步骤计算值a ( v ) ： a 如果y 没有前级节点，则a ( v ) 一a ( v ) ； b 否贝0 ，a ( v ) 一d ( v ) 4 - m a x i a ( u ) ：“- v a n d w ( e ) - 0 ) ； 4 中( g ) 一m a x 日，a o ) 。 算法对每一个节点v 进行运算，得到以该节点为头节点的所有零权路径的最长传输延迟 a ( v ) ，在从所有a 0 ) 中取最大值得到m ( g ) 。因为序列和有序对与边数吲成正比，所以 算法的时间复杂度为o o e l ) 。 2 3 重定时 重定时变换只移动寄存器的位置而不改变电路的结构。本节将定义重定时，并对它 的一些简单特性进行阐述。 时序逻辑电路的有向图为g o ，e ，d ，w ) ，经重定时变换r ：y z ，有向图变为 第1 1 页 国防科学技术大学研究生院学位论文 g ，一，e ，d ，”) ，对于g ，中的任意边“v ，有 h 0 ( e ) 一 v ( e ) + ，( v ) 一r ) 其中w ，0 ) 表示经重定时r 后边e 的权重。 对图2 3 中的电路进行如下重定时变换： 相一 苫灿巍匕 得到图2 2 所示电路。 等式( 2 6 ) 给出了重定时对边的作用，同样也可以用在路径上。 引理1 时序逻辑电路的有向图为g - ，e ，d ，w ) ，r 为- - i l 定时， u 卫_ v ，则有 ；( p ) 一w ( p ) + r ( v ) 一r 0 ) 证明： 假设p 为p ( v l 山v 2 咋) ，则 w r ( p ) 2 w ，瓴) 。( w ) + r ) 一， 2 z 衅r ) + ( r ) 一r “) ) 2 善w ”善眠t ) 吨) ) ( 2 6 ) ( 2 7 ) 对g 中的任意路径 ( 2 8 ) 得证。 推论1 时序逻辑电路的有向图为g ，e ，d ，w ) ，r 为一熏定时，对g 中的任意回路p ， 则有 w ，( p ) - w ( p )( 2 9 ) 如何判断重定时为合法重定，要看g ，是否满足条件d i 、w i 和w 2 。由于g 满足 d 1 ，所以g r 必满足d 1 。强制执行重定时时，可能导致g r 不满足w l ，即导致某些边权 重小于零。根据推论1 可知g ，在g 满足w 2 的条件下必满足w 2 。所以我们可以得到以 下推论。 推论2 时序逻辑电路的有向圈为g 一，e ，d ，们，为一重定时，g g ，若g r 满足 w 1 ，则，为一合法重定时。 第1 2 页 国防科学技术人学研究生院学位论文 2 4 基于线性规划的重定时算法 本节将介耋f 种获得电路最小时钟周期的重定时算法。在介纠锋法之前我们先看一 下下面的l p 问题。 l p 问题：s 为m 个以下线性不等式的集合 工f x is 口“( 2 1 0 ) ，x 2 ，矗是未知的，是给定的约束。决定t 的值存在或不存在。 由( 2 1 0 ) 式形式的约束系统被广泛研究，可以由算法b e l l m a n f o r d 【1 l 】解决，时间复 杂度为o ( m n l ) 算法描述如下： 算法b e l l m a n f o r d 1 初始化：胃x i = ( 1 c ，则w ( u ，v ) 2 1 。 证明： 第1 3 页 k一如m烈孔肌m，他nh，加k一埔埔地m，船 一挖他9 6 3 站舱珀 k o o 6 o 黔埔 k 一6 6 3凹如n 匕一3 3嬲盯盯孔hom孔n“， dhkkhk叶u 国防科学技术大学研究生院学位论文 ( 1 2 ) 如果中( g ) s c ，u 、v 为满足d ( u ，y ) c 的节点。 假设w ( u ，v ) - 0 ，那么“、v 间一定存在一条路径p 使得 d ( p ) 一d ，v ) c w ( p ) 一w 0 ，v ) - 0 由c p 算法知必有a v ( g ) c ，矛盾所以w ( u ，v ) 1 ( 2 1 ) 如果2 成立，对任意零权路径“一v ，有 ，v ) i 以p ) 一0 那么 d ( p ) s d ，v ) s c 则有 垂( g ) s c 得证。 计算w 可以采用f l o y d - w a r s h a l l 算法【1 1 】，该算法的时间复杂度为。洲3 ) ；或采用 j o h n s o n 算法【1 2 】，该算法时间复杂度为d ( e | + i v l 2l g l v l 。下面给出计算和d 的算法 和f l o y d - w a r s h a l l 算法。 算法w d 1 将有向图g 中以任意节点u 为尾节点的边e ，赋予有序对( w ( e ) ，一d “) ) 作权重； 2 利用步骤1 中定义的有序对通过求所有节点对之间的最小权路径算法，求出图中 任意两个节点h 、v 之间的最小权路径的权重；( 在最小权路径算法中，有序对中 的元素分别计算。) 3 对于任意两个节点玑v ，如果步骤2 中计算的最小权路径的权重为( x ，y ) ，则 0 ，v ) 一x d “，v ) i d ( v ) 一y 之所以要求和d 是因为它们在重定时变换中很有用。 算法f l o y d w a r s h a l l 首先定义忡，v ) 为： r oh=v w ( u ，v ) 一j 从e ) e 为边m 一v lm“，晓间没有边相连 算法描述如下： 1 初始化，对于任意h ，v e v 置： 第1 4 页 国防科学技术大学研究生院学位论文 x ( u ，v ) 一w ( u ，v ) y ( u ，y ) 一- d 0 ) 2 f o rk - - 1 t o f v f 对任意h ，v e v ，比较x ( u ，y ) 和x ( u ，v k ) + z 以，v ) ： a 如果x 0 ，v ) ) 工0 ，v k ) + 工v k ，v ) 更新： x ( u ，v ) 一x ( u ，v k ) + x “，p ) y 0 ，v ) 一 ，国，p ) 一d 以) b 如果x ( u ，v ) c ，则r 以) 一r ( v ) w ( u ，v ) - 1 证明： ( 1 ) 由推论2 知坼( e ) 0 因为h g ) 1 w ( e ) + ，o ) 一r 0 ) 代入得 r ( u ) 一r ( v ) s w 0 ) ( 2 ) 由引理2 知，电路q 满足垂( q ) c 则有 对所有节点扒v ，假如d0 ，y ) ，c ，则肜v ) 乏1 将彬 ，p ) 一似y ) + ， ) - r ( u ) 代入得 对于所有节点h 、v ，假如d ，v 卜c ，则，o ) 一，( v ) s 形0 ，v ) 一1 由定理1 得到一组线性不等式，是一个l p 问题，因此我们可以采用b e l l m a n - f o r d 第1 5 页 国防科学技术大学研究生院学位论文 算法来解决问题。不等式的个数为d 旷| 2 ) 个，即m o ( v 1 2 ) 。变量r 为吲维变量，所以时 间复杂度为o ( i v l 3 、。 下面我们给出一种算法求解电路的最小时钟周期电路。 算法o p t l ( c l o c kp e r i o dm i n i m i z a t i o n ) 时序逻辑电路的有向图为g1 缈，e ，d ，w ) ，求r 使巾( g ，) 最小。 1 利用算法w d 计算有向图g 中任意两个节点叭v 之间矩阵元w ( u ，v ) 和o ( u ，v ) ； 2 将所有d 以，v ) 排序； 3 在d 0 ，v ) 值域内寻找最小周期，对可能的c ，用b e l l m a n f o r d 算法看，是否满足 定理1 。 4 由3 得出最小时钟电路的r 为最优重定时。 对于c 的选取一般采用二分法，d 0 ，v ) 为i v l x l v l 的二维数组，所以c 的可能性最多有h 2 种，n 为查找次数，受i j 有 2 。, i v l 2 所以n 为0 0 9 v 1 ) ，即二分查找的计算复杂度为0 0 9 l v l ) ，b e l l m a n f o r d 算法的时间复杂度 为o c 成立，并且 已经确定h 卫一v 的某个子路径的权重大于零，那么很明显p 的权重一定大于零。则 0 ，v ) - - - r ( v ) - - r ( u ) 皂1 ，即满足定理1 ，所以路径“卫一v 是冗余的。 2 5 一种高效的最小时钟的算法( f e a s 算法) f e a s 算法( f e a s i b l ec l o c k p e r i o d t e s t ) 时序逻辑电路的有向图为g 一，e ，d ，w ) 和目的 时钟c ，按以下步骤来判断是否存在r 使垂( g r ) s c 。 1 对每一个n e v ，置r ( n ) 一0 ； 2 重复川一1 次。 ( 1 ) 计算，( v ) 状态下图g ，的形式； ( 2 ) 时序分析，用算法c p 计算g r 中每个v 的0 ) ； ( 3 ) 对每一个a ( v p c 的节点v ，置r ( v ) 一r ( v ) + 1 。 3 如果对所有节点( y ) t c ，则r ) 代表了所要求的时序重排，否则时序重排失败。 步骤2 重复川一1 次，第2 步中步骤( 1 ) 状态图更新的时间复杂度为o d e l ) ( 因为更新的是 边的权重，所以复杂度与边数吲成i e = g ) ，步骤( 2 ) 算法c p 复杂度为d o e l ) ，所以f e a s 算法的时间复杂度为o c 的节点必然为少数，所以更新g ，也 没有必要全面更新。所以本节将从这两方面入手来简化ie a s 算法，以减少算法的时间 复杂度。 3 2 1 压缩循环 当时序逻辑电路由万个组合逻辑门组成，f e a s 的算法时间复杂度为o ( n 3 ) 空间复杂 度为o ( n z ) 。然而我们发现对一个电路g 进行f e a s 重定时变换时，对于目标优化时钟 第1 8 页 国防科学技术大学研究生院学位论文 周期c ，若存在有效重定时，步