658 lines
37 KiB
HTML
658 lines
37 KiB
HTML
<html>
|
||
|
||
<head>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
|
||
<title>Polygon Usage</title>
|
||
</head>
|
||
|
||
<body>
|
||
|
||
<h1>Layout Versus Schematic Tutorial</h1>
|
||
<p>In this tutorial we will implement a toy VLSI layout verification
|
||
application. In VLSI CAD an important step of design is the sign off check
|
||
that verifies that the physical layout as drawn by mask designers and automated
|
||
tools implements the logical schematic specified by design engineers.
|
||
Physical layout is modeled as polygons on layers that are used to print the
|
||
layout to the silicon wafer during manufacture. It is much better to find
|
||
physical design mistakes before spending millions of dollars to prepare
|
||
lithography masks and run a test lot of wafers.</p>
|
||
<p>Real layout file formats are binary and often compressed and represent a
|
||
folded hierarchical model of layout where a group of polygons can be grouped
|
||
into a cell and instantiated as a group into other cells. For this
|
||
tutorial we assume a simplified ascii layout file format with no design
|
||
hierarchy, which we would call "flat" in VLSI jargon. Similarly we assume
|
||
a flat, ascii logical schematic net list file format. A net is a named
|
||
electrical connection in a circuit design. The goal of the layout
|
||
verification tutorial is to parse these two file formats, apply geometry
|
||
operations provided by Boost.Polygon on the layout data to generate a logical
|
||
schematic that represents what is implemented in the physical layout and then
|
||
compare the input schematic with the generated schematic to determine whether
|
||
they are the same.</p>
|
||
<p>First let us define some objects that we will need in the design of our toy
|
||
layout verification application:</p>
|
||
<p>Layout Rectangle: An axis-parallel rectangle with a layer associated<br>
|
||
Layout Pin: An axis-parallel rectangle with a layer and net (electrical signal)
|
||
name associated<br>
|
||
Layout Database: An associative container of layer name to polygon set<br>
|
||
Connectivity Database: An associative container of net name to layout database<br>
|
||
Physical Device: A specific geometric arrangement on several layers with one or
|
||
more input net and one output net<br>
|
||
Logical Net: A named graph node<br>
|
||
Logical Device: An un-named graph node with a device type<br>
|
||
Logical Pin: A special net that defines an input or output for the circuit<br>
|
||
Schematic Database: A graph consisting of nets and logical
|
||
devices</p>
|
||
<p>Next let's define the sequence of operations performed by our toy
|
||
layout versus schematic application:</p>
|
||
<p>Parse Layout: Stream layout rectangles and polygons into a layout database
|
||
and stream layout pins into a connectivity database<br>
|
||
Extract Connectivity: Add polygons from layout database to connectivity database
|
||
by physical touch or overlap relationship<br>
|
||
Extract Devices: Populate a schematic database with logical devices based on
|
||
physical devices identified within the layout geometry and extract their
|
||
terminals from the
|
||
connectivity database<br>
|
||
Extract Net List: Complete graph represented in schematic database derived from
|
||
layout<br>
|
||
Parse Schematic: Stream logical nets, devices and pins into a schematic
|
||
database<br>
|
||
Compare Schematics: Evaluate whether extracted schematic database is equivalent
|
||
to input schematic database and output result</p>
|
||
<p>To test our application we will extract single logic gates. A logic
|
||
gate is several transistors that work together to perform a specific logic
|
||
function. Logic functions include the commonly understood Boolean logic
|
||
operations such as Boolean AND, OR, XOR and INVERT. Also frequently used
|
||
are NAND and NOR, which are respectively AND and OR operations followed by an
|
||
INVERT operation. A NAND gate can be implemented in the CMOS circuit
|
||
family with four transistors. The NAND gate has two inputs and one output.
|
||
Each input goes to two transistors, one p-type transistor and one n-type
|
||
transistor. The "p" stands for positive and the "n" stands for negative.
|
||
When the p-type transistor is on
|
||
it pulls the output up to the same voltage as the voltage source. When the
|
||
n-type transistor is on it pulls the output down to the same voltage as the
|
||
ground. The process of creating a p-type transistor begins by "doping" the silicon
|
||
substrate to create n-type material. This area of n-type material will be
|
||
called the NWELL layer in our test data. Within the area of NWELL a
|
||
p-diffusion area is created by further doping the silicon to create p-type
|
||
material. This area of p-type material will be called PDIFF in our test
|
||
data. Through the middle of a PDIFF area bars of poly-silicon are grown
|
||
that create conductive lines over the diffusion area. The area of
|
||
poly-silicon material will be called POLY in our test data. Under some of these
|
||
poly-silicon lines a thin layer of silicon-oxide provides insulation but allows
|
||
the voltage field of the poly-silicon to interact with the diffusion. Each
|
||
of these insulated poly-silicon lines is the "gate" of a transistor.
|
||
The gate area will be called GATE in our test data. When the
|
||
voltage at the gate is the same as the ground voltage the p-type transistor is
|
||
"on" and can pass current from the voltage source to the output . The
|
||
poly-silicon lines that are not insulated create electrical connections to the
|
||
transistor for output signals and source voltage. The n-type transistor
|
||
differs from the p-type in that its diffusion is n-type material outside of NWELL area. Current can pass from the output to the ground when the
|
||
voltage at the gate of the n-type transistor is at the source voltage level.
|
||
Above the poly-silicon layer is a layer of silicon-oxide insulator with holes
|
||
cut out of it that get filled in with metal. These metal filled holes are
|
||
called vias and we will refer to this layer as VIA0 in our test data. On
|
||
top of VIA0 is a layer of metal polygons with silicon oxide insulator between
|
||
them. These metal polygons are wires and we will call them METAL1 in our
|
||
test data. The Layout Pins in our test data will be on METAL1. In a
|
||
NAND gate the two n-type transistors are configured in series, meaning that the
|
||
output of one is the input voltage source of the other. Only if both
|
||
n-type transistors of a NAND gate are "on" will the output be connected to
|
||
ground, signifying a logical "false". The two p-type transistors in a NAND
|
||
gate are configured in parallel. If either input to the NAND gate is a
|
||
logical "false" the p-type transistor it is connected to will be "on" and the
|
||
output of the gate will be a logical "true" because the transistor will connect
|
||
it to the voltage supply. The diagram below is an example of how a NAND
|
||
gate might be laid out and is not drawn to scale for any real process
|
||
technology. The diffusion material is intended to be cut away under the
|
||
gate material by a Boolean NOT operation and is represented as solid bars under
|
||
the gates of transistors only for convenience of drawing.</p>
|
||
<p>
|
||
<img border="0" src="images/NAND.PNG" width="602" height="387"></p>
|
||
<p>The following is the input layout file for the above NAND gate layout,
|
||
rectangle format is XL XH YL YH:</p>
|
||
<p><font face="Courier New" size="2">Rectangle 0 60 24 48 NWELL<br>
|
||
Rectangle 3 57 32 43 PDIFF<br>
|
||
Rectangle 3 57 5 16 NDIFF<br>
|
||
Rectangle 5 7 0 17 POLY<br>
|
||
Rectangle 5 7 22 45 POLY<br>
|
||
Rectangle 17 19 3 45 POLY<br>
|
||
Rectangle 29 31 31 48 POLY<br>
|
||
Rectangle 41 43 3 45 POLY<br>
|
||
Rectangle 53 55 3 45 POLY<br>
|
||
Rectangle 17 19 4 17 GATE<br>
|
||
Rectangle 17 19 31 44 GATE<br>
|
||
Rectangle 41 43 4 17 GATE<br>
|
||
Rectangle 41 43 31 44 GATE<br>
|
||
Rectangle 5 7 0 2 VIA0<br>
|
||
Rectangle 5 7 23 25 VIA0<br>
|
||
Rectangle 17 19 28 30 VIA0<br>
|
||
Rectangle 29 31 46 48 VIA0<br>
|
||
Rectangle 41 43 18 20 VIA0<br>
|
||
Rectangle 53 55 23 25 VIA0<br>
|
||
Rectangle 0 60 0 2 METAL1<br>
|
||
Rectangle 3 57 28 30 METAL1<br>
|
||
Rectangle 0 60 46 48 METAL1<br>
|
||
Rectangle 3 57 18 20 METAL1<br>
|
||
Rectangle 3 57 23 25 METAL1<br>
|
||
Pin 29 31 0 2 METAL1 GND<br>
|
||
Pin 29 31 23 25 METAL1 OUTPUT</font><font face="Courier New" size="2"><br>
|
||
Pin 29 31 28 30 METAL1 INPUT1</font><font face="Courier New" size="2"><br>
|
||
Pin 29 31 46 48 METAL1 VDD<br>
|
||
Pin 29 31 18 20 METAL1 INPUT2</font></p>
|
||
<p>
|
||
<img border="0" src="images/nands.PNG" width="421" height="402"></p>
|
||
<p>The following is the logic schematic net list file for the above NAND gate
|
||
schematic:</p>
|
||
<p><font face="Courier New" size="2">Pin OUTPUT<br>Pin INPUT1<br>Pin INPUT2<br>
|
||
Pin VDD<br>Pin GND<br>Device PTRANS VDD INPUT1 OUTPUT<br>Device PTRANS VDD
|
||
INPUT2 OUTPUT<br>Device NTRANS GND INPUT1 NET1<br>Device NTRANS NET1 INPUT2
|
||
OUTPUT</font></p>
|
||
<p>A human can look at this schematic and compare it to the drawn layout of the
|
||
NAND gate above to verify that the drawn layout matches what the schematic says
|
||
in a few seconds. If you do that now you will probably find the p and
|
||
n-type transistors and trace the connectivity of the inputs and power to the
|
||
terminals of the transistors and then to the output. Since there are on
|
||
the order of one billion transistors on a single chip these days we need to go a
|
||
lot faster than humans can inspect layout and make fewer mistakes. Using polygon set operations
|
||
and polygon connectivity extraction provided by Boost.Polygon we will automate
|
||
the identification of transistors and the tracing of connectivity. Based
|
||
on this
|
||
<a href="analysis.htm">analysis</a> of Boost.Polygon performance we can expect
|
||
this methodology to easily scale up to million gate blocks on standard
|
||
workstations and arbitrarily large designs given sufficient system memory.
|
||
let's start
|
||
by implementing some data structures for our application.</p>
|
||
<p><font face="Courier New" size="2">struct layout_rectangle {<br>
|
||
int xl, yl, xh, yh;<br>
|
||
std::string layer;<br>
|
||
};</font></p>
|
||
<p>Our layout rectangle is nice and minimal, just enough to store its data.
|
||
It is defined in <a href="tutorial/layout_rectangle.hpp">layout_rectangle.hpp</a>. Next
|
||
let's implement the layout
|
||
pin in a similar way.</p>
|
||
<p><font face="Courier New" size="2">struct layout_pin {<br>
|
||
int xl, yl, xh, yh;<br>
|
||
std::string layer;<br>
|
||
std::string net;<br>
|
||
};</font></p>
|
||
<p>Our layout pin is defined in <a href="tutorial/layout_pin.hpp">layout_pin.hpp</a>. Now
|
||
let's define a layout database object and populate it from our parsed
|
||
layout data in in <a href="tutorial/layout_database.hpp">layout_database.hpp</a>.</p>
|
||
<p><font face="Courier New" size="2">typedef std::map<std::string,
|
||
boost::polygon::polygon_90_set_data<int> > layout_database;<br>
|
||
<br>
|
||
//map the layout rectangle data type to the boost::polygon::rectangle_concept<br>
|
||
namespace boost { namespace polygon{<br>
|
||
template <><br>
|
||
struct rectangle_traits<layout_rectangle> {<br>
|
||
typedef int coordinate_type;<br>
|
||
typedef interval_data<int> interval_type;<br>
|
||
static inline interval_type get(const layout_rectangle&
|
||
rectangle, orientation_2d orient) {<br>
|
||
if(orient == HORIZONTAL)<br>
|
||
return interval_type(rectangle.xl,
|
||
rectangle.xh);<br>
|
||
return interval_type(rectangle.yl, rectangle.yh);<br>
|
||
}<br>
|
||
};<br>
|
||
<br>
|
||
template <><br>
|
||
struct geometry_concept<layout_rectangle> { typedef rectangle_concept
|
||
type; };<br>
|
||
}}<br>
|
||
<br>
|
||
//insert layout rectangles into a layout database<br>
|
||
inline void populate_layout_database(layout_database& layout, std::vector<layout_rectangle>&
|
||
rects) {<br>
|
||
for(std::size_t i = 0; i < rects.size(); ++i) {<br>
|
||
layout[rects[i].layer].insert(rects[i]);<br>
|
||
}<br>
|
||
}</font></p>
|
||
<p>We don't need to insert pins into the layout database because it doesn't know
|
||
anything about connectivity, just geometry. However, we do need to know
|
||
something about connectivity to compare a schematic to a layout, so we need to
|
||
define our connectivity database and some logical objects. First we define
|
||
an object for a logical device in <a href="tutorial/device.hpp">device.hpp</a>.
|
||
Since we are lazy this object does double duty as a pin and both types of
|
||
transistor. A traditional object oriented design might declare a base
|
||
class with virtual destructor and derive every device from that. Since we
|
||
aren't paid by the line of code let's just keep things simple.</p>
|
||
<p><font face="Courier New" size="2">struct device {<br>
|
||
std::string type;<br>
|
||
std::vector<std::string> terminals;<br>
|
||
};</font></p>
|
||
<p>Now let's define a schematic database object in
|
||
<a href="tutorial/schematic_database.hpp">schematic_database.hpp</a> and populate it from our parsed
|
||
schematic data.</p>
|
||
<p><font face="Courier New"><font size="2">struct schematic_database{<br>
|
||
std::vector<device> devices;<br>
|
||
std::map<std::string, std::set<std::size_t> > nets;<br>
|
||
};<br>
|
||
<br>
|
||
//given a vector of devices populate the map of net name to set of device index<br>
|
||
inline void extract_netlist(std::map<std::string, std::set<std::size_t> >& nets,<br>
|
||
|
||
std::vector<device>& devices) {<br>
|
||
for(std::size_t i = 0; i < devices.size(); ++i) {<br>
|
||
for(std::size_t j = 0; j < devices[i].terminals.size(); ++j)
|
||
{<br>
|
||
//create association between net name and device
|
||
id<br>
|
||
|
||
nets[devices[i].terminals[j]].insert(nets[devices[i].terminals[j]].end(), i);<br>
|
||
}<br>
|
||
}<br>
|
||
}</font></font></p>
|
||
<p>Our schematic database is just a vector of devices, which are associated to
|
||
nets by name through their terminals and a map of net name to set of device
|
||
index into the vector, which completes the graph by associating nets with their
|
||
devices. Given the devices and their terminal nets we easily build the
|
||
mapping from nets to devices with the extract_netlist operation. Now we
|
||
are ready to start working on extracting our layout to a derived schematic
|
||
database. However, first we need to build a physical connectivity database
|
||
with geometry in it before we can build a logical connectivity database from the
|
||
layout. We define a simple connectivity database in
|
||
<a href="tutorial/connectivity_database.hpp">connectivity_database.hpp</a> as a
|
||
map of net name to layout database of geometry connected to that net and
|
||
populate it with the layout database and pin data.</p>
|
||
<p><font size="2" face="Courier New">typedef std::map<std::string,
|
||
layout_database > connectivity_database;<br>
|
||
<br>
|
||
//map layout pin data type to boost::polygon::rectangle_concept<br>
|
||
namespace boost { namespace polygon{<br>
|
||
template <><br>
|
||
struct rectangle_traits<layout_pin> {<br>
|
||
typedef int coordinate_type;<br>
|
||
typedef interval_data<int> interval_type;<br>
|
||
static inline interval_type get(const layout_pin& pin,
|
||
orientation_2d orient) {<br>
|
||
if(orient == HORIZONTAL)<br>
|
||
return interval_type(pin.xl, pin.xh);<br>
|
||
return interval_type(pin.yl, pin.yh);<br>
|
||
}<br>
|
||
};<br>
|
||
<br>
|
||
template <><br>
|
||
struct geometry_concept<layout_pin> { typedef rectangle_concept type; };<br>
|
||
}}</font></p>
|
||
<p><font size="2" face="Courier New">//given a layout_database we populate a
|
||
connectivity database<br>
|
||
inline void populate_connectivity_database(connectivity_database& connectivity,<br>
|
||
|
||
std::vector<layout_pin>& pins, layout_database& layout) {<br>
|
||
using namespace boost::polygon;<br>
|
||
using namespace boost::polygon::operators;<br>
|
||
for(std::size_t i = 0; i < pins.size(); ++i) {<br>
|
||
connectivity[pins[i].net][pins[i].layer].insert(pins[i]);<br>
|
||
}<br>
|
||
int internal_net_suffix = 0;<br>
|
||
//connect metal1 layout to pins which were on metal1<br>
|
||
connect_layout_to_layer(connectivity, layout["METAL1"], "METAL1", <br>
|
||
|
||
"METAL1", "__internal_net_", internal_net_suffix);<br>
|
||
//connect via0 layout to metal1<br>
|
||
connect_layout_to_layer(connectivity, layout["VIA0"], "VIA0", <br>
|
||
|
||
"METAL1", "__internal_net_", internal_net_suffix);<br>
|
||
//poly needs to have gates subtracted from it to prevent shorting through
|
||
transistors<br>
|
||
polygon_set poly_not_gate = layout["POLY"] - layout["GATE"];<br>
|
||
//connect poly minus gate to via0<br>
|
||
connect_layout_to_layer(connectivity, poly_not_gate, "POLY", <br>
|
||
|
||
"VIA0", "__internal_net_", internal_net_suffix);<br>
|
||
//we don't want to short signals through transistors so we subtract the
|
||
gate regions<br>
|
||
//from the diffusions<br>
|
||
polygon_set diff_not_gate = (layout["PDIFF"] + layout["NDIFF"]) -
|
||
layout["GATE"];<br>
|
||
//connect diffusion minus gate to poly<br>
|
||
//Note that I made up the DIFF layer name for combined P and NDIFF<br>
|
||
connect_layout_to_layer(connectivity, diff_not_gate, "DIFF", <br>
|
||
|
||
"POLY", "__internal_net_", internal_net_suffix);<br>
|
||
//connect gate to poly to make connections through gates on poly<br>
|
||
connect_layout_to_layer(connectivity, layout["GATE"], "GATE", <br>
|
||
|
||
"POLY", "__internal_net_", internal_net_suffix);<br>
|
||
//now we have traced connectivity of the layout down to the transistor
|
||
level<br>
|
||
//any polygons not connected to pins have been assigned internal net
|
||
names<br>
|
||
}</font></p>
|
||
<p>This populate connectivity database function is our first real use of
|
||
Boost.Polygon in our application. Here we are doing Boolean (polygon set)
|
||
operations on layout layers to merge together the PDIFF and NDIFF layers and cut
|
||
away the GATE layer from the result, for example. We connect up the layout
|
||
starting from the pins and working our way down the layer stack to the
|
||
transistor level. It would work equally well to work our way up the layer
|
||
stack, or connect things up in any order, really, but this way produces fewer
|
||
internal temporary nets that need to be merged when connections between them are
|
||
discovered later. The connect layout to layer function used above needs to
|
||
be implemented before we can populate our connectivity database.</p>
|
||
<p><font size="2" face="Courier New">inline void
|
||
connect_layout_to_layer(connectivity_database& connectivity, polygon_set&
|
||
layout, <br>
|
||
|
||
std::string layout_layer, std::string layer,<br>
|
||
|
||
std::string net_prefix, int& net_suffix) {<br>
|
||
if(layout_layer.empty())<br>
|
||
return;<br>
|
||
boost::polygon::connectivity_extraction_90<int> ce;<br>
|
||
std::vector<std::string> net_ids;<br>
|
||
for(connectivity_database::iterator itr = connectivity.begin(); itr !=
|
||
connectivity.end(); ++itr) {<br>
|
||
net_ids.push_back((*itr).first);<br>
|
||
ce.insert((*itr).second[layer]);<br>
|
||
}<br>
|
||
std::vector<polygon> polygons;<br>
|
||
layout.get_polygons(polygons);<br>
|
||
std::size_t polygon_id_offset = net_ids.size();<br>
|
||
for(std::size_t i = 0; i < polygons.size(); ++i) {<br>
|
||
ce.insert(polygons[i]);<br>
|
||
}<br>
|
||
std::vector<std::set<int> > graph(polygons.size() + net_ids.size(),
|
||
std::set<int>());<br>
|
||
ce.extract(graph);<br>
|
||
std::vector<int> polygon_color(polygons.size() + net_ids.size(), 0);<br>
|
||
//for each net in net_ids populate connected component with net<br>
|
||
for(std::size_t node_id = 0; node_id < net_ids.size(); ++node_id) {<br>
|
||
populate_connected_component(connectivity, polygons,
|
||
polygon_color, graph, node_id, <br>
|
||
polygon_id_offset, net_ids[node_id], net_ids, <br>
|
||
net_prefix, layout_layer);<br>
|
||
}<br>
|
||
//for each polygon_color that is zero populate connected component with
|
||
net_prefix + net_suffix++<br>
|
||
for(std::size_t i = 0; i < polygons.size(); ++i) {<br>
|
||
if(polygon_color[i + polygon_id_offset] == 0) {<br>
|
||
std::stringstream ss(std::stringstream::in |
|
||
std::stringstream::out);<br>
|
||
ss << net_prefix << net_suffix++;<br>
|
||
std::string internal_net; <br>
|
||
ss >> internal_net;<br>
|
||
populate_connected_component(connectivity,
|
||
polygons, polygon_color, graph, <br>
|
||
i + polygon_id_offset, <br>
|
||
polygon_id_offset, internal_net, net_ids, <br>
|
||
net_prefix, layout_layer);<br>
|
||
}<br>
|
||
}<br>
|
||
}</font></p>
|
||
<p>The connect layout to layer function uses the connectivity extraction feature
|
||
of Boost.Polyon to build a connectivity graph for polygons on the input polygon
|
||
set and in the connectivity database on the specified layer. It then finds
|
||
polygons associated with existing nets in the connectivity database through
|
||
graph traversal and inserts them into the connectivity database. Finally,
|
||
polygons that weren't connected to existing nets are inserted into the
|
||
connectivity database on auto-generated internal net names. The insertion
|
||
of a connected component into the connectivity database is handled by the
|
||
recursive traversal of the connectivity graph that we implement next.</p>
|
||
<p><font size="2" face="Courier New">inline void populate_connected_component<br>
|
||
(connectivity_database& connectivity, std::vector<polygon>& polygons, <br>
|
||
std::vector<int> polygon_color, std::vector<std::set<int> >& graph, <br>
|
||
std::size_t node_id, std::size_t polygon_id_offset, std::string& net, <br>
|
||
std::vector<std::string>& net_ids, std::string net_prefix,<br>
|
||
std::string& layout_layer) {<br>
|
||
if(polygon_color[node_id] == 1)<br>
|
||
return;<br>
|
||
polygon_color[node_id] = 1;<br>
|
||
if(node_id < polygon_id_offset && net_ids[node_id] != net) {<br>
|
||
//merge nets in connectivity database<br>
|
||
//if one of the nets is internal net merge it into the other<br>
|
||
std::string net1 = net_ids[node_id];<br>
|
||
std::string net2 = net;<br>
|
||
if(net.compare(0, net_prefix.length(), net_prefix) == 0) {<br>
|
||
net = net1;<br>
|
||
std::swap(net1, net2);<br>
|
||
} else {<br>
|
||
net_ids[node_id] = net;<br>
|
||
}<br>
|
||
connectivity_database::iterator itr =
|
||
connectivity.find(net1);<br>
|
||
if(itr != connectivity.end()) {<br>
|
||
for(layout_database::iterator itr2 = (*itr).second.begin();<br>
|
||
itr2 != (*itr).second.end();
|
||
++itr2) {<br>
|
||
connectivity[net2][(*itr2).first].insert((*itr2).second);<br>
|
||
}<br>
|
||
connectivity.erase(itr);<br>
|
||
}<br>
|
||
}<br>
|
||
if(node_id >= polygon_id_offset)<br>
|
||
connectivity[net][layout_layer].insert(polygons[node_id -
|
||
polygon_id_offset]);<br>
|
||
for(std::set<int>::iterator itr = graph[node_id].begin();<br>
|
||
itr != graph[node_id].end(); ++itr) {<br>
|
||
populate_connected_component(connectivity, polygons,
|
||
polygon_color, graph, <br>
|
||
*itr, polygon_id_offset, net, net_ids, net_prefix,
|
||
layout_layer);<br>
|
||
}<br>
|
||
}<br>
|
||
<br>
|
||
</font>We want to merge internally generated nets into pin nets, which is the
|
||
most complicated part of this simple procedure. Now that we have our
|
||
connectivity database extracted from pins down to transistors we need to extract
|
||
our transistors and establish the relationship between transistor terminals and
|
||
nets in our connectivity database. First let's extract transistors with
|
||
the functions defined in defined in <a href="tutorial/extract_devices.hpp">
|
||
extract_devices.hpp</a>.</p>
|
||
<p><font size="2" face="Courier New">typedef boost::polygon::connectivity_extraction_90<int>
|
||
connectivity_extraction;<br>
|
||
inline std::vector<std::set<int> ><br>
|
||
extract_layer(connectivity_extraction& ce, std::vector<std::string>& net_ids,<br>
|
||
|
||
connectivity_database& connectivity, polygon_set& layout,<br>
|
||
|
||
std::string layer) {<br>
|
||
for(connectivity_database::iterator itr = connectivity.begin(); itr !=
|
||
connectivity.end(); ++itr) {<br>
|
||
net_ids.push_back((*itr).first);<br>
|
||
ce.insert((*itr).second[layer]);<br>
|
||
}<br>
|
||
std::vector<polygon> polygons;<br>
|
||
layout.get_polygons(polygons);<br>
|
||
for(std::size_t i = 0; i < polygons.size(); ++i) {<br>
|
||
ce.insert(polygons[i]);<br>
|
||
}<br>
|
||
std::vector<std::set<int> > graph(polygons.size() + net_ids.size(),
|
||
std::set<int>());<br>
|
||
ce.extract(graph);<br>
|
||
return graph;<br>
|
||
}</font></p>
|
||
<p>This extract layer algorithm constructs a connectivity graph between polygons
|
||
in the input polygon set and polygons in the given layer of the connectivity
|
||
database. It is used to form the association between transistors and their
|
||
terminal nets in the function for extracting a specific transistor type.</p>
|
||
<p><font size="2" face="Courier New">inline void extract_device_type(std::vector<device>&
|
||
devices, connectivity_database& connectivity,<br>
|
||
|
||
polygon_set& layout, std::string type) {<br>
|
||
//recall that P and NDIFF were merged into one DIFF layer in the
|
||
connectivity database<br>
|
||
//find the two nets on the DIFF layer that interact with each transistor<br>
|
||
//and then find the net on the poly layer that interacts with each
|
||
transistor<br>
|
||
boost::polygon::connectivity_extraction_90<int> cediff;<br>
|
||
std::vector<std::string> net_ids_diff;<br>
|
||
std::vector<std::set<int> > graph_diff =<br>
|
||
extract_layer(cediff, net_ids_diff, connectivity, layout,
|
||
"DIFF");<br>
|
||
boost::polygon::connectivity_extraction_90<int> cepoly;<br>
|
||
std::vector<std::string> net_ids_poly;<br>
|
||
std::vector<std::set<int> > graph_poly =<br>
|
||
extract_layer(cepoly, net_ids_poly, connectivity, layout,
|
||
"POLY");<br>
|
||
std::vector<device> tmp_devices(graph_diff.size() - net_ids_poly.size());<br>
|
||
for(std::size_t i = net_ids_poly.size(); i < graph_diff.size(); ++i) {<br>
|
||
tmp_devices[i - net_ids_diff.size()].type = type;<br>
|
||
tmp_devices[i - net_ids_diff.size()].terminals = std::vector<std::string>(3,
|
||
std::string());<br>
|
||
std::size_t j = 0;<br>
|
||
for(std::set<int>::iterator itr = graph_diff[i].begin();<br>
|
||
itr != graph_diff[i].end(); ++itr,
|
||
++j) {<br>
|
||
if(j == 0) {<br>
|
||
tmp_devices[i - net_ids_diff.size()].terminals[0]
|
||
= net_ids_diff[*itr];<br>
|
||
} else if(j == 1) {<br>
|
||
tmp_devices[i - net_ids_diff.size()].terminals[2]
|
||
= net_ids_diff[*itr];<br>
|
||
} else {<br>
|
||
//error, too many diff connections<br>
|
||
tmp_devices[i - net_ids_diff.size()].terminals
|
||
= std::vector<std::string>(3, std::string());<br>
|
||
}<br>
|
||
}<br>
|
||
j = 0;<br>
|
||
for(std::set<int>::iterator itr = graph_poly[i].begin();<br>
|
||
itr != graph_poly[i].end(); ++itr,
|
||
++j) {<br>
|
||
if(j == 0) {<br>
|
||
tmp_devices[i - net_ids_diff.size()].terminals[1]
|
||
= net_ids_poly[*itr];<br>
|
||
} else {<br>
|
||
//error, too many poly connections<br>
|
||
tmp_devices[i - net_ids_poly.size()].terminals
|
||
= std::vector<std::string>(3, std::string());<br>
|
||
}<br>
|
||
}<br>
|
||
}<br>
|
||
<br>
|
||
devices.insert(devices.end(), tmp_devices.begin(), tmp_devices.end());<br>
|
||
}</font></p>
|
||
<p>We append transistors onto the vector of devices with their terminals
|
||
populated with net names extracted from the connectivity database.
|
||
Transistors' terminals are connected through the POLY and DIFF layers where DIFF
|
||
contains both PDIFF and NDIFF. The connection to POLY layer is the gate of
|
||
the transistor while the connections to DIFF on either side of the channel of
|
||
the transistor are the source and drain. We can use this to extract are p
|
||
and n-type transistors. <font size="2" face="Courier New"><br>
|
||
<br>
|
||
//populates vector of devices based on connectivity and layout data<br>
|
||
inline void extract_devices(std::vector<device>& devices, connectivity_database&
|
||
connectivity,<br>
|
||
|
||
layout_database& layout) {<br>
|
||
using namespace boost::polygon::operators;<br>
|
||
//p-type transistors are gate that interact with p diffusion and nwell<br>
|
||
polygon_set ptransistors = layout["GATE"];<br>
|
||
ptransistors.interact(layout["PDIFF"]);<br>
|
||
ptransistors.interact(layout["NWELL"]);<br>
|
||
//n-type transistors are gate that interact with n diffusion and not
|
||
nwell<br>
|
||
polygon_set ntransistors = layout["GATE"];<br>
|
||
ntransistors.interact(layout["NDIFF"]);<br>
|
||
polygon_set not_ntransistors = ntransistors;<br>
|
||
not_ntransistors.interact(layout["NWELL"]);<br>
|
||
ntransistors -= not_ntransistors;<br>
|
||
extract_device_type(devices, connectivity, ptransistors, "PTRANS");<br>
|
||
extract_device_type(devices, connectivity, ntransistors, "NTRANS");<br>
|
||
}</font></p>
|
||
<p>The extract devices procedure makes some more use of Boost.Polygon Boolean
|
||
operations on the layout data when we exclude GATE material over NDIFF that
|
||
isn't also over NWELL to extract our n-type transistors. We also are using
|
||
the "interact" operation on polygon gets, which is implemented in terms of
|
||
connectivity extraction and retains all polygons of a polygon set that touch or
|
||
overlap polygons from another polygon set. Now that we have a vector of
|
||
devices we can build a schematic database by calling the extract_netlist
|
||
function. We can then compare the extracted schematic from the schematic
|
||
read in from file with the functions defined in
|
||
<a href="tutorial/compare_schematics.hpp">compare_schematics.hpp</a>.
|
||
Since comparing two schematics has no geometric aspect we won't go into that
|
||
procedure here in the tutorial and will skip to the integration of all these
|
||
procedures in defined in <a href="tutorial/extract.cpp">extract.cpp</a> to build
|
||
the layout to schematic comparison algorithm.</p>
|
||
<p><font size="2" face="Courier New">bool compare_files(std::string layout_file,
|
||
std::string schematic_file) {<br>
|
||
std::ifstream sin(schematic_file.c_str());<br>
|
||
std::ifstream lin(layout_file.c_str());<br>
|
||
<br>
|
||
std::vector<layout_rectangle> rects;<br>
|
||
std::vector<layout_pin> pins;<br>
|
||
parse_layout(rects, pins, lin);<br>
|
||
<br>
|
||
schematic_database reference_schematic;<br>
|
||
parse_schematic_database(reference_schematic, sin);<br>
|
||
<br>
|
||
layout_database layout;<br>
|
||
populate_layout_database(layout, rects);<br>
|
||
<br>
|
||
connectivity_database connectivity;<br>
|
||
populate_connectivity_database(connectivity, pins, layout);<br>
|
||
<br>
|
||
schematic_database schematic;<br>
|
||
std::vector<device>& devices = schematic.devices;<br>
|
||
for(std::size_t i = 0; i < pins.size(); ++i) {<br>
|
||
devices.push_back(device());<br>
|
||
devices.back().type = "PIN";<br>
|
||
devices.back().terminals.push_back(pins[i].net);<br>
|
||
}<br>
|
||
extract_devices(devices, connectivity, layout);<br>
|
||
extract_netlist(schematic.nets, devices);<br>
|
||
return compare_schematics(reference_schematic, schematic);<br>
|
||
}</font></p>
|
||
<p><font face="Courier New" size="2">int main(int argc, char **argv) {<br>
|
||
if(argc < 3) {<br>
|
||
std::cout << "usage: " << argv[0] << " <layout_file> <schematic_file>"
|
||
<< std::endl;<br>
|
||
return -1;<br>
|
||
}<br>
|
||
bool result = compare_files(argv[1], argv[2]);<br>
|
||
if(result == false) {<br>
|
||
std::cout << "Layout does not match schematic." << std::endl;<br>
|
||
return 1;<br>
|
||
} <br>
|
||
std::cout << "Layout does match schematic." << std::endl;<br>
|
||
return 0;<br>
|
||
}<br>
|
||
<br>
|
||
</font>We test the program with two schematics and three layouts. These
|
||
include a nand and a nor gate layout and schematic as well as an incorrect nand
|
||
gate layout. The nand layout and schematic are the same as shown above.<font face="Courier New" size="2">
|
||
</font></p>
|
||
<p><font face="Courier New" size="2">> lvs<br>
|
||
usage: lvs <layout_file> <schematic_file><br>
|
||
> lvs nand.layout nand.schematic <br>
|
||
Layout does match schematic.<br>
|
||
> lvs nand_short.layout nand.schematic <br>
|
||
Layout does not match schematic.<br>
|
||
> lvs nand.layout nor.schematic <br>
|
||
Layout does not match schematic.<br>
|
||
> lvs nor.layout nor.schematic <br>
|
||
Layout does match schematic.<br>
|
||
> lvs nor.layout nand.schematic <br>
|
||
Layout does not match schematic.</font></p>
|
||
<p>This concludes our tutorial on how to build a simple layout to schematic
|
||
verification application based on Boost.Polygon library capabilities. The
|
||
implementation of this application made many simplifying assumptions that are
|
||
not valid in the real world and hard coded a lot of things that need to be
|
||
configurable in a real layout verification application. However, it does
|
||
give an idea of how to use Boost.Polygon to solve real problems and points in
|
||
the direction of how a real application might use Boost.Polygon.</p>
|
||
|
||
|
||
<table class="docinfo" rules="none" frame="void" id="table1">
|
||
<colgroup>
|
||
<col class="docinfo-name"><col class="docinfo-content">
|
||
</colgroup>
|
||
<tbody vAlign="top">
|
||
<tr>
|
||
<th class="docinfo-name">Copyright:</th>
|
||
<td>Copyright <20> Intel Corporation 2008-2010.</td>
|
||
</tr>
|
||
<tr class="field">
|
||
<th class="docinfo-name">License:</th>
|
||
<td class="field-body">Distributed under the Boost Software License,
|
||
Version 1.0. (See accompanying file <tt class="literal">
|
||
<span class="pre">LICENSE_1_0.txt</span></tt> or copy at
|
||
<a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
|
||
http://www.boost.org/LICENSE_1_0.txt</a>)</td>
|
||
</tr>
|
||
</table>
|
||
|
||
</body>
|
||
|
||
</html> |