Adding safe and effective load balancing to multicomputers
Paul Martin · ERA · 1994
description of the system functions which support load balancing.The Testbed is used in many parts of the thesis because it allows various load balancing topics to be illustrated and because it offers a realistic environment in which to make measurements.Chapters 4 and 5 introduce the formal language Z and show how a specification of protocols for task synchronisation, communication and migration can be developed.The subject of Chapter 6 is verification and in it the safety and correctness of the specification are demonstrated.The cost profiles of the main Testbed operating system functions are given in Chapter 7.This work describes exactly how the experiments were set up and relates the results to the mechanisms specified in Chapters 4 and 5.Chapter 8 then enumerates methods for dynamic measurement of the load experienced by multicomputers and shows how good metrics are selected.A strategy for detecting load imbalances is developed and the effectiveness of a sample load balancer is measured for a range of parallel programs.Chapter 9 concludes the thesis, reviewing the contributions made to the subject area. Chapter 2 Previous Work as a Basis for ResearchThis chapter looks at the previous work on extending concurrent operating systems to support load balancing and develops a strategy for research into the subject of load balancing multicomputers.I begin by describing the motivation for concurrent computing, by classifying the key problems concomitant with concurrency and by identifying one of the greatest problems as being that of scheduling tasks on processors in a balanced way.The central part of this chapter presents a thorough review of the literature on scheduling and evaluates the costs and benefits of the various techniques that have been tried.Finally, I draw some important conclusions from the previous work and use them as a basis for developing a research plan on adding safe and effective load balancing to multicomputer operating systems. The Route to Higher PerformanceThe story of computing over the last 40 years has been one of innovation in architecture design and improvement in technology.Computer performance has increased dramatically with the introduction of pipelining, multiple functional units, caches and optimising compilers while advances in silicon technology have 6-1