Operating chips at high energy efficiency is one of the major challenges for modern large-scale supercomputers. Low-voltage operation of transistors increases the energy efficiency but leads to frequency and power variation across cores on the same chip. Finding energy-optimal configurations for such chips is a hard problem. In this work, we study how integer linear programming techniques can be used to obtain energy-efficient configurations of chips that have heterogeneous cores. Our proposed methodologies give optimal configurations as compared with competent but sub-optimal heuristics while having negligible timing overhead. The proposed ParSearch method gives up to 13.2% and 7% savings in energy while causing only 2% increase in execution time of two HPC applications: miniMD and Jacobi, respectively. Our results show that integer linear programming can be a very powerful online method to obtain energy-optimal configurations.
AcunBGuptaAJainN. (2015). Parallel programming with migratable objects: Charm++ in practice. In: International conference for high performance computing, networking, storage and analysis, SC, January 2015, pp. 647–658. IEEE. DOI: 10.1109/SC.2014.58
AgarwalAMathewSKHsuSK. (2010) A 320mV-to-1.2 V On-die Fine-grained Reconfigurable Fabric For DSP/media Accelerators in 32nm CMOS. In: 2010 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC). IEEE, pp. 328–329.
5.
AlonsoPDolzMFIgualFDMayoRQuintana-OrtES (2012) DVFS-control techniques for dense linear algebra operations on multi-core processors. Computer Science—Research and Development27(4): 289–298.
6.
AlonsoPDolzMFMayoRQuintana-OrtES (2011) Improving power efficiency of dense linear algebra algorithms on multi-core processors via slack control. In: 2011 International Conference on High Performance Computing and Simulation (HPCS). IEEE, pp. 463–470.
7.
BanerjeeAMukherjeeTVarsamopoulosGGuptaS (2010) Cooling-aware and thermal-aware workload placement for green HPC data centers. In: 2010 International Green Computing Conference, pp. 245–256.
8.
BashCFormanG (2007) Cool job allocation: measuring the power savings of placing jobs at cooling-efficient locations in the data center. In: Proceedings of the USENIX Annual Technical Conference. Berkeley, CA: USENIX Association, pp. 29:1–29:6.
9.
BazaraaMSJarvisJJSheraliHD (2011) Linear programming and network flows. New York: John Wiley & Sons.
10.
BehleBBofferdingNBroylesM. (2009) IBM Energyscale for POWER6 Processor-based Systems. IBM White Paper.
11.
BlumofeRDJoergCFKuszmaulBCLeisersonCERandallKHZhouY (1996) Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing37(1): 55–69.
12.
BroylesMFrancoisCGeisslerA. (2010) IBM Energyscale for POWER7 Processor-based Systems. IBM White Paper.
13.
CarlsonTEHeirmanWEeckhoutL (2011) Sniper: exploring the level of abstraction for scalable and accurate parallel multi-core simulation. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. New York: ACM Press, p. 52.
14.
ChoiKSomaRPedramM (2004) Dynamic voltage and frequency scaling based on workload decomposition. In: Proceedings of the 2004 international symposium on Low power electronics and design. New York: ACM Press, pp. 174–179.
15.
ChoiKSomaRPedramM (2005) Fine-grained dynamic voltage and frequency scaling for precise energy and performance tradeoff based on the ratio of off-chip access to on-chip computation times. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems24(1): 18–28.
16.
DagumLMenonR (1998) OpenMP: an industry standard API for shared-memory programming. IEEE Computational Science and Engineering5(1): 46–55.
EtinskiMCorbalanJLabartaJValeroM (2012) Understanding the future of energy-performance trade-off via DVFS in HPC Environments. Journal of Parallel and Distributed Computing72(4): 579–590.
19.
ForrestJ (2012) CBC (Coin-or Branch and Cut) Open-source Mixed Integer Programming Solver. Available at: https://projects.coin-or.org/Cbc.
20.
GloverFWoolseyE (1974) Converting the 0–1 polynomial programming problem to a 0–1 linear program. Operations Research22(1): 180–182.
21.
GraybillRMelhemR (2002) Power aware computing. Kluwer Academic Publishers.
22.
HsuCHFengWc (2005) Effective dynamic voltage scaling through CPU-boundedness detection. In: Power-Aware Computer Systems. Berlin: Springer, pp. 135–149.
23.
HsuSAgarwalAAndersM. (2012) A 2.8 GHz 128-entry× 152b 3-read/2-write Multi-precision Floating-point Register File and Shuffler in 32nm CMOS. In: 2012 Symposium on VLSI Circuits (VLSIC). IEEE, pp. 118–119.
24.
HuangCZhengGKumarSKaléLV (2006) Performance evaluation of adaptive MPI. In: Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2006.
25.
HuangSFengW (2009) Energy-efficient cluster computing via accurate workload characterization. In: Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID ’09). Washington, DC: IEEE Computer Society, pp. 68–75.
26.
KadayifIKandemirMSezerU (2002) An integer linear programming based approach for parallelizing applications in on-chip multiprocessors. In: Proceedings of the 39th annual Design Automation Conference. New York: ACM Press, pp. 703–706.
27.
KarpuzcuURKolluruKBKimNSTorrellasJ (2012) VARIUS-NTV: A microarchitectural model to capture the increased sensitivity of manycores to process variations at near-threshold voltages. In: 2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, pp. 1–11.
28.
KaulHAndersMHsuSAgarwalAKrishnamurthyRBorkarS (2012) Near-threshold voltage (NTV) design: opportunities and challenges. In: Proceedings of the 49th Annual Design Automation Conference. New York: ACM Press, pp. 1153–1158.
29.
KaulHAndersMMathewS. (2009a) A 300mV 494GOPS/W reconfigurable dual-supply 4-way SIMD vector processing accelerator in 45nm CMOS. In: IEEE International Solid-State Circuits Conference, ISSCC 2009, Digest of Technical Papers, San Francisco, CA, USA, 8–12 February, 2009, pp. 260–261.
30.
KaulHAndersMAMathewSK. (2009b) A 320 mV 56 µw 411 GOPS/Watt ultra-low voltage motion estimation accelerator in 65 nm CMOS. IEEE Journal of Solid-State Circuits44(1): 107–114.
31.
KumarRTullsenDMJouppiNP (2006) Core architecture optimization for heterogeneous chip multiprocessors. In: Proceedings of the 15th international conference on parallel architectures and compilation techniques. New York: ACM Press, pp. 23–32.
32.
LangerALifflanderJMillerPPanKCKaleLVRickerP (2012) Scalable algorithms for distributed-memory adaptive mesh refinement. In: Proceedings of the 24th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD 2012). New York, USA.
33.
LangerATotoniEPalekarUSKaléLV (2015) Energy-efficient computing for HPC workloads on heterogeneous manycore chips. In: Proceedings of the Sixth International Workshop on Programming Models and Applications for Multicores and Manycores (PMAM ’15). New York: ACM Press, pp. 11–19.
34.
LaundyRPerregaardMTavaresGTipiHVazacopoulosA (2009) Solving hard mixed-integer programming problems with Xpress-MP: A MIPLIB 2003 case study. INFORMS Journal on Computing21(2): 304–313.
35.
LiSAhnJHStrongRDBrockmanJBTullsenDMJouppiNP (2009) McPAT: an integrated power, area, and timing modeling framework for multicore and manycore architectures. In: 42nd Annual IEEE/ACM International Symposium on Microarchitecture, 2009 (MICRO-42). IEEE, pp. 469–480.
36.
LimMYFreehVWLowenthalDK (2011) Adaptive, transparent CPU scaling algorithms leveraging inter-node MPI communication regions. Parallel Computing37(10–11): 667–683.
MerkelABellosaF (2006) Balancing power consumption in multiprocessor systems. In: Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems (EuroSys ’06). New York: ACM Press, pp. 403–414.
39.
RizvandiNBTaheriJZomayaAY (2011) Some observations on optimal frequency selection in DVFS-based energy consumption minimization. Journal of Parallel and Distributed Computing71(8): 1154–1164.
40.
RountreeBAhnDHde SupinskiBRLowenthalDKSchulzM (2012) Beyond DVFS: a first look at performance under a hardware-enforced power bound. In: IEEE 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum (IPDPSW).
41.
RountreeBLowenthalDKFunkSFreehVWde SupinskiBRSchulzM (2007) Bounding energy consumption in large-scale MPI programs. In: Proceedings of the ACM/IEEE conference on supercomputing, pp. 49:1–49:9.
42.
SaroodOLangerAGuptaAKaleLV (2014) Maximizing throughput of overprovisioned hpc data centers under a strict power budget. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC ’14). New York: ACM Press.
43.
SaroodOLangerAKaleLVRountreeBde SupinskiB (2013) Optimizing power allocation to CPU and memory subsystems in overprovisioned HPC systems. In: Proceedings of IEEE Cluster 2013, Indianapolis, IN, USA.
SpringerRLowenthalDKRountreeBFreehVW (2006) Minimizing execution time in MPI programs on an energy-constrained, power-scalable cluster. In: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP ’06).New York: ACM Press, pp. 230–238.
46.
TangQGuptaSStanzioneDCaytonP (2006) Thermal-aware task scheduling to minimize energy usage of blade server based datacenters. In: 2nd IEEE International Symposium on Dependable, Autonomic and Secure Computing.
47.
TangQGuptaSVarsamopoulosG (2008) Energy-efficient thermal-aware task scheduling for homogeneous high-performance computing data centers: A cyber-physical approach. IEEE Transactions on Parallel and Distributed Systems11: 1458–1472.
48.
TotoniE (2014) Power and Energy Management of Modern Architectures in Adaptive HPC Runtime Systems. PhD Thesis, Dept. of Computer Science, University of Illinois.
49.
ValentiniGLLassondeWKhanSU. (2013) An overview of energy efficiency techniques in cluster computing systems. Cluster Computing16(1): 3–15.
50.
VenugopalanSSinnenO (2012) Optimal linear programming solutions for multiprocessor scheduling with communication delays. In: XiangYStojmenovicIApduhanBWangGNakanoKZomayaA (eds.) Algorithms and Architectures for Parallel Processing (Lecture Notes in Computer Science, vol. 7439). Berlin: Springer, pp. 129–138.
51.
VishnuASongSMarquezA. (2013) Designing energy efficient communication runtime systems: a view from pgas models. The Journal of Supercomputing63(3): 691–709.
52.
WallaceSVishwanathVCoghlanSLanZPapkaME (2013) Measuring power consumption on IBM Blue Gene/Q. In: 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW). IEEE, pp. 853–859.
53.
WangLKhanSUChenD. Energy-aware parallel task scheduling in a cluster. Future Generation Computer Systems29(7): 1661–1670.
54.
WangLvon LaszewskiGDayalJFurlaniT (2009a) Thermal aware workload scheduling with backfilling for green data centers. In: Proceedings of the 2009 IEEE 28th International Performance Computing and Communications Conference (IPCCC).
55.
WangLvon LaszewskiGDayalJHeXYoungeAFurlaniT (2009b) Towards thermal aware workload scheduling in a data center. In: International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN).
56.
WenGHongJXuCBalajiPFengSJiangP (2011) Energy-aware hierarchical scheduling of applications in large scale data centers. In: 2011 International Conference on Cloud and Service Computing (CSC). IEEE, pp. 158–165.
