Coverage for klayout_pex/rcx25/capacitance_distributor.py: 99%
214 statements
« prev ^ index » next coverage.py v7.17.2, created at 2026-11-06 13:14 +0000
1#
2# --------------------------------------------------------------------------------
3# SPDX-FileCopyrightText: 2024-2026 Martin Jan Köhler and Harald Pretl
4# Johannes Kepler University, Institute for Integrated Circuits.
5#
6# This file is part of KPEX
7# (see https://github.com/iic-jku/klayout-pex).
8#
9# This program is free software: you can redistribute it and/or modify
10# it under the terms of the GNU General Public License as published by
11# the Free Software Foundation, either version 3 of the License, or
12# (at your option) any later version.
13#
14# This program is distributed in the hope that it will be useful,
15# but WITHOUT ANY WARRANTY; without even the implied warranty of
16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17# GNU General Public License for more details.
18#
19# You should have received a copy of the GNU General Public License
20# along with this program. If not, see <http://www.gnu.org/licenses/>.
21# SPDX-License-Identifier: GPL-3.0-or-later
22# --------------------------------------------------------------------------------
23#
24"""
25Distribution of the capacitances onto the nodes of the resistor networks (#211 §8)
27NOTE: each part of the geometry of a capacitance (its area, or its edge) goes to the node
28 of the resistor network nearest to it, on each of the two nets (on the layer of the capacitance),
29 so that the RC netlist is a distributed RC, e.g. a wire between 2 nodes has half of its
30 capacitance on each of them (π model). A net without a resistor network keeps its capacitances.
31"""
33from __future__ import annotations
35from bisect import bisect_left, bisect_right
36from collections import defaultdict
37from dataclasses import dataclass
38import math
39from typing import *
41import klayout.db as kdb
43from ..types import LayerName, NetName
45import klayout_pex_protobuf.kpex.layout.location_pb2 as location_pb2
46import klayout_pex_protobuf.kpex.r.r_network_pb2 as r_network_pb2
49Point = Tuple[float, float] # in DBU
50Contour = List[Point]
52# the nodes of a capacitance, of its first and second net
53NodePair = Tuple[NetName, NetName]
56@dataclass(frozen=True)
57class NodeSite:
58 """
59 The location of a node of a resistor network (in DBU), by the name of its node in the netlist
60 """
61 x: float
62 y: float
63 node_name: NetName
65 @classmethod
66 def from_node(cls, node: r_network_pb2.RNode, node_name: NetName) -> Optional[NodeSite]:
67 """
68 :return: the site of a pin, or the center of the box of another node, None without location
69 """
70 K = location_pb2.Location.Kind
71 match node.location.kind:
72 case K.LOCATION_KIND_POINT:
73 return cls(node.location.point.x, node.location.point.y, node_name)
74 case K.LOCATION_KIND_BOX:
75 box = node.location.box
76 return cls((box.lower_left.x + box.upper_right.x) / 2.0,
77 (box.lower_left.y + box.upper_right.y) / 2.0,
78 node_name)
79 case _:
80 return None
83class NodeSites:
84 """
85 The sites of the nodes of a net (on a layer)
86 """
87 def __init__(self, sites: Iterable[NodeSite]):
88 # NOTE: one site per location, as nodes at the same location would share the same part of the geometry
89 by_location: Dict[Point, NodeSite] = {}
90 for site in sorted(sites, key=lambda s: (s.node_name, s.x, s.y)):
91 by_location.setdefault((site.x, site.y), site)
92 self.sites: List[NodeSite] = sorted(by_location.values(), key=lambda s: (s.x, s.y, s.node_name))
93 self.xs: List[float] = [s.x for s in self.sites]
95 def nearest(self, x: float, y: float) -> NodeSite:
96 best_site, best_distance = None, math.inf
97 idx = bisect_left(self.xs, x)
98 # NOTE: outwards from x, as long as the sites can be nearer
99 for indices in (range(idx, len(self.sites)), range(idx - 1, -1, -1)):
100 for i in indices:
101 site = self.sites[i]
102 if abs(site.x - x) > best_distance:
103 break
104 distance = math.hypot(site.x - x, site.y - y)
105 if distance < best_distance:
106 best_site, best_distance = site, distance
107 return best_site
109 def candidates(self, box: kdb.Box | kdb.DBox) -> List[NodeSite]:
110 """
111 The sites that can be the nearest to a point of the box
112 """
113 if len(self.sites) == 1:
114 return self.sites
116 # NOTE: each point of the box has a site within the distance of the farthest corner
117 # from the site nearest to the center, so a site farther from the box is never the nearest
118 center = box.center()
119 site = self.nearest(center.x, center.y)
120 radius = math.hypot(max(abs(site.x - box.left), abs(site.x - box.right)),
121 max(abs(site.y - box.bottom), abs(site.y - box.top)))
122 candidates: List[NodeSite] = []
123 for i in range(bisect_left(self.xs, box.left - radius), bisect_right(self.xs, box.right + radius)):
124 s = self.sites[i]
125 dx = max(box.left - s.x, 0.0, s.x - box.right)
126 dy = max(box.bottom - s.y, 0.0, s.y - box.top)
127 if math.hypot(dx, dy) <= radius:
128 candidates.append(s)
129 return candidates
132def edge_parts(p: Point, q: Point, sites: Sequence[NodeSite]) -> List[Tuple[float, float, NetName]]:
133 """
134 The parts of the segment from p to q, by the site nearest to them
136 :return: (t0, t1, node name) for the points p + t·(q - p), t0 ≤ t ≤ t1, from t = 0 to t = 1
137 """
138 dx, dy = q[0] - p[0], q[1] - p[1]
140 # NOTE: the squared distance of p + t·(q - p) to a site is |q - p|²·t² + a·t + b,
141 # so the nearest site is the one of the lowest line a·t + b
142 lines = sorted(((2.0 * (dx * (p[0] - s.x) + dy * (p[1] - s.y)),
143 (p[0] - s.x) ** 2 + (p[1] - s.y) ** 2,
144 s.node_name) for s in sites),
145 key=lambda line: (line[1], line[0]))
147 parts: List[Tuple[float, float, NetName]] = []
148 t = 0.0
149 a, b, node_name = lines[0]
150 while True:
151 # NOTE: the next line below the current one has a lower slope, and crosses it first
152 next_t, next_line = 1.0, None
153 for line in lines:
154 if line[0] >= a:
155 continue
156 crossing = max(t, (line[1] - b) / (a - line[0]))
157 if crossing < next_t or (crossing == next_t and next_line is not None and line[0] < next_line[0]):
158 next_t, next_line = crossing, line
159 if next_t > t:
160 if parts and parts[-1][2] == node_name:
161 parts[-1] = (parts[-1][0], next_t, node_name)
162 else:
163 parts.append((t, next_t, node_name))
164 if next_line is None:
165 return parts
166 t = next_t
167 a, b, node_name = next_line
170def clip(contour: Contour, nx: float, ny: float, c: float) -> Contour:
171 """
172 The part of the contour where nx·x + ny·y ≤ c (Sutherland–Hodgman)
174 NOTE: the clipped contour of a concave polygon may have edges back and forth on the line,
175 but its area is the one of the part
176 """
177 clipped: Contour = []
178 for i in range(len(contour)):
179 p, q = contour[i - 1], contour[i]
180 dp = nx * p[0] + ny * p[1] - c
181 dq = nx * q[0] + ny * q[1] - c
182 if (dp > 0.0) != (dq > 0.0):
183 s = dp / (dp - dq)
184 clipped.append((p[0] + s * (q[0] - p[0]), p[1] + s * (q[1] - p[1])))
185 if dq <= 0.0:
186 clipped.append(q)
187 return clipped
190def signed_area(contour: Contour) -> float:
191 return 0.5 * sum(contour[i - 1][0] * contour[i][1] - contour[i][0] * contour[i - 1][1]
192 for i in range(len(contour)))
195@dataclass
196class Area:
197 """
198 An area, as contours with their sign (+1 for a hull, -1 for a hole), relative to an origin
199 """
200 contours: List[Tuple[Contour, float]]
202 @classmethod
203 def from_region(cls, region: kdb.Region, origin: kdb.Point) -> Area:
204 contours: List[Tuple[Contour, float]] = []
205 for polygon in region.each():
206 hull = [(p.x - origin.x, p.y - origin.y) for p in polygon.each_point_hull()]
207 contours.append((hull, math.copysign(1.0, signed_area(hull))))
208 for h in range(polygon.holes()):
209 hole = [(p.x - origin.x, p.y - origin.y) for p in polygon.each_point_hole(h)]
210 contours.append((hole, -math.copysign(1.0, signed_area(hole))))
211 return cls(contours)
213 def area(self) -> float:
214 return sum(sign * signed_area(contour) for contour, sign in self.contours)
216 def bbox(self, origin: kdb.Point) -> kdb.DBox:
217 xs = [p[0] for contour, _ in self.contours for p in contour]
218 ys = [p[1] for contour, _ in self.contours for p in contour]
219 return kdb.DBox(min(xs) + origin.x, min(ys) + origin.y, max(xs) + origin.x, max(ys) + origin.y)
221 def parts(self,
222 sites: Optional[NodeSites],
223 net_name: NetName,
224 origin: kdb.Point) -> Iterator[Tuple[NetName, Area]]:
225 """
226 The parts of the area by the node of the site nearest to them (the whole area for a net without sites)
227 """
228 if sites is None:
229 yield net_name, self
230 return
231 candidates = sites.candidates(self.bbox(origin))
232 if len(candidates) == 1:
233 yield candidates[0].node_name, self
234 return
235 for i, site in enumerate(candidates):
236 part = self.clipped_to_cell(candidates, i, origin)
237 if part.contours:
238 yield site.node_name, part
240 def clipped_to_cell(self, sites: Sequence[NodeSite], index: int, origin: kdb.Point) -> Area:
241 """
242 The part of the area nearer to the site of the index than to the other sites (its Voronoi cell)
243 """
244 sx, sy = sites[index].x - origin.x, sites[index].y - origin.y
245 contours = self.contours
246 for j, other in enumerate(sites):
247 if j == index:
248 continue
249 ox, oy = other.x - origin.x, other.y - origin.y
250 # NOTE: |x - s|² ≤ |x - o|² ⇔ (o - s)·x ≤ (|o|² - |s|²) / 2
251 nx, ny, c = ox - sx, oy - sy, (ox * ox + oy * oy - sx * sx - sy * sy) / 2.0
252 contours = [(clipped, sign) for contour, sign in contours
253 if len(clipped := clip(contour, nx, ny, c)) >= 3]
254 return Area(contours)
257class CapacitanceDistributor:
258 """
259 The nodes of the resistor networks, which the capacitances go to, by their geometry
260 """
261 def __init__(self,
262 sites_by_net_and_layer: Dict[Tuple[NetName, LayerName], NodeSites],
263 sites_by_net: Dict[NetName, NodeSites],
264 substrate_layer_name: Optional[LayerName] = None,
265 piece_names: Collection[str] = ()):
266 """
267 :param piece_names: of the pieces of nets (see NetPiece), which are no nodes of the netlist, unlike nets
268 """
269 self.sites_by_net_and_layer = sites_by_net_and_layer
270 self.sites_by_net = sites_by_net
271 self.substrate_layer_name = substrate_layer_name
272 self.piece_names = piece_names
274 @classmethod
275 def from_networks(cls,
276 networks: Iterable[Tuple[r_network_pb2.RNetwork, Dict[int, NetName]]],
277 substrate_layer_name: Optional[LayerName] = None,
278 substrate_well_layer_names: Collection[LayerName] = ()) -> CapacitanceDistributor:
279 """
280 :param networks: each resistor network, with the netlist node names by node ID
281 :param substrate_layer_name: the layer of the substrate, which has no nodes of its own
282 :param substrate_well_layer_names: the wells the substrate is split into, whose nodes are the ones
283 of the substrate (see sites)
284 """
285 sites_by_net_and_layer: Dict[Tuple[NetName, LayerName], List[NodeSite]] = defaultdict(list)
286 sites_by_net: Dict[NetName, List[NodeSite]] = defaultdict(list)
287 piece_names: Set[str] = set()
288 for network, node_names in networks:
289 for node in network.nodes:
290 site = NodeSite.from_node(node, node_names[node.node_id])
291 if site is None:
292 continue
293 sites_by_net_and_layer[(network.net_name, node.layer_name)].append(site)
294 if substrate_layer_name is not None and node.layer_name in substrate_well_layer_names:
295 sites_by_net_and_layer[(network.net_name, substrate_layer_name)].append(site)
296 sites_by_net[network.net_name].append(site)
297 # NOTE: the capacitances of a piece of a net go to its own nodes, not to a nearer one of another piece
298 for piece_name in node.piece_names:
299 piece_names.add(piece_name)
300 sites_by_net_and_layer[(piece_name, node.layer_name)].append(site)
301 if substrate_layer_name is not None and node.layer_name in substrate_well_layer_names:
302 sites_by_net_and_layer[(piece_name, substrate_layer_name)].append(site)
303 sites_by_net[piece_name].append(site)
304 return cls(sites_by_net_and_layer={key: NodeSites(sites) for key, sites in sites_by_net_and_layer.items()},
305 sites_by_net={net_name: NodeSites(sites) for net_name, sites in sites_by_net.items()},
306 substrate_layer_name=substrate_layer_name,
307 piece_names=piece_names)
309 def has_nodes(self, net_name: NetName) -> bool:
310 return net_name in self.sites_by_net
312 def whole_capacitance(self, net_a: NetName, net_b: NetName) -> Dict[NodePair, float]:
313 """
314 :return: the fractions of a capacitance without geometry to go by: all of it between the nets,
315 for a piece of a net on one of its nodes
316 """
317 def node_of(net_name: NetName) -> NetName:
318 return self.sites_by_net[net_name].sites[0].node_name if net_name in self.piece_names else net_name
319 return {(node_of(net_a), node_of(net_b)): 1.0}
321 def sites(self, net_name: NetName, layer_name: LayerName) -> Optional[NodeSites]:
322 """
323 The sites of the nodes of the net on the layer,
324 otherwise on any layer (e.g. a layer the resistance extraction doesn't model),
325 but on the substrate the ones of its wells, otherwise none (the node of the net),
326 as the rest of the substrate is ideal, and not the metal above (#288).
327 A piece of a net always has sites, as it's no node of the netlist (e.g. a well without nodes within a block)
328 """
329 sites = self.sites_by_net_and_layer.get((net_name, layer_name), None)
330 if sites or (layer_name == self.substrate_layer_name and net_name not in self.piece_names):
331 return sites
332 return self.sites_by_net.get(net_name, None)
334 def area_fractions(self,
335 net_a: NetName, layer_a: LayerName,
336 net_b: NetName, layer_b: LayerName,
337 area: Optional[kdb.Region]) -> Dict[NodePair, float]:
338 """
339 The fractions of a capacitance across an area (e.g. an overlap) by the nodes nearest to its parts
341 :return: the fraction by node pair, which sum up to 1
342 """
343 if area is None or area.is_empty():
344 return self.whole_capacitance(net_a, net_b)
346 # NOTE: relative to the center, to keep the coordinates small
347 origin = area.bbox().center()
348 sites_a = self.sites(net_a, layer_a)
349 sites_b = self.sites(net_b, layer_b)
351 fractions: Dict[NodePair, float] = defaultdict(float)
352 for node_a, part_a in Area.from_region(area, origin).parts(sites_a, net_a, origin):
353 for node_b, part in part_a.parts(sites_b, net_b, origin):
354 fractions[(node_a, node_b)] += part.area()
355 return self._normalized(fractions, net_a, net_b)
357 def edge_fractions(self,
358 net_a: NetName, layer_a: LayerName, edge_a: Optional[kdb.Edge],
359 net_b: NetName, layer_b: LayerName, edge_b: Optional[kdb.Edge]) -> Dict[NodePair, float]:
360 """
361 The fractions of a capacitance between two edges (e.g. a sidewall) by the nodes nearest to their parts
363 :param edge_a: the edge of net A
364 :param edge_b: the edge of net B, its points face the ones of edge A (same direction)
365 :return: the fraction by node pair, which sum up to 1
366 """
367 if edge_a is None or edge_b is None:
368 return self.whole_capacitance(net_a, net_b)
370 parts_a = self._edge_parts(net_a, layer_a, edge_a)
371 parts_b = self._edge_parts(net_b, layer_b, edge_b)
373 # NOTE: the parts of both edges facing each other
374 fractions: Dict[NodePair, float] = defaultdict(float)
375 i, j, t = 0, 0, 0.0
376 while i < len(parts_a) and j < len(parts_b):
377 t1 = min(parts_a[i][1], parts_b[j][1])
378 fractions[(parts_a[i][2], parts_b[j][2])] += t1 - t
379 t = t1
380 if parts_a[i][1] <= t1:
381 i += 1
382 if parts_b[j][1] <= t1:
383 j += 1
384 return self._normalized(fractions, net_a, net_b)
386 def _edge_parts(self,
387 net_name: NetName,
388 layer_name: LayerName,
389 edge: kdb.Edge) -> List[Tuple[float, float, NetName]]:
390 sites = self.sites(net_name, layer_name)
391 if sites is None:
392 return [(0.0, 1.0, net_name)]
393 return edge_parts((edge.p1.x, edge.p1.y), (edge.p2.x, edge.p2.y), sites.candidates(edge.bbox()))
395 def _normalized(self, fractions: Dict[NodePair, float], net_a: NetName, net_b: NetName) -> Dict[NodePair, float]:
396 total = sum(fractions.values())
397 if total <= 0.0:
398 return self.whole_capacitance(net_a, net_b)
399 # NOTE: in order, so that the sums are the same from run to run
400 return {pair: fraction / total for pair, fraction in sorted(fractions.items()) if fraction > 0.0}