摘要
在本論文中，我們將針對數個平面規劃（floorplanning）最佳化問題進行研究。首先我們將針對直角化形狀(rectilinear shape)之模組在面積最小化問題中如何將模組切割技巧引入數學規劃表述。在我們提出的表述法之下，彈性模組(soft module)之形狀不再受限於必須為矩形。由於在同一模型中可同時描述由水平及垂直線段構成直角化形狀的固定模組與彈性模組，使得我們所提出的表述方式能夠符合系統單晶片設計趨勢的需求。此外，彈性直角化模組亦不再為預先確定之形狀，此類模組的輪廓乃是在全域性考量下依據最佳化問題中的目標函數所決定。 由於積體電路製程的演進，使得連線上的延遲效應變的越來越重要。於實體設計(physical design)階段設法解決時序收斂(timing closure)問題並嘗試使電路能夠滿足在前段設計流程中給定之時序需求為一非常重要之課題。此外，隨著設計複雜度的增加使得模組的數量越來越多。對於設計一個快速且有效的平面規劃器而言是非常迫切需要的。因此，針對彈性模組之以連線為導向的平面規劃問題，我們針對彈性模組提出一個新的多階段階層式平面規劃演算法，該方法中結合了一個連線導向且快速有效的模組置放方法與階層式晶片面積最小化演算法。 隨著設計與製程上的發展，提前進行時鐘訊號的規劃成為必須且重要的課題。最後我們將探討於平面規劃階段考量時鐘樹分佈之規劃問題並提出一個以序列對為基礎結合快速產生零歪斜(zero-skew)時鐘樹工具的兩階段式模擬退火演算法。
並列摘要
In this thesis, we study several floorplan optimization problems. First, we study the area minimization problem by introducing the module partition technique into the mathematical programming formulation for rectilinear shape modules. Under the proposed formulation, soft modules are no longer limited on rectangular shape. Both of hard type and soft type general rectilinear modules can be described in the same model such that our formulation can meet the design trend requirement of System-on-Chip (SOC). Besides, rectilinear soft module is no longer shape-predetermined and the contour is globally decided by the objective function of the optimization problem. Due to the revolution on IC process technology, the delay effect of interconnection becomes more and more critical. To solve the timing closure problem in physical design such that designs can meet the timing constraints is a very important topic. Besides, as the increasing on design complexity, the number of module on a chip becomes more and more. To design a fast and effective floorplanner is necessary and urgent. Thus, for the interconnection driven soft module floorplanning problem, we present a new multistage hierarchical floorplanning algorithm for soft modules. This algorithm is integrated with a fast and effective interconnect-driven module placement and hierarchical chip area minimization method. As the progress of both design and manufacturing technology, the clock planning in earlier design stage becomes a necessary and important topic. Finally, we study the problem of clock tree distribution planning in the floorplanning stage and propose a sequence pair based two-stage simulated annealing algorithm that is integrated with a fast zero-skew clock tree generation engine.