yangzuhao
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 � 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> |