Universität zu Köln

Liers, Frauke, Nieberg, Tim and Pardella, Gregor (2011). Via Minimization in VLSI Chip Design - Application of a Planar Max-Cut Algorithm. Working Paper.

Preview

PDF zaik2011-630.pdf Download (239kB) | Preview

Abstract

The design of very large scale integrated (VLSI) chips is an exciting area of applied discrete mathematics.Due to the intractability of the majority of the problems, and also due to the huge instance sizes, the design process is decomposed into various sub-problems. In this paper, for a given detailed routing solution, we revisit the assignment of layers to net segments. For connected metalized nets, a layer change is accomplished by a vertical interconnection area (via). We seek to minimize the use of these vias as vias not only reduce the electrical reliability and performance of the chip, but also decrease the manufacturing yield substantially. In the general case, the via minimization problem is NP-hard. However, it is known that the two layer via minimization problem can be solved as a maximum cut problem on a planar graph which is a polynomial task.The focus of this paper is to use this approach for modern real-world chips. From the roughly two dozen wiring layers present, we take two adjacent ones for the via minimization. As a core-routine, we use a fast maximum cut algorithm on planar graphs. For being able to use the solutions in practice, we integrate practically relevant design rule constraints at the expense of potentially using further vias. Thus, our solution satisfies the additional constraints present in actual current designs. The computational results show that our implementation is fast on real-world instances as it usually computes a solution within a few minutes CPU time only. Moreover, often a considerable amount of vias can be saved.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Nieberg, Tim UNSPECIFIED UNSPECIFIED UNSPECIFIED Pardella, Gregor UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550186
Date:	2011
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55018