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

摘要

互连线延时已成为制约大规模集成电路性能的瓶颈，而缓冲器插入能很好解决互连线延时。Van GinnekenfvGl算法是缓冲器插入互连时序优化的经典算法，针对此算法的3个主要操作过程进行改进，利用红黑树数据结构存储路由拓扑数据结构，缩短数据结构的更新访问时间；利用快速冗余判别和排序方法减小解方案数量和求解最优的复杂度。通过标准测试电路集ISCAS89中的电路对本文方法进行测试，测试结果表明，虽然随着电路规模增加，改进方法和传统方法运行时间都相应增加，但改进方法的优势更加明显；且随着缓冲器库规模的增加，其优势也越发明显，如只有一种缓冲器的缓冲器库，改进算法耗时为VG算法的73．28％，当有8种和20种缓冲器的缓冲器库时，耗时分别为VG算法的67．34％和63．05％。采用本文中的快速缓冲器插入算法，能有效缩短基于缓冲器插入的大规模互连时序优化时间。