電子設計自動化演算法

時脈樹建構演算法(clock tree construction algorithm)

時脈訊號必須在幾乎同一瞬間抵達數百萬個正反器中的每一個;時脈樹建構演算法決定該如何佈線與插入緩衝器來分配它,好讓所有葉端同時到達。想像用一個水龍頭灌溉一片廣大果園,卻要求每棵樹在同一毫秒被澆到——你得平衡管線長度並加裝幫浦(緩衝器),讓沒有哪一條分支落後。任何到達時間的落差都是時脈偏斜,會直接侵蝕你的時序預算,並可能造成保持或建立失效。

經典的幾何演算法是 DME(延遲合併嵌入),用以建構零偏斜樹:遞迴地把接收端兩兩配對,為每一對計算一段「合併線段」——從其上任一點都能以相等延遲到達兩個子節點——並把確切位置延後到整棵樹的拓樸已知後,再由上而下嵌入。剛性對稱的 H 樹是教科書理想,卻浪費導線;真實工具會建構偏斜平衡樹,並日益採用多源時脈網(mesh),再利用「有用偏斜」——刻意延遲某些時脈以放鬆緊繃的路徑。更深層的回報是在最小緩衝器功耗下達成低偏斜,畢竟時脈網路可能消耗整顆晶片相當大比例的功率。

延遲合併嵌入建構零偏斜時脈樹

與直覺相反,完美的零偏斜並非現代時脈合成的目標——受控的「有用偏斜」(讓下游階段拿到稍晚一點的時脈)能換來平衡樹無法提供的時序餘裕。

又称
zero-skew treeH-treeDME時脈樹演算法