Scheduling Policies for Heterogeneous, Approximate Computing Systems

ABSTRACT

Energy consumption is a primary concern for modern computer systems. Conservative approaches, such as DVFS, which have been used in the past to optimize the performance / power tradeoff have reached their limits. Heterogeneity is a promising approach: devices with different characteristics, each performance- and energy-efficient for specific computational patterns are combined in the same system. Approximate computing is another more disruptive solution: many applications can tolerate controlled quality loss in exchange to significant improvement of performance and energy footprint. In this paper we introduce three scheduling policies that exploit heterogeneity, one of them combining it with approximate computing. These policies can selectively optimize performance, energy consumption, or the tradeoff between energy consumption and quality of results. They monitor the execution of tasks at runtime in order to identify the appropriate mapping of tasks to devices, as well as to control the degree of approximation. Our experimental evaluation indicates that all three policies closely match the effectiveness of the optimal configuration, selected by an "oracle".

References

1. Woongki Baek and Trishul M. Chilimbi. 2010. Green: A Framework for Supporting Energy-conscious Programming Using Controlled Approximation. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '10). ACM, New York, NY, USA, 198--209.
2. David Bucciarelli. 2010. Smallpt for OpenCL. (2010). http://davibu.interfree.it/opencl/smallptgpu/smallptGPU.html
3. Wu-chun Feng and Kirk W Cameron. 2007. The green500 list: Encouraging sustainable supercomputing. Computer 40, 12 (2007), 50--55.
4. Xizhou Feng, Kirk W. Cameron, and Duncan A. Buell. 2006. PBPI: A High Performance Implementation of Bayesian Phylogenetic Inference. In Proceedings of the 2006 ACM/IEEE Conference on Supercomputing (SC '06). ACM, New York, NY, USA, Article 75, 10 pages.
5. David J Frank, Robert H Dennard, Edward Nowak, Paul M Solomon, Yuan Taur, and Hon-Sum Philip Wong. 2001. Device scaling limits of Si MOSFETs and their application dependencies. Proc. IEEE 89, 3 (2001), 259--288.
6. Intel. 2010. Intel 64 and IA-32 Architectures Software Developer Manual. (2010). Chapter 14.9.1.
7. Kristján Jónasson. 2012. Applied Parallel and Scientific Computing: 10th International Conference, PARA 2010, Reykjavík, Iceland, June 6-9, 2010, Revised Selected Papers. Vol. 7134. Springer Science & Business Media, ReykjavÃŋk, Iceland.
8. James T. Kajiya. 1986. The rendering equation. In Computer Graphics. ACM, New York, NY, USA, 143--150.
9. Panos Koutsovasilis, Christos Kalogirou, Christos Konstantas, Manolis Maroudas, Michalis Spyrou, and Christos D Antonopoulos. 2017. AcHEe: Evaluating Approximate Computing and Heterogeneity for Energy Efficiency. Parallel Comput. (2017).
10. Xue Li. 2011. Power Management for GPU-CPU Heterogeneous Systems. Master's thesis. University of Tennessee. http://trace.tennessee.edu/utk_gradthes/1079
11. Hans Meuer, Erich Strohmaier, Jack Dongarra, and Horst Simon. 2012. Top 500 list. (2012).
12. NVIDIA. 2015. NVML API Reference. (2015). http://docs.nvidia.com/deploy/nvmlapi/index.html.
13. Abbas Rahimi, Andrea Marongiu, Rajesh K. Gupta, and Luca Benini. 2013. A Variability-aware OpenMP Environment for Efficient Execution of Accuracy-configurable Computation on shared-FPU Processor Clusters. In Proceedings of the Ninth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS '13). IEEE Press, Piscataway, NJ, USA, Article 35, 10 pages. http://dl.acm.org/citation.cfm?id=2555692.2555727
14. Michael Ringenburg, Adrian Sampson, Isaac Ackerman, and Luis Ceze Dan Grossman. 2015. Monitoring and Debugging the Quality of Results in Approximate Programs. In Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2015). ACM, Istanbul, Turkey, 13.
15. Mehrzad Samadi, Janghaeng Lee, D. Anoushe Jamshidi, Amir Hormati, and Scott Mahlke. 2013. SAGE: Self-tuning Approximation for Graphics Engines. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-46). ACM, New York, NY, USA, 13--24.
16. Peter Shirley, Changyaw Wang, and Kurt Zimmerman. 1996. Monte Carlo Techniques for Direct Lighting Calculations. ACM Trans. Graph. 15, 1 (Jan. 1996), 1--36.
17. Michalis Spyrou, Christos Kalogirou, Christos Konstantas, Panos K Koutsovasilis, Manolis Maroudas, Christos D Antonopoulos, and Nikolaos Bellas. 2015. Energy Minimization on Heterogeneous Systems through Approximate Computing. In International Conference on Parallel Computing (ParCo). IOS Press, Edinburgh, UK, 741--752.
18. John E. Stone, David Gohara, and Guochun Shi. 2010. OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems. IEEE Des. Test 12, 3 (May 2010), 66--73.
19. Kuen Hung Tsoi and Wayne Luk. 2011. Power Profiling and Optimization for Heterogeneous Multi-core Systems. SIGARCH Comput. Archit. News 39, 4 (Dec. 2011), 8--13.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Heterogeneous (hybrid) systems

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Scheduling

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis