改进的基于属性不变量生成和数学归纳法的时序逻辑优化算法  

An Improved Sequential Logic Optimization Algorithm Based on Invariant Generation and Induction

作　　者：郝亚男[1,2] 杨海钢[1] 路宝珠[1,2] 崔秀海[1] 张茉莉[1,2] 

机构地区：[1]中国科学院电子学研究所可编程芯片与系统研究室,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《计算机辅助设计与图形学学报》2012年第9期1232-1240,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家重点基础研究发展计划项目(2011CB933202);国家自然科学基金(61106033)

摘　　要：为了在时序逻辑综合中使电路面积和关键路径延迟同时得到快速优化,提出一种改进的基于假设后验证的时序优化算法.在位并行随机模拟提取候选属性不变量之前,利用寄存器共享来降低初始候选不变量数目,以减少SAT程序的频繁调用;然后利用推测化简模型和改进的数学归纳法将基本条件和归纳步骤合并处理,有效地降低了电路规模和关键路径延迟,同时提高了算法运行速度.实验数据表明,文中算法使寄存器和节点规模平均下降41%和48%,关键路径延迟减小30%;与同类方法相比,该算法运行时间平均下降17%.To optimize the circuit area and critical path delay simultaneously and fast in sequential synthesis, this paper presents an improved sequential logic optimization algorithm based on an ＂assume-then-prove＂ principle. Prior to applying bit-wise parallel simulation to derive initial candidate invariants, the algorithm makes use of registers sharing to reduce the number of the initial candidate invariants, with which the number of times in calling the SAT procedure can be decreased. Then, it merges the processes of base case and induction steps to improve the induction utilizing speculative reduction model. Therefore it can effectively reduce both the area and critical path delay of the implementation circuits, and improve the computational speed. Experiment results show that the presented algorithm achieves an average reduction in number of the registers and the number of the logic nodes by 41% and 48% respectively, and the critical path delay can be reduced by 30% on average. In comparison with similar method, the average runtime of the new algorithm decreased ：7%.

关 键 词：时序优化 假设后验证 位并行随机模拟 寄存器共享 推测化简模型 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]