臺灣博碩士論文加值系統

在計算平台的最新發展趨勢從同質多核心架構轉移到異構和非對稱多核心架構。因此，新的非對稱多核心平台變成一個重要的議題。然而，大多數現有的排程器著重在如何區分合適的工作負載到那些節能的小核心和性能的大核心上。但是並沒有考慮在非對稱多核心上，以合適的核心頻率下分配工作。
在這篇論文中，在非對稱多核心下，我們提出一個對保證工作產量的省電排程器。我們的排程器不僅能決定每個核心的頻率和指派工作來達成減少電量消耗，而且能保證每個工作的產量。從實作結果中，與常見的完全公平排程器相比，我們提出的排程器省下了29 % 的電量。

A recent trend in computing platforms is moving from homogeneous multicore architectures toward heterogeneous and asymmetric multi-core. Therefore, the design of new schedulers for asymmetric multi-core platform has become an important issue. However, most of the existing schedulers focus on how to distinguish workloads suitable for performance “big” cores from those for power-efficient “little” cores, without considering how to distribute tasks to asymmetric cores running at adjustable frequency.
In this paper, we propose an energy-efficient scheduler for throughput guaranteed tasks running on asymmetric multi-core platforms. The proposed scheduler not only determines the frequency of cores and task assignment in order to reduce energy consumption, but also schedules the tasks so that the throughput of all tasks are guaranteed. The implement results indicate that the proposed scheduler consumes 29% less energy than the conventional Compeletely Fair Scheduler with DVFS enabled.

口試委員會審定書 i
Acknowledgement ii
Chinese Abstract iii
Abstract iv
Contents v
List of Figures vii
List of Tables viii
1 Introduction 1
2 Related Work 4
3 Background 7
3.1 CPU Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Power Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.1 System Sleep Model . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.2 Runtime Power Management Model . . . . . . . . . . . . . . . . 10
4 Energy-credit Based Scheduler 12
4.1 Task Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Frequency Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Time Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Task Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Implementation 20
5.1 Throughput Guaranteed Task Scheduling Class . . . . . . . . . . . . . . 20
5.2 Execution Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2.1 Periodic Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2.2 Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2.3 Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Experiment 25
6.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.2.1 Light-weight Workload . . . . . . . . . . . . . . . . . . . . . . . 27
6.2.2 Median-weight Workload . . . . . . . . . . . . . . . . . . . . . 29
6.2.3 Heavy-weight Workload . . . . . . . . . . . . . . . . . . . . . . 31
6.2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Conclusion 33
Bibliography 34

A. Das A. K. Singh and A. Kumar. Energy optimization by exploiting execution slacks in streaming applications on multiprocessor systems. Design Automation Conference, 2013.

Akash Kumar Anup Das and Bharadwaj Veeravalli. Reliability and energy-aware mapping and scheduling of multimedia applications on multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 2016.

ARM. Streamline performance analyzer, ds-5 development studio. https://developer.arm.com/products/software-developmenttools/ds-5-development-studio/streamline/overview.

Robert D. Blumofe and Dionisios Papadopoulos. The performance of work stealing in multiprogrammed environments (extended abstract. In In Proceedings of the 1998 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Poster Session, pages 266–267. ACM Press, 1998.

P. Bogdan, S. Garg, and U.Y. Ogras. Energy-efficient computing from systems-onchip to micro-server and data centers. In Green Computing Conference and Sustainable Computing Conference (IGSC), 2015 Sixth International, pages 1–6, Dec 2015.

Quan Chen and Minyi Guo. Adaptive workload-aware task scheduling for singleisa asymmetric multicore architectures. ACM Trans. Archit. Code Optim., 11(1): 8:1–8:25, February 2014.

FFmpeg. https://ffmpeg.org/.

Andrei Frumusanu. The samsung exynos 7420 deep dive - inside a modern 14nm soc, 2015.

Peter Greenhalgh. Big. little processing with arm cortex-a15 & cortex-a7. ARM White Paper, 2011.

Vishal Gupta, Min Lee, and Karsten Schwan. Heterovisor: Exploiting resource heterogeneity to enhance the elasticity of cloud platforms. In Proceedings of the 11th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE ’15, pages 79–92, New York, NY, USA, 2015. ACM.

JUAN HAMERS and LIEVEN EECKHOUT. Exploiting media stream similarity for energy-efficient decoding and resource prediction. ACM Transactions on Embedded Computing Systems, 2012.

Brian Jeff. big.little technology moves towards fully heterogeneous global task scheduling. November 2013.

David Atienza Karim Kanoun, Nicholas Mastronarde and Mihaela van der Schaar. Online energy-efficient task-graph scheduling for multicore platforms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014.

Myungsun Kim, Soonhyun Noh, Sungju Huh, and Seongsoo Hong. Fair-share scheduling for performance-asymmetric multicore architecture via scaled virtual runtime. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2015 IEEE 21st International Conference on, pages 60–69, Aug 2015.

Youngjin Kwon, Changdae Kim, Seungryoul Maeng, and Jaehyuk Huh. Virtualizing performance asymmetric multi-core systems. In Proceedings of the 38th Annual International Symposium on Computer Architecture, ISCA ’11, pages 45–56, New York, NY, USA, 2011. ACM.

VLC media player. http://www.videolan.org/vlc/.

Chandandeep Singh Pabla. Completely fair scheduler. Linux J., 2009(184), August 2009.

Padmanabhan Pillai and Kang G Shin. Real-time dynamic voltage scaling for lowpower embedded operating systems. In ACM SIGOPS Operating Systems Review, volume 35, pages 89–102. ACM, 2001.

Nicolas Pitre. Linux support for arm big.little. http://lwn.net/Articles/481055/, 2012.

Chin-Chiang Pan Po-Hsien Tseng, Pi-Cheng Hsiu and Tei-Wei Kuo. User-centric energy-efficient scheduling on multi-core mobile devices. Design Automation Conference, 2014.

Rafael Rodríguez-Sánchez and Enrique S Quintana-Ortí. Architecture-aware optimization of an hevc decoder on asymmetric multicore processors. arXiv preprint arXiv:1601.05313, 2016.

Elsayed Saad, Medhat Awadalla, Mohamed Shalan, and Abdullah Elewi. Energyaware task partitioning on heterogeneous multiprocessor platforms. arXiv preprint arXiv:1206.0396, 2012.

Wonik Seo, Daegil Im, Jeongim Choi, and Jaehyuk Huh. Big or little: A study of mobile interactive applications on an asymmetric multi-core platform. In Workload Characterization (IISWC), 2015 IEEE International Symposium on, pages 1–11, Oct 2015.

William Thies, Michal Karczmarek, and Saman Amarasinghe. Compiler Construction, chapter StreamIt: A Language for Streaming Applications, pages 179–196. Springer Berlin Heidelberg, Berlin, Heidelberg, 2002.

Frances Yao, Alan Demers, and Scott Shenker. A scheduling model for reduced cpu energy. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 374–382. IEEE, 1995.

Yuan-Hao Chang Yu-Ming Chang, Pi-Cheng Hsiu and Che-Wei Chang. A resourcedriven dvfs scheme for smart handheld devices. ACM Transactions on Embedded Computing Systems, 2013.