請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30290
標題: | 使用多重供應電壓進行耗電功率最佳化的演算法 A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages |
作者: | Hung-Yi Liu 劉宏毅 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 多重供應電壓,演算法, multiple supply voltage,algorithm, |
出版年 : | 2007 |
學位: | 碩士 |
摘要: | 使用多重供應電壓是一個對耗電功率進行最佳化的有效方法。這篇論文探討一個在高階合成階段所產生的電壓切割問題。我們指出ㄧ個在最近發表的相關文獻上的理論錯誤,並且證明此電壓切割問題的計算難度是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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30290 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 315.1 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。