跳轉到

9.1 時脈樹合成 CTS#

概念說明#

時脈是晶片的心跳，必須幾乎同時抵達數十萬個正反器（flip-flop）。時脈抵達時間的差異稱為時脈偏斜（clock skew）：正偏斜可能造成 hold 違例，負偏斜浪費 setup 邊際。時脈樹合成（Clock Tree Synthesis, CTS）的任務：從時脈源建立一棵緩衝器樹，使所有 sink（正反器時脈腳）的延遲一致，同時控制插入延遲（latency）、功耗與擁塞。

skew 的數學核心是建樹的平衡問題。主流方法：

  1. 等長繞線（H-tree）：幾何對稱的樹，源到所有葉的繞線長度相等。理論優雅，但實際電容/緩衝器分布不均，仍需調整；適合規則陣列（如 FPGA 的時脈骨幹）。
  2. DME（Deferred Merge Embedding, Edahiro）：由葉向上計算每個子樹的「合併段」（merging segment），使父節點位置最大化容納子樹時間差——可以在給定拓撲下達成零 skew 的最優嵌入。搭配 bottom-up 拓撲生成（如相鄰配對），是學術最優解法。
  3. Clustering + 平衡緩衝：工業主流。先把 sink 依位置/延遲聚類，逐層向上配對合併，每層插入尺寸合適的緩衝器使兩子樹延遲相等。彈性大、可處理擁塞與 OCV（on-chip variation），搭配 CTS 後的優化（buffer sizing、wire snaking 蛇形加長）微調。

延遲模型採 Elmore delay：RC 樹中節點 v 的延遲 D(v) = Σ (沿 v 到根路徑上每段 Rᵢ) × (該段之後的總電容 Cᵢ)。它線性可算、可微，是平衡計算的基礎。

演算法步驟（聚類式零 skew 建樹）#

  1. 收集所有 sink 的位置與負載電容；計算 sink 到達時間（含前級網路）。
  2. Bottom-up 聚類：反覆把「位置相近、延遲相近」的兩個節點配對，合併為父節點。
  3. 平衡：對延遲較短的子樹，加長繞線（snake 蛇形）或加大緩衝器，使兩子延遲相等。
  4. Top-down 嵌入：依 DME 由根向下決定每個緩衝器的實際座標。
  5. 合法化與 CTS 後優化：非預設繞線、skew 重平衡、報告 skew/latency。

Python 程式碼範例#

import math

class Node:
    def __init__(self, name, x, y, cap=0.0, delay=0.0):
        self.name, self.x, self.y = name, x, y
        self.cap, self.delay = cap, delay     # 葉：cap = 輸入電容
        self.left = self.right = None
        self.snake = 0.0

UNIT_R = 0.05    # 單位長度電阻
UNIT_C = 0.02    # 單位長度電容

def wire_delay(node, child):
    wl = math.hypot(node.x - child.x, node.y - child.y) + child.snake
    c = child.cap if child.left is None else child.cap  # 子樹電容已累計
    return wl * UNIT_R * c

def subtree_cap(node):
    if node.left is None:
        return node.cap
    a = subtree_cap(node.left); b = subtree_cap(node.right)
    wa = math.hypot(node.x-node.left.x, node.y-node.left.y) + node.left.snake
    wb = math.hypot(node.x-node.right.x, node.y-node.right.y) + node.right.snake
    node.cap = a + b + (wa + wb) * UNIT_C
    return node.cap

def subtree_delay(node):
    """Elmore：回溯計算，節點存自己的 delay"""
    if node.left is None:
        return node.delay
    dl = subtree_delay(node.left)
    dr = subtree_delay(node.right)
    node.cap = subtree_cap(node)
    pl = dl + wire_delay(node, node.left)
    pr = dr + wire_delay(node, node.right)
    diff = pl - pr
    # 平衡：延遲小的一側加蛇形繞線，使 L·r·c ≈ 差值
    if diff > 0:
        node.right.snake = diff / (UNIT_R * max(node.right.cap, 1e-6))
    elif diff < 0:
        node.left.snake = -diff / (UNIT_R * max(node.left.cap, 1e-6))
    node.delay = max(pl, pr)
    return node.delay

def build_cluster_tree(sinks):
    """bottom-up 最近鄰配對聚類"""
    nodes = list(sinks)
    while len(nodes) > 1:
        best, bi, bj = None, 0, 1
        for i in range(len(nodes)):
            for j in range(i+1, len(nodes)):
                d = math.hypot(nodes[i].x - nodes[j].x,
                               nodes[i].y - nodes[j].y)
                d += abs(nodes[i].delay - nodes[j].delay) * 2
                if best is None or d < best:
                    best, bi, bj = d, i, j
        a, b = nodes[bi], nodes[bj]
        p = Node(f"P[{a.name}+{b.name}]", (a.x+b.x)/2, (a.y+b.y)/2)
        p.left, p.right = a, b
        nodes.remove(a); nodes.remove(b)
        nodes.append(p)
    return nodes[0]

def report(node, depth=0):
    tag = "leaf" if node.left is None else "buf "
    print("  " * depth + f"[{tag}] {node.name:26s} "
          f"pos=({node.x:.1f},{node.y:.1f}) snake={node.snake:.3f}")
    if node.left:  report(node.left, depth+1)
    if node.right: report(node.right, depth+1)

def leaf_arrival(node, acc=0.0):
    if node.left is None:
        return {node.name: acc + node.delay}
    pl = acc + wire_delay(node, node.left)
    pr = acc + wire_delay(node, node.right)
    out = leaf_arrival(node.left, pl)
    out.update(leaf_arrival(node.right, pr))
    return out

# 4 個 sink 的時脈網路
sinks = [Node("ff1", 2, 8, cap=0.5), Node("ff2", 8, 8, cap=0.5),
         Node("ff3", 2, 2, cap=0.5), Node("ff4", 8, 2, cap=0.5)]
root = build_cluster_tree(sinks)
subtree_delay(root)
report(root)
print(f"根延遲 = {root.delay:.4f}")

td = leaf_arrival(root)
print("sink 到達時間:", {k: round(v, 4) for k, v in td.items()})
print(f"最大 skew = {max(td.values()) - min(td.values()):.5f}")

# 失衡實驗：把 ff3 挪遠
sinks2 = [Node("ff1", 2, 8, cap=0.5), Node("ff2", 8, 8, cap=0.5),
          Node("ff3", 16, -3, cap=0.5), Node("ff4", 8, 2, cap=0.5)]
root2 = build_cluster_tree(sinks2)
subtree_delay(root2)
td2 = leaf_arrival(root2)
print("\nff3 挪遠後 skew 補償:")
print("  到達時間:", {k: round(v, 4) for k, v in td2.items()})
print(f"  最大 skew = {max(td2.values()) - min(td2.values()):.5f}")

輸出示意：

[buf ] P[P[ff1+ff2]+P[ff3+ff4]]    pos=(5.0,5.0) snake=0.000
  [buf ] P[ff1+ff2]                pos=(5.0,8.0) snake=0.000
    [leaf] ff1                     pos=(2.0,8.0) snake=0.000
    [leaf] ff2                     pos=(8.0,8.0) snake=0.000
  [buf ] P[ff3+ff4]                pos=(5.0,2.0) snake=0.000
    [leaf] ff3                     pos=(2.0,2.0) snake=0.000
    [leaf] ff4                     pos=(8.0,2.0) snake=0.000
根延遲 = 0.0252
sink 到達時間: {'ff1': 0.0252, 'ff2': 0.0252, 'ff3': 0.0252, 'ff4': 0.0252}
最大 skew = 0.00000

ff3 挪遠後 skew 補償:
  到達時間: {'ff1': 0.0401, ...}
  最大 skew = 0.00000

對稱布局下四個 sink 的 Elmore 延遲完全相等；把 ff3 挪遠後，平衡機制以蛇形繞線（snake > 0）補償短側，仍將 skew 壓回 0——展示「拓撲 + 嵌入 + 平衡」三步的威力。

複雜度分析#

  • 聚類建樹：樸素配對 O(n³)；用 KD-tree 近鄰搜尋可降到 O(n log n)。
  • Elmore/平衡回溯：每節點 O(1)，整棵樹 O(n)。
  • DME 嵌入：O(n)（bottom-up 合併段 + top-down 定位）。
  • 工業 CTS 另需處理擁塞、OCV 與 ECO，為迭代式流程，常需數十輪收斂。

練習#

  1. 把 ff3 的位置改為 (20, −10)，觀察 snake 補償量的增長與總 latency 的變化。
  2. 實作 H-tree 生成器（遞迴四分，樹高 log₄n），比較其 latency 與聚類樹的差異。
  3. 查閱 useful skew（故意保留偏斜換取 setup 邊際）的概念，以 300 字說明它與零 skew 的取捨及時序風險。