張耀文臺灣大學：電子工程學研究所劉宏毅Liu, Hung-YiHung-YiLiu2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57606使用多重供應電壓是一個對耗電功率進行最佳化的有效方法。這篇論文探討一個在高階合成階段所產生的電壓切割問題。我們指出ㄧ個在最近發表的相關文獻上的理論錯誤，並且證明此電壓切割問題的計算難度是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 39en-US多重供應電壓演算法multiple supply voltagealgorithmthesis