A mathematical analysis of the scattered decomposition
John K. Salmon · 1988
A theoretical basis for the scattered decomposition is worked out in some detail. The basic result has been part of the “folklore” for some time, but has never been proved. The load imbalance expected from a scattered decomposition of a set of computational tasks is proportional n-1/2σtask/mtask where n is the number of tasks assigned to each processor, mtask is the mean time per task and σtask is the root mean square deviation time per task. The constant of proportionality is of O(1), and is a very slowly increasing function of the number of processors.