An Integer Linear Programming Algorithm for Crosstalk-Constrained River Routing

Abstract

As the advances in technology bring about smaller interconnection wire spacing and higher circuit operating frequency, the effect of crosstalks on performance and even on yield in integrated circuit design and manufacturing thus increases rapidly. Consequently, reduction of crosstalks between interconnection wires becomes important in VLSI design. In this paper, we present an approach to the gridded river routing problem with the objective of minimizing crosstalks. Given an initial routing solution generated by a conventional river routing algorithm, the reduction of crosstalks is carried out by an iterative reassignment of the horizontal and vertical wire segments. To effectively and optimally perform the reassignment process, an integer linear programming (ILP) formulation is proposed in company with procedures for reducing the number of ILP variables and constraints. The experimental results show that this approach of ILP is very encouraging.