在時序限制下的平面規劃

Abstract

在本篇論文中，我們針對平面規劃設計提出了一個新的拓蹼產生方法。這個方法是在連接關係圖上的每個連線，給予水平或垂直關係的標示而得到『連線標示圖』。於是，所有可能的平面規劃都可以經由這個連線標示圖而產生。 另外我們也提出了一個有效率的連線標示圖評估方法來衡量所相對應平面規劃的面積和時序好壞。因為對於一個固定的連接關係圖形，所有可能的平面規劃拓蹼數量是與此圖形的連線數成指數關係的，結合平面規劃的拓蹼產生和效能評估可以在拓蹼產生的過程中刪除許多非最佳的解，從而增進整個執行速度。這整個平面規劃產生系統將會產生一個滿足給訂的時序限制下最小面積的平面規劃。

In this thesis, we propose a new topology generation algorithm for floorplan designs. The algorithm is based on a graph model named edge labeling graph by labeling horizontal or vertical relationship on edges in the adjacency graph. All valid floorplan topologies will be constructed by performing this algorithm. Efficient cost evaluation approaches on area and timing based on the edge labeling graphs are also proposed. Because the number of topologies is exponential to the number of vertices in the adjacency graph. Integration of topology generation and cost evaluation eliminates sub-optimal solutions thus speeds up the execution time for large circuit in particular. Our floorplan generation system can thus generate optimal size floorplan subjected to timing constraints efficiently.