123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658 |
- <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>
|