Title: Dynamic load balancing on distributed memory computer systems
Abstract: A large number of workloads on parallel systems exhibit variation of load across processors as time progresses. A reduction in execution time is likely if load is dynamically balanced across all participating processors.
New distributed dynamic load balancing schemes for distributed memory systems are presented here. Hierarchical is a general scheme based on hierarchically distributed control using progressively condensed information. Real applications are load balanced on real systems to test performance; the applications and systems are deliberately chosen to be diverse. Hierarchical performs better in branch-and-bound and search applications than, and performs equally well in applications with loosely-related tasks as, another well-performing scheme found in the literature. Statistical analysis using ANOVA enables inferences to be drawn regarding the applicability of these schemes to all datasets.
Conservative distributed simulations are representative of peculiar and complex workloads that require special load balancing schemes. The clock condition must be satisfied before load can be transferred. Various dynamic load balancing schemes are developed by considering various behavioral characteristics. Experimentation using a real manufacturing simulation and datasets with diverse load distributions indicates that dynamic load balancing is applicable to a very limited class of conservative simulations.
Adaptive load balancing schemes may improve performance over dynamic load balancing in spite of greater overhead. The circumstances under which adaptive load balancing is beneficial are studied. If transfer thresholds are to be adaptively varied then the workload's cost and benefit curves across threshold values should be changing in time.
A taxonomy of load balancing is developed that clarifies and unifies disparate concepts found in the literature. The taxonomy includes within its categories the taxonomies presented by other authors.
The relevant characteristics of workloads, computer systems and dynamic load balancing schemes are identified. The experiments indicate significant scheme-workload interaction. Critical workload characteristics cause the categorization of workloads into several classes. Recommendations are made for dynamically load balancing various computational problems on different types of computer systems.
Publication Year: 1992
Publication Date: 1992-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot