This is a prototype application designed to do Layout versus Schematic testing. I wrote it in order to familiarize myself with the algorithms and technology behind chip design and manufacturing.
I wrote it piecemeal because each element in the application presented a new
challenge, and it was convenient to compartmentalize the complexity. The next
step in development is to unify the components into a more manageable application.
LVS Application --source
Inverter --(layout , schematic)
NOR3--(layout , schematic)
extract.c
Reads the vector graphics from a LEF (Library Exchange Format) file
and translates it into a raster image called "extract.bmp". This bitmap
contains the layer information presented in the LEF file by using the
bits in each pixel to represent different layers. The labels for nodes
contained in the LEF file are saved for later use in the scanning phase.
It reads "extract.rules" to determine the connectivity between the
different layers and how to translate a polysilicon-diffusion junction
into a transistor.
It then uses a horizontal scan line to scan each layer looking for new nodes
or merging two nodes together. After a single scan line is complete, using
the connectivity rules in "extract.rules" it scans the junction between layers
and merges existing nodes together where appropriate. During this scanning
phase if a node passes through a labeled point, that node inherits the label.
The end result is a labeled netlist derived from the geometries in the LEF file.
Output of "extract inv.lef" 0:'gnd' 2:'NTRANS' 1:'a' 2g:'NTRANS' 4g:'PTRANS' 3:'y' 2:'NTRANS' 4:'PTRANS' 5:'vdd' 4:'PTRANS'
extract.rules
These are the rules used by "extract.c" that determine the connectivity
between layers.
There are three section to the rules file:
1) FET
2) S-JUNCTION
3) E-JUNCTION
The FET section describes the rules that translate a polysilicon-diffusion
junction into a transistor.
The S-JUNCTION (surface junction) rules define the connectivity between
different layers
The E-JUNCTION(edge junction) rules define the connectivity of different
layers if they share an edge.
nethash.c
This utility takes a homogeneous graph with optionally named vertices and
generates a hash for each vertex.
The easiest way to imagine the hashing algorithm is to envision yourself in a
labyrinth of identical rooms connected by halls. You have a finite number of
helpers with you, and your job is to determine if you have ever been to
this room before. You stand in the room and send your helpers down the
halls to the next room, where they in turn send helpers down the halls leading
from their room. This continues until you run out of helpers. Then you have
everyone return. When everyone comes back you compare notes on how many
halls your room had and how many rooms away you went.
The result is a binary file containing a 32 bit hash of each node in the graph.
Example input to nethash L 0 'gnd' L 1 'a' L 2 'NTRANS' L 3 'y' L 4 'PTRANS' L 5 'vdd' 0 2 3 2 4 5 4 1 6 7 2 6 4 7
netview.c
This utility presents the binary file generated by nethash in a human readable
form.
convert.py
This utility translates a QUISC command file (a schematic netlist generated by
by electric) into a homogeneous graph that nethash can use.
compare.py
This application ties all of the previous commands together and automates the
process of the layout versus schematic comparison.
mkgraph.py
This utility generates a random homogeneous graph to test nethash.
mixgraph.py
This utility takes a pre-existing homogeneous graph and translates it
into a subgraph.
check.py
This application uses mkgraph.py and mixgraph.py to stress/test the
nethash algorithm.