- 學位論文
具邊界限制模組之定形配置設計
Slicing Floorplan Design with Boundary-Constrained Modules
摘要
在本篇論文中，我們討論具邊界限制模組之定形配置設計(slicing floorplan design)。我們設計一個時間複雜度為平方項的方法，此方法可以正確地將一定形配置設計轉換成另一符合所有邊界限制之定形配置設計。這個轉換的方法被整合到模擬退火(simulated annealing process)的方法中，以試著求得一個最佳的解。不像其他已存在的演算法，例如在[10]被提出的演算法，我們所提出的定形配置演算法可以永遠產生出符合邊界限制的解，相對於在[10]所提出的演算法，這是我們的演算法最主要的優點。 我們的演算法已以C語言實現，並利用兩個MCNC的電路: ami33及ami49，做實驗。當只考慮面積的最佳化時，我們的演算法針對ami33及ami49可改進在[10]所提出的演算法達9.38%及2.97%。同時針對ami33及ami49，繞線長度也被我們的演算法改進達6.9%及15.64%。當同時考慮面積與繞線長度的最佳化時，針對ami33及ami49，我們的演算法可改進面積達4.88%及4.48%，可改進繞線長度達8.53%及10.87%。在運算時間方面，我們的演算法幾乎在所有的測試例子中都只花不到一分鐘。
並列摘要
We consider in this thesis the problem of slicing floorplan design with boundary-constrained modules. We develop a quadratic-time method that correctly transform a slicing floorplan into one that satisfies all given boundary constraints. This transformation method is then incorporated into a simulated annealing process to seek for a best possible solution. Unlike any other existing algorithm such as the one in [10], our floorplanning algorithm is always able to generate solutions satisfying all given boundary constraints, which is the major advantage of our algorithm over the algorithm in [10]. Our algorithm has been implemented in C language, and tested on two MCNC examples: ami33, ami49. When optimizing the area alone, our algorithm improved the average area up to 9.38% and 2.97% for ami33 and ami49, respectively, over the algorithm in [10]. Meanwhile the average interconnect wirelength was also improved by our algorithm up to 6.9% and 15.64% for ami33 and for ami49, respectively. When optimizing both area and interconnect wirelength, our algorithm was able to improve the average area up to 4.88% for ami33, 4.48% for ami49, and to improve the average wirelength up to 8.53% for ami33, 10.87% for ami49. As for the run time, our algorithm took less than one minute for almost all test cases.
參考文獻
延伸閱讀
- 張益彰（1997）。有多個非線性元件控制系統之極限環分析〔碩士論文，元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611365715
- 林逸偉（2014）。基於方塊導向模式與虛擬參考回饋調諧之非線性系統控制器設計方法〔碩士論文，國立臺北科技大學〕。華藝線上圖書館。https://doi.org/10.6841/NTUT.2014.00484
- Chang, Y. K. (1995). 針對含多變化構造結構的多種型態約束限制之最佳化設計. 中國航空太空學會學刊, 27(4), 373-380. https://doi.org/10.6124/TAASRC.199512_27(4).10
- Li, C. R. (2010). Fixed-Outline 3-D IC Floorplanning with TSV Co-placement [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2010.00448
- 林志遠（2005）。Floorplanning with consideration of Buffer Resource Allocation〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200500316