Generalized Voronoi Diagrams, Geometric Min-Cuts, and VLSI Critical Area Extraction

  • Autor:

    Prof. Evanthia Papadopoulou (University of Lugano, Switzerland)

  • Datum: 16.10.2009

Generalized Voronoi Diagrams, Geometric Min-Cuts, and VLSI Critical Area Extraction


The Voronoi diagram is a powerful mathematical object encoding nearest neighbor information with numerous applications in diverse areas.  In this talk I will present my work on generalized Voronoi diagrams such as the Hausdorff Voronoi diagram and higher order Voronoi diagrams of segments as motivated by the VLSI Critical Area extraction problem in VLSI designs. Critical Area is a measure reflecting the sensitivity of a VLSI design to random defects during the chip manufacturing process, and its extraction is essential for modern VLSI manufacturing especially when Design for Manufacturability (DFM) changes are under consideration. I will address the critical area extraction problem for various types of faults, such as shorts, open faults, and via blocks, using generalized Voronoi diagrams. To model open faults we formulate a geometric version of the classic min-cut problem in graphs and address it through variants of generalized Voronoi diagrams. The basis of this work has resulted in an IBM-Cadence CAD tool (Voronoi CAA) that is used extensively in production mode by IBM Microelectronics for critical area extraction and yield prediction.

Zeit: Freitag, 16. Oktober 2009, 14:00 Uhr

Ort: Multimedia-Hörsaal -102, Informatik-Hauptgebäude (Geb. 50.34), Am Fasanengarten 5, 76131 Karlsruhe