Dynamic Versus Static Load Balancing In A Pipeline Computation
Anna Brunström, Rahul Simha · International Journal of Modelling and Simulation · 1997
We examine load balancing in a simple pipeline computation, in which a large number of data sets is pipelined through a series of tasks and load balancing is performed by distributing several available processors among the tasks. We compare the performance of the optimal static processor assignment to the performances of three dynamic processor assignment algorithms. Models are derived that allow us to approximate the performance of the dynamic algorithms theoretically. The relative performances of the algorithms are investigated for various amounts of overhead, using a combination of modelling and simulation. We indicate that an appropriate dynamic algorithm can improve performance even when the overhead induced by the algorithm is relatively high.