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