使用高斯梯度與定點技巧的佈局演算法

Abstract

頂尖的全域佈局演算法採用不同的邏輯閘擴散演算法來處理邏輯閘密度。在這項研究裡，我們發現頂尖的全域佈局演算法對於大型障礙物周圍以及穿越大型障礙物處理擺放行為的不同。透過我們的研究結果，佈局演算法在大型障礙物周圍的擺放行為對於可繞線性有顯著的影響，而這項觀察無法由傳統的評價指標去做分析。在解二次方程的佈局演算法中，SimPL 和 Kraftwerk2 所採用的方法代表了兩種不同的邏輯閘擴散演算法類別。我們重新實作兩種演算法類別並實際運用在邏輯閘擺放實驗，我們解釋了這兩種邏輯閘擺放演算法對於在全域與局部兩種規模的控制性有著明顯的不同。我們進一步觀察這兩種演算法對於可繞線性的影響。 為了同時處理全域與局部兩種規模的擺放行為，我們提出了一個兩階段的全域佈局演算法。第一階段的目的是藉由移動邏輯閘跨過大型障礙物以取得精準的可用空間分布。第二階段的目的是藉由邏輯閘在大型障礙物周圍的移動以取得邏輯閘之間正確的相對關係。我們提出的全域佈局演與 ComPLx 有著相同品質的實驗結果表現，而且基於在大型障礙物周圍的擺放行為使得可繞線性的程度提高了。

State of the art global placers adopt different cell spreading algorithms to handle density of placement. In this work, we found there exist different placement behavior when placing cells across and around fixed macros among state of the art global placers. Our findings also suggest that placement behavior around fixed macros has significant impact toward routability of the design that cannot be observed through conventional evaluation metrics. For quadratic placers, the methodologies adopted in SimPL and Kraftwerk2 represent two distinct class of cell spreading algorithms. Based on our implementations of the two frameworks, we answer to the question on whether if there exist different level of controllability in terms of global view and local view among different cell spreading algorithms. We further investigate the impact of placement behavior on routability of the design. To address both global view and local view of the placement, we propose a two stage global placement framework. The first stage aims to assign large portion of cells with precise amount of white space by moving cells across fixed macros. The second stage aims to determine accurate relative order of cells and move cells around fixed macros. Our proposed placement framework achieves equivalent placement quality compared to ComPLx with placement behavior around fixed macros that is inherently desirable to routability.