VLSI Design

VLSI circuit design involves many levels of abstraction; the most geometric of these is the physical design level, in which circuits are represented as (typically) collections of rectangles representing layers of various materials on a chip. Most of the layout, routing, and verification problems at this level involve some amount of computational geometry. At another level of abstraction, simulation of the electronic and physical properties of a chip involves interesting questions of mesh generation, in which there may be some advantage to be taken from the fact that the geometry is rectilinear and planar or nearly planar.

• Academic CAD sites on the web (primarily VLSI rather than other kinds of CAD).

• Applications of computational geometry. John Hershberger describes some geometric problems arising in his work at Mentor graphics including interpolation of thermal data, minimum spanning trees, and breakout routing in PC board design.

• Carafe -- An Inductive Fault Analysis Tool for CMOS VLSI Circuits. This VLSI layout checker finds circuit breaks using a plane sweep algorithm.

• Computational Geometry Problems in Integrated Circuit Design and Layout. Notes by D. Eppstein from a lecture by V. T. Rajan.

• Grid Evolution for Oxidation Simulation. Sahul, McKenna, and Dutton (in this paper from the NUPAD V Conf.) use adaptive quadtree meshes to simulate semiconductor oxidation.

• Level set methods for following the evolution of interfaces, J. Sethian, Berkeley. The basic idea is to solve various "advancing front" type problems such as finding shortest paths around obstacles, by evolving a surface in one higher dimension that describes the dynamics of the front. Includes movies and Java applets describing applications to VLSI design, medical image processing, noise removal from images, and robot motion planning.

• Topological Disorder and Conductance Fluctuations in Thin Films. K. Abkemeier and D. Grier use Delaunay triangulations of randomly perturbed lattice points to form resistor networks that model the electrical behavior of amorphous and polycrystalline silicon.