SWITCH = "switch"

ALL2ALL = "all_to_all"

RING = "ring"

CHAIN = "chain"

MESH2D = "mesh2d"

TORUS2D = "torus2d"

MCHAIN_NRING = "mchain_nring"

kind: TopoKind

shape: Tuple[int, int]

hop_latency: float = 1.0

link_bandwidth: float = 1.0

switch_center_in_bw: Optional[float] = None

switch_center_out_bw: Optional[float] = None

left_in: Optional[callable] = None

left_out: Optional[callable] = None

right_in: Optional[callable] = None

right_out: Optional[callable] = None

up_in: Optional[callable] = None

up_out: Optional[callable] = None

down_in: Optional[callable] = None

down_out: Optional[callable] = None

_show_rates_in_repr: bool = field(

default=False,

repr=False,

compare=False,

)

def __repr__(self) -> str:

"""Return rates only for explicitly caller-owned topology objects."""

summary = (

f"Topology(kind={self.kind.value!r}, shape={self.shape!r}"

)

if self._show_rates_in_repr:

summary += (

f", hop_latency={self.hop_latency!r}, "

f"link_bandwidth={self.link_bandwidth!r}"

)

if self.switch_center_in_bw is not None:

summary += (

f", switch_center_in_bw={self.switch_center_in_bw!r}, "

f"switch_center_out_bw={self.switch_center_out_bw!r}"

)

return summary + ")"

def to_id(self, r: int, c: int) -> int:

M, N = self.shape

return r * N + c

def to_rc(self, idx: int) -> Tuple[int, int]:

M, N = self.shape

return divmod(idx, N)

def ports(self, side: str) -> List[int]:

if self.kind == TopoKind.SWITCH:

return [-1]

if self.kind == TopoKind.ALL2ALL:

fn = {

"left_in": self.left_in, "left_out": self.left_out,

"right_in": self.right_in, "right_out": self.right_out,

"up_in": self.up_in, "up_out": self.up_out,

"down_in": self.down_in, "down_out": self.down_out,

}.get(side)

if fn is not None:

coords = fn(self.shape)

return [self.to_id(r, c) for (r, c) in coords]

M, N = self.shape

S = M * N

if S < 4:

raise ValueError("ALL2ALL 需要至少 4 个节点以均匀分配四个方向的端口")

idxs = list(range(S))

group = {0: [], 1: [], 2: [], 3: []}

for i in idxs:

group[i % 4].append(i)

mapping = {

"left_in": group[0], "left_out": group[0],

"right_in": group[1], "right_out": group[1],

"up_in": group[2], "up_out": group[2],

"down_in": group[3], "down_out": group[3],

}

return mapping.get(side, [])

assert self.kind in {TopoKind.MESH2D, TopoKind.TORUS2D, TopoKind.RING, TopoKind.CHAIN, TopoKind.MCHAIN_NRING, TopoKind.MRING_NCHAIN}

fn = {

"left_in": self.left_in, "left_out": self.left_out,

"right_in": self.right_in, "right_out": self.right_out,

"up_in": self.up_in, "up_out": self.up_out,

"down_in": self.down_in, "down_out": self.down_out,

}.get(side)

if fn is None:

return []

coords = fn(self.shape)

return [self.to_id(r, c) for (r, c) in coords]

def distance(self, a_id: int, b_id: int) -> int:

if a_id == b_id:

return 0

if self.kind in {TopoKind.SWITCH, TopoKind.ALL2ALL}:

return 1

M, N = self.shape

(ar, ac) = self.to_rc(a_id)

(br, bc) = self.to_rc(b_id)

if self.kind == TopoKind.MESH2D:

return abs(ar - br) + abs(ac - bc)

if self.kind == TopoKind.TORUS2D:

dr = min((br - ar) % M, (ar - br) % M)

dc = min((bc - ac) % N, (ac - bc) % N)

return dr + dc

if self.kind == TopoKind.MCHAIN_NRING:

dr = abs(ar - br)

dc = min((bc - ac) % N, (ac - bc) % N)

return dr + dc

if self.kind == TopoKind.MRING_NCHAIN:

dr = min((br - ar) % M, (ar - br) % M)

dc = abs(ac - bc)

return dr + dc

if self.kind == TopoKind.RING:

delta = abs(bc - ac)

return min(delta, N - delta)

if self.kind == TopoKind.CHAIN:

return abs(bc - ac)

return 0

def route_intra(self, s_id: int, d_id: int) -> List[Tuple[int, int]]:

if s_id == d_id:

return []

if self.kind == TopoKind.SWITCH:

if s_id == -1 and d_id == -1:

return []

if s_id == -1:

return [(-1, d_id)]

if d_id == -1:

return [(s_id, -1)]

return [(s_id, -1), (-1, d_id)]

if self.kind == TopoKind.ALL2ALL:

if s_id == -1 and d_id == -1:

return []

if s_id == -1:

return [(-1, d_id)]

if d_id == -1:

return [(s_id, -1)]

return [(s_id, d_id)]

M, N = self.shape

(sr, sc) = self.to_rc(s_id)

(dr, dc) = self.to_rc(d_id)

hops: List[Tuple[int, int]] = []

def id_of(r, c): return self.to_id(r % M, c % N)

if self.kind in {TopoKind.MESH2D, TopoKind.TORUS2D, TopoKind.MCHAIN_NRING, TopoKind.MRING_NCHAIN}:

r_path: List[int] = []

if self.kind in {TopoKind.MESH2D, TopoKind.MCHAIN_NRING}:

step = 1 if dr >= sr else -1

for r in range(sr, dr, step):

r_path.append((r, sc))

hops.append((id_of(r, sc), id_of(r + step, sc)))

else: # row is ring (TORUS2D or MRING_NCHAIN)

delta = (dr - sr) % M

neg = (sr - dr) % M

if delta <= neg:

for k in range(delta):

r = (sr + k) % M

hops.append((id_of(r, sc), id_of(r + 1, sc)))

else:

for k in range(neg):

r = (sr - k) % M

hops.append((id_of(r, sc), id_of(r - 1, sc)))

if self.kind in {TopoKind.MESH2D, TopoKind.MRING_NCHAIN}:

step = 1 if dc >= sc else -1

for c in range(sc, dc, step):

hops.append((id_of(dr, c), id_of(dr, c + step)))

else: # col is ring (TORUS2D or MCHAIN_NRING)

delta = (dc - sc) % N

neg = (sc - dc) % N

if delta <= neg:

for k in range(delta):

c = (sc + k) % N

hops.append((id_of(dr, c), id_of(dr, c + 1)))

else:

for k in range(neg):

c = (sc - k) % N

hops.append((id_of(dr, c), id_of(dr, c - 1)))

return hops

if self.kind == TopoKind.RING:

N = self.shape[1]

delta = (dc - sc) % N

neg = (sc - dc) % N

if delta <= neg:

for k in range(delta):

c = (sc + k) % N

hops.append((self.to_id(0, c), self.to_id(0, (c + 1) % N)))

else:

for k in range(neg):

c = (sc - k) % N

hops.append((self.to_id(0, c), self.to_id(0, (c - 1) % N)))

return hops

if self.kind == TopoKind.CHAIN:

step = 1 if dc >= sc else -1

for c in range(sc, dc, step):

hops.append((self.to_id(0, c), self.to_id(0, c + step)))

return hops

assert kind in (TopoKind.MESH2D, TopoKind.TORUS2D, TopoKind.MCHAIN_NRING, TopoKind.MRING_NCHAIN)

assert M >= 1 and N >= 1, "M,N must be >= 1 for mesh/torus"

assert (M == 1 or M % 2 == 0) and (N == 1 or N % 2 == 0), "M,N must be even unless it's 1 for mesh/torus"

def _split_in_out_indices(dim: int):

"""Split indices [0, dim-1] into input/output halves.

if dim == 1:

return (0,), (0,)

return tuple(range(dim // 2, dim)), tuple(range(0, dim // 2))

rows_in, rows_out = _split_in_out_indices(M)

cols_in, cols_out = _split_in_out_indices(N)

left_in_ports = tuple((r, 0) for r in rows_in)

left_out_ports = tuple((r, 0) for r in rows_out)

right_in_ports = tuple((r, N - 1) for r in rows_out)

right_out_ports = tuple((r, N - 1) for r in rows_in)

up_in_ports = tuple((M - 1, c) for c in cols_in)

up_out_ports = tuple((M - 1, c) for c in cols_out)

down_in_ports = tuple((0, c) for c in cols_out)

down_out_ports = tuple((0, c) for c in cols_in)

def constant_ports(ports):

return lambda shape, _ports=ports: list(_ports)

return Topology(

kind=kind, shape=(M, N), hop_latency=hop_latency, link_bandwidth=link_bandwidth,

left_in=constant_ports(left_in_ports),

left_out=constant_ports(left_out_ports),

right_in=constant_ports(right_in_ports),

right_out=constant_ports(right_out_ports),

up_in=constant_ports(up_in_ports),

up_out=constant_ports(up_out_ports),

down_in=constant_ports(down_in_ports),

down_out=constant_ports(down_out_ports),

assert N % 2 == 0, "N must be even for ring"

def left_in(shape):

return [(0, 0)]

def left_out(shape):

return [(0, 0)]

def right_in(shape):

M, N = shape

return [(0, N-1)]

def right_out(shape):

M, N = shape

return [(0, N-1)]

def up_out(shape):

M, N = shape

return [(0, c) for c in range(0, N//2)]

def up_in(shape):

M, N = shape

return [(0, c) for c in range(N//2, N)]

def down_out(shape):

M, N = shape

return [(0, c) for c in range(N//2, N)]

def down_in(shape):

M, N = shape

return [(0, c) for c in range(0, N//2)]

return Topology(

kind=TopoKind.RING, shape=(1, N), hop_latency=hop_latency, link_bandwidth=link_bandwidth,

left_in=left_in, left_out=left_out, right_in=right_in, right_out=right_out,

up_in=up_in, up_out=up_out, down_in=down_in, down_out=down_out

assert N % 2 == 0, "N must be even for chain"

def left_in(shape): return [(0, 0)]

def left_out(shape): return [(0, 0)]

def right_in(shape):

M, N = shape

return [(0, N-1)]

def right_out(shape):

M, N = shape

return [(0, N-1)]

def up_out(shape):

M, N = shape

return [(0, c) for c in range(0, N//2)]

def up_in(shape):

M, N = shape

return [(0, c) for c in range(N//2, N)]

def down_out(shape):

M, N = shape

return [(0, c) for c in range(N//2, N)]

def down_in(shape):

M, N = shape

return [(0, c) for c in range(0, N//2)]

return Topology(

kind=TopoKind.CHAIN, shape=(1, N), hop_latency=hop_latency, link_bandwidth=link_bandwidth,

left_in=left_in, left_out=left_out, right_in=right_in, right_out=right_out,

up_in=up_in, up_out=up_out, down_in=down_in, down_out=down_out

N: int,

*,

hop_latency: float = 1.0,

link_bandwidth: float = 1.0,

switch_center_in_bw: Optional[float] = None,

switch_center_out_bw: Optional[float] = None,

) -> Topology:

return Topology(

kind=TopoKind.SWITCH,

shape=(1, N),

hop_latency=hop_latency,

link_bandwidth=link_bandwidth,

switch_center_in_bw=switch_center_in_bw,

switch_center_out_bw=switch_center_out_bw,

assert M * N >= 4, "ALL2ALL 需要至少 4 个节点"

def _mk_group(shape):

Mx, Nx = shape

S = Mx * Nx

ids = list(range(S))

g = {0: [], 1: [], 2: [], 3: []}

for i in ids:

g[i % 4].append((i // Nx, i % Nx))

return g

def _left_in(shape):

return _mk_group(shape)[0]

def _left_out(shape):

return _mk_group(shape)[0]

def _right_in(shape):

return _mk_group(shape)[1]

def _right_out(shape):

return _mk_group(shape)[1]

def _up_in(shape):

return _mk_group(shape)[2]

def _up_out(shape):

return _mk_group(shape)[2]

def _down_in(shape):

return _mk_group(shape)[3]

def _down_out(shape):

return _mk_group(shape)[3]

return Topology(

kind=TopoKind.ALL2ALL, shape=(M, N), hop_latency=hop_latency, link_bandwidth=link_bandwidth,

left_in=_left_in, left_out=_left_out,

right_in=_right_in, right_out=_right_out,

up_in=_up_in, up_out=_up_out,

down_in=_down_in, down_out=_down_out,

layers: List[Topology]

port_spread: PortSpread = PortSpread.EVEN

name: str = "default_noc_hierarchy"

node_mapper: Optional[callable] = None # f(node_id: int, layers: List[Topology]) -> List[Tuple[int,int]]

# Optional caller-owned energy profile; None selects the bundled reference path.

energy_config: Optional["NocEnergyConfig"] = None

def __str__(self) -> str:

return str(self.name)

def __repr__(self) -> str:

"""Return topology structure without exposing latency/BW in logs."""

layers = ", ".join(repr(layer) for layer in self.layers)

return (

f"Hierarchy(name={self.name!r}, layers=[{layers}], "

f"port_spread={self.port_spread.value!r})"

)

@property

def num_devices(self) -> int:

"""Return the total number of devices covered by this Hierarchy, equal to the product of all layer shapes."""

n = 1

for layer in self.layers:

n *= layer.shape[0] * layer.shape[1]

return n

def coords_to_nid(self, coords: List[Tuple[int, int]]) -> int:

"""Map outer-to-inner layer coordinates [(r_L3,c_L3), (r_L2,c_L2), (r_L1,c_L1)]

assert len(coords) == len(self.layers), "coords 层数需与 layers 一致"

nid = 0

stride = 1

for (r, c), topo in zip(reversed(coords), reversed(self.layers)):

M, N = topo.shape

assert 0 <= r < M and 0 <= c < N

k = r * N + c

nid += k * stride

stride *= (M * N)

return nid

def nid_to_coords(self, nid: int) -> List[Tuple[int, int]]:

"""Convert a linear nid back to outer-to-inner layer coordinates, reversing coords_to_nid:

coords_rev: List[Tuple[int, int]] = []

rem = int(nid)

for topo in reversed(self.layers):

M, N = topo.shape

size = M * N

k = rem % size

rem //= size

r = k // N

c = k % N

coords_rev.append((r, c))

return list(reversed(coords_rev))

def map_node(self, nid: int) -> List[Tuple[int, int]]:

if self.node_mapper:

return self.node_mapper(nid, self.layers)

return self.nid_to_coords(nid)

def first_diff_layer(self, s_coords: List[Tuple[int,int]], d_coords: List[Tuple[int,int]]) -> int:

for i, (a, b) in enumerate(zip(s_coords, d_coords)):

if a != b:

return i

return len(s_coords) - 1

def ports_for_cross(self, topo: Topology, direction: str) -> List[int]:

# direction in {"up_out","up_in","down_out","down_in","left_out","left_in","right_out","right_in"}

return topo.ports(direction)

def route(self, src: int, dst: int, bytes_value: int) -> List[Chain]:

s_coords = self.map_node(src)

d_coords = self.map_node(dst)

# print(f"s_coords: {s_coords}, d_coords: {d_coords}")

log.debug("s_coords: %s, d_coords: %s", s_coords, d_coords)

L = len(self.layers)

chains: List[Chain] = [Chain(hops=[], bytes=bytes_value)]

for ch in chains:

ch.states_coords.append(list(s_coords))

if self.layers[-1].kind == TopoKind.SWITCH:

for ch in chains:

init = list(ch.states_coords[-1])

init[-1] = (-1, -1)

ch.states_coords.append(init)

start_layer = self.first_diff_layer(s_coords, d_coords)

cur_start_ids = [self.layers[i].to_id(*s_coords[i]) for i in range(L)]

def hop_dir(topo: Topology, u: int, v: int) -> str:

(ur, uc) = topo.to_rc(u)

(vr, vc) = topo.to_rc(v)

M, N = topo.shape

if ur != vr:

if topo.kind in {TopoKind.TORUS2D, TopoKind.MRING_NCHAIN}:

return "down" if (vr == (ur - 1) % M) else "up"

else:

return "up" if vr > ur else "down"

else:

if topo.kind in {TopoKind.TORUS2D, TopoKind.RING, TopoKind.MCHAIN_NRING}:

return "left" if (vc == (uc - 1) % N) else "right"

else:

return "right" if vc > uc else "left"

def port_sides(direction: str) -> tuple[str, str]:

if direction == "down":

return "down_out", "up_in"

if direction == "up":

return "up_out", "down_in"

if direction == "right":

return "right_out", "left_in"

if direction == "left":

return "left_out", "right_in"

raise ValueError(f"Invalid direction: {direction}")

def select_index(num: int, layer_idx: int, hop_idx: int) -> int:

if num <= 0:

return -1

x = (int(src) * 1315423911) ^ (int(dst) * 2654435761) ^ (int(layer_idx) * 97) ^ int(hop_idx)

if x < 0:

x = -x

return x % num

def append_state(ch: Chain, snap: List[Tuple[int, int]]):

if not ch.states_coords or ch.states_coords[-1] != snap:

ch.states_coords.append(snap)

for layer_idx in range(start_layer, L):

topo = self.layers[layer_idx]

s_id = cur_start_ids[layer_idx]

d_id = self.layers[layer_idx].to_id(*d_coords[layer_idx])

outer_hops = topo.route_intra(s_id, d_id)

for ch in chains:

for (u, v) in outer_hops:

ch.hops.append((layer_idx, u, v))

if layer_idx < L - 1:

inner_topo = self.layers[layer_idx + 1]

last_snapshot = None

for hop_idx, (u, v) in enumerate(outer_hops):

direction = hop_dir(topo, u, v)

out_side, in_side = port_sides(direction)

out_ports_outer = topo.ports(out_side)

in_ports_inner = inner_topo.ports(in_side)

out_ports_inner = inner_topo.ports(out_side)

K = min(len(out_ports_outer), len(in_ports_inner), len(out_ports_inner) if out_ports_inner else len(in_ports_inner))

if K <= 0:

continue

sel = select_index(K, layer_idx, hop_idx)

out_id = out_ports_outer[sel]

in_id = in_ports_inner[sel]

inner_out_id = out_ports_inner[sel] if out_ports_inner else in_id

inner_cur = cur_start_ids[layer_idx + 1]

if inner_cur != inner_out_id:

inner_steps_to_out = inner_topo.route_intra(inner_cur, inner_out_id)

for ch in chains:

snap_base = list(ch.states_coords[-1]) if last_snapshot is None else list(last_snapshot)

for (uu, vv) in inner_steps_to_out:

ch.hops.append((layer_idx + 1, uu, vv))

if self.layers[-1].kind == TopoKind.SWITCH:

vr2, vc2 = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step = list(snap_base)

snap_step[layer_idx + 1] = (vr2, vc2)

append_state(ch, snap_step)

snap_base = snap_step

else:

ll_topo = self.layers[-1]

ll_dir = hop_dir(ll_topo, uu, vv)

ll_out_side, ll_in_side = port_sides(ll_dir)

ll_out_ports_outer = inner_topo.ports(ll_out_side)

ll_in_ports_inner = ll_topo.ports(ll_in_side)

ll_out_ports_inner = ll_topo.ports(ll_out_side)

ll_K = min(len(ll_out_ports_outer), len(ll_in_ports_inner), len(ll_out_ports_inner) if ll_out_ports_inner else len(ll_in_ports_inner))

if ll_K <= 0:

continue

ll_sel = select_index(ll_K, layer_idx+1, hop_idx)

ll_out_id = ll_out_ports_outer[ll_sel]

ll_in_id = ll_in_ports_inner[ll_sel]

ll_inner_out_id = ll_out_ports_inner[ll_sel] if ll_out_ports_inner else ll_in_id

ll_inner_cur = cur_start_ids[-1]

if ll_inner_cur != ll_inner_out_id:

ll_inner_steps_to_out = ll_topo.route_intra(ll_inner_cur, ll_inner_out_id)

for (uuu, vvv) in ll_inner_steps_to_out:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step2 = list(snap_base)

snap_step2[-1] = (vr3, vc3)

append_state(ch, snap_step2)

snap_base = snap_step2

snap_step3 = list(snap_base)

snap_step3[layer_idx + 1] = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step3[-1] = self.layers[-1].to_rc(ll_in_id) if ll_in_id != -1 else (-1, -1)

append_state(ch, snap_step3)

if ll_in_id != vv:

ll_steps_to_outer = ll_topo.route_intra(ll_in_id, vv)

for (uuu, vvv) in ll_steps_to_outer:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step4 = list(snap_step3)

snap_step4[-1] = (vr3, vc3)

append_state(ch, snap_step4)

snap_base = snap_step4

cur_start_ids[-1] = ll_inner_out_id

last_snapshot = snap_base

cur_start_ids[layer_idx + 1] = inner_out_id

for ch in chains:

ch.hops.append((layer_idx, out_id, out_id))

ch.hops.append((layer_idx + 1, in_id, in_id))

ur, uc = self.layers[layer_idx].to_rc(u) if u != -1 else (-1, -1)

ior, ioc = self.layers[layer_idx + 1].to_rc(inner_out_id) if inner_out_id != -1 else (-1, -1)

prev = list(ch.states_coords[-1]) if last_snapshot is None else list(last_snapshot)

snap_out = list(prev)

snap_out[layer_idx] = (ur, uc)

snap_out[layer_idx + 1] = (ior, ioc)

append_state(ch, snap_out)

last_snapshot = snap_out

vr, vc = self.layers[layer_idx].to_rc(v) if v != -1 else (-1, -1)

inr, inc = self.layers[layer_idx + 1].to_rc(in_id) if in_id != -1 else (-1, -1)

snap_in = list(last_snapshot)

snap_in[layer_idx] = (vr, vc)

snap_in[layer_idx + 1] = (inr, inc)

if self.layers[-1].kind == TopoKind.SWITCH:

append_state(ch, snap_in)

else:

ll_in_ports_inner = self.layers[-1].ports(in_side)

ll_sel = select_index(len(ll_in_ports_inner), -1, hop_idx)

ll_in_id = ll_in_ports_inner[ll_sel]

snap_in[-1] = self.layers[-1].to_rc(ll_in_id)

append_state(ch, snap_in)

cur_start_ids[-1] = ll_in_id

last_snapshot = snap_in

cur_start_ids[layer_idx + 1] = in_id

inner_cur = cur_start_ids[layer_idx + 1]

if hop_idx < len(outer_hops) - 1:

next_u, next_v = outer_hops[hop_idx + 1]

next_dir = hop_dir(topo, next_u, next_v)

next_out_side, _ = port_sides(next_dir)

next_out_ports_inner = inner_topo.ports(next_out_side)

if next_out_ports_inner:

sel_next = select_index(len(next_out_ports_inner), layer_idx, hop_idx + 1)

inner_out_next = next_out_ports_inner[sel_next]

else:

inner_out_next = inner_cur

inner_steps = inner_topo.route_intra(inner_cur, inner_out_next)

for ch in chains:

snap_base = list(last_snapshot)

for (uu, vv) in inner_steps:

ch.hops.append((layer_idx + 1, uu, vv))

if self.layers[-1].kind == TopoKind.SWITCH:

vr2, vc2 = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step = list(snap_base)

snap_step[layer_idx + 1] = (vr2, vc2)

append_state(ch, snap_step)

snap_base = snap_step

else:

ll_topo = self.layers[-1]

ll_dir = hop_dir(ll_topo, uu, vv)

ll_out_side, ll_in_side = port_sides(ll_dir)

ll_out_ports_outer = inner_topo.ports(ll_out_side)

ll_in_ports_inner = ll_topo.ports(ll_in_side)

ll_out_ports_inner = ll_topo.ports(ll_out_side)

ll_K = min(len(ll_out_ports_outer), len(ll_in_ports_inner), len(ll_out_ports_inner) if ll_out_ports_inner else len(ll_in_ports_inner))

if ll_K <= 0:

continue

ll_sel = select_index(ll_K, layer_idx+1, hop_idx)

ll_out_id = ll_out_ports_outer[ll_sel]

ll_in_id = ll_in_ports_inner[ll_sel]

ll_inner_out_id = ll_out_ports_inner[ll_sel] if ll_out_ports_inner else ll_in_id

ll_inner_cur = cur_start_ids[-1]

if ll_inner_cur != ll_inner_out_id:

ll_inner_steps_to_out = ll_topo.route_intra(ll_inner_cur, ll_inner_out_id)

for (uuu, vvv) in ll_inner_steps_to_out:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step2 = list(snap_base)

snap_step2[-1] = (vr3, vc3)

append_state(ch, snap_step2)

snap_base = snap_step2

snap_step3 = list(snap_base)

snap_step3[layer_idx + 1] = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step3[-1] = self.layers[-1].to_rc(ll_in_id) if ll_in_id != -1 else (-1, -1)

append_state(ch, snap_step3)

if ll_in_id != vv:

ll_steps_to_outer = ll_topo.route_intra(ll_in_id, vv)

for (uuu, vvv) in ll_steps_to_outer:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step4 = list(snap_step3)

snap_step4[-1] = (vr3, vc3)

append_state(ch, snap_step4)

snap_base = snap_step4

cur_start_ids[-1] = ll_inner_out_id

cur_start_ids[layer_idx + 1] = inner_out_next

last_snapshot = chains[0].states_coords[-1]

else:

inner_target = inner_topo.to_id(*d_coords[layer_idx + 1])

inner_steps = inner_topo.route_intra(inner_cur, inner_target)

for ch in chains:

snap_base = list(last_snapshot)

for (uu, vv) in inner_steps:

ch.hops.append((layer_idx + 1, uu, vv))

if self.layers[-1].kind == TopoKind.SWITCH:

vr2, vc2 = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step = list(snap_base)

snap_step[layer_idx + 1] = (vr2, vc2)

append_state(ch, snap_step)

snap_base = snap_step

else:

ll_topo = self.layers[-1]

ll_dir = hop_dir(ll_topo, uu, vv)

ll_out_side, ll_in_side = port_sides(ll_dir)

ll_out_ports_outer = inner_topo.ports(ll_out_side)

ll_in_ports_inner = ll_topo.ports(ll_in_side)

ll_out_ports_inner = ll_topo.ports(ll_out_side)

ll_K = min(len(ll_out_ports_outer), len(ll_in_ports_inner), len(ll_out_ports_inner) if ll_out_ports_inner else len(ll_in_ports_inner))

if ll_K <= 0:

continue

ll_sel = select_index(ll_K, layer_idx+1, hop_idx)

ll_out_id = ll_out_ports_outer[ll_sel]

ll_in_id = ll_in_ports_inner[ll_sel]

ll_inner_out_id = ll_out_ports_inner[ll_sel] if ll_out_ports_inner else ll_in_id

ll_inner_cur = cur_start_ids[-1]

if ll_inner_cur != ll_inner_out_id:

ll_inner_steps_to_out = ll_topo.route_intra(ll_inner_cur, ll_inner_out_id)

for (uuu, vvv) in ll_inner_steps_to_out:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step2 = list(snap_base)

snap_step2[-1] = (vr3, vc3)

append_state(ch, snap_step2)

snap_base = snap_step2

snap_step3 = list(snap_base)

snap_step3[layer_idx + 1] = self.layers[layer_idx + 1].to_rc(vv) if vv != -1 else (-1, -1)

snap_step3[-1] = self.layers[-1].to_rc(ll_in_id) if ll_in_id != -1 else (-1, -1)

append_state(ch, snap_step3)

if ll_in_id != vv:

ll_steps_to_outer = ll_topo.route_intra(ll_in_id, vv)

for (uuu, vvv) in ll_steps_to_outer:

ch.hops.append((-1, uuu, vvv))

vr3, vc3 = self.layers[-1].to_rc(vvv) if vvv != -1 else (-1, -1)

snap_step4 = list(snap_step3)

snap_step4[-1] = (vr3, vc3)

append_state(ch, snap_step4)

snap_base = snap_step4

cur_start_ids[-1] = ll_inner_out_id

cur_start_ids[layer_idx + 1] = inner_target

last_snapshot = chains[0].states_coords[-1]

for ch in chains:

if ch.states_coords:

last = ch.states_coords[-1]

target = list(d_coords)

if last[-1] != target[-1]:

if self.layers[-1].kind == TopoKind.SWITCH:

final_snap = list(last)

final_snap[-1] = target[-1]

if final_snap != last:

ch.states_coords.append(final_snap)

else:

self_id = self.layers[-1].to_id(*last[-1])

target_id = self.layers[-1].to_id(*target[-1])

final_steps = self.layers[-1].route_intra(self_id, target_id)

for (uu, vv) in final_steps:

ch.hops.append((L - 1, uu, vv))

vr, vc = self.layers[-1].to_rc(vv) if vv != -1 else (-1, -1)

final_snap = list(ch.states_coords[-1])

final_snap[-1] = (vr, vc)

ch.states_coords.append(final_snap)

max_logical_hops: int

max_hop_latency: float

link_bytes: Dict[Link, int]

max_link_load: Tuple[Link, int]

max_link_time: Tuple[Link, float]