面向裕量优化的高效时钟偏差规划和延迟提取.pdfVIP

第20卷第lo期 计算机辅助设计与图形学学报 Vol。20，No．10 2008年10月 CoMPUTER—AIDEDDESIGN＆COMPUTERGRAPHICSOct．，2008 JOURNAl，oF 面向裕量优化的高效时钟偏差规划和延迟提取 王 逵 方 昊 程 旭 (北京大学计算机科学与技术系 北京 100871) (北京大学微处理器研究开发中心北京 100871) (wangkui@mprc．pku．edu．en) 摘 要 为了减少时钟偏差规划所需的时间，提出一种准线性时间复杂度的时钟偏差规划方法．该方法以整数来描 述延迟大小的时钟偏差规划算法，限制每次对时钟延迟调整的步进至少为1，降低了算法的时间复杂度；改变了传统 的预先生成完整的时序图作为算法输入的流程，采用一种新的增量式延迟提取策略为时钟偏差规划算法提取关键 边的权重，减少了生成时序图所需要的时间．实验结果表明，采用文中方法进行时钟偏差规划的效率很高，对包含数 千触发器的基准测试电路，其运行时间仅为数t‘秒． 关键词时钟偏差规划；时序分析；逻辑综合；时钟树综合 中图法分类号TN47 Extraction EfficientClockSkew and forSlack SchedulingDelay Kui Hao Xu Wang Fang Cheng Scienceand 100871) (DepartmentofComputer Technology，PekingUniversity，BeOing 100871) (MicroprocessorResearch＆DevelopmentCenter，PekingUniversity，Beijing AbstractToreducetheruntimeforclockskew novelnear-lineartime is scheduling，a approach ofthis isaclockskew whichuses to proposed．Thekeypart approach schedulingalgorithm integers measure incrementoftheclock tobeatleastoneateach the delay．Byrequiring latency time canbe also thetraditionalflowwhich the reduced．This changes generates complexity approach full asthe forclockskew novelincremental sequential input schedulingalgorithms．Instead，a graph extractionmethodisusedtOextractthe ofcriticalarcsforclockskew delay only weights scheduling the is