跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/01 01:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:江峻瑋
研究生(外文):Chun-Wei Chiang
論文名稱:以整數線性規劃法解決全客戶式 超大型積體電路增量式平面規劃
論文名稱(外文):An Integer Linear Programming Approach to Full-Custom VLSI Incremental Floorplanning
指導教授:程仲勝程仲勝引用關係
指導教授(外文):Jong-Sheng Cherng
口試委員:程仲勝林浩仁王欣平
口試委員(外文):Jong-Sheng CherngHow-Rern LinShin-Ping Wang
口試日期:2012-07-16
學位類別:碩士
校院名稱:大葉大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:59
中文關鍵詞:增量式平面規劃數學歸納法
外文關鍵詞:incremental floorplanningmathematical programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:133
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
平面規劃是實體設計最重要的步驟之一,但因電路系統設計日趨複雜,難以直接設計出一個最佳的平面規劃結果,因此很可能需反覆執行平面規劃,以求得一個較佳的結果,但這會增加佈局所需的時間。為了縮短重複進行平面規劃的時間,增量式平面規劃(incremental floorplanning)策略因此被提出用以改進必須耗時地整個重新執行平面規劃之缺點。
本論文以數學規劃法(mathematical programming)解決增量式平面規劃問題,嘗試達到佈局最佳化以保障系統效能為目標。增量式平面規劃問題是一個二維的最佳化問題,在論文研究中,我們將此二維最佳化問題轉換成幾個連續的一維最佳化問題,而每一個一維最佳化問題再以整數線性規劃法(integer linear programming)求解。線性規劃式子中考量一個能達到修改模組大小、保留閒置空間及控制網列連線長度的多目標函式,而此目標函式同時受制於幾個限制式,並在不改變模組間拓撲關係及不增加整體晶片面積之條件下,找出最佳佈局結果。以上整數線性規劃以LINGO軟體求其解。實驗結果顯示所提出的增量式平面規劃系統確實可有效的修改模組維度,並控制網列連線長度。

Floorplanning is one of the most important stages in physical design. It is difficult to obtain an optimal floorplanning result due to the increasing complexity in electronic circuit systems. Therefore, to obtain a better solution, it is possible to repeatedly perform the floorplanning procedure. However, this will take more time for circuit layout. For shortening the whole floorplanning process, incremental floorplanning strategy has hence been proposed for quickly reperforming floorplanning when the floorplan has some small changes.
In this thesis, an incremental floorplanning system based on mathematical programming has been proposed to guide physical design towards an optimal layout solution. The incremental floorplanning problem is a two-dimensional optimization problem which has been transformed into several one-dimensional subproblems in our research. Each subproblem can then be solved by integer linear programming technique. The multi-objective function of the linear programming formulation, which being subject to several constraints, is designed to simultaneously consider changing module size, preserving available whitespace, and controlling interconnection length. The final floorplan is obtained by performing the integer linear programming formulation without the change of topology among modules and without the increase of chip size. The integer linear programming formulation has been solved by LINGO software. Experimental results show that it is effective for the proposed incremental floorplanning system to change module dimensions and control interconnection length.

目錄
封面內頁
簽名頁
摘要 iii
Abstract iv
誌謝 v
目錄 vi
圖目錄 viii
表目錄 x
第一章 緒論 1
1.1 研究背景及動機 1
1.2 研究方法 1
1.3 論文架構 2
第二章 增量式平面規劃相關研究 3
2.1 一般平面規劃 3
2.2 增量式平面規劃 4
2.2.1 基於基因演算法之增量式平面規劃 4
2.2.2 基於模擬退火演算法之增量式平面規劃 4
2.2.3 基於Delaunay Triangulation表示法之增量式平面規劃 5
2.2.4 基於走訪二元樹演算法之增量式平面規劃 6
2.3 線性規劃法 6
第三章 以整數線性規劃法解決全客戶式超大   型積體電路增量式平面規劃 8
3.1 問題描述 8
3.2 目標函數 9
3.3 位移限制 10
3.4 水平/垂直限制 12
3.5 邊界擴展限制 13
3.6 增量面積限制 14
3.7 邊長限制 15
3.8 比例限制 16
第四章 實驗結果 21
4.1 模組增量實驗 21
4.1.1 策略一:先水平移動再垂直移動 23
4.1.2 策略二:先垂直移動再水平移動 25
4.2 模組增減量實驗 29
4.2.1 策略一:先水平移動再垂直移動 30
4.2.2 策略二:先垂直移動再水平移動 32
4.3 考慮網列長度實驗 34
4.3.1策略一:先水平移動再垂直移動 35
4.3.2策略二:先垂直移動再水平移動 39
第五章 結論與未來展望 45
參考文獻 46

參考文獻

[1]R. H. J. M. Otten (1982) “Automatic Floorplan Design” Proceedings of the 19th ACM/IEEE Design Automation Conference, Pages 261-267.
[2]D. F. Wong and C. L. Liu (1986) “A New Algorithm for Floorplan Designs” Proceedings of the 23th ACM/IEEE Design Automation Conference, Pages 101-107.
[3]H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani (1996) “VLSI Module Placement Based on Rectangle-Packing by the Sequence–Pair” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 15, Issue 12, Pages 1518-1524.
[4]S. Nakata, K. Fujuoshi, H. Murata, and Y. Kajitani (1996) “Module Placement Based on BSG-Structure and IC Layout Applications” Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, Pages 484-491.
[5]P. N. Guo, C. K. Cheng, and T. Yoshimura (1999) “An O-tree Representation of Non-Slicing Floorplan and Its Applications” Proceedings of the 36th ACM/IEEE Design Automation Conference, Pages 268-273.
[6]Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu (2000) “B*-Trees: A New Representation for Non-Slicing Floorplans” Proceedings of the 37th ACM/IEEE Design Automation Conference, Pages 458-463.
[7]X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C. K. Cheng, and Jun Gu (2000) “Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan” Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design, Pages 8-12.
[8]J. M. Lin and Y. W. Chang (2001) “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans” Proceeding of the 38th ACM/IEEE Design Automation Conference, Pages 764-769.
[9]Peter G. Sassone and Sung K. Lim (2003) “A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning” Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design, Pages 74-80.
[10]S. Zhou, S. Dong, C. K. Cheng and J. Gu (2001) “ECBL: an extended corner block list with solution space including optimum placement” Proceedings of the 2001 international symposium on Physical design Conference. Pages 150 – 155
[11]Y. Ma, S. Dong, X. Hong, Y. Cai, C. K. Cheng, and J. Gu (2001) “VLSI Floorplanning with Boundary Constraints Based on Corner Block List” Proceedings of Asia and South Pacific Design Automation Conference, Pages 509-514.
[12]Y. Ma, X. Hong, S. Dong, Y. Cai, C. K. Cheng, and J. Gu (2001) “A Compact Algorithm for Placement Design Using Corner Block List Representation” Proceedings of the 4th ASIC Conference, Pages 146-149.
[13]X. Tang and D. F. Wong (2002) “Floorplanning with Alignment and Performance Constraints” Proceedings of the 39th ACM/IEEE Design Automation Conference, Pages 848-853.
[14]H. Xiang, X. Tang, and D. F. Wong (2003) “Bus-Driven Floorplanning” Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design, Pages 66-73.
[15]J. Cong and M. Sarrafzadeh (2000) “Incremental Physical Design” Proceedings of International Symposium on Physical Design.
[16]J. A. Roy , I L. Markov (2007) “ECO-System: Embracing the Change in Placement” Computer-Aided Design of Integrated Circuits and Systems, Pages: 2173-2185.
[17]Y. Liu, H. Yang and R. Luo (2003) “An Incremental Floorplanner Based on Genetic Algorithm” Proceedings of 5th International Conference on ASCI Vol.1, Pages 331-334.
[18]Y. Liu, H. Yang, R. Luo and H. Wang (2003) “A Hierarchical Approach for Incremental Floorplan Based on Genetic Algorithms” Lecture Notes in Computer Science Vol.3612, Pages 219-224.

[19]L. Yang, Y. Ma, X. Hong, S. Dong and Q. Zhou (2005) “An Incremental Algorithm for Non-Slicing Floorplan Based on Corner Block List Representation” Chinese Journal of Semiconductors Vol.26 No.12, Pages 2335-2343.
[20]高一宏、程仲勝,植基於CBL表示法之增量式平面規劃之研究,大葉大學電機工程研究所,2007年。
[21]Qing. Dong, Bo. Yang, Jing. Li, (2009) “Incremental Buffer Insertion and Module Resizing Algorithm Using Geometric Prograμming” Great Lakes Symposium on VLSI, Pages 413-416.
[22]張家銘、程仲勝、陳木松,植基於Corner Stitching表示法之增量式平面規劃之研究,大葉大學電機工程研究所,2009年。
[23]盧志鴻、張家銘、程仲勝,植基於Corner Stitching表示法之增量式平面規劃之研究,第四屆智慧型系統工程應用研討會,2010年。
[24]G. Dantzig. (1984) “Programming in linear structure” USAF, Washington D.C.
[25]J.-G. Kim and Y.-D. Kim (2003) “A Linear Programming-Based Algorithm for Floorplanning in VLSI Design” Computer-Aided Design of Integrated Circuits and Systems Pages 584-592.
[26]梅宗菀、江蕙如,適用於三維積體電路之線性規劃,國立交通大學電子研究所,2011年。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top