電子設計自動化演算法
擺置演算法(placement algorithm)
擺置演算法在任何連線畫出之前,決定數百萬個標準元件各自該擺在晶片版圖的哪個位置。想像在婚宴上安排座位,讓需要交談的人坐得近——只是這裡每個元件都和數十個元件相連、任兩個元件都不能重疊,而且賓客有數百萬之多。擺錯了,連線會橫跨整顆晶片,延遲與功耗暴增;擺對了,整個設計就會又快、又小、又好繞線。
現代擺置器多採用解析法:把總線長建模成一個平滑的數學函數(二次式,或半周長線長的 log-sum-exp 近似),用數值求解器去最小化它,再加上一股「擴散力」把重疊的元件推開,避免版圖塌成一堆。這個「全域擺置」會得到一個粗略、略為重疊的佈局;後續的「細部擺置」再把每個元件對齊到合法的標準元件列與空隙上。RePlAce、學術界的 ePlace 系列,乃至 Google 以強化學習做的平面規劃器,攻克的都是同一場「線長 vs. 擴散」的拔河。
minimize Σ_nets HPWL(net) s.t. no cell overlap
線長通常用 HPWL(半周長線長)估算——也就是每條連線所有接腳外接矩形周長的一半——因為它計算便宜,而且和實際繞出來的線長吻合得出奇地好。
又称
另见