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

Fast interconnect on chip buffer insertion timing optimization analysis

作　　者：王新胜[1,2] 刘兴春[2] 喻明艳[1,2] 

机构地区：[1]哈尔滨工业大学航天学院,黑龙江哈尔滨150001 [2]哈尔滨工业大学信息与电气工程学院,山东威海264209

出　　处：《太赫兹科学与电子信息学报》2013年第6期1000-1004,共5页Journal of Terahertz Science and Electronic Information Technology

基　　金：国家科技重大专项基金资助项目(2009ZX03003-005-01)

摘　　要：互连线延时已成为制约大规模集成电路性能的瓶颈,而缓冲器插入能很好解决互连线延时。Van Ginneken(VG)算法是缓冲器插入互连时序优化的经典算法,针对此算法的3个主要操作过程进行改进,利用红黑树数据结构存储路由拓扑数据结构,缩短数据结构的更新访问时间;利用快速冗余判别和排序方法减小解方案数量和求解最优的复杂度。通过标准测试电路集ISCAS89中的电路对本文方法进行测试,测试结果表明,虽然随着电路规模增加,改进方法和传统方法运行时间都相应增加,但改进方法的优势更加明显;且随着缓冲器库规模的增加,其优势也越发明显,如只有一种缓冲器的缓冲器库,改进算法耗时为VG算法的73.28%,当有8种和20种缓冲器的缓冲器库时,耗时分别为VG算法的67.34%和63.05%。采用本文中的快速缓冲器插入算法,能有效缩短基于缓冲器插入的大规模互连时序优化时间。Along with large scale integrated bottleneck of restricting its performance. Buffer circuit development, interconnect delay has become the insertion is one of the ways to solve interconnect delay problem. VG algorithm is the classical algorithm of buffer insertion interconnection sequence optimization. The improvement is performed based on the three main operation processes of VG algorithm in this paper. Red-black tree data structure is employed to store and route topology data structure, therefore speed up the update and access of the data structure;fast redundancy discrimination and sorting method are adopted to decrease the quantity and the complexity of the optimal solution. The circuits included in standard test circuit International Symposium of Circuits and Systems in 1989 （ISCAS89） set are used to test the proposed method, and the test results show that although the running time of both the improved method and the traditional method is linearly increasing with the increasing of circuit scale, the advantages ~ft the improved algorithm are still more obvious than traditional method. Meanwhile, the advantages are also more significant along with the buffer numbers increasing in the buffer library. In the case of one buffer in the buffer library, the running time of improved algorithm is 73.28% of VG algorithm, while in the case of 8 buffers and 20 buffers in the buffer library, the running time of improved algorithm is 67.34% and 63.05% of VG, respectively. The proposed method can effectively reduce buffer insertion time in the mass interconnection sequence optimization.

关 键 词：片上互连 缓冲器插入 时序优化 

分 类 号：TN47[电子电信—微电子学与固体电子学]