臺灣博碩士論文加值系統

使用多重供應電壓是一個對耗電功率進行最佳化的有效方法。這篇論文探討一個在高階合成階段所產生的電壓切割問題。我們指出ㄧ個在最近發表的相關文獻上的理論錯誤，並且證明此電壓切割問題的計算難度是NP-hard。雖然如此，我們提出一個有效的α2 近似演算法來處理此問題 (α是一個最大電壓對最小電壓的常數比例)。相較最近的文獻結果，其需要O(dn2) 的時間複雜度，我們的演算法時間複雜度只需要O(dkn)，其中d、k、n 分別是真正採用的電壓種類、元件庫所提供的電壓種類、與功能元件的數量。值得注意的是在實際應用上，d 跟k 都可以被視為很小的常數。因此我們的演算法在實際上只需要花費線性時間。此外，我們的近似演算法在特殊的子問題可提供最加解；而在一般的NP-hard問題，我們的演算法也不會產生到達α2 這個常數上限的解。而實驗結果也顯示，相較於最近的文獻結果，我們的演算法能達到 36 倍至 255 倍不等的速度提升，同時依然能節省一樣多的耗電功率。

Power optimization is a crucial concern for modern circuit designs, and multiple supply voltages (MSV’s) provide an effective technique for the optimization. This thesis addresses a voltage partitioning problem arising in MSV design during high-level synthesis. We point out a theoretical mistake in a recent publication and prove that the partitioning problem is NP-hard. Despite its NP-hardness, we propose an efficient α2-approximation algorithm for the problem, where α is the constant ratio
of the maximum to the minimum voltages. Compared with the previous work that runs in O(dn2) time, the time complexity of our algorithm is only O(dkn), where d is the number of voltages employed in the final designs (i.e., voltage domains), k is the number of available supply voltages in the technology library, and n is the number of functional units. Note that both d and k can be considered as small constants for practical applications. Experimental results show that our algorithm (with empirical O(n0.87) and O(n0.93) time) can achieve very significant run-time speedups than the recent work (with empirical O(n2.02) and O(n2.08) time), with the same power reductions of about 60% by using dual-Vdd’s and 67% by using triple-Vdd’s.

Acknowledgements i
Abstract (Chinese) ii
Abstract iii
List of Figures vi
List of Tables vii
Chapter 1. Introduction 1
1.1 Multi-Supply-Voltage Design . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Works in High-Level Synthesis . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Works in Physical Design . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Thesis Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 2. Problem Formulation 9
2.1 Voltage Partitioning Problem (VPP) . . . . . . . . . . . . . . . . . . . . 9
2.2 NP-Hardness of VPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Chapter 3. Algorithms 14
3.1 Gu et al.’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Fast Ordered Voltage Partitioning . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Functional-Unit Rearrangement . . . . . . . . . . . . . . . . . . . . 15
3.2.2 Dynamic Programming for Ordered VPP with d = 2 or 3 . . . . . 16
3.2.3 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.4 Algorithm Optimality and Performance Bound . . . . . . . . . . . 25
3.2.5 Algorithm Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.6 Dynamic Programming for Ordered VPP with d 4 . . . . . . . . 30
Chapter 4. Experimental Results 32
Chapter 5. Conclusions and Future Work 37
Bibliography 39

[1] D. Chen, J. Cong, Y. Fan, and J. Xu, “Optimality Study of Resource Binding with Multi-Vdds,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 580–585, 2006.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, McGraw-Hill, 2001.
[3] 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, 2006.
[4] R. P. Dick, D. L. Rhodes, and W. Wolf, “TGFF: Task Graphs for Free,” in Proceedings of International Workshop on Hardware/Software Co-Design, pp. 97–101, 1998
[5] Z. Gu, Private communication.
[6] M. R. Garey and D. S. Johnson, A Guide to the Theory of NP-Completeness, Freeman, 1979.
[7] Z. Gu, Y. Yang, J. Wang, R. P. Dick, and L. Shang, “TAPHS: Thermal-Aware Unified Physical-Level and High-Level Synthesis,” in Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pp. 879–885, 2006.
[8] M. Hamada, Y. Ootaguro, and T. Kuroda, “Utilizing Surplus Timing for Power Reduction,” in Proceedings of IEEE Custom Integrated Circuits Conference, pp. 89–92, 2001.
[9] 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, 2004.
[10] 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 ACM/IEEE Asia South Pacific Design Automation Conference, pp. 582–587, 2006.
[11] 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. 2006.
[12] W.-P. Lee, H.-Y. Liu, and Y.-W. Chang, “An ILP Algorithm for Post-Floorplanning Voltage-Island Generation,” to appear in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2007.
[13] 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, 2002.
[14] W.-K. Mak and J.-W. Chen, “Voltage Island Generation under Performance Requirement for SoC Designs,” in Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pp. 798–803, 2007.
[15] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI Module Placement Based on Rectangle-Packing by The Sequence Pair,” in IEEE Transaction
on Computer-Aided Design, vol. 15, no. 12, pp. 1518–1524, Dec. 1996.
[16] D. Marculescu and S. Garg, “System-Level Process-Driven Variability Analysis for Single and Multiple Voltage-Frequency Island Systems,” in Proceedings of
IEEE/ACM International Conference on Computer-Aided Design, pp. 541–546, 2006.
[17] K. Usami and M. Horowitz, “Clustered Voltage Scaling Technique for Low-Power Design,” in Proceedings of International Symposium on Low Power Electronics and Design, pp. 3–8, 1995.
[18] H. Wu, I.-M. Liu, M. 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, 2005.
[19] H. Wu and M. Wong, “Improving Voltage Assignment by Outlier Detection and Incremental Placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 459–464, 2007.
[20] 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, 2006.
[21] H. Zhou and J. Wang, “ACG—Adjacent Constraint Graph for General Floorplans,” in Proceedings of IEEE International Conference on Computer Design, pp. 572–575, 2004.