臺灣博碩士論文加值系統

隨著可攜式設備的功能日趨繁複，系統效能的需求漸趨提高，使用多核心處理器架構的可攜式裝置亦日漸增加。由於可攜式設備多以電池供電，在電池容量受限的狀況下，多核心系統的能源管理機制將成為影響設備操作時間的主要因素。目前主要的嵌入式系統電源管理如Linux電源管理、Android週邊管理等機制，多以自動管理週邊與處理器工作頻率，無法因應使用者的期待與需求，配合實際工作負載，節省系統能源，且無法動態開啟或關閉處理器核心，以符合實際使用需求。有鑑於此，本研究提出新式BPM-DFS(Bounded-Power Multi-core Dynamic Frequency Scaling)電源管理機制。此機制整合了一精確的系統組態選擇演算法、工作重新排程機制、與耗能預估模型，針對多核心的電腦系統，依使用者指定之電源預算(Power Budget)，藉由核心開啟與否、核心工作頻率調整、與工作的重新配置，在不高於電源預算下，儘可能提高工作速度。本研究並將BPM-DFS電源管理機制實現於四核心x86 Android系統，並與其他低耗能排程機制如SCA-ICA、Linux/Android內建管理機制，比較實際執行時的功耗差異，並探討調整功耗造成之效能變化。實驗結果指出，BPM-DFS與Linux Performance模式相比，可節省25%總功耗，與SCA-ICA相比可節省至21%總功耗，若Linux/Android最低耗能的的Linux Powersave模式相比，BPM-DFS可節省至約2%總功耗。

As the growing functionality of modern hand-held devices, the requirement of system performance is increased. The multicore processors are widely adopted in the hand-held systems accordingly. Since the hand-held systems are powered by battery, the battery life will become the dominated limitation of these high-performance multicore hand-held devices. Therefore an efficient power management mechanism for hand-held multicore system is become important today. Conventional power management systems of embedded systems, such as Linux power CPU power manager, Android peripheral manager, adopt an automatic scheme to control the usage of peripheral operations and processor frequency. It can not consider the requirement of user, actually task loading, and power-on/shutdown processors in the multicore system, to meet the actual operating situation. Therefore, this paper propose a novel power management mechanism, called Bounded-Power Multi-core Dynamic Frequency Scaling (BPM-DFS), which integrates a system configuration selection algorithm, a task re-scheduling mechanism, and a predictive power model. According to the assigned power budget by the user, BPM-DFS can dynamically adjust the configuration of the multicore system to control the suitable alive core number, working frequency, and task reassignment, to achieve good performance and under the limitation of power consumption. The proposed BPM-DFS has been implemented on quad-core x86 Android system to compare the actual capabilities of other power management schemes, such as SCA-ICA, Linux/Android build-in power managers. The experimental results reveal that BPM-DFS can save 25 % power consumption than Linux performance mode; save 21% power consumption than SCA-ICA. It also can save 2% power consumption than the most low-power Linux operation mode, Linux powersave mode.

目錄
摘要 I
Abstract II
謝誌 III
目錄 IV
圖目錄 V
表格目錄 VII
第一章 介紹 1
第二章 背景說明與相關研究 3
2.1 Android系統簡介 3
2.2 簡介Android系統內部架構 4
2.3 Dalvik虛擬機器與Core Library介紹 7
2.4 相關研究 8
2.5 Bounded-Power Multicore DFS Scheduling Mechanism 10
第三章 BPMDFS演算法 13
3.1 符號定義 13
3.2 函式定義 14
3.3 Predictive Power Model 14
3.4 演算法說明 15
第四章 範例分析 19
第五章 實驗結果 24
5.1 實驗環境 24
5.2 Profiling experiments for Predictive Power Model 24
5.3 各機制排程結果之實驗 30
5.4 實驗總結 47
第六章 結論 49
參考文獻 50

圖目錄
圖一：十種採用Android系統之智慧型手機 3
圖二：Android系統架構圖 4
圖三：應用程式、Android Framework、OpenGL、Skia、Surface關係圖 (Android圖形系統Client端) 6
圖四：Bounded-Power Multicore DFS Scheduling Mechanism功能示意圖 12
圖五：BPM-DFS演算法 17
圖六：CoreTaskMapping演算法 18
圖七：一個Task序列 19
圖八：Task序列於初期各個機制之Bin Packing結果與數據 20
圖九：Task序列於系統即將進入高負載時各個機制之Bin Packing結果與數據 21
圖十：Task序列於系統進入高負載後各個機制之Bin Packing結果與數據 23
圖十一：頻率與功耗成正比關係圖 25
圖十二：負載與功耗成正比關係圖 26
圖十三：核心數與ω值之關係圖 28
圖十四：理論負載轉實際負載之圖表 30
圖十五、BPM-DFS 8種Power Budget、SCA-ICA與Linux之耗能實驗結果 31
圖十六：164.gzip於Linux Powersave模式與BPM-DFS Budget 71之功耗歷程 32
圖十七：164.gzip於Linux Powersave模式與BPM-DFS Budget 71之完整功耗與執行時間比較 32
圖十八：176.gcc於Linux Powersave模式與BPM-DFS Budget 71之功耗歷程 33
圖十九：176.gcc於Linux Powersave模式與BPM-DFS Budget 71之完整功耗與執行時間比較 33
圖二十：176.gcc於Linux Powersave模式與BPM-DFS Budget 71之功耗歷程 34
圖二十一：181.mcf於Linux Powersave模式與BPM-DFS Budget 71之完整功耗與執行時間比較 34
圖二十二：300.twolf於Linux Powersave模式與BPM-DFS Budget 71之功耗歷程 35
圖二十三：300.twolf於Linux Powersave模式與BPM-DFS Budget 71功耗 35
圖二十四：SpecJvm98 raytrace於Linux Powersave模式與BPM-DFS Budget 71之功耗歷程 36
圖二十五：SpecJvm98 raytrace於Linux Powersave模式與BPM-DFS Budget 71之完整功耗與執行時間比較 36
圖二十六：164.gzip於SCA-ICA與BPM-DFS Budget 78之功耗歷程 37
圖二十七：164.gzip於SCA-ICA與BPM-DFS Budget 78之完整功耗與執行時間比較 37
圖二十八：176.gcc於SCA-ICA與BPM-DFS Budget 78之功耗歷程 38
圖二十九：176.gcc於SCA-ICA與BPM-DFS Budget 78之完整功耗與執行時間比較 38
圖三十：181.mcf於SCA-ICA與BPM-DFS Budget 78之功耗歷程 39
圖三十一：181.mcf於SCA-ICA與BPM-DFS Budget 78之完整功耗與執行時間比較 39
圖三十二：300.twolf於SCA-ICA與BPM-DFS Budget 78之功耗歷程 40
圖三十三：300.twolf於SCA-ICA與BPM-DFS Budget 78之完整功耗與執行時間比較 40
圖三十四：SpecJvm98 raytrace於SCA-ICA與BPM-DFS Budget 78之功耗歷程 41
圖三十五：SpecJvm98 raytrace於SCA-ICA與BPM-DFS Budget 78之完整功耗與執行時間比較 41
圖三十六：164.gzip於Linux Performance模式與BPM-DFS Budget 91之功耗歷程 42
圖三十七：164.gzip於Linux Performance模式與BPM-DFS Budget 91之完整功耗與執行時間比較 42
圖三十八：176.gcc於Linux Performance模式與BPM-DFS Budget 91之功耗歷程 43
圖三十九：176.gcc於Linux Performance模式與BPM-DFS Budget 91之完整功耗與執行時間 43
圖四十：181.mcf於Linux Performance模式與BPM-DFS Budget 91之功耗歷程 44
圖四十一：181.mcf於Linux Performance模式與BPM-DFS Budget 91之完整功耗與執行時間比較 44
圖四十二：300.twolf於Linux Performance模式與BPM-DFS Budget 91之功耗歷程 45
圖四十三：300.twolf於Linux Performance模式與BPM-DFS Budget 91之完整功耗與執行時間比較 45
圖四十四：SpecJvm98 raytrace於Linux Performance模式與BPM-DFS Budget 91之功耗歷程 46
圖四十五：SpecJvm98 raytrace於Linux Performance模式與BPM-DFS Budget 91之完整功耗與執行時間比較 46
圖四十六、對於SpecJvm98 Raytrace耗能與效能實驗綜合比較 47
圖四十七、Linux Powersave模式為比較基礎之功耗減少比例 48
圖四十八、Linux Performance模式為比較基礎之功耗減少比例 48


表格目錄
表一：BPM-DSF符號定義 13
表二：各個核心開啟數量於負載為0時之功耗 25
表三：各核心開啟數量於負載為100並使用最大工作頻率時之功耗 28
表四：各個核心開啟數量於各負載時之ω值與ω平均值 28

[1]C. Xian and Y.-H. Lu, “Dynamic voltage scaling for multitasking realtime systems with uncertain execution time,” in ACM Great Lakes Symp. VLSI (GLSVLSI), 2006, pp. 392–397.
[2]E. Talpes and D. Marculescu, “Toward a multiple clock/voltage island design style for power-aware processors,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 13, no. 5, pp. 591–603, 2005.
[3]G. Magklis, G. Semeraro, D. H. Albonesi, S. G. Dropsho, S. Dwarkadas, and M. L. Scott, “Dynamic frequency and voltage scaling for a multipleclock-domain microprocessor,” IEEE Micro, vol. 23, no. 6, pp. 62–68, 2003.
[4]Advanced Configuration and Power Interface,[Available Online]:http://www.acpi.info/
[5]Goglin, B., LaBRI, INRIA, Talence, France, Furmento, N., “Enabling high-performance memory migration for multithreaded applications on LINUX” , Parallel &; Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, May 2009, pp. 23-29.
[6]Patrick Brady, “2008 Google I/O Anatomy &; Physiology of an Android”, [Available Online]: http://sites.google.com/site/io/anatomy--physiology-of-an-android.
[7]Haisang Wu, Binoy Ravindran, E. Douglas Jenseny, and Peng Li, “CPU Scheduling for Statistically-Assured Real-Time Performance and Improved Energy Efficiency” , CODES+ISSS’04, September 8–10, 2004, Stockholm, Sweden.
[8]J. R. Lorch and A. J. Smith, “Improving dynamic voltage scaling algorithms with PACE,” in SIGMETRICS/Performance, 2001, pp. 50–61.
[9]Wan Yeon Lee, “Energy-saving DVFS Scheduling of Multiple Periodic Real-time Tasks on Multi-core Processors” , DS-RT '09 Proceedings of the 2009 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications, pp. 216–223.
[10]W. Horn. “Some simple scheduling algorithms.” , Naval Research Logistics Quarterly, 21:177–185, 1974.
[11]P. Pillai and K. G. Shin., “Real-time dynamic voltage scaling for low-power embedded operating systems.” , In ACM SOSP, pages 89–102, 2001.
[12]Don Domingo, “Power Management Guide”, Linux Whitepapers [Available Online]:https://www.linux.com/learn/whitepapers/
[13]IBM Developer Works, “Pwer Management” , [Available Online] : http://www.ibm.com/developerworks/cn/linux/l-power
[14]Patrick Mochel, “Linux Kernel Power Management” , Proceedings of the Linux Symposium, July 23th–26th, 2003, pp. 326-339.
[15]Arch Linux, “CPU Frequency Scaling” , [Available Online] : https://wiki.archlinux.org/index.php/CPU_Frequency_Scaling
[16]J. E. G. Coffman, M. R. Garey, and D. S. Johnson, “Approximation algorithms for NP-hard problems.” ,Boston, MA, USA: D. Hochbaum, PWS Publishing Co., 1996, ch. 2. Approximation algorithms for bin packing: a survey, pp. 46–93.
[17]T. Martin. Balancing Batteries, “Power and Performance: System Issues in CPU Speed-Setting for Mobile Computing.” PhD thesis ,Carnegie Mellon ,University, August 1999.
[18]J. Wang, B. Ravindran, and T. Martin., ”A power aware best-effort real-time task scheduling algorithm” , In IEEE WSTFES/ISORC Workshop, pages 21–28, May 2003.
[19]SPEC, "SPEC CPU2000”, http://www.spec.org/cpu2000/.
[20]SPEC, "SPEC JVM98”, http://www.spec.org/jvm98/.