Procrustes 1 : Power Constrained Performance Improvement Using Extended Maximize-Then-Swap Algorithm
Open Access
- 10 April 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 34 (10) , 1664-1676
Abstract
This paper proposes an efficient algorithm that maximizes performance under power constraints and is applicable in the general context of traditional dynamic voltage/frequency (V/P) scaling, or core heterogeneity and emerging dynamic micro-architectural adaptation. Performance maximization in these scenarios can be essentially viewed as mapping application threads to appropriate core states that have various power/performance characteristics. Such problems are formulated as a generic 0-1 integer linear program (ILP). The proposed algorithm is an iterative heuristic-based solution. Compared with an optimal solution generated by commercial ILP solver, the proposed algorithm produces results less than 1% away from optimum on average, with more than two orders of magnitude improvement in runtime. The algorithm can be brought online for hundred-core heterogeneous systems as it scales to systems comprised of 256 cores with less than 1 ms in overhead in worst cases. The intrinsic history awareness also provides flexibility to control cost induced by switching V/F pairs, migrating threads across cores, or tuning on/off micro-architectural resources.Keywords
Funding Information
- Intel University Research Office Grant
- NSF (CNS-1128624)
- Samsung Electronics Grant
This publication has 18 references indexed in Scilit:
- Price theory based power management for heterogeneous multi-cores2014
- Scheduling heterogeneous multi-cores through performance impact estimation (PIE)2012
- Sniper2011
- Scalable thread scheduling and global power management for heterogeneous many-core architectures2010
- Bias scheduling in heterogeneous multi-core architectures2010
- Efficient program scheduling for heterogeneous multi-core processors2009
- HASSACM SIGOPS Operating Systems Review, 2009
- The PARSEC benchmark suite2008
- Core fusion2007
- Dynamic thread assignment on heterogeneous multiprocessor architectures2006