跳到主要內容

臺灣博碩士論文加值系統

(44.210.151.5) 您好!臺灣時間:2024/07/13 11:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:鄭世揚
研究生(外文):Shih-Yang Cheng
論文名稱:低功率多電壓分割與排程之方法
論文名稱(外文):Multiple voltages scheduling and partitioning scheme for low power design
指導教授:顧孟愷
指導教授(外文):Mong-Kai Ku
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:54
中文關鍵詞:低功率多電壓排程
外文關鍵詞:multiple voltagesschdulinglow power
相關次數:
  • 被引用被引用:0
  • 點閱點閱:218
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在行動產品愈趨多元的今日,低必v的設計需求日益重要,不但可減少熱能發散,並延長產品的使用時間。高階低功率技術具有較大的彈性及效果。本章介紹功率消耗可分為動態必v消耗、短路必v消耗及漏電必v消耗,引進多電壓源技術及其必v消耗模式,並介紹高階合成各步驟及在電路設計中各階層低必v設計技術。

控制資料流程圖(CDFG)是在高階合成中常用的一種圖形,用來表示資料的流動及運算。在第二章介紹其定義、格式及其表示法。並利用工具分析硬體描述語言(VHDL),產生控制資料流程圖。之後我們會介紹物件導向圖形函式庫。此論文方法利用圖形函式庫來做為之後程式排程、配置及繫結。

第三章對控制資料流程圖做基本排程,包含最早(ASAP)及最晚(ALAP)排程。同時也介紹分割方法及模擬退火法。根據這此資訊,結合區塊分割方法,我們利用模擬退火法提出新的方法,在取代運算時考慮線路上的必v消耗,從模擬退火法的四大要件來說明及其細部方法。在經過排程後的控制資料流程圖會決定每個運算的運算時間,變數的生存時間被決定。藉由建立衝突圖(Conflict Graph),可得到每個排程後的控制資料流程圖所需的暫存器和多工器。

最後,我們利用8筆測試資料來檢驗此方法的效果,並比較不同分割數及時間限制,數據顯示此方法約可節省20%~40%的必v消耗。
A multiple scheduling method is one of the useful techniques for low power high level synthesis which replaces functional units with lower supply voltage. The thesis presents a scheduling scheme combining with partitioning that minimizes power consumption. This scheme takes power consumption of interconnection into account to keep balance between functional units and interconnection. The timing constrained scheduling method is achieved by performing simulated annealing which is an iterative and non-deterministic algorithm that allows uphill moves to escape from local optima. The proposed algorithm consists of two phases, the initial partition and modification process. In the first phase, the initial solution is decided according to list-based scheduling algorithm. In the next stage, two types of modification are introduced during the process of the simulated annealing. One modification is replacement which moves operation from one partition to another. The other is exchange which exchanges operations in different partitions. A power reduction of 20~40% is shown with strict timing constraint.
Contents
1 Introduction .................................................................................................... 1
1.1 The trend of low power.......................................................................... 1
1.2 High Level synthesis ............................................................................. 1
1.3 Multiple voltages ................................................................................... 4
1.4 Low power design at various levels of abstraction ............................ 6
1.5 The goal of the thesis ............................................................................ 8
2 CDFG parser, generator and representation ............................................... 10
2.1 CDFG representation ........................................................................... 10
2.2 CDFG format ........................................................................................ 11
2.3 CDFG toolkit ......................................................................................... 13
2.3.1 Parser ............................................................................................ 13
2.3.2 Generator ..................................................................................... 13
3 Scheduling and partitioning scheme for low power .................................... 15
3.1 Basic scheduling and partitioning algorithm ..................................... 15
3.1.1 ASAP scheduling ......................................................................... 16
3.1.2 ALAP Scheduling ........................................................................ 18
3.2 Multiple voltages scheduling with slack time ..................................... 21
3.3 Partitioning ............................................................................................ 22
3.4 Simulated annealing ............................................................................. 23
3.5 Min-cost algorithm based on simulation annealing ........................... 24
3.5.1 Solution space ............................................................................... 25
3.5.2 Neighborhood structure .............................................................. 27
3.5.3 Cost function ................................................................................ 28
3.5.4 Annealing schedule ...................................................................... 32
3.5.5 Initial solution – list based scheduling ....................................... 33
4
4 Allocation and binding .................................................................................. 37
4.1 Conflict graph construction ................................................................. 38
4.2 Heuristic algorithms ............................................................................. 40
5 Experimental results ...................................................................................... 44
5.1 Experimental environment .................................................................. 44
5.2 Experimental results ............................................................................. 45
6 Conclusion ....................................................................................................... 49
Reference ................................................................................................................ 50
Appendix ................................................................................................................ 53
[1] Gajski, D.D., Ramachandran, L., “Introduction to high-level synthesis,” Design & Test of Computers, IEEE, Volume 11, Issue 4 , Winter 1994, Pages:44 – 54.

[2] D. Gajski, N. Dutt, A. Wu, S. Lin, “High-Level Synthesis: Introduction to Chip and System,” Design. Kluwer Academic Publishing, 1992.

[3] M. Kamble, K. Ghose, “Analytical energy dissipation model for low-power caches,” ACM/IEEE International Symposium on Low Power Design, April 1995, Pages:63-68

[4] P. Chandrakasan, S. Cheng, R. W. Brodersen, “Low Power CMOS Digital Design,” IEEE J. Solid-State Circuits. vol.27, Apr. 1992, Pages:473-483.

[5] M.C. Johnson and K. Roy, “Datapath Scheduling with Multiple Supply Voltages and Level Converters,” ACM Trans. Design Automation Electronic Systems, vol.2, July 1997, Pages:227-248.

[6] Usami, K.; Nogami, K.; Igarashi, M.; Minami, F.; Kawasaki, Y.; Ishikawa, T.; Kanazawa, M.; Aoki, T.; Takano, M.; Mizuno, C.; Ichida, M.; Sonoda, S.; Takahashi, M.; Hatanaka, N., “Automated low-power technique exploiting multiple supply voltages applied to a media processor,” Custom Integrated Circuits Conference, Proceedings of the IEEE, 5-8 May 1997, Pages:131 - 134

[7] Choi, J.-Y.; Lin, C.-H.; Kim, H.-S., ”A low power register scheduling and allocation algorithm for multiple voltage,” Electrical and Electronic Technology, 2001. TENCON. Proceedings of IEEE Region 10 International Conference on, Volume 2, 19-22 Aug. 2001, Pages:627 - 630

[8] Manzak, A.; Chakrabarti, C., “A low power scheduling scheme with resources operating at multiple voltages,” Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, Volume: 10, Issue 1, Feb. 2002 Pages:6 - 14

[9] R. Mehra, L. M. Guerra, and J. M. Rabaey, “Low Power Architectural Synthesis and the Impact of Exploiting Locality,“ J. VLSI. Signal Processing, vol.13, 1996, Pages:239-258.

[10] CDFG toolkit: http://poppy.snu.ac.kr/CDFG/cdfg.html

[11] Krishna, V.; Ranganathan, N.; Vijaykrishnan, N., “Energy efficient datapath synthesis using dynamic frequency clocking and multiple voltages,” VLSI Design, 1999. Proceedings. Twelfth International Conference On , 7-10 Jan. 1999
Pages:440 - 445

[12] S. Katkoori and R. Vemura., “Scheduling for low power under Resource and Lantency Constraints”, ISCAS, 2000, Pages:53-56.

[13] W.T.Shiue and C. Chakrabarti., “ILP-based Scheme for Low Power Scheduling and Resource Binding,” ISCAS,2000, Pages:279-282.

[14] Y.Lin, C.Hwang and A.Wu, “Scheduling Techniques for Variable Voltage Low Power Designs,” ACM Transactions on Design Automation of Electronic Systems, April 1997, Pages:81-97.

[15] Kernighan and Lin, “An efficient heuristic procedure for partitioning graphs,” The Bell System Technical Journal, Feb. 1970, vol. 49, no. 2

[16] Kirkpatrick, S., Gerlatt, C. D. Jr., and Vecchi, M.P., “Optimization by Simulated Annealing,”, Science 220, 1983, Pages:671-680.

[17] Peeter Ellervee, ”High-Level Synthesis of Control and Memory Intensive Applications”

[18] Peeter Ellervee, Shashi Kumar1, Ahmed Hemani, “Allocation and Binding in High Level Synthesis”

[19] G. De Micheli, “Synthesis and Optimization of Digital Circuits,” McGraw-Hill, Inc., 1994.

[20] Chien-Cheng Yu, Wei-Ping Wang and Bin-Da Liu, “A New Level Converter for Low-Power Applications”, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top