4 <meta http-equiv=
"Content-Type" content=
"text/html; charset=windows-1252">
5 <title>Polygon Usage
</title>
10 <h1>Layout Versus Schematic Tutorial
</h1>
11 <p>In this tutorial we will implement a toy VLSI layout verification
12 application.
In VLSI CAD an important step of design is the sign off check
13 that verifies that the physical layout as drawn by mask designers and automated
14 tools implements the logical schematic specified by design engineers.
15 Physical layout is modeled as polygons on layers that are used to print the
16 layout to the silicon wafer during manufacture.
It is much better to find
17 physical design mistakes before spending millions of dollars to prepare
18 lithography masks and run a test lot of wafers.
</p>
19 <p>Real layout file formats are binary and often compressed and represent a
20 folded hierarchical model of layout where a group of polygons can be grouped
21 into a cell and instantiated as a group into other cells.
For this
22 tutorial we assume a simplified ascii layout file format with no design
23 hierarchy, which we would call
"flat
" in VLSI jargon.
Similarly we assume
24 a flat, ascii logical schematic net list file format.
A net is a named
25 electrical connection in a circuit design.
The goal of the layout
26 verification tutorial is to parse these two file formats, apply geometry
27 operations provided by Boost.Polygon on the layout data to generate a logical
28 schematic that represents what is implemented in the physical layout and then
29 compare the input schematic with the generated schematic to determine whether
30 they are the same.
</p>
31 <p>First let us define some objects that we will need in the design of our toy
32 layout verification application:
</p>
33 <p>Layout Rectangle: An axis-parallel rectangle with a layer associated
<br>
34 Layout Pin: An axis-parallel rectangle with a layer and net (electrical signal)
36 Layout Database: An associative container of layer name to polygon set
<br>
37 Connectivity Database: An associative container of net name to layout database
<br>
38 Physical Device: A specific geometric arrangement on several layers with one or
39 more input net and one output net
<br>
40 Logical Net: A named graph node
<br>
41 Logical Device: An un-named graph node with a device type
<br>
42 Logical Pin: A special net that defines an input or output for the circuit
<br>
43 Schematic Database: A graph consisting of nets and logical
45 <p>Next let's define the sequence of operations performed by our toy
46 layout versus schematic application:
</p>
47 <p>Parse Layout: Stream layout rectangles and polygons into a layout database
48 and stream layout pins into a connectivity database
<br>
49 Extract Connectivity: Add polygons from layout database to connectivity database
50 by physical touch or overlap relationship
<br>
51 Extract Devices: Populate a schematic database with logical devices based on
52 physical devices identified within the layout geometry and extract their
54 connectivity database
<br>
55 Extract Net List: Complete graph represented in schematic database derived from
57 Parse Schematic: Stream logical nets, devices and pins into a schematic
59 Compare Schematics: Evaluate whether extracted schematic database is equivalent
60 to input schematic database and output result
</p>
61 <p>To test our application we will extract single logic gates.
A logic
62 gate is several transistors that work together to perform a specific logic
63 function.
Logic functions include the commonly understood Boolean logic
64 operations such as Boolean AND, OR, XOR and INVERT.
Also frequently used
65 are NAND and NOR, which are respectively AND and OR operations followed by an
66 INVERT operation.
A NAND gate can be implemented in the CMOS circuit
67 family with four transistors.
The NAND gate has two inputs and one output.
68 Each input goes to two transistors, one p-type transistor and one n-type
69 transistor.
The
"p
" stands for positive and the
"n
" stands for negative.
70 When the p-type transistor is on
71 it pulls the output up to the same voltage as the voltage source.
When the
72 n-type transistor is on it pulls the output down to the same voltage as the
73 ground.
The process of creating a p-type transistor begins by
"doping
" the silicon
74 substrate to create n-type material.
This area of n-type material will be
75 called the NWELL layer in our test data.
Within the area of NWELL a
76 p-diffusion area is created by further doping the silicon to create p-type
77 material.
This area of p-type material will be called PDIFF in our test
78 data.
Through the middle of a PDIFF area bars of poly-silicon are grown
79 that create conductive lines over the diffusion area.
The area of
80 poly-silicon material will be called POLY in our test data.
Under some of these
81 poly-silicon lines a thin layer of silicon-oxide provides insulation but allows
82 the voltage field of the poly-silicon to interact with the diffusion.
Each
83 of these insulated poly-silicon lines is the
"gate
" of a transistor.
84 The gate area will be called GATE in our test data.
When the
85 voltage at the gate is the same as the ground voltage the p-type transistor is
86 "on
" and can pass current from the voltage source to the output .
The
87 poly-silicon lines that are not insulated create electrical connections to the
88 transistor for output signals and source voltage.
The n-type transistor
89 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
90 voltage at the gate of the n-type transistor is at the source voltage level.
91 Above the poly-silicon layer is a layer of silicon-oxide insulator with holes
92 cut out of it that get filled in with metal.
These metal filled holes are
93 called vias and we will refer to this layer as VIA0 in our test data.
On
94 top of VIA0 is a layer of metal polygons with silicon oxide insulator between
95 them.
These metal polygons are wires and we will call them METAL1 in our
96 test data.
The Layout Pins in our test data will be on METAL1.
In a
97 NAND gate the two n-type transistors are configured in series, meaning that the
98 output of one is the input voltage source of the other.
Only if both
99 n-type transistors of a NAND gate are
"on
" will the output be connected to
100 ground, signifying a logical
"false
".
The two p-type transistors in a NAND
101 gate are configured in parallel.
If either input to the NAND gate is a
102 logical
"false
" the p-type transistor it is connected to will be
"on
" and the
103 output of the gate will be a logical
"true
" because the transistor will connect
104 it to the voltage supply.
The diagram below is an example of how a NAND
105 gate might be laid out and is not drawn to scale for any real process
106 technology.
The diffusion material is intended to be cut away under the
107 gate material by a Boolean NOT operation and is represented as solid bars under
108 the gates of transistors only for convenience of drawing.
</p>
110 <img border=
"0" src=
"images/NAND.PNG" width=
"602" height=
"387"></p>
111 <p>The following is the input layout file for the above NAND gate layout,
112 rectangle format is XL XH YL YH:
</p>
113 <p><font face=
"Courier New" size=
"2">Rectangle
0 60 24 48 NWELL
<br>
114 Rectangle
3 57 32 43 PDIFF
<br>
115 Rectangle
3 57 5 16 NDIFF
<br>
116 Rectangle
5 7 0 17 POLY
<br>
117 Rectangle
5 7 22 45 POLY
<br>
118 Rectangle
17 19 3 45 POLY
<br>
119 Rectangle
29 31 31 48 POLY
<br>
120 Rectangle
41 43 3 45 POLY
<br>
121 Rectangle
53 55 3 45 POLY
<br>
122 Rectangle
17 19 4 17 GATE
<br>
123 Rectangle
17 19 31 44 GATE
<br>
124 Rectangle
41 43 4 17 GATE
<br>
125 Rectangle
41 43 31 44 GATE
<br>
126 Rectangle
5 7 0 2 VIA0
<br>
127 Rectangle
5 7 23 25 VIA0
<br>
128 Rectangle
17 19 28 30 VIA0
<br>
129 Rectangle
29 31 46 48 VIA0
<br>
130 Rectangle
41 43 18 20 VIA0
<br>
131 Rectangle
53 55 23 25 VIA0
<br>
132 Rectangle
0 60 0 2 METAL1
<br>
133 Rectangle
3 57 28 30 METAL1
<br>
134 Rectangle
0 60 46 48 METAL1
<br>
135 Rectangle
3 57 18 20 METAL1
<br>
136 Rectangle
3 57 23 25 METAL1
<br>
137 Pin
29 31 0 2 METAL1 GND
<br>
138 Pin
29 31 23 25 METAL1 OUTPUT
</font><font face=
"Courier New" size=
"2"><br>
139 Pin
29 31 28 30 METAL1 INPUT1
</font><font face=
"Courier New" size=
"2"><br>
140 Pin
29 31 46 48 METAL1 VDD
<br>
141 Pin
29 31 18 20 METAL1 INPUT2
</font></p>
143 <img border=
"0" src=
"images/nands.PNG" width=
"421" height=
"402"></p>
144 <p>The following is the logic schematic net list file for the above NAND gate
146 <p><font face=
"Courier New" size=
"2">Pin OUTPUT
<br>Pin INPUT1
<br>Pin INPUT2
<br>
147 Pin VDD
<br>Pin GND
<br>Device PTRANS VDD INPUT1 OUTPUT
<br>Device PTRANS VDD
148 INPUT2 OUTPUT
<br>Device NTRANS GND INPUT1 NET1
<br>Device NTRANS NET1 INPUT2
150 <p>A human can look at this schematic and compare it to the drawn layout of the
151 NAND gate above to verify that the drawn layout matches what the schematic says
152 in a few seconds.
If you do that now you will probably find the p and
153 n-type transistors and trace the connectivity of the inputs and power to the
154 terminals of the transistors and then to the output.
Since there are on
155 the order of one billion transistors on a single chip these days we need to go a
156 lot faster than humans can inspect layout and make fewer mistakes.
Using polygon set operations
157 and polygon connectivity extraction provided by Boost.Polygon we will automate
158 the identification of transistors and the tracing of connectivity.
Based
160 <a href=
"analysis.htm">analysis
</a> of Boost.Polygon performance we can expect
161 this methodology to easily scale up to million gate blocks on standard
162 workstations and arbitrarily large designs given sufficient system memory.
164 by implementing some data structures for our application.
</p>
165 <p><font face=
"Courier New" size=
"2">struct layout_rectangle {
<br>
166 int xl, yl, xh, yh;
<br>
167 std::string layer;
<br>
169 <p>Our layout rectangle is nice and minimal, just enough to store its data.
170 It is defined in
<a href=
"tutorial/layout_rectangle.hpp">layout_rectangle.hpp
</a>. Next
171 let's implement the layout
172 pin in a similar way.
</p>
173 <p><font face=
"Courier New" size=
"2">struct layout_pin {
<br>
174 int xl, yl, xh, yh;
<br>
175 std::string layer;
<br>
176 std::string net;
<br>
178 <p>Our layout pin is defined in
<a href=
"tutorial/layout_pin.hpp">layout_pin.hpp
</a>.
Now
179 let's define a layout database object and populate it from our parsed
180 layout data in in
<a href=
"tutorial/layout_database.hpp">layout_database.hpp
</a>.
</p>
181 <p><font face=
"Courier New" size=
"2">typedef std::map
<std::string,
182 boost::polygon::polygon_90_set_data
<int
> > layout_database;
<br>
184 //map the layout rectangle data type to the boost::polygon::rectangle_concept
<br>
185 namespace boost { namespace polygon{
<br>
186 template
<><br>
187 struct rectangle_traits
<layout_rectangle
> {
<br>
188 typedef int coordinate_type;
<br>
189 typedef interval_data
<int
> interval_type;
<br>
190 static inline interval_type get(const layout_rectangle
&
191 rectangle, orientation_2d orient) {
<br>
192 if(orient == HORIZONTAL)
<br>
193 return interval_type(rectangle.xl,
195 return interval_type(rectangle.yl, rectangle.yh);
<br>
196 }
<br>
199 template
<><br>
200 struct geometry_concept
<layout_rectangle
> { typedef rectangle_concept
204 //insert layout rectangles into a layout database
<br>
205 inline void populate_layout_database(layout_database
& layout, std::vector
<layout_rectangle
>&
207 for(std::size_t i =
0; i
< rects.size(); ++i) {
<br>
208 layout[rects[i].layer].insert(rects[i]);
<br>
211 <p>We don't need to insert pins into the layout database because it doesn't know
212 anything about connectivity, just geometry.
However, we do need to know
213 something about connectivity to compare a schematic to a layout, so we need to
214 define our connectivity database and some logical objects.
First we define
215 an object for a logical device in
<a href=
"tutorial/device.hpp">device.hpp
</a>.
216 Since we are lazy this object does double duty as a pin and both types of
217 transistor.
A traditional object oriented design might declare a base
218 class with virtual destructor and derive every device from that.
Since we
219 aren't paid by the line of code let's just keep things simple.
</p>
220 <p><font face=
"Courier New" size=
"2">struct device {
<br>
221 std::string type;
<br>
222 std::vector
<std::string
> terminals;
<br>
224 <p>Now let's define a schematic database object in
225 <a href=
"tutorial/schematic_database.hpp">schematic_database.hpp
</a> and populate it from our parsed
227 <p><font face=
"Courier New"><font size=
"2">struct schematic_database{
<br>
228 std::vector
<device
> devices;
<br>
229 std::map
<std::string, std::set
<std::size_t
> > nets;
<br>
232 //given a vector of devices populate the map of net name to set of device index
<br>
233 inline void extract_netlist(std::map
<std::string, std::set
<std::size_t
> >& nets,
<br>
234
235 std::vector
<device
>& devices) {
<br>
236 for(std::size_t i =
0; i
< devices.size(); ++i) {
<br>
237 for(std::size_t j =
0; j
< devices[i].terminals.size(); ++j)
239 //create association between net name and device
241
242 nets[devices[i].terminals[j]].insert(nets[devices[i].terminals[j]].end(), i);
<br>
243 }
<br>
246 <p>Our schematic database is just a vector of devices, which are associated to
247 nets by name through their terminals and a map of net name to set of device
248 index into the vector, which completes the graph by associating nets with their
249 devices.
Given the devices and their terminal nets we easily build the
250 mapping from nets to devices with the extract_netlist operation.
Now we
251 are ready to start working on extracting our layout to a derived schematic
252 database.
However, first we need to build a physical connectivity database
253 with geometry in it before we can build a logical connectivity database from the
254 layout.
We define a simple connectivity database in
255 <a href=
"tutorial/connectivity_database.hpp">connectivity_database.hpp
</a> as a
256 map of net name to layout database of geometry connected to that net and
257 populate it with the layout database and pin data.
</p>
258 <p><font size=
"2" face=
"Courier New">typedef std::map
<std::string,
259 layout_database
> connectivity_database;
<br>
261 //map layout pin data type to boost::polygon::rectangle_concept
<br>
262 namespace boost { namespace polygon{
<br>
263 template
<><br>
264 struct rectangle_traits
<layout_pin
> {
<br>
265 typedef int coordinate_type;
<br>
266 typedef interval_data
<int
> interval_type;
<br>
267 static inline interval_type get(const layout_pin
& pin,
268 orientation_2d orient) {
<br>
269 if(orient == HORIZONTAL)
<br>
270 return interval_type(pin.xl, pin.xh);
<br>
271 return interval_type(pin.yl, pin.yh);
<br>
272 }
<br>
275 template
<><br>
276 struct geometry_concept
<layout_pin
> { typedef rectangle_concept type; };
<br>
278 <p><font size=
"2" face=
"Courier New">//given a layout_database we populate a
279 connectivity database
<br>
280 inline void populate_connectivity_database(connectivity_database
& connectivity,
<br>
281
282 std::vector
<layout_pin
>& pins, layout_database
& layout) {
<br>
283 using namespace boost::polygon;
<br>
284 using namespace boost::polygon::operators;
<br>
285 for(std::size_t i =
0; i
< pins.size(); ++i) {
<br>
286 connectivity[pins[i].net][pins[i].layer].insert(pins[i]);
<br>
288 int internal_net_suffix =
0;
<br>
289 //connect metal1 layout to pins which were on metal1
<br>
290 connect_layout_to_layer(connectivity, layout[
"METAL1
"],
"METAL1
",
<br>
291
292 "METAL1
",
"__internal_net_
", internal_net_suffix);
<br>
293 //connect via0 layout to metal1
<br>
294 connect_layout_to_layer(connectivity, layout[
"VIA0
"],
"VIA0
",
<br>
295
296 "METAL1
",
"__internal_net_
", internal_net_suffix);
<br>
297 //poly needs to have gates subtracted from it to prevent shorting through
299 polygon_set poly_not_gate = layout[
"POLY
"] - layout[
"GATE
"];
<br>
300 //connect poly minus gate to via0
<br>
301 connect_layout_to_layer(connectivity, poly_not_gate,
"POLY
",
<br>
302
303 "VIA0
",
"__internal_net_
", internal_net_suffix);
<br>
304 //we don't want to short signals through transistors so we subtract the
306 //from the diffusions
<br>
307 polygon_set diff_not_gate = (layout[
"PDIFF
"] + layout[
"NDIFF
"]) -
308 layout[
"GATE
"];
<br>
309 //connect diffusion minus gate to poly
<br>
310 //Note that I made up the DIFF layer name for combined P and NDIFF
<br>
311 connect_layout_to_layer(connectivity, diff_not_gate,
"DIFF
",
<br>
312
313 "POLY
",
"__internal_net_
", internal_net_suffix);
<br>
314 //connect gate to poly to make connections through gates on poly
<br>
315 connect_layout_to_layer(connectivity, layout[
"GATE
"],
"GATE
",
<br>
316
317 "POLY
",
"__internal_net_
", internal_net_suffix);
<br>
318 //now we have traced connectivity of the layout down to the transistor
320 //any polygons not connected to pins have been assigned internal net
323 <p>This populate connectivity database function is our first real use of
324 Boost.Polygon in our application.
Here we are doing Boolean (polygon set)
325 operations on layout layers to merge together the PDIFF and NDIFF layers and cut
326 away the GATE layer from the result, for example.
We connect up the layout
327 starting from the pins and working our way down the layer stack to the
328 transistor level.
It would work equally well to work our way up the layer
329 stack, or connect things up in any order, really, but this way produces fewer
330 internal temporary nets that need to be merged when connections between them are
331 discovered later.
The connect layout to layer function used above needs to
332 be implemented before we can populate our connectivity database.
</p>
333 <p><font size=
"2" face=
"Courier New">inline void
334 connect_layout_to_layer(connectivity_database
& connectivity, polygon_set
&
336
337 std::string layout_layer, std::string layer,
<br>
338
339 std::string net_prefix, int
& net_suffix) {
<br>
340 if(layout_layer.empty())
<br>
341 return;
<br>
342 boost::polygon::connectivity_extraction_90
<int
> ce;
<br>
343 std::vector
<std::string
> net_ids;
<br>
344 for(connectivity_database::iterator itr = connectivity.begin(); itr !=
345 connectivity.end(); ++itr) {
<br>
346 net_ids.push_back((*itr).first);
<br>
347 ce.insert((*itr).second[layer]);
<br>
349 std::vector
<polygon
> polygons;
<br>
350 layout.get_polygons(polygons);
<br>
351 std::size_t polygon_id_offset = net_ids.size();
<br>
352 for(std::size_t i =
0; i
< polygons.size(); ++i) {
<br>
353 ce.insert(polygons[i]);
<br>
355 std::vector
<std::set
<int
> > graph(polygons.size() + net_ids.size(),
356 std::set
<int
>());
<br>
357 ce.extract(graph);
<br>
358 std::vector
<int
> polygon_color(polygons.size() + net_ids.size(),
0);
<br>
359 //for each net in net_ids populate connected component with net
<br>
360 for(std::size_t node_id =
0; node_id
< net_ids.size(); ++node_id) {
<br>
361 populate_connected_component(connectivity, polygons,
362 polygon_color, graph, node_id,
<br>
363 polygon_id_offset, net_ids[node_id], net_ids,
<br>
364 net_prefix, layout_layer);
<br>
366 //for each polygon_color that is zero populate connected component with
367 net_prefix + net_suffix++
<br>
368 for(std::size_t i =
0; i
< polygons.size(); ++i) {
<br>
369 if(polygon_color[i + polygon_id_offset] ==
0) {
<br>
370 std::stringstream ss(std::stringstream::in |
371 std::stringstream::out);
<br>
372 ss
<< net_prefix
<< net_suffix++;
<br>
373 std::string internal_net;
<br>
374 ss
>> internal_net;
<br>
375 populate_connected_component(connectivity,
376 polygons, polygon_color, graph,
<br>
377 i + polygon_id_offset,
<br>
378 polygon_id_offset, internal_net, net_ids,
<br>
379 net_prefix, layout_layer);
<br>
380 }
<br>
383 <p>The connect layout to layer function uses the connectivity extraction feature
384 of Boost.Polyon to build a connectivity graph for polygons on the input polygon
385 set and in the connectivity database on the specified layer.
It then finds
386 polygons associated with existing nets in the connectivity database through
387 graph traversal and inserts them into the connectivity database.
Finally,
388 polygons that weren't connected to existing nets are inserted into the
389 connectivity database on auto-generated internal net names.
The insertion
390 of a connected component into the connectivity database is handled by the
391 recursive traversal of the connectivity graph that we implement next.
</p>
392 <p><font size=
"2" face=
"Courier New">inline void populate_connected_component
<br>
393 (connectivity_database
& connectivity, std::vector
<polygon
>& polygons,
<br>
394 std::vector
<int
> polygon_color, std::vector
<std::set
<int
> >& graph,
<br>
395 std::size_t node_id, std::size_t polygon_id_offset, std::string
& net,
<br>
396 std::vector
<std::string
>& net_ids, std::string net_prefix,
<br>
397 std::string
& layout_layer) {
<br>
398 if(polygon_color[node_id] ==
1)
<br>
399 return;
<br>
400 polygon_color[node_id] =
1;
<br>
401 if(node_id
< polygon_id_offset
&& net_ids[node_id] != net) {
<br>
402 //merge nets in connectivity database
<br>
403 //if one of the nets is internal net merge it into the other
<br>
404 std::string net1 = net_ids[node_id];
<br>
405 std::string net2 = net;
<br>
406 if(net.compare(
0, net_prefix.length(), net_prefix) ==
0) {
<br>
407 net = net1;
<br>
408 std::swap(net1, net2);
<br>
409 } else {
<br>
410 net_ids[node_id] = net;
<br>
411 }
<br>
412 connectivity_database::iterator itr =
413 connectivity.find(net1);
<br>
414 if(itr != connectivity.end()) {
<br>
415 for(layout_database::iterator itr2 = (*itr).second.begin();
<br>
416 itr2 != (*itr).second.end();
418 connectivity[net2][(*itr2).first].insert((*itr2).second);
<br>
419 }
<br>
420 connectivity.erase(itr);
<br>
421 }
<br>
423 if(node_id
>= polygon_id_offset)
<br>
424 connectivity[net][layout_layer].insert(polygons[node_id -
425 polygon_id_offset]);
<br>
426 for(std::set
<int
>::iterator itr = graph[node_id].begin();
<br>
427 itr != graph[node_id].end(); ++itr) {
<br>
428 populate_connected_component(connectivity, polygons,
429 polygon_color, graph,
<br>
430 *itr, polygon_id_offset, net, net_ids, net_prefix,
435 </font>We want to merge internally generated nets into pin nets, which is the
436 most complicated part of this simple procedure.
Now that we have our
437 connectivity database extracted from pins down to transistors we need to extract
438 our transistors and establish the relationship between transistor terminals and
439 nets in our connectivity database.
First let's extract transistors with
440 the functions defined in defined in
<a href=
"tutorial/extract_devices.hpp">
441 extract_devices.hpp
</a>.
</p>
442 <p><font size=
"2" face=
"Courier New">typedef boost::polygon::connectivity_extraction_90
<int
>
443 connectivity_extraction;
<br>
444 inline std::vector
<std::set
<int
> ><br>
445 extract_layer(connectivity_extraction
& ce, std::vector
<std::string
>& net_ids,
<br>
446
447 connectivity_database
& connectivity, polygon_set
& layout,
<br>
448
449 std::string layer) {
<br>
450 for(connectivity_database::iterator itr = connectivity.begin(); itr !=
451 connectivity.end(); ++itr) {
<br>
452 net_ids.push_back((*itr).first);
<br>
453 ce.insert((*itr).second[layer]);
<br>
455 std::vector
<polygon
> polygons;
<br>
456 layout.get_polygons(polygons);
<br>
457 for(std::size_t i =
0; i
< polygons.size(); ++i) {
<br>
458 ce.insert(polygons[i]);
<br>
460 std::vector
<std::set
<int
> > graph(polygons.size() + net_ids.size(),
461 std::set
<int
>());
<br>
462 ce.extract(graph);
<br>
463 return graph;
<br>
465 <p>This extract layer algorithm constructs a connectivity graph between polygons
466 in the input polygon set and polygons in the given layer of the connectivity
467 database.
It is used to form the association between transistors and their
468 terminal nets in the function for extracting a specific transistor type.
</p>
469 <p><font size=
"2" face=
"Courier New">inline void extract_device_type(std::vector
<device
>&
470 devices, connectivity_database
& connectivity,
<br>
471
472 polygon_set
& layout, std::string type) {
<br>
473 //recall that P and NDIFF were merged into one DIFF layer in the
474 connectivity database
<br>
475 //find the two nets on the DIFF layer that interact with each transistor
<br>
476 //and then find the net on the poly layer that interacts with each
478 boost::polygon::connectivity_extraction_90
<int
> cediff;
<br>
479 std::vector
<std::string
> net_ids_diff;
<br>
480 std::vector
<std::set
<int
> > graph_diff =
<br>
481 extract_layer(cediff, net_ids_diff, connectivity, layout,
482 "DIFF
");
<br>
483 boost::polygon::connectivity_extraction_90
<int
> cepoly;
<br>
484 std::vector
<std::string
> net_ids_poly;
<br>
485 std::vector
<std::set
<int
> > graph_poly =
<br>
486 extract_layer(cepoly, net_ids_poly, connectivity, layout,
487 "POLY
");
<br>
488 std::vector
<device
> tmp_devices(graph_diff.size() - net_ids_poly.size());
<br>
489 for(std::size_t i = net_ids_poly.size(); i
< graph_diff.size(); ++i) {
<br>
490 tmp_devices[i - net_ids_diff.size()].type = type;
<br>
491 tmp_devices[i - net_ids_diff.size()].terminals = std::vector
<std::string
>(
3,
493 std::size_t j =
0;
<br>
494 for(std::set
<int
>::iterator itr = graph_diff[i].begin();
<br>
495 itr != graph_diff[i].end(); ++itr,
497 if(j ==
0) {
<br>
498 tmp_devices[i - net_ids_diff.size()].terminals[
0]
499 = net_ids_diff[*itr];
<br>
500 } else if(j ==
1) {
<br>
501 tmp_devices[i - net_ids_diff.size()].terminals[
2]
502 = net_ids_diff[*itr];
<br>
503 } else {
<br>
504 //error, too many diff connections
<br>
505 tmp_devices[i - net_ids_diff.size()].terminals
506 = std::vector
<std::string
>(
3, std::string());
<br>
507 }
<br>
508 }
<br>
509 j =
0;
<br>
510 for(std::set
<int
>::iterator itr = graph_poly[i].begin();
<br>
511 itr != graph_poly[i].end(); ++itr,
513 if(j ==
0) {
<br>
514 tmp_devices[i - net_ids_diff.size()].terminals[
1]
515 = net_ids_poly[*itr];
<br>
516 } else {
<br>
517 //error, too many poly connections
<br>
518 tmp_devices[i - net_ids_poly.size()].terminals
519 = std::vector
<std::string
>(
3, std::string());
<br>
520 }
<br>
521 }
<br>
524 devices.insert(devices.end(), tmp_devices.begin(), tmp_devices.end());
<br>
526 <p>We append transistors onto the vector of devices with their terminals
527 populated with net names extracted from the connectivity database.
528 Transistors' terminals are connected through the POLY and DIFF layers where DIFF
529 contains both PDIFF and NDIFF.
The connection to POLY layer is the gate of
530 the transistor while the connections to DIFF on either side of the channel of
531 the transistor are the source and drain.
We can use this to extract are p
532 and n-type transistors.
<font size=
"2" face=
"Courier New"><br>
534 //populates vector of devices based on connectivity and layout data
<br>
535 inline void extract_devices(std::vector
<device
>& devices, connectivity_database
&
537
538 layout_database
& layout) {
<br>
539 using namespace boost::polygon::operators;
<br>
540 //p-type transistors are gate that interact with p diffusion and nwell
<br>
541 polygon_set ptransistors = layout[
"GATE
"];
<br>
542 ptransistors.interact(layout[
"PDIFF
"]);
<br>
543 ptransistors.interact(layout[
"NWELL
"]);
<br>
544 //n-type transistors are gate that interact with n diffusion and not
546 polygon_set ntransistors = layout[
"GATE
"];
<br>
547 ntransistors.interact(layout[
"NDIFF
"]);
<br>
548 polygon_set not_ntransistors = ntransistors;
<br>
549 not_ntransistors.interact(layout[
"NWELL
"]);
<br>
550 ntransistors -= not_ntransistors;
<br>
551 extract_device_type(devices, connectivity, ptransistors,
"PTRANS
");
<br>
552 extract_device_type(devices, connectivity, ntransistors,
"NTRANS
");
<br>
554 <p>The extract devices procedure makes some more use of Boost.Polygon Boolean
555 operations on the layout data when we exclude GATE material over NDIFF that
556 isn't also over NWELL to extract our n-type transistors.
We also are using
557 the
"interact
" operation on polygon gets, which is implemented in terms of
558 connectivity extraction and retains all polygons of a polygon set that touch or
559 overlap polygons from another polygon set.
Now that we have a vector of
560 devices we can build a schematic database by calling the extract_netlist
561 function.
We can then compare the extracted schematic from the schematic
562 read in from file with the functions defined in
563 <a href=
"tutorial/compare_schematics.hpp">compare_schematics.hpp
</a>.
564 Since comparing two schematics has no geometric aspect we won't go into that
565 procedure here in the tutorial and will skip to the integration of all these
566 procedures in defined in
<a href=
"tutorial/extract.cpp">extract.cpp
</a> to build
567 the layout to schematic comparison algorithm.
</p>
568 <p><font size=
"2" face=
"Courier New">bool compare_files(std::string layout_file,
569 std::string schematic_file) {
<br>
570 std::ifstream sin(schematic_file.c_str());
<br>
571 std::ifstream lin(layout_file.c_str());
<br>
573 std::vector
<layout_rectangle
> rects;
<br>
574 std::vector
<layout_pin
> pins;
<br>
575 parse_layout(rects, pins, lin);
<br>
577 schematic_database reference_schematic;
<br>
578 parse_schematic_database(reference_schematic, sin);
<br>
580 layout_database layout;
<br>
581 populate_layout_database(layout, rects);
<br>
583 connectivity_database connectivity;
<br>
584 populate_connectivity_database(connectivity, pins, layout);
<br>
586 schematic_database schematic;
<br>
587 std::vector
<device
>& devices = schematic.devices;
<br>
588 for(std::size_t i =
0; i
< pins.size(); ++i) {
<br>
589 devices.push_back(device());
<br>
590 devices.back().type =
"PIN
";
<br>
591 devices.back().terminals.push_back(pins[i].net);
<br>
593 extract_devices(devices, connectivity, layout);
<br>
594 extract_netlist(schematic.nets, devices);
<br>
595 return compare_schematics(reference_schematic, schematic);
<br>
597 <p><font face=
"Courier New" size=
"2">int main(int argc, char **argv) {
<br>
598 if(argc
< 3) {
<br>
599 std::cout
<< "usage:
" << argv[
0]
<< " <layout_file
> <schematic_file
>"
600 << std::endl;
<br>
601 return -
1;
<br>
603 bool result = compare_files(argv[
1], argv[
2]);
<br>
604 if(result == false) {
<br>
605 std::cout
<< "Layout does not match schematic.
" << std::endl;
<br>
606 return
1;
<br>
608 std::cout
<< "Layout does match schematic.
" << std::endl;
<br>
612 </font>We test the program with two schematics and three layouts.
These
613 include a nand and a nor gate layout and schematic as well as an incorrect nand
614 gate layout.
The nand layout and schematic are the same as shown above.
<font face=
"Courier New" size=
"2">
616 <p><font face=
"Courier New" size=
"2">> lvs
<br>
617 usage: lvs
<layout_file
> <schematic_file
><br>
618 > lvs nand.layout nand.schematic
<br>
619 Layout does match schematic.
<br>
620 > lvs nand_short.layout nand.schematic
<br>
621 Layout does not match schematic.
<br>
622 > lvs nand.layout nor.schematic
<br>
623 Layout does not match schematic.
<br>
624 > lvs nor.layout nor.schematic
<br>
625 Layout does match schematic.
<br>
626 > lvs nor.layout nand.schematic
<br>
627 Layout does not match schematic.
</font></p>
628 <p>This concludes our tutorial on how to build a simple layout to schematic
629 verification application based on Boost.Polygon library capabilities.
The
630 implementation of this application made many simplifying assumptions that are
631 not valid in the real world and hard coded a lot of things that need to be
632 configurable in a real layout verification application.
However, it does
633 give an idea of how to use Boost.Polygon to solve real problems and points in
634 the direction of how a real application might use Boost.Polygon.
</p>
637 <table class=
"docinfo" rules=
"none" frame=
"void" id=
"table1">
639 <col class=
"docinfo-name"><col class=
"docinfo-content">
643 <th class=
"docinfo-name">Copyright:
</th>
644 <td>Copyright © Intel Corporation
2008-
2010.
</td>
647 <th class=
"docinfo-name">License:
</th>
648 <td class=
"field-body">Distributed under the Boost Software License,
649 Version
1.0. (See accompanying file
<tt class=
"literal">
650 <span class=
"pre">LICENSE_1_0.txt
</span></tt> or copy at
651 <a class=
"reference" target=
"_top" href=
"http://www.boost.org/LICENSE_1_0.txt">
652 http://www.boost.org/LICENSE_1_0.txt
</a>)
</td>
projects / ceph.git / blob