Resource Proportional Software Design for Emerging Systems

Cover......Page 1
Half Title......Page 2
Title Page......Page 4
Copyright Page......Page 5
Contents......Page 6
Authors......Page 16
Preface......Page 18
Acknowledgments......Page 22
Part I: Software Bloat, Lost Throughput, and Wasted Joules......Page 24
 1. Introduction......Page 26
  1.1 Green Software for the Expanding Digital Universe: Designing with a Sense of Proportion......Page 27
  1.2 The Challenge Posed by Emerging Systems: Why Hardware Advancements Are Not Enough......Page 29
   1.2.1 Runtime bloat in framework based software......Page 30
   1.2.2 Software interaction with systems......Page 31
   1.2.3 Impact of non-volatile memory and low-latency fabrics......Page 33
   1.2.4 Large scale connected architectures from edge to cloud......Page 35
   1.2.5 Emerging software models and data centricity......Page 36
   1.3.1 The flexibility, productivity, and efficiency trade-off......Page 37
   1.3.2 Unsustainability of tightly coupled hardware-software abstractions......Page 38
   1.3.4 Difficulty in quantifying the opportunity and impact of software bloat reduction......Page 39
   1.4.1 How to assess the propensity for bloat in a software component?......Page 40
   1.4.2 How to broaden supported features without a runtime overhead?......Page 41
   1.4.3 Can software be designed to cope with changing trade-offs as technology evolves?......Page 42
   1.4.4 Can we anticipate what proportion of data processed by application is truly useful?......Page 43
  1.5 Dimensions of Resource Proportional Design......Page 44
   1.5.1 Resource proportional code features......Page 45
   1.5.2 Resource proportional response to technology and system evolution......Page 46
   1.5.3 Resource proportional data processing......Page 48
  1.6 Approach in This Book......Page 49
 2. The Problem of Software Bloat......Page 52
  2.1 The Notion of Software Bloat......Page 54
   2.2.1 Principal aspects of bloat......Page 55
   2.2.2 Definitions of software runtime bloat relevant for this book......Page 56
   2.2.3 Systemic practices in framework based development attributed as causes of bloat......Page 57
   2.3.2 Container image bloat......Page 60
   2.4.1 Runtime bloat categories in Java applications......Page 61
   2.4.2 Relationship between the various runtime manifestations of bloat......Page 62
   2.5.1 Modeling and measuring bloat......Page 63
    2.5.2.2 Automated code optimization......Page 67
    2.5.2.3 Can runtime bloat be avoided by construction?......Page 69
  2.6 Conclusions......Page 70
 3. Does Lean Imply Green? How Bloat in Software Impacts System Power Performance......Page 72
   3.1.1 Allocation wall effect......Page 74
   3.1.4 Influence of system configuration......Page 75
  3.2 Insights from an Experimental Study......Page 76
   3.2.1 Multi-platform experiments and results......Page 77
   3.2.2 Single platform experiment variations: Cache pressure and power management......Page 78
   3.2.3 Key experimental observations......Page 80
   3.3.1 Power efficiency impact quantified using a simple abstract model......Page 81
   3.3.3 System bottlenecks and bloat: A curious interaction......Page 83
    3.3.3.2 Bloat at bottleneck resource......Page 84
   3.3.5 Model predictions seen in experimental observations......Page 85
  3.4 Conclusions......Page 87
Part II: The Antidote: Resource Proportional Software Design......Page 88
 4. Resource Proportional Software Design Principles to Reduce Propensity for Bloat......Page 90
  4.2 Resource Proportional Design of Software Features......Page 91
  4.3 How Software Becomes Non-resource Proportional......Page 93
  4.4 Defining Resource Proportionality with Respect to Feature Utilization to Predict Bloat Propensity......Page 97
   4.4.2 Weighted RP accounting for scenario distribution......Page 99
   4.4.3 Effect of adding features not required for a scenario......Page 100
   4.4.5 Computing bloat propensity when Rspecialized is not directly available......Page 101
   4.4.6 Trade-off between feature exploitation and provisioning overhead......Page 102
    4.4.7.2 General scenarios (unordered feature spaces)......Page 103
  4.5 Resource Proportional Optimization Control Points for Bloat Mitigation......Page 104
  4.6 Conclusions......Page 106
 5. Resource Proportional Design Strategies I: What Component and Tool Developers Can Do......Page 108
  5.1 Strategy 1: Minimize Interactions between Independently Usable Features without Sacrificing Efficient Reuse......Page 109
   5.1.1 Development practice: Abstracting a minimal core of base features – Lessons from the Linux kernel......Page 110
   5.1.2 A formal discipline for labeling feature interactions due to optional features: Insights from FOP (feature oriented programming)......Page 112
   5.1.3 RPD analysis tool: Aid detection of structural interactions using Concern Augmented Program Analysis (CAPA)......Page 116
    5.1.3.1 Computing microslices......Page 118
    5.1.3.3 Computing the Concern Augmented microslice interaction graph......Page 120
    5.1.3.4 Putting it together: The CAPA tool......Page 123
   5.1.4 Interactions due to hidden features......Page 125
   5.2.1 Object reuse and result caching (amortize data construction overheads)......Page 126
   5.2.2 Adaptive selection and replacement of collection data structures......Page 128
   5.3.1 Insights from AOP (aspect oriented programming)......Page 129
   5.3.2 Practical considerations (80-20% rule vs. pure RPD)......Page 130
  5.4 Strategy 4: Design Programming Constructs and Runtimes with Resource Proportionality Awareness......Page 131
   5.4.2 Alternate data and program representations......Page 132
    5.4.2.2 Separating data structure bloat......Page 133
    5.4.2.3 New programming construct to represent associative pointers......Page 135
    5.4.2.4 Research topic: Content addressable data layout for associative structures......Page 136
  5.5 Summary......Page 140
 6. Resource Proportional Design Strategies II: Refactoring Existing Software for Improved Resource Proportionality......Page 144
   6.1.1 Resource utilization, bottleneck analysis and power, performance models......Page 145
   6.1.2 Measure indicators of bloat......Page 147
   6.2.1 Example: Serialization-Deserialization......Page 148
   6.3.1 Object reuse and memoization......Page 149
   6.4.1 Using optional feature indicators......Page 150
  6.5 Summary......Page 151
  7.1 Introduction......Page 154
   7.1.1 Resource proportionality and high level design: Internal vs. external brokering......Page 156
   7.1.2 A simple model for systems resource proportionality......Page 157
    7.1.2.1 A simple regression based model......Page 158
   7.1.3 Steering a system towards RP......Page 159
   7.1.4 Difficulties in realizing k-RPD......Page 161
    7.1.4.1 Searching a large RP design space......Page 163
   7.2.1 Impact on \"optimal\" RPDs......Page 164
    7.2.1.1 Impact on \"microservices\"-based RPDs......Page 165
   7.2.2 RPD in the context of rapid change......Page 166
  7.3 RPD and Security: Resource Usage as a Side Channel......Page 168
   7.3.1 RP remediation/countermeasures......Page 171
   7.4.1 Real time systems......Page 173
   7.4.2 Correctness......Page 175
  7.5 Conclusions......Page 177
Part III: Responding to Emerging Technologies: Designing Resource Proportional Systems......Page 178
  8.1 Characteristics of Emerging Persistent Memory Technologies......Page 180
   8.2.1 Data flow implications......Page 183
    8.2.1.1 Marshaling......Page 184
    8.2.1.2 Flushing and fencing......Page 185
    8.2.1.3 Data recoverability......Page 186
    8.2.2.1 Context switch elimination......Page 188
    8.2.2.2 Perturbation of CPU utilization......Page 190
   8.2.3 Code reuse implications......Page 192
    8.2.3.1 Data access granularity......Page 195
    8.2.3.2 Atomicity......Page 196
  8.3 Storage Stack Bloat in the Dual Stack Scenario......Page 197
   8.3.1 Analytic model of the dual stack scenario......Page 199
    8.3.1.2 RAM disk path......Page 201
    8.3.1.4 MM disk path......Page 202
    8.3.1.5 Dual stack RP baseline......Page 203
  8.4 Multi-Layer Storage Stack Bloat Related to Atomicity......Page 205
  8.5 Resource Proportional High Availability......Page 207
  8.6 HA and Atomicity Function Deployment Scenarios......Page 209
  8.7 Keeping up with the Evolution of Persistent Memory......Page 211
 9. Resource Proportionality in Memory Interconnects......Page 214
  9.1 Characteristics of Memory Interconnects......Page 215
  9.2 Resource Proportionality and the Separation of Media Controllers from Memory Controllers......Page 219
   9.2.1 Cost of asymmetric R/W latency with asynchronous MI......Page 220
  9.3 Efficiency Model of Memory Fabric......Page 224
  9.4 Resource Proportional Capacity Scaling......Page 227
    9.5.1.1 Multi-phase write......Page 229
   9.5.2 Functionality placement given split vs. monolithic memory controllers......Page 230
  9.6 Resource Proportionality and Memory Centric System Architecture......Page 234
  10.1 Introduction......Page 238
   10.1.1 Simple examples of RPD in systems design......Page 240
    10.1.1.1 Layering costs......Page 241
    10.1.1.2 Resource rate mismatch costs......Page 244
   10.1.2 Copy elimination in RDMA based storage stacks......Page 245
   10.1.3 High level RP systems design......Page 246
    10.1.3.1 Proportional design at different levels of the stack......Page 249
   10.1.4 RPD by mixing analog and digital components then and now......Page 252
   10.1.5 Blockchains and the proportional heuristic......Page 254
   10.1.7 Some newer issues......Page 256
   10.2.1 Chains......Page 259
   10.2.2 Crosslayer optimization......Page 260
   10.2.6 Applying the 80% 20% rule where possible......Page 261
   10.2.7 Some theoretical insights useful for RPD......Page 262
  10.3 General Design Principles and Observations for RPD......Page 263
  10.4 What Is Feasible Theoretically?......Page 268
  10.5 Conclusions......Page 271
 11. Data Centric Resource Proportional System Design......Page 272
   11.1.1 Data intensive rather than compute intensive......Page 273
   11.1.2 Analytics oriented: Emphasis on insight derivation rather than data serving......Page 274
  11.2 Data Centric Frameworks and Stack Evolution......Page 275
   11.3.1 Characteristic resource cost amplifiers in data centric applications......Page 276
    11.3.1.2 Fault tolerance, check-pointing, and lineage......Page 277
    11.3.2.2 Computation on data that does not produce additional insight......Page 278
  11.4 Graph Analytics Case Study......Page 280
   11.4.1 Reducing the size of the input graph data processed......Page 282
   11.4.2 Enhancing the proportion of relevant data paged in by the system......Page 283
  11.5 Data Mining Case Study (Map-reduce/Spark)......Page 285
   11.5.1 RPD aware storage systems for insight-centric applications......Page 286
    11.5.1.1 Cross-layer insight reuse......Page 287
    11.5.1.3 Approximation reuse......Page 288
  11.6 Streaming IoT Analytics Case Study......Page 289
  11.7 Summary......Page 292
Part IV: The Road Ahead......Page 294
 12. Adapting the Systems Software Stack to a Radically Non-Uniform Memory System......Page 296
  12.1 Resource Proportionality of Memory Resource Allocation......Page 297
   12.1.1 The evolution of memory pooling......Page 298
   12.1.2 Allocation system model......Page 301
  12.2 Comparison of Guided vs. Automated Allocation Policies......Page 303
   12.2.1 Class of Service driven allocation......Page 305
   12.2.2 Automated caching and phase change......Page 308
  12.3 Resource Proportionality of Waiting, Polling, and Context Switching......Page 310
  12.4 Managing Non-uniformity Using Work Flow Scheduling and Classes of Service......Page 313
  13.1 Introduction......Page 316
  13.2 Approximate Computing......Page 317
  13.3 Stateless Designs Revisited, or Reducing \"State Spill\"......Page 321
   13.3.1 \"Spill free designs\" and failures......Page 324
   13.3.3 Pointer management......Page 326
    13.3.3.1 Memory management, pointer management, and read-copy-update......Page 327
    13.3.3.3 Systems design vs. ML-based methods......Page 329
  13.4 Type Analysis......Page 330
   13.4.2 Homomorphic computation......Page 332
  13.5 When Is Resource Proportionality Not Applicable?......Page 333
  13.6 Conclusions......Page 335
 14. Conclusions......Page 336
  14.1 Applicability to Large Scale Solution Stacks, Rising Complexity, and Software Evolution......Page 337
  14.2 Resilience to Future Changes as Hardware Technology Advancements Are Raising the Bar......Page 340
  14.3 RP Impact on Productivity and Other Metrics......Page 341
  14.4 Future Systems Design......Page 343
Glossary......Page 346
Bibliography......Page 360
Index......Page 400