关键词: 缓冲器插入, 有效节点存储, 统计最短路径问题, 迪杰特斯拉算法

Abstract:

A buffer insertion method of a rapid timing optimization under process variation is proposed. The method carries out graph transformation on wire net in routing area, and so the random problem becomes a deterministic problem i.e. the buffer insertion problem for reducing time delay will be equivalent to statistics the shortest path problem. Moreover, we propose a valid node storage algorithm, which is optimized in constructing the graph process, and is greatly improving the memory space and working efficiency. In experiment section, the method is firstly used in 90 nm, 65 nm and 45 nm process global interconnect buffer insertion and analysis, and the insertion results are consistent with reference result, which confirms the validity of this method. Meanwhile, the algorithm was applied to two kinds of actual interconnect nets in integrated circuit: simple wire net and tree type wire net, which gets perfect timing optimization results based 17 inserted buffers and 3 inserted buffers respectively.

Key words: buffer insertion, valid node storage, statistical shortest path problem, Dijkstra algorithm