SEEC Model for Self-Aware Computing System Optimization

The SEEC Framework and Runtime System Henry Hoffmann MIT CSAIL http://heartbeats.csail.mit.edu/ High Performance Embedded Computing Workshop September 21-22, 2011 This work was funded by the U.S. Government under the DARPA UHPC program. The views and conclusions contained herein are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Government.

In the beginning* Application programmers had one goal: Performance *The beginning, in this case, refers to the beginning of my career (1999) 2

But Modern Systems Have Increased the Burden on Application Programmers Lo Hi Power Power Many additional constraints Performance beat/s Even worse, constraints can change dynamically E.g. power cap, workload fluctuation, core failure 3

Most Programming Models Designed for Performance Coherent Shared Memory Global Shared Cache Message Passing data Local Memory Local Memory Local Cache Local Cache data data data data store store load load Network Network Interface Network Interface RF RF RF RF Core 0 Core 1 Core 0 Core 1 Multi-threaded Multi-process Concurrency Through Network Through Memory Communication Locks Messages Coordination Procedural Procedural Control Procedural control insufficient to meet the needs of modern systems 4

SEEC Replaces Procedural Control with Self-Aware Control Procedural Control Self-Aware Control Observe Decide Decide Act Act Run in open loop Run in closed loop Assumptions made at design time Based on guesses about future Understand user goals Monitor the environment - Application optimized for system - No flexibility to adapt to changes +System optimizes for application +Flexibly adapt behavior The self-aware model allows the system to solve constrained optimization problems dynamically 5

Outline Introduction/Motivation The SEEC Model and Implementation Experimental Validation Conclusions 6 6

The SElf-awarE Computing (SEEC) Model Goal: Reduce programmer burden by continuously optimizing online Key Features: 1. Decoupled Approach: Applications explicitly state goals and progress System software and hardware state available actions The SEEC runtime system dynamically selects actions to maintain goals 2. General and Extensible: New applications can be supported without training New actions can be added without redesign and reimplementation Observe Act Application Developer Systems Developer API SPI Decide SEEC Runtime 7

Example Self-Aware System Built from SEEC Observe Video Encoder 20 b/s 30 b/s 33 b/s Goals: 30 beat/s, Minimize Power Decide Act Control and Learning System Actuators Initial Model 9 8 Heart Rate 7 _r 6 Speedup 5 4 3 pure delay slow convergence oscillating 2 1 0 5 10 15 20 25 30 Algorithm Cores Time Action Desired Heart Rate _ r r Desired Heart Rate _ Application Application Error Error Speedup Speedup SEEC Controller Controller SEEC - - e(k) e(k) s(k) s(k) Observed Heart Rate Observed Heart Rate Frequency Bandwidth r(k) r(k) 8

Roles in SEECs Decoupled Model Application Developer Systems Developer SEEC Runtime System Express application goals and progress (e.g. frames/ second) Read goals and performance Observe Determine how to adapt (e.g. How much to speed up the application) Decide Provide a set of actions and a callback function (e.g. allocation of cores to process) Initiate actions based on results of decision phase Act 9

Observe Registering Application Goals Application Performance SEEC Quality Decision Engine Power Lo Hi Power Performance Goals: target heart rate and/or latency between tagged heartbeats Progress: issue heartbeats at important intervals Quality Goals: distortion (distance from application defined nominal value) Progress: distortion over last heartbeat Power Goals: target heart rate / Watt and/or target energy between tagged heartbeats Progress: Power/energy over last heartbeat interval Research to date focuses on meeting performance while minimizing power/maximizing quality 10

Act Registering System Actions Actuators Estimated Speedup SEEC Algorithm Cores Cost Decision Engine Callback Frequency Bandwidth Each action has the following attributes: Estimated Speedup Predicted benefit of taking an action Cost Predicted downside of taking an action Axis for cost (accuracy, power, etc.) RPC handle A function that takes an id an implements the associated action This is currently subject to change/redesign 11

The SEEC Decision Engine (A general, extensible approach) Decide Pros: Simple, Analyzable, Works well for profiled applications Cons: Lack of generality for unseen applications Classic Control System: Generalized second order system Controller (Decide) Actuator (Act) Application (Observe) Performance Goal - Current Performance 12

The SEEC Decision Engine (A general, extensible approach) Decide Pros: Adapts to unseen applications Cons: Assumes (relative) system models are correct Cannot support race-to-idle Adaptive Control: Based on 1-Dimensional Kalman Filter for Workload Estimation Application Model (Decide) Classic Control System Controller (Decide) Actuator (Act) Application (Observe) Performance Goal - Current Performance 13

The SEEC Decision Engine (A general, extensible approach) Pros: Supports race-to-idle and proportional allocation Cons: May overprovision due to system model errors Decide Adaptive Action Selection: Approximates solution to linear programming problem for meeting goals and minimizing cost Resource Model (Decide) Adaptive Control Application Model (Decide) Classic Control System Controller (Decide) Actuator (Act) Application (Observe) Performance Goal - Current Performance 14

The SEEC Decision Engine (A general, extensible approach) Decide Machine Learner: Uses reinforcement learning to estimate system models online, becomes control system when models converge Adaptive Action Selection System Model (Decide) Resource Model (Decide) Adaptive Control Application Model (Decide) Classic Control System Controller (Decide) Actuator (Act) Application (Observe) Performance Goal - Current Performance 15

Outline Introduction/Motivation The SEEC Model and Implementation Experimental Validation Conclusions 16 16

Systems Built with SEEC System Actions Tradeoff Benchmarks Dynamic Loop Perforation Skip some loop iterations Performance vs. Quality 7/13 PARSECs Dynamic Knobs Make static parameters dynamic Performance vs. Quality bodytrack, swaptions, x264, SWISH++ Core Scheduler Assign N cores to application Compute vs. Power PARSEC Clock Scaler Change processor speed Compute vs. Power PARSEC Bandwidth Allocator Assign memory controllers to application Memory vs. Power STREAM, PARSEC Power Manager Combination of the three above Performance vs. Power PARSEC, STREAM, simple test apps (mergesort, binary search) Learned Models Power Manager with speedup and cost learned online Performance vs. Power PARSEC Multi-App Control Power Manager with multiple applications Performance vs. Power and Quality for multiple applications Combinations of PARSECs 17 17

Systems Built with SEEC System Actions Tradeoff Benchmarks Dynamic Loop Perforation Skip some loop iterations Performance vs. Quality 7/13 PARSECs Dynamic Knobs Make static parameters dynamic Performance vs. Quality bodytrack, swaptions, x264, SWISH++ Core Scheduler Assign N cores to application Compute vs. Power PARSEC Clock Scaler Change processor speed Compute vs. Power PARSEC Bandwidth Allocator Assign memory controllers to application Memory vs. Power STREAM Power Manager Combination of the three above Performance vs. Power PARSEC, STREAM, extra test apps (mergesort, binary search) Learned Models Power Manager with speedup and cost learned online Performance vs. Power PARSEC Multi-App Control Power Manager with multiple applications Performance vs. Power and Quality for multiple applications Combinations of PARSECs 18 18

Constrained Optimization: Managing Performance/Watt for PARSEC Optimize performance/Watt on multiple machines Maintain performance, minimize power Application Goals Allocate cores Allocate clock speed System Actions Allocate memory bandwidth Execute on two machines (w/ different power profiles) Experiment Compare SEEC to several other approaches including a static oracle 19 19

Performance/Watt for PARSEC (On server with low idle power) static oracle Heuristic Classic Control SEEC (AAS) SEEC (ML) 1.4 Normalized Performance Per Watt 1.2 1 0.8 0.6 0.4 0.2 0 Benchmark SEEC beats the static oracle by adjusting to phases within an application and recognizing when to race-to-idle

Performance/Watt for PARSEC (On server with high idle power) static oracle Heuristic Classic Control SEEC (AAS) SEEC (ML) 1.6 Normalized Performance Per Watt 1.4 1.2 1 0.8 0.6 0.4 0.2 0 Benchmark SEEC is able to beat the static oracle on a different machine without code changes

Learning Models Online Adapt system behavior when initial models are wrong Minimize power consumption while meeting target performance Application Goals Change cores, clock speed, and mem. bandwidth System Actions Initial models are incredibly optimistic (Assume linear speedup with any resource increase) Benchmark: STREAM Experiment Observe convergence time and performance/Watt for converged system 22 22

SEEC Can Learn Models Online Classic Control SEEC 1.2 Normalized Performance Per 1 0.8 Watt 0.6 0.4 0.2 0 0 100 200 Time 300 400 SEEC learns not to allocate too many compute resources to a memory bound application

When System Models Are Wrong (Breakdown) Classic Control SEEC (AAS) SEEC (ML) Classic Control SEEC (AAS) SEEC (ML) 1.2 1.4 1 Normalized Performance 1.2 Normalized Power 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0 0 0 100 200 Time 300 400 0 100 200 Time 300 400 Adaptive Control achieves performance fastest, but wastes power. ML reaches target performance slowest, but saves power 24

Managing Application and System Resources Concurrently Manage multiple applications when clock frequency changes bodytrack: maintain performance, minimize power Application Goals x264: maintain performance, minimize quality loss Change core allocation to both applications System Actions Change x264 s algorithms Maintain performance of both applications when clock frequency changes Experiment 25 25

SEEC Management of Multiple Applications In Response to a Power Cap bodytrack x264 SEEC allocates cores to bodytrack SEEC removes cores from x264 2.5 7 2.5 7 x264 w/ adaptation x264 x264 cores 6 6 2 2 Normalized Performance Normalized Performance 5 5 1.5 1.5 4 4 Cores Cores 3 3 1 1 2 2 bodytrack w/ adaptation bodytrack bodytrack cores 0.5 0.5 1 1 0 0 0 0 40 Clock drops 2.4-1.6GHz 90 140 190 240 40 90 140 190 240 Time (Heartbeat) Time (Heartbeat) SEEC adjusts algorithm to meet goals w/o SEEC app misses goals w/o SEEC app exceeds goals 26 26

Outline Introduction/Motivation The SEEC Framework Experimental Validation Conclusions 27 27

Conclusions SEEC is designed to help ease programmer burden Solves resource allocation problems Adapts to fluctuations in environment and application behavior SEEC has two distinguishing features Decoupled Design Incorporates goals and feedback directly from the application Allows independent specification of adaptation General and Extensible Decision Engine Uses an adaptive second order control system to manage adaptation Demonstrated the benefits of SEEC in several experiments Optimize performance per Watt for multiple benchmarks on multiple machines Adapts algorithms and resource allocation as environment changes 28 28

Thanks DARPA s UHPC Program MIT, Politecnico di Milano, Freescale Martina Maggio, Marco D. Santambrogio, Jason E. Miller, Jonathan Eastep Stelios Sidiroglou, Sasa Misailovic, Michael Carbin Anant Agarwal, Martin Rinard, Alberto Leva, Jim Holt 29