]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright 2010 Intel Corporation | |
3 | ||
4 | Use, modification and distribution are subject to the Boost Software License, | |
5 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt). | |
7 | */ | |
8 | //connectivity_database.hpp | |
9 | #ifndef BOOST_POLYGON_TUTORIAL_CONNECTIVITY_DATABASE_HPP | |
10 | #define BOOST_POLYGON_TUTORIAL_CONNECTIVITY_DATABASE_HPP | |
11 | #include <boost/polygon/polygon.hpp> | |
12 | #include <map> | |
13 | #include <sstream> | |
14 | #include "layout_database.hpp" | |
15 | #include "layout_pin.hpp" | |
16 | ||
17 | typedef std::map<std::string, layout_database > connectivity_database; | |
18 | ||
19 | //map layout pin data type to boost::polygon::rectangle_concept | |
20 | namespace boost { namespace polygon{ | |
21 | template <> | |
22 | struct rectangle_traits<layout_pin> { | |
23 | typedef int coordinate_type; | |
24 | typedef interval_data<int> interval_type; | |
25 | static inline interval_type get(const layout_pin& pin, orientation_2d orient) { | |
26 | if(orient == HORIZONTAL) | |
27 | return interval_type(pin.xl, pin.xh); | |
28 | return interval_type(pin.yl, pin.yh); | |
29 | } | |
30 | }; | |
31 | ||
32 | template <> | |
33 | struct geometry_concept<layout_pin> { typedef rectangle_concept type; }; | |
34 | }} | |
35 | ||
36 | typedef boost::polygon::polygon_90_data<int> polygon; | |
37 | typedef boost::polygon::polygon_90_set_data<int> polygon_set; | |
38 | ||
39 | inline void populate_connected_component | |
40 | (connectivity_database& connectivity, std::vector<polygon>& polygons, | |
41 | std::vector<int> polygon_color, std::vector<std::set<int> >& graph, | |
42 | std::size_t node_id, std::size_t polygon_id_offset, std::string& net, | |
43 | std::vector<std::string>& net_ids, std::string net_prefix, | |
44 | std::string& layout_layer) { | |
45 | if(polygon_color[node_id] == 1) | |
46 | return; | |
47 | polygon_color[node_id] = 1; | |
48 | if(node_id < polygon_id_offset && net_ids[node_id] != net) { | |
49 | //merge nets in connectivity database | |
50 | //if one of the nets is internal net merge it into the other | |
51 | std::string net1 = net_ids[node_id]; | |
52 | std::string net2 = net; | |
53 | if(net.compare(0, net_prefix.length(), net_prefix) == 0) { | |
54 | net = net1; | |
55 | std::swap(net1, net2); | |
56 | } else { | |
57 | net_ids[node_id] = net; | |
58 | } | |
59 | connectivity_database::iterator itr = connectivity.find(net1); | |
60 | if(itr != connectivity.end()) { | |
61 | for(layout_database::iterator itr2 = (*itr).second.begin(); | |
62 | itr2 != (*itr).second.end(); ++itr2) { | |
63 | connectivity[net2][(*itr2).first].insert((*itr2).second); | |
64 | } | |
65 | connectivity.erase(itr); | |
66 | } | |
67 | } | |
68 | if(node_id >= polygon_id_offset) | |
69 | connectivity[net][layout_layer].insert(polygons[node_id - polygon_id_offset]); | |
70 | for(std::set<int>::iterator itr = graph[node_id].begin(); | |
71 | itr != graph[node_id].end(); ++itr) { | |
72 | populate_connected_component(connectivity, polygons, polygon_color, graph, | |
73 | *itr, polygon_id_offset, net, net_ids, net_prefix, layout_layer); | |
74 | } | |
75 | } | |
76 | ||
77 | inline void connect_layout_to_layer(connectivity_database& connectivity, polygon_set& layout, std::string layout_layer, std::string layer, std::string net_prefix, int& net_suffix) { | |
78 | if(layout_layer.empty()) | |
79 | return; | |
80 | boost::polygon::connectivity_extraction_90<int> ce; | |
81 | std::vector<std::string> net_ids; | |
82 | for(connectivity_database::iterator itr = connectivity.begin(); itr != connectivity.end(); ++itr) { | |
83 | net_ids.push_back((*itr).first); | |
84 | ce.insert((*itr).second[layer]); | |
85 | } | |
86 | std::vector<polygon> polygons; | |
87 | layout.get_polygons(polygons); | |
88 | std::size_t polygon_id_offset = net_ids.size(); | |
89 | for(std::size_t i = 0; i < polygons.size(); ++i) { | |
90 | ce.insert(polygons[i]); | |
91 | } | |
92 | std::vector<std::set<int> > graph(polygons.size() + net_ids.size(), std::set<int>()); | |
93 | ce.extract(graph); | |
94 | std::vector<int> polygon_color(polygons.size() + net_ids.size(), 0); | |
95 | //for each net in net_ids populate connected component with net | |
96 | for(std::size_t node_id = 0; node_id < net_ids.size(); ++node_id) { | |
97 | populate_connected_component(connectivity, polygons, polygon_color, graph, node_id, | |
98 | polygon_id_offset, net_ids[node_id], net_ids, | |
99 | net_prefix, layout_layer); | |
100 | } | |
101 | //for each polygon_color that is zero populate connected compontent with net_prefix + net_suffix++ | |
102 | for(std::size_t i = 0; i < polygons.size(); ++i) { | |
103 | if(polygon_color[i + polygon_id_offset] == 0) { | |
104 | std::stringstream ss(std::stringstream::in | std::stringstream::out); | |
105 | ss << net_prefix << net_suffix++; | |
106 | std::string internal_net; | |
107 | ss >> internal_net; | |
108 | populate_connected_component(connectivity, polygons, polygon_color, graph, | |
109 | i + polygon_id_offset, | |
110 | polygon_id_offset, internal_net, net_ids, | |
111 | net_prefix, layout_layer); | |
112 | } | |
113 | } | |
114 | } | |
115 | ||
116 | //given a layout_database we populate a connectivity database | |
117 | inline void populate_connectivity_database(connectivity_database& connectivity, std::vector<layout_pin>& pins, layout_database& layout) { | |
118 | using namespace boost::polygon; | |
119 | using namespace boost::polygon::operators; | |
120 | for(std::size_t i = 0; i < pins.size(); ++i) { | |
121 | connectivity[pins[i].net][pins[i].layer].insert(pins[i]); | |
122 | } | |
123 | int internal_net_suffix = 0; | |
124 | //connect metal1 layout to pins which were on metal1 | |
125 | connect_layout_to_layer(connectivity, layout["METAL1"], "METAL1", | |
126 | "METAL1", "__internal_net_", internal_net_suffix); | |
127 | //connect via0 layout to metal1 | |
128 | connect_layout_to_layer(connectivity, layout["VIA0"], "VIA0", | |
129 | "METAL1", "__internal_net_", internal_net_suffix); | |
130 | //poly needs to have gates subtracted from it to prevent shorting through transistors | |
131 | polygon_set poly_not_gate = layout["POLY"] - layout["GATE"]; | |
132 | //connect poly minus gate to via0 | |
133 | connect_layout_to_layer(connectivity, poly_not_gate, "POLY", | |
134 | "VIA0", "__internal_net_", internal_net_suffix); | |
135 | //we don't want to short signals through transistors so we subtract the gate regions | |
136 | //from the diffusions | |
137 | polygon_set diff_not_gate = (layout["PDIFF"] + layout["NDIFF"]) - layout["GATE"]; | |
138 | //connect diffusion minus gate to poly | |
139 | //Note that I made up the DIFF layer name for combined P and NDIFF | |
140 | connect_layout_to_layer(connectivity, diff_not_gate, "DIFF", | |
141 | "POLY", "__internal_net_", internal_net_suffix); | |
142 | //connect gate to poly to make connections through gates on poly | |
143 | connect_layout_to_layer(connectivity, layout["GATE"], "GATE", | |
144 | "POLY", "__internal_net_", internal_net_suffix); | |
145 | //now we have traced connectivity of the layout down to the transistor level | |
146 | //any polygons not connected to pins have been assigned internal net names | |
147 | } | |
148 | ||
149 | #endif |