快速片上互连缓冲器插入时序优化分析

摘要

本文是在经典的缓冲器插入互连时序优化算法van Ginneken算法基础上,针对其三个主要操作过程进行改进研究.添加线和添加缓冲器的过程,主要影响数据结构的更新访问时间;冗余判别方法决定最优解方案个数和求解最优插入策略的复杂度.本文利用红黑树数据结构存储路由拓扑数据结构,利用快速冗余判别和排序方法减小解方案数量和求解最优的复杂度.利用标准测试电路集ISCAS89中的电路对本文的方法进行了测试,同时把待插入的缓冲器库分为三类,测试结果表明改进方法和传统方法虽然都随着电路规模增加运行时间也相应增加,但改进算法随着电路规模的增加优势也越明显,同时随着缓冲器库规模的增加优势也越来越明显,如只有一种缓冲器的缓冲器库改进26.72％,有8种和20种缓冲器的缓冲器库时改进分别为32.66％和36.95％.