(3.236.231.61) 您好!臺灣時間:2021/05/11 21:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李秉光
研究生(外文):Ping-Kuang Lee
論文名稱:一個解決標準晶元模組擺置合理化問題之動態規劃演算法
論文名稱(外文):A Dynamic Programming Algorithm for Legalization in Standard Cell Placement
指導教授:陳木松陳木松引用關係程仲勝程仲勝引用關係
指導教授(外文):Mu-Song ChenJong-Sheng Cherng
學位類別:碩士
校院名稱:大葉大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:65
中文關鍵詞:擺置實體設計
外文關鍵詞:placementphysical design
相關次數:
  • 被引用被引用:0
  • 點閱點閱:157
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著半導體製造技術的日益精進,VLSI電路元件越來越龐大,因此對積體電路前端及後端設計而言,其設計流程亦日趨複雜。以具有標準晶元設計為考量之後端實體設計(physical design)而言,擺置(placement)是一個相當重要的設計階段。其可細分為三大階段,分別為全域擺置(global Placement)、合理化(legalization)和細部擺置(detailed placement),擺置結果嚴重影響整個後端設計之良窳。
全域擺置是以減少網列(netlist)連線長度及擁擠度等為目標,產生初始電路擺置圖,合理化階段為解決晶元合理擺置問題,以符合電路設計原則,而細部擺置的目的在於微調合理化的電路,使電路效能更加提升。在本論文中,我們提出一個演算法來解決擺置合理化問題,演算法中包含晶元列切割、晶元指派到晶元列內以及利用動態規劃解決各晶元列內晶元位置合理化三大步驟。合理化問題目標為讓晶元總位移量越少越好。
實驗結果顯示所提演算法確實能解決合理化問題,且平均而言在執行時間與結果品質兩方面皆能有不錯之成效。
With the increasing technology of semiconductor, the number of VLSI devices is getting more larger. Hence, the design flows become more complexity for the IC front-end and back-end designs. For the row-based physical design, placement is a very importing step. In general, placement can be divided into three stages including global placement, legalization and detailed placement. The resultant solution of placement is crucial to the subsequent stages of physical design.
The global placement generates an initial solution with the objectives of minimizing wirelength and congestion. The subsequent legalization stage is used to solve the legalization problem of cell placement. And then, the purpose of detailed placement is to promote the circuit performance by improving the previous solution. In this thesis, an effective algorithm, including row partition step, cell assignment step and dynamic programming based cell position adjustment step, is proposed to solve the legalization problem. The problem objective is to derive a legalization solution with total displacement as few as possible.
The experimental result shows that the proposed algorithm has good performance on runtime and solution quality on average.
封面內頁
簽名頁
授權..........................iii
中文摘要........................iv
英文摘要 ........................v
誌謝..........................vi
目錄..........................vii
圖目錄.........................ix
表目錄.........................xii

第一章 緒論.......................1
1.1 研究背景與動機..................1
1.2 研究方法.....................1
1.3 論文架構.....................2
第二章 文獻探討.....................3
2.1標準晶元合理化..................3
2.1.1階層式標準晶元合理化.............4
2.1.2平面式(flat)式標準晶元合理化..........9
2.2混合模式合理化..................14
第三章 動態規劃法解決合理化問題............16
3.1 問題描述 ....................17
3.2以動態規劃進行合理化演算法............20
3.2.1切割晶元列.................21
3.2.2晶元指派..................27
3.2.3晶元指派順序................28
3.2.4晶元位移擾動................28
3.2.5晶元重疊面積及晶元重疊個數.........30
3.2.6以區域切割輔助指派.............31
3.2.7固定順序之動態規劃.............33
3.2.8插入虛擬晶元巨集..............39
第四章 實驗結果 ....................41
第五章 結論與未來展望 .................59
參考文獻........................63
[1]Tony F. Chan, Jason Cong, Tianming Kong and Joseph R. Shinnerl(2000) "Multilevel optimization for large-scale circuit placement" IEEE/ACM International Conference on Computer Aided Design, pages 171 - 176.
[2]Jens Vygen (1997) "Algorithms for large-scale flat placement" Design Automation Conference, pages 746 - 751
[3]Ulrich Brenner, Anna Pauli and Jens Vygen (2004) "Almost optimum placement legalization by minimum cost flow and dynamic programming" International Symposium on Physical Design, pages 2 - 9.
[4]Ulrich Brenner and Jens Vygen (2004) "Legalizing a placement with minimum total movement" IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pages 1597 - 1613.
[5]Sung-Woo Hur and John Lillis (2000) "Mongrel: hybrid techniques for standard cell placement" IEEE/ACM International Conference on Computer Aided Design, pages 165 - 170.
[6]Giancarlo Beraudo and John Lillis (2003) "Timing optimization of FPGA placements by logic replication" Design Automation Conference, pages 196 - 201.
[7]Ameya Agnihotri, Mehmet Can YlLDlZ, Ateen Khatkhate, Ajita Mathur, Satoshi Ono, and Patrick H. Madden (2003) "Fractional cut: improved recursive bisection placement" IEEE/ACM International Conference on Computer Aided Design, pages 307 - 310.
[8]Andrew B. Kahng, Igor L. Markov and Sherief Reda (2004) "On legalization of row-based placements" ACM Great Lakes Symposium on VLSI, pages 214 - 219.
[9]Tao Luo, Haoxing Ren, Charles J. Alpert, and David Z. Pan (2005) "Computational geometry based placement migration" IEEE/ACM International Conference on Computer Aided Design, pages 41 - 47.
[10]Majid Sarrafzadeh and Maogang Wang (1997) "NRG: global and detailed placement" IEEE/ACM International Conference on Computer Aided Design,1997, pages 532 - 537.
[11]Dwight Hill (2002) "Method and system for high speed detailed placement of cells within an integrated circuit design" United States Patent 6370673.
[12]Haoxing Ren, avid Z. Pan, Charles J. Alpert and Paul Villarrubia (2005) "Diffusion-based placement migration" Design Automation Conference, pages 515 - 520.
[13]林彥劭,標準元件合法化擺置之最小位移研究,碩士論文,逢甲大學資訊工程系,2009。
[14]卓政達,一個解決標準晶元模組擺置合理化問題之建構式演算法,碩士論文,大葉大學電機工程學系,2009。
[15]Ateen Khatkhate, Chen Li, Ameya R. Agnihotri, Mehmet C. Yildiz, Satoshi Ono, Cheng-Kok Koh and Patrick H. Madden (2004) "Recursive bisection based mixed block placement" International Symposium on Physical Design, pages 84 - 89.
[16]Andrew B. Kahng and Qinke Wang (2004) "Implementation and extensibility of an analytic placer" International Symposium on Physical Design, pages 18 - 25.
[17]Andrew B. Kahng, Igor L. Markov and Sherief Reda (2004) "On legalization of row-based placements" ACM Great Lakes Symposium on VLSI, pages 214 - 219.
[18]Bo Yao, Hongyu Chen, Chung-Kuan Cheng, Nan-Chi Chou, Lung-Tien Liu and Peter Suaris (2005) "Unified quadratic programming approach for mixed mode placement" International Symposium on Physical Design, pages 193 - 199.
[19]Jarrod A. Roy and Igor L. Markov (2007) "ECO-System: Embracing the Change in Placement" Asia and South Pacific Design Automation Conference, pages 147 - 152.
[20]http://cad_contest.ee.ntu.edu.tw/cad08/
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔