The Algorithm Study Of IC Interconnect Timing Optimization

With the development of integrated circuit technology, the interconnect delayincreases while the gate delay decreases gradually. There are studies which showinterconnect delay can even occupy more than50%of the entire delay when thefeature size of technology is reduced to180nm and below. Therefore, it becomesmore and more inportant to study how to reduce interconnect delay.This thesis studies how to reduce the interconnect delay through bufferinsertion/sizing and wire sizing. First, study the existing buffer insertion/sizingalgorithms and wire sizing algorithms, and analyze their time complexity andbottlenecks of computing speed, then propose two new algorithms throughimproving existing algorithms.The buffer insertion/sizing algorithm proposed in this thesis is based on VanGinneken algorithm. If there are ‘b’ types of buffers, and ‘n’ condidate bufferinsertion points, the time complexity of Van Ginneken algorithm is O（b²n²）, and thenew algorithm’s time complexity is O（b²n（log₂n）²） in theory because two newtechniques are applied. The first technique is proposing a new redundancy checkmethod, the other technique is employing red-black trees to store candidatesolutions. Test the algorithms using benchmark ISCAS89. It can be concluded fromthe results that the new algorithm has more speed advantage over Van Ginnekenalgorithm if the scale of circuits is larger. And if more types of buffer are used, morespeed advantage is acquired, too. For example, if only one type of buffer iscandidate, the new algorithm’s runtime is73.28%of the Van Ginneken algorithm’sruntime. And if eight and twenty types of buffer are candidate, the percentage is67.34%and63.05%respectively.The wire sizing algorithm proposed in this thesis is based on the active setalgorithm which is effective in solving quadratic programming problems. And thewire sizing problem is just a convex quadratic programming problem. The newalgorithm takes advantage of the feature that the coefficient matrixes of wire sizingproblem is symmetric decomposable matrixes to speed up the computation ofcoefficient matrixes’ inverse matrixes. The wire sizing problem has another featurethat its inequality constraints of are very special. If some constraint is active，thecorresponding variable is equal to zero and can be ignored. So the number ofvariables can be reduced. Based on these two features, the time complexity of theproposed algorithm can be reduced from O（n⁴） to O（n³） in the worst case and fromO（n³） to O（n²） in the best case. Choose a set of interconnet wire length values basedon the existing research results and the interconnect wire length distribution result in Post-Place&Route benchmark ISCAS89to test the performance of the algorithm.The results show that the runtime of the new algorithm decreases and the newalgorithm’s speed advantage over active set algorithm decreases when theinterconnect wire length increases, and the advantage doesn’t change any morewhen the interconnect wire is longer than some length. It can be also concluded thatthe new algorithm’s speed advantage over active set algorithm increases when thenumber of candidate interconnet width values increases.