Context Navigation

← Previous Post
Next Post →

Load balancing algorithm

I made some minor adjustments to the load balancing algorithm to match the description in the paper and the initial results are encouraging… Now the threading / dynamic load balancing is 10% faster on 8 cores… Need to do some scaling runs on 32 / 64 to confirm that this trend persists. Also trying to figure out the right functional form to fit the scaling data.

Weak Scaling

Weak scaling results for various levels of AMR for 128² cells per proc per level

And the weak scaling results for 3 levels of AMR with 64², 128², and 512² cells per proc per level

If we let C represent the total number of cells to update, and \alpha represent the computational cost per cell and X be the additional computational work that is incurred with N processors, and let R be the wall time then

begin{eqnarray} NR&=&\alpha C+X \nonumber \\ \frac{NR}{C}&=&\alpha+\frac{X}{C}=\alpha (1+\frac{X}{\alpha C} )\nonumber \\ \end{eqnarray}

Furthermore if \frac{NR}{C} = \alpha N^\beta then for \beta << 1 we can taylor expand N^\beta=1+\beta \ln(N) + \frac{\beta^2}{2!} \ln(N) + ... which combined with the scaling results gives

begin{eqnarray} \frac{X}{\alpha C}&=&\beta \ln(N) \nonumber \\ X&=&\beta \alpha C \ln(N) \nonumber \\ X&=&\beta W \ln(N) \mbox{ where W is the total computational work load} \nonumber \\ \end{eqnarray}

Also \frac{X+W}{W} = 1+\beta \ln(N) = 2 \mbox{ for } N=\exp^\frac{1}{\beta} = 360000

However, if we assume that \frac{X+W}{W} = \alpha N^\beta then \frac{X+W}{W}=N^\beta=2 \mbox {for } N=\exp^\frac{\ln 2}{\beta}=7233

The problem is we don't have enough data points to determine which functional fit is accurate so it is difficult to project.

So I went back and looked at different possible fit functions and plotted the results…

The best fit is the first one y=a(1+b\ln(x)) and if it holds, implies performance drops to 50% at N=1781 or 1.74 KProcs and to 25% at 5.3 GProcs! Granted this is weak scaling and your resolution at 5.3 GProcs would be 36 MCells² and simulating one crossing time would take 12 yrs instead of 3 yrs… but that's why strong scaling is more important… or being able to weakly scale when the workload per processor is only a few cells.

Why would the scaling be proportional to 1+\ln{N}? If we consider the distribution of grids at each time step and assume that the workload distribution W_i follows a normal distribution with some standard deviation \sigma, then the time to complete each step is not given by the mean of the workload \overline{W} but by the max of the workload \max{W}. The average maximum value is given by the last order statistic W_{(N)} where N is the number of processors. I couldn't find an expression for the last order statistic for a normal distribution, but monte-carlo experiments give a fitting function \frac{W_{(N)}}{\overline{W}}=.806\ln{N}^{.692}\frac{\sigma}{\overline{W}}. Given the best fit this implies that \frac{\sigma}{W} \approx .16

Posted: 13 years ago (Updated: 13 years ago)
Author: Jonathan
Categories: (none)

Attachments (6)

Scaling1.png (24.6 KB) - added by Jonathan 13 years ago.
Scaling2.png (27.4 KB) - added by Jonathan 13 years ago.
scaling1.png (7.4 KB) - added by Jonathan 13 years ago.
scaling2.png (6.9 KB) - added by Jonathan 13 years ago.
scaling3.png (7.3 KB) - added by Jonathan 13 years ago.
scaling4.png (7.5 KB) - added by Jonathan 13 years ago.

astrobear

Context Navigation

Load balancing algorithm

Weak Scaling

Attachments (6)

Comments

Download in other formats: