# 臺灣博碩士論文加值系統

(98.82.140.17) 您好！臺灣時間：2024/09/10 13:47

:::

### 詳目顯示

:

• 被引用:0
• 點閱:132
• 評分:
• 下載:0
• 書目收藏:0
 使用多重供應電壓是一個對耗電功率進行最佳化的有效方法。這篇論文探討一個在高階合成階段所產生的電壓切割問題。我們指出ㄧ個在最近發表的相關文獻上的理論錯誤，並且證明此電壓切割問題的計算難度是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 ratioof 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 iAbstract (Chinese) iiAbstract iiiList of Figures viList of Tables viiChapter 1. Introduction 11.1 Multi-Supply-Voltage Design . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 Works in High-Level Synthesis . . . . . . . . . . . . . . . . . . . . 41.2.2 Works in Physical Design . . . . . . . . . . . . . . . . . . . . . . . 51.3 Thesis Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Chapter 2. Problem Formulation 92.1 Voltage Partitioning Problem (VPP) . . . . . . . . . . . . . . . . . . . . 92.2 NP-Hardness of VPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Chapter 3. Algorithms 143.1 Gu et al.’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Fast Ordered Voltage Partitioning . . . . . . . . . . . . . . . . . . . . . . 153.2.1 Functional-Unit Rearrangement . . . . . . . . . . . . . . . . . . . . 153.2.2 Dynamic Programming for Ordered VPP with d = 2 or 3 . . . . . 163.2.3 An Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . 203.2.4 Algorithm Optimality and Performance Bound . . . . . . . . . . . 253.2.5 Algorithm Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 293.2.6 Dynamic Programming for Ordered VPP with d 4 . . . . . . . . 30Chapter 4. Experimental Results 32Chapter 5. Conclusions and Future Work 37Bibliography 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 Transactionon 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 ofIEEE/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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 以齧齒類缺血性腦中風模式進行腦部血管相關基因之研究 2 矩形大面積質子交換膜燃料電池膜電極組製程開發研究 3 順序學習式RBF類神經網絡應用於自評自調運動控制之設計法 4 具薄型閘極介電層之矽基金氧半電容元件之特性研究暨溫度感測應用 5 達到分集與多工最佳取捨的時空編碼之峰均值減低方法 6 多輸入多輸出廣播通道下回饋策略之影響 7 無線透膚電能轉換系統 8 以自組特徵映射網路推估蒸發量 9 感知無線電中基於馬可夫模型之分散式優先使用者保護架構 10 在移動網路上之互助式多路傳輸機制 11 β1,4-N-acetylgalactosaminyltransferase-III在大腸癌細胞中扮演的角色 12 探討公司多角化與資訊不對稱問題：以庫藏股宣告事件為例 13 《韓非子》賞罰思想之研究 14 智慧型手機平台競合策略與發展藍圖 15 中國大陸改革開放後憲法修改之研究(1988-2004)

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室