8.3 全局繞線與詳細繞線#

import heapq
from collections import defaultdict

class GlobalRouter:
    """GCell 網格上的縮略全局繞線（PathFinder 風格）"""
    def __init__(self, R, C, capacity=2):
        self.R, self.C, self.cap = R, C, capacity
        self.usage = defaultdict(int)     # 邊 -> 使用量
        self.hist = defaultdict(float)    # 邊 -> 歷史成本

    def edge(self, a, b):
        return (a, b) if a < b else (b, a)

    def edge_cost(self, a, b, present):
        e = self.edge(a, b)
        cong = max(0, self.usage[e] + present - self.cap)
        base = 1.0
        return base + 3.0 * cong + self.hist[e]

    def route_net(self, pins):
        """多腳 net：以簡易 Steiner（依序連到已繞部分）+ A*"""
        def astar(src, dst_set, present):
            openq = [(0, src, None)]
            g = {src: 0}
            parent = {}
            while openq:
                f, n, p = heapq.heappop(openq)
                if n in dst_set:
                    # 回溯
                    path, cur = [], n
                    while cur:
                        path.append(cur); cur = parent.get(cur)
                    return path[::-1]
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    m = (n[0]+dr, n[1]+dc)
                    if 0 <= m[0] < self.R and 0 <= m[1] < self.C:
                        ng = g[n] + self.edge_cost(n, m, present)
                        if m not in g or ng < g[m]:
                            g[m] = ng; parent[m] = n
                            h = min(abs(m[0]-d[0]) + abs(m[1]-d[1])
                                    for d in dst_set)
                            heapq.heappush(openq, (ng + h, m, n))
            return None

        connected = {pins[0]}
        paths = []
        for p in pins[1:]:
            path = astar(p, connected, present=False)
            # 記錄使用
            for a, b in zip(path, path[1:]):
                self.usage[self.edge(a, b)] += 1
            paths.append(path)
            connected |= set(path)
        return paths

    def overflow(self):
        return sum(max(0, u - self.cap) for u in self.usage.values())

    def iterate(self, nets, max_iter=6):
        """rip-up & reroute：溢位邊加 history，重繞全部"""
        all_routes = {}
        for i, (name, pins) in enumerate(nets):
            all_routes[name] = self.route_net(pins)
        print(f"初始溢位 = {self.overflow()}")
        for it in range(max_iter):
            if self.overflow() == 0:
                break
            # 溢位邊加歷史成本
            for e, u in self.usage.items():
                if u > self.cap:
                    self.hist[e] += 1.5
            # 清空使用量，全部重繞（含 history 懲罰）
            self.usage.clear()
            for name, pins in nets:
                all_routes[name] = self.route_net(pins)
            print(f"  第 {it+1} 輪後溢位 = {self.overflow()}")
        return all_routes

# 場景：8x8 GCell，多條 net 擠中央通道
nets = [("n1", [(0,0), (0,7)]),
        ("n2", [(1,0), (1,7)]),
        ("n3", [(7,0), (7,7)]),
        ("n4", [(0,3), (7,3)]),
        ("n5", [(3,0), (3,7)]),
        ("n6", [(2,2), (5,5)])]
gr = GlobalRouter(8, 8, capacity=2)
routes = gr.iterate(nets)
print("最終溢位 =", gr.overflow())
for name, paths in routes.items():
    total_len = sum(len(p)-1 for p in paths)
    print(f"  {name}: {len(paths)} 段, 總長 {total_len}")

初始溢位 = 4
  第 1 輪後溢位 = 2
  第 2 輪後溢位 = 0
最終溢位 = 0
  n1: 1 段, 總長 7
  n2: 1 段, 總長 7
  ...
  n4: 1 段, 總長 10