Scheduling for PseudoThreading

Every time we enter the advance network - we would like to know how long to spend before returning to perform the collective operations that occur following the completion of each advance. Since it is possible that some processors will only have finest level data - it makes sense to synchronize as soon as they are done. First let's define the work load assigned to each processor p, for each level l amd substep s as w_{p,s}^l where s counts the number of advances on a given level since the last root grid step. So on a given level l, s will in general go from 1 to 2^l where L is the max level of refinement.

Before any synchronization event on level l, all of the advances on lower levels will have needed to complete. We can define the work load each processor needs to do before a particular synchronization event following the s^{th} advance on level l as…

begin{equation} W^l_{p,s}=\displaystyle{ \sum_{i=1}^s \left [ \sum_{j=l}^L \left [ \sum_{k=1}^{2^{j-l}} w^j_{p,[(i-1) \times 2^{(j-l)}+k]} \right ] \right ] } \end{equation}

We can also define the earliest completion of any of these advances as

begin{equation} T^l_s=\displaystyle{\max_p (W^l_{p,s})} \end{equation}

Or equivalently

begin{displaymath} \Delta T^l_s = \left\{ \begin{array}{lr} T^l_s - T^{l+1}_{2s} & : l < L\\ T^l_s-T^l_{s-1} & : l = L \end{array} \right. \end{displaymath}

where \Delta T^l_s is the additional time before we can synchronize the current step after having synchronized the previously completed step.

If Advances were the only thing that took time any time, we could just collectively calculate these times and use them as the wall times to return from the advance web…, Unfortunately other stages of the algorithm can lead to advances not beginning at the same time - so some form of synchronization should happen before each advance.

If we need to synchronize these wall times then it makes the most sense to do so as late as possible to be as accurate as possible. And all that we need to synchronize these times is the current remaining workload left for this step. If each processor stored the amount of work that it had already performed during higher level advances a^l_s then

begin{equation} \Delta T^l_s=\displaystyle \max_p(w^l_{p,s}-a^l_{p,s}) \end{equation}