跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:李婉萍
研究生(外文):Wan-Ping Lee
論文名稱:從電壓分配到平面規劃之多重電壓晶片設計流程
論文名稱(外文):A Multiple-Supply-Voltage Design Flow from Voltage Assignment to Floorplanning
指導教授:張耀文張耀文引用關係
指導教授(外文):Yao-Wen Chang
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:121
中文關鍵詞:實體設計平面規劃多重電壓省電設計電源網路合成動態規劃整數線性規劃多邊形輪廓搜尋三維晶片
外文關鍵詞:physical designfloorplanningmultiple-supply voltagelow-power designpower-network synthesisdynamic programminginteger-linear programmingcontour searching3D ICs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:133
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著製程進入奈米時代,功率消耗呈現劇烈地成長,因此過度的功率消耗成為晶片設計上之重大挑戰。如果急劇成長的功率消耗現象仍舊不見趨緩,晶片之溫度將會過熱,更進一步,晶片之功能將會失效。為了抑制功率消耗的成長,多重電壓設計﹝multiple-supply voltage design﹞方式因此被提出且被廣泛地應用於動態功率的降低。簡單地說,多重電壓設計是省電與效能之間的取捨;在省電的同時,有可能危害到晶片的效能。因此如何在這之間做取捨,是非常重要的課題。多重電壓設計模式緩和了動態功率的消耗,但,同時,它也帶來許多更嚴苛的晶片設計挑戰,尤其在電壓配置、平面規劃及電源網路合成上。因此,為了處理如此複雜的多重電壓晶片設計,一套完整的設計流程將不可或缺的。

在此篇論文中,我們提出一個多重電壓設計流程﹝由電壓配置、平面規劃至電源網路合成與調整﹞,此流程共包含了三大部分:﹝一﹞電壓配置與多重電壓導向之平面規劃、﹝二﹞平面規劃後之電壓島形成、及﹝三﹞平面規劃後之多重電壓導向電源網路的合成。
在這系統裡,我們首先發展一個以動態規劃﹝dynamic programming﹞為基礎的電壓分配技術。在符合高效能的要求下,此方法能得到最佳或近似最佳解。在電壓分配步驟之後,我們將產生電壓轉換器,針對於那些需要電壓轉換的連線,這些連線通常連接著不同電壓的電路元件。而後,我們執行電源網路導向的平面規劃,來對多重電壓設計之電路進行平面規劃與擺置的動作。

緊接著,我們提出電壓島形成之問題,在此問題裡,我們更深入考慮了電壓轉換器與電源網路規劃之議題。為了解決與處理這問題,我們運用整數線性規劃﹝integer-linear programming﹞技巧來發展數學模式,此模式包含﹝一﹞電壓轉換器考量之連線估計,﹝二﹞電壓島群聚之不等式及﹝三﹞電源網路繞線資源之不等式。

又,我們發現先前電源環合成之缺陷,因而發展出新的模組。先前電源環總是被考慮成封住電壓島的「四方形」,但,我們發現,此種假設缺少了實用性,因此,我們將電源環考慮成封住電壓島之「多邊形」。這新的假設將使得電源環之估計更顯精準,且電源環之合成更顯實際。我們提出一套演算法流程,其中包含﹝一﹞快速電壓島之電源環搜尋演算法,與﹝二﹞快速電源環之修整最佳化演算法,以力求電源環之完整性。
As the CMOS technology enters the nanometer era, power dissipation is increasing severely and becomes a key challenge in nanometer chip design. If the increasing trend of power dissipation is still not tamed, the temperature of chips may be overheated, and further the functionality of the chips may fail. To moderate the increasing power dissipation, the multiple-supply voltage (MSV) design style recently has been extensively applied to mitigate dynamic-power consumption. Concisely, MSV is a trade-off between power saving and performance; in other words, we may sacrifice the performance whiling conserving the energy. Therefore, how to make a good trade-off becomes a key point for MSV design. MSV lowers supply voltages of non-timing-critical cells for power saving while raising ones of timing-critical cells for performance guarantee. Although the MSV design paradigm mitigates dynamic-power consumption, it brings many crucial design challenges at the same time, especially in voltage assignment, floorplanning, and power-ring synthesis. For such complicated designs, it is desirable to develop a methodology dealing with MSV designs.

In this dissertation, we propose an MSV design flow from voltage assignment, through floorplanning, to power-ring synthesis and adjustment. This system consists of three parts: (1) voltage assignment and MSV-aware floorplanning,
(2) post-floorplanning voltage-island generation, and (3) MSV-aware post-floorplanning power ring synthesis.

In this system, we first propose an effective voltage-assignment technique based on dynamic programming for MSV-aware technology mapping. For circuits without re-convergent fanouts, an optimal solution for the voltage assignment is guaranteed; (that is the power consumption is minimized while the timing constraint is satisfied.) for circuits with re-convergent fanouts, a near-optimal solution is obtained.

After the voltage assignment, we then generate a level shifter for each net that connects two blocks in different voltage domains, and perform power-network aware floorplanning for the MSV design. Next, we present a general formulation of the voltage-island generation problem
that considers level-shifter planning and power-network routing resources.
To tackle the addressed problem, we employ an integer-linear programming (ILP) formulation which consists of
(1) level-shifter aware wirelength estimation to capture the timing overhead caused by level shifters, (2) voltage-island-clustering inequalities to avoid complicated constraint transformations, and (3) inequalities to capture the power-network routing-resource usage.

Unlike previous works that form the power rings as enclosing bounding boxes of voltage islands, we enable power rings alignment to the outer boundaries of voltage islands. With this new formulation, the power-ring estimation becomes more accurate during floorplanning,
and the power-ring synthesis becomes more practical after floorplanning. We therefore propose a linear-time voltage-island power-ring search algorithm to identify the power rings of voltage islands and then present a linear-time optimal power-ring corner-patching algorithm to minimize the number of corners in the power rings by using post-floorplanning whitespaces.
Acknowledgements ii
Abstract (Chinese) iv
Abstract vii
List of Tables xiii
List of Figures xiv
Chapter 1. Introduction 1
1.1 Multiple-Supply Voltage Design . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Physical Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Floorplanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 2. Related Work and Preliminaries 9
2.1 Related Works in Multiple-Supply Voltage Design . . . . . . . . . . . . . 9
2.1.1 Works in Voltage Assignment . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Works in Physical Design . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Level Shifters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 B*-tree Floorplanning Representation . . . . . . . . . . . . . . . . 13
Chapter 3. Voltage Assignment and MSV-Aware Floorplanning 16
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Dynamic Programming for Voltage Assignment . . . . . . . . . . . 23
3.3.2 Level Shifter (Soft Block) Insertion . . . . . . . . . . . . . . . . . . 35
3.3.3 Power-Network Aware Floorplanning . . . . . . . . . . . . . . . . . 36
3.4 Optimality of Our Voltage Assignment . . . . . . . . . . . . . . . . . . . 37
3.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.1 Results on the Power-Network Routing-Resource Model . . . . . . 39
3.5.2 Multiple-Supply Voltage Results . . . . . . . . . . . . . . . . . . . 41
3.6 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Chapter 4. Post-Floorplanning Voltage-Island Generation 51
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3.1 Block-Adjacency-Graph Construction . . . . . . . . . . . . . . . . 57
4.3.2 Timing-Constrained Power Optimization . . . . . . . . . . . . . . 60
4.3.3 Level-Shifter Planning . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3.4 Voltage-Island Clustering . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.5 Power-Network Routing Resource Estimation . . . . . . . . . . . . 70
4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Chapter 5. MSV-Aware Post-Floorplanning Power Ring Synthesis 77
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Comparisons of Power-Ring Formulations . . . . . . . . . . . . . . . . . . 80
5.3 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.4.1 Voltage-Island Contour Search Algorithm . . . . . . . . . . . . . . 85
5.4.2 Corner-Patching Algorithm . . . . . . . . . . . . . . . . . . . . . . 95
5.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5.1 Corner Effect Validation . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5.2 Corner Number Minimization by Whitespace Patching . . . . . . . 103
5.6 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Chapter 6. Concluding Remarks and Future Work 107
Bibliography 110
Vita 118
Publication List 120
[1] K. Banerjee, S. J. Souri, P. Kapur, and K. C. Saraswat, “3-D ICs: A Novel
Chip Design for Improving Deep-Submicrometer Interconnect Performance
and Systems-on-Chip Integration,” in Proceedings of the IEEE, vol. 89, pp.
602–633, May 2001.
[2] R. K. Brayton, G. D. Hachtel, and A. L. Sangiovanni-Vincenmtelli, “Multilevel
Logic Synthesis,” in Proceedings of the IEEE, vol. 78, pp. 264–300, February
1990.
[3] Y. Cai, B. Liu, J. Shi, Q. Zhou, and X. Hong, “Power Delivery Aware Floorplanning
for Voltage Island Designs,” in Proceedings of IEEE International
Symposium on Quality Electronic Design , pp. 350–355, San Jose, CA, March
2007.
[4] CFD-ACE+ Module Manual, vol. I, version 2002.
[5] J. Chang and M. Pedram, “Energy Minimization Using Multiple Supply Voltages,”
in Proceedings of ACM/IEEE International Symposium on Low Power
Electronics and Design, pp. 157–162, Monterey, CA, August 1996.
[6] J. Chang and M. Pedram, “Energy Minimization Using Multiple Supply Voltages,”
IEEE Transactions on Very Large Scale Integration Systems, vol. 5, no.
4, pp. 436–443, December 1997.
[7] Y.-C. Chang, Y.-W. Chang, G.-M.Wu, and S.-W.Wu, “B*-trees: A New Representation
for Non-slicing Floorplans,” in Proceedings of ACM/IEEE Design
Automation Conference, pp. 458–463, Los Angeles, CA, June 2000.
[8] K. Chaudhary and M. Pedram, “Computing the Area Versus Delay Trade-
Off Curves in Technology Mapping,” IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, vol. 14, pp. 1480–1489, December
1995.
[9] C. Chen, A. Srivastava, and M. Sarrafzadeh, “On Gate Level Power Optimization
Using Dual-Supply Voltages,” IEEE Transactions on Very Large Scale
Integration Systems, vol. 9, pp. 616–629, October 2001.
[10] T.-C. Chen and Y.-W. Chang, “Modern Floorplanning Based on Fast Simulated
Annealing,” in Proceedings of ACM International Symposium on Physical
Design, pp. 104–112, San Francisco, CA, April 2005.
[11] T.-C. Chen and Y.-W. Chang, “Modern Floorplanning Based on B*-trees and
Fast Simulated Annealing,” IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems, vol. 25, pp. 637–650, April 2006.
[12] R. Ching, E. Young, K. Leung, and C. Chu, “Post-Placement Voltage Island
Generation,” in Proceedings of IEEE/ACM International Conference on
Computer-Aided Design, pp. 641–646, San Jose, CA, November 2006.
[13] J. Cong and Y. Zhang, “Thermal-Driven Multilevel Routing for 3-D ICs,” in
Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference,
pp. 121–126, Shanghai, China, January 2005.
[14] J. Cong and Y. Zhang, “Thermal Via Planning for 3-D IC’s,” in Proceedings
of IEEE/ACM International Conference on Computer Aided Design, pp. 745–
752, San Jose, CA, November 2005.
[15] J. Cong, A. Jagannathan, Y. Ma, G. Reinman, J. Wei, and Y. Zhang, “An
Automated Design Flow for 3D Microarchitecture Evaluation,” in Proceedings
of ACM/IEEE Asia and South Pacific Design Automation Conference, pp.
384–389, Yokohama, Japan, January 2006.
[16] J. Cong and Y. Zhang, “Thermal-Aware Physical Design Flow for 3-D ICs”,
in Proceedings of IEEE International VLSI Multilevel Interconnection Conference,
pp. 73–80, Fremont, CA, September 2006.
[17] J. Cong, G. Luo, J. Wei, and Y. Zhang, “Thermal-Aware 3D IC Placement via
Transformation,” in Proceedings of ACM/IEEE Asia and South Pacific Design
Automation Conference, pp. 780–785, Yokohama, Japan, January 2007.
[18] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to
Algorithms, 2nd Ed., McGraw-Hill, 2001.
[19] S. Das, A. Chandrakasan, and R. Reif, “Three-Dimensional Integrated Circuits:
Performance, Design Methodology, and CAD Tools” in Proceedings of
IEEE Computer Society Annual Symposium on VLSI, pp. 13–18, February
2003.
[20] P. Gupta, A. B. Kahng, and P. Sharma, “A Practical Transistor-level Dual
Threshold Voltage Assignment Methodology,” in Proceedings of IEEE International
Symposium on Quality Electronic Design, pp. 421–426, San Jose, CA,
March 2005.
[21] M. Hamada, Y. Ootaguro, and T. Kuroda, “Utilizing Surplus Timing for
Power Reduction,” in Proceedings of IEEE Conference on Custom Integrated
Circuits, pp. 89–92, San Diego, CA, May 2001.
[22] J. Hu, Y. Shin, N. Dhanwada, and R. Marculescu, “Architecting Voltage
Islands in Core-Based System-on-a-Chip Designs,” in Proceedings of
ACM/IEEE International Symposium on Low Power Electronics and Design,
pp. 180–185, Newport Beach, CA, August 2004.
[23] W.-L. Hung, G.M. Link, Yuan Xie, N. Vijaykrishnan, N. Dhanwada, and
J. Corner, “Temperature-Aware Voltage Islands Architecting in System-on-
Chip Designs,” in Proceedings of IEEE International Conference on Computer
Design, pp. 689–694, San Jose, CA, October 2005.
[24] A. B. Kahng, “Classical Floorplanning Harmful?” in Proceedings of ACM
International Symposium on Physical Design, pp. 207–213, San Diego, CA,
April 2000.
[25] K. Keutzer, “DAGON: Technology Binding and Local Optimization by DAG
Matching,” in Proceedings of IEEE/ACM Design Automation Conference, pp.
341–347, June 1987.
[26] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated
Annealing,” Science, vol. 220, pp. 671–680, May 1983.
[27] S. H. Kulkarni, A. N. Srivastava, and D. Sylvester, “A New Algorithm for
Improved VDD Assignment in Low Power Dual VDD Systems,” in Proceedings
of ACM International Symposium on Lower Power Electronics and Design, pp.
200–205, Newport, CA, August 2004.
[28] S. H. Kulkarni and D. Sylvester, “Power Distribution Techniques for Dual
VDD Circuits,” in Proceedings of IEEE Asia and South Pacific Design Automation
Conference, pp. 838–843, Yokohama, Japan, January 2006.
[29] D. E. Lackey, P. S. Zuchowski, T. R. Bednar, D. W. Stout, S. W. Gould, and J.
M. Cohn, “Managing Power and Performance for System-on-Chip Designs Using
Voltage Islands,” in Proceedings of IEEE/ACM International Conference
on Computer-Aided Design, pp. 195–202, San Jose, CA, November 2002.
[30] W.-P. Lee, H.-Y. Liu, and Y.-W. Chang, “Voltage Island Aware Floorplanning
for Power and Timing Optimization,” in Proceedings of IEEE/ACM International
Conference on Computer-Aided Design, pp. 389–394, San Jose, CA,
November 2006.
[31] W.-P. Lee, H.-Y. Liu, and Y.-W. Chang, “An ILP Algorithm for Post-
Floorplanning Voltage-Island Generation,” in Proceedings of IEEE/ACM International
Conference on Computer-Aided Design, pp. 650–655, San Jose,
CA, November 2007.
[32] Z. Li, X. Hong, Q. Zhou, Y. Cai, J. Bian, H. H. Yang, V. Pitchumani, and
C.-K. Cheng, “Hierarchical 3-D Floorplanning Algorithm for Wirelength Optimization,”
IEEE Transactions on Circuits and Systems, vol. 53, pp. 2637–
2642, December 2006.
[33] B. Liu, Y. Cai, Q. Zhou, and X. Hong, “Power Driven Placement with Layout
Aware Supply Voltage Assignment for Voltage Island Generation in Dual-Vdd
Designs,” in Proceedings of IEEE/ACM Asia South Pacific Design Automation
Conference, pp. 582–587, Yokohama, Japan, January 2006.
[34] lp solve, http://tech.groups.yahoo.com/group/lp solve, 2007.
[35] Q. Ma and E. F. Y. Young, “Voltage Island-Driven Floorplanning,” in Proceedings
of IEEE/ACM International Conference on Computer-Aided Design,
pp. 644–649, San Jose, CA, November 2007.
[36] W.-K. Mak and J.-W. Chen, “Voltage Island Generation under Performance
Requirement for SoC Designs,” in Proceedings of IEEE/ACM Asia South Pacific
Design Automation Conference, pp. 798–803, Yokohama, Japan, January
2007.
[37] S. Nahar and S. Sarni, “Fast Algorithm for Polygon Decomposition,” IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
vol. 7, pp. 473–483, 1988.
[38] Opencores, http://www.opencores.com
[39] R. Puri, L. Stok, J. Cohn, D. Kung, D. Pan, D. Sylvester, A. Srivastava, and S.
Kulkarni, “Pushing ASIC Performance in a Power Envelope,” in Proceedings
of ACM/IEEE Design Automation Conference, pp. 788–793, Anaheim, CA,
June 2003.
[40] S. M. Sait and H. Youssef, “VLSI Physical Design Automation: Theory and
Practice,” McGraw-Hill, 1995.
[41] P. H. Shiu and S. K. Lim, “Multi-Layer for Reliable System-on-Package,” in
Proceedings of IEEE International Symposium on Circuits and Systems, vol.
5, pp. 69–72, May 2004.
[42] S. Sutanthavibul, E. Shragowitz, and J. B. Rosen, “An Analytical Approach
to Floorplan Design and Optimization,” in Proceedings of ACM/IEEE Design
Automation Conference, pp. 187–192, March 1990.
[43] K. H. Tam and L. He, “Power Optimal Dual-Vdd Buffered Tree Considering
Buffer Stations and Blockages,” in Proceedings of ACM/IEEE Design Automation
Conference, pp. 497–502, Anaheim, CA, June 2005.
[44] X. Tang and D.F. Wong, “Floorplanning with Alignment and Performance
Constraints,” in Proceedings of ACM/IEEE Design Automation Conference,
pp. 848–853, New Orleans, LA, June 2002.
[45] K. Usami and M. Horowitz, “Clustered Voltage Scaling Technique for Low-
Power Design,” in Proceedings of ACM International Symposium on Lower
Power Electronics and Design, pp. 3–8, Dana Point, CA, August 1995.
[46] K. Usami, M. Igarashi, F. Minami, M. Ishikawa, M. Ichida, and K. Nogami,
“Automated Low-Power Technique Exploiting Multiple Supply Voltages Applied
to a Media Processor,” IEEE Transactions on Solid-State Circuits, vol.
33, no. 3, pp. 463–472, March 1998.
[47] D. F. Wong and C. L. Liu, “A New Algorithm for Floorplan Design,” in
Proceedings of ACM/IEEE Design Automation Conference, pp. 101–107, Las
Vegas, Nevada, 1986.
[48] H. Wu, I. M. Liu, Martin D. F. Wong, and Y. Wang, “Post-Placement Voltage
Island Generation Under Performance Requirement,” in Proceedings of
IEEE/ACM International Conference on Computer-Aided Design, pp. 309–
316, San Jose, CA, November 2005.
[49] H. Wu, M. Wong, and I.-M. Liu, “Timing-Constrained and Voltage-Island-
Aware Voltage Assignment,” in Proceedings of ACM/IEEE Design Automation
Conference, pp. 429–432, San Francisco, CA, July 2006.
[50] M.-C. Wu and Y.-W. Chang, “Placement with Alignment and Performance
Constraints Using the B*-tree Representation,” in Proceedings of ACM/IEEE
Design Automation Conference, pp. 568–571, San Diego, CA, June 2004.
[51] Y.-J. Yeh and S.-Y. Kuo, “An Optimization-based Multiple-Voltage Scaling
Technique for Low Power CMOS Digital Design,” Journal of Circuits, Systems,
and Computers, Special issue on Low Power IC Design, vol. 11, no. 4, pp. 365–
375, October 2002.
[52] P. Zhou, Y. Ma, Z. Li, R. P. Dick, L. Shang, H. Zhou, X. Hong, and Q.
Zhou, “3D-STAF: Scalable Temperature and Leakage Aware Floorplanning
for Three-Dimensional Integrated Circuits,” in Proceedings of IEEE/ACM International
Conference on Computer Aided Design, pp. 590–597, San Jose,
CA, November 2007.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊