by Sau-ming Lau. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 131-134). / Abstract --- p.i / Acknowledgement --- p.iii / List of Tables --- p.viii / List of Figures --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Basic Concepts and Related Work --- p.9 / Chapter 2.1 --- Components of Dynamic Load Balancing Algorithms --- p.10 / Chapter 2.2 --- Classification of Load Balancing Algorithms --- p.11 / Chapter 2.2.1 --- Casavant and Kuhl's Taxonomy --- p.12 / Chapter 3 --- System Model and Assumptions --- p.19 / Chapter 3.1 --- The System Model and Assumptions --- p.19 / Chapter 3.2 --- Survey on Cost Models --- p.21 / Chapter 3.2.1 --- "Eager, Lazowska, and Zahorjan's Model" --- p.22 / Chapter 3.2.2 --- "Shivaratri, Krueger, and Singhal's Model" --- p.23 / Chapter 3.3 --- Our Cost Model --- p.24 / Chapter 3.3.1 --- Design Philosophy --- p.24 / Chapter 3.3.2 --- Polling Query Cost Model --- p.25 / Chapter 3.3.3 --- Load State Broadcasting Cost Model --- p.26 / Chapter 3.3.4 --- Task Assignment Cost Model --- p.27 / Chapter 3.3.5 --- Task Migration Cost Model --- p.28 / Chapter 3.3.6 --- Execution Priority --- p.29 / Chapter 3.3.7 --- Simulation Parameter Values --- p.31 / Chapter 3.4 --- Performance Metrics --- p.33 / Chapter 4 --- A Performance Study on Load Information Dissemination Strategies --- p.36 / Chapter 4.1 --- Algorithm Descriptions --- p.37 / Chapter 4.1.1 --- Transfer Policy --- p.37 / Chapter 4.1.2 --- Information Policy --- p.40 / Chapter 4.1.3 --- Location Policy --- p.40 / Chapter 4.1.4 --- Categorization of the Algorithms --- p.43 / Chapter 4.2 --- Simulations and Analysis of Results --- p.43 / Chapter 4.2.1 --- Performance Comparisons --- p.44 / Chapter 4.2.2 --- Effect of Imbalance Factor on AWLT Algorithms --- p.49 / Chapter 4.2.3 --- Comparison of Average Performance --- p.52 / Chapter 4.2.4 --- Raw Simulation Results --- p.54 / Chapter 4.3 --- Discussions --- p.55 / Chapter 5 --- Resolving Processor Thrashing with Batch Assignment --- p.56 / Chapter 5.1 --- The GR.batch Algorithm --- p.57 / Chapter 5.1.1 --- The Guarantee and Reservation Protocol --- p.57 / Chapter 5.1.2 --- The Location Policy --- p.58 / Chapter 5.1.3 --- Batch Size Determination --- p.60 / Chapter 5.1.4 --- The Complete GR.batch Description --- p.62 / Chapter 5.2 --- Additional Performance Metrics --- p.66 / Chapter 5.3 --- Simulations and Analysis of Results --- p.67 / Chapter 5.4 --- Discussions --- p.73 / Chapter 6 --- Applying Batch Assignment to Systems with Bursty Task Arrival Patterns --- p.75 / Chapter 6.1 --- Bursty Workload Pattern Characterization Model --- p.76 / Chapter 6.2 --- Algorithm Descriptions --- p.77 / Chapter 6.2.1 --- The GR.batch Algorithm --- p.77 / Chapter 6.2.2 --- The SK .single Algorithm --- p.77 / Chapter 6.2.3 --- Summary of Algorithm Properties --- p.77 / Chapter 6.3 --- Analysis of Simulation Results --- p.77 / Chapter 6.3.1 --- Performance Comparison --- p.79 / Chapter 6.3.2 --- Time Trace --- p.80 / Chapter 6.4 --- Discussions --- p.80 / Chapter 7 --- A Preliminary Study on Task Assignment Augmented with Migration --- p.87 / Chapter 7.1 --- Algorithm Descriptions --- p.87 / Chapter 7.1.1 --- Information Policy --- p.88 / Chapter 7.1.2 --- Location Policy --- p.88 / Chapter 7.1.3 --- Transfer Policy --- p.88 / Chapter 7.1.4 --- The Three Load Balancing Algorithms --- p.89 / Chapter 7.2 --- Simulations and Analysis of Results --- p.90 / Chapter 7.2.1 --- Even Task Service Time --- p.90 / Chapter 7.2.2 --- Uneven Task Service Time --- p.94 / Chapter 7.3 --- Discussions --- p.99 / Chapter 8 --- Assignment Augmented with Migration Revisited --- p.100 / Chapter 8.1 --- Algorithm Descriptions --- p.100 / Chapter 8.1.1 --- The GR.BATCH.A Algorithm --- p.101 / Chapter 8.1.2 --- The SK.SINGLE.AM Algorithm --- p.101 / Chapter 8.1.3 --- Summary of Algorithm Properties --- p.101 / Chapter 8.2 --- Simulations and Analysis of Results --- p.101 / Chapter 8.2.1 --- Performance Comparisons --- p.102 / Chapter 8.2.2 --- Effect of Workload Imbalance --- p.105 / Chapter 8.3 --- Discussions --- p.106 / Chapter 9 --- Applying Batch Transfer to Heterogeneous Systems with Many Task Classes --- p.108 / Chapter 9.1 --- Heterogeneous System Model --- p.109 / Chapter 9.1.1 --- Processing Node Specification --- p.110 / Chapter 9.1.2 --- Task Type Specification --- p.111 / Chapter 9.1.3 --- Workload State Measurement --- p.112 / Chapter 9.1.4 --- Task Selection Candidates --- p.113 / Chapter 9.2 --- Algorithm Descriptions --- p.115 / Chapter 9.2.1 --- First Category ´ؤ The Sk .single Variations --- p.115 / Chapter 9.2.2 --- Second Category ´ؤ The GR. batch Variation Modeled with SSP --- p.117 / Chapter 9.3 --- Analysis of Simulation Results --- p.123 / Chapter 10 --- Conclusions and Future Work --- p.127 / Bibliography --- p.131 / Appendix A System Model Notations and Definitions --- p.131 / Appendix A.1 Processing Node Model --- p.131 / Appendix A.2 Cost Models --- p.132 / Appendix A.3 Load Measurement --- p.134 / Appendix A.4 Batch Size Determination Rules --- p.135 / Appendix A.5 Bursty Arrivals Modeling --- p.135 / Appendix A.6 Heterogeneous Systems Modeling --- p.135 / Appendix B Shivaratri and Krueger's Location Policy --- p.137
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_320606 |
| Date | January 1995 |
| Contributors | Lau, Sau-ming., Chinese University of Hong Kong Graduate School. Division of Computer Science. |
| Publisher | Chinese University of Hong Kong |
| Source Sets | The Chinese University of Hong Kong |
| Language | English |
| Detected Language | English |
| Type | Text, bibliography |
| Format | print, xii, 142 leaves : ill. ; 30 cm. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0026 seconds