- 學位論文
利用分治法找尋可產生極端漏電流情況的輸入向量
A Divide-and-Conquer Approach to Finding A Vector Leading to Extreme Leakage Current
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
小於100奈米的製程中，漏電流功率已是整體功率管理的惡夢之一。不論是正常還是待機模式，漏電流都會存在。整體功率中漏電流功率的比率將製程進步而變大。我們必須考慮深臨界電壓的漏電流(sub-threshold leakage)和閘極的漏電流(gate leakage current)。 對CMOS電路來說，於待機模式將主要輸入和記憶單元設定為低漏電流狀態是一個可行的方法。在本論文中，我們提出一個基於分治法的可延伸的方法，可在大型CMOS電路中，找尋可產生極端漏電流情況的輸入向量。這方法可以有效地找尋較佳的輸入向量。 首先，我們將建造一有權重的圖(graph)，每一個主要輸入或記憶單元當成一個圖的端點且邊上的權重是依據主要輸入或記憶單元所形成的邏輯錐互相重疊的情況來決定。然後，我們將圖分割成較小的群，而較小的群可利用徹底找尋法來逐群地找尋輸入向量。葛雷碼(Gray code)可以用來縮小因輸入訊號改變所引起的訊號傳播的時間。 在ISCAS的較大的測試電路中，找尋最小漏電流情況時，我們的方法可以只花少許的時間就可以得到比使用100000筆隨機產生的輸入向量所得的結果還好11%的結果。但是針對組合電路(combinatorial circuit) 時，我們的方法並沒有改善。在找尋最大漏電流情況時，我們的方法的結果可以改善78%。 我們也針對最大的三個電路做了一些實驗，這些實驗用於分析我們的方法中分割的動作對結果的影響。從這些結果，我們發現我們的方法對分割的分割群數量和不平衡因子的改變並不敏感。
並列摘要
The leakage power is one of the components in the overall power management nightmare for sub-100nm processes. Leakage power exists both in active and standby modes and the ratio of leakage power to total power will become bigger when process technology is scaled down. We must consider the sub-threshold leakage and the gate leakage current. Forcing primary inputs and memory elements into certain logic values is a viable method to lower standby leakage current for COMS circuits. This thesis presents a scalable approach to finding the extreme leakage state for large CMOS circuits based on the concept of divide-and-conquer. This approach is proved very effective in finding better vectors. First, we build a weighted graph where each primary input or memory element is treated as a vertex and the edge weight is used to represent the overlapping degree of the two logic cones rooted at two primary inputs or memory elements. We then partition the graph into strongly related groups of smaller size that enables effective exhaustive search on a group-by-group basis. Gray code is used to minimize the time spent on propagating the input changes through a circuit. In finding the lowest leakage current state with only a small fraction of time, our approach gains up to 11% of improvement with respect to the results obtained by using 100000 random vectors for large ISCAS benchmark circuits. For combinatorial circuits, there is no improvement. In finding the largest leakage current state, it gains up to 78% of improvement. We perform some experiments for the three large circuits to analyze how partitioning stage would influence the results of our approach. From these experiments, we find that our approach is insensitive to the perturbation incurred by varying the number of parts and the imbalance factor used for graph partitioning.
參考文獻
[FANG03] Ja-Shong Fang, ” A new Algorithm for Finding Lowest-Leakage-Power State,” Master Thesis, Graduate Institute of Computer Science and Engineering, Yuan-Ze University, Taiwan, R.O.C., 2003.
[ABDO02] A. Abdollahi, F. Fallah, and M. Pedram, "Runtime Mechanisms for LeakageCurrent Reduction in CMOS VLSI Circuits," ISLPED, 2002, pp. 213~218.
[ABDO04] Afshin Abdollahi, Farzan Fallah, and Massoud Pedram, "Leakage Current Reduction in CMOS VLSI Circuits by Input Vector Control," IEEE Trans. on Very Large Scale Integration (VLSI) System, Vol. 12, NO. 2, February, 2004, pp. 140~154.
[ANIS03] M. Anis, S. Areibi, M. Elmasry, "Design and Optimization of Multithreshold CMOS (MTCMOS) Circuits," IEEE Transactions on CAD, Volume: 22 Issue: 10 , Oct. 2003, pp. 1324-1342.
[CHEN96] Z. Chen, C. Diaz, J. D. Plummer, M. Cao, and W. Greene, "0.18um Dual Vt MOSFET Process and Energy-Delay Measurement," IEDM, 1996, pp. 851-854.