同步时序电路中的重定时算法研究

摘要

Leiserson和Saxe于1983年提出了利用重定时优化同步时序电路,并于1991年对重定时优化算法做了全面的总结.近年来,重定时技术被应用于电路设计自动化的各个领域中.遗憾的是,以前提出的重定时算法不能很好地与组合方法结合起来.而实际的电路优化系统应该将重定时算法与其它组合优化方法结合在一个优化流中,充分发挥二者的优势.该文提一种新的重定时算法,可以与其它组合优化算法很好地结合.当给定设定的时序约束条件,如目标时钟周期时,利用重定时优化可以消除时序冲突,我们称此重定时优化方法为时序调整策略.有效重定时的判定算法是重定时优化的关键,因此也是时序调整策略的关键.在时序调整策略中,有效重定时的判定算法主要分为两类,一类是基于图中最小权路径算法的有效重定时的判定算法,另一类是基于简单重定时的有效重定时的判定算法.该文在基于简单重定时的基础上提出了一种重定时算法FAM,此算法的时间计算复杂度较经典算法FEAS有所改善.

目录

文摘

英文文摘

第1章绪论

1.1项目背景

1.1.1集成电路的发展

1.1.2 IC设计开发技术的发展历史

1.2电子设计自动化中的重定时技术的理论研究

1.3重定时技术的应用研究

1.3.1高层次综合中的重定时技术

1.3.2考虑连线延时和时钟偏斜的重定时技术

1.3.3电路可测性设计中的重定时技术

1.3.4以功耗为目的的重定时技术

1.3.5重定时技术与其它优化技术相结合

1.3.6重定时在DSP电路中的应用

1.4问题的提出

1.5本文的主要内容

第2章同步时序电路的时序约束条件及时序分析

2.1引言

2.2同步时序电路的时序模型和时钟模型

2.2.1同步时序电路的时序模型

2.2.2同步时序电路的时钟模型

2.3同步时序电路的时序约束条件

2.3.1单相、沿触发同步时序电路的时序约束条件

2.3.2多相、电平触发同步时序电路的时序约束条件

2.3.3具有有效时钟规划同步时序电路的时序约束条件

2.4同步时序电路的时序分析

2.4.1单相、沿触发同步时序电路的时序分析

2.4.2多相、电平触发同步时序电路的时序分析

2.5本章小结

第3章重定时的基本理论

3.1引言

3.2同步时序电路优化中的重定时

3.2.1重定时(Retiming)

3.2.2性能驱动的重定时优化算法

3.2.3重定时变换下电路的行为等价性

3.3重定时优化后的电路的初始态计算

3.3.1重定时电路的初始态

3.3.2重定时优化后的电路的初始态计算

3.4以时钟周期为目标的重定时优化策略

3.5本章小结

第4章时序电路优化的改进重定时算法

4.1问题的引入

4.2组合逻辑电路的优化方法

4.2.1分支界限法

4.2.2动态规划法

4.2.3整数线性规划法

4.3现有的重定时算法分折

4.4改进的重定时算法

4.4.1算法思想

4.4.2算法描述

4.4.3算法时间复杂性

4.4.4与其它组合优化方法的结合

4.5本章小结

第5章基于简单重定时变换的有效重定时判定算法

5.1引言

5.2时序调整策略

5.3基于简单重定时变换的有效重定时判定算法

5.4同步时序电路中的时序调整算法FAM

5.5本章小结

结 论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致 谢