Project description: Layout is the physical representation of VLSI circuit, in which all kinds of electronic devices – transistors, capacitances, resistances as well as interconnects are represented by rectangular polygons made of different materials used in semiconductor technology: different kinds of doped silicon, metals and insulators. For example, a layout of CMOS inverter is shown in the picture below. The layout shows “top view” of all polygons located at different layers of die, in order to distinguish between polygons of different types, different colors are used.
Different CAD tools exist for layout verification and analysis. For example, some geometrical rules should be checked for given layout in order to ensure correct layout fabrication. Another example is a need for extraction of parasitic capacitances and resistances from layout, in order to back annotate them to timing verification tool. In both examples, the tools should be able to perform basic operations on the layout, like recognition of overlaps, calculation of area and perimeter of union of polygons etc.
In this project, students will implement a set of basic operations on the layout using specialized data structures, such as Segment Tree, Interval Tree and Priority Search Tree. The set will be implemented as a C++ library (in Linux / UNIX) with TCL interface using SWIG layer. TCL library will be used in the future for writing more complicated layout algorithms.
Prerequisites: Programming in C++. Any course on data structures and algorithms.