Decomposability

Foreword

Preface

Acknowledgments

Introduction and Overview

Near-Complete Decomposability

Queueing Networks

Computer System Models

Chapter I Nearly Completely Decomposable Systems


1.1 Eigencharacteristics and Condition Numbers


1.2 The Simon-Ando Theorems


1.3 Interpretation of Theorems


1.4 Aggregation of Variables


1.5 Multilevel Decomposability


1.6 Block Triangular Systems

Chapter II On the Degree of Approximation


2.1 Error Analysis


2.2 Conditioning and Indecomposability of Aggregates


2.3 Block Stochastic Systems


2.4 Error Estimation


2.5 Multilevel Aggregation


2.6 A Posteriori Error Bound


2.7 Conclusions

Chapter III Criterion for Near-Complete Decomposability Equivalence Classes of Aggregates


3.1 Necessary Conditions


3.2 Criterion for Near-Complete Decomposability


3.3 Lumping States


3.4 Classes of Equivalence for Aggregates

Chapter IV Decomposability of Queueing Networks


4.1 Basic Model


4.2 Conditions for Near-Complete Decomposability


4.3 Sufficient Conditions of Network Decomposability


4.4 Discussion


4.5 Central-Server Model

Chapter V Hierarchy of Aggregate Resources


5.1 Decomposition Into Levels of Aggregation


5.2 Level Analysis


5.3 Interlevel Relationship


5.4 Conclusions

Chapter VI Queueing-Network Analysis


6.1 State Dependency


6.2 Arbitrary Service Time Distributions


6.3 Further Generalizations


6.4 Computational Efficiency

Chapter VII Memory Hierarchies


7.1 Basic Assumptions


7.2 Access Probabilities


7.3 Single-Process Storage Hierarchy


7.4 Multiprocess Storage Hierarchy


7.5 Near-Complete Decomposability


7.6 Memory Level Aggregation


7.7 Dynamic Space Sharing


7.8 Linear Storage Hierarchies

Chapter VIII Near-Complete Decomposability in Program Behavior


8.1 Preliminaries


8.2 Existing Models of Program Paging Behavior


8.3 Nearly Completely Decomposable Model of Program Behavior


8.4 Page Fault Rate


8.5 Numerical Example


8.6 Working-Set Size Distribution


8.7 Not Strictly Disjoint Localities


8.8 Conclusion

Chapter IX Instabilities and Saturation in Multiprogramming Systems


9.1 System Model


9.2 User Program Model


9.3 Simplifying Assumptions


9.4 Numerical Data


9.5 Page Fault Rate


9.6 Parachor and Parachron


9.7 Page Transfer Rate


9.8 Decomposability of the Model


9.9 Aggregate Short-Term Equilibrium


9.10 System Long-Term Equilibrium


9.11 Instabilities


9.12 Asymptotic Behavior of the Congestion


9.13 Saturation


9.14 System Response Time


9.15 Conclusions and Open Questions

Chapter X Hierarchical System Design


10.1 Levels of Abstraction


10.2 Aggregation and Ordering of Abstractions


10.3 Aggregation and Stepwise Design Evaluation

Conclusions

Appendix I Proof of Theorem 2.1

Appendix II Proof of Theorem 2.2

Appendix III Numerical Example

Appendix IV Eigenvalues of the Matrix Q(N, 1)

References

Index