Interconnect Performance Optimization Based On Buffer Insertion

With the development of integrated circuits technology, the feature size ofdevices continues to scale down, which causes many new problems. Achieving timeclosure is one of the main problems. Interconnect delay plays a more and moreimportant role in system timing. Since the process technology came into nanoscalesize, the interconnect delay has exceeded the gate delay and becomes the key factorof the total chip delay. Consequently, delay optimization techniques for interconnectare vital for achieving timing closure of high performance chip.Buffer insertion is one of the main strategies for interconnect delayoptimization. For a specific routing tree, buffers can be inserted at appropriatevertices to reduce the critical path delay. To solve the buffer insertion problem fastenough, many algorithms have been presented. Different time complexity likeO(b2nlog2n) algorithms have been developed based on different number of buffertypes, sink vertices and candidate buffer insertion vertices. However， whencandidate buffer insertion vertices are quite large, the algorithm will still cost a lotof time to find the best buffer insertion.To improve the efficiency, the dissertation presents an O(b2n+bmn) timecomplexity algorithm. Assuming that the number of sinks is fixed, it is a significantimprovement over time O(b2nlog2n) algorithm. Two techniques are applied to thenew algorithm: a new pruning rule and the predictive merging technique. The newpruning rule can prune the redundant solutions utmost, and the non-redundantsolutions after pruning have some special properties, which are essential to makethe algorithm linear time complexity. The predictive merging technique uses a newdata structure, which will predict the type of the next vertex and then choose thecorresponding pruning rule. Simulation results show that for a given routing tree,the new algorithm can be faster by50%than the precious best algorithm.