運用增廣拉格朗日方法的多階層式混合尺寸置放器

Abstract

由於矽智財的普遍使用以及越來越多的不同元件整合成系統單晶片，混合尺寸的電路元件置放成為實體電路設計中關鍵的一環。然而在處理置放問題時，對於大電路單元和標準電路元，兩者演算法在本質上差異甚大，因此要在一套流程中一起完成混合尺寸的置放是十分具有挑戰性的問題。在這篇論文中，我們將原本的置放問題轉化為一套新的最佳化模型，並以數學解析的方法配合多階層式架構求解。由實驗結果可知此套模型確實可用於實作全域式置放器，以應用增廣拉格朗日方法做為非線性最佳化求解的核心，能夠對整體電路繞線長度得到良好的成果。

Due to the trends of IP re-use and the SOC integration, mixed-size designs are very common now, and the quality of mixed-size placement becomes a critical step in the VLSI physical design. However, because the algorithms of macro placement and standard-cell placement are fundamentally distinct, placing the mixed-size design in a single flow is actually a challenging problem. In this thesis, we formulate the general placement problem as a nonlinear constrained optimization problem and solve it by the analytical approach incorporating with a multi-level scheme. The experimental results clearly show that our model can be employed as a global placer. By applying the augmented Lagrangian method to perform nonlinear programming, the result of the total half-perimeter wire length is comparable to current state-of-the-art placers.