以拓撲結構相似性驅動之線長極小化佈局演算法

Abstract

積體電路的佈局(floorplan)是電子實體電路設計過程的第一步。它決定電路模組(module)在晶片上擺放的位置，進而影響了晶片面積以及線長。晶片面積反映在晶片的製造成本上，而線長影響效能。因此佈局在實體設計中有其重要性。 自動佈局的演算法多以退火演算法為基礎。這類方法是塞填驅動的(packing-driven)。塞填驅動雖對面積是有利的，但對線長可能是有害的。另一方面，解析方法裡，以二次規劃(quadratic programming)為基礎的演算法，是線長驅動(wirelength-driven)的。在佈局裡，模組空間不重疊是重要的法則。塞填驅動有效的避開了不合法的佈局。然而以二次規劃為基礎的演算法卻不行。且塞填驅動能夠產生擁有較小面積的佈局。但二次規劃能從全局的視野最佳化線長是傳統以退火為基礎的演算法所不及。因此我們定義了拓撲相似性(topology similarity)並提出以相似性驅動(similarity-driven)之兩階段佈局演算法。其第一階段是以二次規劃為基礎的，並以尋找對線長友善的模組間拓撲關係為目標。而第二階段是以退火演算法為基礎，並以第一階段的結果做為其在進行相似性感知(similarity-aware)搜尋時的參考對像。我們藉此控制退火演算法在解析解附近的解空間尋找最佳解。實驗結果顯示，我們的演算法在線長上的收斂更快，同時能得到更短的線長且在面積上沒有顯著的增加。

Floorplanning is in the early stages of VLSI physical design. It determines the locations of modules and significantly governs the chip dimensions and the total wirelength on the chip. Thus it is important in terms of both fabrication cost and chip performance. Floorplanning based on simulated annealing (SA) is popular. But this approach is packing-driven and may be profitless for the wirelength. On the other hand, the analytical approach by quadratic programming is wirelength-driven. Packing-driven approach has much success in the handling of the non-overlapping constraint and results floorplans with smaller area. But unlike the quadratic programming approach, traditional SA-based methods lack a global view of the interconnections. To eliminate this drawback, we define topology similarity and propose similarity-driven approach. In our approach, SA is guided by an analytical result. Similarity-aware perturbations are proposed to make searches more efficient. Compared to traditional packing-driven approach, experiments show the proposed algorithm produces solutions of shorter wirelength without apparent degradation in area.