Periodic load balancing

Multiprocessor load balancing aims to improve performance by moving jobs fr om highly loaded processors to more lightly loaded processors. Some schemes allow only migration of new jobs upon arrival, while other schemes allow m igration of jobs in progress. A difficulty with all these schemes, however, is that they require continuously maintaining detailed state information. In this paper we consider the alternative of periodic load balancing, in wh ich the loads are balanced only at each T time units for some appropriate T . With periodic load balancing, state information is only needed at the bal ancing times. Moreover, it is often possible to use slightly stale informat ion collected during the interval between balancing limes. In this paper we study the performance of periodic load balancing. We consider multiple que ues in parallel with unlimited waiting space to which jabs come either in s eparate independent streams or by assignment (either random or cyclic) from a single stream. Resource sharing is achieved by periodically redistributi ng the jobs or the work in the system among the queues. The performance of these systems of queues coupled by periodic load balancing depends on the t ransient behavior of a single queue. We focus on useful approximations obta ined by considering a large number of homogeneous queues and a heavy load. When the number of queues is sufficiently large, the number of jobs or quan tity of work at each queue immediately after redistribution tends to evolve deterministically, by the law of large numbers. The steady-state (limiting ) value of this deterministic sequence is obtained as the solution of a fix ed point equation, where the initial value is equal to the expected transie nt value over the interval between successive redistributions conditional o n the initial value. A refined approximation based on the central limit the orem is a normal distribution, where the mean and variance are obtained by solving a pair of fixed-point equations. With higher loads, which is natura l to consider when load balancing is performed, a heavy-traffic limit theor em shows that one-dimensional reflected Brownian motion can be used to appr oximately describe system performance, even with general arrival and servic e processes. With these approximations, we show how performance depends on the assumed arrival pattern of jobs and the model parameters. We do numeric al calculations and conduct simulation experiments to show the accuracy of the approximations.