FAST TECHNIQUE FOR LINEAR WIRE-LENGTH CALCULATION OF VERY LARGE SCALE INTEGRATION CIRCUITS

Abstract

Many algorithms for very large scale integration placement improvement require fast calculation of the linear wire-length depending on the position of given cell and assuming other cells fixed. Particularly it is required to find optimal locations of the cell. This paper suggests a fast algorithm for this problem. Complexity of the algorithm is $O(n \log n)$, where $n$ is the number of nets of this cell.