Optimizing total wire length for internal-external routings

The architecture of present day computers consists of very-large-scale integrated (VLSI) chips. VLSI technology is used in designing high-performance multipro- cessors for the purpose of parallel computing. In addition, VLSI technology is used in the design of semi-conductor storage to achieve fast memory access. Of particular interest here is the use of computers to aid in the routing stage of VLSI design. We focus on one aspect of this routing process, namely, the river routing problem.

Popular classes of routings for the river routing problem include internal rout- ings, internal-external routings, and mixed routings. Each class is a superset of the preceding class. Optimization criteria typically used in the VLSI river routing problem are area of enclosing rectangle, vertical density (number of tracks), num- ber of jogs, maximum individual wire length, and total wire length. An algorithm exists to produce internal routings with minimum total wire length, but total wire length has not been considered as an optimization criterion for internal-external or mixed routings. Here, we present a new polynomial time algorithm that produces internal-external routings with minimum total wire length.