PREFACE xxix ACKNOWLEDGMENTS xxxi CONTRIBUTORS xxxiii 1 POWER ALLOCATION AND TASK SCHEDULING ON MULTIPROCESSOR COMPUTERS WITH ENERGY AND TIME CONSTRAINTS 1 Keqin Li 1.1 Introduction 1 1.1.1 Energy Consumption 1 1.1.2 Power Reduction 2 1.1.3 Dynamic Power Management 3 1.

1.4 Task Scheduling with Energy and Time Constraints 4 1.1.5 Chapter Outline 5 1.2 Preliminaries 5 1.2.1 Power Consumption Model 5 1.2.

2 Problem Definitions 6 1.2.3 Task Models 7 1.2.4 Processor Models 8 1.2.5 Scheduling Models 9 1.2.

6 Problem Decomposition 9 1.2.7 Types of Algorithms 10 1.3 Problem Analysis 10 1.3.1 Schedule Length Minimization 10 1.3.1.

1 Uniprocessor computers 10 1.3.1.2 Multiprocessor computers 11 1.3.2 Energy Consumption Minimization 12 1.3.2.

1 Uniprocessor computers 12 1.3.2.2 Multiprocessor computers 13 1.3.3 Strong NP-Hardness 14 1.3.4 Lower Bounds 14 1.

3.5 Energy-Delay Trade-off 15 1.4 Pre-Power-Determination Algorithms 16 1.4.1 Overview 16 1.4.2 Performance Measures 17 1.4.

3 Equal-Time Algorithms and Analysis 18 1.4.3.1 Schedule length minimization 18 1.4.3.2 Energy consumption minimization 19 1.4.

4 Equal-Energy Algorithms and Analysis 19 1.4.4.1 Schedule length minimization 19 1.4.4.2 Energy consumption minimization 21 1.4.

5 Equal-Speed Algorithms and Analysis 22 1.4.5.1 Schedule length minimization 22 1.4.5.2 Energy consumption minimization 23 1.4.

6 Numerical Data 24 1.4.7 Simulation Results 25 1.5 Post-Power-Determination Algorithms 28 1.5.1 Overview 28 1.5.2 Analysis of List Scheduling Algorithms 29 1.

5.2.1 Analysis of algorithm LS 29 1.5.2.2 Analysis of algorithm LRF 30 1.5.3 Application to Schedule Length Minimization 30 1.

5.4 Application to Energy Consumption Minimization 31 1.5.5 Numerical Data 32 1.5.6 Simulation Results 32 1.6 Summary and Further Research 33 References 34 2 POWER-AWARE HIGH PERFORMANCE COMPUTING 39 Rong Ge and Kirk W. Cameron 2.

1 Introduction 39 2.2 Background 41 2.2.1 Current Hardware Technology and Power Consumption 41 2.2.1.1 Processor power 41 2.2.

1.2 Memory subsystem power 42 2.2.2 Performance 43 2.2.3 Energy Efficiency 44 2.3 Related Work 45 2.3.

1 Power Profiling 45 2.3.1.1 Simulator-based power estimation 45 2.3.1.2 Direct measurements 46 2.3.

1.3 Event-based estimation 46 2.3.2 Performance Scalability on Power-Aware Systems 46 2.3.3 Adaptive Power Allocation for Energy-Efficient Computing 47 2.4 PowerPack: Fine-Grain Energy Profiling of HPC Applications 48 2.4.

1 Design and Implementation of PowerPack 48 2.4.1.1 Overview 48 2.4.1.2 Fine-grain systematic power measurement 50 2.4.

1.3 Automatic power profiling and code synchronization 51 2.4.2 Power Profiles of HPC Applications and Systems 53 2.4.2.1 Power distribution over components 53 2.4.

2.2 Power dynamics of applications 54 2.4.2.3 Power bounds on HPC systems 55 2.4.2.4 Power versus dynamic voltage and frequency scaling 57 2.

5 Power-Aware Speedup Model 59 2.5.1 Power-Aware Speedup 59 2.5.1.1 Sequential execution time for a single workload T1(w, f ) 60 2.5.1.

2 Sequential execution time for an ON-chip/OFF-chip workload 60 2.5.1.3 Parallel execution time on N processors for an ON-/OFF-chip workload with DOP = i 61 2.5.1.4 Power-aware speedup for DOP and ON-/OFF-chip workloads 62 2.5.

2 Model Parametrization and Validation 63 2.5.2.1 Coarse-grain parametrization and validation 64 2.5.2.2 Fine-grain parametrization and validation 66 2.6 Model Usages 69 2.

6.1 Identification of Optimal System Configurations 70 2.6.2 PAS-Directed Energy-Driven Runtime Frequency Scaling 71 2.7 Conclusion 73 References 75 3 ENERGY EFFICIENCY IN HPC SYSTEMS 81 Ivan Rodero and Manish Parashar 3.1 Introduction 81 3.2 Background and Related Work 83 3.2.

1 CPU Power Management 83 3.2.1.1 OS-level CPU power management 83 3.2.1.2 Workload-level CPU power management 84 3.2.

1.3 Cluster-level CPU power management 84 3.2.2 Component-Based Power Management 85 3.2.2.1 Memory subsystem 85 3.2.

2.2 Storage subsystem 86 3.2.3 Thermal-Conscious Power Management 87 3.2.4 Power Management in Virtualized Datacenters 87 3.3 Proactive, Component-Based Power Management 88 3.3.

1 Job Allocation Policies 88 3.3.2 Workload Profiling 90 3.4 Quantifying Energy Saving Possibilities 91 3.4.1 Methodology 92 3.4.2 Component-Level Power Requirements 92 3.

4.3 Energy Savings 94 3.5 Evaluation of the Proposed Strategies 95 3.5.1 Methodology 96 3.5.2 Workloads 96 3.5.

3 Metrics 97 3.6 Results 97 3.7 Concluding Remarks 102 3.8 Summary 103 References 104 4 A STOCHASTIC FRAMEWORK FOR HIERARCHICAL SYSTEM-LEVEL POWER MANAGEMENT 109 Peng Rong and Massoud Pedram 4.1 Introduction 109 4.2 Related Work 111 4.3 A Hierarchical DPM Architecture 113 4.4 Modeling 114 4.

4.1 Model of the Application Pool 114 4.4.2 Model of the Service Flow Control 118 4.4.3 Model of the Simulated Service Provider 119 4.4.4 Modeling Dependencies between SPs 120 4.

5 Policy Optimization 122 4.5.1 Mathematical Formulation 122 4.5.2 Optimal Time-Out Policy for Local Power Manager 123 4.6 Experimental Results 125 4.7 Conclusion 130 References 130 5 ENERGY-EFFICIENT RESERVATION INFRASTRUCTURE FOR GRIDS, CLOUDS, AND NETWORKS 133 Anne-Ce´ cile Orgerie and Laurent Lefe' vre 5.1 Introduction 133 5.

2 Related Works 134 5.2.1 Server and Data Center Power Management 135 5.2.2 Node Optimizations 135 5.2.3 Virtualization to Improve Energy Efficiency 136 5.2.

4 Energy Awareness in Wired Networking Equipment 136 5.2.5 Synthesis 137 5.3 ERIDIS: Energy-Efficient Reservation Infrastructure for Large-Scale Distributed Systems 138 5.3.1 ERIDIS Architecture 138 5.3.2 Management of the Resource Reservations 141 5.

3.3 Resource Management and On/Off Algorithms 145 5.3.4 Energy-Consumption Estimates 146 5.3.5 Prediction Algorithms 146 5.4 EARI: Energy-Aware Reservation Infrastructure for Data Centers and Grids 147 5.4.

1 EARI''s Architecture 147 5.4.2 Validation of EARI on Experimental Grid Traces 147 5.5 GOC: Green Open Cloud 149 5.5.1 GOC''s Resource Manager Architecture 150 5.5.2 Validation of the GOC Framework 152 5.

6 HERMES: High Level Energy-Aware Model for Bandwidth Reservation in End-To-End Networks 152 5.6.1 HERMES'' Architecture 154 5.6.2 The Reservation Process of HERMES 155 5.6.3 Discussion 157 5.7 Summary 158 References 158 6 ENERGY-EFFICIENT JOB PLACEMENT ON CLUSTERS, GRIDS, AND CLOUDS 163 Damien Borgetto, Henri Casanova, Georges Da Costa, and Jean-Marc Pierson 6.

1 Problem and Motivation 163 6.1.1 Context 163 6.1.2 Chapter Roadmap 164 6.2 Energy-Aware Infrastructures 164 6.2.1 Buildings 165 6.

2.2 Context-Aware Buildings 165 6.2.3 Cooling 166 6.3 Current Resource Management Practices 167 6.3.1 Widely Used Resource Management Systems 167 6.3.

2 Job Requirement Description 169 6.4 Scientific and Technical Challenges 170 6.4.1 Theoretical Difficulties 170 6.4.2 Technical Difficulties 170 6.4.3 Controlling and Tuning Jobs 171 6.

5 Energy-Aware Job Placement Algorithms 172 6.5.1 State of the Art 172 6.5.2 Detailing One Approach 174 6.6 Discussion 180 6.6.1 Open Issues and Opportunities 180 6.

6.2 Obstacles for Adoption in Production 182 6.7 Conclusion 183 References 184 7 COMPARISON AND ANALYSIS OF GREEDY ENERGY-EFFICIENT SCHEDULING ALGORITHMS FOR COMPUTATIONAL GRIDS 189 Peder Lindberg, James Leingang, Daniel Lysaker, Kashif Bilal, Samee Ullah Khan, Pascal Bouvry, Nasir Ghani, Nasro Min-Allah, and Juan Li 7.1 Introduction 189 7.2 Problem Formulation 191 7.2.1 The System Model 191 7.2.

1.1 PEs 191 7.2.1.2 DVS 191 7.2.1.3 Tasks 192 7.

2.1.4 Preliminaries 192 7.2.2 Formulating the Energy-Makespan Minimization Problem 192 7.3 Proposed Algorithms 193 7.3.1 Greedy Heuristics 194 7.

3.1.1 Greedy heuristic scheduling algorithm 196 7.3.1.2 Greedy-min 197 7.3.1.

3 Greedy-deadline 198 7.3.1.4 Greedy-max 198 7.3.1.5 MaxMin 199 7.3.

1.6 ObFun 199 7.3.1.7 MinMin StdDev 202 7.3.1.8 MinMax StdDev 202 7.

4 Simulations, Results, and Discussion 203 7.4.1 Workload 203 7.4.2 Comparative Results 204 7.4.2.1 Small-size problems 204 7.

4.2.2 Large-size problems 206 7.5 Related Works 211 7.6 Conclusion 211 References 212 8 TOWARD ENERGY-AWARE SCHEDULING USING MACHINE LEARNING 215 Josep LL. Berral, In~ igo Goiri, Ramon Nou, Ferran Julia' , Josep O. Fito´ , Jordi Guitart, Ricard Gavalda´ , and Jordi Torres 8.1 Introduction 215 8.

1.1 Energetic Impact of the Cloud 216 8.1.2 An Intelligent Way to Manage Data Centers 216 8.1.3 Current Autonomic Computing Techniques 217