This thesis presents scalable dynamic algorithms to solve the problems of load balancing and mapping in distributed computer systems.  The  load balancing problem partitions a large set of concurrent processes into equally balanced subsets for execution on a small set of computers.  The  mapping problem partitions the same set of processes into connected sub-graphs for the same purpose.  Both problems have the goal of optimizing the performance of the processes on the computers: in the case of load balancing, to equalize (and therefore minimize) the time required by each computer; in the case of mapping, to minimize the amount of communication among computers.

(Footnote: the mapping and load balancing problems are similar to a number of other important problems, such as the problem of partitioning circuits for VLSI placement and simulation.  The approach that is demonstrated here may be applicable to some of these other problems.)

These algorithms are constructed using an approach based on spectral properties of graphs: graphs of physical network links among computers in the load balancing problem, and graphs of logical communication channels among processes in the mapping problem.  In both problems the approach starts by characterizing problem solutions as equilibrium distributions of appropriately chosen scalar quantities.  For the load balancing problem this characterization is easily arrived at, since every solution is an equilibrium distribution of workload among a set of computers.  For the mapping problem the characterization is somewhat less obvious, and the equilibrium sought is an equal distribution of  communication distance as measured along paths through a physical interconnection network.

After the problem has been formulated in this way an algorithm is constructed from an iterative procedure to solve the Laplace equation on the vertices of the graph.  The procedure to solve the Laplace equation is analogous to a process in which an initial dis-equilibrium condition diffuses (or relaxes) to an equilibrium.  The iterative procedure yields a matrix of coefficients known as the  Laplacian matrix of the graph.  Spectral properties of this matrix can be used to analyze the convergence and scaling properties of the resulting algorithms.  The thesis uses these properties to prove a  scalability theorem which says that the resulting algorithms will reduce a discrete  disturbance at a constant rate regardless of the scale of the system in which the disturbance occurs.  Constant convergence can be a useful property for algorithms that execute on scalable computer systems, and a necessary property for the largest systems.

The scalability theorem assumes a simplified model in which individual imbalances arise, one after another, with each imbalance confined to a single computer.  In real applications this simplified model may not be realistic.  Imbalances may arise on several computers simultaneously, as a result of several unrelated events, or as a result of a single event that involves several computers.  When the number of such events is fixed the rate of convergence of the algorithms is not significantly affected by problem scale, just as in the case of a single disturbance.  Scale-independent convergence is also the expected behavior for any number of events, when they occur at random times, on randomly selected computers, and with random magnitude.

These claims of scalability are tested in an implementation of a distributed algorithm for image synthesis.  A dynamic load balancing algorithm is implemented according to the approach presented here, and used to support a photo-realistic Monte Carlo path tracing algorithm.  The scaling of these two algorithms are measured, and the observed load balancing solutions are compared to solutions produced by competing load balancing algorithms.  The measurements show that the performance of the load balancing and Monte Carlo algorithms are consistent with the scalability theorem.  The comparison shows that the load balancing algorithm is superior, in both cost and quality of solution, to a popular load balancing algorithm for ray-tracing on parallel computer systems.

A subsequent chapter presents the dynamic mapping problem and derives an algorithm to solve it.  The mapping algorithm is applied to a simple model problem that illustrates some of the issues that arise in a distributed application.  A final chapter discusses issues in developing the software for this study and shows a partial program trace for one of the many data points that were collected.  The purpose of presenting this information is to aid in reproducibility, by showing the many ancillary issues that must be addressed in order to implement the complete application.  It also shows explicitly how the data was gathered.

Scalability is the principal feature that distinguishes these algorithms from competing approaches.  The algorithms are distributed and concurrent, have no central thread of control, and require no centralized communication.  These properties are necessary for achieving scalable performance on the largest distributed computer systems.  Examples of such systems include "massively parallel" computer systems which have hundreds and in some cases thousands of processors connected by high performance communication networks.  Another example is the Internet which has millions of computers connected by a relatively poor network in which communication is slow and synchronization is impractical.

When scalability is not important the algorithms presented in this thesis have little advantage over competing approaches.  The load balancing and mapping problems can always be solved by serial algorithms that compute a solution on a single computer and then broadcast the result to the other computers.  A serial approach may often be the simplest to implement, and may be satisfactory for small parallel computer systems.  However this approach will not give scalable performance on large computer systems, and may not even be feasible on a system such as the Internet.  In these cases algorithms such as those presented here may be the only ones that are practical.
 

Summary of original contributions

This thesis presents novel problem formulations, algorithms, literature surveys, algorithm  analysis, and empirical data.  The key contributions are listed here.

• Algorithm 1 offers a distributed dynamic solution to the problems of load balancing, or of load balancing and mapping.  The derivation and correctness (sections 3.1, 3.2) make explicit the relationship between this algorithm (and others discussed in section 2.4.3) and the Laplace equation.  The explicitness of this relationship makes it possible to analyze these algorithms in terms of the spectral properties of the Laplacian matrix of a graph.  The Laplacian matrix has been used extensively to analyze properties of algorithms for the mapping problem, and in particular, the  recursive spectral bisection algorithm.  It has not previously been available for analysis of load balancing algorithms.

• A  scalability theorem proves that, for a purely local disturbance, the rate of convergence of algorithm 1 is constant on computer systems of arbitrarily large scale.  This property also holds for disturbances that are not purely local as is shown through discussion and simulation.  A model of the worst-case disturbance is presented for which algorithm 1 is ineffective.  This worst-case is shown to have a vanishing probability of occurrence with increasing problem scale.  In addition, it is shown that if the worst-case characteristics are not present in a problem at small scale, then they will not be present at large scales either.  These two characteristics are in sharp contrast to problems that commonly arise in solving differential equations by iterative algorithms and that give rise to research in multigrid methods.  In such problems the worst-case behavior has an increasing probability of occurrence with increasing problem scale, and problems that converge rapidly at small scales may converge slowly or not at all when the scale is increased.

• Algorithm 4 offers a scalable solution to the dynamic mapping problem based on the computational kernel of equation (3.5).  This is one of the first algorithms ever proposed for the dynamic mapping problem on general interconnection topologies.  The local nature of the algorithm ensures that it will produce better solutions than random placement algorithms.  The similarity of algorithms 1 and 4 serves to both unify and highlight the differences between the problems of load balancing and mapping.

• The analysis of randomization strategies in section 4.4 presents a model to calculate the expected workload imbalance on any number of computers as a function of statistical properties of an image.  This analysis shows that the difficulty of achieving a balanced workload increases with problem scale, and that tiling strategies commonly used for load balancing in image synthesis have a detrimental effect.  It illustrates the difficulty of achieving a balanced workload by static methods and shows the necessity for dynamic load balancing in distributed image synthesis computations.  This section presents predicted and simulated data for load imbalance of representative images on up to 1,024 computers.  This data may be useful to future studies in scalable image synthesis.

• Problems 1 and 2 define the dynamic load balancing problem in a form that is amenable to analysis.  These definitions make explicit the relationship between the problems of load balancing and mapping in a form that has not appeared previously.  This form makes it possible to present a unified discussion of these two problems, and to analyze them both within a common formal framework.

• Section 2.4.3 ("diffusion'') presents the most complete survey to date of a class of load balancing algorithms that are based on the informal concept of  diffusion.  This survey demonstrates that over the past several years a consensus has emerged about the preferred local load balancing algorithms for distributed applications.  The emergence of this consensus has not been widely recognized.

• Algorithm 2 describes a path tracing iteration to sample the photo-realistic values of image pixels in a Monte Carlo procedure.  It is unconventional to compute these values using an iteration, and this computation is typically formulated as a tail recursion.  The advantage of formulating the computation as an iteration rather than as a recursion is that it becomes easy to redistribute work among computers as a result of dynamic load balancing.

• Algorithm 3 shows one way to use algorithm 1 to provide dynamic load balancing for a Monte Carlo image synthesis application based on algorithm 2.  The discussion in section 4.3 ("a concurrent implementation'') brings to light practical issues of implementation that may be relevant to load balancing in support of other applications.

• An empirical comparison of the performance of four different load balancing strategies on systems of up to 64 computers appears in table 4.2.   These results reinforce the need for dynamic load balancing for problems in image synthesis.  They show that algorithm 1 was consistently as good as or superior to one of the most popular load balancing algorithms for ray-tracing on parallel computers.