Coverage for klayout_pex/rcx25/r/resistor_network.py: 88%
227 statements
« prev ^ index » next coverage.py v7.8.0, created at 2025-03-31 19:36 +0000
1#
2# --------------------------------------------------------------------------------
3# SPDX-FileCopyrightText: 2024 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/martinjankoehler/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#
25from __future__ import annotations
26from dataclasses import dataclass
27from typing import *
29import klayout.db as kdb
31from klayout_pex.log import (
32 debug,
33 error,
34 warning,
35)
36from .conductance import Conductance
37from ..types import LayerName
38from ...klayout.lvsdb_extractor import KLayoutDeviceTerminal, KLayoutDeviceInfo
40NodeID = int
43class ResistorNetwork:
44 """
45 A general container for a resistor network
47 The container manages the networks through node IDs. Those are integers
48 describing one network node. A node has a location (a kdb.Point) and
49 one to many resistors connecting two of them each.
51 Attributes are:
52 * nodes -> dict[kdb.Point, NodeID]: The node IDs per kdb.Point
53 * locations -> dict[NodeID, kdb.Point]: the kdb.Point of a node (given by ID)
54 * s -> dict[(NodeID, NodeID), Conductance]: the registors
55 * node_to_s -> dict[NodeID, list[(Conductance, NodeID)]]: the resistors connected to a node with the
56 node connected by the resistor
57 * precious -> set[NodeID]: a set of node IDs for the precious nodes
58 * node_names -> dict[NodeID, str]: the names of nodes
59 """
61 def __init__(self):
62 self.nodes = {}
63 self.locations = {}
64 self.s = {}
65 self.node_to_s = {}
66 self.next_id = 0
67 self.precious = set()
68 self.node_names = {}
70 @staticmethod
71 def is_skinny_tri(pts: list[kdb.Point]) -> Optional[bool]:
72 for i in range(0, 3):
73 pm1 = pts[i]
74 p0 = pts[(i + 1) % 3]
75 p1 = pts[(i + 2) % 3]
77 lm1 = (p0 - pm1).sq_length()
78 l0 = (p1 - p0).sq_length()
79 l1 = (pm1 - p1).sq_length()
81 if l0 + l1 < lm1 * (1.0 - 1e-10):
82 return i != 0
84 return None
86 @staticmethod
87 def expand_skinny_tris(p: kdb.Polygon) -> List[kdb.Polygon]:
88 pts = [pt for pt in p.each_point_hull()]
90 i = ResistorNetwork.is_skinny_tri(pts)
91 if i is None:
92 return [p]
94 pm1 = pts[i]
95 p0 = pts[(i + 1) % 3]
96 p1 = pts[(i + 2) % 3]
98 lm1 = (p0 - pm1).sq_length()
99 px = p0 + (pm1 - p0) * ((pm1 - p0).sprod(p1 - p0) / lm1)
101 return [kdb.Polygon([p0, p1, px]), kdb.Polygon([px, p1, pm1])]
103 def __str__(self) -> str:
104 return self.to_string(False)
106 def to_string(self, resistance: bool = False) -> str:
107 """ A more elaborate string generator
109 :param resistance: if true, prints resistance values instead of conductance values
110 """
112 res: List[str] = []
113 res.append("Nodes:")
114 for nid in sorted(self.locations.keys()):
115 nn = self.node_names[nid] if nid in self.node_names else str(nid)
116 res.append(f" {nn}: {self.locations[nid]}")
118 if not resistance:
119 res.append("Conductors:")
120 for ab in sorted(self.s.keys()):
121 if ab[0] < ab[1]:
122 nna = self.node_names[ab[0]] if ab[0] in self.node_names else str(ab[0])
123 nnb = self.node_names[ab[1]] if ab[1] in self.node_names else str(ab[1])
124 res.append(f" {nna},{nnb}: {self.s[ab]}")
125 return "\n".join(res)
127 res.append("Resistors:")
128 for ab in sorted(self.s.keys()):
129 if ab[0] < ab[1]:
130 nna = self.node_names[ab[0]] if ab[0] in self.node_names else str(ab[0])
131 nnb = self.node_names[ab[1]] if ab[1] in self.node_names else str(ab[1])
132 res.append(f" {nna},{nnb}: {self.s[ab].res()}")
133 return "\n".join(res)
135 def check(self) -> int:
136 """
137 A self-check.
139 :return: the number of errors found
140 """
141 errors = 0
142 for nid in sorted(self.locations.keys()):
143 loc = self.locations[nid]
144 if loc not in self.nodes:
145 error(f"location {loc} with id {nid} not found in nodes list")
146 errors += 1
147 for loc in sorted(self.nodes.keys()):
148 nid = self.nodes[loc]
149 if nid not in self.locations:
150 error(f"node id {nid} with location {loc} not found in locations list")
151 errors += 1
152 for ab in sorted(self.s.keys()):
153 if (ab[1], ab[0]) not in self.s:
154 error(f"reverse of key pair {ab} not found in conductor list")
155 errors += 1
156 if ab[0] not in self.node_to_s:
157 error(f"No entry for node {ab[0]} in star list")
158 errors += 1
159 elif ab[1] not in self.node_to_s:
160 error(f"No entry for node {ab[1]} in star list")
161 errors += 1
162 else:
163 cond = self.s[ab]
164 if (cond, ab[1]) not in self.node_to_s[ab[0]]:
165 error(f"Missing entry {cond}@{ab[1]} in star list")
166 errors += 1
167 if (cond, ab[0]) not in self.node_to_s[ab[1]]:
168 error(f"Missing entry {cond}@{ab[0]} in star list")
169 errors += 1
170 for nid in sorted(self.node_to_s.keys()):
171 star = self.node_to_s[nid]
172 for s in star:
173 if (nid, s[1]) not in self.s:
174 error(f"Missing star entry {nid},{s[1]} in conductor list")
175 errors += 1
176 return errors
178 # TODO: this is slow!
179 def node_ids(self, edge: kdb.Edge) -> List[NodeID]:
180 """
181 Gets the node IDs that are on a given Edge
182 """
183 return [nid for (p, nid) in self.nodes.items() if edge.contains(p)]
185 def node_id(self, point: kdb.Point) -> NodeID:
186 """
187 Gets the node ID for a given point
188 """
189 if point in self.nodes:
190 return self.nodes[point]
192 nid = self.next_id
193 self.nodes[point] = nid
194 self.locations[nid] = point
195 self.next_id += 1
196 return nid
198 def has_node(self, point: kdb.Point) -> bool:
199 """
200 Returns a value indicating that there is a node with the given kdb.Point
201 """
202 return point in self.nodes
204 def name(self, nid: int, name: str):
205 """
206 Provides a name for a node
207 """
208 self.node_names[nid] = name
210 def mark_precious(self, nid: NodeID):
211 """
212 Marks a node a precious
214 Precious nodes are not eliminated
215 """
216 self.precious.add(nid)
218 def location(self, nid: NodeID) -> Optional[kdb.Point]:
219 """
220 Gets the location for a given node ID
221 """
222 if nid in self.locations:
223 return self.locations[nid]
225 return None
227 def add_cond(self, a: NodeID, b: NodeID, cond: Conductance):
228 """
229 Adds a resistor connecting two nodes
231 If a resistor already exists connecting these nodes, the new one is added in parallel to it.
232 """
233 if (a, b) in self.s:
234 self.s[(a, b)].add_parallel(cond)
235 else:
236 self.s[(a, b)] = self.s[(b, a)] = cond
237 if a not in self.node_to_s:
238 self.node_to_s[a] = []
239 self.node_to_s[a].append((cond, b))
240 if b not in self.node_to_s:
241 self.node_to_s[b] = []
242 self.node_to_s[b].append((cond, a))
244 def eliminate_node(self, nid: NodeID):
245 """
246 Eliminates a node
248 This uses start to n-mesh transformation to eliminate
249 the node.
250 """
251 if nid not in self.node_to_s:
252 return
254 star = self.node_to_s[nid]
255 s_sum = 0.0
256 for s in star:
257 s_sum += s[0].cond
258 if abs(s_sum) > 1e-10:
259 for i in range(0, len(star) - 1):
260 for j in range(i + 1, len(star)):
261 s1 = star[i]
262 s2 = star[j]
263 c = s1[0].cond * s2[0].cond / s_sum
264 self.add_cond(s1[1], s2[1], Conductance(c))
265 self.remove_node(nid)
267 def remove_node(self, nid: NodeID):
268 """
269 Deletes a node and the corresponding resistors
270 """
271 if nid not in self.node_to_s:
272 return
273 star = self.node_to_s[nid]
274 for (cond, other) in star:
275 if other in self.node_to_s:
276 self.node_to_s[other].remove((cond, nid))
277 del self.s[(nid, other)]
278 del self.s[(other, nid)]
279 del self.node_to_s[nid]
280 del self.nodes[self.locations[nid]]
281 del self.locations[nid]
283 def connect_nodes(self, a: NodeID, b: NodeID):
284 """
285 Contracts a and b into a.
286 NOTE: b will be removed and is no longer valid afterwards
287 """
288 if b not in self.node_to_s:
289 return
290 star_b = self.node_to_s[b]
291 for (cond, other) in star_b:
292 if other != a:
293 self.add_cond(a, other, cond)
294 if other in self.node_to_s:
295 self.node_to_s[other].remove((cond, b))
296 del self.s[(b, other)]
297 del self.s[(other, b)]
298 del self.node_to_s[b]
299 del self.nodes[self.locations[b]]
300 del self.locations[b]
302 def eliminate_all(self):
303 """
304 Runs the elimination loop
306 The loop finishes when only precious nodes are left.
307 """
309 debug(f"Starting with {len(self.node_to_s)} nodes with {len(self.s)} edges.")
311 niter = 0
312 nmax = 3
313 while nmax is not None:
314 another_loop = True
316 while another_loop:
317 nmax_next = None
318 to_eliminate = []
319 for nid in sorted(self.node_to_s.keys()):
320 if nid not in self.precious:
321 n = len(self.node_to_s[nid])
322 if n <= nmax:
323 to_eliminate.append(nid)
324 elif nmax_next is None or n < nmax_next:
325 nmax_next = n
327 if len(to_eliminate) == 0:
328 another_loop = False
329 nmax = nmax_next
330 debug(f"Nothing left to eliminate with nmax={nmax}.")
331 else:
332 for nid in to_eliminate:
333 self.eliminate_node(nid)
334 niter += 1
335 debug(f"Nodes left after iteration {niter} with nmax={nmax}: "
336 f"{len(self.node_to_s)} with {len(self.s)} edges.")
339@dataclass
340class ResistorNetworks:
341 layer_name: str
342 layer_sheet_resistance: float # mΩ/µm^2
343 networks: List[ResistorNetwork]
345 def find_network_nodes(self, location: kdb.Polygon) -> List[Tuple[ResistorNetwork, NodeID]]:
346 matches = []
348 for nw in self.networks:
349 for point, nid in nw.nodes.items():
350 if location.inside(point):
351 print(f"node {nid} is located ({point}) within search area {location}")
352 matches.append((nw, nid))
354 return matches
357@dataclass
358class ViaJunction:
359 layer_name: LayerName
360 network: ResistorNetwork
361 node_id: NodeID
364@dataclass
365class DeviceTerminal:
366 device: KLayoutDeviceInfo
367 device_terminal: KLayoutDeviceTerminal
370@dataclass
371class ViaResistor:
372 bottom: ViaJunction | DeviceTerminal
373 top: ViaJunction
374 resistance: float # mΩ
377@dataclass
378class MultiLayerResistanceNetwork:
379 resistor_networks_by_layer: Dict[LayerName, ResistorNetworks]
380 via_resistors: List[ViaResistor]