Coverage for klayout_pex/netlist/rc

2# --------------------------------------------------------------------------------

3# SPDX-FileCopyrightText: 2024-2026 Martin Jan Köhler and Harald Pretl

4# Johannes Kepler University, Institute for Integrated Circuits.

6# This file is part of KPEX

7# (see https://github.com/iic-jku/klayout-pex).

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#

25"""

26Reduction of RC networks, keeping their behaviour at the protected nodes (#214).

28Two passes, both realizable (the result is again an RC network with positive values):

30TICER (Sheehan, ICCAD 1999 and TCAD 2007) eliminates the *quick* nodes, those whose time constant

31τ_N = χ_N / γ_N (capacitance and conductance sums at the node) is at most a threshold τ_max,

32by the star-mesh transform: each pair of former neighbours i, j gets

34 g_ij += g_iN g_jN / γ_N (exact: the Schur complement of G, so DC is exact)

35 c_ij += (g_iN c_jN + c_iN g_jN) / γ_N (the quasi-DC approximation, error O(2π f τ_N))

37The capacitance at N is moved, not lost: between N's net and every other net it is conserved exactly,

38and in total it only shrinks by Σ g_iN c_iN / γ_N for neighbours with a resistor *and* a capacitor to N

39(that capacitor is shorted at the frequencies where N is quick).

40With τ_max = ε / (2π f_max), the relative error per eliminated node is about ε at f_max (Theorem 1),

41the errors of many eliminations can add up (Sec. VIII).

43So TICER keeps DC and the capacitances, the response to first order in f. The next order is not kept:

44the losses of the AC currents in the eliminated resistors, e.g. the series resistance (the Q) of a MOM

45capacitor, shrink or vanish, unless τ_max is small against 1 / (2π f Q).

47Capacitor-only nodes (no resistor, e.g. floating metal) are eliminated exactly, at every frequency,

48by the capacitive star-mesh, the Schur complement of C (TICER's slow-node rule in its exact limit γ_N = 0):

50 c_ij += c_iN c_jN / χ_N

52A plate between two nets becomes their series capacitance. Before that, every *floating island*

53(nodes connected by resistors, none of them protected) is merged into one node: exact at DC, at other

54frequencies it neglects the island's internal resistances.

56Slow nodes with resistors (the general slow-node rule, Sheehan 1999, (4.1)) are not eliminated: the rule is

57exact only at DC and at infinite frequency, in between it needs a lowest frequency of interest,

58but operating points and transients start at DC.

60Both passes skip nodes with too many neighbours, to bound the fill-in: TICER those with more than

61a maximum number of resistors (RDeg in Sheehan 2007; d resistors give up to d(d-1)/2 new ones),

62the capacitor-only pass those with more than a maximum number of capacitors (d(d-1)/2 new ones).

63The capacitor-only nodes kept for that have no DC path, so they are tied to ground by a large resistor

64(see :data:`TIE_RESISTANCE`), a mark of the node (see :meth:`RCNetwork.tie`), which TICER doesn't see as a resistor.

65The capacitor-only pass drops the ties it is given and ties again what it keeps, so that a reduced network

66can be reduced again (e.g. with a higher degree limit).

67"""

69from __future__ import annotations

71from dataclasses import dataclass

72import heapq

73import math

74from typing import *

76from .rc_network import RCNetwork

79GROUND_NODE_NAME = '0'

80"""The node the capacitor-only nodes are tied to (SPICE's global ground)"""

82TIE_RESISTANCE = 1e12

83"""Ω, ties a capacitor-only node above the degree limit to ground, so that DC has a solution"""

86@dataclass(frozen=True)

87class ReductionOptions:

88 """

89 Which passes run, and their limits (the defaults are those of #214)

90 """

92 ticer: bool = True

93 ticer_tau: float = 0.1e-12

94 """τ_max [s]: nodes with a time constant up to this are quick"""

95 ticer_max_degree: int = 5

96 """TICER keeps nodes with more resistors than this"""

98 floating: bool = True

99 """merge the floating islands, eliminate the capacitor-only nodes, tie the rest to ground"""

100 floating_max_degree: int = 64

101 """capacitor-only nodes with more capacitors than this are kept and tied to ground"""

102

103 def __post_init__(self):

104 """

105 :raises ValueError: naming every invalid value and the valid ones

106 """

107 problems: List[str] = []

108 tau = self.ticer_tau

109 if isinstance(tau, bool) or not isinstance(tau, (int, float)) or not math.isfinite(tau) or tau <= 0:

110 problems.append(f"ticer_tau must be a finite number of seconds > 0, got {tau!r}")

111 for name in ('ticer_max_degree', 'floating_max_degree'):

112 value = getattr(self, name)

113 if isinstance(value, bool) or not isinstance(value, int) or value < 1:

114 problems.append(f"{name} must be an integer ≥ 1, got {value!r}")

115 for name in ('ticer', 'floating'):

116 value = getattr(self, name)

117 if not isinstance(value, bool):

118 problems.append(f"{name} must be True or False, got {value!r}")

119 if not problems and not (self.ticer or self.floating):

120 problems.append("ticer and floating are both False, there is nothing to do")

121 if problems:

122 raise ValueError('; '.join(problems))

123

124

125@dataclass

126class ReductionStatistics:

127 floating_islands: int = 0

128 """floating islands (resistor-connected, no protected node) merged into one node each"""

129 floating_island_nodes: int = 0

130 """nodes merged away by that"""

131 quick_nodes: int = 0

132 """nodes eliminated by TICER"""

133 capacitor_only_nodes: int = 0

134 """capacitor-only nodes eliminated (exactly)"""

135 tied_nodes: int = 0

136 """capacitor-only nodes kept for their degree, tied to ground"""

137

138

139# --------------------------------------------------------------------------------- elementary steps

140

141def eliminate_quick_node(network: RCNetwork, node: int):

142 """

143 Remove a node with resistors by TICER's quick-node rules (Sheehan 2007, (27)), applied to every

144 unordered pair of neighbours (unlike Fig. 5 of the paper, whose 'j > i' on line 6 drops

145 the capacitors g_iN c_jN / G_N of the pairs with j < i)

146 """

147 neighbours = list(network.branches(node).items())

148 conductance = sum(b.conductance for _, b in neighbours)

149 if conductance <= 0.0:

150 raise ValueError(f"Node {network.name(node)} has no resistor, TICER does not apply")

151 for index, (node_i, branch_i) in enumerate(neighbours):

152 g_i, c_i = branch_i.conductance, branch_i.capacitance

153 for node_j, branch_j in neighbours[index + 1:]:

154 g_j, c_j = branch_j.conductance, branch_j.capacitance

155 network.add(node_i, node_j,

156 conductance=g_i * g_j / conductance,

157 capacitance=(g_i * c_j + c_i * g_j) / conductance)

158 network.remove_node(node)

159

160

161def eliminate_capacitor_only_node(network: RCNetwork, node: int):

162 """

163 Remove a node without resistors exactly, by the capacitive star-mesh c_ij += c_iN c_jN / χ_N

164 """

165 neighbours = list(network.branches(node).items())

166 if any(b.conductance != 0.0 for _, b in neighbours):

167 raise ValueError(f"Node {network.name(node)} has a resistor, it is not capacitor-only")

168 capacitance = sum(b.capacitance for _, b in neighbours)

169 if capacitance != 0.0:

170 for index, (node_i, branch_i) in enumerate(neighbours):

171 for node_j, branch_j in neighbours[index + 1:]:

172 network.add(node_i, node_j,

173 capacitance=branch_i.capacitance * branch_j.capacitance / capacitance)

174 network.remove_node(node)

175

176

177# ------------------------------------------------------------------------------------------- passes

178

179def merge_floating_islands(network: RCNetwork) -> Tuple[int, int]:

180 """

181 Merge each floating island (two or more nodes connected by resistors, none of them protected)

182 into its node with the smallest name.

183

184 :return: the number of islands, and of the nodes merged away

185 """

186 islands = 0

187 merged_nodes = 0

188 visited: Set[int] = set()

189 for start in network.nodes():

190 if start in visited:

191 continue

192 island = [start]

193 visited.add(start)

194 index = 0

195 while index < len(island):

196 for neighbour, branch in network.branches(island[index]).items():

197 if branch.conductance != 0.0 and neighbour not in visited:

198 visited.add(neighbour)

199 island.append(neighbour)

200 index += 1

201 if len(island) < 2 or any(network.is_protected(n) for n in island):

202 continue

203 island.sort(key=network.sort_key)

204 for node in island[1:]:

205 network.merge_node(node, into=island[0])

206 islands += 1

207 merged_nodes += len(island) - 1

208 return islands, merged_nodes

209

210

211HeapKey = Tuple[Any, ...]

212

213

214def _eliminate_in_order(network: RCNetwork,

215 heap_key: Callable[[int], Optional[HeapKey]],

216 eliminate: Callable[[RCNetwork, int], None]) -> int:

217 """

218 Eliminate the nodes that have a heap key (None for those to keep), smallest key first.

219 An elimination changes the neighbours' branches, so they get new keys

220 (a heap with lazy deletion: entries whose key is no longer the node's key are skipped).

221

222 :return: the number of nodes eliminated

223 """

224 heap: List[Tuple[HeapKey, int]] = []

225 queued: Dict[int, HeapKey] = {} # node → the key of its valid heap entry

226

227 def queue(node: int):

228 key = heap_key(node)

229 if key is None:

230 queued.pop(node, None)

231 elif queued.get(node) != key:

232 queued[node] = key

233 heapq.heappush(heap, (key, node))

234

235 for node in network.nodes():

236 queue(node)

237

238 eliminated = 0

239 while heap:

240 key, node = heapq.heappop(heap)

241 if queued.get(node) != key:

242 continue

243 del queued[node]

244 neighbours = list(network.branches(node))

245 eliminate(network, node)

246 eliminated += 1

247 for neighbour in neighbours:

248 queue(neighbour)

249 return eliminated

250

251

252def eliminate_quick_nodes(network: RCNetwork, tau: float, max_degree: int) -> int:

253 """

254 TICER (Sheehan 2007, Fig. 6, with a heap as in Sec. IV-D): eliminate the unprotected quick nodes

255 (time constant ≤ tau) with at most max_degree resistors, those with fewer resistors and smaller

256 time constants first. Nodes with one resistor (leaves) are deferred to a final sweep

257 (Sec. IV-B), so that stubs are not eaten from their end one node at a time.

258

259 :return: the number of nodes eliminated

260 """

261 def heap_key(node: int) -> Optional[HeapKey]:

262 if network.is_protected(node):

263 return None

264 degree = network.resistive_degree(node)

265 if degree < 2 or degree > max_degree:

266 return None

267 time_constant = network.time_constant(node)

268 if time_constant > tau:

269 return None

270 return degree, time_constant, network.sort_key(node)

271

272 eliminated = _eliminate_in_order(network, heap_key, eliminate_quick_node)

273

274 leaves = [n for n in network.nodes()

275 if not network.is_protected(n) and network.resistive_degree(n) == 1]

276 leaves.sort(key=lambda n: (network.time_constant(n), network.sort_key(n)))

277 for node in leaves:

278 if network.is_alive(node) and network.resistive_degree(node) == 1 \

279 and network.time_constant(node) <= tau:

280 eliminate_quick_node(network, node)

281 eliminated += 1

282 return eliminated

283

284

285def eliminate_capacitor_only_nodes(network: RCNetwork, max_degree: int) -> int:

286 """

287 Eliminate the unprotected nodes without resistor with at most max_degree capacitors exactly,

288 those with fewer capacitors first.

289

290 :return: the number of nodes eliminated

291 """

292 def heap_key(node: int) -> Optional[HeapKey]:

293 if network.is_protected(node) or network.resistive_degree(node) != 0:

294 return None

295 degree = network.degree(node)

296 if degree == 0 or degree > max_degree:

297 return None

298 return degree, network.sort_key(node)

299

300 return _eliminate_in_order(network, heap_key, eliminate_capacitor_only_node)

301

302

303def tie_capacitor_only_nodes(network: RCNetwork) -> int:

304 """

305 Tie every unprotected node that has capacitors but no resistor to ground (node '0'),

306 by :data:`TIE_RESISTANCE`, so that DC has a solution (see :meth:`RCNetwork.tie`).

307

308 :return: the number of nodes tied

309 """

310 nodes = [n for n in network.nodes()

311 if not network.is_protected(n) and network.degree(n) > 0 and network.resistive_degree(n) == 0]

312 for node in nodes:

313 network.tie(node)

314 return len(nodes)

315

316

317def reduce_network(network: RCNetwork, options: ReductionOptions) -> ReductionStatistics:

318 """

319 Run the passes the options enable, in this order:

320 merge the floating islands, TICER, eliminate the capacitor-only nodes, tie the remaining ones to ground.

321

322 TICER runs before the capacitor-only elimination, so that a plate's neighbours along a wire are

323 merged first: the plate then has fewer capacitors, gives fewer new ones (d(d-1)/2)

324 and stays below its degree limit more often. The protected nodes are never eliminated or merged.

325 The floating passes drop the ties of the network first, the last one ties again what is left.

326 """

327 statistics = ReductionStatistics()

328 if options.floating:

329 for node in network.tied_nodes():

330 network.untie(node)

331 statistics.floating_islands, statistics.floating_island_nodes = merge_floating_islands(network)

332 if options.ticer:

333 statistics.quick_nodes = eliminate_quick_nodes(network, tau=options.ticer_tau,

334 max_degree=options.ticer_max_degree)

335 if options.floating:

336 statistics.capacitor_only_nodes = eliminate_capacitor_only_nodes(

337 network, max_degree=options.floating_max_degree)

338 statistics.tied_nodes = tie_capacitor_only_nodes(network)

339 return statistics

Coverage for klayout_pex/netlist/rc_reduction.py: 99%

165 statements