Resource Proportional Software Design for Emerging Systems

Description

Efficiency is a crucial concern across computing systems, from the edge to the cloud. Paradoxically, even as the latencies of bottleneck components such as storage and networks have dropped by up to four orders of magnitude, software path lengths have progressively increased due to overhead from the very frameworks that have revolutionized the pace of information technology. Such overhead can be severe enough to overshadow the benefits from switching to new technologies like persistent memory and low latency interconnects. Resource Proportional Software Design for Emerging Systems introduces resource proportional design (RPD) as a principled approach to software component and system development that counters the overhead of deeply layered code without removing flexibility or ease of development. RPD makes resource consumption proportional to situational utility by adapting to diverse emerging needs and technology systems evolution. Highlights: Analysis of run-time bloat in deep software stacks, an under-explored source of power-performance wastage in IT systems Qualitative and quantitative treatment of key dimensions of resource proportionality Code features: Unify and broaden supported but optional features without losing efficiency Technology and systems evolution: Design software to adapt with changing trade-offs as technology evolves Data processing: Design systems to predict which subsets of data processed by an (analytics or ML) application are likely to be useful System wide trade-offs: Address interacting local and global considerations throughout software stacks and hardware including cross-layer co-design involving code, data and systems dimensions, and non-functional requirements such as security and fault tolerance Written from a systems perspective to explore RPD principles, best practices, models and tools in the context of emerging technologies and applications This book is primarily geared towards practitioners with some advanced topics for researchers. The principles shared in the book are expected to be useful for programmers, engineers and researchers interested in ensuring software and systems are optimized for existing and next generation technologies. The authors are from both industry (Bhattacharya and Voigt) and academic (Gopinath) backgrounds. Cover Half Title Title Page Copyright Page Contents Authors Preface Acknowledgments Part I: Software Bloat, Lost Throughput, and Wasted Joules 1. Introduction 1.1 Green Software for the Expanding Digital Universe: Designing with a Sense of Proportion 1.2 The Challenge Posed by Emerging Systems: Why Hardware Advancements Are Not Enough 1.2.1 Runtime bloat in framework based software 1.2.2 Software interaction with systems 1.2.3 Impact of non-volatile memory and low-latency fabrics 1.2.4 Large scale connected architectures from edge to cloud 1.2.5 Emerging software models and data centricity 1.3 The Heart of the Matter: Why a Plea for Lean Software Is Not Enough 1.3.1 The flexibility, productivity, and efficiency trade-off 1.3.2 Unsustainability of tightly coupled hardware-software abstractions 1.3.3 Traditional performance optimization is not enough 1.3.4 Difficulty in quantifying the opportunity and impact of software bloat reduction 1.4 The Resource Proportional Software Design Principle 1.4.1 How to assess the propensity for bloat in a software component? 1.4.2 How to broaden supported features without a runtime overhead? 1.4.3 Can software be designed to cope with changing trade-offs as technology evolves? 1.4.4 Can we anticipate what proportion of data processed by application is truly useful? 1.5 Dimensions of Resource Proportional Design 1.5.1 Resource proportional code features 1.5.2 Resource proportional response to technology and system evolution 1.5.3 Resource proportional data processing 1.6 Approach in This Book 2. The Problem of Software Bloat 2.1 The Notion of Software Bloat 2.2 Software Bloat: Causes and Consequences 2.2.1 Principal aspects of bloat 2.2.2 Definitions of software runtime bloat relevant for this book 2.2.3 Systemic practices in framework based development attributed as causes of bloat 2.3 Bloat in Containerized Software 2.3.1 Application containers vs. virtual machines 2.3.2 Container image bloat 2.3.3 Runtime bloat in serverless computing 2.4 Different Forms of Software Runtime Bloat 2.4.1 Runtime bloat categories in Java applications 2.4.2 Relationship between the various runtime manifestations of bloat 2.5 Progress in Bloat Characterization, Measurement, and Mitigation 2.5.1 Modeling and measuring bloat 2.5.2 Mitigating and avoiding bloat 2.5.2.1 Semi-automated approaches 2.5.2.2 Automated code optimization 2.5.2.3 Can runtime bloat be avoided by construction? 2.6 Conclusions 3. Does Lean Imply Green? How Bloat in Software Impacts System Power Performance 3.1 The Effects of Java Runtime Bloat on System Resources 3.1.1 Allocation wall effect 3.1.2 Heap pressure effect 3.1.3 Object construction computation overhead 3.1.4 Influence of system configuration 3.2 Insights from an Experimental Study 3.2.1 Multi-platform experiments and results 3.2.2 Single platform experiment variations: Cache pressure and power management 3.2.3 Key experimental observations 3.3 Analyzing the Interplay of Bloat, Energy Proportionality, and System Bottlenecks 3.3.1 Power efficiency impact quantified using a simple abstract model 3.3.2 Effect of degrees of energy proportionality 3.3.3 System bottlenecks and bloat: A curious interaction 3.3.3.1 Bloat at non-bottleneck resource 3.3.3.2 Bloat at bottleneck resource 3.3.3.3 Bloat reduction shifts bottleneck 3.3.4 Summary 3.3.5 Model predictions seen in experimental observations 3.4 Conclusions Part II: The Antidote: Resource Proportional Software Design 4. Resource Proportional Software Design Principles to Reduce Propensity for Bloat 4.1 Insights from Energy Proportional Hardware Design 4.2 Resource Proportional Design of Software Features 4.3 How Software Becomes Non-resource Proportional 4.4 Defining Resource Proportionality with Respect to Feature Utilization to Predict Bloat Propensity 4.4.1 Effect of using a generalized component in this scenario 4.4.2 Weighted RP accounting for scenario distribution 4.4.3 Effect of adding features not required for a scenario 4.4.4 Bloat relative to actual resource consumed by a component 4.4.5 Computing bloat propensity when Rspecialized is not directly available 4.4.6 Trade-off between feature exploitation and provisioning overhead 4.4.7 Resource proportionality characteristics 4.4.7.1 Scenarios with montonically ordered feature spaces 4.4.7.2 General scenarios (unordered feature spaces) 4.5 Resource Proportional Optimization Control Points for Bloat Mitigation 4.6 Conclusions 5. Resource Proportional Design Strategies I: What Component and Tool Developers Can Do 5.1 Strategy 1: Minimize Interactions between Independently Usable Features without Sacrificing Efficient Reuse 5.1.1 Development practice: Abstracting a minimal core of base features – Lessons from the Linux kernel 5.1.2 A formal discipline for labeling feature interactions due to optional features: Insights from FOP (feature oriented programming) 5.1.3 RPD analysis tool: Aid detection of structural interactions using Concern Augmented Program Analysis (CAPA) 5.1.3.1 Computing microslices 5.1.3.2 Computing the microslice interaction graph 5.1.3.3 Computing the Concern Augmented microslice interaction graph 5.1.3.4 Putting it together: The CAPA tool 5.1.3.5 Example: Big endian to little endian conversion 5.1.4 Interactions due to hidden features 5.2 Strategy 2: Reduce Recurring Overheads due to Incidental Sources of Bloat 5.2.1 Object reuse and result caching (amortize data construction overheads) 5.2.2 Adaptive selection and replacement of collection data structures 5.3 Strategy 3: Activate or Deactivate High Overhead Features On-demand 5.3.1 Insights from AOP (aspect oriented programming) 5.3.2 Practical considerations (80-20% rule vs. pure RPD) 5.4 Strategy 4: Design Programming Constructs and Runtimes with Resource Proportionality Awareness 5.4.1 Annotating code with line of sight into sources of overheads 5.4.2 Alternate data and program representations 5.4.2.1 Separating code bloat 5.4.2.2 Separating data structure bloat 5.4.2.3 New programming construct to represent associative pointers 5.4.2.4 Research topic: Content addressable data layout for associative structures 5.5 Summary 6. Resource Proportional Design Strategies II: Refactoring Existing Software for Improved Resource Proportionality 6.1 Strategy 1: Whole System Impact Analysis to Identify Candidate Resources and Indicators of Bloat that Are Likely to Matter the Most 6.1.1 Resource utilization, bottleneck analysis and power, performance models 6.1.2 Measure indicators of bloat 6.2 Strategy 2: Replacing Entire Components or Features with a Different Implementation 6.2.1 Example: Serialization-Deserialization 6.2.2 Example: Collection replacement 6.2.3 Example: Trimming unused code (bloatware mitigation) 6.3 Strategy 3: Reduce Recurring Overheads Due to Incidental Sources of Bloat 6.3.1 Object reuse and memoization 6.4 Strategy 4: Refactor Code to Minimize Structural Interactions 6.4.1 Using optional feature indicators 6.4.2 Using concern analysis tools 6.5 Summary 7. Implications of a Resource Proportional Design 7.1 Introduction 7.1.1 Resource proportionality and high level design: Internal vs. external brokering 7.1.2 A simple model for systems resource proportionality 7.1.2.1 A simple regression based model 7.1.3 Steering a system towards RP 7.1.4 Difficulties in realizing k-RPD 7.1.4.1 Searching a large RP design space 7.1.5 Summary 7.2 RPD over Time 7.2.1 Impact on "optimal" RPDs 7.2.1.1 Impact on "microservices"-based RPDs 7.2.2 RPD in the context of rapid change 7.3 RPD and Security: Resource Usage as a Side Channel 7.3.1 RP remediation/countermeasures 7.4 RPD and Other Systemwide Concerns 7.4.1 Real time systems 7.4.2 Correctness 7.5 Conclusions Part III: Responding to Emerging Technologies: Designing Resource Proportional Systems 8. Resource Proportional Programming for Persistent Memory 8.1 Characteristics of Emerging Persistent Memory Technologies 8.2 System Implications of PM Technology 8.2.1 Data flow implications 8.2.1.1 Marshaling 8.2.1.2 Flushing and fencing 8.2.1.3 Data recoverability 8.2.2 Process flow implications 8.2.2.1 Context switch elimination 8.2.2.2 Perturbation of CPU utilization 8.2.3 Code reuse implications 8.2.3.1 Data access granularity 8.2.3.2 Atomicity 8.3 Storage Stack Bloat in the Dual Stack Scenario 8.3.1 Analytic model of the dual stack scenario 8.3.1.1 PM path 8.3.1.2 RAM disk path 8.3.1.3 Disk path 8.3.1.4 MM disk path 8.3.1.5 Dual stack RP baseline 8.4 Multi-Layer Storage Stack Bloat Related to Atomicity 8.5 Resource Proportional High Availability 8.6 HA and Atomicity Function Deployment Scenarios 8.7 Keeping up with the Evolution of Persistent Memory 9. Resource Proportionality in Memory Interconnects 9.1 Characteristics of Memory Interconnects 9.2 Resource Proportionality and the Separation of Media Controllers from Memory Controllers 9.2.1 Cost of asymmetric R/W latency with asynchronous MI 9.3 Efficiency Model of Memory Fabric 9.4 Resource Proportional Capacity Scaling 9.5 PM Related Functionality Placement 9.5.1 PM related functions 9.5.1.1 Multi-phase write 9.5.1.2 Atomic rewrite in place 9.5.1.3 Memory interleave 9.5.1.4 Redundancy 9.5.2 Functionality placement given split vs. monolithic memory controllers 9.6 Resource Proportionality and Memory Centric System Architecture 10. Applying Resource Proportional Design Principles to a Deeply Layered or Complex Software Stack 10.1 Introduction 10.1.1 Simple examples of RPD in systems design 10.1.1.1 Layering costs 10.1.1.2 Resource rate mismatch costs 10.1.2 Copy elimination in RDMA based storage stacks 10.1.3 High level RP systems design 10.1.3.1 Proportional design at different levels of the stack 10.1.4 RPD by mixing analog and digital components then and now 10.1.5 Blockchains and the proportional heuristic 10.1.6 Anti-RP designs 10.1.7 Some newer issues 10.2 Some High-level Recurring Patterns in RPD 10.2.1 Chains 10.2.2 Crosslayer optimization 10.2.3 Memoization, checkpointing, and lazy/deferred designs 10.2.4 Managing configuration space 10.2.5 Using virtualization 10.2.6 Applying the 80% 20% rule where possible 10.2.7 Some theoretical insights useful for RPD 10.3 General Design Principles and Observations for RPD 10.4 What Is Feasible Theoretically? 10.5 Conclusions 11. Data Centric Resource Proportional System Design 11.1 Characteristics of Data Centric Workloads 11.1.1 Data intensive rather than compute intensive 11.1.2 Analytics oriented: Emphasis on insight derivation rather than data serving 11.2 Data Centric Frameworks and Stack Evolution 11.3 Sources and Impact of Non-resource Proportionality 11.3.1 Characteristic resource cost amplifiers in data centric applications 11.3.1.1 Data movement expense 11.3.1.2 Fault tolerance, check-pointing, and lineage 11.3.2 Characteristic sources of overheads in data centric applications 11.3.2.1 Impedance mismatch between workload locality patterns and page locality of the system 11.3.2.2 Computation on data that does not produce additional insight 11.3.2.3 Unnecessary synchronization 11.4 Graph Analytics Case Study 11.4.1 Reducing the size of the input graph data processed 11.4.2 Enhancing the proportion of relevant data paged in by the system 11.5 Data Mining Case Study (Map-reduce/Spark) 11.5.1 RPD aware storage systems for insight-centric applications 11.5.1.1 Cross-layer insight reuse 11.5.1.2 Semantic similarity detection 11.5.1.3 Approximation reuse 11.5.1.4 Proactive data gradation 11.6 Streaming IoT Analytics Case Study 11.7 Summary Part IV: The Road Ahead 12. Adapting the Systems Software Stack to a Radically Non-Uniform Memory System 12.1 Resource Proportionality of Memory Resource Allocation 12.1.1 The evolution of memory pooling 12.1.2 Allocation system model 12.2 Comparison of Guided vs. Automated Allocation Policies 12.2.1 Class of Service driven allocation 12.2.2 Automated caching and phase change 12.3 Resource Proportionality of Waiting, Polling, and Context Switching 12.4 Managing Non-uniformity Using Work Flow Scheduling and Classes of Service 13. Bridging the Gap from What We Know Today to Open Challenges and Research Topics 13.1 Introduction 13.2 Approximate Computing 13.3 Stateless Designs Revisited, or Reducing "State Spill" 13.3.1 "Spill free designs" and failures 13.3.2 "Spill free designs" and "serverless" computing/microservices 13.3.3 Pointer management 13.3.3.1 Memory management, pointer management, and read-copy-update 13.3.3.2 Learned indices 13.3.3.3 Systems design vs. ML-based methods 13.4 Type Analysis 13.4.1 Information flow 13.4.2 Homomorphic computation 13.4.3 Intermittent computation 13.5 When Is Resource Proportionality Not Applicable? 13.6 Conclusions 14. Conclusions 14.1 Applicability to Large Scale Solution Stacks, Rising Complexity, and Software Evolution 14.2 Resilience to Future Changes as Hardware Technology Advancements Are Raising the Bar 14.3 RP Impact on Productivity and Other Metrics 14.4 Future Systems Design Glossary Bibliography Index