| Abstract: | We have studied the interaction between process-based parallel programs whose characteristics change in various ways at run time and the operation of load-balancing, as implemented by process migration. In order to do this, we propose a simple performance model, whose parameters represent features of the program's execution such as the frequency and regularity of the changes in computational characteristics, and conduct a series of experiments involving simulated executions of synthetic programs with controlled parameter values. From these we can deduce the relative importance of the parameters from the point of view of their influence on performance. We can explain our observations in terms of a simplified stochastic model that relates local changes in load to global behaviour. We show that the dynamics of load-balancing can be represented approximately by a first-order difference equation, and that the distributed process migration algorithm is consistent with a behaviour on the global scale which can be regarded as that of a traditional feedback controller. |
